對於定時器事件,Libevent采用兩種方法處理定時器:
1、定時器尾隊列
2、時間堆
在event結構體中,定義了聯合體類型ev_timeout_pos來指明定時器的位置
//僅用於定時事件處理器:當為通過定時器時,ev_next_with_common_timeout指向定時器隊列中的位置
//當為其它定時器時,min_heap_idx為指向時間堆中的索引
union {
TAILQ_ENTRY(event) ev_next_with_common_timeout;
int min_heap_idx;
} ev_timeout_pos;
開發者認為有時候使用簡單的鏈表(通用定時器)來管理定時器將具有更高的效率。如下所述:
當需要獲取多個具有同一超時值的定時器時,定時器鏈表比時間堆效率更高,此處個人理解為:若超時時間相同,在定時器鏈表中,可以通過順序遍歷的方法獲取超時的定時器,而采用時間堆的話,每獲取一個定時器需要維護堆,時間復雜度為nlogn。
一個定時器是否是通用定時器取決於其超時值(超時值由具體超時值、幻數5以及定時器索引組成),具體由is_common_timeout函數決定:
/* Common timeouts are special timeouts that are handled as queues rather than
* in the minheap. This is more efficient than the minheap if we happen to
* know that we're going to get several thousands of timeout events all with
* the same timeout value.
*
* Since all our timeout handling code assumes timevals can be copied,
* assigned, etc, we can't use "magic pointer" to encode these common
* timeouts. Searching through a list to see if every timeout is common could
* also get inefficient. Instead, we take advantage of the fact that tv_usec
* is 32 bits long, but only uses 20 of those bits (since it can never be over
* 999999.) We use the top bits to encode 4 bites of magic number, and 8 bits
* of index into the event_base's aray of common timeouts.
*/
#define MICROSECONDS_MASK COMMON_TIMEOUT_MICROSECONDS_MASK
#define COMMON_TIMEOUT_IDX_MASK 0x0ff00000
#define COMMON_TIMEOUT_IDX_SHIFT 20
#define COMMON_TIMEOUT_MASK 0xf0000000
#define COMMON_TIMEOUT_MAGIC 0x50000000
#define COMMON_TIMEOUT_IDX(tv) \
(((tv)->tv_usec & COMMON_TIMEOUT_IDX_MASK)>>COMMON_TIMEOUT_IDX_SHIFT)
/** Return true iff if 'tv' is a common timeout in 'base' */
static inline int
is_common_timeout(const struct timeval *tv,
const struct event_base *base)
{
int idx;
if ((tv->tv_usec & COMMON_TIMEOUT_MASK) != COMMON_TIMEOUT_MAGIC)
return 0;
idx = COMMON_TIMEOUT_IDX(tv);
return idx < base->n_common_timeouts;
}
32位定時值tv->tv_usec高四位為幻數,該定時器的幻數不等於0101b時,定時器是時間堆定時器;
idx = COMMON_TIMEOUT_IDX取出定時器的20-27位(由於定時器不超過999999,只用了0-19位,因此20-31位可以用於鋪助功能,這個是個編程技巧),判斷idx < Reactor對象中的n_common_timeouts,該變量保存了當前Reactor對象中通用定時器隊列的長度,若idx在長度范圍內,則為通用定時器,否則為時間堆定時器。
使用libevent編寫Linux服務 http://www.linuxidc.com/Linux/2011-09/43321.htm
Linux下安裝配置MemCached(以及libevent) http://www.linuxidc.com/Linux/2011-08/41868.htm