include/wine/rbtree.h

   1 /*
   2  * Red-black search tree support
   3  *
   4  * Copyright 2009 Henri Verbeet
   5  * Copyright 2009 Andrew Riedi
   6  * Copyright 2016 Jacek Caban for CodeWeavers
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  21  */
  22
  23 #ifndef __WINE_WINE_RBTREE_H
  24 #define __WINE_WINE_RBTREE_H
  25
  26 #define RB_ENTRY_VALUE(element, type, field) \
  27     ((type *)((char *)(element) - offsetof(type, field)))
  28
  29 struct rb_entry
  30 {
  31     struct rb_entry *parent;
  32     struct rb_entry *left;
  33     struct rb_entry *right;
  34     unsigned int flags;
  35 };
  36
  37 typedef int (*rb_compare_func)(const void *key, const struct rb_entry *entry);
  38
  39 struct rb_tree
  40 {
  41     rb_compare_func compare;
  42     struct rb_entry *root;
  43 };
  44
  45 typedef void (rb_traverse_func)(struct rb_entry *entry, void *context);
  46
  47 #define RB_FLAG_RED                0x1
  48
  49 static inline int rb_is_red(struct rb_entry *entry)
  50 {
  51     return entry && (entry->flags & RB_FLAG_RED);
  52 }
  53
  54 static inline void rb_rotate_left(struct rb_tree *tree, struct rb_entry *e)
  55 {
  56     struct rb_entry *right = e->right;
  57
  58     if (!e->parent)
  59         tree->root = right;
  60     else if (e->parent->left == e)
  61         e->parent->left = right;
  62     else
  63         e->parent->right = right;
  64
  65     e->right = right->left;
  66     if (e->right) e->right->parent = e;
  67     right->left = e;
  68     right->parent = e->parent;
  69     e->parent = right;
  70 }
  71
  72 static inline void rb_rotate_right(struct rb_tree *tree, struct rb_entry *e)
  73 {
  74     struct rb_entry *left = e->left;
  75
  76     if (!e->parent)
  77         tree->root = left;
  78     else if (e->parent->left == e)
  79         e->parent->left = left;
  80     else
  81         e->parent->right = left;
  82
  83     e->left = left->right;
  84     if (e->left) e->left->parent = e;
  85     left->right = e;
  86     left->parent = e->parent;
  87     e->parent = left;
  88 }
  89
  90 static inline void rb_flip_color(struct rb_entry *entry)
  91 {
  92     entry->flags ^= RB_FLAG_RED;
  93     entry->left->flags ^= RB_FLAG_RED;
  94     entry->right->flags ^= RB_FLAG_RED;
  95 }
  96
  97 static inline struct rb_entry *rb_head(struct rb_entry *iter)
  98 {
  99     if (!iter) return NULL;
 100     while (iter->left) iter = iter->left;
 101     return iter;
 102 }
 103
 104 static inline struct rb_entry *rb_tail(struct rb_entry *iter)
 105 {
 106     if (!iter) return NULL;
 107     while (iter->right) iter = iter->right;
 108     return iter;
 109 }
 110
 111 static inline struct rb_entry *rb_next(struct rb_entry *iter)
 112 {
 113     if (iter->right) return rb_head(iter->right);
 114     while (iter->parent && iter->parent->right == iter) iter = iter->parent;
 115     return iter->parent;
 116 }
 117
 118 static inline struct rb_entry *rb_prev(struct rb_entry *iter)
 119 {
 120     if (iter->left) return rb_tail(iter->left);
 121     while (iter->parent && iter->parent->left == iter) iter = iter->parent;
 122     return iter->parent;
 123 }
 124
 125 static inline struct rb_entry *rb_postorder_head(struct rb_entry *iter)
 126 {
 127     if (!iter) return NULL;
 128
 129     for (;;) {
 130         while (iter->left) iter = iter->left;
 131         if (!iter->right) return iter;
 132         iter = iter->right;
 133     }
 134 }
 135
 136 static inline struct rb_entry *rb_postorder_next(struct rb_entry *iter)
 137 {
 138     if (!iter->parent) return NULL;
 139     if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
 140     return rb_postorder_head(iter->parent->right);
 141 }
 142
 143 /* iterate through the tree */
 144 #define RB_FOR_EACH(cursor, tree) \
 145     for ((cursor) = rb_head((tree)->root); (cursor); (cursor) = rb_next(cursor))
 146
 147 /* iterate through the tree using a tree entry */
 148 #define RB_FOR_EACH_ENTRY(elem, tree, type, field) \
 149     for ((elem) = RB_ENTRY_VALUE(rb_head((tree)->root), type, field); \
 150          (elem) != RB_ENTRY_VALUE(0, type, field); \
 151          (elem) = RB_ENTRY_VALUE(rb_next(&elem->field), type, field))
 152
 153 /* iterate through the tree using using postorder, making it safe to free the entry */
 154 #define RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree) \
 155     for ((cursor) = rb_postorder_head((tree)->root); \
 156          (cursor) && (((cursor2) = rb_postorder_next(cursor)) || 1); \
 157          (cursor) = (cursor2))
 158
 159 /* iterate through the tree using a tree entry and postorder, making it safe to free the entry */
 160 #define RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field) \
 161     for ((elem) = RB_ENTRY_VALUE(rb_postorder_head((tree)->root), type, field); \
 162          (elem) != RB_ENTRY_VALUE(0, type, field) \
 163              && (((elem2) = RB_ENTRY_VALUE(rb_postorder_next(&(elem)->field), type, field)) || 1); \
 164          (elem) = (elem2))
 165
 166
 167 static inline void rb_postorder(struct rb_tree *tree, rb_traverse_func *callback, void *context)
 168 {
 169     struct rb_entry *iter, *next;
 170     RB_FOR_EACH_DESTRUCTOR(iter, next, tree) callback(iter, context);
 171 }
 172
 173 static inline void rb_init(struct rb_tree *tree, rb_compare_func compare)
 174 {
 175     tree->compare = compare;
 176     tree->root = NULL;
 177 }
 178
 179 static inline void rb_for_each_entry(struct rb_tree *tree, rb_traverse_func *callback, void *context)
 180 {
 181     struct rb_entry *iter;
 182     RB_FOR_EACH(iter, tree) callback(iter, context);
 183 }
 184
 185 static inline void rb_destroy(struct rb_tree *tree, rb_traverse_func *callback, void *context)
 186 {
 187     /* Note that we use postorder here because the callback will likely free the entry. */
 188     if (callback) rb_postorder(tree, callback, context);
 189     tree->root = NULL;
 190 }
 191
 192 static inline struct rb_entry *rb_get(const struct rb_tree *tree, const void *key)
 193 {
 194     struct rb_entry *entry = tree->root;
 195     while (entry)
 196     {
 197         int c = tree->compare(key, entry);
 198         if (!c) return entry;
 199         entry = c < 0 ? entry->left : entry->right;
 200     }
 201     return NULL;
 202 }
 203
 204 static inline int rb_put(struct rb_tree *tree, const void *key, struct rb_entry *entry)
 205 {
 206     struct rb_entry **iter = &tree->root, *parent = tree->root;
 207
 208     while (*iter)
 209     {
 210         int c;
 211
 212         parent = *iter;
 213         c = tree->compare(key, parent);
 214         if (!c) return -1;
 215         else if (c < 0) iter = &parent->left;
 216         else iter = &parent->right;
 217     }
 218
 219     entry->flags = RB_FLAG_RED;
 220     entry->parent = parent;
 221     entry->left = NULL;
 222     entry->right = NULL;
 223     *iter = entry;
 224
 225     while (rb_is_red(entry->parent))
 226     {
 227         if (entry->parent == entry->parent->parent->left)
 228         {
 229             if (rb_is_red(entry->parent->parent->right))
 230             {
 231                 rb_flip_color(entry->parent->parent);
 232                 entry = entry->parent->parent;
 233             }
 234             else
 235             {
 236                 if (entry == entry->parent->right)
 237                 {
 238                     entry = entry->parent;
 239                     rb_rotate_left(tree, entry);
 240                 }
 241                 entry->parent->flags &= ~RB_FLAG_RED;
 242                 entry->parent->parent->flags |= RB_FLAG_RED;
 243                 rb_rotate_right(tree, entry->parent->parent);
 244             }
 245         }
 246         else
 247         {
 248             if (rb_is_red(entry->parent->parent->left))
 249             {
 250                 rb_flip_color(entry->parent->parent);
 251                 entry = entry->parent->parent;
 252             }
 253             else
 254             {
 255                 if (entry == entry->parent->left)
 256                 {
 257                     entry = entry->parent;
 258                     rb_rotate_right(tree, entry);
 259                 }
 260                 entry->parent->flags &= ~RB_FLAG_RED;
 261                 entry->parent->parent->flags |= RB_FLAG_RED;
 262                 rb_rotate_left(tree, entry->parent->parent);
 263             }
 264         }
 265     }
 266
 267     tree->root->flags &= ~RB_FLAG_RED;
 268
 269     return 0;
 270 }
 271
 272 static inline void rb_remove(struct rb_tree *tree, struct rb_entry *entry)
 273 {
 274     struct rb_entry *iter, *child, *parent, *w;
 275     int need_fixup;
 276
 277     if (entry->right && entry->left)
 278         for(iter = entry->right; iter->left; iter = iter->left);
 279     else
 280         iter = entry;
 281
 282     child = iter->left ? iter->left : iter->right;
 283
 284     if (!iter->parent)
 285         tree->root = child;
 286     else if (iter == iter->parent->left)
 287         iter->parent->left = child;
 288     else
 289         iter->parent->right = child;
 290
 291     if (child) child->parent = iter->parent;
 292     parent = iter->parent;
 293
 294     need_fixup = !rb_is_red(iter);
 295
 296     if (entry != iter)
 297     {
 298         *iter = *entry;
 299         if (!iter->parent)
 300             tree->root = iter;
 301         else if (entry == iter->parent->left)
 302             iter->parent->left = iter;
 303         else
 304             iter->parent->right = iter;
 305
 306         if (iter->right) iter->right->parent = iter;
 307         if (iter->left)  iter->left->parent = iter;
 308         if (parent == entry) parent = iter;
 309     }
 310
 311     if (need_fixup)
 312     {
 313         while (parent && !rb_is_red(child))
 314         {
 315             if (child == parent->left)
 316             {
 317                 w = parent->right;
 318                 if (rb_is_red(w))
 319                 {
 320                     w->flags &= ~RB_FLAG_RED;
 321                     parent->flags |= RB_FLAG_RED;
 322                     rb_rotate_left(tree, parent);
 323                     w = parent->right;
 324                 }
 325                 if (rb_is_red(w->left) || rb_is_red(w->right))
 326                 {
 327                     if (!rb_is_red(w->right))
 328                     {
 329                         w->left->flags &= ~RB_FLAG_RED;
 330                         w->flags |= RB_FLAG_RED;
 331                         rb_rotate_right(tree, w);
 332                         w = parent->right;
 333                     }
 334                     w->flags = (w->flags & ~RB_FLAG_RED) | (parent->flags & RB_FLAG_RED);
 335                     parent->flags &= ~RB_FLAG_RED;
 336                     if (w->right)
 337                         w->right->flags &= ~RB_FLAG_RED;
 338                     rb_rotate_left(tree, parent);
 339                     child = NULL;
 340                     break;
 341                 }
 342             }
 343             else
 344             {
 345                 w = parent->left;
 346                 if (rb_is_red(w))
 347                 {
 348                     w->flags &= ~RB_FLAG_RED;
 349                     parent->flags |= RB_FLAG_RED;
 350                     rb_rotate_right(tree, parent);
 351                     w = parent->left;
 352                 }
 353                 if (rb_is_red(w->left) || rb_is_red(w->right))
 354                 {
 355                     if (!rb_is_red(w->left))
 356                     {
 357                         w->right->flags &= ~RB_FLAG_RED;
 358                         w->flags |= RB_FLAG_RED;
 359                         rb_rotate_left(tree, w);
 360                         w = parent->left;
 361                     }
 362                     w->flags = (w->flags & ~RB_FLAG_RED) | (parent->flags & RB_FLAG_RED);
 363                     parent->flags &= ~RB_FLAG_RED;
 364                     if (w->left)
 365                         w->left->flags &= ~RB_FLAG_RED;
 366                     rb_rotate_right(tree, parent);
 367                     child = NULL;
 368                     break;
 369                 }
 370             }
 371             w->flags |= RB_FLAG_RED;
 372             child = parent;
 373             parent = child->parent;
 374         }
 375         if (child) child->flags &= ~RB_FLAG_RED;
 376     }
 377
 378     if (tree->root) tree->root->flags &= ~RB_FLAG_RED;
 379 }
 380
 381 static inline void rb_remove_key(struct rb_tree *tree, const void *key)
 382 {
 383     struct rb_entry *entry = rb_get(tree, key);
 384     if (entry) rb_remove(tree, entry);
 385 }
 386
 387 static inline void rb_replace(struct rb_tree *tree, struct rb_entry *dst, struct rb_entry *src)
 388 {
 389     if (!(src->parent = dst->parent))
 390         tree->root = src;
 391     else if (dst->parent->left == dst)
 392         dst->parent->left = src;
 393     else
 394         dst->parent->right = src;
 395
 396     if ((src->left = dst->left))
 397         src->left->parent = src;
 398     if ((src->right = dst->right))
 399         src->right->parent = src;
 400     src->flags = dst->flags;
 401 }
 402
 403 /* old names for backwards compatibility */
 404 #define wine_rb_entry rb_entry
 405 #define wine_rb_tree rb_tree
 406 #define wine_rb_init rb_init
 407 #define wine_rb_for_each_entry rb_for_each_entry
 408 #define wine_rb_destroy rb_destroy
 409 #define wine_rb_get rb_get
 410 #define wine_rb_put rb_put
 411 #define wine_rb_remove rb_remove
 412 #define wine_rb_remove_key rb_remove_key
 413 #define wine_rb_replace rb_replace
 414 #define WINE_RB_ENTRY_VALUE RB_ENTRY_VALUE
 415 #define WINE_RB_FOR_EACH_ENTRY RB_FOR_EACH_ENTRY
 416 #define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR RB_FOR_EACH_ENTRY_DESTRUCTOR
 417
 418 #endif  /* __WINE_WINE_RBTREE_H */