1 // util/rbtree.h -- A red/black tree implementation
3 // This software is copyright (c) 2006 Scott Wood <scott@buserror.net>.
5 // Permission is hereby granted, free of charge, to any person obtaining a copy of
6 // this software and associated documentation files (the "Software"), to deal with
7 // the Software without restriction, including without limitation the rights to
8 // use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
9 // of the Software, and to permit persons to whom the Software is furnished to do
10 // so, subject to the following conditions:
12 // * Redistributions of source code must retain the above copyright notice,
13 // this list of conditions and the following disclaimers.
15 // * Redistributions in binary form must reproduce the above copyright notice,
16 // this list of conditions and the following disclaimers in the
17 // documentation and/or other materials provided with the distribution.
19 // * The names of the Software's authors and/or contributors
20 // may not be used to endorse or promote products derived from
21 // this Software without specific prior written permission.
23 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
25 // FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 // CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
31 #ifndef _UTIL_RBTREE_H
32 #define _UTIL_RBTREE_H
39 // T must have an RBTree<T, NodeV, KeyV>::Node member called rbtree_node.
40 // NodeV < NodeV, NodeV < KeyV, and NodeV > KeyV must be supported.
42 // Using NodeV != KeyV allows things such as having NodeV represent a
43 // range of values and KeyV a single value, causing find() to search
44 // for the node in whose range KeyV falls. It is an error to add
45 // nodes that are not well ordered.
47 template <typename T, typename NodeV, typename KeyV>
51 Node *parent, *left, *right;
55 // A pointer to the parent's left or right pointer
56 // (whichever side this node is on). This is also
57 // used for sanity checks (it is NULL for nodes not
64 parent = left = right = NULL;
70 return parentlink != NULL;
77 T *node_to_type(Node *n)
79 return reinterpret_cast<T *>(reinterpret_cast<uintptr_t>(n) -
80 offsetof(T, rbtree_node));
83 void assert_rb_condition(Node *left, Node *right)
85 assert(left->value < right->value);
86 assert(!(right->value < left->value));
87 assert(!left->red || !right->red);
90 void assert_well_ordered(Node *left, NodeV right)
92 assert(left->value < right);
93 assert(!(left->value > right));
94 assert(!left->red || !right->red);
97 Node *find_node(Node *n, NodeV &val, Node ***link);
98 Node *find_node_key(KeyV val, bool exact = true);
100 bool node_is_left(Node *n)
102 assert(n->parentlink == &n->parent->left ||
103 n->parentlink == &n->parent->right);
105 return n->parentlink == &n->parent->left;
108 Node *sibling(Node *n)
111 return n->parent->right;
113 return n->parent->left;
118 return sibling(n->parent);
121 void rotate_left(Node *n);
122 void rotate_right(Node *n);
124 // B must have no right child and have A as an ancestor.
125 void swap(Node *a, Node *b);
145 Node *n = find_node_key(value);
148 return node_to_type(n);
153 T *find_nearest(KeyV value)
155 Node *n = find_node_key(value, false);
158 return node_to_type(n);
160 // Should only happen on an empty tree
168 template <typename T, typename NodeV, typename KeyV>
169 typename RBTree<T, NodeV, KeyV>::Node *
170 RBTree<T, NodeV, KeyV>::find_node(Node *n, NodeV &val, Node ***link)
176 *link = n->parentlink;
186 if (n->value < val) {
190 assert_rb_condition(n, next);
198 // This assert detects duplicate nodes, but not
199 // overlapping ranges (or otherwise non-well-ordered
202 assert(val < n->value);
206 assert_rb_condition(next, n);
221 template <typename T, typename NodeV, typename KeyV>
222 typename RBTree<T, NodeV, KeyV>::Node *
223 RBTree<T, NodeV, KeyV>::find_node_key(KeyV val, bool exact)
230 if (n->value < val) {
234 assert_rb_condition(n, next);
235 } else if (n->value > val) {
239 assert_rb_condition(next, n);
253 template <typename T, typename NodeV, typename KeyV>
254 void RBTree<T, NodeV, KeyV>::rotate_left(Node *n)
256 Node *new_top = n->right;
258 assert(*n->parentlink == n);
259 *n->parentlink = new_top;
261 assert(new_top->parent == n);
262 assert(new_top->parentlink == &n->right);
264 new_top->parent = n->parent;
265 new_top->parentlink = n->parentlink;
268 n->parentlink = &new_top->left;
270 n->right = new_top->left;
274 assert(n->right->parent == new_top);
275 assert(n->right->parentlink == &new_top->left);
277 n->right->parent = n;
278 n->right->parentlink = &n->right;
282 template <typename T, typename NodeV, typename KeyV>
283 void RBTree<T, NodeV, KeyV>::rotate_right(Node *n)
285 Node *new_top = n->left;
287 assert(*n->parentlink == n);
288 *n->parentlink = new_top;
290 assert(new_top->parent == n);
291 assert(new_top->parentlink == &n->left);
293 new_top->parent = n->parent;
294 new_top->parentlink = n->parentlink;
297 n->parentlink = &new_top->right;
299 n->left = new_top->right;
303 assert(n->left->parent == new_top);
304 assert(n->left->parentlink == &new_top->right);
307 n->left->parentlink = &n->left;
311 // B must have no right child and have A as an ancestor.
312 template <typename T, typename NodeV, typename KeyV>
313 void RBTree<T, NodeV, KeyV>::swap(Node *a, Node *b)
315 Node *bparent = b->parent;
316 Node **bparentlink = b->parentlink;
319 assert(a->left || a->right);
321 b->parent = a->parent;
322 b->parentlink = a->parentlink;
326 a->parentlink = &b->left;
329 a->parentlink = bparentlink;
332 assert(a->parent != a);
333 assert(b->parent != b);
335 Node *bleft = b->left;
345 assert(a->parent != a);
346 assert(b->parent != b);
354 a->left->parentlink = &a->left;
358 b->right->parent = b;
359 b->right->parentlink = &b->right;
364 b->left->parentlink = &b->left;
367 template <typename T, typename NodeV, typename KeyV>
368 void RBTree<T, NodeV, KeyV>::add(T *t)
370 Node *n = &t->rbtree_node;
371 assert(!n->is_on_rbtree());
373 Node *insert_at = find_node(top, n->value, &n->parentlink);
375 assert(insert_at || !top);
377 n->parent = insert_at;
378 n->left = n->right = NULL;
381 assert(n->parentlink);
382 assert(*n->parentlink == n);
389 assert(n->parent->value < n->value != n->value < n->parent->value);
395 Node *unc = uncle(n);
397 assert(!n->parent->parent->red);
398 n->parent->red = unc->red = false;
399 n = n->parent->parent;
403 if (node_is_left(n)) {
404 if (!node_is_left(n->parent)) {
405 rotate_right(n->parent);
409 if (node_is_left(n->parent)) {
410 rotate_left(n->parent);
415 assert(n->parent->red);
416 assert(!red(uncle(n)));
417 assert(!n->parent->parent->red);
419 n->parent->red = false;
420 n->parent->parent->red = true;
422 if (node_is_left(n)) {
423 assert(node_is_left(n->parent));
424 rotate_right(n->parent->parent);
426 assert(!node_is_left(n->parent));
427 rotate_left(n->parent->parent);
431 template <typename T, typename NodeV, typename KeyV>
432 void RBTree<T, NodeV, KeyV>::del(T *t)
434 Node *n = &t->rbtree_node;
435 assert(*n->parentlink == n);
437 if (n->left && n->right) {
438 Node *highest_on_left = find_node(n->left, n->value, NULL);
439 assert(!highest_on_left->right);
440 swap(n, highest_on_left);
444 Node *parent = n->parent;
445 Node *child = n->left ? n->left : n->right;
448 assert(child->parent == n);
450 child->parent = n->parent;
451 child->parentlink = n->parentlink;
452 *child->parentlink = child;
453 assert(child != parent);
455 *n->parentlink = NULL;
458 n->parentlink = NULL;
481 sib = parent->left ? parent->left : parent->right;
484 assert(!parent->red);
485 assert(!red(sib->left));
486 assert(!red(sib->right));
491 if (node_is_left(sib)) {
492 rotate_right(parent);
500 assert(sib == sibling(n));
501 } else if (!parent->red && !red(sib->left) && !red(sib->right)) {
505 parent = parent->parent;
511 if (!parent->red && !red(sib->left) && !red(sib->right)) {
517 if (!red(sib->left) && !red(sib->right)) {
524 if (node_is_left(sib) && !red(sib->left) && red(sib->right)) {
526 sib->right->red = false;
529 } else if (!node_is_left(sib) && !red(sib->right) && red(sib->left)) {
531 sib->left->red = false;
536 assert(parent == sib->parent);
539 sib->red = parent->red;
542 if (node_is_left(sib)) {
543 assert(sib->left->red);
544 sib->left->red = false;
545 rotate_right(parent);
547 assert(sib->right->red);
548 sib->right->red = false;