lib/llrb.h

   1 /* ==========================================================================
   2  * llrb.h - Iterative Left-leaning Red-Black Tree.
   3  * --------------------------------------------------------------------------
   4  * Copyright (c) 2011, 2013  William Ahern <william@25thandClement.com>
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sublicense, and/or sell copies of the Software, and to permit
  11  * persons to whom the Software is furnished to do so, subject to the
  12  * following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included
  15  * in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  18  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
  20  * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
  21  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  22  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
  23  * USE OR OTHER DEALINGS IN THE SOFTWARE.
  24  * --------------------------------------------------------------------------
  25  * CREDITS:
  26  *      o Algorithm courtesy of Robert Sedgewick, "Left-leaning Red-Black
  27  *        Trees" (September 2008); and Robert Sedgewick and Kevin Wayne,
  28  *        Algorithms (4th ed. 2011).
  29  *
  30  *        Sedgewick touts the simplicity of the recursive implementation,
  31  *        but at least for the 2-3 tree variant the iterative approach is
  32  *        almost line-for-line identical. The magic of C pointers helps;
  33  *        it'd be uglier with Java.
  34  *
  35  *        A couple of missing NULL checks were added to Sedgewick's deletion
  36  *        example, and insert was optimized to short-circuit rotations when
  37  *        walking up the tree.
  38  *
  39  *      o Code implemented in the fashion of Niels Provos' excellent *BSD
  40  *        sys/tree.h pre-processor library.
  41  *
  42  *        Regarding relative performance, I've refrained from sharing my own
  43  *        benchmarks. Differences in run-time speed were too correlated to
  44  *        compiler options and other external factors.
  45  *
  46  *        Provos' delete implementation doesn't need to start at the root of
  47  *        the tree. However, RB_REMOVE must be passed the actual node to be
  48  *        removed. LLRB_REMOVE merely requires a key, much like
  49  *        RB_FIND/LLRB_FIND.
  50  * ==========================================================================
  51  */
  52 #ifndef LLRB_H
  53 #define LLRB_H
  54
  55 #define LLRB_VENDOR "william@25thandClement.com"
  56 #define LLRB_VERSION 0x20130925
  57
  58 #ifndef LLRB_STATIC
  59 #ifdef __GNUC__
  60 #define LLRB_STATIC __attribute__((__unused__)) static
  61 #else
  62 #define LLRB_STATIC static
  63 #endif
  64 #endif
  65
  66 #define LLRB_HEAD(name, type) \
  67 struct name { struct type *rbh_root; }
  68
  69 #define LLRB_INITIALIZER(root) { 0 }
  70
  71 #define LLRB_INIT(root) do { (root)->rbh_root = 0; } while (0)
  72
  73 #define LLRB_BLACK 0
  74 #define LLRB_RED   1
  75
  76 #define LLRB_ENTRY(type) \
  77 struct { struct type *rbe_left, *rbe_right, *rbe_parent; _Bool rbe_color; }
  78
  79 #define LLRB_LEFT(elm, field) (elm)->field.rbe_left
  80 #define LLRB_RIGHT(elm, field) (elm)->field.rbe_right
  81 #define LLRB_PARENT(elm, field) (elm)->field.rbe_parent
  82 #define LLRB_EDGE(head, elm, field) (((elm) == LLRB_ROOT(head))? &LLRB_ROOT(head) : ((elm) == LLRB_LEFT(LLRB_PARENT((elm), field), field))? &LLRB_LEFT(LLRB_PARENT((elm), field), field) : &LLRB_RIGHT(LLRB_PARENT((elm), field), field))
  83 #define LLRB_COLOR(elm, field) (elm)->field.rbe_color
  84 #define LLRB_ROOT(head) (head)->rbh_root
  85 #define LLRB_EMPTY(head) ((head)->rbh_root == 0)
  86 #define LLRB_ISRED(elm, field) ((elm) && LLRB_COLOR((elm), field) == LLRB_RED)
  87
  88 #define LLRB_PROTOTYPE(name, type, field, cmp) \
  89         LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
  90 #define LLRB_PROTOTYPE_STATIC(name, type, field, cmp) \
  91         LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
  92 #define LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
  93 attr struct type *name##_LLRB_INSERT(struct name *, struct type *); \
  94 attr struct type *name##_LLRB_DELETE(struct name *, struct type *); \
  95 attr struct type *name##_LLRB_FIND(struct name *, struct type *); \
  96 attr struct type *name##_LLRB_MIN(struct type *); \
  97 attr struct type *name##_LLRB_MAX(struct type *); \
  98 attr struct type *name##_LLRB_NEXT(struct type *);
  99
 100 #define LLRB_GENERATE(name, type, field, cmp) \
 101         LLRB_GENERATE_INTERNAL(name, type, field, cmp,)
 102 #define LLRB_GENERATE_STATIC(name, type, field, cmp) \
 103         LLRB_GENERATE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
 104 #define LLRB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
 105 static inline void name##_LLRB_ROTL(struct type **pivot) { \
 106         struct type *a = *pivot; \
 107         struct type *b = LLRB_RIGHT(a, field); \
 108         if ((LLRB_RIGHT(a, field) = LLRB_LEFT(b, field))) \
 109                 LLRB_PARENT(LLRB_RIGHT(a, field), field) = a; \
 110         LLRB_LEFT(b, field) = a; \
 111         LLRB_COLOR(b, field) = LLRB_COLOR(a, field); \
 112         LLRB_COLOR(a, field) = LLRB_RED; \
 113         LLRB_PARENT(b, field) = LLRB_PARENT(a, field); \
 114         LLRB_PARENT(a, field) = b; \
 115         *pivot = b; \
 116 } \
 117 static inline void name##_LLRB_ROTR(struct type **pivot) { \
 118         struct type *b = *pivot; \
 119         struct type *a = LLRB_LEFT(b, field); \
 120         if ((LLRB_LEFT(b, field) = LLRB_RIGHT(a, field))) \
 121                 LLRB_PARENT(LLRB_LEFT(b, field), field) = b; \
 122         LLRB_RIGHT(a, field) = b; \
 123         LLRB_COLOR(a, field) = LLRB_COLOR(b, field); \
 124         LLRB_COLOR(b, field) = LLRB_RED; \
 125         LLRB_PARENT(a, field) = LLRB_PARENT(b, field); \
 126         LLRB_PARENT(b, field) = a; \
 127         *pivot = a; \
 128 } \
 129 static inline void name##_LLRB_FLIP(struct type *root) { \
 130         LLRB_COLOR(root, field) = !LLRB_COLOR(root, field); \
 131         LLRB_COLOR(LLRB_LEFT(root, field), field) = !LLRB_COLOR(LLRB_LEFT(root, field), field); \
 132         LLRB_COLOR(LLRB_RIGHT(root, field), field) = !LLRB_COLOR(LLRB_RIGHT(root, field), field); \
 133 } \
 134 static inline void name##_LLRB_FIXUP(struct type **root) { \
 135         if (LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field)) \
 136                 name##_LLRB_ROTL(root); \
 137         if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
 138                 name##_LLRB_ROTR(root); \
 139         if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_RIGHT(*root, field), field)) \
 140                 name##_LLRB_FLIP(*root); \
 141 } \
 142 attr struct type *name##_LLRB_INSERT(struct name *head, struct type *elm) { \
 143         struct type **root = &LLRB_ROOT(head); \
 144         struct type *parent = 0; \
 145         while (*root) { \
 146                 int comp = (cmp)((elm), (*root)); \
 147                 parent = *root; \
 148                 if (comp < 0) \
 149                         root = &LLRB_LEFT(*root, field); \
 150                 else if (comp > 0) \
 151                         root = &LLRB_RIGHT(*root, field); \
 152                 else \
 153                         return *root; \
 154         } \
 155         LLRB_LEFT((elm), field) = 0; \
 156         LLRB_RIGHT((elm), field) = 0; \
 157         LLRB_COLOR((elm), field) = LLRB_RED; \
 158         LLRB_PARENT((elm), field) = parent; \
 159         *root = (elm); \
 160         while (parent && (LLRB_ISRED(LLRB_LEFT(parent, field), field) || LLRB_ISRED(LLRB_RIGHT(parent, field), field))) { \
 161                 root = LLRB_EDGE(head, parent, field); \
 162                 parent = LLRB_PARENT(parent, field); \
 163                 name##_LLRB_FIXUP(root); \
 164         } \
 165         LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
 166         return 0; \
 167 } \
 168 static inline void name##_LLRB_MOVL(struct type **pivot) { \
 169         name##_LLRB_FLIP(*pivot); \
 170         if (LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*pivot, field), field), field)) { \
 171                 name##_LLRB_ROTR(&LLRB_RIGHT(*pivot, field)); \
 172                 name##_LLRB_ROTL(pivot); \
 173                 name##_LLRB_FLIP(*pivot); \
 174         } \
 175 } \
 176 static inline void name##_LLRB_MOVR(struct type **pivot) { \
 177         name##_LLRB_FLIP(*pivot); \
 178         if (LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) { \
 179                 name##_LLRB_ROTR(pivot); \
 180                 name##_LLRB_FLIP(*pivot); \
 181         } \
 182 } \
 183 static inline struct type *name##_DELETEMIN(struct name *head, struct type **root) { \
 184         struct type **pivot = root, *deleted, *parent; \
 185         while (LLRB_LEFT(*pivot, field)) { \
 186                 if (!LLRB_ISRED(LLRB_LEFT(*pivot, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) \
 187                         name##_LLRB_MOVL(pivot); \
 188                 pivot = &LLRB_LEFT(*pivot, field); \
 189         } \
 190         deleted = *pivot; \
 191         parent = LLRB_PARENT(*pivot, field); \
 192         *pivot = 0; \
 193         while (root != pivot) { \
 194                 pivot = LLRB_EDGE(head, parent, field); \
 195                 parent = LLRB_PARENT(parent, field); \
 196                 name##_LLRB_FIXUP(pivot); \
 197         } \
 198         return deleted; \
 199 } \
 200 attr struct type *name##_LLRB_DELETE(struct name *head, struct type *elm) { \
 201         struct type **root = &LLRB_ROOT(head), *parent = 0, *deleted = 0; \
 202         int comp; \
 203         while (*root) { \
 204                 parent = LLRB_PARENT(*root, field); \
 205                 comp = (cmp)(elm, *root); \
 206                 if (comp < 0) { \
 207                         if (LLRB_LEFT(*root, field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
 208                                 name##_LLRB_MOVL(root); \
 209                         root = &LLRB_LEFT(*root, field); \
 210                 } else { \
 211                         if (LLRB_ISRED(LLRB_LEFT(*root, field), field)) { \
 212                                 name##_LLRB_ROTR(root); \
 213                                 comp = (cmp)(elm, *root); \
 214                         } \
 215                         if (!comp && !LLRB_RIGHT(*root, field)) { \
 216                                 deleted = *root; \
 217                                 *root = 0; \
 218                                 break; \
 219                         } \
 220                         if (LLRB_RIGHT(*root, field) && !LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*root, field), field), field)) { \
 221                                 name##_LLRB_MOVR(root); \
 222                                 comp = (cmp)(elm, *root); \
 223                         } \
 224                         if (!comp) { \
 225                                 struct type *orphan = name##_DELETEMIN(head, &LLRB_RIGHT(*root, field)); \
 226                                 LLRB_COLOR(orphan, field) = LLRB_COLOR(*root, field); \
 227                                 LLRB_PARENT(orphan, field) = LLRB_PARENT(*root, field); \
 228                                 if ((LLRB_RIGHT(orphan, field) = LLRB_RIGHT(*root, field))) \
 229                                         LLRB_PARENT(LLRB_RIGHT(orphan, field), field) = orphan; \
 230                                 if ((LLRB_LEFT(orphan, field) = LLRB_LEFT(*root, field))) \
 231                                         LLRB_PARENT(LLRB_LEFT(orphan, field), field) = orphan; \
 232                                 deleted = *root; \
 233                                 *root = orphan; \
 234                                 parent = *root; \
 235                                 break; \
 236                         } else \
 237                                 root = &LLRB_RIGHT(*root, field); \
 238                 } \
 239         } \
 240         while (parent) { \
 241                 root = LLRB_EDGE(head, parent, field); \
 242                 parent = LLRB_PARENT(parent, field); \
 243                 name##_LLRB_FIXUP(root); \
 244         } \
 245         if (LLRB_ROOT(head)) \
 246                 LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
 247         return deleted; \
 248 } \
 249 attr struct type *name##_LLRB_FIND(struct name *head, struct type *key) { \
 250         struct type *elm = LLRB_ROOT(head); \
 251         while (elm) { \
 252                 int comp = (cmp)(key, elm); \
 253                 if (comp < 0) \
 254                         elm = LLRB_LEFT(elm, field); \
 255                 else if (comp > 0) \
 256                         elm = LLRB_RIGHT(elm, field); \
 257                 else \
 258                         return elm; \
 259         } \
 260         return 0; \
 261 } \
 262 attr struct type *name##_LLRB_MIN(struct type *elm) { \
 263         while (elm && LLRB_LEFT(elm, field)) \
 264                 elm = LLRB_LEFT(elm, field); \
 265         return elm; \
 266 } \
 267 attr struct type *name##_LLRB_MAX(struct type *elm) { \
 268         while (elm && LLRB_RIGHT(elm, field)) \
 269                 elm = LLRB_RIGHT(elm, field); \
 270         return elm; \
 271 } \
 272 attr struct type *name##_LLRB_NEXT(struct type *elm) { \
 273         if (LLRB_RIGHT(elm, field)) { \
 274                 return name##_LLRB_MIN(LLRB_RIGHT(elm, field)); \
 275         } else if (LLRB_PARENT(elm, field)) { \
 276                 if (elm == LLRB_LEFT(LLRB_PARENT(elm, field), field)) \
 277                         return LLRB_PARENT(elm, field); \
 278                 while (LLRB_PARENT(elm, field) && elm == LLRB_RIGHT(LLRB_PARENT(elm, field), field)) \
 279                         elm = LLRB_PARENT(elm, field); \
 280                 return LLRB_PARENT(elm, field); \
 281         } else return 0; \
 282 }
 283
 284 #define LLRB_INSERT(name, head, elm) name##_LLRB_INSERT((head), (elm))
 285 #define LLRB_DELETE(name, head, elm) name##_LLRB_DELETE((head), (elm))
 286 #define LLRB_REMOVE(name, head, elm) name##_LLRB_DELETE((head), (elm))
 287 #define LLRB_FIND(name, head, elm) name##_LLRB_FIND((head), (elm))
 288 #define LLRB_MIN(name, head) name##_LLRB_MIN(LLRB_ROOT((head)))
 289 #define LLRB_MAX(name, head) name##_LLRB_MAX(LLRB_ROOT((head)))
 290 #define LLRB_NEXT(name, head, elm) name##_LLRB_NEXT((elm))
 291
 292 #define LLRB_FOREACH(elm, name, head) \
 293 for ((elm) = LLRB_MIN(name, head); (elm); (elm) = name##_LLRB_NEXT((elm)))
 294
 295 #endif /* LLRB_H */