|
10554
|
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 }
|
