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