在后端的開(kāi)發(fā)中，定時(shí)器有很廣泛的應(yīng)用。

比如：

心跳檢測(cè)

倒計(jì)時(shí)

游戲開(kāi)發(fā)的技能冷卻

redis的鍵值的有效期等等，都會(huì)使用到定時(shí)器。

定時(shí)器的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)選擇

紅黑樹(shù)

對(duì)于增刪查，時(shí)間復(fù)雜度為O(logn)，對(duì)于紅黑樹(shù)最?節(jié)點(diǎn)為最左側(cè)節(jié)點(diǎn)，時(shí)間復(fù)雜度O(logn)

最小堆

對(duì)于增查，時(shí)間復(fù)雜度為O(logn)，對(duì)于刪時(shí)間復(fù)雜度為O(n)，但是可以通過(guò)輔助數(shù)據(jù)結(jié)構(gòu)（ map 或者h(yuǎn)ashtable來(lái)快速索引節(jié)點(diǎn)）來(lái)加快刪除操作；對(duì)于最?節(jié)點(diǎn)為根節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(1)

跳表

對(duì)于增刪查，時(shí)間復(fù)雜度為O(logn)，對(duì)于跳表最?節(jié)點(diǎn)為最左側(cè)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(1)，但是空間復(fù)雜度?較?，為O(1.5n)

時(shí)間輪

對(duì)于增刪查，時(shí)間復(fù)雜度為O(1)，查找最?節(jié)點(diǎn)也為O(1)

libco的使用了時(shí)間輪的實(shí)現(xiàn)

首先，時(shí)間輪有幾個(gè)結(jié)構(gòu)，必須理清他們的關(guān)系。

struct stTimeoutItem_t
{
	enum { eMaxTimeout = 40 * 1000 };	// 40s
	stTimeoutItem_t* pPrev;				// 前
	stTimeoutItem_t* pNext;				// 后
	stTimeoutItemLink_t* pLink;			// 鏈表，沒(méi)有用到，寫(xiě)這里有毛用

	OnPreparePfn_t pfnPrepare;			// 不是超時(shí)的事件的處理函數(shù)
	OnProcessPfn_t pfnProcess;			// resume協(xié)程回調(diào)函數(shù)

	void* pArg;							// routine 協(xié)程對(duì)象指針
	bool bTimeout;						// 是否超時(shí)
	unsigned long long ullExpireTime;	// 到期時(shí)間
};

struct stPoll_t;
struct stPollItem_t : public stTimeoutItem_t
{
	struct pollfd* pSelf;			// 對(duì)應(yīng)的poll結(jié)構(gòu)
	stPoll_t* pPoll;				// 所屬的stPoll_t
	struct epoll_event stEvent;		// epoll事件，poll轉(zhuǎn)換過(guò)來(lái)的
};

// co_poll_inner 創(chuàng)建，管理這多個(gè)stPollItem_t
struct stPoll_t : public stTimeoutItem_t
{
	struct pollfd* fds;				// poll 的fd集合
	nfds_t nfds;					// poll 事件個(gè)數(shù)
	stPollItem_t* pPollItems;		// 要加入epoll 事件
	int iAllEventDetach;			// 如果處理過(guò)該對(duì)象的子項(xiàng)目pPollItems，賦值為1
	int iEpollFd;					// epoll fd句柄
	int iRaiseCnt;					// 此次觸發(fā)的事件數(shù)
};

我把這幾個(gè)結(jié)構(gòu)拉一起了，

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

// TimeoutItem的鏈表
struct stTimeoutItemLink_t
{
	stTimeoutItem_t* head;
	stTimeoutItem_t* tail;
};

// TimeOut 
struct stTimeout_t	// 時(shí)間倫
{
	stTimeoutItemLink_t* pItems;	// 時(shí)間輪鏈表，開(kāi)始初始化分配只一圈的長(zhǎng)度，后續(xù)直接使用
	int iItemSize;					// 超時(shí)鏈表中一圈的tick 60*1000
	unsigned long long ullStart;	// 時(shí)間輪開(kāi)始時(shí)間，會(huì)一直變化
	long long llStartIdx;			// 時(shí)間輪開(kāi)始的下標(biāo)，會(huì)一直變化
};

