core/schedule.c

   1 /* schedule.c */
   2
   3 #include "schedule.h"
   4 #include "error.h"
   5 #include "hooks.h"
   6 #include "../lib/array.h"
   7 #include <string.h>
   8 #include <stdlib.h>
   9 #include <stdio.h>
  10 #include <assert.h>
  11
  12 #define INITSCHEDSIZE      1000
  13 #define GROWSCHEDSIZE      500
  14
  15 #undef SCHEDDEBUG
  16
  17 schedule **events;
  18 int heapsize;
  19 int heapmax;
  20
  21 int schedadds;
  22 int scheddels;
  23 int scheddelfast;
  24 int schedexes;
  25
  26 /* Local prototypes */
  27 void schedulestats(int hooknum, void *arg);
  28
  29 void initschedule() {
  30   events=NULL;
  31   schedadds=scheddels=schedexes=scheddelfast=0;
  32   registerhook(HOOK_CORE_STATSREQUEST, &schedulestats);
  33   heapsize=0;
  34   heapmax=INITSCHEDSIZE;
  35   events=(schedule **)malloc(INITSCHEDSIZE*sizeof(schedule *));
  36 }
  37
  38 void finischedule() {
  39   deregisterhook(HOOK_CORE_STATSREQUEST, &schedulestats);
  40   free(events);
  41 }
  42
  43 void schedule_heapify(int index) {
  44   int firstindex=index;
  45   schedule *ep;
  46
  47   /* If this node is a leaf, do nothing */
  48   if ((index*2)+1 >= heapsize) {
  49     return;
  50   }
  51
  52   /* Check left child */
  53   if (events[index]->nextschedule > events[(index*2)+1]->nextschedule) {
  54     firstindex=(index*2)+1;
  55   }
  56
  57   /* Check right (if exists) */
  58   if ((index*2)+2 < heapsize) {
  59     if (events[firstindex]->nextschedule > events[(index*2)+2]->nextschedule) {
  60       firstindex=(index*2)+2;
  61     }
  62   }
  63
  64   /* If both children were scheduled after us, we're done */
  65   if (firstindex==index) {
  66     return;
  67   }
  68
  69   /* Swap the two pointers around in the heap */
  70   ep=events[firstindex];
  71   events[firstindex]=events[index];
  72   events[index]=ep;
  73
  74   /* Fix up the "index" field in the structures */
  75   events[firstindex]->index=firstindex;
  76   events[index]->index=index;
  77
  78   schedule_heapify(firstindex);
  79 }
  80
  81 void insertschedule (schedule *sp) {
  82   int mypos,myparent;
  83
  84   schedadds++;
  85
  86   if (heapsize>=heapmax) {
  87     /* We need to grow the heap */
  88     heapmax+=GROWSCHEDSIZE;
  89     events=(schedule **)realloc((void *)events,heapmax*sizeof(schedule *));
  90   }
  91
  92   mypos=heapsize++;
  93
  94   /* Travel up the heap looking for a slot for this new element */
  95   /* mypos points at a (vacant) candidate space; we either put the element
  96    * in this space, or pull it's parent down and try again with it's parent's space */
  97   for (;;) {
  98     myparent=(mypos-1)/2;
  99     if (mypos==0 || (sp->nextschedule >= events[myparent]->nextschedule)) {
 100       /* We reached the top, or our parent is scheduled before us -- end */
 101       events[mypos]=sp;
 102       sp->index=mypos;
 103       break;
 104     } else {
 105       /* Pull the parent into this space and move up the heap */
 106       events[mypos]=events[myparent];
 107       events[mypos]->index=mypos;
 108       mypos=myparent;
 109     }
 110   }
 111 }
 112
 113 void schedule_remove (int index) {
 114   int mypos,myparent;
 115   schedule *sp;
 116
 117   assert(index<heapsize);
 118
 119 #ifdef SCHEDDEBUG
 120   Error("schedule",ERR_DEBUG,"schedule_remove: %d",index);
 121 #endif
 122
 123   if (index<0)
 124     return;
 125
 126   scheddels++;
 127   heapsize--;
 128
 129   /* Move the last element into the position we just deleted, then heapify
 130    * If we happen to be deleting the last element, do nothing */
 131   if (index!=heapsize) {
 132     events[index]->index=-1;
 133     events[index]=events[heapsize];
 134     events[index]->index=index;
 135     schedule_heapify(index);
 136
 137     /* Now we may need to float the element up the heap, similar to the insert case */
 138     mypos=index;
 139     for (;;) {
 140       myparent=(mypos-1)/2;
 141       if (mypos==0 || (events[mypos]->nextschedule >= events[myparent]->nextschedule)) {
 142         break;
 143       } else {
 144         /* Swap the element up the tree */
 145         sp=events[myparent];
 146         events[myparent]=events[mypos];
 147         events[mypos]=sp;
 148         /* Fix up the index members */
 149         events[myparent]->index=myparent;
 150         events[mypos]->index=mypos;
 151
 152         mypos=myparent;
 153       }
 154     }
 155   }
 156 }
 157
 158 void *scheduleoneshot(time_t when, ScheduleCallback callback, void *arg) {
 159   schedule *sp;
 160
 161   sp=getschedule();
 162
 163   sp->nextschedule=when;
 164   sp->type=SCHEDULE_ONESHOT;
 165   sp->repeatinterval=0;
 166   sp->repeatcount=1;
 167   sp->callback=callback;
 168   sp->callbackparam=arg;
 169   sp->deleted=0;
 170
 171   insertschedule(sp);
 172
 173 #ifdef SCHEDDEBUG
 174   Error("schedule",ERR_DEBUG,"scheduleoneshot: (%ld, %x, %x) = %x",when, (unsigned int)callback, (unsigned int)arg, (unsigned int)sp);
 175 #endif
 176
 177   return (void *)sp;
 178 }
 179
 180 void *schedulerecurring(time_t first, int count, time_t interval, ScheduleCallback callback, void *arg) {
 181   schedule *sp;
 182
 183   if (count==1) {
 184     return scheduleoneshot(first, callback, arg);
 185   }
 186
 187   sp=getschedule();
 188
 189   sp->nextschedule=first;
 190   sp->type=SCHEDULE_REPEATING;
 191   sp->repeatinterval=interval;
 192   sp->repeatcount=(count-1);
 193   sp->callback=callback;
 194   sp->callbackparam=arg;
 195   sp->deleted=0;
 196
 197   insertschedule(sp);
 198
 199   return (void *)sp;
 200 }
 201
 202 void deleteschedule(void *sch, ScheduleCallback callback, void *arg) {
 203   schedule *sp;
 204   int i;
 205
 206   /* New (optional) faster path: Clients can track the schedule pointer if they wish and
 207    * pass it in here for an O(1) *cough* O(lg n) delete */
 208
 209 #ifdef SCHEDDEBUG
 210   Error("schedule",ERR_DEBUG,"deleteschedule(%x,%x,%x)",(unsigned int)sch,(unsigned int)callback, (unsigned int)arg);
 211 #endif
 212
 213   if (sch) {
 214     sp=(schedule *)sch;
 215     /* Double check the params are correct:
 216      * it's perfectly OK to delete a schedule that has been executed,
 217      * we're just marking the schedule as deleted here so that it can be
 218      * cleaned up by doscheduledevents later on. */
 219
 220     if (sp->callback==callback && sp->callbackparam==arg && !sp->deleted) {
 221       scheddelfast++;
 222       sp->deleted=1;
 223 #ifdef SCHEDDEBUG
 224     } else {
 225       Error("schedule",ERR_DEBUG,"deleted schedule that was previously marked as deleted");
 226 #endif
 227     }
 228     return;
 229   }
 230
 231   /* Argh, have to find it by brute force */
 232
 233   for(i=0;i<heapsize;i++) {
 234     if (events[i]->callback==callback && events[i]->callbackparam==arg && !events[i]->deleted) {
 235       sp=events[i];
 236       sp->deleted=1;
 237       return;
 238     }
 239   }
 240 }
 241
 242 void deleteallschedules(ScheduleCallback callback) {
 243   schedule *sp;
 244   int i;
 245
 246 trydel:
 247   /* OK, this gets to be REALLY cheesy and stupidly slow as well */
 248
 249   for(i=0;i<heapsize;i++) {
 250     if (events[i]->callback==callback) {
 251       sp=events[i];
 252       schedule_remove(sp->index);
 253       freeschedule(sp);
 254       goto trydel;
 255     }
 256   }
 257 }
 258
 259 void doscheduledevents(time_t when) {
 260   void *arg;
 261   ScheduleCallback sc;
 262   schedule *sp;
 263
 264   while (heapsize && events[0] && events[0]->nextschedule <= when) {
 265     /* Pick out the first element first */
 266     sp=events[0];
 267     sp->index=-1; /* Invalidate index so that an explicit delete doesn't screw us up */
 268
 269     /* Remove from the top of the heap */
 270     heapsize--;
 271     events[0]=events[heapsize];
 272     events[0]->index=0;
 273     schedule_heapify(0);
 274
 275     /* This schedule was previously marked as deleted and we're now lazily cleaning it up. */
 276     if (sp->deleted) {
 277       freeschedule(sp);
 278       continue;
 279     }
 280
 281     if (sp->callback==NULL) {
 282       Error("core",ERR_ERROR,"Tried to call NULL function in doscheduledevents(): (%p, %p, %p)",sp,sp->callback,sp->callbackparam);
 283       continue;
 284     }
 285
 286     /* Store the callback */
 287     arg=(sp->callbackparam);
 288     sc=(sp->callback);
 289
 290     /* Update the structures _before_ doing the callback.. */
 291     switch(sp->type) {
 292     case SCHEDULE_ONESHOT:
 293       sp->deleted=1;
 294       break;
 295
 296     case SCHEDULE_REPEATING:
 297       sp->nextschedule+=sp->repeatinterval;
 298       /* Repeat count:
 299        *  0 for repeat forever
 300        *  1 for repeat set number of times..
 301        *
 302        * When we schedule it for the last time, change it to a ONESHOT event
 303        */
 304       if (sp->repeatcount>0) {
 305         sp->repeatcount--;
 306         if (sp->repeatcount==0) {
 307           sp->type=SCHEDULE_ONESHOT;
 308         }
 309       }
 310       break;
 311     }
 312
 313     insertschedule(sp);
 314
 315 #ifdef SCHEDDEBUG
 316     Error("schedule",ERR_DEBUG,"exec schedule:(%x, %x, %x)", (unsigned int)sp, (unsigned int)sc, (unsigned int)arg);
 317 #endif
 318     (sc)(arg);
 319 #ifdef SCHEDDEBUG
 320     Error("schedule",ERR_DEBUG,"schedule run OK");
 321 #endif
 322     schedexes++;
 323   }
 324 }
 325
 326 void schedulestats(int hooknum, void *arg) {
 327   long level=(long)arg;
 328   char buf[512];
 329
 330   if (level>5) {
 331     sprintf(buf,"Schedule:%7d events scheduled, %7d events executed",schedadds,schedexes);
 332     triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
 333     sprintf(buf,"Schedule:%7d events deleted,   %7d fast deletes (%.2f%%)",scheddels,scheddelfast,(float)(scheddelfast*100)/scheddels);
 334     triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
 335     sprintf(buf,"Schedule:%7d events currently in queue",heapsize);
 336     triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
 337   }
 338 }