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_postorder_head(struct wine_rb_entry *iter)
  98 {
  99     if (!iter) return NULL;
 100
 101     for (;;) {
 102         while (iter->left) iter = iter->left;
 103         if (!iter->right) return iter;
 104         iter = iter->right;
 105     }
 106 }
 107
 108 static inline struct wine_rb_entry *wine_rb_postorder_next(struct wine_rb_entry *iter)
 109 {
 110     if (!iter->parent) return NULL;
 111     if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
 112     return wine_rb_postorder_head(iter->parent->right);
 113 }
 114
 115 static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 116 {
 117     struct wine_rb_entry *iter, *next;
 118
 119     for (iter = wine_rb_postorder_head(tree->root); iter; iter = next)
 120     {
 121         next = wine_rb_postorder_next(iter);
 122         callback(iter, context);
 123     }
 124 }
 125
 126 static inline void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t compare)
 127 {
 128     tree->compare = compare;
 129     tree->root = NULL;
 130 }
 131
 132 static inline void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 133 {
 134     wine_rb_postorder(tree, callback, context);
 135 }
 136
 137 static inline void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 138 {
 139     /* Note that we use postorder here because the callback will likely free the entry. */
 140     if (callback) wine_rb_postorder(tree, callback, context);
 141     tree->root = NULL;
 142 }
 143
 144 static inline void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 145 {
 146     wine_rb_clear(tree, callback, context);
 147 }
 148
 149 static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)
 150 {
 151     struct wine_rb_entry *entry = tree->root;
 152     while (entry)
 153     {
 154         int c = tree->compare(key, entry);
 155         if (!c) return entry;
 156         entry = c < 0 ? entry->left : entry->right;
 157     }
 158     return NULL;
 159 }
 160
 161 static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
 162 {
 163     struct wine_rb_entry **iter = &tree->root, *parent = tree->root;
 164
 165     while (*iter)
 166     {
 167         int c;
 168
 169         parent = *iter;
 170         c = tree->compare(key, parent);
 171         if (!c) return -1;
 172         else if (c < 0) iter = &parent->left;
 173         else iter = &parent->right;
 174     }
 175
 176     entry->flags = WINE_RB_FLAG_RED;
 177     entry->parent = parent;
 178     entry->left = NULL;
 179     entry->right = NULL;
 180     *iter = entry;
 181
 182     while (wine_rb_is_red(entry->parent))
 183     {
 184         if (entry->parent == entry->parent->parent->left)
 185         {
 186             if (wine_rb_is_red(entry->parent->parent->right))
 187             {
 188                 wine_rb_flip_color(entry->parent->parent);
 189                 entry = entry->parent->parent;
 190             }
 191             else
 192             {
 193                 if (entry == entry->parent->right)
 194                 {
 195                     entry = entry->parent;
 196                     wine_rb_rotate_left(tree, entry);
 197                 }
 198                 entry->parent->flags &= ~WINE_RB_FLAG_RED;
 199                 entry->parent->parent->flags |= WINE_RB_FLAG_RED;
 200                 wine_rb_rotate_right(tree, entry->parent->parent);
 201             }
 202         }
 203         else
 204         {
 205             if (wine_rb_is_red(entry->parent->parent->left))
 206             {
 207                 wine_rb_flip_color(entry->parent->parent);
 208                 entry = entry->parent->parent;
 209             }
 210             else
 211             {
 212                 if (entry == entry->parent->left)
 213                 {
 214                     entry = entry->parent;
 215                     wine_rb_rotate_right(tree, entry);
 216                 }
 217                 entry->parent->flags &= ~WINE_RB_FLAG_RED;
 218                 entry->parent->parent->flags |= WINE_RB_FLAG_RED;
 219                 wine_rb_rotate_left(tree, entry->parent->parent);
 220             }
 221         }
 222     }
 223
 224     tree->root->flags &= ~WINE_RB_FLAG_RED;
 225
 226     return 0;
 227 }
 228
 229 static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key)
 230 {
 231     struct wine_rb_entry *entry, *iter, *child, *parent, *w;
 232     int need_fixup;
 233
 234     if (!(entry = wine_rb_get(tree, key))) return;
 235
 236     if (entry->right && entry->left)
 237         for(iter = entry->right; iter->left; iter = iter->left);
 238     else
 239         iter = entry;
 240
 241     child = iter->left ? iter->left : iter->right;
 242
 243     if (!iter->parent)
 244         tree->root = child;
 245     else if (iter == iter->parent->left)
 246         iter->parent->left = child;
 247     else
 248         iter->parent->right = child;
 249
 250     if (child) child->parent = iter->parent;
 251     parent = iter->parent;
 252
 253     need_fixup = !wine_rb_is_red(iter);
 254
 255     if (entry != iter)
 256     {
 257         *iter = *entry;
 258         if (!iter->parent)
 259             tree->root = iter;
 260         else if (entry == iter->parent->left)
 261             iter->parent->left = iter;
 262         else
 263             iter->parent->right = iter;
 264
 265         if (iter->right) iter->right->parent = iter;
 266         if (iter->left)  iter->left->parent = iter;
 267         if (parent == entry) parent = iter;
 268     }
 269
 270     if (need_fixup)
 271     {
 272         while (parent && !wine_rb_is_red(child))
 273         {
 274             if (child == parent->left)
 275             {
 276                 w = parent->right;
 277                 if (wine_rb_is_red(w))
 278                 {
 279                     w->flags &= ~WINE_RB_FLAG_RED;
 280                     parent->flags |= WINE_RB_FLAG_RED;
 281                     wine_rb_rotate_left(tree, parent);
 282                     w = parent->right;
 283                 }
 284                 if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
 285                 {
 286                     if (!wine_rb_is_red(w->right))
 287                     {
 288                         w->left->flags &= ~WINE_RB_FLAG_RED;
 289                         w->flags |= WINE_RB_FLAG_RED;
 290                         wine_rb_rotate_right(tree, w);
 291                         w = parent->right;
 292                     }
 293                     w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
 294                     parent->flags &= ~WINE_RB_FLAG_RED;
 295                     if (w->right)
 296                         w->right->flags &= ~WINE_RB_FLAG_RED;
 297                     wine_rb_rotate_left(tree, parent);
 298                     child = NULL;
 299                     break;
 300                 }
 301             }
 302             else
 303             {
 304                 w = parent->left;
 305                 if (wine_rb_is_red(w))
 306                 {
 307                     w->flags &= ~WINE_RB_FLAG_RED;
 308                     parent->flags |= WINE_RB_FLAG_RED;
 309                     wine_rb_rotate_right(tree, parent);
 310                     w = parent->left;
 311                 }
 312                 if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
 313                 {
 314                     if (!wine_rb_is_red(w->left))
 315                     {
 316                         w->right->flags &= ~WINE_RB_FLAG_RED;
 317                         w->flags |= WINE_RB_FLAG_RED;
 318                         wine_rb_rotate_left(tree, w);
 319                         w = parent->left;
 320                     }
 321                     w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
 322                     parent->flags &= ~WINE_RB_FLAG_RED;
 323                     if (w->left)
 324                         w->left->flags &= ~WINE_RB_FLAG_RED;
 325                     wine_rb_rotate_right(tree, parent);
 326                     child = NULL;
 327                     break;
 328                 }
 329             }
 330             w->flags |= WINE_RB_FLAG_RED;
 331             child = parent;
 332             parent = child->parent;
 333         }
 334         if (child) child->flags &= ~WINE_RB_FLAG_RED;
 335     }
 336
 337     if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
 338 }
 339
 340 #endif  /* __WINE_WINE_RBTREE_H */