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 __P((void*));
118 static Timer *add_timer __P((Timer *));
120 Timer *timer_set_rel(time_rel, proc, arg)
122 void (*proc) __P((void *));
127 new_t = (Timer *) malloc(sizeof(*new_t));
130 new_t->abstime = time_rel + NOW;
133 return add_timer(new_t);
142 /* Free the timer, saving its heap position. */
146 if (pos != num_timers - 1) {
147 /* Replace the timer with the last timer in the heap and
148 * restore the heap, propagating the timer either up or
149 * down, depending on which way it violates the heap
150 * property to insert the last timer in place of the
152 if (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos))) {
154 HEAP_ASSIGN(pos, heap[PARENT(pos)]);
156 } while (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos)));
157 HEAP_ASSIGN(pos, heap[num_timers - 1]);
159 while (CHILD2(pos) < num_timers) {
160 min = num_timers - 1;
161 if (TIME(CHILD1(pos)) < TIME(min))
163 if (TIME(CHILD2(pos)) < TIME(min))
165 HEAP_ASSIGN(pos, heap[min]);
168 if (pos != num_timers - 1)
169 HEAP_ASSIGN(pos, heap[num_timers - 1]);
176 #define set_timeval(t,s) ((t).tv_sec=(s),(t).tv_usec=0,(t))
184 /* Create or resize the heap as necessary. */
185 if (heap_size == 0) {
186 heap_size = INITIAL_HEAP_SIZE;
187 heap = (Timer **) malloc(heap_size * sizeof(Timer *));
188 } else if (num_timers >= heap_size) {
189 heap_size = heap_size * 2 + DELTA;
190 heap = (Timer **) realloc(heap, heap_size * sizeof(Timer *));
197 /* Insert the Timer *into the heap. */
199 while (pos > 0 && new->abstime < TIME(PARENT(pos))) {
200 HEAP_ASSIGN(pos, heap[PARENT(pos)]);
203 HEAP_ASSIGN(pos, new);
217 if (num_timers == 0 || heap[0]->abstime > NOW)
220 /* Remove the first timer from the heap, remembering its
221 * function and argument. */
225 t->func = timer_botch;
229 /* Run the function. */
235 struct timeval *tvbuf;
237 if (num_timers > 0) {
238 tvbuf->tv_sec = heap[0]->abstime - NOW;
239 if (tvbuf->tv_sec < 0)
252 syslog(LOG_CRIT, "timer botch\n");