[irc/quakenet/newserv.git] / core / schedule.c

/* schedule.c */

#include "schedule.h"
#include "error.h"
#include "hooks.h"
#include "../lib/array.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define INITSCHEDSIZE      1000
#define GROWSCHEDSIZE      500

#undef SCHEDDEBUG

schedule **events;
int heapsize;
int heapmax;

int schedadds;
int scheddels;
int scheddelfast;
int schedexes;

/* Local prototypes */
void schedulestats(int hooknum, void *arg);

void initschedule() {
  events=NULL;
  schedadds=scheddels=schedexes=scheddelfast=0;
  registerhook(HOOK_CORE_STATSREQUEST, &schedulestats);
  heapsize=0;
  heapmax=INITSCHEDSIZE;
  events=(schedule **)malloc(INITSCHEDSIZE*sizeof(schedule *));
}

void finischedule() {
  deregisterhook(HOOK_CORE_STATSREQUEST, &schedulestats);
  free(events);
}

void schedule_heapify(int index) {
  int firstindex=index;
  schedule *ep;
  
  /* If this node is a leaf, do nothing */  
  if ((index*2)+1 >= heapsize) {
    return;
  }

  /* Check left child */  
  if (events[index]->nextschedule > events[(index*2)+1]->nextschedule) {
    firstindex=(index*2)+1;
  }

  /* Check right (if exists) */
  if ((index*2)+2 < heapsize) {
    if (events[firstindex]->nextschedule > events[(index*2)+2]->nextschedule) {
      firstindex=(index*2)+2;
    }
  }
  
  /* If both children were scheduled after us, we're done */
  if (firstindex==index) {
    return;
  }

  /* Swap the two pointers around in the heap */  
  ep=events[firstindex];
  events[firstindex]=events[index];
  events[index]=ep;

  /* Fix up the "index" field in the structures */
  events[firstindex]->index=firstindex;
  events[index]->index=index;
  
  schedule_heapify(firstindex);
}

void insertschedule (schedule *sp) {
  int mypos,myparent;

  schedadds++;
  
  if (heapsize>=heapmax) {
    /* We need to grow the heap */
    heapmax+=GROWSCHEDSIZE;
    events=(schedule **)realloc((void *)events,heapmax*sizeof(schedule *));
  }
  
  mypos=heapsize++;
  
  /* Travel up the heap looking for a slot for this new element */
  /* mypos points at a (vacant) candidate space; we either put the element
   * in this space, or pull it's parent down and try again with it's parent's space */
  for (;;) {
    myparent=(mypos-1)/2;
    if (mypos==0 || (sp->nextschedule >= events[myparent]->nextschedule)) {
      /* We reached the top, or our parent is scheduled before us -- end */
      events[mypos]=sp;
      sp->index=mypos;
      break;
    } else {
      /* Pull the parent into this space and move up the heap */
      events[mypos]=events[myparent];
      events[mypos]->index=mypos;
      mypos=myparent;
    }
  }
}

void schedule_remove (int index) {
  int mypos,myparent;
  schedule *sp;

  assert(index<heapsize);

#ifdef SCHEDDEBUG
  Error("schedule",ERR_DEBUG,"schedule_remove: %d",index);
#endif

  if (index<0)
    return;

  scheddels++;  
  heapsize--;
  
  /* Move the last element into the position we just deleted, then heapify 
   * If we happen to be deleting the last element, do nothing */
  if (index!=heapsize) {
    events[index]->index=-1;
    events[index]=events[heapsize];
    events[index]->index=index;
    schedule_heapify(index);
    
    /* Now we may need to float the element up the heap, similar to the insert case */
    mypos=index;
    for (;;) {
      myparent=(mypos-1)/2;
      if (mypos==0 || (events[mypos]->nextschedule >= events[myparent]->nextschedule)) {
        break;
      } else {
        /* Swap the element up the tree */
        sp=events[myparent];
        events[myparent]=events[mypos];
        events[mypos]=sp;
        /* Fix up the index members */
        events[myparent]->index=myparent;
        events[mypos]->index=mypos;
        
        mypos=myparent;
      }
    }
  }
}
  
