Created
November 27, 2011 15:34
-
-
Save reusee/1397703 to your computer and use it in GitHub Desktop.
timer wheel
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment