很多程序都需要處理一系列定時(shí)事件，一個(gè)Timer程序就是實(shí)現(xiàn)定時(shí)事件集合的管理。
每個(gè)timer事件項(xiàng)一般包括超時(shí)值(delay), 標(biāo)識(shí)(key)和回調(diào)函數(shù)，Timer程序的作用就是實(shí)現(xiàn)插入，刪除，更新和調(diào)用。
方法1. 鏈表
最簡(jiǎn)單的實(shí)現(xiàn)是有序鏈表。list_head保存到當(dāng)前時(shí)間的剩余時(shí)間remain_time，后一節(jié)點(diǎn)保存與前一節(jié)點(diǎn)的超時(shí)時(shí)間的差(而不是到當(dāng)前時(shí)間的差)。
更新：每次tick update時(shí)，只需要更新鏈表頭節(jié)點(diǎn)remain_time，如果remain_time <= 0, 調(diào)用函數(shù)，刪除該頭節(jié)點(diǎn)，然后更新后一個(gè)節(jié)點(diǎn)的remain_time,如此類(lèi)推直到頭結(jié)點(diǎn)remain_time > 0或鏈表為空. O(1)
插入：相當(dāng)于插入排序。有序插入到適當(dāng)位置，更新后一個(gè)節(jié)點(diǎn)的remain_time.
刪除：遍歷鏈表搜索，刪除節(jié)點(diǎn)，更新后一個(gè)節(jié)點(diǎn)的remain_time.
例子：live555流媒體服務(wù)器
方法2. 最小堆(優(yōu)先隊(duì)列)
方法與鏈表類(lèi)似，插入/刪除效率從O(n)變?yōu)镺(lgN)
libevent中有min-heap實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列，根節(jié)點(diǎn)是最先觸發(fā)的超時(shí)時(shí)間, 與方法1一樣，只需更新根節(jié)點(diǎn)。根節(jié)點(diǎn)超時(shí)后，調(diào)整堆即可
方法3. Hash或分級(jí)
根據(jù)超時(shí)值的范圍(比如CPU的流逝ticks)進(jìn)行hash，hash后每個(gè)bucket實(shí)現(xiàn)方法1所示的鏈表. 較方法1減少了搜索次數(shù)
例子：MudOS定時(shí)器
方法4. 分級(jí)hash
這是linux內(nèi)核timer的實(shí)現(xiàn)方法，值得參考。見(jiàn)文獻(xiàn)[1]
方法：假設(shè)定時(shí)值以tick為單位，每tick更新timer一次。
定時(shí)值范圍為0 ~ 2^32個(gè)tick(32個(gè)bit), 則把他分成4級(jí)，每級(jí)做一個(gè)hash, 每個(gè)則有256個(gè)bucket (剛好8bit)
000000000 00000000 00000000 00000000
--------- -------- -------- --------
A B C D
插入：算出 tick_trig = delay + 當(dāng)前tick， mask = tick_trig & 0xFF000000，
如果mask不等于0，在A hash表插入timer項(xiàng), 否則進(jìn)入下一級(jí)，mask = tick_trig & 0x00FF0000, 插入B hash表，如此類(lèi)推。
更新：每次tick++, 先檢查D hash表(最低8位的與操作)有無(wú)timer項(xiàng)，如果有，執(zhí)行函數(shù)并刪除。
如果tick滿(mǎn)255進(jìn)位， 則檢查C hash表中對(duì)應(yīng)位置有否timer項(xiàng)，如果有，重新插入(此處的timer項(xiàng)必定會(huì)插入D hash表中)，如此類(lèi)推
這樣，插入，更新，刪除都做到O(1)了
疑惑：這個(gè)方法用于內(nèi)核級(jí)程序。對(duì)于用戶(hù)級(jí)程序，每次update的間隔不恒定（即每次tick不一定是+1），這時(shí)需要掃描tick之前的幾個(gè)bucket了
參考文獻(xiàn)
[1] George Varghese
, Tony Lauck. Hashed and
Hierarchical Timing Wheels:
Efficient Data Structures for Implementing a Timer Facility
(1996)
[2] libevent 源碼
[3] <understanding linux kernel 3rd ed>
[4] MudOS 源碼