[MAJOR] replace the wait-queue linked list with an rbtree.
This patch from Sin Yu makes use of an rbtree for the wait queue,
which will solve the slowdown problem encountered when timeouts
are heterogenous in the configuration. The next step will be to
turn maintain_proxies() into a per-proxy task so that we won't
have to scan them all after each poll() loop.
diff --git a/include/proto/task.h b/include/proto/task.h
index 70abb82..8bd973a 100644
--- a/include/proto/task.h
+++ b/include/proto/task.h
@@ -61,8 +61,8 @@
*/
static inline struct task *task_delete(struct task *t)
{
- t->prev->next = t->next;
- t->next->prev = t->prev;
+ rb_erase(&t->rb_node, t->wq);
+ t->wq = NULL;
return t;
}
diff --git a/include/types/task.h b/include/types/task.h
index 6b1df22..d09efae 100644
--- a/include/types/task.h
+++ b/include/types/task.h
@@ -25,6 +25,7 @@
#include <sys/time.h>
#include <common/config.h>
+#include <common/rbtree.h>
/* values for task->state */
#define TASK_IDLE 0
@@ -32,9 +33,9 @@
/* The base for all tasks */
struct task {
- struct task *next, *prev; /* chaining ... */
+ struct rb_node rb_node;
+ struct rb_root *wq;
struct task *rqnext; /* chaining in run queue ... */
- struct task *wq; /* the wait queue this task is in */
int state; /* task state : IDLE or RUNNING */
struct timeval expire; /* next expiration time for this task, use only for fast sorting */
int (*process)(struct task *t); /* the function which processes the task */
@@ -44,7 +45,7 @@
#define sizeof_task sizeof(struct task)
extern void **pool_task;
-extern struct task wait_queue[2];
+extern struct rb_root wait_queue[2];
extern struct task *rq;