Modify scheduler to use a binary heap (using libpbl).

Scheduled events are now in event time order, so schedule_run simply takes the top
event off the heap and runs it (if we're polling, rather than having received a signal
that the next event is due to be run, we check first that we have passed the scheduled
time).

This should provide performance benefits as we are no longer trawling the entire list
of scheduled events (potentially hundreds) every time an event is signalled or the
schedule list is polled.

svn path=/trunk/netsurf/; revision=11703

5 files changed, 84 insertions, 75 deletions

diff --git a/amiga/Makefile.target b/amiga/Makefile.target
index 4d7022e19..8b49f204e 100644
--- a/amiga/Makefile.target
+++ b/amiga/Makefile.target
@@ -22,7 +22,7 @@ ifeq ($(HOST),amiga)
   $(eval $(call feature_enabled,AMIGA_ICON,-DWITH_AMIGA_ICON,,Amiga icon        ))
 
   CFLAGS += -D__USE_INLINE__ -D__USE_BASETYPE__ -I /SDK/local/common/include/libpng12
-  LDFLAGS += -lxml2 -lcurl -lrtmp -lpthread -lregex -lauto
+  LDFLAGS += -lxml2 -lcurl -lrtmp -lpthread -lregex -lauto -lpbl
   LDFLAGS += -lssl -lcrypto -lhubbub -lcss -lparserutils -lwapcaplet -liconv
 
   ifeq ($(NETSURF_AMIGA_USE_CAIRO),YES)
diff --git a/amiga/gui.c b/amiga/gui.c
index daaafe681..1db49bb27 100755
--- a/amiga/gui.c
+++ b/amiga/gui.c
@@ -457,8 +457,8 @@ void gui_init(int argc, char** argv)
 	plot=amiplot;
 
 	if(option_context_menu) ami_context_menu_init();
+	ami_schedule_create();
 
-	schedule_list = NewObjList();
 	window_list = NewObjList();
 
 	urldb_load(option_url_file);
@@ -1919,7 +1919,7 @@ void ami_get_msg(void)
 		while(timermsg = GetMsg(msgport))
 		{
 			ReplyMsg(timermsg);
-			schedule_run();
+			schedule_run(FALSE);
 		}
 	}
 }
@@ -1947,7 +1947,7 @@ void gui_poll(bool active)
 	if(active)
 	{
 		gui_multitask();
-		schedule_run();
+		schedule_run(TRUE);
 	}
 	else
 	{
@@ -2140,7 +2140,8 @@ void gui_quit(void)
 	FreeSysObject(ASOT_IOREQUEST,tioreq);
 	FreeSysObject(ASOT_PORT,msgport);
 
-	FreeObjList(schedule_list);
+	ami_schedule_free();
+
 	FreeObjList(window_list);
 }
 
diff --git a/amiga/object.c b/amiga/object.c
index 93094cbda..cb5adaa00 100755
--- a/amiga/object.c
+++ b/amiga/object.c
@@ -77,11 +77,7 @@ void FreeObjList(struct MinList *objlist)
 	do
 	{
 		nnode=(struct nsObject *)GetSucc((struct Node *)node);
-		if(node->Type == AMINS_CALLBACK)
-			ami_remove_timer_event((struct nscallback *)node->objstruct);
-
 		DelObject(node);
-		
 	}while(node=nnode);
 
 	FreeVec(objlist);
diff --git a/amiga/schedule.c b/amiga/schedule.c
index 7b8565960..1c670c4bb 100755
--- a/amiga/schedule.c
+++ b/amiga/schedule.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2008 Chris Young <chris@unsatisfactorysoftware.co.uk>
+ * Copyright 2008, 2011 Chris Young <chris@unsatisfactorysoftware.co.uk>
  *
  * This file is part of NetSurf, http://www.netsurf-browser.org/
  *
@@ -18,11 +18,24 @@
 
 #include "desktop/browser.h"
 #include "amiga/os3support.h"
-#include "amiga/object.h"
 #include "amiga/schedule.h"
 
 #include <proto/exec.h>
 
