#
source:
trunk/athena/etc/larvnetd/timer.c
@
11936

Revision 11936, 6.3 KB checked in by ghudson, 26 years ago (diff) |
---|

Rev | Line | |
---|---|---|

[11904] | 1 | /* Copyright 1998 by the Massachusetts Institute of Technology. |

2 | * | |

3 | * Permission to use, copy, modify, and distribute this | |

4 | * software and its documentation for any purpose and without | |

5 | * fee is hereby granted, provided that the above copyright | |

6 | * notice appear in all copies and that both that copyright | |

7 | * notice and this permission notice appear in supporting | |

8 | * documentation, and that the name of M.I.T. not be used in | |

9 | * advertising or publicity pertaining to distribution of the | |

10 | * software without specific, written prior permission. | |

11 | * M.I.T. makes no representations about the suitability of | |

12 | * this software for any purpose. It is provided "as is" | |

13 | * without express or implied warranty. | |

14 | */ | |

15 | ||

16 | /* This file implements a mini-library of functions for setting up | |

17 | * and processing timers. | |

18 | */ | |

19 | ||

[11936] | 20 | static const char rcsid[] = "$Id: timer.c,v 1.2 1998-09-15 15:03:37 ghudson Exp $"; |

[11904] | 21 | |

22 | #include <sys/types.h> | |

[11936] | 23 | #include <sys/time.h> |

[11904] | 24 | #include <stdlib.h> |

25 | #include <time.h> | |

26 | #include <syslog.h> | |

27 | #include "larvnetd.h" | |

28 | #include "timer.h" | |

29 | ||

30 | /* DELTA is just an offset to keep the size a bit less than a power of | |

31 | * two. It's measured in pointers, so it's 32 bytes on most systems. | |

32 | */ | |

33 | #define DELTA 8 | |

34 | #define INITIAL_HEAP_SIZE (1024 - DELTA) | |

35 | ||

36 | /* We have three operations which we need to be able to perform | |

37 | * quickly: adding a timer, deleting a timer given a pointer to | |

38 | * it, and determining which timer will be the next to go off. A | |

39 | * heap is an ideal data structure for these purposes, so we use | |

40 | * one. The heap is an array of pointers to timers, and each timer | |

41 | * knows the position of its pointer in the heap. | |

42 | * | |

43 | * Okay, what is the heap, exactly? It's a data structure, | |

44 | * represented as an array, with the invariant condition that | |

45 | * the timeout of heap[i] is less than or equal to the timeout of | |

46 | * heap[i * 2 + 1] and heap[i * 2 + 2] (assuming i * 2 + 1 and | |

47 | * i * 2 + 2 are valid * indices). An obvious consequence of this | |

48 | * is that heap[0] has the lowest timer value, so finding the first | |

49 | * timer to go off is easy. We say that an index i has "children" | |

50 | * i * 2 + 1 and i * 2 + 1, and the "parent" (i - 1) / 2. | |

51 | * | |

52 | * To add a timer to the heap, we start by adding it to the end, and | |

53 | * then keep swapping it with its parent until it has a parent with | |

54 | * a timer value less than its value. With a little bit of thought, | |

55 | * you can see that this preserves the heap property on all indices | |

56 | * of the array. | |

57 | * | |

58 | * To delete a timer at position i from the heap, we discard it and | |

59 | * fill in its position with the last timer in the heap. In order | |

60 | * to restore the heap, we have to consider two cases: the timer | |

61 | * value at i is less than that of its parent, or the timer value at | |

62 | * i is greater than that of one of its children. In the first case, | |

63 | * we propagate the timer at i up the tree, swapping it with its | |

64 | * parent, until the heap is restored; in the second case, we | |

65 | * propagate the timer down the tree, swapping it with its least | |

66 | * child, until the heap is restored. | |

67 | */ | |

68 | ||

69 | /* In order to ensure that the back pointers from timers are consistent | |

70 | * with the heap pointers, all heap assignments should be done with the | |

71 | * HEAP_ASSIGN() macro, which sets the back pointer and updates the | |

72 | * heap at the same time. | |

73 | */ | |

74 | #define PARENT(i) (((i) - 1) / 2) | |

75 | #define CHILD1(i) ((i) * 2 + 1) | |

76 | #define CHILD2(i) ((i) * 2 + 2) | |

77 | #define TIME(i) (heap[i]->abstime) | |

78 | #define HEAP_ASSIGN(pos, tmr) ((heap[pos] = (tmr))->heap_pos = (pos)) | |

79 | ||

80 | static Timer **heap; | |

81 | static int num_timers = 0; | |

82 | static int heap_size = 0; | |

83 | ||

84 | static void timer_botch(void *); | |

85 | static Timer *add_timer(Timer *); | |

86 | ||

87 | Timer *timer_set_rel(int reltime, Timer_proc proc, void *arg) | |

88 | { | |

89 | return timer_set_abs(time(NULL) + reltime, proc, arg); | |

90 | } | |

