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 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 66 static bool is_red(struct rbtree *h) 67 { 68 return h && h->red; 69 } 70 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 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 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 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 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
