![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to rbtree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / kern|
Return to rbtree.c CVS log | Up to [GnuMach] / Gnu-Mach / kern |
1.1 root 1: /*
2: * Copyright (c) 2010, 2012 Richard Braun.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms, with or without
6: * modification, are permitted provided that the following conditions
7: * are met:
8: * 1. Redistributions of source code must retain the above copyright
9: * notice, this list of conditions and the following disclaimer.
10: * 2. Redistributions in binary form must reproduce the above copyright
11: * notice, this list of conditions and the following disclaimer in the
12: * documentation and/or other materials provided with the distribution.
13: *
14: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24: */
25:
26: #include <kern/assert.h>
27: #include <kern/rbtree.h>
28: #include <kern/rbtree_i.h>
29: #include <sys/types.h>
30:
31: #define unlikely(expr) __builtin_expect(!!(expr), 0)
32:
33: /*
34: * Return the index of a node in the children array of its parent.
35: *
36: * The parent parameter must not be null, and must be the parent of the
37: * given node.
38: */
39: static inline int rbtree_index(const struct rbtree_node *node,
40: const struct rbtree_node *parent)
41: {
42: assert(parent != NULL);
43: assert((node == NULL) || (rbtree_parent(node) == parent));
44:
45: if (parent->children[RBTREE_LEFT] == node)
46: return RBTREE_LEFT;
47:
48: assert(parent->children[RBTREE_RIGHT] == node);
49:
50: return RBTREE_RIGHT;
51: }
52:
53: /*
54: * Return the color of a node.
55: */
56: static inline int rbtree_color(const struct rbtree_node *node)
57: {
58: return node->parent & RBTREE_COLOR_MASK;
59: }
60:
61: /*
62: * Return true if the node is red.
63: */
64: static inline int rbtree_is_red(const struct rbtree_node *node)
65: {
66: return rbtree_color(node) == RBTREE_COLOR_RED;
67: }
68:
69: /*
70: * Return true if the node is black.
71: */
72: static inline int rbtree_is_black(const struct rbtree_node *node)
73: {
74: return rbtree_color(node) == RBTREE_COLOR_BLACK;
75: }
76:
77: /*
78: * Set the parent of a node, retaining its current color.
79: */
80: static inline void rbtree_set_parent(struct rbtree_node *node,
81: struct rbtree_node *parent)
82: {
83: assert(rbtree_check_alignment(node));
84: assert(rbtree_check_alignment(parent));
85:
86: node->parent = (unsigned long)parent | (node->parent & RBTREE_COLOR_MASK);
87: }
88:
89: /*
90: * Set the color of a node, retaining its current parent.
91: */
92: static inline void rbtree_set_color(struct rbtree_node *node, int color)
93: {
94: assert((color & ~RBTREE_COLOR_MASK) == 0);
95: node->parent = (node->parent & RBTREE_PARENT_MASK) | color;
96: }
97:
98: /*
99: * Set the color of a node to red, retaining its current parent.
100: */
101: static inline void rbtree_set_red(struct rbtree_node *node)
102: {
103: rbtree_set_color(node, RBTREE_COLOR_RED);
104: }
105:
106: /*
107: * Set the color of a node to black, retaining its current parent.
108: */
109: static inline void rbtree_set_black(struct rbtree_node *node)
110: {
111: rbtree_set_color(node, RBTREE_COLOR_BLACK);
112: }
113:
114: /*
115: * Perform a tree rotation, rooted at the given node.
116: *
117: * The direction parameter defines the rotation direction and is either
118: * RBTREE_LEFT or RBTREE_RIGHT.
119: */
120: static void rbtree_rotate(struct rbtree *tree, struct rbtree_node *node,
121: int direction)
122: {
123: struct rbtree_node *parent, *rnode;
124: int left, right;
125:
126: left = direction;
127: right = 1 - left;
128: parent = rbtree_parent(node);
129: rnode = node->children[right];
130:
131: node->children[right] = rnode->children[left];
132:
133: if (rnode->children[left] != NULL)
134: rbtree_set_parent(rnode->children[left], node);
135:
136: rnode->children[left] = node;
137: rbtree_set_parent(rnode, parent);
138:
139: if (unlikely(parent == NULL))
140: tree->root = rnode;
141: else
142: parent->children[rbtree_index(node, parent)] = rnode;
143:
144: rbtree_set_parent(node, rnode);
145: }
146:
147: void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
148: int index, struct rbtree_node *node)
149: {
150: struct rbtree_node *grand_parent, *uncle, *tmp;
151: int left, right;
152:
153: assert(rbtree_check_alignment(parent));
154: assert(rbtree_check_alignment(node));
155:
156: node->parent = (unsigned long)parent | RBTREE_COLOR_RED;
157: node->children[RBTREE_LEFT] = NULL;
158: node->children[RBTREE_RIGHT] = NULL;
159:
160: if (unlikely(parent == NULL))
161: tree->root = node;
162: else
163: parent->children[index] = node;
164:
165: for (;;) {
166: if (parent == NULL) {
167: rbtree_set_black(node);
168: break;
169: }
170:
171: if (rbtree_is_black(parent))
172: break;
173:
174: grand_parent = rbtree_parent(parent);
175: assert(grand_parent != NULL);
176:
177: left = rbtree_index(parent, grand_parent);
178: right = 1 - left;
179:
180: uncle = grand_parent->children[right];
181:
182: /*
183: * Uncle is red. Flip colors and repeat at grand parent.
184: */
185: if ((uncle != NULL) && rbtree_is_red(uncle)) {
186: rbtree_set_black(uncle);
187: rbtree_set_black(parent);
188: rbtree_set_red(grand_parent);
189: node = grand_parent;
190: parent = rbtree_parent(node);
191: continue;
192: }
193:
194: /*
195: * Node is the right child of its parent. Rotate left at parent.
196: */
197: if (parent->children[right] == node) {
198: rbtree_rotate(tree, parent, left);
199: tmp = node;
200: node = parent;
201: parent = tmp;
202: }
203:
204: /*
205: * Node is the left child of its parent. Handle colors, rotate right
206: * at grand parent, and leave.
207: */
208: rbtree_set_black(parent);
209: rbtree_set_red(grand_parent);
210: rbtree_rotate(tree, grand_parent, right);
211: break;
212: }
213:
214: assert(rbtree_is_black(tree->root));
215: }
216:
217: void rbtree_remove(struct rbtree *tree, struct rbtree_node *node)
218: {
219: struct rbtree_node *child, *parent, *brother;
220: int color, left, right;
221:
222: if (node->children[RBTREE_LEFT] == NULL)
223: child = node->children[RBTREE_RIGHT];
224: else if (node->children[RBTREE_RIGHT] == NULL)
225: child = node->children[RBTREE_LEFT];
226: else {
227: struct rbtree_node *successor;
228:
229: /*
230: * Two-children case: replace the node with its successor.
231: */
232:
233: successor = node->children[RBTREE_RIGHT];
234:
235: while (successor->children[RBTREE_LEFT] != NULL)
236: successor = successor->children[RBTREE_LEFT];
237:
238: color = rbtree_color(successor);
239: child = successor->children[RBTREE_RIGHT];
240: parent = rbtree_parent(node);
241:
242: if (unlikely(parent == NULL))
243: tree->root = successor;
244: else
245: parent->children[rbtree_index(node, parent)] = successor;
246:
247: parent = rbtree_parent(successor);
248:
249: /*
250: * Set parent directly to keep the original color.
251: */
252: successor->parent = node->parent;
253: successor->children[RBTREE_LEFT] = node->children[RBTREE_LEFT];
254: rbtree_set_parent(successor->children[RBTREE_LEFT], successor);
255:
256: if (node == parent)
257: parent = successor;
258: else {
259: successor->children[RBTREE_RIGHT] = node->children[RBTREE_RIGHT];
260: rbtree_set_parent(successor->children[RBTREE_RIGHT], successor);
261: parent->children[RBTREE_LEFT] = child;
262:
263: if (child != NULL)
264: rbtree_set_parent(child, parent);
265: }
266:
267: goto update_color;
268: }
269:
270: /*
271: * Node has at most one child.
272: */
273:
274: color = rbtree_color(node);
275: parent = rbtree_parent(node);
276:
277: if (child != NULL)
278: rbtree_set_parent(child, parent);
279:
280: if (unlikely(parent == NULL))
281: tree->root = child;
282: else
283: parent->children[rbtree_index(node, parent)] = child;
284:
285: /*
286: * The node has been removed, update the colors. The child pointer can
287: * be null, in which case it is considered a black leaf.
288: */
289: update_color:
290: if (color == RBTREE_COLOR_RED)
291: return;
292:
293: for (;;) {
294: if ((child != NULL) && rbtree_is_red(child)) {
295: rbtree_set_black(child);
296: break;
297: }
298:
299: if (parent == NULL)
300: break;
301:
302: left = rbtree_index(child, parent);
303: right = 1 - left;
304:
305: brother = parent->children[right];
306:
307: /*
308: * Brother is red. Recolor and rotate left at parent so that brother
309: * becomes black.
310: */
311: if (rbtree_is_red(brother)) {
312: rbtree_set_black(brother);
313: rbtree_set_red(parent);
314: rbtree_rotate(tree, parent, left);
315: brother = parent->children[right];
316: }
317:
318: /*
319: * Brother has no red child. Recolor and repeat at parent.
320: */
321: if (((brother->children[RBTREE_LEFT] == NULL)
322: || rbtree_is_black(brother->children[RBTREE_LEFT]))
323: && ((brother->children[RBTREE_RIGHT] == NULL)
324: || rbtree_is_black(brother->children[RBTREE_RIGHT]))) {
325: rbtree_set_red(brother);
326: child = parent;
327: parent = rbtree_parent(child);
328: continue;
329: }
330:
331: /*
332: * Brother's right child is black. Recolor and rotate right at brother.
333: */
334: if ((brother->children[right] == NULL)
335: || rbtree_is_black(brother->children[right])) {
336: rbtree_set_black(brother->children[left]);
337: rbtree_set_red(brother);
338: rbtree_rotate(tree, brother, right);
339: brother = parent->children[right];
340: }
341:
342: /*
343: * Brother's left child is black. Exchange parent and brother colors
344: * (we already know brother is black), set brother's right child black,
345: * rotate left at parent and leave.
346: */
347: rbtree_set_color(brother, rbtree_color(parent));
348: rbtree_set_black(parent);
349: rbtree_set_black(brother->children[right]);
350: rbtree_rotate(tree, parent, left);
351: break;
352: }
353:
354: assert((tree->root == NULL) || rbtree_is_black(tree->root));
355: }
356:
357: struct rbtree_node * rbtree_nearest(struct rbtree_node *parent, int index,
358: int direction)
359: {
360: assert(rbtree_check_index(direction));
361:
362: if (parent == NULL)
363: return NULL;
364:
365: assert(rbtree_check_index(index));
366:
367: if (index != direction)
368: return parent;
369:
370: return rbtree_walk(parent, direction);
371: }
372:
373: struct rbtree_node * rbtree_firstlast(const struct rbtree *tree, int direction)
374: {
375: struct rbtree_node *prev, *cur;
376:
377: assert(rbtree_check_index(direction));
378:
379: prev = NULL;
380:
381: for (cur = tree->root; cur != NULL; cur = cur->children[direction])
382: prev = cur;
383:
384: return prev;
385: }
386:
387: struct rbtree_node * rbtree_walk(struct rbtree_node *node, int direction)
388: {
389: int left, right;
390:
391: assert(rbtree_check_index(direction));
392:
393: left = direction;
394: right = 1 - left;
395:
396: if (node == NULL)
397: return NULL;
398:
399: if (node->children[left] != NULL) {
400: node = node->children[left];
401:
402: while (node->children[right] != NULL)
403: node = node->children[right];
404: } else {
405: struct rbtree_node *parent;
406: int index;
407:
408: for (;;) {
409: parent = rbtree_parent(node);
410:
411: if (parent == NULL)
412: return NULL;
413:
414: index = rbtree_index(node, parent);
415: node = parent;
416:
417: if (index == right)
418: break;
419: }
420: }
421:
422: return node;
423: }
424:
425: /*
426: * Return the left-most deepest child node of the given node.
427: */
428: static struct rbtree_node * rbtree_find_deepest(struct rbtree_node *node)
429: {
430: struct rbtree_node *parent;
431:
432: assert(node != NULL);
433:
434: for (;;) {
435: parent = node;
436: node = node->children[RBTREE_LEFT];
437:
438: if (node == NULL) {
439: node = parent->children[RBTREE_RIGHT];
440:
441: if (node == NULL)
442: return parent;
443: }
444: }
445: }
446:
447: struct rbtree_node * rbtree_postwalk_deepest(const struct rbtree *tree)
448: {
449: struct rbtree_node *node;
450:
451: node = tree->root;
452:
453: if (node == NULL)
454: return NULL;
455:
456: return rbtree_find_deepest(node);
457: }
458:
459: struct rbtree_node * rbtree_postwalk_unlink(struct rbtree_node *node)
460: {
461: struct rbtree_node *parent;
462: int index;
463:
464: if (node == NULL)
465: return NULL;
466:
467: assert(node->children[RBTREE_LEFT] == NULL);
468: assert(node->children[RBTREE_RIGHT] == NULL);
469:
470: parent = rbtree_parent(node);
471:
472: if (parent == NULL)
473: return NULL;
474:
475: index = rbtree_index(node, parent);
476: parent->children[index] = NULL;
477: node = parent->children[RBTREE_RIGHT];
478:
479: if (node == NULL)
480: return parent;
481:
482: return rbtree_find_deepest(node);
483: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.