// epoll 結(jié)構(gòu)
struct stCoEpoll_t
{
	int iEpollFd;
	static const int _EPOLL_SIZE = 1024 * 10;
	struct stTimeout_t* pTimeout;					// epoll 存著時(shí)間輪
	struct stTimeoutItemLink_t* pstTimeoutList;		// 超時(shí)事件鏈表
	struct stTimeoutItemLink_t* pstActiveList;		// 用于signal時(shí)會(huì)插入
	co_epoll_res* result;
};

也就是說(shuō)，一個(gè)協(xié)程，就有一個(gè)，在co_init_curr_thread_env 中創(chuàng)建

它管理著超時(shí)鏈表，信號(hào)事件鏈表

其中的pTimeout，就是時(shí)間輪，也就是一個(gè)數(shù)組，這個(gè)數(shù)組的大小位60*1000

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

這就是分配的時(shí)間輪的方法，首先指定了下標(biāo)時(shí)間等信息，根據(jù)結(jié)構(gòu)注釋?xiě)?yīng)該不難懂

// apTimeout：時(shí)間輪
// apItem: 某一個(gè)定時(shí)item
// allNow：當(dāng)前的時(shí)間
// 函數(shù)目的，將超時(shí)項(xiàng)apItem加入到apTimeout
int AddTimeout( stTimeout_t *apTimeout, stTimeoutItem_t *apItem ,unsigned long long allNow )
{
// 這個(gè)判斷有點(diǎn)多余，start正常已經(jīng)分配了
if( apTimeout->ullStart == 0 )
{
apTimeout->ullStart = allNow;
apTimeout->llStartIdx = 0;
}
// 當(dāng)前時(shí)間也不大可能比前面的時(shí)間大
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__;
}
// 到期時(shí)間到start的時(shí)間差
unsigned long long diff = apItem- >ullExpireTime - apTimeout- >ullStart;
// itemsize 實(shí)際上是毫秒數(shù)，如果超出了，說(shuō)明設(shè)置的超時(shí)時(shí)間過(guò)長(zhǎng)
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;

}

其實(shí)，這里有個(gè)概念，stTimeoutItemLink_t 與stTimeoutItem_t，也就是說(shuō)，stTimeout_t里面管理的時(shí)60*1000個(gè)鏈表，而每個(gè)鏈表有一個(gè)或者多個(gè)stTimeoutItem_t，下面這個(gè)函數(shù)，就是把節(jié)點(diǎn)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)

到這里，基本把一個(gè)超時(shí)事件添加到時(shí)間輪中了，這時(shí)就應(yīng)該切換協(xié)程了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;
}

接下來(lái)，看怎么檢測(cè)超時(shí)事件co_eventloop

for(;;)
{
// 等待事件或超時(shí)1ms
int ret = co_epoll_wait( ctx->iEpollFd,result,stCoEpoll_t::_EPOLL_SIZE, 1 );

//  遍歷所有ret事件處理
	for(int i=0;i< ret;i++)
	{
		pfnPrepare(xxx)
	}

	// 取出所有的超時(shí)時(shí)間item，設(shè)置為超時(shí)
	TakeAllTimeout( ctx- >pTimeout, now, plsTimeout );
	stTimeoutItem_t *lp = plsTimeout- >head;
	while( lp )
	{
		lp- >bTimeout = true;
		lp = lp- >pNext;
	}

	// 將超時(shí)鏈表plsTimeout加入到plsActive
	Join< stTimeoutItem_t, stTimeoutItemLink_t >( plsActive, plsTimeout );
	lp = plsActive- >head;
	while( lp )
	{
        // 彈出鏈表頭，處理超時(shí)事件
		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 才需要切協(xié)程，要切回去了
		if( lp- >pfnProcess )
		{
			lp- >pfnProcess( lp );
		}
		lp = plsActive- >head;
	}

	// 如果傳入該函數(shù)指針，則可以控制event_loop 退出
	if( pfn )
	{
		if( -1 == pfn( arg ) )
		{
			break;
		}
	}
}

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