void *scheduleoneshot(time_t when, ScheduleCallback callback, void *arg) {
  schedule *sp;
  
  sp=getschedule();
  
  sp->nextschedule=when;
  sp->type=SCHEDULE_ONESHOT;
  sp->repeatinterval=0;
  sp->repeatcount=1;
  sp->callback=callback;
  sp->callbackparam=arg;

  insertschedule(sp);
  
#ifdef SCHEDDEBUG
  Error("schedule",ERR_DEBUG,"scheduleoneshot: (%ld, %x, %x) = %x",when, (unsigned int)callback, (unsigned int)arg, (unsigned int)sp);
#endif

  return (void *)sp;
}

void *schedulerecurring(time_t first, int count, time_t interval, ScheduleCallback callback, void *arg) {
  schedule *sp;

  if (count==1) {
    return scheduleoneshot(first, callback, arg);
  }

  sp=getschedule();

  sp->nextschedule=first;
  sp->type=SCHEDULE_REPEATING;
  sp->repeatinterval=interval;
  sp->repeatcount=(count-1);
  sp->callback=callback;
  sp->callbackparam=arg;
  
  insertschedule(sp);
  
  return (void *)sp;
}

void deleteschedule(void *sch, ScheduleCallback callback, void *arg) {
  schedule *sp;
  int i;
  
  /* New (optional) faster path: Clients can track the schedule pointer if they wish and 
   * pass it in here for an O(1) *cough* O(lg n) delete */

#ifdef SCHEDDEBUG
  Error("schedule",ERR_DEBUG,"deleteschedule(%x,%x,%x)",(unsigned int)sch,(unsigned int)callback, (unsigned int)arg);
#endif

  if (sch) {
    sp=(schedule *)sch;
    /* Double check the params are correct: 
     *  because we recycle and never free schedule structs it's
     *  actually OK to try and delete a schedule that has been executed... */
     
    if (sp->callback==callback && sp->callbackparam==arg) {
      scheddelfast++;
      schedule_remove(sp->index);
      freeschedule(sp);
    }
    return;
  }
  
  /* Argh, have to find it by brute force */

  for(i=0;i<heapsize;i++) {
    if ((events[i]->callback==callback) && (events[i]->callbackparam==arg)) {
      sp=events[i];
      schedule_remove(sp->index);
      freeschedule(sp);
      return;
    }
  }
}

void deleteallschedules(ScheduleCallback callback) {
  schedule *sp;
  int i;
  
trydel:
  /* OK, this gets to be REALLY cheesy and stupidly slow as well */
  
  for(i=0;i<heapsize;i++) {
    if (events[i]->callback==callback) {
      sp=events[i];
      schedule_remove(sp->index);
      freeschedule(sp);
      goto trydel;
    }
  }
}

