com32/sysdump/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 <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 }