轉載自:http://blog.sina.com.cn/s/blog_77c6324101018j1k.html
最近在看LIVE555的源碼，對其中的延時隊列感覺有點亂，網上查詢資料，于是就總結一下。
首先描述一下LIVE555中的延時隊列的設計理念。如下圖，A,B,C分別為時間軸上的三個事件點，而head表示當前時間點。
要描述一個事件發生的時間，通常可以有兩種方法：一種方法直接描述事件發生的絕對時間；另一種方法則是可以描述和另一事件發生的相對時間。而LIVE555中采用的就是后者。
在LIVE555中，首先將所有的事件點以發生時間的先后進行排序，然后每個事件對應的時間都是相對于前一事件發生的時間差。比如B事件中存儲的時間就是A事件觸發后，再去觸發B事件所需要的時間。這樣，我們每次去查詢這個隊列中是否有事件被觸發的時候，就只需要查詢整個隊列中的第一個事件就可以了。
然后就是LIVE555中的實現方法了。整個延時隊列是用DelayQueue這個類實現的，而它的基類DelayQueueEntry就是用來描述每個事件節點的。在DelayQueueEntry中的主要成員有以下幾個：fDelayTimeRemaining表示的就是與前一事件之間的時間差；fNext和fPrev就是指向時間軸上的下一個事件和前一個事件的指針；ftoken表示當前節點的標識；handleTimeout就是事件超時后的處理方法。
而DelayQueue類里描述的則是具體的實現方法。首先是一些對這個隊列進行的基本操作：addEntry實現的是在隊列中增加事件節點；removeEntry實現的是在隊列中刪除某事件節點；updateEntry實現的則是更新某事件的觸發時間；而findEntryByToken則是根據節點的標識查找相應的事件。在此類中最常用的方法應該是synchronize，它實現的就是將整個事件隊列和當前系統時間進行同步，檢測有無事件已經被觸發，如果觸發并調用handleAlarm方法對相應事件進行處理。而屬性fLastSyncTime表示的就是上次同步的系統時間，其實一般情況下，方法synchronize的實現方法其實就是簡單地把隊列上第一個事件節點存儲的時間差減去當前系統時間和上次同步時間的差。
附：相關類結構：
=================================================================
==> 相關typedef定義
typedef void TaskFunc(void* clientData);
typedef void* TaskToken;
// 下面Timeval類有涉及
#ifdef TIME_BASE
typedef TIME_BASE time_base_seconds;
#else
typedef long time_base_seconds;
#endif
==> 相關類的說明（由于有些類很大，故不會完整貼出，故用說明）
///// A "Timeval" can be either an absolute time, or a time interval /////
class Timeval {
public:
time_base_seconds seconds() const {
return fTv.tv_sec;
}
time_base_seconds seconds() {
return fTv.tv_sec;
}
time_base_seconds useconds() const {
return fTv.tv_usec;
}
int operator>=(Timeval const& arg2) const; // 以>=為基礎，推算出其余條件判斷（<=、<</span>、>等）的真假
int operator<=(Timeval const& arg2) const {
return arg2 >= *this;
}
int operator<</b>(Timeval const& arg2) const {
return !(*this >= arg2);
}
int operator>(Timeval const& arg2) const {
return arg2 < *this;
}
int operator==(Timeval const& arg2) const {
return *this >= arg2 && arg2 >= *this;
}
int operator!=(Timeval const& arg2) const {
return !(*this == arg2);
}
void operator+=(class DelayInterval const& arg2);
void operator-=(class DelayInterval const& arg2);
// returns ZERO iff arg2 >= arg1
protected:
Timeval_r(time_base_seconds seconds, time_base_seconds useconds) {
fTv.tv_sec = seconds; fTv.tv_usec = useconds;
}
private:
time_base_seconds& secs() {
return (time_base_seconds&)fTv.tv_sec;
}
time_base_seconds& usecs() {
return (time_base_seconds&)fTv.tv_usec;
}
struct timeval fTv; // 看到，所有的所有，其實是在為timeval這個結構體封裝了一系列操作函數
};
++++++++++++++++++++++++++++++++++++++++++
// 下面這個類用以處理自1970年1月1日以來的絕對時間
class EventTime: public Timeval {
public:
EventTime(unsigned secondsSinceEpoch = 0,
unsigned usecondsSinceEpoch = 0)
// We use the Unix standard epoch: January 1, 1970
: Timeval_r(secondsSinceEpoch, usecondsSinceEpoch) {}
};
class DelayQueueEntry { // 通過它來鏈接所有的事件信息，組成隊列（見下面DelayQueue類）
public:
virtual ~DelayQueueEntry();
intptr_t token() {
return fToken;
}
protected: // abstract base class
DelayQueueEntry(DelayInterval delay);
virtual void handleTimeout();
private:
friend class DelayQueue;
DelayQueueEntry* fNext;
DelayQueueEntry* fPrev;
DelayInterval fDeltaTimeRemaining;
intptr_t fToken;
static intptr_t tokenCounter;
};
class DelayQueue: public DelayQueueEntry {
public:
DelayQueue();
virtual ~DelayQueue();
void addEntry(DelayQueueEntry* newEntry); // returns a token for the entry
void updateEntry(DelayQueueEntry* entry, DelayInterval newDelay);
void updateEntry(intptr_t tokenToFind, DelayInterval newDelay);
void removeEntry(DelayQueueEntry* entry); // but doesn't delete it
DelayQueueEntry* removeEntry(intptr_t tokenToFind); // but doesn't delete it
DelayInterval const& timeToNextAlarm();
void handleAlarm();
private:
DelayQueueEntry* head() { return fNext; } // 返回DelayQueueEntry類中的fNext隊頭成員
DelayQueueEntry* findEntryByToken(intptr_t token);
void synchronize(); // bring the 'time remaining' fields up-to-date
EventTime fLastSyncTime;
};
////////// A subclass of DelayQueueEntry,
////////// used to implement BasicTaskScheduler0::scheduleDelayedTask()
class AlarmHandler: public DelayQueueEntry {
public:
AlarmHandler(TaskFunc* proc, void* clientData, DelayInterval timeToDelay)
: DelayQueueEntry(timeToDelay), fProc(proc), fClientData(clientData) {
}
private: // redefined virtual functions
virtual void handleTimeout() {
(*fProc)(fClientData);
DelayQueueEntry::handleTimeout();
}
private:
TaskFunc* fProc;
void* fClientData;
};