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

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

Line | |
---|---|

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 | |

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

21 | |

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

23 | #include <sys/time.h> |

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.