Merge branch 'nasm-2.09.xx'
[nasm/nasm.git] / rbtree.c
blob5af6067d6cc86e300cfad8976d60828dd863ad4a
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.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following
9 * conditions are met:
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.
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.
32 * ----------------------------------------------------------------------- */
35 * rbtree.c
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.
42 * See http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf for
43 * information about left-leaning red-black trees.
46 #include "rbtree.h"
48 struct rbtree *rb_search(struct rbtree *tree, uint64_t key)
50 struct rbtree *best = NULL;
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;
62 return best;
65 static bool is_red(struct rbtree *h)
67 return h && h->red;
70 static struct rbtree *rotate_left(struct rbtree *h)
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;
80 static struct rbtree *rotate_right(struct rbtree *h)
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;
90 static void color_flip(struct rbtree *h)
92 h->red = !h->red;
93 h->left->red = !h->left->red;
94 h->right->red = !h->right->red;
97 struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node)
99 if (!tree) {
100 node->red = true;
101 return node;
104 if (is_red(tree->left) && is_red(tree->right))
105 color_flip(tree);
107 if (node->key < tree->key)
108 tree->left = rb_insert(tree->left, node);
109 else
110 tree->right = rb_insert(tree->right, node);
112 if (is_red(tree->right))
113 tree = rotate_left(tree);
115 if (is_red(tree->left) && is_red(tree->left->left))
116 tree = rotate_right(tree);
118 return tree;