+#include <pbl.h>
+
+struct nscallback
+{
+	struct TimeVal tv;
+	void *callback;
+	void *p;
+	struct TimeRequest *treq;
+};
+
+PblHeap *schedule_list;
+
+void ami_remove_timer_event(struct nscallback *nscb);
+
 /**
  * Schedule a callback.
  *
@@ -36,22 +49,11 @@
 
 void schedule(int t, void (*callback)(void *p), void *p)
 {
-	struct nsObject *obj;
 	struct nscallback *nscb;
 	struct timeval tv;
 
-	obj = AddObject(schedule_list,AMINS_CALLBACK);
-	if(!obj) return;
-
-	obj->objstruct_size = sizeof(struct nscallback);
-	obj->objstruct = AllocVec(obj->objstruct_size,MEMF_PRIVATE | MEMF_CLEAR);
-	if(!obj->objstruct)
-	{
-		DelObject(obj);
-		return;
-	}
-
-	nscb = (struct nscallback *)obj->objstruct;
+	nscb = AllocVec(sizeof(struct nscallback), MEMF_PRIVATE | MEMF_CLEAR);
+	if(!nscb) return;
 
 	nscb->tv.Seconds = 0;
 	nscb->tv.Microseconds = t*10000;
@@ -76,6 +78,8 @@ void schedule(int t, void (*callback)(void *p), void *p)
 
 	nscb->callback = callback;
 	nscb->p = p;
+
+	pblHeapInsert(schedule_list, nscb);
 }
 
 /**
@@ -89,69 +93,65 @@ void schedule(int t, void (*callback)(void *p), void *p)
 
 void schedule_remove(void (*callback)(void *p), void *p)
 {
-	struct nsObject *node;
-	struct nsObject *nnode;
+	PblIterator *iterator;
 	struct nscallback *nscb;
+	bool restoreheap = false;
 
-	if(IsMinListEmpty(schedule_list)) return;
+	if(pblHeapIsEmpty(schedule_list)) return;
 
-	node = (struct nsObject *)GetHead((struct List *)schedule_list);
+	iterator = pblHeapIterator(schedule_list);
 
-	do
+	while ((nscb = pblIteratorNext(iterator)) != -1)
 	{
-		nnode=(struct nsObject *)GetSucc((struct Node *)node);
-
-		nscb = node->objstruct;
-		if(!nscb) continue;
-
 		if((nscb->callback == callback) && (nscb->p == p))
 		{
 			ami_remove_timer_event(nscb);
-			DelObject(node);
+			pblIteratorRemove(iterator);
+			FreeVec(nscb);
+			restoreheap = true;
 		}
+	};
 
-	}while (node=nnode);
+	pblIteratorFree(iterator);
+
+	if(restoreheap) pblHeapConstruct(schedule_list);
 }
 
 /**
  * Process events up to current time.
+ * This implementation only takes the top entry off the heap, it does not
+ * venture to later scheduled events until the next time it is called -
+ * immediately afterwards, if we're in a timer signalled loop.
  */
 
-BOOL schedule_run(void)
+void schedule_run(BOOL poll)
 {
-	struct nsObject *node;
-	struct nsObject *nnode;
 	struct nscallback *nscb;
 	void (*callback)(void *p);
 	void *p;
 	struct timeval tv;
 
-	if(IsMinListEmpty(schedule_list)) return false;
-
-	GetSysTime(&tv);
+	nscb = pblHeapGetFirst(schedule_list);
 
-	node = (struct nsObject *)GetHead((struct List *)schedule_list);
+	if(nscb == -1) return false;
 
-	do
+	if(poll)
 	{
-		nnode=(struct nsObject *)GetSucc((struct Node *)node);
-
-		if((node->Type == AMINS_CALLBACK) && (node->objstruct))
-		{
-			nscb = node->objstruct;
-
-			if(CmpTime(&tv,&nscb->tv) <= 0)
-			{
-				callback = nscb->callback;
-				p = nscb->p;
-				ami_remove_timer_event(nscb);
-				DelObject(node);
-				callback(p);
-			}
-		}
-	} while(node=nnode);
-
-        return true;
+		/* Ensure the scheduled event time has passed (CmpTime<=0)
+		 * For timer signalled events this must *always* be true,
+		 * so we save some time by only checking if we're polling.
+		 */
+
+		GetSysTime(&tv);
+		if(CmpTime(&tv, &nscb->tv) > 0) return;
+ 	}
+
+	callback = nscb->callback;
+	p = nscb->p;
+	ami_remove_timer_event(nscb);
+	pblHeapRemoveFirst(schedule_list);
+	FreeVec(nscb);
+	callback(p);
 }
 
 void ami_remove_timer_event(struct nscallback *nscb)
@@ -160,10 +160,31 @@ void ami_remove_timer_event(struct nscallback *nscb)
 
 	if(nscb->treq)
 	{
-//		if(CheckIO((struct IORequest *)nscb->treq)==NULL)
+		if(CheckIO((struct IORequest *)nscb->treq)==NULL)
    			AbortIO((struct IORequest *)nscb->treq);
 
 		WaitIO((struct IORequest *)nscb->treq);
 		FreeVec(nscb->treq);
 	}
 }
+
+int ami_schedule_compare(const void *prev, const void *next)
+{
+	struct nscallback *nscb1 = *(struct nscallback **)prev;
+	struct nscallback *nscb2 = *(struct nscallback **)next;
+
+	return CmpTime(&nscb1->tv, &nscb2->tv);
+}
+
+BOOL ami_schedule_create(void)
+{
+	schedule_list = pblHeapNew();
+	if(schedule_list == PBL_ERROR_OUT_OF_MEMORY) return false;
+
+	pblHeapSetCompareFunction(schedule_list, ami_schedule_compare);
+}
+
+void ami_schedule_free(void)
+{
+	pblHeapFree(schedule_list);
+}
diff --git a/amiga/schedule.h b/amiga/schedule.h
index bc983a0a2..7a3b25f1b 100755
--- a/amiga/schedule.h
+++ b/amiga/schedule.h
@@ -18,23 +18,14 @@
 
 #ifndef AMIGA_SCHEDULE_H
 #define AMIGA_SCHEDULE_H
-#include <exec/lists.h>
 #include <proto/timer.h>
 
 #include "amiga/os3support.h"
 
-struct MinList *schedule_list;
 struct TimeRequest *tioreq;
 struct MsgPort *msgport;
 
-struct nscallback
-{
-	struct TimeVal tv;
-	void *callback;
-	void *p;
-	struct TimeRequest *treq;
-};
-
-void ami_remove_timer_event(struct nscallback *nscb);
-BOOL schedule_run(void);
+BOOL ami_schedule_create(void);
+void ami_schedule_free(void);
+void schedule_run(BOOL poll);
 #endif