在后端的開發中，定時器有很廣泛的應用。

比如：

心跳檢測

倒計時

游戲開發的技能冷卻

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

定時器的實現數據結構選擇

紅黑樹

對于增刪查，時間復雜度為O(logn)，對于紅黑樹最?節點為最左側節點，時間復雜度O(logn)

最小堆

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

跳表

對于增刪查，時間復雜度為O(logn)，對于跳表最?節點為最左側節點，時間復雜度為O(1)，但是空間復雜度?較?，為O(1.5n)

時間輪

對于增刪查，時間復雜度為O(1)，查找最?節點也為O(1)

libco的使用了時間輪的實現

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

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;
}

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

// 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
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;
}

![圖片](//file1.elecfans.com/web2/M00/AD/ED/wKgaomVRwIaAdU0AAADdUXMLTLQ483.jpg)

到這里，基本把一個超時事件添加到時間輪中了，這時就應該切換協程了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;
		}
	}
}

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