1 /* ----------------------------------------------------------------------- *
2 *
3 * Copyright 1996-2009 The NASM Authors - All Rights Reserved
4 * See the file AUTHORS included with the NASM distribution for
5 * the specific copyright holders.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following
9 * conditions are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
19 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
21 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
26 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
29 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
30 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 *
32 * ----------------------------------------------------------------------- */
33
34 /*
35 * rbtree.c
36 *
37 * Simple implementation of a left-leaning red-black tree with 64-bit
38 * integer keys. The search operation will return the highest node <=
39 * the key; only search and insert are supported, but additional
40 * standard llrbtree operations can be coded up at will.
41 *
42 * See http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf for
43 * information about left-leaning red-black trees.
44 */
45
46 #include <stdlib.h>
47 #include "rbtree.h"
48
rb_search(struct rbtree * tree,uint64_t key)49 struct rbtree *rb_search(struct rbtree *tree, uint64_t key)
50 {
51 struct rbtree *best = NULL;
52
53 while (tree) {
54 if (tree->key == key)
55 return tree;
56 else if (tree->key > key)
57 tree = tree->left;
58 else {
59 best = tree;
60 tree = tree->right;
61 }
62 }
63 return best;
64 }
65
is_red(struct rbtree * h)66 static bool is_red(struct rbtree *h)
67 {
68 return h && h->red;
69 }
70
rotate_left(struct rbtree * h)71 static struct rbtree *rotate_left(struct rbtree *h)
72 {
73 struct rbtree *x = h->right;
74 h->right = x->left;
75 x->left = h;
76 x->red = x->left->red;
77 x->left->red = true;
78 return x;
79 }
80
rotate_right(struct rbtree * h)81 static struct rbtree *rotate_right(struct rbtree *h)
82 {
83 struct rbtree *x = h->left;
84 h->left = x->right;
85 x->right = h;
86 x->red = x->right->red;
87 x->right->red = true;
88 return x;
89 }
90
color_flip(struct rbtree * h)91 static void color_flip(struct rbtree *h)
92 {
93 h->red = !h->red;
94 h->left->red = !h->left->red;
95 h->right->red = !h->right->red;
96 }
97
rb_insert(struct rbtree * tree,struct rbtree * node)98 struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node)
99 {
100 node->left = node->right = NULL;
101 node->red = false;
102
103 if (!tree) {
104 node->red = true;
105 return node;
106 }
107
108 if (is_red(tree->left) && is_red(tree->right))
109 color_flip(tree);
110
111 if (node->key < tree->key)
112 tree->left = rb_insert(tree->left, node);
113 else
114 tree->right = rb_insert(tree->right, node);
115
116 if (is_red(tree->right))
117 tree = rotate_left(tree);
118
119 if (is_red(tree->left) && is_red(tree->left->left))
120 tree = rotate_right(tree);
121
122 return tree;
123 }
124
rb_destroy(struct rbtree * tree)125 void rb_destroy(struct rbtree *tree)
126 {
127 if (tree->left)
128 rb_destroy(tree->left);
129 if (tree->right)
130 rb_destroy(tree->right);
131 free(tree);
132 }
133