diff options
author | David Woodhouse <dwmw2@infradead.org> | 2006-04-21 12:35:51 (GMT) |
---|---|---|
committer | David Woodhouse <dwmw2@infradead.org> | 2006-04-21 12:35:51 (GMT) |
commit | 55a981027fc393c86de2c4e7836c9515088a9a58 (patch) | |
tree | dd950b79d9f57ce48b2b2a91262b88eecb5296da /include/linux | |
parent | 1975e59375756da4ff4e6e7d12f67485e813ace0 (diff) | |
download | linux-fsl-qoriq-55a981027fc393c86de2c4e7836c9515088a9a58.tar.xz |
[RBTREE] Merge colour and parent fields of struct rb_node.
We only used a single bit for colour information, so having a whole
machine word of space allocated for it was a bit wasteful. Instead,
store it in the lowest bit of the 'parent' pointer, since that was
always going to be aligned anyway.
Signed-off-by: David Woodhouse <dwmw2@infradead.org>
Diffstat (limited to 'include/linux')
-rw-r--r-- | include/linux/rbtree.h | 32 |
1 files changed, 19 insertions, 13 deletions
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index ffee81c..748be50 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -99,28 +99,35 @@ 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_colour; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; }; -#define rb_parent(r) ((r)->rb_parent) -#define rb_set_parent(r,p) do { (r)->rb_parent = p; } while (0) -#define rb_colour(r) ((r)->rb_colour) -#define rb_is_red(r) ((r)->colour == RB_RED) -#define rb_is_black(r) ((r)->colour == RB_BLACK) -#define rb_set_red(r) do { (r)->colour = RB_RED; } while (0) -#define rb_set_black(r) do { (r)->colour = RB_BLACK; } while (0) -#define rb_set_colour(r,c) do { (r)->colour = (c); } while (0) - struct rb_root { struct rb_node *rb_node; }; + +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_colour & ~3)) +#define rb_colour(r) ((r)->rb_parent_colour & 1) +#define rb_is_red(r) (!rb_colour(r)) +#define rb_is_black(r) rb_colour(r) +#define rb_set_red(r) do { (r)->rb_parent_colour &= ~1; } while (0) +#define rb_set_black(r) do { (r)->rb_parent_colour |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->rb_parent_colour = (rb->rb_parent_colour & 3) | (unsigned long)p; +} +static inline void rb_set_colour(struct rb_node *rb, int colour) +{ + rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour; +} + #define RB_ROOT (struct rb_root) { NULL, } #define rb_entry(ptr, type, member) container_of(ptr, type, member) @@ -140,8 +147,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_colour = (unsigned long )parent; node->rb_left = node->rb_right = NULL; *rb_link = node; |