rbtree.c

   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 }