91 | ||

92 | Timer *timer_set_abs(time_t abstime, Timer_proc proc, void *arg) | |

93 | { | |

94 | Timer *timer; | |

95 | ||

96 | timer = (Timer *) emalloc(sizeof(Timer)); | |

97 | timer->abstime = abstime; | |

98 | timer->func = proc; | |

99 | timer->arg = arg; | |

100 | return add_timer(timer); | |

101 | } | |

102 | ||

103 | void *timer_reset(Timer *timer) | |

104 | { | |

105 | int pos, min; | |

106 | void *arg; | |

107 | ||

108 | /* Free the timer, saving its heap position and argument. */ | |

109 | pos = timer->heap_pos; | |

110 | arg = timer->arg; | |

111 | free(timer); | |

112 | ||

113 | if (pos != num_timers - 1) | |

114 | { | |

115 | /* Replace the timer with the last timer in the heap and | |

116 | * restore the heap, propagating the timer either up or | |

117 | * down, depending on which way it violates the heap | |

118 | * property to insert the last timer in place of the | |

119 | * deleted timer. | |

120 | */ | |

121 | if (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos))) | |

122 | { | |

123 | do | |

124 | { | |

125 | HEAP_ASSIGN(pos, heap[PARENT(pos)]); | |

126 | pos = PARENT(pos); | |

127 | } | |

128 | while (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos))); | |

129 | HEAP_ASSIGN(pos, heap[num_timers - 1]); | |

130 | } | |

131 | else | |

132 | { | |

133 | while (CHILD2(pos) < num_timers) | |

134 | { | |

135 | min = num_timers - 1; | |

136 | if (TIME(CHILD1(pos)) < TIME(min)) | |

137 | min = CHILD1(pos); | |

138 | if (TIME(CHILD2(pos)) < TIME(min)) | |

139 | min = CHILD2(pos); | |

140 | HEAP_ASSIGN(pos, heap[min]); | |

141 | pos = min; | |

142 | } | |

143 | if (pos != num_timers - 1) | |

144 | HEAP_ASSIGN(pos, heap[num_timers - 1]); | |

145 | } | |

146 | } | |

147 | num_timers--; | |

148 | return arg; | |

149 | } | |

150 | ||

151 | static Timer *add_timer(Timer *new) | |

152 | { | |

153 | int pos; | |

154 | ||

155 | /* Create or resize the heap as necessary. */ | |

156 | if (heap_size == 0) | |

157 | { | |

158 | heap_size = INITIAL_HEAP_SIZE; | |

159 | heap = (Timer **) emalloc(heap_size * sizeof(Timer *)); | |

160 | } | |

161 | else if (num_timers >= heap_size) | |

162 | { | |

163 | heap_size = heap_size * 2 + DELTA; | |

164 | heap = (Timer **) erealloc(heap, heap_size * sizeof(Timer *)); | |

165 | } | |

166 | ||

167 | /* Insert the Timer *into the heap. */ | |

168 | pos = num_timers; | |

169 | while (pos > 0 && new->abstime < TIME(PARENT(pos))) | |

170 | { | |

171 | HEAP_ASSIGN(pos, heap[PARENT(pos)]); | |

172 | pos = PARENT(pos); | |

173 | } | |

174 | HEAP_ASSIGN(pos, new); | |

175 | num_timers++; | |

176 | ||

177 | return new; | |

178 | } | |

179 | ||

180 | void timer_process(void) | |

181 | { | |

182 | Timer *t; | |

183 | Timer_proc func; | |

184 | void *arg; | |

185 | ||

186 | if (num_timers == 0 || heap[0]->abstime > time(NULL)) | |

187 | return; | |

188 | ||

189 | /* Remove the first timer from the heap, remembering its | |

190 | * function and argument. | |

191 | */ | |

192 | t = heap[0]; | |

193 | func = t->func; | |

194 | arg = t->arg; | |

195 | t->func = timer_botch; | |

196 | t->arg = NULL; | |

197 | timer_reset(t); | |

198 | ||

199 | /* Run the function. */ | |

200 | func(arg); | |

201 | } | |

202 | ||

203 | struct timeval *timer_timeout(struct timeval *tvbuf) | |

204 | { | |

205 | if (num_timers > 0) | |

206 | { | |

207 | tvbuf->tv_sec = heap[0]->abstime - time(NULL); | |

208 | if (tvbuf->tv_sec < 0) | |

209 | tvbuf->tv_sec = 0; | |

210 | tvbuf->tv_usec = 0; | |

211 | return tvbuf; | |

212 | } | |

213 | else | |

214 | return NULL; | |

215 | } | |

216 | ||

217 | static void timer_botch(void *arg) | |

218 | { | |

219 | syslog(LOG_ALERT, "timer botch"); | |

220 | abort(); | |

221 | } |

**Note:**See TracBrowser for help on using the repository browser.