1 /* ----------------------------------------------------------------------- *
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
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 * ----------------------------------------------------------------------- */
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.
48 struct rbtree *rb_search(struct rbtree *tree, uint64_t key)
50 struct rbtree *best = NULL;
55 else if (tree->key > key)
65 static bool is_red(struct rbtree *h)
70 static struct rbtree *rotate_left(struct rbtree *h)
72 struct rbtree *x = h->right;
75 x->red = x->left->red;
80 static struct rbtree *rotate_right(struct rbtree *h)
82 struct rbtree *x = h->left;
85 x->red = x->right->red;
90 static void color_flip(struct rbtree *h)
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)
104 if (is_red(tree->left) && is_red(tree->right))
107 if (node->key < tree->key)
108 tree->left = rb_insert(tree->left, node);
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);