轉(zhuǎn)載自:http://blog.sina.com.cn/s/blog_77c6324101018j1k.html
最近在看LIVE555的源碼，對其中的延時(shí)隊(duì)列感覺有點(diǎn)亂，網(wǎng)上查詢資料，于是就總結(jié)一下。
首先描述一下LIVE555中的延時(shí)隊(duì)列的設(shè)計(jì)理念。如下圖，A,B,C分別為時(shí)間軸上的三個(gè)事件點(diǎn)，而head表示當(dāng)前時(shí)間點(diǎn)。
要描述一個(gè)事件發(fā)生的時(shí)間，通常可以有兩種方法：一種方法直接描述事件發(fā)生的絕對時(shí)間；另一種方法則是可以描述和另一事件發(fā)生的相對時(shí)間。而LIVE555中采用的就是后者。
在LIVE555中，首先將所有的事件點(diǎn)以發(fā)生時(shí)間的先后進(jìn)行排序，然后每個(gè)事件對應(yīng)的時(shí)間都是相對于前一事件發(fā)生的時(shí)間差。比如B事件中存儲(chǔ)的時(shí)間就是A事件觸發(fā)后，再去觸發(fā)B事件所需要的時(shí)間。這樣，我們每次去查詢這個(gè)隊(duì)列中是否有事件被觸發(fā)的時(shí)候，就只需要查詢整個(gè)隊(duì)列中的第一個(gè)事件就可以了。
然后就是LIVE555中的實(shí)現(xiàn)方法了。整個(gè)延時(shí)隊(duì)列是用DelayQueue這個(gè)類實(shí)現(xiàn)的，而它的基類DelayQueueEntry就是用來描述每個(gè)事件節(jié)點(diǎn)的。在DelayQueueEntry中的主要成員有以下幾個(gè)：fDelayTimeRemaining表示的就是與前一事件之間的時(shí)間差；fNext和fPrev就是指向時(shí)間軸上的下一個(gè)事件和前一個(gè)事件的指針；ftoken表示當(dāng)前節(jié)點(diǎn)的標(biāo)識；handleTimeout就是事件超時(shí)后的處理方法。
而DelayQueue類里描述的則是具體的實(shí)現(xiàn)方法。首先是一些對這個(gè)隊(duì)列進(jìn)行的基本操作：addEntry實(shí)現(xiàn)的是在隊(duì)列中增加事件節(jié)點(diǎn)；removeEntry實(shí)現(xiàn)的是在隊(duì)列中刪除某事件節(jié)點(diǎn)；updateEntry實(shí)現(xiàn)的則是更新某事件的觸發(fā)時(shí)間；而findEntryByToken則是根據(jù)節(jié)點(diǎn)的標(biāo)識查找相應(yīng)的事件。在此類中最常用的方法應(yīng)該是synchronize，它實(shí)現(xiàn)的就是將整個(gè)事件隊(duì)列和當(dāng)前系統(tǒng)時(shí)間進(jìn)行同步，檢測有無事件已經(jīng)被觸發(fā)，如果觸發(fā)并調(diào)用handleAlarm方法對相應(yīng)事件進(jìn)行處理。而屬性fLastSyncTime表示的就是上次同步的系統(tǒng)時(shí)間，其實(shí)一般情況下，方法synchronize的實(shí)現(xiàn)方法其實(shí)就是簡單地把隊(duì)列上第一個(gè)事件節(jié)點(diǎn)存儲(chǔ)的時(shí)間差減去當(dāng)前系統(tǒng)時(shí)間和上次同步時(shí)間的差。
附：相關(guān)類結(jié)構(gòu)：
=================================================================
==> 相關(guān)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
==> 相關(guān)類的說明（由于有些類很大，故不會(huì)完整貼出，故用說明）
///// 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; // 以>=為基礎(chǔ)，推算出其余條件判斷（<=、<</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; // 看到，所有的所有，其實(shí)是在為timeval這個(gè)結(jié)構(gòu)體封裝了一系列操作函數(shù)
};
++++++++++++++++++++++++++++++++++++++++++
// 下面這個(gè)類用以處理自1970年1月1日以來的絕對時(shí)間
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 { // 通過它來鏈接所有的事件信息，組成隊(duì)列（見下面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隊(duì)頭成員
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;
};