include/wine/rbtree.h

   1 /*
   2  * Red-black search tree support
   3  *
   4  * Copyright 2009 Henri Verbeet
   5  * Copyright 2009 Andrew Riedi
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  20  */
  21
  22 #ifndef __WINE_WINE_RBTREE_H
  23 #define __WINE_WINE_RBTREE_H
  24
  25 #define WINE_RB_ENTRY_VALUE(element, type, field) \
  26     ((type *)((char *)(element) - offsetof(type, field)))
  27
  28 struct wine_rb_entry
  29 {
  30     struct wine_rb_entry *left;
  31     struct wine_rb_entry *right;
  32     unsigned int flags;
  33 };
  34
  35 struct wine_rb_stack
  36 {
  37     struct wine_rb_entry ***entries;
  38     size_t count;
  39     size_t size;
  40 };
  41
  42 struct wine_rb_functions
  43 {
  44     void *(*alloc)(size_t size);
  45     void *(*realloc)(void *ptr, size_t size);
  46     void (*free)(void *ptr);
  47     int (*compare)(const void *key, const struct wine_rb_entry *entry);
  48 };
  49
  50 struct wine_rb_tree
  51 {
  52     const struct wine_rb_functions *functions;
  53     struct wine_rb_entry *root;
  54     struct wine_rb_stack stack;
  55 };
  56
  57 typedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *context);
  58
  59 #define WINE_RB_FLAG_RED                0x1
  60 #define WINE_RB_FLAG_STOP               0x2
  61 #define WINE_RB_FLAG_TRAVERSED_LEFT     0x4
  62 #define WINE_RB_FLAG_TRAVERSED_RIGHT    0x8
  63
  64 static inline void wine_rb_stack_clear(struct wine_rb_stack *stack)
  65 {
  66     stack->count = 0;
  67 }
  68
  69 static inline void wine_rb_stack_push(struct wine_rb_stack *stack, struct wine_rb_entry **entry)
  70 {
  71     stack->entries[stack->count++] = entry;
  72 }
  73
  74 static inline int wine_rb_ensure_stack_size(struct wine_rb_tree *tree, size_t size)
  75 {
  76     struct wine_rb_stack *stack = &tree->stack;
  77
  78     if (size > stack->size)
  79     {
  80         size_t new_size = stack->size << 1;
  81         struct wine_rb_entry ***new_entries = tree->functions->realloc(stack->entries,
  82                 new_size * sizeof(*stack->entries));
  83
  84         if (!new_entries) return -1;
  85
  86         stack->entries = new_entries;
  87         stack->size = new_size;
  88     }
  89
  90     return 0;
  91 }
  92
  93 static inline int wine_rb_is_red(struct wine_rb_entry *entry)
  94 {
  95     return entry && (entry->flags & WINE_RB_FLAG_RED);
  96 }
  97
  98 static inline void wine_rb_rotate_left(struct wine_rb_entry **entry)
  99 {
 100     struct wine_rb_entry *e = *entry;
 101     struct wine_rb_entry *right = e->right;
 102
 103     e->right = right->left;
 104     right->left = e;
 105     right->flags &= ~WINE_RB_FLAG_RED;
 106     right->flags |= e->flags & WINE_RB_FLAG_RED;
 107     e->flags |= WINE_RB_FLAG_RED;
 108     *entry = right;
 109 }
 110
 111 static inline void wine_rb_rotate_right(struct wine_rb_entry **entry)
 112 {
 113     struct wine_rb_entry *e = *entry;
 114     struct wine_rb_entry *left = e->left;
 115
 116     e->left = left->right;
 117     left->right = e;
 118     left->flags &= ~WINE_RB_FLAG_RED;
 119     left->flags |= e->flags & WINE_RB_FLAG_RED;
 120     e->flags |= WINE_RB_FLAG_RED;
 121     *entry = left;
 122 }
 123
 124 static inline void wine_rb_flip_color(struct wine_rb_entry *entry)
 125 {
 126     entry->flags ^= WINE_RB_FLAG_RED;
 127     entry->left->flags ^= WINE_RB_FLAG_RED;
 128     entry->right->flags ^= WINE_RB_FLAG_RED;
 129 }
 130
 131 static inline void wine_rb_fixup(struct wine_rb_stack *stack)
 132 {
 133     while (stack->count)
 134     {
 135         struct wine_rb_entry **entry = stack->entries[stack->count - 1];
 136
 137         if ((*entry)->flags & WINE_RB_FLAG_STOP)
 138         {
 139             (*entry)->flags &= ~WINE_RB_FLAG_STOP;
 140             return;
 141         }
 142
 143         if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(entry);
 144         if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(entry);
 145         if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->right)) wine_rb_flip_color(*entry);
 146         --stack->count;
 147     }
 148 }
 149
 150 static inline void wine_rb_move_red_left(struct wine_rb_entry **entry)
 151 {
 152     wine_rb_flip_color(*entry);
 153     if (wine_rb_is_red((*entry)->right->left))
 154     {
 155         wine_rb_rotate_right(&(*entry)->right);
 156         wine_rb_rotate_left(entry);
 157         wine_rb_flip_color(*entry);
 158     }
 159 }
 160
 161 static inline void wine_rb_move_red_right(struct wine_rb_entry **entry)
 162 {
 163     wine_rb_flip_color(*entry);
 164     if (wine_rb_is_red((*entry)->left->left))
 165     {
 166         wine_rb_rotate_right(entry);
 167         wine_rb_flip_color(*entry);
 168     }
 169 }
 170
 171 static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 172 {
 173     struct wine_rb_entry **entry;
 174
 175     if (!tree->root) return;
 176
 177     for (entry = &tree->root;;)
 178     {
 179         struct wine_rb_entry *e = *entry;
 180
 181         if (e->left && !(e->flags & WINE_RB_FLAG_TRAVERSED_LEFT))
 182         {
 183             wine_rb_stack_push(&tree->stack, entry);
 184             e->flags |= WINE_RB_FLAG_TRAVERSED_LEFT;
 185             entry = &e->left;
 186             continue;
 187         }
 188
 189         if (e->right && !(e->flags & WINE_RB_FLAG_TRAVERSED_RIGHT))
 190         {
 191             wine_rb_stack_push(&tree->stack, entry);
 192             e->flags |= WINE_RB_FLAG_TRAVERSED_RIGHT;
 193             entry = &e->right;
 194             continue;
 195         }
 196
 197         e->flags &= ~(WINE_RB_FLAG_TRAVERSED_LEFT | WINE_RB_FLAG_TRAVERSED_RIGHT);
 198         callback(e, context);
 199
 200         if (!tree->stack.count) break;
 201         entry = tree->stack.entries[--tree->stack.count];
 202     }
 203 }
 204
 205 static inline int wine_rb_init(struct wine_rb_tree *tree, const struct wine_rb_functions *functions)
 206 {
 207     tree->functions = functions;
 208     tree->root = NULL;
 209
 210     tree->stack.entries = functions->alloc(16 * sizeof(*tree->stack.entries));
 211     if (!tree->stack.entries) return -1;
 212     tree->stack.size = 16;
 213     tree->stack.count = 0;
 214
 215     return 0;
 216 }
 217
 218 static inline void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 219 {
 220     wine_rb_postorder(tree, callback, context);
 221 }
 222
 223 static inline void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 224 {
 225     /* Note that we use postorder here because the callback will likely free the entry. */
 226     if (callback) wine_rb_postorder(tree, callback, context);
 227     tree->root = NULL;
 228 }
 229
 230 static inline void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 231 {
 232     wine_rb_clear(tree, callback, context);
 233     tree->functions->free(tree->stack.entries);
 234 }
 235
 236 static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)
 237 {
 238     struct wine_rb_entry *entry = tree->root;
 239     while (entry)
 240     {
 241         int c = tree->functions->compare(key, entry);
 242         if (!c) return entry;
 243         entry = c < 0 ? entry->left : entry->right;
 244     }
 245     return NULL;
 246 }
 247
 248 static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
 249 {
 250     struct wine_rb_entry **parent = &tree->root;
 251     size_t black_height = 1;
 252
 253     while (*parent)
 254     {
 255         int c;
 256
 257         if (!wine_rb_is_red(*parent)) ++black_height;
 258
 259         wine_rb_stack_push(&tree->stack, parent);
 260
 261         c = tree->functions->compare(key, *parent);
 262         if (!c)
 263         {
 264             wine_rb_stack_clear(&tree->stack);
 265             return -1;
 266         }
 267         else if (c < 0) parent = &(*parent)->left;
 268         else parent = &(*parent)->right;
 269     }
 270
 271     /* After insertion, the path length to any node should be <= (black_height + 1) * 2. */
 272     if (wine_rb_ensure_stack_size(tree, black_height << 1) == -1)
 273     {
 274         wine_rb_stack_clear(&tree->stack);
 275         return -1;
 276     }
 277
 278     entry->flags = WINE_RB_FLAG_RED;
 279     entry->left = NULL;
 280     entry->right = NULL;
 281     *parent = entry;
 282
 283     wine_rb_fixup(&tree->stack);
 284     tree->root->flags &= ~WINE_RB_FLAG_RED;
 285
 286     return 0;
 287 }
 288
 289 static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key)
 290 {
 291     struct wine_rb_entry **entry = &tree->root;
 292
 293     while (*entry)
 294     {
 295         if (tree->functions->compare(key, *entry) < 0)
 296         {
 297             wine_rb_stack_push(&tree->stack, entry);
 298             if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry);
 299             entry = &(*entry)->left;
 300         }
 301         else
 302         {
 303             if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(entry);
 304             if (!tree->functions->compare(key, *entry) && !(*entry)->right)
 305             {
 306                 *entry = NULL;
 307                 break;
 308             }
 309             if (!wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->right->left))
 310                 wine_rb_move_red_right(entry);
 311             if (!tree->functions->compare(key, *entry))
 312             {
 313                 struct wine_rb_entry **e = &(*entry)->right;
 314                 struct wine_rb_entry *m = *e;
 315                 while (m->left) m = m->left;
 316
 317                 wine_rb_stack_push(&tree->stack, entry);
 318                 (*entry)->flags |= WINE_RB_FLAG_STOP;
 319
 320                 while ((*e)->left)
 321                 {
 322                     wine_rb_stack_push(&tree->stack, e);
 323                     if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(e);
 324                     e = &(*e)->left;
 325                 }
 326                 *e = NULL;
 327                 wine_rb_fixup(&tree->stack);
 328
 329                 *m = **entry;
 330                 *entry = m;
 331
 332                 break;
 333             }
 334             else
 335             {
 336                 wine_rb_stack_push(&tree->stack, entry);
 337                 entry = &(*entry)->right;
 338             }
 339         }
 340     }
 341
 342     wine_rb_fixup(&tree->stack);
 343     if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
 344 }
 345
 346 #endif  /* __WINE_WINE_RBTREE_H */