| /* |
| * Red-black search tree support |
| * |
| * Copyright 2009 Henri Verbeet |
| * Copyright 2009 Andrew Riedi |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Lesser General Public |
| * License as published by the Free Software Foundation; either |
| * version 2.1 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Lesser General Public License for more details. |
| * |
| * You should have received a copy of the GNU Lesser General Public |
| * License along with this library; if not, write to the Free Software |
| * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA |
| */ |
| |
| #ifndef __WINE_WINE_RBTREE_H |
| #define __WINE_WINE_RBTREE_H |
| |
| #define WINE_RB_ENTRY_VALUE(element, type, field) \ |
| ((type *)((char *)(element) - offsetof(type, field))) |
| |
| struct wine_rb_entry |
| { |
| struct wine_rb_entry *left; |
| struct wine_rb_entry *right; |
| unsigned int flags; |
| }; |
| |
| struct wine_rb_stack |
| { |
| struct wine_rb_entry ***entries; |
| size_t count; |
| size_t size; |
| }; |
| |
| struct wine_rb_functions |
| { |
| void *(*alloc)(size_t size); |
| void *(*realloc)(void *ptr, size_t size); |
| void (*free)(void *ptr); |
| int (*compare)(const void *key, const struct wine_rb_entry *entry); |
| }; |
| |
| struct wine_rb_tree |
| { |
| const struct wine_rb_functions *functions; |
| struct wine_rb_entry *root; |
| struct wine_rb_stack stack; |
| }; |
| |
| typedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *context); |
| |
| #define WINE_RB_FLAG_RED 0x1 |
| #define WINE_RB_FLAG_STOP 0x2 |
| #define WINE_RB_FLAG_TRAVERSED_LEFT 0x4 |
| #define WINE_RB_FLAG_TRAVERSED_RIGHT 0x8 |
| |
| static inline void wine_rb_stack_clear(struct wine_rb_stack *stack) |
| { |
| stack->count = 0; |
| } |
| |
| static inline void wine_rb_stack_push(struct wine_rb_stack *stack, struct wine_rb_entry **entry) |
| { |
| stack->entries[stack->count++] = entry; |
| } |
| |
| static inline int wine_rb_ensure_stack_size(struct wine_rb_tree *tree, size_t size) |
| { |
| struct wine_rb_stack *stack = &tree->stack; |
| |
| if (size > stack->size) |
| { |
| size_t new_size = stack->size << 1; |
| struct wine_rb_entry ***new_entries = tree->functions->realloc(stack->entries, |
| new_size * sizeof(*stack->entries)); |
| |
| if (!new_entries) return -1; |
| |
| stack->entries = new_entries; |
| stack->size = new_size; |
| } |
| |
| return 0; |
| } |
| |
| static inline int wine_rb_is_red(struct wine_rb_entry *entry) |
| { |
| return entry && (entry->flags & WINE_RB_FLAG_RED); |
| } |
| |
| static inline void wine_rb_rotate_left(struct wine_rb_entry **entry) |
| { |
| struct wine_rb_entry *e = *entry; |
| struct wine_rb_entry *right = e->right; |
| |
| e->right = right->left; |
| right->left = e; |
| right->flags &= ~WINE_RB_FLAG_RED; |
| right->flags |= e->flags & WINE_RB_FLAG_RED; |
| e->flags |= WINE_RB_FLAG_RED; |
| *entry = right; |
| } |
| |
| static inline void wine_rb_rotate_right(struct wine_rb_entry **entry) |
| { |
| struct wine_rb_entry *e = *entry; |
| struct wine_rb_entry *left = e->left; |
| |
| e->left = left->right; |
| left->right = e; |
| left->flags &= ~WINE_RB_FLAG_RED; |
| left->flags |= e->flags & WINE_RB_FLAG_RED; |
| e->flags |= WINE_RB_FLAG_RED; |
| *entry = left; |
| } |
| |
| static inline void wine_rb_flip_color(struct wine_rb_entry *entry) |
| { |
| entry->flags ^= WINE_RB_FLAG_RED; |
| entry->left->flags ^= WINE_RB_FLAG_RED; |
| entry->right->flags ^= WINE_RB_FLAG_RED; |
| } |
| |
| static inline void wine_rb_fixup(struct wine_rb_stack *stack) |
| { |
| while (stack->count) |
| { |
| struct wine_rb_entry **entry = stack->entries[stack->count - 1]; |
| |
| if ((*entry)->flags & WINE_RB_FLAG_STOP) |
| { |
| (*entry)->flags &= ~WINE_RB_FLAG_STOP; |
| return; |
| } |
| |
| if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(entry); |
| if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(entry); |
| if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->right)) wine_rb_flip_color(*entry); |
| --stack->count; |
| } |
| } |
| |
| static inline void wine_rb_move_red_left(struct wine_rb_entry **entry) |
| { |
| wine_rb_flip_color(*entry); |
| if (wine_rb_is_red((*entry)->right->left)) |
| { |
| wine_rb_rotate_right(&(*entry)->right); |
| wine_rb_rotate_left(entry); |
| wine_rb_flip_color(*entry); |
| } |
| } |
| |
| static inline void wine_rb_move_red_right(struct wine_rb_entry **entry) |
| { |
| wine_rb_flip_color(*entry); |
| if (wine_rb_is_red((*entry)->left->left)) |
| { |
| wine_rb_rotate_right(entry); |
| wine_rb_flip_color(*entry); |
| } |
| } |
| |
| static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) |
| { |
| struct wine_rb_entry **entry; |
| |
| if (!tree->root) return; |
| |
| for (entry = &tree->root;;) |
| { |
| struct wine_rb_entry *e = *entry; |
| |
| if (e->left && !(e->flags & WINE_RB_FLAG_TRAVERSED_LEFT)) |
| { |
| wine_rb_stack_push(&tree->stack, entry); |
| e->flags |= WINE_RB_FLAG_TRAVERSED_LEFT; |
| entry = &e->left; |
| continue; |
| } |
| |
| if (e->right && !(e->flags & WINE_RB_FLAG_TRAVERSED_RIGHT)) |
| { |
| wine_rb_stack_push(&tree->stack, entry); |
| e->flags |= WINE_RB_FLAG_TRAVERSED_RIGHT; |
| entry = &e->right; |
| continue; |
| } |
| |
| e->flags &= ~(WINE_RB_FLAG_TRAVERSED_LEFT | WINE_RB_FLAG_TRAVERSED_RIGHT); |
| callback(e, context); |
| |
| if (!tree->stack.count) break; |
| entry = tree->stack.entries[--tree->stack.count]; |
| } |
| } |
| |
| static inline int wine_rb_init(struct wine_rb_tree *tree, const struct wine_rb_functions *functions) |
| { |
| tree->functions = functions; |
| tree->root = NULL; |
| |
| tree->stack.entries = functions->alloc(16 * sizeof(*tree->stack.entries)); |
| if (!tree->stack.entries) return -1; |
| tree->stack.size = 16; |
| tree->stack.count = 0; |
| |
| return 0; |
| } |
| |
| static inline void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) |
| { |
| wine_rb_postorder(tree, callback, context); |
| } |
| |
| static inline void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) |
| { |
| /* Note that we use postorder here because the callback will likely free the entry. */ |
| if (callback) wine_rb_postorder(tree, callback, context); |
| tree->root = NULL; |
| } |
| |
| static inline void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) |
| { |
| wine_rb_clear(tree, callback, context); |
| tree->functions->free(tree->stack.entries); |
| } |
| |
| static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key) |
| { |
| struct wine_rb_entry *entry = tree->root; |
| while (entry) |
| { |
| int c = tree->functions->compare(key, entry); |
| if (!c) return entry; |
| entry = c < 0 ? entry->left : entry->right; |
| } |
| return NULL; |
| } |
| |
| static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry) |
| { |
| struct wine_rb_entry **parent = &tree->root; |
| size_t black_height = 1; |
| |
| while (*parent) |
| { |
| int c; |
| |
| if (!wine_rb_is_red(*parent)) ++black_height; |
| |
| wine_rb_stack_push(&tree->stack, parent); |
| |
| c = tree->functions->compare(key, *parent); |
| if (!c) |
| { |
| wine_rb_stack_clear(&tree->stack); |
| return -1; |
| } |
| else if (c < 0) parent = &(*parent)->left; |
| else parent = &(*parent)->right; |
| } |
| |
| /* After insertion, the path length to any node should be <= (black_height + 1) * 2. */ |
| if (wine_rb_ensure_stack_size(tree, black_height << 1) == -1) |
| { |
| wine_rb_stack_clear(&tree->stack); |
| return -1; |
| } |
| |
| entry->flags = WINE_RB_FLAG_RED; |
| entry->left = NULL; |
| entry->right = NULL; |
| *parent = entry; |
| |
| wine_rb_fixup(&tree->stack); |
| tree->root->flags &= ~WINE_RB_FLAG_RED; |
| |
| return 0; |
| } |
| |
| static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) |
| { |
| struct wine_rb_entry **entry = &tree->root; |
| |
| while (*entry) |
| { |
| if (tree->functions->compare(key, *entry) < 0) |
| { |
| wine_rb_stack_push(&tree->stack, entry); |
| if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry); |
| entry = &(*entry)->left; |
| } |
| else |
| { |
| if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(entry); |
| if (!tree->functions->compare(key, *entry) && !(*entry)->right) |
| { |
| *entry = NULL; |
| break; |
| } |
| if (!wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->right->left)) |
| wine_rb_move_red_right(entry); |
| if (!tree->functions->compare(key, *entry)) |
| { |
| struct wine_rb_entry **e = &(*entry)->right; |
| struct wine_rb_entry *m = *e; |
| while (m->left) m = m->left; |
| |
| wine_rb_stack_push(&tree->stack, entry); |
| (*entry)->flags |= WINE_RB_FLAG_STOP; |
| |
| while ((*e)->left) |
| { |
| wine_rb_stack_push(&tree->stack, e); |
| if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(e); |
| e = &(*e)->left; |
| } |
| *e = NULL; |
| wine_rb_fixup(&tree->stack); |
| |
| *m = **entry; |
| *entry = m; |
| |
| break; |
| } |
| else |
| { |
| wine_rb_stack_push(&tree->stack, entry); |
| entry = &(*entry)->right; |
| } |
| } |
| } |
| |
| wine_rb_fixup(&tree->stack); |
| if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED; |
| } |
| |
| #endif /* __WINE_WINE_RBTREE_H */ |