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 "rbtree.h" |
47 | |
48 | struct rbtree *rb_search(struct rbtree *tree, uint64_t key) |
49 | { |
50 | struct rbtree *best = NULL; |
51 | |
52 | while (tree) { |
53 | if (tree->key == key) |
54 | return tree; |
55 | else if (tree->key > key) |
56 | tree = tree->left; |
57 | else { |
58 | best = tree; |
59 | tree = tree->right; |
60 | } |
61 | } |
62 | return best; |
63 | } |
64 | |
65 | static bool is_red(struct rbtree *h) |
66 | { |
67 | return h && h->red; |
68 | } |
69 | |
70 | static struct rbtree *rotate_left(struct rbtree *h) |
71 | { |
72 | struct rbtree *x = h->right; |
73 | h->right = x->left; |
74 | x->left = h; |
75 | x->red = x->left->red; |
76 | x->left->red = true; |
77 | return x; |
78 | } |
79 | |
80 | static struct rbtree *rotate_right(struct rbtree *h) |
81 | { |
82 | struct rbtree *x = h->left; |
83 | h->left = x->right; |
84 | x->right = h; |
85 | x->red = x->right->red; |
86 | x->right->red = true; |
87 | return x; |
88 | } |
89 | |
90 | static void color_flip(struct rbtree *h) |
91 | { |
92 | h->red = !h->red; |
93 | h->left->red = !h->left->red; |
94 | h->right->red = !h->right->red; |
95 | } |
96 | |
97 | struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node) |
98 | { |
99 | if (!tree) { |
100 | node->red = true; |
101 | return node; |
102 | } |
103 | |
104 | if (is_red(tree->left) && is_red(tree->right)) |
105 | color_flip(tree); |
106 | |
107 | if (node->key < tree->key) |
108 | tree->left = rb_insert(tree->left, node); |
109 | else |
110 | tree->right = rb_insert(tree->right, node); |
111 | |
112 | if (is_red(tree->right)) |
113 | tree = rotate_left(tree); |
114 | |
115 | if (is_red(tree->left) && is_red(tree->left->left)) |
116 | tree = rotate_right(tree); |
117 | |
118 | return tree; |
119 | } |
120 | |