aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--arch/um/kernel/physmem.c2
-rw-r--r--block/as-iosched.c5
-rw-r--r--block/cfq-iosched.c8
-rw-r--r--block/deadline-iosched.c5
-rw-r--r--fs/eventpoll.c6
-rw-r--r--fs/ext3/dir.c2
-rw-r--r--fs/jffs2/nodelist.h1
-rw-r--r--fs/jffs2/readinode.c18
-rw-r--r--include/linux/hrtimer.h2
-rw-r--r--include/linux/rbtree.h26
-rw-r--r--kernel/hrtimer.c4
-rw-r--r--lib/rbtree.c189
-rw-r--r--security/keys/key.c8
13 files changed, 140 insertions, 136 deletions
diff --git a/arch/um/kernel/physmem.c b/arch/um/kernel/physmem.c
index fc0f0b085ca7..166cb09cae4c 100644
--- a/arch/um/kernel/physmem.c
+++ b/arch/um/kernel/physmem.c
@@ -69,7 +69,7 @@ static void insert_phys_mapping(struct phys_desc *desc)
69 panic("Physical remapping for %p already present", 69 panic("Physical remapping for %p already present",
70 desc->virt); 70 desc->virt);
71 71
72 rb_link_node(&desc->rb, (*n)->rb_parent, n); 72 rb_link_node(&desc->rb, rb_parent(*n), n);
73 rb_insert_color(&desc->rb, &phys_mappings); 73 rb_insert_color(&desc->rb, &phys_mappings);
74} 74}
75 75
diff --git a/block/as-iosched.c b/block/as-iosched.c
index a7caf35ca0c2..0c750393be4a 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -353,10 +353,9 @@ static struct request *as_find_arq_hash(struct as_data *ad, sector_t offset)
353/* 353/*
354 * rb tree support functions 354 * rb tree support functions
355 */ 355 */
356#define RB_NONE (2)
357#define RB_EMPTY(root) ((root)->rb_node == NULL) 356#define RB_EMPTY(root) ((root)->rb_node == NULL)
358#define ON_RB(node) ((node)->rb_color != RB_NONE) 357#define ON_RB(node) (rb_parent(node) != node)
359#define RB_CLEAR(node) ((node)->rb_color = RB_NONE) 358#define RB_CLEAR(node) (rb_set_parent(node, node))
360#define rb_entry_arq(node) rb_entry((node), struct as_rq, rb_node) 359#define rb_entry_arq(node) rb_entry((node), struct as_rq, rb_node)
361#define ARQ_RB_ROOT(ad, arq) (&(ad)->sort_list[(arq)->is_sync]) 360#define ARQ_RB_ROOT(ad, arq) (&(ad)->sort_list[(arq)->is_sync])
362#define rq_rb_key(rq) (rq)->sector 361#define rq_rb_key(rq) (rq)->sector
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 052b17487625..6200d9b9af28 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -60,14 +60,9 @@ static DEFINE_SPINLOCK(cfq_exit_lock);
60/* 60/*
61 * rb-tree defines 61 * rb-tree defines
62 */ 62 */
63#define RB_NONE (2)
64#define RB_EMPTY(node) ((node)->rb_node == NULL) 63#define RB_EMPTY(node) ((node)->rb_node == NULL)
65#define RB_CLEAR_COLOR(node) (node)->rb_color = RB_NONE
66#define RB_CLEAR(node) do { \ 64#define RB_CLEAR(node) do { \
67 (node)->rb_parent = NULL; \ 65 memset(node, 0, sizeof(*node)); \
68 RB_CLEAR_COLOR((node)); \
69 (node)->rb_right = NULL; \
70 (node)->rb_left = NULL; \
71} while (0) 66} while (0)
72#define RB_CLEAR_ROOT(root) ((root)->rb_node = NULL) 67#define RB_CLEAR_ROOT(root) ((root)->rb_node = NULL)
73#define rb_entry_crq(node) rb_entry((node), struct cfq_rq, rb_node) 68#define rb_entry_crq(node) rb_entry((node), struct cfq_rq, rb_node)
@@ -567,7 +562,6 @@ static inline void cfq_del_crq_rb(struct cfq_rq *crq)
567 cfq_update_next_crq(crq); 562 cfq_update_next_crq(crq);
568 563
569 rb_erase(&crq->rb_node, &cfqq->sort_list); 564 rb_erase(&crq->rb_node, &cfqq->sort_list);
570 RB_CLEAR_COLOR(&crq->rb_node);
571 565
572 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list)) 566 if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list))
573 cfq_del_cfqq_rr(cfqd, cfqq); 567 cfq_del_cfqq_rr(cfqd, cfqq);
diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index 3bd0415a9828..c94de8e12fbf 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -165,10 +165,9 @@ deadline_find_drq_hash(struct deadline_data *dd, sector_t offset)
165/* 165/*
166 * rb tree support functions 166 * rb tree support functions
167 */ 167 */
168#define RB_NONE (2)
169#define RB_EMPTY(root) ((root)->rb_node == NULL) 168#define RB_EMPTY(root) ((root)->rb_node == NULL)
170#define ON_RB(node) ((node)->rb_color != RB_NONE) 169#define ON_RB(node) (rb_parent(node) != node)
171#define RB_CLEAR(node) ((node)->rb_color = RB_NONE) 170#define RB_CLEAR(node) (rb_set_parent(node, node))
172#define rb_entry_drq(node) rb_entry((node), struct deadline_rq, rb_node) 171#define rb_entry_drq(node) rb_entry((node), struct deadline_rq, rb_node)
173#define DRQ_RB_ROOT(dd, drq) (&(dd)->sort_list[rq_data_dir((drq)->request)]) 172#define DRQ_RB_ROOT(dd, drq) (&(dd)->sort_list[rq_data_dir((drq)->request)])
174#define rq_rb_key(rq) (rq)->sector 173#define rq_rb_key(rq) (rq)->sector
diff --git a/fs/eventpoll.c b/fs/eventpoll.c
index 1b4491cdd115..2695337d4d64 100644
--- a/fs/eventpoll.c
+++ b/fs/eventpoll.c
@@ -337,20 +337,20 @@ static inline int ep_cmp_ffd(struct epoll_filefd *p1,
337/* Special initialization for the rb-tree node to detect linkage */ 337/* Special initialization for the rb-tree node to detect linkage */
338static inline void ep_rb_initnode(struct rb_node *n) 338static inline void ep_rb_initnode(struct rb_node *n)
339{ 339{
340 n->rb_parent = n; 340 rb_set_parent(n, n);
341} 341}
342 342
343/* Removes a node from the rb-tree and marks it for a fast is-linked check */ 343/* Removes a node from the rb-tree and marks it for a fast is-linked check */
344static inline void ep_rb_erase(struct rb_node *n, struct rb_root *r) 344static inline void ep_rb_erase(struct rb_node *n, struct rb_root *r)
345{ 345{
346 rb_erase(n, r); 346 rb_erase(n, r);
347 n->rb_parent = n; 347 rb_set_parent(n, n);
348} 348}
349 349
350/* Fast check to verify that the item is linked to the main rb-tree */ 350/* Fast check to verify that the item is linked to the main rb-tree */
351static inline int ep_rb_linked(struct rb_node *n) 351static inline int ep_rb_linked(struct rb_node *n)
352{ 352{
353 return n->rb_parent != n; 353 return rb_parent(n) != n;
354} 354}
355 355
356/* 356/*
diff --git a/fs/ext3/dir.c b/fs/ext3/dir.c
index f37528ed222e..fbb0d4ed07d4 100644
--- a/fs/ext3/dir.c
+++ b/fs/ext3/dir.c
@@ -284,7 +284,7 @@ static void free_rb_tree_fname(struct rb_root *root)
284 * beginning of the loop and try to free the parent 284 * beginning of the loop and try to free the parent
285 * node. 285 * node.
286 */ 286 */
287 parent = n->rb_parent; 287 parent = rb_parent(n);
288 fname = rb_entry(n, struct fname, rb_hash); 288 fname = rb_entry(n, struct fname, rb_hash);
289 while (fname) { 289 while (fname) {
290 struct fname * old = fname; 290 struct fname * old = fname;
diff --git a/fs/jffs2/nodelist.h b/fs/jffs2/nodelist.h
index 7ad8ee043880..b16c60bbcf6e 100644
--- a/fs/jffs2/nodelist.h
+++ b/fs/jffs2/nodelist.h
@@ -315,7 +315,6 @@ static inline struct jffs2_node_frag *frag_last(struct rb_root *root)
315 return rb_entry(node, struct jffs2_node_frag, rb); 315 return rb_entry(node, struct jffs2_node_frag, rb);
316} 316}
317 317
318#define rb_parent(rb) ((rb)->rb_parent)
319#define frag_next(frag) rb_entry(rb_next(&(frag)->rb), struct jffs2_node_frag, rb) 318#define frag_next(frag) rb_entry(rb_next(&(frag)->rb), struct jffs2_node_frag, rb)
320#define frag_prev(frag) rb_entry(rb_prev(&(frag)->rb), struct jffs2_node_frag, rb) 319#define frag_prev(frag) rb_entry(rb_prev(&(frag)->rb), struct jffs2_node_frag, rb)
321#define frag_parent(frag) rb_entry(rb_parent(&(frag)->rb), struct jffs2_node_frag, rb) 320#define frag_parent(frag) rb_entry(rb_parent(&(frag)->rb), struct jffs2_node_frag, rb)
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index 5ea4faafa2d3..5fec012b02ed 100644
--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -66,7 +66,7 @@ static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
66 jffs2_free_full_dnode(tn->fn); 66 jffs2_free_full_dnode(tn->fn);
67 jffs2_free_tmp_dnode_info(tn); 67 jffs2_free_tmp_dnode_info(tn);
68 68
69 this = this->rb_parent; 69 this = rb_parent(this);
70 if (!this) 70 if (!this)
71 break; 71 break;
72 72
@@ -708,12 +708,12 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
708 jffs2_mark_node_obsolete(c, fn->raw); 708 jffs2_mark_node_obsolete(c, fn->raw);
709 709
710 BUG_ON(rb->rb_left); 710 BUG_ON(rb->rb_left);
711 if (rb->rb_parent && rb->rb_parent->rb_left == rb) { 711 if (rb_parent(rb) && rb_parent(rb)->rb_left == rb) {
712 /* We were then left-hand child of our parent. We need 712 /* We were then left-hand child of our parent. We need
713 * to move our own right-hand child into our place. */ 713 * to move our own right-hand child into our place. */
714 repl_rb = rb->rb_right; 714 repl_rb = rb->rb_right;
715 if (repl_rb) 715 if (repl_rb)
716 repl_rb->rb_parent = rb->rb_parent; 716 rb_set_parent(repl_rb, rb_parent(rb));
717 } else 717 } else
718 repl_rb = NULL; 718 repl_rb = NULL;
719 719
@@ -721,14 +721,14 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
721 721
722 /* Remove the spent tn from the tree; don't bother rebalancing 722 /* Remove the spent tn from the tree; don't bother rebalancing
723 * but put our right-hand child in our own place. */ 723 * but put our right-hand child in our own place. */
724 if (tn->rb.rb_parent) { 724 if (rb_parent(&tn->rb)) {
725 if (tn->rb.rb_parent->rb_left == &tn->rb) 725 if (rb_parent(&tn->rb)->rb_left == &tn->rb)
726 tn->rb.rb_parent->rb_left = repl_rb; 726 rb_parent(&tn->rb)->rb_left = repl_rb;
727 else if (tn->rb.rb_parent->rb_right == &tn->rb) 727 else if (rb_parent(&tn->rb)->rb_right == &tn->rb)
728 tn->rb.rb_parent->rb_right = repl_rb; 728 rb_parent(&tn->rb)->rb_right = repl_rb;
729 else BUG(); 729 else BUG();
730 } else if (tn->rb.rb_right) 730 } else if (tn->rb.rb_right)
731 tn->rb.rb_right->rb_parent = NULL; 731 rb_set_parent(tn->rb.rb_right, NULL);
732 732
733 jffs2_free_tmp_dnode_info(tn); 733 jffs2_free_tmp_dnode_info(tn);
734 if (ret) { 734 if (ret) {
diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h
index 306acf1dc6d5..7d2a1b974c5e 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -127,7 +127,7 @@ extern ktime_t hrtimer_get_next_event(void);
127 127
128static inline int hrtimer_active(const struct hrtimer *timer) 128static inline int hrtimer_active(const struct hrtimer *timer)
129{ 129{
130 return timer->node.rb_parent != HRTIMER_INACTIVE; 130 return rb_parent(&timer->node) != &timer->node;
131} 131}
132 132
133/* Forward a hrtimer so it expires after now: */ 133/* Forward a hrtimer so it expires after now: */
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 4b7cc4fe366d..f37006f21664 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -99,19 +99,36 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
99 99
100struct rb_node 100struct rb_node
101{ 101{
102 struct rb_node *rb_parent; 102 unsigned long rb_parent_color;
103 int rb_color;
104#define RB_RED 0 103#define RB_RED 0
105#define RB_BLACK 1 104#define RB_BLACK 1
106 struct rb_node *rb_right; 105 struct rb_node *rb_right;
107 struct rb_node *rb_left; 106 struct rb_node *rb_left;
108}; 107} __attribute__((aligned(sizeof(long))));
108 /* The alignment might seem pointless, but allegedly CRIS needs it */
109 109
110struct rb_root 110struct rb_root
111{ 111{
112 struct rb_node *rb_node; 112 struct rb_node *rb_node;
113}; 113};
114 114
115
116#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
117#define rb_color(r) ((r)->rb_parent_color & 1)
118#define rb_is_red(r) (!rb_color(r))
119#define rb_is_black(r) rb_color(r)
120#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
121#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
122
123static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
124{
125 rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
126}
127static inline void rb_set_color(struct rb_node *rb, int color)
128{
129 rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
130}
131
115#define RB_ROOT (struct rb_root) { NULL, } 132#define RB_ROOT (struct rb_root) { NULL, }
116#define rb_entry(ptr, type, member) container_of(ptr, type, member) 133#define rb_entry(ptr, type, member) container_of(ptr, type, member)
117 134
@@ -131,8 +148,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
131static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, 148static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
132 struct rb_node ** rb_link) 149 struct rb_node ** rb_link)
133{ 150{
134 node->rb_parent = parent; 151 node->rb_parent_color = (unsigned long )parent;
135 node->rb_color = RB_RED;
136 node->rb_left = node->rb_right = NULL; 152 node->rb_left = node->rb_right = NULL;
137 153
138 *rb_link = node; 154 *rb_link = node;
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index 01fa2ae98a85..18324305724a 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -393,7 +393,7 @@ static void __remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base)
393 if (base->first == &timer->node) 393 if (base->first == &timer->node)
394 base->first = rb_next(&timer->node); 394 base->first = rb_next(&timer->node);
395 rb_erase(&timer->node, &base->active); 395 rb_erase(&timer->node, &base->active);
396 timer->node.rb_parent = HRTIMER_INACTIVE; 396 rb_set_parent(&timer->node, &timer->node);
397} 397}
398 398
399/* 399/*
@@ -582,7 +582,7 @@ void hrtimer_init(struct hrtimer *timer, clockid_t clock_id,
582 clock_id = CLOCK_MONOTONIC; 582 clock_id = CLOCK_MONOTONIC;
583 583
584 timer->base = &bases[clock_id]; 584 timer->base = &bases[clock_id];
585 timer->node.rb_parent = HRTIMER_INACTIVE; 585 rb_set_parent(&timer->node, &timer->node);
586} 586}
587EXPORT_SYMBOL_GPL(hrtimer_init); 587EXPORT_SYMBOL_GPL(hrtimer_init);
588 588
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 14b791ac5089..1e55ba1c2edf 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -26,60 +26,66 @@
26static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) 26static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
27{ 27{
28 struct rb_node *right = node->rb_right; 28 struct rb_node *right = node->rb_right;
29 struct rb_node *parent = rb_parent(node);
29 30
30 if ((node->rb_right = right->rb_left)) 31 if ((node->rb_right = right->rb_left))
31 right->rb_left->rb_parent = node; 32 rb_set_parent(right->rb_left, node);
32 right->rb_left = node; 33 right->rb_left = node;
33 34
34 if ((right->rb_parent = node->rb_parent)) 35 rb_set_parent(right, parent);
36
37 if (parent)
35 { 38 {
36 if (node == node->rb_parent->rb_left) 39 if (node == parent->rb_left)
37 node->rb_parent->rb_left = right; 40 parent->rb_left = right;
38 else 41 else
39 node->rb_parent->rb_right = right; 42 parent->rb_right = right;
40 } 43 }
41 else 44 else
42 root->rb_node = right; 45 root->rb_node = right;
43 node->rb_parent = right; 46 rb_set_parent(node, right);
44} 47}
45 48
46static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 49static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
47{ 50{
48 struct rb_node *left = node->rb_left; 51 struct rb_node *left = node->rb_left;
52 struct rb_node *parent = rb_parent(node);
49 53
50 if ((node->rb_left = left->rb_right)) 54 if ((node->rb_left = left->rb_right))
51 left->rb_right->rb_parent = node; 55 rb_set_parent(left->rb_right, node);
52 left->rb_right = node; 56 left->rb_right = node;
53 57
54 if ((left->rb_parent = node->rb_parent)) 58 rb_set_parent(left, parent);
59
60 if (parent)
55 { 61 {
56 if (node == node->rb_parent->rb_right) 62 if (node == parent->rb_right)
57 node->rb_parent->rb_right = left; 63 parent->rb_right = left;
58 else 64 else
59 node->rb_parent->rb_left = left; 65 parent->rb_left = left;
60 } 66 }
61 else 67 else
62 root->rb_node = left; 68 root->rb_node = left;
63 node->rb_parent = left; 69 rb_set_parent(node, left);
64} 70}
65 71
66void rb_insert_color(struct rb_node *node, struct rb_root *root) 72void rb_insert_color(struct rb_node *node, struct rb_root *root)
67{ 73{
68 struct rb_node *parent, *gparent; 74 struct rb_node *parent, *gparent;
69 75
70 while ((parent = node->rb_parent) && parent->rb_color == RB_RED) 76 while ((parent = rb_parent(node)) && rb_is_red(parent))
71 { 77 {
72 gparent = parent->rb_parent; 78 gparent = rb_parent(parent);
73 79
74 if (parent == gparent->rb_left) 80 if (parent == gparent->rb_left)
75 { 81 {
76 { 82 {
77 register struct rb_node *uncle = gparent->rb_right; 83 register struct rb_node *uncle = gparent->rb_right;
78 if (uncle && uncle->rb_color == RB_RED) 84 if (uncle && rb_is_red(uncle))
79 { 85 {
80 uncle->rb_color = RB_BLACK; 86 rb_set_black(uncle);
81 parent->rb_color = RB_BLACK; 87 rb_set_black(parent);
82 gparent->rb_color = RB_RED; 88 rb_set_red(gparent);
83 node = gparent; 89 node = gparent;
84 continue; 90 continue;
85 } 91 }
@@ -94,17 +100,17 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
94 node = tmp; 100 node = tmp;
95 } 101 }
96 102
97 parent->rb_color = RB_BLACK; 103 rb_set_black(parent);
98 gparent->rb_color = RB_RED; 104 rb_set_red(gparent);
99 __rb_rotate_right(gparent, root); 105 __rb_rotate_right(gparent, root);
100 } else { 106 } else {
101 { 107 {
102 register struct rb_node *uncle = gparent->rb_left; 108 register struct rb_node *uncle = gparent->rb_left;
103 if (uncle && uncle->rb_color == RB_RED) 109 if (uncle && rb_is_red(uncle))
104 { 110 {
105 uncle->rb_color = RB_BLACK; 111 rb_set_black(uncle);
106 parent->rb_color = RB_BLACK; 112 rb_set_black(parent);
107 gparent->rb_color = RB_RED; 113 rb_set_red(gparent);
108 node = gparent; 114 node = gparent;
109 continue; 115 continue;
110 } 116 }
@@ -119,13 +125,13 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
119 node = tmp; 125 node = tmp;
120 } 126 }
121 127
122 parent->rb_color = RB_BLACK; 128 rb_set_black(parent);
123 gparent->rb_color = RB_RED; 129 rb_set_red(gparent);
124 __rb_rotate_left(gparent, root); 130 __rb_rotate_left(gparent, root);
125 } 131 }
126 } 132 }
127 133
128 root->rb_node->rb_color = RB_BLACK; 134 rb_set_black(root->rb_node);
129} 135}
130EXPORT_SYMBOL(rb_insert_color); 136EXPORT_SYMBOL(rb_insert_color);
131 137
@@ -134,43 +140,40 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
134{ 140{
135 struct rb_node *other; 141 struct rb_node *other;
136 142
137 while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node) 143 while ((!node || rb_is_black(node)) && node != root->rb_node)
138 { 144 {
139 if (parent->rb_left == node) 145 if (parent->rb_left == node)
140 { 146 {
141 other = parent->rb_right; 147 other = parent->rb_right;
142 if (other->rb_color == RB_RED) 148 if (rb_is_red(other))
143 { 149 {
144 other->rb_color = RB_BLACK; 150 rb_set_black(other);
145 parent->rb_color = RB_RED; 151 rb_set_red(parent);
146 __rb_rotate_left(parent, root); 152 __rb_rotate_left(parent, root);
147 other = parent->rb_right; 153 other = parent->rb_right;
148 } 154 }
149 if ((!other->rb_left || 155 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
150 other->rb_left->rb_color == RB_BLACK) 156 (!other->rb_right || rb_is_black(other->rb_right)))
151 && (!other->rb_right ||
152 other->rb_right->rb_color == RB_BLACK))
153 { 157 {
154 other->rb_color = RB_RED; 158 rb_set_red(other);
155 node = parent; 159 node = parent;
156 parent = node->rb_parent; 160 parent = rb_parent(node);
157 } 161 }
158 else 162 else
159 { 163 {
160 if (!other->rb_right || 164 if (!other->rb_right || rb_is_black(other->rb_right))
161 other->rb_right->rb_color == RB_BLACK)
162 { 165 {
163 register struct rb_node *o_left; 166 struct rb_node *o_left;
164 if ((o_left = other->rb_left)) 167 if ((o_left = other->rb_left))
165 o_left->rb_color = RB_BLACK; 168 rb_set_black(o_left);
166 other->rb_color = RB_RED; 169 rb_set_red(other);
167 __rb_rotate_right(other, root); 170 __rb_rotate_right(other, root);
168 other = parent->rb_right; 171 other = parent->rb_right;
169 } 172 }
170 other->rb_color = parent->rb_color; 173 rb_set_color(other, rb_color(parent));
171 parent->rb_color = RB_BLACK; 174 rb_set_black(parent);
172 if (other->rb_right) 175 if (other->rb_right)
173 other->rb_right->rb_color = RB_BLACK; 176 rb_set_black(other->rb_right);
174 __rb_rotate_left(parent, root); 177 __rb_rotate_left(parent, root);
175 node = root->rb_node; 178 node = root->rb_node;
176 break; 179 break;
@@ -179,38 +182,35 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
179 else 182 else
180 { 183 {
181 other = parent->rb_left; 184 other = parent->rb_left;
182 if (other->rb_color == RB_RED) 185 if (rb_is_red(other))
183 { 186 {
184 other->rb_color = RB_BLACK; 187 rb_set_black(other);
185 parent->rb_color = RB_RED; 188 rb_set_red(parent);
186 __rb_rotate_right(parent, root); 189 __rb_rotate_right(parent, root);
187 other = parent->rb_left; 190 other = parent->rb_left;
188 } 191 }
189 if ((!other->rb_left || 192 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
190 other->rb_left->rb_color == RB_BLACK) 193 (!other->rb_right || rb_is_black(other->rb_right)))
191 && (!other->rb_right ||
192 other->rb_right->rb_color == RB_BLACK))
193 { 194 {
194 other->rb_color = RB_RED; 195 rb_set_red(other);
195 node = parent; 196 node = parent;
196 parent = node->rb_parent; 197 parent = rb_parent(node);
197 } 198 }
198 else 199 else
199 { 200 {
200 if (!other->rb_left || 201 if (!other->rb_left || rb_is_black(other->rb_left))
201 other->rb_left->rb_color == RB_BLACK)
202 { 202 {
203 register struct rb_node *o_right; 203 register struct rb_node *o_right;
204 if ((o_right = other->rb_right)) 204 if ((o_right = other->rb_right))
205 o_right->rb_color = RB_BLACK; 205 rb_set_black(o_right);
206 other->rb_color = RB_RED; 206 rb_set_red(other);
207 __rb_rotate_left(other, root); 207 __rb_rotate_left(other, root);
208 other = parent->rb_left; 208 other = parent->rb_left;
209 } 209 }
210 other->rb_color = parent->rb_color; 210 rb_set_color(other, rb_color(parent));
211 parent->rb_color = RB_BLACK; 211 rb_set_black(parent);
212 if (other->rb_left) 212 if (other->rb_left)
213 other->rb_left->rb_color = RB_BLACK; 213 rb_set_black(other->rb_left);
214 __rb_rotate_right(parent, root); 214 __rb_rotate_right(parent, root);
215 node = root->rb_node; 215 node = root->rb_node;
216 break; 216 break;
@@ -218,7 +218,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
218 } 218 }
219 } 219 }
220 if (node) 220 if (node)
221 node->rb_color = RB_BLACK; 221 rb_set_black(node);
222} 222}
223 223
224void rb_erase(struct rb_node *node, struct rb_root *root) 224void rb_erase(struct rb_node *node, struct rb_root *root)
@@ -238,48 +238,41 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
238 while ((left = node->rb_left) != NULL) 238 while ((left = node->rb_left) != NULL)
239 node = left; 239 node = left;
240 child = node->rb_right; 240 child = node->rb_right;
241 parent = node->rb_parent; 241 parent = rb_parent(node);
242 color = node->rb_color; 242 color = rb_color(node);
243 243
244 if (child) 244 if (child)
245 child->rb_parent = parent; 245 rb_set_parent(child, parent);
246 if (parent) 246 if (parent == old) {
247 { 247 parent->rb_right = child;
248 if (parent->rb_left == node)
249 parent->rb_left = child;
250 else
251 parent->rb_right = child;
252 }
253 else
254 root->rb_node = child;
255
256 if (node->rb_parent == old)
257 parent = node; 248 parent = node;
258 node->rb_parent = old->rb_parent; 249 } else
259 node->rb_color = old->rb_color; 250 parent->rb_left = child;
251
252 node->rb_parent_color = old->rb_parent_color;
260 node->rb_right = old->rb_right; 253 node->rb_right = old->rb_right;
261 node->rb_left = old->rb_left; 254 node->rb_left = old->rb_left;
262 255
263 if (old->rb_parent) 256 if (rb_parent(old))
264 { 257 {
265 if (old->rb_parent->rb_left == old) 258 if (rb_parent(old)->rb_left == old)
266 old->rb_parent->rb_left = node; 259 rb_parent(old)->rb_left = node;
267 else 260 else
268 old->rb_parent->rb_right = node; 261 rb_parent(old)->rb_right = node;
269 } else 262 } else
270 root->rb_node = node; 263 root->rb_node = node;
271 264
272 old->rb_left->rb_parent = node; 265 rb_set_parent(old->rb_left, node);
273 if (old->rb_right) 266 if (old->rb_right)
274 old->rb_right->rb_parent = node; 267 rb_set_parent(old->rb_right, node);
275 goto color; 268 goto color;
276 } 269 }
277 270
278 parent = node->rb_parent; 271 parent = rb_parent(node);
279 color = node->rb_color; 272 color = rb_color(node);
280 273
281 if (child) 274 if (child)
282 child->rb_parent = parent; 275 rb_set_parent(child, parent);
283 if (parent) 276 if (parent)
284 { 277 {
285 if (parent->rb_left == node) 278 if (parent->rb_left == node)
@@ -327,6 +320,8 @@ EXPORT_SYMBOL(rb_last);
327 320
328struct rb_node *rb_next(struct rb_node *node) 321struct rb_node *rb_next(struct rb_node *node)
329{ 322{
323 struct rb_node *parent;
324
330 /* If we have a right-hand child, go down and then left as far 325 /* If we have a right-hand child, go down and then left as far
331 as we can. */ 326 as we can. */
332 if (node->rb_right) { 327 if (node->rb_right) {
@@ -342,15 +337,17 @@ struct rb_node *rb_next(struct rb_node *node)
342 ancestor is a right-hand child of its parent, keep going 337 ancestor is a right-hand child of its parent, keep going
343 up. First time it's a left-hand child of its parent, said 338 up. First time it's a left-hand child of its parent, said
344 parent is our 'next' node. */ 339 parent is our 'next' node. */
345 while (node->rb_parent && node == node->rb_parent->rb_right) 340 while ((parent = rb_parent(node)) && node == parent->rb_right)
346 node = node->rb_parent; 341 node = parent;
347 342
348 return node->rb_parent; 343 return parent;
349} 344}
350EXPORT_SYMBOL(rb_next); 345EXPORT_SYMBOL(rb_next);
351 346
352struct rb_node *rb_prev(struct rb_node *node) 347struct rb_node *rb_prev(struct rb_node *node)
353{ 348{
349 struct rb_node *parent;
350
354 /* If we have a left-hand child, go down and then right as far 351 /* If we have a left-hand child, go down and then right as far
355 as we can. */ 352 as we can. */
356 if (node->rb_left) { 353 if (node->rb_left) {
@@ -362,17 +359,17 @@ struct rb_node *rb_prev(struct rb_node *node)
362 359
363 /* No left-hand children. Go up till we find an ancestor which 360 /* No left-hand children. Go up till we find an ancestor which
364 is a right-hand child of its parent */ 361 is a right-hand child of its parent */
365 while (node->rb_parent && node == node->rb_parent->rb_left) 362 while ((parent = rb_parent(node)) && node == parent->rb_left)
366 node = node->rb_parent; 363 node = parent;
367 364
368 return node->rb_parent; 365 return parent;
369} 366}
370EXPORT_SYMBOL(rb_prev); 367EXPORT_SYMBOL(rb_prev);
371 368
372void rb_replace_node(struct rb_node *victim, struct rb_node *new, 369void rb_replace_node(struct rb_node *victim, struct rb_node *new,
373 struct rb_root *root) 370 struct rb_root *root)
374{ 371{
375 struct rb_node *parent = victim->rb_parent; 372 struct rb_node *parent = rb_parent(victim);
376 373
377 /* Set the surrounding nodes to point to the replacement */ 374 /* Set the surrounding nodes to point to the replacement */
378 if (parent) { 375 if (parent) {
@@ -384,9 +381,9 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
384 root->rb_node = new; 381 root->rb_node = new;
385 } 382 }
386 if (victim->rb_left) 383 if (victim->rb_left)
387 victim->rb_left->rb_parent = new; 384 rb_set_parent(victim->rb_left, new);
388 if (victim->rb_right) 385 if (victim->rb_right)
389 victim->rb_right->rb_parent = new; 386 rb_set_parent(victim->rb_right, new);
390 387
391 /* Copy the pointers/colour from the victim to the replacement */ 388 /* Copy the pointers/colour from the victim to the replacement */
392 *new = *victim; 389 *new = *victim;
diff --git a/security/keys/key.c b/security/keys/key.c
index b6061fa29da7..3fdc49c6a02c 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -211,12 +211,12 @@ static inline void key_alloc_serial(struct key *key)
211 key->serial = 2; 211 key->serial = 2;
212 key_serial_next = key->serial + 1; 212 key_serial_next = key->serial + 1;
213 213
214 if (!parent->rb_parent) 214 if (!rb_parent(parent))
215 p = &key_serial_tree.rb_node; 215 p = &key_serial_tree.rb_node;
216 else if (parent->rb_parent->rb_left == parent) 216 else if (rb_parent(parent)->rb_left == parent)
217 p = &parent->rb_parent->rb_left; 217 p = &(rb_parent(parent)->rb_left);
218 else 218 else
219 p = &parent->rb_parent->rb_right; 219 p = &(rb_parent(parent)->rb_right);
220 220
221 parent = rb_next(parent); 221 parent = rb_next(parent);
222 if (!parent) 222 if (!parent)