void doscheduledevents(time_t when) {
  void *arg;
  ScheduleCallback sc;
  schedule *sp;

  while (heapsize && events[0] && events[0]->nextschedule <= when) {
    /* Pick out the first element first */
    sp=events[0];
    sp->index=-1; /* Invalidate index so that an explicit delete doesn't screw us up */

    /* Remove from the top of the heap */
    heapsize--;
    events[0]=events[heapsize];
    events[0]->index=0;
    schedule_heapify(0);
    
    if (sp->callback==NULL) {
      Error("core",ERR_ERROR,"Tried to call NULL function in doscheduledevents(): (%p, %p, %p)",sp,sp->callback,sp->callbackparam);
      continue;
    }

    /* Store the callback */
    arg=(sp->callbackparam);
    sc=(sp->callback);
    
    /* Update the structures _before_ doing the callback.. */
    switch(sp->type) {
    case SCHEDULE_ONESHOT:
      freeschedule(sp);
      break;
        
    case SCHEDULE_REPEATING:
      sp->nextschedule+=sp->repeatinterval;
      /* Repeat count:
       *  0 for repeat forever
       *  1 for repeat set number of times..
       *
       * When we schedule it for the last time, change it to a ONESHOT event
       */
      if (sp->repeatcount>0) {
	sp->repeatcount--;
	if (sp->repeatcount==0) {
	  sp->type=SCHEDULE_ONESHOT;       
	}
      }
      insertschedule(sp);
      break;
    }
#ifdef SCHEDDEBUG
    Error("schedule",ERR_DEBUG,"exec schedule:(%x, %x, %x)", (unsigned int)sp, (unsigned int)sc, (unsigned int)arg);
#endif
    (sc)(arg);
#ifdef SCHEDDEBUG
    Error("schedule",ERR_DEBUG,"schedule run OK");
#endif
    schedexes++;
  }
}

void schedulestats(int hooknum, void *arg) {
  long level=(long)arg;
  char buf[512];

  if (level>5) {
    sprintf(buf,"Schedule:%7d events scheduled, %7d events executed",schedadds,schedexes);
    triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
    sprintf(buf,"Schedule:%7d events deleted,   %7d fast deletes (%.2f%%)",scheddels,scheddelfast,(float)(scheddelfast*100)/scheddels);
    triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
    sprintf(buf,"Schedule:%7d events currently in queue",heapsize);
    triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
  }
}
Commit	Line	Data
2c5db955 CP	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() {
2c5db955 CP	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(INITSCHEDSIZEsizeof(schedule *));
	36	}
	37
f074aada P	38	void finischedule() {
	39	deregisterhook(HOOK_CORE_STATSREQUEST, &schedulestats);
	40	free(events);
	41	}
	42
