时间轮
前文提到，基于排序链表的定时器存在一个问题：添加定时器的效率偏低。一种简单的时间轮如图所示：
在这个时间轮中，实线指针指向轮子上的一个槽（slot）。它以恒定的速度顺时针转动，每转动一步就指向下一个槽（slot）。每次转动称为一个滴答（tick）。一个tick时间间隔为时间轮的si（slot interval）。该时间轮共有N个槽，因此它转动一周的时间是N*si.每个槽指向一条定时器链表，每条链表上的定时器具有相同的特征：它们的定时时间相差N*si的整数倍。时间轮正是利用这个关系将定时器散列到不同的链表中。假如现在指针指向槽cs，我们要添加一个定时时间为ti的定时器，则该定时器将被插入槽ts（timer slot）对应的链表中：
ts=（cs+（ti/si））%N
基于排序链表的定时器使用唯一的一条链表来管理所有的定时器，所以插入操作的效率随着定时器的数目增多而降低。而时间轮使用了哈希表处理冲突的思想，将定时器散列到不同的链表上。这样每条链表上的定时器数目都将明显少于原来的排序链表上的定时器数目，插入操作的效率基本不受定时器数目的影响。
很显然，对于时间轮而言，要提高精度，就要使si的值足够小; 要提高执行效率，则要求N值足够大，使定时器尽可能的分布在不同的槽。
下列代码描述了一个简单的时间轮，如果想继续提高效率，可以实现多个不同精度的轮子，提高查找的效率。
1 #ifndef TIME_WHEEL_TIMER
2 #define TIME_WHEEL_TIMER
3
4 #include
5 #include
6 #include
7
8 #define BUFFER_SIZE 64
9 class tw_timer;
10 struct client_data//绑定socket和定时器
11 {
12 sockaddr_in address;
13 int sockfd;
14 char buf[ BUFFER_SIZE ];
15 tw_timer* timer;
16 };
17
18 class tw_timer//定时器类
19 {
20 public:
21 tw_timer( int rot, int ts )
22 : next( NULL ), prev( NULL ), rotation( rot ), time_slot( ts ){}
23
24 public:
25 int rotation;//记录该定时器在时间轮转多少圈后生效
26 int time_slot;//记录定时器属于那个槽
27 void (*cb_func)( client_data* );//定时器回调函数
28 client_data* user_data;//用户数据
29 tw_timer* next;//指向上一个定时器
30 tw_timer* prev;//指向下一个定时器
31 };
32
33 class time_wheel//事件轮管理定时器
34 {
35 public:
36 time_wheel() : cur_slot( 0 )
37 {
38 for( int i = 0; i < N; ++i )
39 {
40 slots[i] = NULL;//每个槽的头节点初始化为空
41 }
42 }
43 ~time_wheel()
44 {
45 for( int i = 0; i < N; ++i )
46 {
47 tw_timer* tmp = slots[i];
48 while( tmp )
49 {
50 slots[i] = tmp->next;
51 delete tmp;//遍历每个槽销毁new分配在堆中的定时器
52 tmp = slots[i];
53 }
54 }
55 }
56 tw_timer* add_timer( int timeout )//添加新的定时器，插入到合适的槽中
57 {
58 if( timeout < 0 )//时间错误
59 {
60 return NULL;
61 }
62 int ticks = 0;
63 if( timeout < TI )//小于每个槽的interval，则为1
64 {
65 ticks = 1;
66 }
67 else
68 {
69 ticks = timeout / TI;//相对当前位置的槽数
70 }
71 int rotation = ticks / N;//记录多少圈后生效
72 int ts = ( cur_slot + ( ticks % N ) ) % N;//确定插入槽的位置
73 tw_timer* timer = new tw_timer( rotation, ts );//根据位置和圈数，插入对应的槽中
74 if( !slots[ts] )//所在槽头节点为空，直接插入
75 {
76 printf( "add timer, rotation is %d, ts is %d, cur_slot is %d\n", rotation, ts, cur_slot );
77 slots[ts] = timer;
78 }
79 else //头插法
80 {
81 timer->next = slots[ts];
82 slots[ts]->prev = timer;
83 slots[ts] = timer;
84 }
85 return timer;//返回含有时间信息和所在槽位置的定时器
86 }
87 void del_timer( tw_timer* timer )//从时间轮上删除定时器
88 {
89 if( !timer )
90 {
91 return;
92 }
93 int ts = timer->time_slot;//找到所在槽
94 if( timer == slots[ts] )
95 {
96 slots[ts] = slots[ts]->next;
97 if( slots[ts] )
98 {
99 slots[ts]->prev = NULL;
100 }
101 delete timer;
102 }
103 else
104 {
105 timer->prev->next = timer->next;
106 if( timer->next )
107 {
108 timer->next->prev = timer->prev;
109 }
110 delete timer;
111 }
112 }
113 void tick()
114 {
115 tw_timer* tmp = slots[cur_slot];//取出当前槽的头节点
116 printf( "current slot is %d\n", cur_slot );
117 while( tmp )//遍历
118 {
119 printf( "tick the timer once\n" );
120 if( tmp->rotation > 0 )
121 {
122 tmp->rotation--;
123 tmp = tmp->next;
124 }
125 else
126 {
127 tmp->cb_func( tmp->user_data );//符合条件，调用回调函数
128 if( tmp == slots[cur_slot] )
129 {
130 printf( "delete header in cur_slot\n" );
131 slots[cur_slot] = tmp->next;
132 delete tmp;
133 if( slots[cur_slot] )
134 {
135 slots[cur_slot]->prev = NULL;
136 }
137 tmp = slots[cur_slot];
138 }
139 else
140 {
141 tmp->prev->next = tmp->next;
142 if( tmp->next )
143 {
144 tmp->next->prev = tmp->prev;
145 }
146 tw_timer* tmp2 = tmp->next;
147 delete tmp;
148 tmp = tmp2;
149 }
150 }
151 }
152 cur_slot = ++cur_slot % N;
153 }
154
155 private:
156 static const int N = 60;
157 static const int TI = 1;
158 tw_timer* slots[N];
159 int cur_slot;
160 };
161
162 #endif
时间堆实现高性能定时器
设计定时器的另外一种思路是：将所有定时器中超时时间最小定时器的timeout作为心搏的间隔。这样，当tick（）被调用时，超时时间最小的定时器必然到期。
下列代码给出了一个简单的时间堆的实现
1 #ifndef intIME_HEAP
2 #define intIME_HEAP
3
4 #include
5 #include
6 #include
7 using std::exception;
8
9 #define BUFFER_SIZE 64
10
11 class heap_timer;
12 struct client_data
13 {
14 sockaddr_in address;
15 int sockfd;
16 char buf[ BUFFER_SIZE ];
17 heap_timer* timer;
18 };
19
20 class heap_timer
21 {
22 public:
23 heap_timer( int delay )
24 {
25 expire = time( NULL ) + delay;
26 }
27
28 public:
29 time_t expire;
30 void (*cb_func)( client_data* );
31 client_data* user_data;
32 };
33
34 class time_heap
35 {
36 public:
37 time_heap( int cap ) throw ( std::exception )
38 : capacity( cap ), cur_size( 0 )
39 {
40 array = new heap_timer* [capacity];
41 if ( ! array )
42 {
43 throw std::exception();
44 }
45 for( int i = 0; i < capacity; ++i )
46 {
47 array[i] = NULL;
48 }
49 }
50 time_heap( heap_timer** init_array, int size, int capacity ) throw ( std::exception )
51 : cur_size( size ), capacity( capacity )
52 {
53 if ( capacity < size )
54 {
55 throw std::exception();
56 }
57 array = new heap_timer* [capacity];
58 if ( ! array )
59 {
60 throw std::exception();
61 }
62 for( int i = 0; i < capacity; ++i )
63 {
64 array[i] = NULL;
65 }
66 if ( size != 0 )
67 {
68 for ( int i = 0; i < size; ++i )
69 {
70 array[ i ] = init_array[ i ];
71 }
72 for ( int i = (cur_size-1)/2; i >=0; --i )
73 {
74 percolate_down( i );
75 }
76 }
77 }
78 ~time_heap()
79 {
80 for ( int i = 0; i < cur_size; ++i )
81 {
82 delete array[i];
83 }
84 delete [] array;
85 }
86
87 public:
88 void add_timer( heap_timer* timer ) throw ( std::exception )
89 {
90 if( !timer )
91 {
92 return;
93 }
94 if( cur_size >= capacity )
95 {
96 resize();
97 }
98 int hole = cur_size++;
99 int parent = 0;
100 for( ; hole > 0; hole=parent )
101 {
102 parent = (hole-1)/2;
103 if ( array[parent]->expire <= timer->expire )
104 {
105 break;
106 }
107 array[hole] = array[parent];
108 }
109 array[hole] = timer;
110 }
111 void del_timer( heap_timer* timer )
112 {
113 if( !timer )
114 {
115 return;
116 }
117 // lazy delelte
118 timer->cb_func = NULL;
119 }
120 heap_timer* top() const
121 {
122 if ( empty() )
123 {
124 return NULL;
125 }
126 return array[0];
127 }
128 void pop_timer()
129 {
130 if( empty() )
131 {
132 return;
133 }
134 if( array[0] )
135 {
136 delete array[0];
137 array[0] = array[--cur_size];
138 percolate_down( 0 );
139 }
140 }
141 void tick()
142 {
143 heap_timer* tmp = array[0];
144 time_t cur = time( NULL );
145 while( !empty() )
146 {
147 if( !tmp )
148 {
149 break;
150 }
151 if( tmp->expire > cur )
152 {
153 break;
154 }
155 if( array[0]->cb_func )
156 {
157 array[0]->cb_func( array[0]->user_data );
158 }
159 pop_timer();
160 tmp = array[0];
161 }
162 }
163 bool empty() const { return cur_size == 0; }
164
165 private:
166 void percolate_down( int hole )
167 {
168 heap_timer* temp = array[hole];
169 int child = 0;
170 for ( ; ((hole*2+1) <= (cur_size-1)); hole=child )
171 {
172 child = hole*2+1;
173 if ( (child < (cur_size-1)) && (array[child+1]->expire < array[child]->expire ) )
174 {
175 ++child;
176 }
177 if ( array[child]->expire < temp->expire )
178 {
179 array[hole] = array[child];
180 }
181 else
182 {
183 break;
184 }
185 }
186 array[hole] = temp;
187 }
188 void resize() throw ( std::exception )
189 {
190 heap_timer** temp = new heap_timer* [2*capacity];
191 for( int i = 0; i < 2*capacity; ++i )
192 {
193 temp[i] = NULL;
194 }
195 if ( ! temp )
196 {
197 throw std::exception();
198 }
199 capacity = 2*capacity;
200 for ( int i = 0; i < cur_size; ++i )
201 {
202 temp[i] = array[i];
203 }
204 delete [] array;
205 array = temp;
206 }
207
208 private:
209 heap_timer** array;
210 int capacity;
211 int cur_size;
212 };
213
214 #endif
参考文献：《Linux高性能服务器编程》——游双