554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync#ifndef __WINE_WINE_RBTREE_H

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync#define __WINE_WINE_RBTREE_H

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync#define WINE_RB_ENTRY_VALUE(element, type, field) \

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync ((type *)((char *)(element) - FIELD_OFFSET(type, field)))

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstruct wine_rb_entry

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync unsigned int flags;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync};

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstruct wine_rb_stack

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry ***entries;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync size_t count;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync size_t size;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync};

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstruct wine_rb_functions

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync void *(*alloc)(size_t size);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync void *(*realloc)(void *ptr, size_t size);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync void (*free)(void *ptr);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync int (*compare)(const void *key, const struct wine_rb_entry *entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync};

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstruct wine_rb_tree

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync const struct wine_rb_functions *functions;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *root;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_stack stack;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync};

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsynctypedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *context);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync#define WINE_RB_FLAG_RED 0x1

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync#define WINE_RB_FLAG_STOP 0x2

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync#define WINE_RB_FLAG_TRAVERSED_LEFT 0x4

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync#define WINE_RB_FLAG_TRAVERSED_RIGHT 0x8

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_stack_clear(struct wine_rb_stack *stack)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync stack->count = 0;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_stack_push(struct wine_rb_stack *stack, struct wine_rb_entry **entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync stack->entries[stack->count++] = entry;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline int wine_rb_ensure_stack_size(struct wine_rb_tree *tree, size_t size)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_stack *stack = &tree->stack;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (size > stack->size)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync size_t new_size = stack->size << 1;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry ***new_entries = tree->functions->realloc(stack->entries,

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync new_size * sizeof(*stack->entries));

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!new_entries) return -1;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync stack->entries = new_entries;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync stack->size = new_size;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync return 0;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline int wine_rb_is_red(struct wine_rb_entry *entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync return entry && (entry->flags & WINE_RB_FLAG_RED);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_rotate_left(struct wine_rb_entry **entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *e = *entry;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *right = e->right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync e->right = right->left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync right->left = e;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync right->flags &= ~WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync right->flags |= e->flags & WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync e->flags |= WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync *entry = right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_rotate_right(struct wine_rb_entry **entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *e = *entry;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *left = e->left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync e->left = left->right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync left->right = e;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync left->flags &= ~WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync left->flags |= e->flags & WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync e->flags |= WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync *entry = left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_flip_color(struct wine_rb_entry *entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry->flags ^= WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry->left->flags ^= WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry->right->flags ^= WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_fixup(struct wine_rb_stack *stack)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync while (stack->count)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry **entry = stack->entries[stack->count - 1];

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if ((*entry)->flags & WINE_RB_FLAG_STOP)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync (*entry)->flags &= ~WINE_RB_FLAG_STOP;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync return;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->right)) wine_rb_flip_color(*entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync --stack->count;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_move_red_left(struct wine_rb_entry **entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_flip_color(*entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (wine_rb_is_red((*entry)->right->left))

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_rotate_right(&(*entry)->right);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_rotate_left(entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_flip_color(*entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_move_red_right(struct wine_rb_entry **entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_flip_color(*entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (wine_rb_is_red((*entry)->left->left))

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_rotate_right(entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_flip_color(*entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry **entry;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!tree->root) return;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync for (entry = &tree->root;;)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *e = *entry;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (e->left && !(e->flags & WINE_RB_FLAG_TRAVERSED_LEFT))

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_push(&tree->stack, entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync e->flags |= WINE_RB_FLAG_TRAVERSED_LEFT;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry = &e->left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync continue;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (e->right && !(e->flags & WINE_RB_FLAG_TRAVERSED_RIGHT))

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_push(&tree->stack, entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync e->flags |= WINE_RB_FLAG_TRAVERSED_RIGHT;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry = &e->right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync continue;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync e->flags &= ~(WINE_RB_FLAG_TRAVERSED_LEFT | WINE_RB_FLAG_TRAVERSED_RIGHT);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync callback(e, context);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!tree->stack.count) break;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry = tree->stack.entries[--tree->stack.count];

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline int wine_rb_init(struct wine_rb_tree *tree, const struct wine_rb_functions *functions)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync tree->functions = functions;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync tree->root = NULL;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync tree->stack.entries = functions->alloc(16 * sizeof(*tree->stack.entries));

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!tree->stack.entries) return -1;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync tree->stack.size = 16;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync tree->stack.count = 0;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync return 0;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_postorder(tree, callback, context);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync /* Note that we use postorder here because the callback will likely free the entry. */

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (callback) wine_rb_postorder(tree, callback, context);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync tree->root = NULL;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync tree->functions->free(tree->stack.entries);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *entry = tree->root;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync while (entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync int c = tree->functions->compare(key, entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!c) return entry;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry = c < 0 ? entry->left : entry->right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync return NULL;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry **parent = &tree->root;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync size_t black_height = 1;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync while (*parent)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync int c;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!wine_rb_is_red(*parent)) ++black_height;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_push(&tree->stack, parent);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync c = tree->functions->compare(key, *parent);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!c)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_clear(&tree->stack);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync return -1;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync else if (c < 0) parent = &(*parent)->left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync else parent = &(*parent)->right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync /* After insertion, the path length to any node should be <= (black_height + 1) * 2. */

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (wine_rb_ensure_stack_size(tree, black_height << 1) == -1)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_clear(&tree->stack);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync return -1;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry->flags = WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry->left = NULL;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry->right = NULL;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync *parent = entry;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_fixup(&tree->stack);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync tree->root->flags &= ~WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync return 0;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsyncstatic inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync{

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry **entry = &tree->root;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync while (*entry)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (tree->functions->compare(key, *entry) < 0)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_push(&tree->stack, entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry = &(*entry)->left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync else

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!tree->functions->compare(key, *entry) && !(*entry)->right)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync *entry = NULL;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync break;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->right->left))

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_move_red_right(entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!tree->functions->compare(key, *entry))

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry **e = &(*entry)->right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync struct wine_rb_entry *m = *e;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync while (m->left) m = m->left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_push(&tree->stack, entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync (*entry)->flags |= WINE_RB_FLAG_STOP;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync while ((*e)->left)

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_push(&tree->stack, e);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(e);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync e = &(*e)->left;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync *e = NULL;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_fixup(&tree->stack);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync *m = **entry;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync *entry = m;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync break;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync else

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync {

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_stack_push(&tree->stack, entry);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync entry = &(*entry)->right;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync }

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync wine_rb_fixup(&tree->stack);

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync}

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync

554f00fe75489f3f3ce7fbb6d126ce1d2c5c922cvboxsync#endif /* __WINE_WINE_RBTREE_H */