/* Copyright 1989, 1990 by James Aspnes, David Applegate, and Bennet Yee */ /* See the file COPYING for distribution information */ #include "db.h" #include "config.h" #include "globals.h" #include "externs.h" int no_delays = 0; /* elements in delay heap */ struct thunk { datum thing; datum time; }; static struct thunk *delay_heap = 0; static int delay_heap_size = 0; int delay_heap_top = 0; /* inserts 'me' into the delay heap at specified time */ datum delay (datum t) { datum current_time; int i; /* for scanning up the delay heap */ int parent; /* only WIZARD objects can delay when blocked */ if (no_delays && !flag_set (me, F_WIZARD)) return 0; /* can't schedule into the past */ current_time = time (0); if (current_time > t) t = current_time; /* get the place to put it in */ i = delay_heap_top++; /* make sure there is enough room */ if (delay_heap_size == 0) { delay_heap = (struct thunk *) malloc (sizeof (struct thunk)); delay_heap_size = 1; } else if (delay_heap_top >= delay_heap_size) { delay_heap_size *= 2; delay_heap = (struct thunk *) realloc ((void *) delay_heap, sizeof (struct thunk) * delay_heap_size); } /* find the spot for the new thing, floating other thunks down */ while (i > 0 && t < delay_heap[parent = (i - 1) / 2].time) { delay_heap[i] = delay_heap[parent]; i = parent; } /* insert new thunk */ delay_heap[i].thing = me; delay_heap[i].time = t; return 1; } /* removes the heap element at position i */ static void delete_heap_element (int i) { int left; /* twice i, left child */ int winner; /* earlier child of left & left+1 */ if (i >= delay_heap_top) return; delay_heap_top--; /* cut off the last element */ while ((left = i + i + 1) < delay_heap_top) { /* find earlier child */ if (left + 1 >= delay_heap_top || delay_heap[left].time < delay_heap[left + 1].time) { winner = left; } else { winner = left + 1; } /* do we keep going? */ if (delay_heap[delay_heap_top].time <= delay_heap[winner].time) break; /* yes, we keep going */ delay_heap[i] = delay_heap[winner]; i = winner; } /* stuff the last node into place */ delay_heap[i] = delay_heap[delay_heap_top]; } /* returns thing in heap scheduled for earliest time <= t, if any */ /* and deletes it from the heap */ datum undelay (datum t) { datum thing; /* check to see if we're going to return anything at all */ if (delay_heap_top == 0 || delay_heap[0].time > t) return NOTHING; /* else there's something there */ /* save the thing */ thing = delay_heap[0].thing; delete_heap_element (0); /* kill the root */ /* return what we found up top */ return thing; } /* removes all pending delays for an object */ void remove_delays (datum victim) { int i; i = 0; while (i < delay_heap_top) { if (delay_heap[i].thing == victim) { delete_heap_element (i); /* believe it or not, this actually works! */ /* why? well, when we float the min down from position i */ /* we are only affecting the array for positions >= i */ /* thus we don't have to worry about skipping some other */ /* heap element we want to delete, since if it's < i we will */ /* have processed it already */ /* (it only looks like we are being stupid) */ } else { i++; /* try the next position */ } } } unsigned long next_event_time (void) { if (delay_heap_top > 0) { return delay_heap[0].time; } else { return 0; } }