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) - FIELD_OFFSET(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_destroy(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
 228     tree->root = NULL;
 229     tree->functions->free(tree->stack.entries);
 230 }
 231
 232 static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)
 233 {
 234     struct wine_rb_entry *entry = tree->root;
 235     while (entry)
 236     {
 237         int c = tree->functions->compare(key, entry);
 238         if (!c) return entry;
 239         entry = c < 0 ? entry->left : entry->right;
 240     }
 241     return NULL;
 242 }
 243
 244 static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
 245 {
 246     struct wine_rb_entry **parent = &tree->root;
 247     size_t black_height = 1;
 248
 249     while (*parent)
 250     {
 251         int c;
 252
 253         if (!wine_rb_is_red(*parent)) ++black_height;
 254
 255         wine_rb_stack_push(&tree->stack, parent);
 256
 257         c = tree->functions->compare(key, *parent);
 258         if (!c)
 259         {
 260             wine_rb_stack_clear(&tree->stack);
 261             return -1;
 262         }
 263         else if (c < 0) parent = &(*parent)->left;
 264         else parent = &(*parent)->right;
 265     }
 266
 267     /* After insertion, the path length to any node should be <= (black_height + 1) * 2. */
 268     if (wine_rb_ensure_stack_size(tree, black_height << 1) == -1)
 269     {
 270         wine_rb_stack_clear(&tree->stack);
 271         return -1;
 272     }
 273
 274     entry->flags = WINE_RB_FLAG_RED;
 275     entry->left = NULL;
 276     entry->right = NULL;
 277     *parent = entry;
 278
 279     wine_rb_fixup(&tree->stack);
 280     tree->root->flags &= ~WINE_RB_FLAG_RED;
 281
 282     return 0;
 283 }
 284
 285 static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key)
 286 {
 287     struct wine_rb_entry **entry = &tree->root;
 288
 289     while (*entry)
 290     {
 291         if (tree->functions->compare(key, *entry) < 0)
 292         {
 293             wine_rb_stack_push(&tree->stack, entry);
 294             if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry);
 295             entry = &(*entry)->left;
 296         }
 297         else
 298         {
 299             if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(entry);
 300             if (!tree->functions->compare(key, *entry) && !(*entry)->right)
 301             {
 302                 *entry = NULL;
 303                 break;
 304             }
 305             if (!wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->right->left))
 306                 wine_rb_move_red_right(entry);
 307             if (!tree->functions->compare(key, *entry))
 308             {
 309                 struct wine_rb_entry **e = &(*entry)->right;
 310                 struct wine_rb_entry *m = *e;
 311                 while (m->left) m = m->left;
 312
 313                 wine_rb_stack_push(&tree->stack, entry);
 314                 (*entry)->flags |= WINE_RB_FLAG_STOP;
 315
 316                 while ((*e)->left)
 317                 {
 318                     wine_rb_stack_push(&tree->stack, e);
 319                     if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(e);
 320                     e = &(*e)->left;
 321                 }
 322                 *e = NULL;
 323                 wine_rb_fixup(&tree->stack);
 324
 325                 *m = **entry;
 326                 *entry = m;
 327
 328                 break;
 329             }
 330             else
 331             {
 332                 wine_rb_stack_push(&tree->stack, entry);
 333                 entry = &(*entry)->right;
 334             }
 335         }
 336     }
 337
 338     wine_rb_fixup(&tree->stack);
 339     if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
 340 }
 341
 342 #endif  /* __WINE_WINE_RBTREE_H */