1 /* timers.c - simple timer routines
2 **
3 ** Copyright � 1995,1998,2000 by Jef Poskanzer <jef@mail.acme.com>.
4 ** All rights reserved.
5 **
6 ** Redistribution and use in source and binary forms, with or without
7 ** modification, are permitted provided that the following conditions
8 ** are met:
9 ** 1. Redistributions of source code must retain the above copyright
10 ** notice, this list of conditions and the following disclaimer.
11 ** 2. Redistributions in binary form must reproduce the above copyright
12 ** notice, this list of conditions and the following disclaimer in the
13 ** documentation and/or other materials provided with the distribution.
14 **
15 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 ** ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 ** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 ** ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 ** FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 ** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 ** OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 ** HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 ** LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 ** OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 ** SUCH DAMAGE.
26 */
27
28 #include <sys/types.h>
29
30 #include <stdlib.h>
31 #include <stdio.h>
32
33 #include "timers.h"
34
35 #define HASH_SIZE 67
36 static Timer *timers[HASH_SIZE];
37 static Timer *free_timers = (Timer *)0;
38 static long mstimeout_cache = -1;
39
40 ClientData JunkClientData;
41
42 static unsigned int
hash(Timer * t)43 hash(Timer *t)
44 {
45 /* We can hash on the trigger time, even though it can change over
46 ** the life of a timer via either the periodic bit or the tmr_reset()
47 ** call. This is because both of those guys call l_resort(), which
48 ** recomputes the hash and moves the timer to the appropriate list.
49 */
50 return ((unsigned int)t->time.tv_sec ^ (unsigned int)t->time.tv_usec) % HASH_SIZE;
51 }
52
53 static void
l_add(Timer * t)54 l_add(Timer *t)
55 {
56 int h = t->hash;
57 Timer *t2;
58 Timer *t2prev;
59
60 t2 = timers[h];
61 if (t2 == (Timer *)0) {
62 /* The list is empty. */
63 timers[h] = t;
64 t->prev = t->next = (Timer *)0;
65 } else {
66 if (t->time.tv_sec < t2->time.tv_sec || (t->time.tv_sec == t2->time.tv_sec && t->time.tv_usec <= t2->time.tv_usec)) {
67 /* The new timer goes at the head of the list. */
68 timers[h] = t;
69 t->prev = (Timer *)0;
70 t->next = t2;
71 t2->prev = t;
72 } else {
73 /* Walk the list to find the insertion point. */
74 for (t2prev = t2, t2 = t2->next; t2 != (Timer *)0; t2prev = t2, t2 = t2->next) {
75 if (t->time.tv_sec < t2->time.tv_sec || (t->time.tv_sec == t2->time.tv_sec && t->time.tv_usec <= t2->time.tv_usec)) {
76 /* Found it. */
77 t2prev->next = t;
78 t->prev = t2prev;
79 t->next = t2;
80 t2->prev = t;
81 return;
82 }
83 }
84 /* Oops, got to the end of the list. Add to tail. */
85 t2prev->next = t;
86 t->prev = t2prev;
87 t->next = (Timer *)0;
88 }
89 }
90 }
91
92 static void
l_remove(Timer * t)93 l_remove(Timer *t)
94 {
95 int h = t->hash;
96
97 if (t->prev == (Timer *)0)
98 timers[h] = t->next;
99 else
100 t->prev->next = t->next;
101 if (t->next != (Timer *)0)
102 t->next->prev = t->prev;
103 }
104
105 static void
l_resort(Timer * t)106 l_resort(Timer *t)
107 {
108 /* Remove the timer from its old list. */
109 l_remove(t);
110 /* Recompute the hash. */
111 t->hash = hash(t);
112 /* And add it back in to its new list, sorted correctly. */
113 l_add(t);
114 }
115
116 void
tmr_init(void)117 tmr_init(void)
118 {
119 int h;
120
121 mstimeout_cache = -1;
122 for (h = 0; h < HASH_SIZE; ++h)
123 timers[h] = (Timer *)0;
124 }
125
126 Timer *
tmr_create(struct timeval * nowP,TimerProc * timer_proc,ClientData client_data,long msecs,int periodic)127 tmr_create(struct timeval *nowP, TimerProc *timer_proc, ClientData client_data, long msecs, int periodic)
128 {
129 Timer *t;
130
131 if (free_timers != (Timer *)0) {
132 t = free_timers;
133 free_timers = t->next;
134 } else {
135 t = (Timer *)malloc(sizeof(Timer));
136 if (t == (Timer *)0)
137 return (Timer *)0;
138 }
139
140 mstimeout_cache = -1;
141 t->timer_proc = timer_proc;
142 t->client_data = client_data;
143 t->msecs = msecs;
144 t->periodic = periodic;
145 if (nowP != (struct timeval *)0)
146 t->time = *nowP;
147 else
148 (void)gettimeofday(&t->time, (struct timezone *)0);
149 t->time.tv_sec += msecs / 1000L;
150 t->time.tv_usec += (msecs % 1000L) * 1000L;
151 if (t->time.tv_usec >= 1000000L) {
152 t->time.tv_sec += t->time.tv_usec / 1000000L;
153 t->time.tv_usec %= 1000000L;
154 }
155 t->hash = hash(t);
156 /* Add the new timer to the proper active list. */
157 l_add(t);
158
159 return t;
160 }
161
162 struct timeval *
tmr_timeout(struct timeval * nowP)163 tmr_timeout(struct timeval *nowP)
164 {
165 long msecs;
166 static struct timeval timeout;
167
168 msecs = tmr_mstimeout(nowP);
169 if (msecs == INFTIM)
170 return (struct timeval *)0;
171 timeout.tv_sec = msecs / 1000L;
172 timeout.tv_usec = (msecs % 1000L) * 1000L;
173 return &timeout;
174 }
175
176 long
tmr_mstimeout(struct timeval * nowP)177 tmr_mstimeout(struct timeval *nowP)
178 {
179 if (mstimeout_cache > -1) {
180 return mstimeout_cache;
181 } else {
182 int h;
183 int gotone;
184 long msecs, m;
185 Timer *t;
186
187 gotone = 0;
188 msecs = 0; /* make lint happy */
189 /* Since the lists are sorted, we only need to look at the
190 ** first timer on each one.
191 */
192 for (h = 0; h < HASH_SIZE; ++h) {
193 t = timers[h];
194 if (t != (Timer *)0) {
195 m = (t->time.tv_sec - nowP->tv_sec) * 1000L + (t->time.tv_usec - nowP->tv_usec) / 1000L;
196 if (!gotone) {
197 msecs = m;
198 gotone = 1;
199 } else if (m < msecs)
200 msecs = m;
201 }
202 }
203 if (!gotone)
204 return INFTIM;
205 if (msecs <= 0)
206 msecs = 0;
207 mstimeout_cache = msecs;
208
209 return msecs;
210 }
211 }
212
213 void
tmr_run(struct timeval * nowP)214 tmr_run(struct timeval *nowP)
215 {
216 int h;
217 Timer *t;
218 Timer *next;
219
220 for (h = 0; h < HASH_SIZE; ++h)
221 for (t = timers[h]; t != (Timer *)0; t = next) {
222 next = t->next;
223 /* Since the lists are sorted, as soon as we find a timer
224 ** that isn't ready yet, we can go on to the next list.
225 */
226 if (t->time.tv_sec > nowP->tv_sec || (t->time.tv_sec == nowP->tv_sec && t->time.tv_usec > nowP->tv_usec))
227 break;
228
229 /* Invalidate mstimeout cache, since we're modifying the queue */
230 mstimeout_cache = -1;
231
232 (t->timer_proc)(t->client_data, nowP);
233 if (t->periodic) {
234 /* Reschedule. */
235 t->time.tv_sec += t->msecs / 1000L;
236 t->time.tv_usec += (t->msecs % 1000L) * 1000L;
237 if (t->time.tv_usec >= 1000000L) {
238 t->time.tv_sec += t->time.tv_usec / 1000000L;
239 t->time.tv_usec %= 1000000L;
240 }
241 l_resort(t);
242 } else
243 tmr_cancel(t);
244 }
245 }
246
247 void
tmr_reset(struct timeval * nowP,Timer * t)248 tmr_reset(struct timeval *nowP, Timer *t)
249 {
250 mstimeout_cache = -1;
251 t->time = *nowP;
252 t->time.tv_sec += t->msecs / 1000L;
253 t->time.tv_usec += (t->msecs % 1000L) * 1000L;
254 if (t->time.tv_usec >= 1000000L) {
255 t->time.tv_sec += t->time.tv_usec / 1000000L;
256 t->time.tv_usec %= 1000000L;
257 }
258 l_resort(t);
259 }
260
261 void
tmr_cancel(Timer * t)262 tmr_cancel(Timer *t)
263 {
264 mstimeout_cache = -1;
265 /* Remove it from its active list. */
266 l_remove(t);
267 /* And put it on the free list. */
268 t->next = free_timers;
269 free_timers = t;
270 t->prev = (Timer *)0;
271 }
272
273 void
tmr_cleanup(void)274 tmr_cleanup(void)
275 {
276 Timer *t;
277
278 mstimeout_cache = -1;
279 while (free_timers != (Timer *)0) {
280 t = free_timers;
281 free_timers = t->next;
282 free((void *)t);
283 }
284 }
285
286 void
tmr_destroy(void)287 tmr_destroy(void)
288 {
289 int h;
290
291 mstimeout_cache = -1;
292 for (h = 0; h < HASH_SIZE; ++h)
293 while (timers[h] != (Timer *)0)
294 tmr_cancel(timers[h]);
295 tmr_cleanup();
296 }
297