nasmlib/rbtree.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2020 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 threaded red-black tree"
  38  * with 64-bit integer keys.  The search operation will return the
  39  * highest node <= the key; only search and insert are supported, but
  40  * additional 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  * The "threaded" part means that left and right pointers that would
  46  * otherwise be NULL are pointers to the in-order predecessor or
  47  * successor node. The only pointers that are NULL are the very left-
  48  * and rightmost, for which no corresponding side node exists.
  49  *
  50  * This, among other things, allows for efficient predecessor and
  51  * successor operations without requiring dedicated space for a parent
  52  * pointer.
  53  *
  54  * This implementation is robust for identical key values; such keys
  55  * will not have their insertion order preserved, and after insertion
  56  * of unrelated keys a lookup may return a different node for the
  57  * duplicated key, but the prev/next operations will always enumerate
  58  * all entries.
  59  *
  60  * The NULL pointers at the end are considered predecessor/successor
  61  * pointers, so if the corresponding flags are clear it is always safe
  62  * to access the pointed-to object without an explicit NULL pointer
  63  * check.
  64  */
  65
  66 #include "rbtree.h"
  67 #include "nasmlib.h"
  68
  69 struct rbtree *rb_search(const struct rbtree *tree, uint64_t key)
  70 {
  71     const struct rbtree *best = NULL;
  72
  73     if (tree) {
  74         while (true) {
  75             if (tree->key > key) {
  76                 if (tree->m.flags & RBTREE_NODE_PRED)
  77                     break;
  78                 tree = tree->m.left;
  79             } else {
  80                 best = tree;
  81                 if (tree->key == key || (tree->m.flags & RBTREE_NODE_SUCC))
  82                     break;
  83                 tree = tree->m.right;
  84             }
  85         }
  86     }
  87     return (struct rbtree *)best;
  88 }
  89
  90 struct rbtree *rb_search_exact(const struct rbtree *tree, uint64_t key)
  91 {
  92     struct rbtree *rv;
  93
  94     rv = rb_search(tree, key);
  95     return (rv && rv->key == key) ? rv : NULL;
  96 }
  97
  98 /* Reds two left in a row? */
  99 static inline bool is_red_left_left(struct rbtree *h)
 100 {
 101     return !(h->m.flags & RBTREE_NODE_PRED) &&
 102         !(h->m.left->m.flags & (RBTREE_NODE_BLACK|RBTREE_NODE_PRED)) &&
 103         !(h->m.left->m.left->m.flags & RBTREE_NODE_BLACK);
 104 }
 105
 106 /* Node to the right is red? */
 107 static inline bool is_red_right(struct rbtree *h)
 108 {
 109     return !(h->m.flags & RBTREE_NODE_SUCC) &&
 110            !(h->m.right->m.flags & RBTREE_NODE_BLACK);
 111 }
 112
 113 /* Both the left and right hand nodes are red? */
 114 static inline bool is_red_both(struct rbtree *h)
 115 {
 116     return !(h->m.flags & (RBTREE_NODE_PRED|RBTREE_NODE_SUCC))
 117         && !(h->m.left->m.flags & h->m.right->m.flags & RBTREE_NODE_BLACK);
 118 }
 119
 120 static inline struct rbtree *rotate_left(struct rbtree *h)
 121 {
 122     struct rbtree *x = h->m.right;
 123     enum rbtree_node_flags hf = h->m.flags;
 124     enum rbtree_node_flags xf = x->m.flags;
 125
 126     if (xf & RBTREE_NODE_PRED) {
 127         h->m.right = x;
 128         h->m.flags = (hf & RBTREE_NODE_PRED)  | RBTREE_NODE_SUCC;
 129     } else {
 130         h->m.right = x->m.left;
 131         h->m.flags = hf & RBTREE_NODE_PRED;
 132     }
 133     x->m.flags = (hf & RBTREE_NODE_BLACK) | (xf & RBTREE_NODE_SUCC);
 134     x->m.left = h;
 135
 136     return x;
 137 }
 138
 139 static inline struct rbtree *rotate_right(struct rbtree *h)
 140 {
 141     struct rbtree *x = h->m.left;
 142     enum rbtree_node_flags hf = h->m.flags;
 143     enum rbtree_node_flags xf = x->m.flags;
 144
 145     if (xf & RBTREE_NODE_SUCC) {
 146         h->m.left = x;
 147         h->m.flags = (hf & RBTREE_NODE_SUCC)  | RBTREE_NODE_PRED;
 148     } else {
 149         h->m.left = x->m.right;
 150         h->m.flags = hf & RBTREE_NODE_SUCC;
 151     }
 152     x->m.flags = (hf & RBTREE_NODE_BLACK) | (xf & RBTREE_NODE_PRED);
 153     x->m.right = h;
 154
 155     return x;
 156 }
 157
 158 static inline void color_flip(struct rbtree *h)
 159 {
 160     h->m.flags          ^= RBTREE_NODE_BLACK;
 161     h->m.left->m.flags  ^= RBTREE_NODE_BLACK;
 162     h->m.right->m.flags ^= RBTREE_NODE_BLACK;
 163 }
 164
 165 static struct rbtree *
 166 _rb_insert(struct rbtree *tree, struct rbtree *node);
 167
 168 struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node)
 169 {
 170     /* Initialize node as if it was the sole member of the tree */
 171
 172     nasm_zero(node->m);
 173     node->m.flags = RBTREE_NODE_PRED|RBTREE_NODE_SUCC;
 174
 175     if (unlikely(!tree))
 176         return node;
 177
 178     return _rb_insert(tree, node);
 179 }
 180
 181 static struct rbtree *
 182 _rb_insert(struct rbtree *tree, struct rbtree *node)
 183 {
 184     /* Recursive part of the algorithm */
 185
 186     /* Red on both sides? */
 187     if (is_red_both(tree))
 188         color_flip(tree);
 189
 190     if (node->key < tree->key) {
 191         node->m.right  = tree;  /* Potential successor */
 192         if (tree->m.flags & RBTREE_NODE_PRED) {
 193             node->m.left   = tree->m.left;
 194             tree->m.flags &= ~RBTREE_NODE_PRED;
 195             tree->m.left   = node;
 196         } else {
 197             tree->m.left   = _rb_insert(tree->m.left, node);
 198         }
 199     } else {
 200         node->m.left   = tree;  /* Potential predecessor */
 201         if (tree->m.flags & RBTREE_NODE_SUCC) {
 202             node->m.right  = tree->m.right;
 203             tree->m.flags &= ~RBTREE_NODE_SUCC;
 204             tree->m.right  = node;
 205         } else {
 206             tree->m.right  = _rb_insert(tree->m.right, node);
 207         }
 208     }
 209
 210     if (is_red_right(tree))
 211         tree = rotate_left(tree);
 212
 213     if (is_red_left_left(tree))
 214         tree = rotate_right(tree);
 215
 216     return tree;
 217 }
 218
 219 struct rbtree *rb_first(const struct rbtree *tree)
 220 {
 221     if (unlikely(!tree))
 222         return NULL;
 223
 224     while (!(tree->m.flags & RBTREE_NODE_PRED))
 225         tree = tree->m.left;
 226
 227     return (struct rbtree *)tree;
 228 }
 229
 230 struct rbtree *rb_last(const struct rbtree *tree)
 231 {
 232     if (unlikely(!tree))
 233         return NULL;
 234
 235     while (!(tree->m.flags & RBTREE_NODE_SUCC))
 236         tree = tree->m.right;
 237
 238     return (struct rbtree *)tree;
 239 }
 240
 241 struct rbtree *rb_prev(const struct rbtree *node)
 242 {
 243     struct rbtree *np = node->m.left;
 244
 245     if (node->m.flags & RBTREE_NODE_PRED)
 246         return np;
 247     else
 248         return rb_last(np);
 249 }
 250
 251 struct rbtree *rb_next(const struct rbtree *node)
 252 {
 253     struct rbtree *np = node->m.right;
 254
 255     if (node->m.flags & RBTREE_NODE_SUCC)
 256         return np;
 257     else
 258         return rb_first(np);
 259 }