转载自: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;
};