zhm/timer.c

   1 /* This file is part of the Project Athena Zephyr Notification System.
   2  * It contains functions for managing multiple timeouts.
   3  *
   4  *      Created by:     John T. Kohl
   5  *      Derived from timer_manager_ by Ken Raeburn
   6  *
   7  *      $Id: timer.c,v 1.2 1999/01/22 23:19:58 ghudson Exp $
   8  *
   9  */
  10
  11 #include "internal.h"
  12 #include "timer.h"
  13
  14 #ifndef SABER
  15 #ifndef lint
  16 static const char rcsid[] =
  17 "$Id: timer.c,v 1.2 1999/01/22 23:19:58 ghudson Exp $";
  18 #endif /* lint */
  19 #endif /* SABER */
  20
  21 /*
  22  * timer_manager_ -- routines for handling timers in login_shell
  23  * (and elsewhere)
  24  *
  25  * Copyright 1986 Student Information Processing Board,
  26  * Massachusetts Institute of Technology
  27  *
  28  * written by Ken Raeburn
  29
  30  Permission to use, copy, modify, and distribute this
  31  software and its documentation for any purpose and without
  32  fee is hereby granted, provided that the above copyright
  33  notice appear in all copies and that both that copyright
  34  notice and this permission notice appear in supporting
  35  documentation, and that the name of M.I.T. and the Student
  36  Information Processing Board not be used in
  37  advertising or publicity pertaining to distribution of the
  38  software without specific, written prior permission.
  39  M.I.T. and the Student Information Processing Board
  40  make no representations about the suitability of
  41  this software for any purpose.  It is provided "as is"
  42  without express or implied warranty.
  43
  44  */
  45
  46
  47 /*
  48  * External functions:
  49  *
  50  * Timer *timer_set_rel (time_rel, proc, arg)
  51  *      long time_rel;
  52  *      void (*proc)();
  53  *      caddr_t arg;
  54  * Timer *timer_set_abs (time_abs, proc, arg)
  55  *      long time_abs;
  56  *      void (*proc)();
  57  *      caddr_t arg;
  58  *
  59  * void timer_reset(tmr)
  60  *      Timer *tmr;
  61  *
  62  * void timer_process()
  63  *
  64  */
  65
  66 /* DELTA is just an offset to keep the size a bit less than a power
  67  * of two.  It's measured in pointers, so it's 32 bytes on most
  68  * systems. */
  69 #define DELTA 8
  70 #define INITIAL_HEAP_SIZE (1024 - DELTA)
  71
  72 /* We have three operations which we need to be able to perform
  73  * quickly: adding a timer, deleting a timer given a pointer to
  74  * it, and determining which timer will be the next to go off.  A
  75  * heap is an ideal data structure for these purposes, so we use
  76  * one.  The heap is an array of pointers to timers, and each timer
  77  * knows the position of its pointer in the heap.
  78  *
  79  * Okay, what is the heap, exactly?  It's a data structure,
  80  * represented as an array, with the invariant condition that
  81  * the timeout of heap[i] is less than or equal to the timeout of
  82  * heap[i * 2 + 1] and heap[i * 2 + 2] (assuming i * 2 + 1 and
  83  * i * 2 + 2 are valid * indices).  An obvious consequence of this
  84  * is that heap[0] has the lowest timer value, so finding the first
  85  * timer to go off is easy.  We say that an index i has "children"
  86  * i * 2 + 1 and i * 2 + 1, and the "parent" (i - 1) / 2.
  87  *
  88  * To add a timer to the heap, we start by adding it to the end, and
  89  * then keep swapping it with its parent until it has a parent with
  90  * a timer value less than its value.  With a little bit of thought,
  91  * you can see that this preserves the heap property on all indices
  92  * of the array.
  93  *
  94  * To delete a timer at position i from the heap, we discard it and
  95  * fill in its position with the last timer in the heap.  In order
  96  * to restore the heap, we have to consider two cases: the timer
  97  * value at i is less than that of its parent, or the timer value at
  98  * i is greater than that of one of its children.  In the first case,
  99  * we propagate the timer at i up the tree, swapping it with its
 100  * parent, until the heap is restored; in the second case, we
 101  * propagate the timer down the tree, swapping it with its least
 102  * child, until the heap is restored. */
 103
 104 /* In order to ensure that the back pointers from timers are consistent
 105  * with the heap pointers, all heap assignments should be done with the
 106  * HEAP_ASSIGN() macro, which sets the back pointer and updates the
 107  * heap at the same time. */
 108 #define PARENT(i) (((i) - 1) / 2)
 109 #define CHILD1(i) ((i) * 2 + 1)
 110 #define CHILD2(i) ((i) * 2 + 2)
 111 #define TIME(i) (heap[i]->abstime)
 112 #define HEAP_ASSIGN(pos, tmr) ((heap[pos] = (tmr))->heap_pos = (pos))
 113
 114 static Timer **heap;
 115 static int num_timers = 0;
 116 static int heap_size = 0;
 117
 118 static void timer_botch __P((void*));
 119 static Timer *add_timer __P((Timer *));
 120
 121 Timer *timer_set_rel(time_rel, proc, arg)
 122     long time_rel;
 123     void (*proc) __P((void *));
 124     void *arg;
 125 {
 126     Timer *new_t;
 127
 128     new_t = (Timer *) malloc(sizeof(*new_t));
 129     if (new_t == NULL)
 130         return(NULL);
 131     new_t->abstime = time_rel + time(NULL);
 132     new_t->func = proc;
 133     new_t->arg = arg;
 134     return add_timer(new_t);
 135 }
 136
 137 void
 138 timer_reset(tmr)
 139     Timer *tmr;
 140 {
 141     int pos, min;
 142
 143     /* Free the timer, saving its heap position. */
 144     pos = tmr->heap_pos;
 145     free(tmr);
 146
 147     if (pos != num_timers - 1) {
 148         /* Replace the timer with the last timer in the heap and
 149          * restore the heap, propagating the timer either up or
 150          * down, depending on which way it violates the heap
 151          * property to insert the last timer in place of the
 152          * deleted timer. */
 153         if (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos))) {
 154             do {
 155                 HEAP_ASSIGN(pos, heap[PARENT(pos)]);
 156                 pos = PARENT(pos);
 157             } while (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos)));
 158             HEAP_ASSIGN(pos, heap[num_timers - 1]);
 159         } else {
 160             while (CHILD2(pos) < num_timers) {
 161                 min = num_timers - 1;
 162                 if (TIME(CHILD1(pos)) < TIME(min))
 163                     min = CHILD1(pos);
 164                 if (TIME(CHILD2(pos)) < TIME(min))
 165                     min = CHILD2(pos);
 166                 HEAP_ASSIGN(pos, heap[min]);
 167                 pos = min;
 168             }
 169             if (pos != num_timers - 1)
 170                 HEAP_ASSIGN(pos, heap[num_timers - 1]);
 171         }
 172     }
 173     num_timers--;
 174 }
 175
 176
 177 #define set_timeval(t,s) ((t).tv_sec=(s),(t).tv_usec=0,(t))
 178
 179 static Timer *
 180 add_timer(new)
 181     Timer *new;
 182 {
 183     int pos;
 184
 185     /* Create or resize the heap as necessary. */
 186     if (heap_size == 0) {
 187         heap_size = INITIAL_HEAP_SIZE;
 188         heap = (Timer **) malloc(heap_size * sizeof(Timer *));
 189     } else if (num_timers >= heap_size) {
 190         heap_size = heap_size * 2 + DELTA;
 191         heap = (Timer **) realloc(heap, heap_size * sizeof(Timer *));
 192     }
 193     if (!heap) {
 194         free(new);
 195         return NULL;
 196     }
 197
 198     /* Insert the Timer *into the heap. */
 199     pos = num_timers;
 200     while (pos > 0 && new->abstime < TIME(PARENT(pos))) {
 201         HEAP_ASSIGN(pos, heap[PARENT(pos)]);
 202         pos = PARENT(pos);
 203     }
 204     HEAP_ASSIGN(pos, new);
 205     num_timers++;
 206
 207     return new;
 208 }
 209
 210 void
 211 timer_process()
 212 {
 213     Timer *t;
 214     timer_proc func;
 215     void *arg;
 216     int valid = 0;
 217
 218     if (num_timers == 0 || heap[0]->abstime > time(NULL))
 219         return;
 220
 221     /* Remove the first timer from the heap, remembering its
 222      * function and argument. */
 223     t = heap[0];
 224     func = t->func;
 225     arg = t->arg;
 226     t->func = timer_botch;
 227     t->arg = NULL;
 228     timer_reset(t);
 229
 230     /* Run the function. */
 231     func(arg);
 232 }
 233
 234 struct timeval *
 235 timer_timeout(tvbuf)
 236     struct timeval *tvbuf;
 237 {
 238     if (num_timers > 0) {
 239         tvbuf->tv_sec = heap[0]->abstime - time(NULL);
 240         if (tvbuf->tv_sec < 0)
 241             tvbuf->tv_sec = 0;
 242         tvbuf->tv_usec = 0;
 243         return tvbuf;
 244     } else {
 245         return NULL;
 246     }
 247 }
 248
 249 static void
 250 timer_botch(arg)
 251     void *arg;
 252 {
 253     syslog(LOG_CRIT, "timer botch\n");
 254     abort();
 255 }
 256