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