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 WINE_RB_ENTRY_VALUE(element, type, field) \
  27     ((type *)((char *)(element) - offsetof(type, field)))
  28
  29 struct wine_rb_entry
  30 {
  31     struct wine_rb_entry *parent;
  32     struct wine_rb_entry *left;
  33     struct wine_rb_entry *right;
  34     unsigned int flags;
  35 };
  36
  37 typedef int (*wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry);
  38
  39 struct wine_rb_tree
  40 {
  41     wine_rb_compare_func_t compare;
  42     struct wine_rb_entry *root;
  43 };
  44
  45 typedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *context);
  46
  47 #define WINE_RB_FLAG_RED                0x1
  48
  49 static inline int wine_rb_is_red(struct wine_rb_entry *entry)
  50 {
  51     return entry && (entry->flags & WINE_RB_FLAG_RED);
  52 }
  53
  54 static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
  55 {
  56     struct wine_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 wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
  73 {
  74     struct wine_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 wine_rb_flip_color(struct wine_rb_entry *entry)
  91 {
  92     entry->flags ^= WINE_RB_FLAG_RED;
  93     entry->left->flags ^= WINE_RB_FLAG_RED;
  94     entry->right->flags ^= WINE_RB_FLAG_RED;
  95 }
  96
  97 static inline struct wine_rb_entry *wine_rb_head(struct wine_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 wine_rb_entry *wine_rb_next(struct wine_rb_entry *iter)
 105 {
 106     if (iter->right) return wine_rb_head(iter->right);
 107     while (iter->parent && iter->parent->right == iter) iter = iter->parent;
 108     return iter->parent;
 109 }
 110
 111 static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter)
 112 {
 113     if (!iter) return NULL;
 114
 115     for (;;) {
 116         while (iter->left) iter = iter->left;
 117         if (!iter->right) return iter;
 118         iter = iter->right;
 119     }
 120 }
 121
 122 static inline struct wine_rb_entry *wine_rb_postorder_next(struct wine_rb_entry *iter)
 123 {
 124     if (!iter->parent) return NULL;
 125     if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
 126     return wine_rb_postorder_head(iter->parent->right);
 127 }
 128
 129 /* iterate through the tree */
 130 #define WINE_RB_FOR_EACH(cursor, tree) \
 131     for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))
 132
 133 /* iterate through the tree using a tree entry */
 134 #define WINE_RB_FOR_EACH_ENTRY(elem, tree, type, field) \
 135     for ((elem) = WINE_RB_ENTRY_VALUE(wine_rb_head((tree)->root), type, field); \
 136          &(elem)->field; \
 137          (elem) = WINE_RB_ENTRY_VALUE(wine_rb_next(&elem->field), type, field))
 138
 139 /* iterate through the tree using using postorder, making it safe to free the entry */
 140 #define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree) \
 141     for ((cursor) = wine_rb_postorder_head((tree)->root); \
 142          (cursor) && (((cursor2) = wine_rb_postorder_next(cursor)) || 1); \
 143          (cursor) = (cursor2))
 144
 145 /* iterate through the tree using a tree entry and postorder, making it safe to free the entry */
 146 #define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field) \
 147     for ((elem) = WINE_RB_ENTRY_VALUE(wine_rb_postorder_head((tree)->root), type, field); \
 148          &(elem)->field \
 149              && (((elem2) = WINE_RB_ENTRY_VALUE(wine_rb_postorder_next(&(elem)->field), type, field)) || 1); \
 150          (elem) = (elem2))
 151
 152
 153 static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 154 {
 155     struct wine_rb_entry *iter, *next;
 156     WINE_RB_FOR_EACH_DESTRUCTOR(iter, next, tree) callback(iter, context);
 157 }
 158
 159 static inline void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t compare)
 160 {
 161     tree->compare = compare;
 162     tree->root = NULL;
 163 }
 164
 165 static inline void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 166 {
 167     struct wine_rb_entry *iter;
 168     WINE_RB_FOR_EACH(iter, tree) callback(iter, context);
 169 }
 170
 171 static inline void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 172 {
 173     /* Note that we use postorder here because the callback will likely free the entry. */
 174     if (callback) wine_rb_postorder(tree, callback, context);
 175     tree->root = NULL;
 176 }
 177
 178 static inline void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 179 {
 180     wine_rb_clear(tree, callback, context);
 181 }
 182
 183 static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)
 184 {
 185     struct wine_rb_entry *entry = tree->root;
 186     while (entry)
 187     {
 188         int c = tree->compare(key, entry);
 189         if (!c) return entry;
 190         entry = c < 0 ? entry->left : entry->right;
 191     }
 192     return NULL;
 193 }
 194
 195 static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
 196 {
 197     struct wine_rb_entry **iter = &tree->root, *parent = tree->root;
 198
 199     while (*iter)
 200     {
 201         int c;
 202
 203         parent = *iter;
 204         c = tree->compare(key, parent);
 205         if (!c) return -1;
 206         else if (c < 0) iter = &parent->left;
 207         else iter = &parent->right;
 208     }
 209
 210     entry->flags = WINE_RB_FLAG_RED;
 211     entry->parent = parent;
 212     entry->left = NULL;
 213     entry->right = NULL;
 214     *iter = entry;
 215
 216     while (wine_rb_is_red(entry->parent))
 217     {
 218         if (entry->parent == entry->parent->parent->left)
 219         {
 220             if (wine_rb_is_red(entry->parent->parent->right))
 221             {
 222                 wine_rb_flip_color(entry->parent->parent);
 223                 entry = entry->parent->parent;
 224             }
 225             else
 226             {
 227                 if (entry == entry->parent->right)
 228                 {
 229                     entry = entry->parent;
 230                     wine_rb_rotate_left(tree, entry);
 231                 }
 232                 entry->parent->flags &= ~WINE_RB_FLAG_RED;
 233                 entry->parent->parent->flags |= WINE_RB_FLAG_RED;
 234                 wine_rb_rotate_right(tree, entry->parent->parent);
 235             }
 236         }
 237         else
 238         {
 239             if (wine_rb_is_red(entry->parent->parent->left))
 240             {
 241                 wine_rb_flip_color(entry->parent->parent);
 242                 entry = entry->parent->parent;
 243             }
 244             else
 245             {
 246                 if (entry == entry->parent->left)
 247                 {
 248                     entry = entry->parent;
 249                     wine_rb_rotate_right(tree, entry);
 250                 }
 251                 entry->parent->flags &= ~WINE_RB_FLAG_RED;
 252                 entry->parent->parent->flags |= WINE_RB_FLAG_RED;
 253                 wine_rb_rotate_left(tree, entry->parent->parent);
 254             }
 255         }
 256     }
 257
 258     tree->root->flags &= ~WINE_RB_FLAG_RED;
 259
 260     return 0;
 261 }
 262
 263 static inline void wine_rb_remove(struct wine_rb_tree *tree, struct wine_rb_entry *entry)
 264 {
 265     struct wine_rb_entry *iter, *child, *parent, *w;
 266     int need_fixup;
 267
 268     if (entry->right && entry->left)
 269         for(iter = entry->right; iter->left; iter = iter->left);
 270     else
 271         iter = entry;
 272
 273     child = iter->left ? iter->left : iter->right;
 274
 275     if (!iter->parent)
 276         tree->root = child;
 277     else if (iter == iter->parent->left)
 278         iter->parent->left = child;
 279     else
 280         iter->parent->right = child;
 281
 282     if (child) child->parent = iter->parent;
 283     parent = iter->parent;
 284
 285     need_fixup = !wine_rb_is_red(iter);
 286
 287     if (entry != iter)
 288     {
 289         *iter = *entry;
 290         if (!iter->parent)
 291             tree->root = iter;
 292         else if (entry == iter->parent->left)
 293             iter->parent->left = iter;
 294         else
 295             iter->parent->right = iter;
 296
 297         if (iter->right) iter->right->parent = iter;
 298         if (iter->left)  iter->left->parent = iter;
 299         if (parent == entry) parent = iter;
 300     }
 301
 302     if (need_fixup)
 303     {
 304         while (parent && !wine_rb_is_red(child))
 305         {
 306             if (child == parent->left)
 307             {
 308                 w = parent->right;
 309                 if (wine_rb_is_red(w))
 310                 {
 311                     w->flags &= ~WINE_RB_FLAG_RED;
 312                     parent->flags |= WINE_RB_FLAG_RED;
 313                     wine_rb_rotate_left(tree, parent);
 314                     w = parent->right;
 315                 }
 316                 if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
 317                 {
 318                     if (!wine_rb_is_red(w->right))
 319                     {
 320                         w->left->flags &= ~WINE_RB_FLAG_RED;
 321                         w->flags |= WINE_RB_FLAG_RED;
 322                         wine_rb_rotate_right(tree, w);
 323                         w = parent->right;
 324                     }
 325                     w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
 326                     parent->flags &= ~WINE_RB_FLAG_RED;
 327                     if (w->right)
 328                         w->right->flags &= ~WINE_RB_FLAG_RED;
 329                     wine_rb_rotate_left(tree, parent);
 330                     child = NULL;
 331                     break;
 332                 }
 333             }
 334             else
 335             {
 336                 w = parent->left;
 337                 if (wine_rb_is_red(w))
 338                 {
 339                     w->flags &= ~WINE_RB_FLAG_RED;
 340                     parent->flags |= WINE_RB_FLAG_RED;
 341                     wine_rb_rotate_right(tree, parent);
 342                     w = parent->left;
 343                 }
 344                 if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
 345                 {
 346                     if (!wine_rb_is_red(w->left))
 347                     {
 348                         w->right->flags &= ~WINE_RB_FLAG_RED;
 349                         w->flags |= WINE_RB_FLAG_RED;
 350                         wine_rb_rotate_left(tree, w);
 351                         w = parent->left;
 352                     }
 353                     w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
 354                     parent->flags &= ~WINE_RB_FLAG_RED;
 355                     if (w->left)
 356                         w->left->flags &= ~WINE_RB_FLAG_RED;
 357                     wine_rb_rotate_right(tree, parent);
 358                     child = NULL;
 359                     break;
 360                 }
 361             }
 362             w->flags |= WINE_RB_FLAG_RED;
 363             child = parent;
 364             parent = child->parent;
 365         }
 366         if (child) child->flags &= ~WINE_RB_FLAG_RED;
 367     }
 368
 369     if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
 370 }
 371
 372 static inline void wine_rb_remove_key(struct wine_rb_tree *tree, const void *key)
 373 {
 374     struct wine_rb_entry *entry = wine_rb_get(tree, key);
 375     if (entry) wine_rb_remove(tree, entry);
 376 }
 377
 378 #endif  /* __WINE_WINE_RBTREE_H */