aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Woodhouse <dwmw2@infradead.org>2006-04-21 08:35:51 -0400
committerDavid Woodhouse <dwmw2@infradead.org>2006-04-21 08:35:51 -0400
commit55a981027fc393c86de2c4e7836c9515088a9a58 (patch)
treedd950b79d9f57ce48b2b2a91262b88eecb5296da
parent1975e59375756da4ff4e6e7d12f67485e813ace0 (diff)
[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>
-rw-r--r--include/linux/rbtree.h32
-rw-r--r--lib/rbtree.c178
2 files changed, 109 insertions, 101 deletions
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index ffee81ce7b6f..748be50329d8 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,
99 99
100struct rb_node 100struct rb_node
101{ 101{
102 struct rb_node *rb_parent; 102 unsigned long rb_parent_colour;
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};
109 108
110#define rb_parent(r) ((r)->rb_parent)
111#define rb_set_parent(r,p) do { (r)->rb_parent = p; } while (0)
112#define rb_colour(r) ((r)->rb_colour)
113#define rb_is_red(r) ((r)->colour == RB_RED)
114#define rb_is_black(r) ((r)->colour == RB_BLACK)
115#define rb_set_red(r) do { (r)->colour = RB_RED; } while (0)
116#define rb_set_black(r) do { (r)->colour = RB_BLACK; } while (0)
117#define rb_set_colour(r,c) do { (r)->colour = (c); } while (0)
118
119struct rb_root 109struct rb_root
120{ 110{
121 struct rb_node *rb_node; 111 struct rb_node *rb_node;
122}; 112};
123 113
114
115#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_colour & ~3))
116#define rb_colour(r) ((r)->rb_parent_colour & 1)
117#define rb_is_red(r) (!rb_colour(r))
118#define rb_is_black(r) rb_colour(r)
119#define rb_set_red(r) do { (r)->rb_parent_colour &= ~1; } while (0)
120#define rb_set_black(r) do { (r)->rb_parent_colour |= 1; } while (0)
121
122static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
123{
124 rb->rb_parent_colour = (rb->rb_parent_colour & 3) | (unsigned long)p;
125}
126static inline void rb_set_colour(struct rb_node *rb, int colour)
127{
128 rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour;
129}
130
124#define RB_ROOT (struct rb_root) { NULL, } 131#define RB_ROOT (struct rb_root) { NULL, }
125#define rb_entry(ptr, type, member) container_of(ptr, type, member) 132#define rb_entry(ptr, type, member) container_of(ptr, type, member)
126 133
@@ -140,8 +147,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
140static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, 147static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
141 struct rb_node ** rb_link) 148 struct rb_node ** rb_link)
142{ 149{
143 node->rb_parent = parent; 150 node->rb_parent_colour = (unsigned long )parent;
144 node->rb_color = RB_RED;
145 node->rb_left = node->rb_right = NULL; 151 node->rb_left = node->rb_right = NULL;
146 152
147 *rb_link = node; 153 *rb_link = node;
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 63473e04f18a..4a7173cad149 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_colour(other, rb_colour(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_colour(other, rb_colour(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,43 +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_colour(node);
243 243
244 if (child) 244 if (child)
245 child->rb_parent = parent; 245 rb_set_parent(child, parent);
246 246 if (parent == old) {
247 if (node->rb_parent == old) {
248 parent->rb_right = child; 247 parent->rb_right = child;
249 parent = node; 248 parent = node;
250 } else 249 } else
251 parent->rb_left = child; 250 parent->rb_left = child;
252 251
253 node->rb_parent = old->rb_parent; 252 node->rb_parent_colour = old->rb_parent_colour;
254 node->rb_color = old->rb_color;
255 node->rb_right = old->rb_right; 253 node->rb_right = old->rb_right;
256 node->rb_left = old->rb_left; 254 node->rb_left = old->rb_left;
257 255
258 if (old->rb_parent) 256 if (rb_parent(old))
259 { 257 {
260 if (old->rb_parent->rb_left == old) 258 if (rb_parent(old)->rb_left == old)
261 old->rb_parent->rb_left = node; 259 rb_parent(old)->rb_left = node;
262 else 260 else
263 old->rb_parent->rb_right = node; 261 rb_parent(old)->rb_right = node;
264 } else 262 } else
265 root->rb_node = node; 263 root->rb_node = node;
266 264
267 old->rb_left->rb_parent = node; 265 rb_set_parent(old->rb_left, node);
268 if (old->rb_right) 266 if (old->rb_right)
269 old->rb_right->rb_parent = node; 267 rb_set_parent(old->rb_right, node);
270 goto color; 268 goto color;
271 } 269 }
272 270
273 parent = node->rb_parent; 271 parent = rb_parent(node);
274 color = node->rb_color; 272 color = rb_colour(node);
275 273
276 if (child) 274 if (child)
277 child->rb_parent = parent; 275 rb_set_parent(child, parent);
278 if (parent) 276 if (parent)
279 { 277 {
280 if (parent->rb_left == node) 278 if (parent->rb_left == node)
@@ -322,6 +320,8 @@ EXPORT_SYMBOL(rb_last);
322 320
323struct rb_node *rb_next(struct rb_node *node) 321struct rb_node *rb_next(struct rb_node *node)
324{ 322{
323 struct rb_node *parent;
324
325 /* 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
326 as we can. */ 326 as we can. */
327 if (node->rb_right) { 327 if (node->rb_right) {
@@ -337,15 +337,17 @@ struct rb_node *rb_next(struct rb_node *node)
337 ancestor is a right-hand child of its parent, keep going 337 ancestor is a right-hand child of its parent, keep going
338 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
339 parent is our 'next' node. */ 339 parent is our 'next' node. */
340 while (node->rb_parent && node == node->rb_parent->rb_right) 340 while ((parent = rb_parent(node)) && node == parent->rb_right)
341 node = node->rb_parent; 341 node = parent;
342 342
343 return node->rb_parent; 343 return parent;
344} 344}
345EXPORT_SYMBOL(rb_next); 345EXPORT_SYMBOL(rb_next);
346 346
347struct rb_node *rb_prev(struct rb_node *node) 347struct rb_node *rb_prev(struct rb_node *node)
348{ 348{
349 struct rb_node *parent;
350
349 /* 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
350 as we can. */ 352 as we can. */
351 if (node->rb_left) { 353 if (node->rb_left) {
@@ -357,17 +359,17 @@ struct rb_node *rb_prev(struct rb_node *node)
357 359
358 /* 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
359 is a right-hand child of its parent */ 361 is a right-hand child of its parent */
360 while (node->rb_parent && node == node->rb_parent->rb_left) 362 while ((parent = rb_parent(node)) && node == parent->rb_left)
361 node = node->rb_parent; 363 node = parent;
362 364
363 return node->rb_parent; 365 return parent;
364} 366}
365EXPORT_SYMBOL(rb_prev); 367EXPORT_SYMBOL(rb_prev);
366 368
367void rb_replace_node(struct rb_node *victim, struct rb_node *new, 369void rb_replace_node(struct rb_node *victim, struct rb_node *new,
368 struct rb_root *root) 370 struct rb_root *root)
369{ 371{
370 struct rb_node *parent = victim->rb_parent; 372 struct rb_node *parent = rb_parent(victim);
371 373
372 /* Set the surrounding nodes to point to the replacement */ 374 /* Set the surrounding nodes to point to the replacement */
373 if (parent) { 375 if (parent) {
@@ -379,9 +381,9 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
379 root->rb_node = new; 381 root->rb_node = new;
380 } 382 }
381 if (victim->rb_left) 383 if (victim->rb_left)
382 victim->rb_left->rb_parent = new; 384 rb_set_parent(victim->rb_left, new);
383 if (victim->rb_right) 385 if (victim->rb_right)
384 victim->rb_right->rb_parent = new; 386 rb_set_parent(victim->rb_right, new);
385 387
386 /* Copy the pointers/colour from the victim to the replacement */ 388 /* Copy the pointers/colour from the victim to the replacement */
387 *new = *victim; 389 *new = *victim;