zephyr/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$
   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$";
  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 (void*);
 119 static Timer *add_timer (Timer *);
 120
 121 Timer *
 122 timer_set_rel(long time_rel,
 123               void (*proc)(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(Timer *tmr)
 139 {
 140     int pos, min;
 141
 142     /* Free the timer, saving its heap position. */
 143     pos = tmr->heap_pos;
 144     free(tmr);
 145
 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
 151          * deleted timer. */
 152         if (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos))) {
 153             do {
 154                 HEAP_ASSIGN(pos, heap[PARENT(pos)]);
 155                 pos = PARENT(pos);
 156             } while (pos > 0 && TIME(num_timers - 1) < TIME(PARENT(pos)));
 157             HEAP_ASSIGN(pos, heap[num_timers - 1]);
 158         } else {
 159             while (CHILD2(pos) < num_timers) {
 160                 min = num_timers - 1;
 161                 if (TIME(CHILD1(pos)) < TIME(min))
 162                     min = CHILD1(pos);
 163                 if (TIME(CHILD2(pos)) < TIME(min))
 164                     min = CHILD2(pos);
 165                 HEAP_ASSIGN(pos, heap[min]);
 166                 pos = min;
 167             }
 168             if (pos != num_timers - 1)
 169                 HEAP_ASSIGN(pos, heap[num_timers - 1]);
 170         }
 171     }
 172     num_timers--;
 173 }
 174
 175
 176 #define set_timeval(t,s) ((t).tv_sec=(s),(t).tv_usec=0,(t))
 177
 178 static Timer *
 179 add_timer(Timer *new)
 180 {
 181     int pos;
 182
 183     /* Create or resize the heap as necessary. */
 184     if (heap_size == 0) {
 185         heap_size = INITIAL_HEAP_SIZE;
 186         heap = (Timer **) malloc(heap_size * sizeof(Timer *));
 187     } else if (num_timers >= heap_size) {
 188         heap_size = heap_size * 2 + DELTA;
 189         heap = (Timer **) realloc(heap, heap_size * sizeof(Timer *));
 190     }
 191     if (!heap) {
 192         free(new);
 193         return NULL;
 194     }
 195
 196     /* Insert the Timer *into the heap. */
 197     pos = num_timers;
 198     while (pos > 0 && new->abstime < TIME(PARENT(pos))) {
 199         HEAP_ASSIGN(pos, heap[PARENT(pos)]);
 200         pos = PARENT(pos);
 201     }
 202     HEAP_ASSIGN(pos, new);
 203     num_timers++;
 204
 205     return new;
 206 }
 207
 208 void
 209 timer_process(void)
 210 {
 211     Timer *t;
 212     timer_proc func;
 213     void *arg;
 214
 215     if (num_timers == 0 || heap[0]->abstime > time(NULL))
 216         return;
 217
 218     /* Remove the first timer from the heap, remembering its
 219      * function and argument. */
 220     t = heap[0];
 221     func = t->func;
 222     arg = t->arg;
 223     t->func = timer_botch;
 224     t->arg = NULL;
 225     timer_reset(t);
 226
 227     /* Run the function. */
 228     func(arg);
 229 }
 230
 231 struct timeval *
 232 timer_timeout(struct timeval *tvbuf)
 233 {
 234     if (num_timers > 0) {
 235         tvbuf->tv_sec = heap[0]->abstime - time(NULL);
 236         if (tvbuf->tv_sec < 0)
 237             tvbuf->tv_sec = 0;
 238         tvbuf->tv_usec = 0;
 239         return tvbuf;
 240     } else {
 241         return NULL;
 242     }
 243 }
 244
 245 static void
 246 timer_botch(void *arg)
 247 {
 248     syslog(LOG_CRIT, "timer botch\n");
 249     abort();
 250 }
 251