live555延時隊列

原文位址：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;

};