From 0bc6b06188c993a9d64a4833e329446d37f553e8 Mon Sep 17 00:00:00 2001 From: Jens Axboe Date: Thu, 30 Oct 2008 15:04:20 +0100 Subject: Update rbtree to version with unified parent + color This saves 4-8 bytes per node, which can be quite a bit of memory with blktrace. Signed-off-by: Jens Axboe --- rbtree.h | 22 ++++++++++++++++++---- 1 file changed, 18 insertions(+), 4 deletions(-) (limited to 'rbtree.h') diff --git a/rbtree.h b/rbtree.h index e722b1e..4c06d98 100644 --- a/rbtree.h +++ b/rbtree.h @@ -98,8 +98,7 @@ static inline struct page * rb_insert_page_cache(struct inode * inode, struct rb_node { - struct rb_node *rb_parent; - int rb_color; + unsigned long rb_parent_color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; @@ -122,6 +121,22 @@ struct rb_root const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) +#define rb_color(r) ((r)->rb_parent_color & 1) +#define rb_is_red(r) (!rb_color(r)) +#define rb_is_black(r) rb_color(r) +#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) +#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; +} +static inline void rb_set_color(struct rb_node *rb, int color) +{ + rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; +} + #define RB_ROOT (struct rb_root) { NULL, } #define rb_entry(ptr, type, member) container_of(ptr, type, member) @@ -141,8 +156,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 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; + node->rb_parent_color = (unsigned long )parent; node->rb_left = node->rb_right = NULL; *rb_link = node; -- cgit v1.2.3