timer wheel

gistfile1.cpp

#include <iostream>
#include <list>
using std::list;
using std::string;
using std::cout;
using std::endl;

#define ROOT_BITS 8
#define REST_BITS 8
#define REST_NUM 3
#define ROOT_SIZE (1 << ROOT_BITS)
#define REST_SIZE (1 << REST_BITS)
#define ROOT_MASK (ROOT_SIZE - 1)
#define REST_MASK (REST_SIZE - 1)

template<class Event>
class Timer {
  public:
    Timer() : jiffies(0), rest_index({0}) {}

    void add(Event event) {
      unsigned long expire = event.expire;
      unsigned long idx = expire - jiffies;
      list<Event> *pos(nullptr);

      if (idx < ROOT_SIZE) 
        pos = root + (expire & ROOT_MASK);
      else 
        for (int tv = 0; tv < REST_NUM; ++tv) 
          if (idx < 1UL << (REST_BITS + (tv + 1) * REST_BITS)) {
            pos = rest[tv] + (expire >> (ROOT_BITS + tv * REST_BITS) & REST_MASK);
            break;
          }

      if (pos == nullptr) 
        throw "expire overflow";
      pos->push_back(event);
    }

    void tick() {
      jiffies &= (1UL << (ROOT_BITS + REST_NUM * REST_BITS)) - 1;

      for (int tv = 0; tv < REST_NUM; ++tv) {
        unsigned long tv_index = jiffies >> (ROOT_BITS + tv * REST_BITS) & REST_MASK;
        if (tv_index != rest_index[tv]) {
          for (Event &e : rest[tv][tv_index]) 
            add(e);
          rest[tv][tv_index].clear();
          rest_index[tv] = tv_index;
        }
      }

      unsigned long root_index = jiffies & ((1UL << REST_BITS) - 1);

      for (Event &e : root[root_index]) {
        cout << "at " << jiffies << endl;
        e.happen();
      }
      root[root_index].clear();

      jiffies += 1;
    }

    void del(Event &event) {
    }

  private:
    unsigned long jiffies;
    unsigned long rest_index[REST_NUM];
    list<Event> root[ROOT_SIZE];
    list<Event> rest[REST_NUM][REST_SIZE];
};

struct Event {
  public:
    Event(int e, string s) : expire(e), event(s) {}
    
    void happen() {
      cout << "== " << event << " ==" << endl;
    }

    int expire;

  private:
    string event;
};

int main() {
  Timer<Event> t;
  t.add(Event {0, "A"});
  t.add(Event {0, "A2"});
  t.add(Event {0, "A3"});
  t.add(Event {0, "A4"});
  t.add(Event {1, "B"});
  t.add(Event {2, "C"});
  t.add(Event {3, "D"});
  t.add(Event {4, "E"});
  t.add(Event {5, "F"});
  t.add(Event {6, "G"});
  t.add(Event {7, "H"});
  t.add(Event {0xFFFFFFF, "H"});

  for (;;) 
    t.tick();

  return 0;
}