1 /* This file is part of the Project Athena Zephyr Notification System.
2 * It contains functions for managing multiple timeouts.
4 * Created by: John T. Kohl
5 * Derived from timer_manager_ by Ken Raeburn
15 static const char rcsid[] =
21 * timer_manager_ -- routines for handling timers in login_shell
24 * Copyright 1986 Student Information Processing Board,
25 * Massachusetts Institute of Technology
27 * written by Ken Raeburn
29 Permission to use, copy, modify, and distribute this
30 software and its documentation for any purpose and without
31 fee is hereby granted, provided that the above copyright
32 notice appear in all copies and that both that copyright
33 notice and this permission notice appear in supporting
34 documentation, and that the name of M.I.T. and the Student
35 Information Processing Board not be used in
36 advertising or publicity pertaining to distribution of the
37 software without specific, written prior permission.
38 M.I.T. and the Student Information Processing Board
39 make no representations about the suitability of
40 this software for any purpose. It is provided "as is"
41 without express or implied warranty.
49 * Timer *timer_set_rel (time_rel, proc, arg)
53 * Timer *timer_set_abs (time_abs, proc, arg)
58 * void timer_reset(tmr)
61 * void timer_process()
65 /* DELTA is just an offset to keep the size a bit less than a power
66 * of two. It's measured in pointers, so it's 32 bytes on most
69 #define INITIAL_HEAP_SIZE (1024 - DELTA)
71 /* We have three operations which we need to be able to perform
72 * quickly: adding a timer, deleting a timer given a pointer to
73 * it, and determining which timer will be the next to go off. A
74 * heap is an ideal data structure for these purposes, so we use
75 * one. The heap is an array of pointers to timers, and each timer
76 * knows the position of its pointer in the heap.
78 * Okay, what is the heap, exactly? It's a data structure,
79 * represented as an array, with the invariant condition that
80 * the timeout of heap[i] is less than or equal to the timeout of
81 * heap[i * 2 + 1] and heap[i * 2 + 2] (assuming i * 2 + 1 and
82 * i * 2 + 2 are valid * indices). An obvious consequence of this
83 * is that heap[0] has the lowest timer value, so finding the first
84 * timer to go off is easy. We say that an index i has "children"
85 * i * 2 + 1 and i * 2 + 1, and the "parent" (i - 1) / 2.
87 * To add a timer to the heap, we start by adding it to the end, and
88 * then keep swapping it with its parent until it has a parent with
89 * a timer value less than its value. With a little bit of thought,
90 * you can see that this preserves the heap property on all indices
93 * To delete a timer at position i from the heap, we discard it and
94 * fill in its position with the last timer in the heap. In order
95 * to restore the heap, we have to consider two cases: the timer
96 * value at i is less than that of its parent, or the timer value at
97 * i is greater than that of one of its children. In the first case,
98 * we propagate the timer at i up the tree, swapping it with its
99 * parent, until the heap is restored; in the second case, we
100 * propagate the timer down the tree, swapping it with its least
101 * child, until the heap is restored. */
103 /* In order to ensure that the back pointers from timers are consistent
104 * with the heap pointers, all heap assignments should be done with the
105 * HEAP_ASSIGN() macro, which sets the back pointer and updates the
106 * heap at the same time. */
107 #define PARENT(i) (((i) - 1) / 2)
108 #define CHILD1(i) ((i) * 2 + 1)
109 #define CHILD2(i) ((i) * 2 + 2)
110 #define TIME(i) (heap[i]->abstime)
111 #define HEAP_ASSIGN(pos, tmr) ((heap[pos] = (tmr))->heap_pos = (pos))
114 static int num_timers = 0;
115 static int heap_size = 0;
117 static void timer_botch (void*);
118 static Timer *add_timer (Timer *);
121 timer_set_rel(long time_rel,
122 void (*proc)(void *),
127 new_t = (Timer *) malloc(sizeof(*new_t));
130 new_t->abstime = time_rel + NOW;
133 return add_timer(new_t);
137 timer_reset(Timer *tmr)
141 /* Free the timer, saving its heap position. */
145 if (pos != num_timers - 1) {
146 /* Replace the timer with the last timer in the heap and
147 * restore the heap, propagating the timer either up or
148 * down, depending on which way it violates the heap
149 * property to insert the last timer in place of the
151 if (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos))) {
153 HEAP_ASSIGN(pos, heap[PARENT(pos)]);
155 } while (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos)));
156 HEAP_ASSIGN(pos, heap[num_timers - 1]);
158 while (CHILD2(pos) < num_timers) {
159 min = num_timers - 1;
160 if (TIME(CHILD1(pos)) < TIME(min))
162 if (TIME(CHILD2(pos)) < TIME(min))
164 HEAP_ASSIGN(pos, heap[min]);
167 if (pos != num_timers - 1)
168 HEAP_ASSIGN(pos, heap[num_timers - 1]);
175 #define set_timeval(t,s) ((t).tv_sec=(s),(t).tv_usec=0,(t))
178 add_timer(Timer *new)
182 /* Create or resize the heap as necessary. */
183 if (heap_size == 0) {
184 heap_size = INITIAL_HEAP_SIZE;
185 heap = (Timer **) malloc(heap_size * sizeof(Timer *));
186 } else if (num_timers >= heap_size) {
187 heap_size = heap_size * 2 + DELTA;
188 heap = (Timer **) realloc(heap, heap_size * sizeof(Timer *));
195 /* Insert the Timer *into the heap. */
197 while (pos > 0 && new->abstime < TIME(PARENT(pos))) {
198 HEAP_ASSIGN(pos, heap[PARENT(pos)]);
201 HEAP_ASSIGN(pos, new);
214 if (num_timers == 0 || heap[0]->abstime > NOW)
217 /* Remove the first timer from the heap, remembering its
218 * function and argument. */
222 t->func = timer_botch;
226 /* Run the function. */
231 timer_timeout(struct timeval *tvbuf)
233 if (num_timers > 0) {
234 tvbuf->tv_sec = heap[0]->abstime - NOW;
235 if (tvbuf->tv_sec < 0)
245 timer_botch(void *arg)
247 syslog(LOG_CRIT, "timer botch\n");