2c5db955 CP	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,heapmaxsizeof(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
170	insertschedule(sp);
171
172	#ifdef SCHEDDEBUG
f074aada	173	Error("schedule",ERR_DEBUG,"scheduleoneshot: (%ld, %x, %x) = %x",when, (unsigned int)callback, (unsigned int)arg, (unsigned int)sp);
2c5db955 CP	174	#endif
	175
	176	return (void *)sp;
	177	}
	178
	179	void schedulerecurring(time_t first, int count, time_t interval, ScheduleCallback callback, void arg) {
	180	schedule *sp;
	181
	182	if (count==1) {
	183	return scheduleoneshot(first, callback, arg);
	184	}
	185
	186	sp=getschedule();
	187
	188	sp->nextschedule=first;
	189	sp->type=SCHEDULE_REPEATING;
	190	sp->repeatinterval=interval;
	191	sp->repeatcount=(count-1);
	192	sp->callback=callback;
	193	sp->callbackparam=arg;
	194
	195	insertschedule(sp);
	196
	197	return (void *)sp;
	198	}
	199
	200	void deleteschedule(void sch, ScheduleCallback callback, void arg) {
	201	schedule *sp;
	202	int i;
	203
	204	/* New (optional) faster path: Clients can track the schedule pointer if they wish and
	205	* pass it in here for an O(1) cough O(lg n) delete */
	206
	207	#ifdef SCHEDDEBUG
f074aada	208	Error("schedule",ERR_DEBUG,"deleteschedule(%x,%x,%x)",(unsigned int)sch,(unsigned int)callback, (unsigned int)arg);
2c5db955 CP	209	#endif
	210
	211	if (sch) {
	212	sp=(schedule *)sch;
	213	/* Double check the params are correct:
	214	* because we recycle and never free schedule structs it's
	215	* actually OK to try and delete a schedule that has been executed... */
	216
	217	if (sp->callback==callback && sp->callbackparam==arg) {
	218	scheddelfast++;
	219	schedule_remove(sp->index);
	220	freeschedule(sp);
	221	}
	222	return;
	223	}
	224
	225	/* Argh, have to find it by brute force */
	226
	227	for(i=0;i<heapsize;i++) {
	228	if ((events[i]->callback==callback) && (events[i]->callbackparam==arg)) {
	229	sp=events[i];
	230	schedule_remove(sp->index);
	231	freeschedule(sp);
	232	return;
	233	}
	234	}
	235	}
	236
	237	void deleteallschedules(ScheduleCallback callback) {
	238	schedule *sp;
	239	int i;
	240
	241	trydel:
	242	/* OK, this gets to be REALLY cheesy and stupidly slow as well */
	243
	244	for(i=0;i<heapsize;i++) {
	245	if (events[i]->callback==callback) {
	246	sp=events[i];
	247	schedule_remove(sp->index);
	248	freeschedule(sp);
	249	goto trydel;
	250	}
	251	}
	252	}
	253
	254	void doscheduledevents(time_t when) {
	255	void *arg;
	256	ScheduleCallback sc;
	257	schedule *sp;
	258
	259	while (heapsize && events[0] && events[0]->nextschedule <= when) {
	260	/* Pick out the first element first */
	261	sp=events[0];
	262	sp->index=-1; /* Invalidate index so that an explicit delete doesn't screw us up */
	263
	264	/* Remove from the top of the heap */
	265	heapsize--;
	266	events[0]=events[heapsize];
	267	events[0]->index=0;
	268	schedule_heapify(0);
	269
	270	if (sp->callback==NULL) {
16739dbe	271	Error("core",ERR_ERROR,"Tried to call NULL function in doscheduledevents(): (%p, %p, %p)",sp,sp->callback,sp->callbackparam);
2c5db955 CP	272	continue;
	273	}
	274
	275	/* Store the callback */
	276	arg=(sp->callbackparam);
	277	sc=(sp->callback);
	278
	279	/* Update the structures _before_ doing the callback.. */
	280	switch(sp->type) {
	281	case SCHEDULE_ONESHOT:
	282	freeschedule(sp);
	283	break;
	284
	285	case SCHEDULE_REPEATING:
	286	sp->nextschedule+=sp->repeatinterval;
	287	/* Repeat count:
	288	* 0 for repeat forever
	289	* 1 for repeat set number of times..
	290	*
	291	* When we schedule it for the last time, change it to a ONESHOT event
	292	*/
	293	if (sp->repeatcount>0) {
	294	sp->repeatcount--;
	295	if (sp->repeatcount==0) {
	296	sp->type=SCHEDULE_ONESHOT;
	297	}
	298	}
	299	insertschedule(sp);
	300	break;
	301	}
	302	#ifdef SCHEDDEBUG
f074aada	303	Error("schedule",ERR_DEBUG,"exec schedule:(%x, %x, %x)", (unsigned int)sp, (unsigned int)sc, (unsigned int)arg);
2c5db955 CP	304	#endif
	305	(sc)(arg);
	306	#ifdef SCHEDDEBUG
	307	Error("schedule",ERR_DEBUG,"schedule run OK");
	308	#endif
	309	schedexes++;
	310	}
	311	}
	312
	313	void schedulestats(int hooknum, void *arg) {
c3db6f7e	314	long level=(long)arg;
2c5db955 CP	315	char buf[512];
	316
	317	if (level>5) {
	318	sprintf(buf,"Schedule:%7d events scheduled, %7d events executed",schedadds,schedexes);
	319	triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
	320	sprintf(buf,"Schedule:%7d events deleted, %7d fast deletes (%.2f%%)",scheddels,scheddelfast,(float)(scheddelfast*100)/scheddels);
	321	triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
	322	sprintf(buf,"Schedule:%7d events currently in queue",heapsize);
	323	triggerhook(HOOK_CORE_STATSREPLY,(void *)buf);
	324	}
	325	}