[PATCH 2.6 2/4]: replace eligible list by rbtree

[Patrick McHardy <kaber@trash.net>]

[-- Attachment #1: Type: text/plain, Size: 52 bytes --]

This patch replaces the eligible list by a rbtree.


[-- Attachment #2: 02-hfsc-2.6.diff --]
[-- Type: text/x-patch, Size: 6589 bytes --]

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2004/08/11 23:14:57+02:00 kaber@coreworks.de 
#   [NET_SCHED]: Replace eligible list by rbtree in HFSC scheduler
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
# net/sched/sch_hfsc.c
#   2004/08/11 23:14:39+02:00 kaber@coreworks.de +42 -69
#   [NET_SCHED]: Replace eligible list by rbtree in HFSC scheduler
# 
diff -Nru a/net/sched/sch_hfsc.c b/net/sched/sch_hfsc.c
--- a/net/sched/sch_hfsc.c	2004-08-12 23:25:23 +02:00
+++ b/net/sched/sch_hfsc.c	2004-08-12 23:25:23 +02:00
@@ -62,6 +62,7 @@
 #include <linux/slab.h>
 #include <linux/timer.h>
 #include <linux/list.h>
+#include <linux/rbtree.h>
 #include <linux/init.h>
 #include <linux/netdevice.h>
 #include <linux/rtnetlink.h>
@@ -133,9 +134,9 @@
 	struct list_head children;	/* child classes */
 	struct Qdisc	*qdisc;		/* leaf qdisc */
 
+	struct rb_node el_node;		/* qdisc's eligible tree member */
 	struct list_head actlist;	/* active children list */
 	struct list_head alist;		/* active children list member */
-	struct list_head ellist;	/* eligible list member */
 	struct list_head hlist;		/* hash list member */
 	struct list_head dlist;		/* drop list member */
 
@@ -183,7 +184,7 @@
 	u16	defcls;				/* default class id */
 	struct hfsc_class root;			/* root class */
 	struct list_head clhash[HFSC_HSIZE];	/* class hash */
-	struct list_head eligible;		/* eligible list */
+	struct rb_root eligible;		/* eligible tree */
 	struct list_head droplist;		/* active leaf class list (for
 						   dropping) */
 	struct sk_buff_head requeue;		/* requeued packet */
@@ -219,82 +220,51 @@
 
 
 /*
- * eligible list holds backlogged classes being sorted by their eligible times.
- * there is one eligible list per hfsc instance.
+ * eligible tree holds backlogged classes being sorted by their eligible times.
+ * there is one eligible tree per hfsc instance.
  */
 
 static void
-ellist_insert(struct hfsc_class *cl)
+eltree_insert(struct hfsc_class *cl)
 {
-	struct list_head *head = &cl->sched->eligible;
-	struct hfsc_class *p;
-
-	/* check the last entry first */
-	if (list_empty(head) ||
-	    ((p = list_entry(head->prev, struct hfsc_class, ellist)) &&
-	     p->cl_e <= cl->cl_e)) {
-		list_add_tail(&cl->ellist, head);
-		return;
-	}
-
-	list_for_each_entry(p, head, ellist) {
-		if (cl->cl_e < p->cl_e) {
-			/* insert cl before p */
-			list_add_tail(&cl->ellist, &p->ellist);
-			return;
-		}
+	struct rb_node **p = &cl->sched->eligible.rb_node;
+	struct rb_node *parent = NULL;
+	struct hfsc_class *cl1;
+
+	while (*p != NULL) {
+		parent = *p;
+		cl1 = rb_entry(parent, struct hfsc_class, el_node);
+		if (cl->cl_e >= cl1->cl_e)
+			p = &parent->rb_right;
+		else
+			p = &parent->rb_left;
 	}
-	ASSERT(0); /* should not reach here */
+	rb_link_node(&cl->el_node, parent, p);
+	rb_insert_color(&cl->el_node, &cl->sched->eligible);
 }
 
 static inline void
-ellist_remove(struct hfsc_class *cl)
+eltree_remove(struct hfsc_class *cl)
 {
-	list_del(&cl->ellist);
+	rb_erase(&cl->el_node, &cl->sched->eligible);
 }
 
-static void
-ellist_update(struct hfsc_class *cl)
+static inline void
+eltree_update(struct hfsc_class *cl)
 {
-	struct list_head *head = &cl->sched->eligible;
-	struct hfsc_class *p, *last;
-
-	/*
-	 * the eligible time of a class increases monotonically.
-	 * if the next entry has a larger eligible time, nothing to do.
-	 */
-	if (cl->ellist.next == head ||
-	    ((p = list_entry(cl->ellist.next, struct hfsc_class, ellist)) &&
-	     cl->cl_e <= p->cl_e))
-		return;
-
-	/* check the last entry */
-	last = list_entry(head->prev, struct hfsc_class, ellist);
-	if (last->cl_e <= cl->cl_e) {
-		list_move_tail(&cl->ellist, head);
-		return;
-	}
-
-	/*
-	 * the new position must be between the next entry
-	 * and the last entry
-	 */
-	list_for_each_entry_continue(p, head, ellist) {
-		if (cl->cl_e < p->cl_e) {
-			list_move_tail(&cl->ellist, &p->ellist);
-			return;
-		}
-	}
-	ASSERT(0); /* should not reach here */
+	eltree_remove(cl);
+	eltree_insert(cl);
 }
 
 /* find the class with the minimum deadline among the eligible classes */
 static inline struct hfsc_class *
-ellist_get_mindl(struct list_head *head, u64 cur_time)
+eltree_get_mindl(struct hfsc_sched *q, u64 cur_time)
 {
 	struct hfsc_class *p, *cl = NULL;
+	struct rb_node *n;
 
-	list_for_each_entry(p, head, ellist) {
+	for (n = rb_first(&q->eligible); n != NULL; n = rb_next(n)) {
+		p = rb_entry(n, struct hfsc_class, el_node);
 		if (p->cl_e > cur_time)
 			break;
 		if (cl == NULL || p->cl_d < cl->cl_d)
@@ -305,11 +275,14 @@
 
 /* find the class with minimum eligible time among the eligible classes */
 static inline struct hfsc_class *
-ellist_get_minel(struct list_head *head)
+eltree_get_minel(struct hfsc_sched *q)
 {
-	if (list_empty(head))
+	struct rb_node *n;
+	
+	n = rb_first(&q->eligible);
+	if (n == NULL)
 		return NULL;
-	return list_entry(head->next, struct hfsc_class, ellist);
+	return rb_entry(n, struct hfsc_class, el_node);
 }
 
 /*
@@ -711,7 +684,7 @@
 	cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
 	cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
 
-	ellist_insert(cl);
+	eltree_insert(cl);
 }
 
 static void
@@ -720,7 +693,7 @@
 	cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
 	cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
 
-	ellist_update(cl);
+	eltree_update(cl);
 }
 
 static inline void
@@ -941,7 +914,7 @@
 set_passive(struct hfsc_class *cl)
 {
 	if (cl->cl_flags & HFSC_RSC)
-		ellist_remove(cl);
+		eltree_remove(cl);
 
 	list_del(&cl->dlist);
 
@@ -1528,7 +1501,7 @@
 	u64 next_time = 0;
 	long delay;
 
-	if ((cl = ellist_get_minel(&q->eligible)) != NULL)
+	if ((cl = eltree_get_minel(q)) != NULL)
 		next_time = cl->cl_e;
 	if (q->root.cl_cfmin != 0) {
 		if (next_time == 0 || next_time > q->root.cl_cfmin)
@@ -1559,7 +1532,7 @@
 	q->defcls = qopt->defcls;
 	for (i = 0; i < HFSC_HSIZE; i++)
 		INIT_LIST_HEAD(&q->clhash[i]);
-	INIT_LIST_HEAD(&q->eligible);
+	q->eligible = RB_ROOT;
 	INIT_LIST_HEAD(&q->droplist);
 	skb_queue_head_init(&q->requeue);
 
@@ -1641,7 +1614,7 @@
 			hfsc_reset_class(cl);
 	}
 	__skb_queue_purge(&q->requeue);
-	INIT_LIST_HEAD(&q->eligible);
+	q->eligible = RB_ROOT;
 	INIT_LIST_HEAD(&q->droplist);
 	del_timer(&q->wd_timer);
 	sch->flags &= ~TCQ_F_THROTTLED;
@@ -1749,7 +1722,7 @@
 	 * find the class with the minimum deadline among
 	 * the eligible classes.
 	 */
-	if ((cl = ellist_get_mindl(&q->eligible, cur_time)) != NULL) {
+	if ((cl = eltree_get_mindl(q, cur_time)) != NULL) {
 		realtime = 1;
 	} else {
 		/*