diff options
Diffstat (limited to 'include/linux/rbtree.h')
-rw-r--r-- | include/linux/rbtree.h | 34 |
1 files changed, 9 insertions, 25 deletions
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 2049087c43b7..bf836a2c6a32 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h | |||
@@ -32,37 +32,19 @@ | |||
32 | #include <linux/kernel.h> | 32 | #include <linux/kernel.h> |
33 | #include <linux/stddef.h> | 33 | #include <linux/stddef.h> |
34 | 34 | ||
35 | struct rb_node | 35 | struct rb_node { |
36 | { | 36 | unsigned long __rb_parent_color; |
37 | unsigned long rb_parent_color; | ||
38 | #define RB_RED 0 | ||
39 | #define RB_BLACK 1 | ||
40 | struct rb_node *rb_right; | 37 | struct rb_node *rb_right; |
41 | struct rb_node *rb_left; | 38 | struct rb_node *rb_left; |
42 | } __attribute__((aligned(sizeof(long)))); | 39 | } __attribute__((aligned(sizeof(long)))); |
43 | /* The alignment might seem pointless, but allegedly CRIS needs it */ | 40 | /* The alignment might seem pointless, but allegedly CRIS needs it */ |
44 | 41 | ||
45 | struct rb_root | 42 | struct rb_root { |
46 | { | ||
47 | struct rb_node *rb_node; | 43 | struct rb_node *rb_node; |
48 | }; | 44 | }; |
49 | 45 | ||
50 | 46 | ||
51 | #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) | 47 | #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) |
52 | #define rb_color(r) ((r)->rb_parent_color & 1) | ||
53 | #define rb_is_red(r) (!rb_color(r)) | ||
54 | #define rb_is_black(r) rb_color(r) | ||
55 | #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) | ||
56 | #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) | ||
57 | |||
58 | static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) | ||
59 | { | ||
60 | rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; | ||
61 | } | ||
62 | static inline void rb_set_color(struct rb_node *rb, int color) | ||
63 | { | ||
64 | rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; | ||
65 | } | ||
66 | 48 | ||
67 | #define RB_ROOT (struct rb_root) { NULL, } | 49 | #define RB_ROOT (struct rb_root) { NULL, } |
68 | #define rb_entry(ptr, type, member) container_of(ptr, type, member) | 50 | #define rb_entry(ptr, type, member) container_of(ptr, type, member) |
@@ -70,8 +52,10 @@ static inline void rb_set_color(struct rb_node *rb, int color) | |||
70 | #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) | 52 | #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) |
71 | 53 | ||
72 | /* 'empty' nodes are nodes that are known not to be inserted in an rbree */ | 54 | /* 'empty' nodes are nodes that are known not to be inserted in an rbree */ |
73 | #define RB_EMPTY_NODE(node) ((node)->rb_parent_color == (unsigned long)(node)) | 55 | #define RB_EMPTY_NODE(node) \ |
74 | #define RB_CLEAR_NODE(node) ((node)->rb_parent_color = (unsigned long)(node)) | 56 | ((node)->__rb_parent_color == (unsigned long)(node)) |
57 | #define RB_CLEAR_NODE(node) \ | ||
58 | ((node)->__rb_parent_color = (unsigned long)(node)) | ||
75 | 59 | ||
76 | 60 | ||
77 | extern void rb_insert_color(struct rb_node *, struct rb_root *); | 61 | extern void rb_insert_color(struct rb_node *, struct rb_root *); |
@@ -98,7 +82,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, | |||
98 | static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, | 82 | static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, |
99 | struct rb_node ** rb_link) | 83 | struct rb_node ** rb_link) |
100 | { | 84 | { |
101 | node->rb_parent_color = (unsigned long )parent; | 85 | node->__rb_parent_color = (unsigned long)parent; |
102 | node->rb_left = node->rb_right = NULL; | 86 | node->rb_left = node->rb_right = NULL; |
103 | 87 | ||
104 | *rb_link = node; | 88 | *rb_link = node; |