比如：

心跳檢測

倒計時

遊戲開發的技能冷卻

Redis的鍵值的有效期等等，都會使用到定時器。

紅黑樹

對于增删查，時間複雜度為O(logn)，對于紅黑樹最⼩節點為最左側節點，時間複雜度O(logn)

最小堆

對于增查，時間複雜度為O(logn)，對于删時間複雜度為O(n)，但是可以通過輔助數據結構（ map 或者hashtable來快速索引節點）來加快删除操作；對于最⼩節點為根節點，時間複雜度為O(1)

跳表

對于增删查，時間複雜度為O(logn)，對于跳表最⼩節點為最左側節點，時間複雜度為O(1)，但是空間複雜度⽐較⾼，為O(1.5n)

時間輪

對于增删查，時間複雜度為O(1)，查找最⼩節點也為O(1)

首先，時間輪有幾個結構，必須理清他們的關系。

struct stTimeoutItem_t { enum { eMaxTimeout = 40 * 1000 }; // 40s stTimeoutItem_t* pPrev; // 前 stTimeoutItem_t* pNext; // 後 stTimeoutItemLink_t* pLink; // 鍊表，沒有用到，寫這裡有毛用 OnPreparePfn_t pfnPrepare; // 不是超時的事件的處理函數 OnProcessPfn_t pfnProcess; // resume協程回調函數 void* pArg; // routine 協程對象指針 bool bTimeout; // 是否超時 unsigned long long ullExpireTime; // 到期時間 }; struct stPoll_t; struct stpollItem_t : public stTimeoutItem_t { struct pollfd* pSelf; // 對應的poll結構 stPoll_t* pPoll; // 所屬的stPoll_t struct epoll_event stEvent; // epoll事件，poll轉換過來的 }; // co_poll_inner 創建，管理這多個stPollItem_t struct stPoll_t : public stTimeoutItem_t { struct pollfd* fds; // poll 的fd集合 nfds_t nfds; // poll 事件個數 stPollItem_t* pPollItems; // 要加入epoll 事件 int iAllEventDetach; // 如果處理過該對象的子項目pPollItems，賦值為1 int iepollFd; // epoll fd句柄 int iRaiseCnt; // 此次觸發的事件數 };

我把這幾個結構拉一起了，

其中，能看出，stCoEpool_t管理了這一切

// TimeoutItem的鍊表 struct stTimeoutItemLink_t { stTimeoutItem_t* head; stTimeoutItem_t* tail; }; // TimeOut struct stTimeout_t // 時間倫 { stTimeoutItemLink_t* pItems; // 時間輪鍊表，開始初始化分配隻一圈的長度，後續直接使用 int iItemSize; // 超時鍊表中一圈的tick 60*1000 unsigned long long ullStart; // 時間輪開始時間，會一直變化 long long llStartIdx; // 時間輪開始的下标，會一直變化 }; // epoll 結構 struct stCoEpoll_t { int iEpollFd; static const int _EPOLL_SIZE = 1024 * 10; struct stTimeout_t* pTimeout; // epoll 存着時間輪 struct stTimeoutItemLink_t* pstTimeoutList; // 超時事件鍊表 struct stTimeoutItemLink_t* pstActiveList; // 用于signal時會插入 co_epoll_res* result; };

也就是說，一個協程，就有一個，在co_init_curr_thread_env 中創建

它管理着超時鍊表，信号事件鍊表

其中的pTimeout，就是時間輪，也就是一個數組，這個數組的大小位60*1000

stTimeout_t *AllocTimeout( int iSize ) { stTimeout_t *lp = (stTimeout_t*)calloc( 1,sizeof(stTimeout_t) ); lp->iItemSize = iSize; // 注意這裡先把item分配好了，後續直接使用 lp->pItems = (stTimeoutItemLink_t*)calloc( 1, sizeof(stTimeoutItemLink_t) * lp->iItemSize ); lp->ullStart = GetTickMS(); lp->llStartIdx = 0; return lp; }

這就是分配的時間輪的方法，首先指定了下标時間等信息，根據結構注釋應該不難懂

相關視頻推薦

紅黑樹、最小堆、時間輪、跳表多種方式實現定時器

協程！協程！協程！給你一個吊打面試官的機會

協程在 reactor 網絡模型中的應用

需要C/C Linux服務器架構師學習資料加qun812855908獲取（資料包括C/C ，Linux，golang技術，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg等），免費分享

​有了這些後，再來看看時怎麼添加超時事件的

// apTimeout：時間輪 // apItem: 某一個定時item // allNow：當前的時間 // 函數目的，将超時項apItem加入到apTimeout int AddTimeout( stTimeout_t *apTimeout, stTimeoutItem_t *apItem ,unsigned long long allNow ) { // 這個判斷有點多餘，start正常已經分配了 if( apTimeout->ullStart == 0 ) { apTimeout->ullStart = allNow; apTimeout->llStartIdx = 0; } // 當前時間也不大可能比前面的時間大 if( allNow < apTimeout->ullStart ) { co_log_err("CO_ERR: AddTimeout line %d allNow %llu apTimeout->ullStart %llu", __LINE__,allNow,apTimeout->ullStart); return __LINE__; } if( apItem->ullExpireTime < allNow ) { co_log_err("CO_ERR: AddTimeout line %d apItem->ullExpireTime %llu allNow %llu apTimeout->ullStart %llu", __LINE__,apItem->ullExpireTime,allNow,apTimeout->ullStart); return __LINE__; } // 到期時間到start的時間差 unsigned long long diff = apItem->ullExpireTime - apTimeout->ullStart; // itemsize 實際上是毫秒數，如果超出了，說明設置的超時時間過長 if( diff >= (unsigned long long)apTimeout->iItemSize ) { diff = apTimeout->iItemSize - 1; co_log_err("CO_ERR: AddTimeout line %d diff %d", __LINE__,diff); //return __LINE__; } // 将apItem加到末尾 AddTail( apTimeout->pItems ( apTimeout->llStartIdx diff ) % apTimeout->iItemSize , apItem ); return 0; }

其實，這裡有個概念，stTimeoutItemLink_t 與stTimeoutItem_t，也就是說，stTimeout_t裡面管理的時60*1000個鍊表，而每個鍊表有一個或者多個stTimeoutItem_t，下面這個函數，就是把節點Item加入到鍊表的方法。

template <class TNode,class TLink> void inline AddTail(TLink*apLink, TNode *ap) { if( ap->pLink ) { return ; } if(apLink->tail) { apLink->tail->pNext = (TNode*)ap; ap->pNext = NULL; ap->pPrev = apLink->tail; apLink->tail = ap; } else { apLink->head = apLink->tail = ap; ap->pNext = ap->pPrev = NULL; } ap->pLink = apLink; }

​到這裡，基本把一個超時事件添加到時間輪中了，這時就應該切換協程了co_yield_env

int ret = AddTimeout( ctx->pTimeout, &arg, now ); int iRaiseCnt = 0; if( ret != 0 ) { co_log_err("CO_ERR: AddTimeout ret %d now %lld timeout %d arg.ullExpireTime %lld", ret,now,timeout,arg.ullExpireTime); errno = EINVAL; iRaiseCnt = -1; } else { co_yield_env( co_get_curr_thread_env() ); iRaiseCnt = arg.iRaiseCnt; }

接下來，看怎麼檢測超時事件co_eventloop

for(;;) { // 等待事件或超時1ms int ret = co_epoll_wait( ctx->iEpollFd,result,stCoEpoll_t::_EPOLL_SIZE, 1 ); // 遍曆所有ret事件處理 for(int i=0;i<ret;i ) { pfnPrepare(xxx) } // 取出所有的超時時間item，設置為超時 TakeAllTimeout( ctx->pTimeout, now, plsTimeout ); stTimeoutItem_t *lp = plsTimeout->head; while( lp ) { lp->bTimeout = true; lp = lp->pNext; } // 将超時鍊表plsTimeout加入到plsActive Join<stTimeoutItem_t, stTimeoutItemLink_t>( plsActive, plsTimeout ); lp = plsActive->head; while( lp ) { // 彈出鍊表頭，處理超時事件 PopHead<stTimeoutItem_t,stTimeoutItemLink_t>( plsActive ); if (lp->bTimeout && now < lp->ullExpireTime) { int ret = AddTimeout(ctx->pTimeout, lp, now); if (!ret) { lp->bTimeout = false; lp = plsActive->head; continue; } } // 隻有stPool_t 才需要切協程，要切回去了 if( lp->pfnProcess ) { lp->pfnProcess( lp ); } lp = plsActive->head; } // 如果傳入該函數指針，則可以控制event_loop 退出 if( pfn ) { if( -1 == pfn( arg ) ) { break; } } }

其中包括了定時事件處理，協程切換，主協程退出等操作。如果設置了主協程退出函數，則主協程可以正常的退出。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!