include/rbtree.h

   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 #ifndef NASM_RBTREE_H
  35 #define NASM_RBTREE_H
  36
  37 #include "compiler.h"
  38
  39 /*
  40  * This structure should be embedded in a larger data structure;
  41  * the final output from rb_search() can then be converted back
  42  * to the larger data structure via container_of().
  43  *
  44  * An empty tree is simply represented by a NULL pointer.
  45  */
  46
  47 /* Note: the values of these flags is significant */
  48 enum rbtree_node_flags {
  49     RBTREE_NODE_BLACK   = 1,  /* Node color is black */
  50     RBTREE_NODE_PRED    = 2,  /* Left pointer is an uplink */
  51     RBTREE_NODE_SUCC    = 4   /* Right pointer is an uplink */
  52 };
  53
  54 struct rbtree {
  55     uint64_t key;
  56     struct rbtree_metadata {
  57         struct rbtree *left, *right;
  58         enum rbtree_node_flags flags;
  59     } m;
  60 };
  61
  62 /*
  63  * Add a node to a tree. Returns the new root pointer.
  64  * The key value in the structure needs to be preinitialized;
  65  * the rest of the structure should be zero.
  66  */
  67 struct rbtree *rb_insert(struct rbtree *, struct rbtree *);
  68
  69 /*
  70  * Find a node in the tree corresponding to the key immediately
  71  * <= the passed-in key value.
  72  */
  73 struct rbtree *rb_search(const struct rbtree *, uint64_t);
  74
  75 /*
  76  * Find a node in the tree exactly matching the key value.
  77  */
  78 struct rbtree *rb_search_exact(const struct rbtree *, uint64_t);
  79
  80 /*
  81  * Return the immediately previous or next node in key order.
  82  * Returns NULL if this node is the end of the tree.
  83  * These operations are safe for complee (but not partial!)
  84  * tree walk-with-destruction in key order.
  85  */
  86 struct rbtree *rb_prev(const struct rbtree *);
  87 struct rbtree *rb_next(const struct rbtree *);
  88
  89 /*
  90  * Return the very first or very last node in key order.
  91  */
  92 struct rbtree *rb_first(const struct rbtree *);
  93 struct rbtree *rb_last(const struct rbtree *);
  94
  95 /*
  96  * Left and right nodes, if real. These operations are
  97  * safe for tree destruction, but not for splitting a tree.
  98  */
  99 static inline struct rbtree *rb_left(const struct rbtree *rb)
 100 {
 101     return (rb->m.flags & RBTREE_NODE_PRED) ? NULL : rb->m.left;
 102 }
 103 static inline struct rbtree *rb_right(const struct rbtree *rb)
 104 {
 105     return (rb->m.flags & RBTREE_NODE_SUCC) ? NULL : rb->m.right;
 106 }
 107
 108 #endif /* NASM_RBTREE_H */