Messages in this thread Patch in this message | | | Subject | rbtree shrinkage | From | David Woodhouse <> | Date | Sun, 11 Apr 2004 22:34:20 +0100 |
| |
We waste space in struct rbtree by using a whole int for colour. This patch uses the LSB of the 'rb_parent' pointer, because we know it's always going to be aligned.
We could possibly optimise the code in rbtree.c a little more by trying to set parent and colour simultaneously, but the compiler shouldn't do that bad a job as it is.
===== include/linux/rbtree.h 1.4 vs edited ===== --- 1.4/include/linux/rbtree.h Mon Oct 7 19:39:24 2002 +++ edited/include/linux/rbtree.h Sun Apr 11 22:07:35 2004 @@ -99,10 +99,9 @@ struct rb_node { - struct rb_node *rb_parent; - int rb_color; -#define RB_RED 0 -#define RB_BLACK 1 + unsigned long rb_parent_colour; +#define RB_RED 0 +#define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; }; @@ -112,7 +111,28 @@ struct rb_node *rb_node; }; +#define rb_parent(node) ((struct rb_node *)((node)->rb_parent_colour & ~1)) +#define rb_colour(node) (((node)->rb_parent_colour & 1)) + +#define rb_is_black(node) (((node)->rb_parent_colour & 1)) +#define rb_is_red(node) (!rb_is_black(node)) +#define rb_set_red(node) do { (node)->rb_parent_colour &= ~1; } while(0) +#define rb_set_black(node) do { (node)->rb_parent_colour |= 1; } while(0) + +#define rb_set_parent_colour(node, p, c) ((node->rb_parent_colour) = ((unsigned long)p) | c) +#define rb_set_parent(node, parent) do { \ + struct rb_node *__n = (node); \ + __n->rb_parent_colour = rb_colour(__n) | (unsigned long)(parent); \ +} while(0) +#define rb_set_colour(node, colour) do { \ + struct rb_node *__n = (node); \ + __n->rb_parent_colour = colour | (unsigned long)rb_parent(__n); \ +} while(0) + #define RB_ROOT (struct rb_root) { NULL, } +#define ON_RB(node) ((node)->rb_parent_colour != 2) +#define RB_CLEAR(node) ((node)->rb_parent_colour = 2) + #define rb_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) @@ -131,8 +151,7 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link) { - node->rb_parent = parent; - node->rb_color = RB_RED; + rb_set_parent_colour(node, parent, RB_RED); node->rb_left = node->rb_right = NULL; *rb_link = node; ===== lib/rbtree.c 1.5 vs edited ===== --- 1.5/lib/rbtree.c Mon Oct 7 19:39:24 2002 +++ edited/lib/rbtree.c Sun Apr 11 21:17:07 2004 @@ -28,19 +28,21 @@ struct rb_node *right = node->rb_right; if ((node->rb_right = right->rb_left)) - right->rb_left->rb_parent = node; + rb_set_parent(right->rb_left, node); right->rb_left = node; - if ((right->rb_parent = node->rb_parent)) + rb_set_parent(right, rb_parent(node)); + + if (rb_parent(node)) { - if (node == node->rb_parent->rb_left) - node->rb_parent->rb_left = right; + if (node == rb_parent(node)->rb_left) + rb_parent(node)->rb_left = right; else - node->rb_parent->rb_right = right; + rb_parent(node)->rb_right = right; } else root->rb_node = right; - node->rb_parent = right; + rb_set_parent(node, right); } static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) @@ -48,38 +50,39 @@ struct rb_node *left = node->rb_left; if ((node->rb_left = left->rb_right)) - left->rb_right->rb_parent = node; + rb_set_parent(left->rb_right, node); left->rb_right = node; - if ((left->rb_parent = node->rb_parent)) + rb_set_parent(left, rb_parent(node)); + if (rb_parent(node)) { - if (node == node->rb_parent->rb_right) - node->rb_parent->rb_right = left; + if (node == rb_parent(node)->rb_right) + rb_parent(node)->rb_right = left; else - node->rb_parent->rb_left = left; + rb_parent(node)->rb_left = left; } else root->rb_node = left; - node->rb_parent = left; + rb_set_parent(node, left); } void rb_insert_color(struct rb_node *node, struct rb_root *root) { struct rb_node *parent, *gparent; - while ((parent = node->rb_parent) && parent->rb_color == RB_RED) + while ((parent = rb_parent(node)) && rb_is_red(parent)) { - gparent = parent->rb_parent; + gparent = rb_parent(parent); if (parent == gparent->rb_left) { { register struct rb_node *uncle = gparent->rb_right; - if (uncle && uncle->rb_color == RB_RED) + if (uncle && rb_is_red(uncle)) { - uncle->rb_color = RB_BLACK; - parent->rb_color = RB_BLACK; - gparent->rb_color = RB_RED; + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); node = gparent; continue; } @@ -94,17 +97,17 @@ node = tmp; } - parent->rb_color = RB_BLACK; - gparent->rb_color = RB_RED; + rb_set_black(parent); + rb_set_red(gparent); __rb_rotate_right(gparent, root); } else { { register struct rb_node *uncle = gparent->rb_left; - if (uncle && uncle->rb_color == RB_RED) + if (uncle && rb_is_red(uncle)) { - uncle->rb_color = RB_BLACK; - parent->rb_color = RB_BLACK; - gparent->rb_color = RB_RED; + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); node = gparent; continue; } @@ -119,13 +122,13 @@ node = tmp; } - parent->rb_color = RB_BLACK; - gparent->rb_color = RB_RED; + rb_set_black(parent); + rb_set_red(gparent); __rb_rotate_left(gparent, root); } } - root->rb_node->rb_color = RB_BLACK; + rb_set_black(root->rb_node); } EXPORT_SYMBOL(rb_insert_color); @@ -134,43 +137,43 @@ { struct rb_node *other; - while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node) + while ((!node || rb_is_black(node)) && node != root->rb_node) { if (parent->rb_left == node) { other = parent->rb_right; - if (other->rb_color == RB_RED) + if (rb_is_red(other)) { - other->rb_color = RB_BLACK; - parent->rb_color = RB_RED; + rb_set_black(other); + rb_set_red(parent); __rb_rotate_left(parent, root); other = parent->rb_right; } if ((!other->rb_left || - other->rb_left->rb_color == RB_BLACK) + rb_is_black(other->rb_left)) && (!other->rb_right || - other->rb_right->rb_color == RB_BLACK)) + rb_is_black(other->rb_right))) { - other->rb_color = RB_RED; + rb_set_red(other); node = parent; - parent = node->rb_parent; + parent = rb_parent(node); } else { if (!other->rb_right || - other->rb_right->rb_color == RB_BLACK) + rb_is_black(other->rb_right)) { register struct rb_node *o_left; if ((o_left = other->rb_left)) - o_left->rb_color = RB_BLACK; - other->rb_color = RB_RED; + rb_set_black(o_left); + rb_set_red(other); __rb_rotate_right(other, root); other = parent->rb_right; } - other->rb_color = parent->rb_color; - parent->rb_color = RB_BLACK; + rb_set_colour(other, rb_colour(parent)); + rb_set_black(parent); if (other->rb_right) - other->rb_right->rb_color = RB_BLACK; + rb_set_black(other->rb_right); __rb_rotate_left(parent, root); node = root->rb_node; break; @@ -179,38 +182,38 @@ else { other = parent->rb_left; - if (other->rb_color == RB_RED) + if (rb_is_red(other)) { - other->rb_color = RB_BLACK; - parent->rb_color = RB_RED; + rb_set_black(other); + rb_set_red(parent); __rb_rotate_right(parent, root); other = parent->rb_left; } if ((!other->rb_left || - other->rb_left->rb_color == RB_BLACK) + rb_is_black(other->rb_left)) && (!other->rb_right || - other->rb_right->rb_color == RB_BLACK)) + rb_is_black(other->rb_right))) { - other->rb_color = RB_RED; + rb_set_red(other); node = parent; - parent = node->rb_parent; + parent = rb_parent(node); } else { if (!other->rb_left || - other->rb_left->rb_color == RB_BLACK) + rb_is_black(other->rb_left)) { register struct rb_node *o_right; if ((o_right = other->rb_right)) - o_right->rb_color = RB_BLACK; - other->rb_color = RB_RED; + rb_set_black(o_right); + rb_set_red(other); __rb_rotate_left(other, root); other = parent->rb_left; } - other->rb_color = parent->rb_color; - parent->rb_color = RB_BLACK; + rb_set_colour(other, rb_colour(parent)); + rb_set_black(parent); if (other->rb_left) - other->rb_left->rb_color = RB_BLACK; + rb_set_black(other->rb_left); __rb_rotate_right(parent, root); node = root->rb_node; break; @@ -218,7 +221,7 @@ } } if (node) - node->rb_color = RB_BLACK; + rb_set_black(node); } void rb_erase(struct rb_node *node, struct rb_root *root) @@ -238,11 +241,11 @@ while ((left = node->rb_left)) node = left; child = node->rb_right; - parent = node->rb_parent; - color = node->rb_color; + parent = rb_parent(node); + color = rb_colour(node); if (child) - child->rb_parent = parent; + rb_set_parent(child, parent); if (parent) { if (parent->rb_left == node) @@ -253,33 +256,33 @@ else root->rb_node = child; - if (node->rb_parent == old) + if (rb_parent(node) == old) parent = node; - node->rb_parent = old->rb_parent; - node->rb_color = old->rb_color; + rb_set_parent(node, rb_parent(old)); + rb_set_colour(node, rb_colour(old)); node->rb_right = old->rb_right; node->rb_left = old->rb_left; - if (old->rb_parent) + if (rb_parent(old)) { - if (old->rb_parent->rb_left == old) - old->rb_parent->rb_left = node; + if (rb_parent(old)->rb_left == old) + rb_parent(old)->rb_left = node; else - old->rb_parent->rb_right = node; + rb_parent(old)->rb_right = node; } else root->rb_node = node; - old->rb_left->rb_parent = node; + rb_set_parent(old->rb_left, node); if (old->rb_right) - old->rb_right->rb_parent = node; + rb_set_parent(old->rb_right, node); goto color; } - parent = node->rb_parent; - color = node->rb_color; + parent = rb_parent(node); + color = rb_colour(node); if (child) - child->rb_parent = parent; + rb_set_parent(child, parent); if (parent) { if (parent->rb_left == node) @@ -329,10 +332,10 @@ ancestor is a right-hand child of its parent, keep going up. First time it's a left-hand child of its parent, said parent is our 'next' node. */ - while (node->rb_parent && node == node->rb_parent->rb_right) - node = node->rb_parent; + while (rb_parent(node) && node == rb_parent(node)->rb_right) + node = rb_parent(node); - return node->rb_parent; + return rb_parent(node); } EXPORT_SYMBOL(rb_next); @@ -349,17 +352,17 @@ /* No left-hand children. Go up till we find an ancestor which is a right-hand child of its parent */ - while (node->rb_parent && node == node->rb_parent->rb_left) - node = node->rb_parent; + while (rb_parent(node) && node == rb_parent(node)->rb_left) + node = rb_parent(node); - return node->rb_parent; + return rb_parent(node); } EXPORT_SYMBOL(rb_prev); void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { - struct rb_node *parent = victim->rb_parent; + struct rb_node *parent = rb_parent(victim); /* Set the surrounding nodes to point to the replacement */ if (parent) { @@ -371,9 +374,9 @@ root->rb_node = new; } if (victim->rb_left) - victim->rb_left->rb_parent = new; + rb_set_parent(victim->rb_left, new); if (victim->rb_right) - victim->rb_right->rb_parent = new; + rb_set_parent(victim->rb_right, new); /* Copy the pointers/colour from the victim to the replacement */ *new = *victim; ===== drivers/block/as-iosched.c 1.35 vs edited ===== --- 1.35/drivers/block/as-iosched.c Mon Jan 19 06:28:32 2004 +++ edited/drivers/block/as-iosched.c Sun Apr 11 22:16:21 2004 @@ -326,10 +326,7 @@ /* * rb tree support functions */ -#define RB_NONE (2) #define RB_EMPTY(root) ((root)->rb_node == NULL) -#define ON_RB(node) ((node)->rb_color != RB_NONE) -#define RB_CLEAR(node) ((node)->rb_color = RB_NONE) #define rb_entry_arq(node) rb_entry((node), struct as_rq, rb_node) #define ARQ_RB_ROOT(ad, arq) (&(ad)->sort_list[(arq)->is_sync]) #define rq_rb_key(rq) (rq)->sector ===== drivers/block/deadline-iosched.c 1.28 vs edited ===== --- 1.28/drivers/block/deadline-iosched.c Wed Oct 22 06:10:19 2003 +++ edited/drivers/block/deadline-iosched.c Sun Apr 11 22:07:39 2004 @@ -177,10 +177,7 @@ /* * rb tree support functions */ -#define RB_NONE (2) #define RB_EMPTY(root) ((root)->rb_node == NULL) -#define ON_RB(node) ((node)->rb_color != RB_NONE) -#define RB_CLEAR(node) ((node)->rb_color = RB_NONE) #define rb_entry_drq(node) rb_entry((node), struct deadline_rq, rb_node) #define DRQ_RB_ROOT(dd, drq) (&(dd)->sort_list[rq_data_dir((drq)->request)]) #define rq_rb_key(rq) (rq)->sector ===== fs/ext3/dir.c 1.17 vs edited ===== --- 1.17/fs/ext3/dir.c Fri Mar 12 09:30:20 2004 +++ edited/fs/ext3/dir.c Sun Apr 11 21:17:07 2004 @@ -287,7 +287,7 @@ * beginning of the loop and try to free the parent * node. */ - parent = n->rb_parent; + parent = rb_parent(n); fname = rb_entry(n, struct fname, rb_hash); while (fname) { struct fname * old = fname; ===== fs/jffs2/nodelist.h 1.10 vs edited ===== --- 1.10/fs/jffs2/nodelist.h Sat Oct 11 15:47:54 2003 +++ edited/fs/jffs2/nodelist.h Sun Apr 11 21:17:07 2004 @@ -300,7 +300,6 @@ node = node->rb_left; return rb_entry(node, struct jffs2_node_frag, rb); } -#define rb_parent(rb) ((rb)->rb_parent) #define frag_next(frag) rb_entry(rb_next(&(frag)->rb), struct jffs2_node_frag, rb) #define frag_prev(frag) rb_entry(rb_prev(&(frag)->rb), struct jffs2_node_frag, rb) #define frag_parent(frag) rb_entry(rb_parent(&(frag)->rb), struct jffs2_node_frag, rb) ===== net/sched/sch_htb.c 1.22 vs edited ===== --- 1.22/net/sched/sch_htb.c Mon Mar 22 06:51:20 2004 +++ edited/net/sched/sch_htb.c Sun Apr 11 21:17:07 2004 @@ -71,7 +71,7 @@ #define HTB_HSIZE 16 /* classid hash size */ #define HTB_EWMAC 2 /* rate average over HTB_EWMAC*HTB_HSIZE sec */ -#define HTB_DEBUG 1 /* compile debugging support (activated by tc tool) */ +//#define HTB_DEBUG 1 /* compile debugging support (activated by tc tool) */ #define HTB_RATECM 1 /* whether to use rate computer */ #define HTB_HYSTERESIS 1/* whether to use mode hysteresis for speedup */ #define HTB_QLOCK(S) spin_lock_bh(&(S)->dev->queue_lock)
-- dwmw2
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |