多级时间轮定时器_时间轮与哈希表定时

    // timeout为定时时间，SI为槽之间切换的时间
    int ticks;
    if( timeout < SI ) {
        ticks = 1;
    } else {
        ticks = timeout / SI;
    }

    int rotation = ticks / N;  // 被触发的圈数
    int ts = ( cur_slot + ticks % N ) % N;  // 被插入的槽

#ifndef _TIMEWHEEL_H_
#define _TIMEWHEEL_H_
#include <time.h>
#include <netinet/in.h>
const int BUFFER_SIZE = 64;
class TwTimer;
// 用户数据，绑定socket和定时器
struct client_data {
sockaddr_in address;
int sock_fd;
char buf[BUFFER_SIZE];
TwTimer* timer;
};
// 定时器类，时间轮采用双向链表
class TwTimer {
public:
int rotation;  // 定时器转多少圈后生效
int time_slot;  // 记录定时器属于时间轮的哪个时间槽
client_data* user_data;  // 客户数据
TwTimer* next;  // 指向下一个定时器
TwTimer* pre;  // 指向上一个定时器
public:
TwTimer( int rot, int ts ) : rotation(rot), time_slot(ts), next(NULL), pre(NULL) {}
void (*cb_func)( client_data * );  // 回调函数
};
class TimeWheel {
private: 
static const int N = 60;  // 槽的数目
static const int SI = 1;  // 定时器槽之间时间间隔
TwTimer* slot[ N ];  // 时间轮的槽，指向一个定时器链表，链表无序
int cur_slot;  // 当前槽
public:
TimeWheel() : cur_slot(0) {
for( int i = 0; i < N; i++ ) {
slot[i] = NULL;
}
}
~TimeWheel() {
for( int i = 0; i < N; i++ ) {
TwTimer* tmp;
while( tmp = slot[i], tmp ) {
slot[i] = tmp->next;
delete tmp;
}
}
}
TwTimer* add_timer( int timeout );  // 根据定时值创建定时器，并插入槽中
void del_timer( TwTimer* timer );
void tick();
};
TwTimer* TimeWheel::add_timer( int timeout ) {
if( timeout < 0 ) {
return NULL;
}
// 记录多少个tick后被触发，不足最小单位SI的记为1，其余为timeout/SI
int ticks = 0;
if( timeout < SI ) {
ticks = 1;
} else {
ticks = timeout / SI;
}
int rotation = ticks / N;  // 被触发的圈数
int ts = ( cur_slot + ticks % N ) % N;  // 被插入的槽
TwTimer* timer = new TwTimer( rotation, ts );
// 如果链表为空，则放到头，否则插入到第一个位置
if( !slot[ts] ) {
slot[ts] = timer;
} else {
timer->next = slot[ts];
slot[ts]->pre = timer;
slot[ts] = timer;
}
return timer;
}
// 删除定时器
void TimeWheel::del_timer( TwTimer* timer ) {
if( !timer ) {
return;
}
// 注意链表为双向的
int ts = timer->time_slot;
if( timer == slot[ts] ) {
slot[ts] = slot[ts]->next;
if( slot[ts] ) {
slot[ts]->pre = NULL;
}
} else {
timer->pre->next = timer->next;
if( timer->next ) {
timer->next->pre = timer->pre;
}
}
delete timer;
}
// SI时间到后，条用该函数，时间轮向前滚动一个槽的间隔
void TimeWheel::tick() {
TwTimer* tmp = slot[cur_slot];
while( tmp ) {
if( tmp->rotation > 0 ) {  // 定时时间未到
tmp->rotation--;
tmp = tmp->next;
} else {  // 定时时间已到
tmp->cb_func( tmp->user_data );
if( tmp == slot[cur_slot] ) {  // tmp位于链表首
slot[cur_slot] = tmp->next;
if( slot[cur_slot] ) {
slot[cur_slot]->pre = NULL;
}
delete tmp;
tmp = slot[cur_slot];
} else {  // tmp位于链表中
tmp->pre->next = tmp->next;
if( tmp->next ) {
tmp->next->pre = tmp->pre;
}
TwTimer* tmp2 = tmp->next;
delete tmp;
tmp = tmp2;
}
}
}
cur_slot = ( cur_slot + 1 ) % N;
}
#endif