return strcmp(name, type->name);
}
-static inline void *d3dcompiler_alloc_rb(size_t size)
-{
- return d3dcompiler_alloc(size);
-}
-
-static inline void *d3dcompiler_realloc_rb(void *ptr, size_t size)
-{
- return d3dcompiler_realloc(ptr, size);
-}
-
-static inline void d3dcompiler_free_rb(void *ptr)
-{
- d3dcompiler_free(ptr);
-}
-static const struct wine_rb_functions hlsl_type_rb_funcs =
-{
- d3dcompiler_alloc_rb,
- d3dcompiler_realloc_rb,
- d3dcompiler_free_rb,
- compare_hlsl_types_rb,
-};
-
void push_scope(struct hlsl_parse_ctx *ctx)
{
struct hlsl_scope *new_scope = d3dcompiler_alloc(sizeof(*new_scope));
}
TRACE("Pushing a new scope\n");
list_init(&new_scope->vars);
- if (wine_rb_init(&new_scope->types, &hlsl_type_rb_funcs) == -1)
- {
- ERR("Failed to initialize types rbtree.\n");
- d3dcompiler_free(new_scope);
- return;
- }
+ wine_rb_init(&new_scope->types, compare_hlsl_types_rb);
new_scope->upper = ctx->cur_scope;
ctx->cur_scope = new_scope;
list_add_tail(&ctx->scopes, &new_scope->entry);
return 0;
}
-static const struct wine_rb_functions hlsl_ir_function_decl_rb_funcs =
-{
- d3dcompiler_alloc_rb,
- d3dcompiler_realloc_rb,
- d3dcompiler_free_rb,
- compare_function_decl_rb,
-};
-
static int compare_function_rb(const void *key, const struct wine_rb_entry *entry)
{
const char *name = key;
return strcmp(name, func->name);
}
-static const struct wine_rb_functions function_rb_funcs =
-{
- d3dcompiler_alloc_rb,
- d3dcompiler_realloc_rb,
- d3dcompiler_free_rb,
- compare_function_rb,
-};
-
void init_functions_tree(struct wine_rb_tree *funcs)
{
- if (wine_rb_init(&hlsl_ctx.functions, &function_rb_funcs) == -1)
- ERR("Failed to initialize functions rbtree.\n");
+ wine_rb_init(&hlsl_ctx.functions, compare_function_rb);
}
static const char *debug_base_type(const struct hlsl_type *type)
TRACE("Function %s redeclared as a user defined function.\n", debugstr_a(name));
func->intrinsic = intrinsic;
wine_rb_destroy(&func->overloads, free_function_decl_rb, NULL);
- if (wine_rb_init(&func->overloads, &hlsl_ir_function_decl_rb_funcs) == -1)
- {
- ERR("Failed to initialize function rbtree.\n");
- return;
- }
+ wine_rb_init(&func->overloads, compare_function_decl_rb);
}
decl->func = func;
if ((old_entry = wine_rb_get(&func->overloads, decl->parameters)))
d3dcompiler_free(name);
return;
}
- wine_rb_remove(&func->overloads, decl->parameters);
+ wine_rb_remove(&func->overloads, old_entry);
free_function_decl(old_decl);
}
wine_rb_put(&func->overloads, decl->parameters, &decl->entry);
}
func = d3dcompiler_alloc(sizeof(*func));
func->name = name;
- if (wine_rb_init(&func->overloads, &hlsl_ir_function_decl_rb_funcs) == -1)
- {
- ERR("Failed to initialize function rbtree.\n");
- d3dcompiler_free(name);
- d3dcompiler_free(func);
- return;
- }
+ wine_rb_init(&func->overloads, compare_function_decl_rb);
decl->func = func;
wine_rb_put(&func->overloads, decl->parameters, &decl->entry);
func->intrinsic = intrinsic;
*
* Copyright 2009 Henri Verbeet
* Copyright 2009 Andrew Riedi
+ * Copyright 2016 Jacek Caban for CodeWeavers
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
#ifndef __WINE_WINE_RBTREE_H
#define __WINE_WINE_RBTREE_H
-#define WINE_RB_ENTRY_VALUE(element, type, field) \
- ((type *)((char *)(element) - FIELD_OFFSET(type, field)))
+#ifdef __GNUC__
+# define WINE_RB_ENTRY_VALUE(element, type, field) ({ \
+ const typeof(((type *)0)->field) *__ptr = (element); \
+ (type *)((char *)__ptr - offsetof(type, field)); })
+#else
+# define WINE_RB_ENTRY_VALUE(element, type, field) \
+ ((type *)((char *)(element) - offsetof(type, field)))
+#endif
struct wine_rb_entry
{
+ struct wine_rb_entry *parent;
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);
-};
+typedef int (*wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry);
struct wine_rb_tree
{
- const struct wine_rb_functions *functions;
+ wine_rb_compare_func_t compare;
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)
+static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
{
- struct wine_rb_entry *e = *entry;
struct wine_rb_entry *right = e->right;
+ if (!e->parent)
+ tree->root = right;
+ else if (e->parent->left == e)
+ e->parent->left = right;
+ else
+ e->parent->right = right;
+
e->right = right->left;
+ if (e->right) e->right->parent = e;
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;
+ right->parent = e->parent;
+ e->parent = right;
}
-static inline void wine_rb_rotate_right(struct wine_rb_entry **entry)
+static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
{
- struct wine_rb_entry *e = *entry;
struct wine_rb_entry *left = e->left;
+ if (!e->parent)
+ tree->root = left;
+ else if (e->parent->left == e)
+ e->parent->left = left;
+ else
+ e->parent->right = left;
+
e->left = left->right;
+ if (e->left) e->left->parent = e;
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;
+ left->parent = e->parent;
+ e->parent = left;
}
static inline void wine_rb_flip_color(struct wine_rb_entry *entry)
entry->right->flags ^= WINE_RB_FLAG_RED;
}
-static inline void wine_rb_fixup(struct wine_rb_stack *stack)
+static inline struct wine_rb_entry *wine_rb_head(struct wine_rb_entry *iter)
{
- 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;
- }
+ if (!iter) return NULL;
+ while (iter->left) iter = iter->left;
+ return iter;
}
-static inline void wine_rb_move_red_left(struct wine_rb_entry **entry)
+static inline struct wine_rb_entry *wine_rb_next(struct wine_rb_entry *iter)
{
- 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);
- }
+ if (iter->right) return wine_rb_head(iter->right);
+ while (iter->parent && iter->parent->right == iter) iter = iter->parent;
+ return iter->parent;
}
-static inline void wine_rb_move_red_right(struct wine_rb_entry **entry)
+static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter)
{
- wine_rb_flip_color(*entry);
- if (wine_rb_is_red((*entry)->left->left))
- {
- wine_rb_rotate_right(entry);
- wine_rb_flip_color(*entry);
+ if (!iter) return NULL;
+
+ for (;;) {
+ while (iter->left) iter = iter->left;
+ if (!iter->right) return iter;
+ iter = iter->right;
}
}
-static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
+static inline struct wine_rb_entry *wine_rb_postorder_next(struct wine_rb_entry *iter)
{
- struct wine_rb_entry **entry;
+ if (!iter->parent) return NULL;
+ if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
+ return wine_rb_postorder_head(iter->parent->right);
+}
- if (!tree->root) return;
+/* iterate through the tree */
+#define WINE_RB_FOR_EACH(cursor, tree) \
+ for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))
- for (entry = &tree->root;;)
- {
- struct wine_rb_entry *e = *entry;
+/* iterate through the tree using a tree entry */
+#define WINE_RB_FOR_EACH_ENTRY(elem, tree, type, field) \
+ for ((elem) = WINE_RB_ENTRY_VALUE(wine_rb_head((tree)->root), type, field); \
+ &(elem)->field; \
+ (elem) = WINE_RB_ENTRY_VALUE(wine_rb_next(&elem->field), type, field))
- 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);
+static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
+{
+ struct wine_rb_entry *iter, *next;
- if (!tree->stack.count) break;
- entry = tree->stack.entries[--tree->stack.count];
+ for (iter = wine_rb_postorder_head(tree->root); iter; iter = next)
+ {
+ next = wine_rb_postorder_next(iter);
+ callback(iter, context);
}
}
-static inline int wine_rb_init(struct wine_rb_tree *tree, const struct wine_rb_functions *functions)
+static inline void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t compare)
{
- tree->functions = functions;
+ tree->compare = compare;
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);
+ struct wine_rb_entry *iter;
+ WINE_RB_FOR_EACH(iter, tree) callback(iter, context);
}
static inline void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
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);
+ int c = tree->compare(key, entry);
if (!c) return entry;
entry = c < 0 ? entry->left : entry->right;
}
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;
+ struct wine_rb_entry **iter = &tree->root, *parent = tree->root;
- while (*parent)
+ while (*iter)
{
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;
+ parent = *iter;
+ c = tree->compare(key, parent);
+ if (!c) return -1;
+ else if (c < 0) iter = &parent->left;
+ else iter = &parent->right;
}
entry->flags = WINE_RB_FLAG_RED;
+ entry->parent = parent;
entry->left = NULL;
entry->right = NULL;
- *parent = entry;
+ *iter = entry;
+
+ while (wine_rb_is_red(entry->parent))
+ {
+ if (entry->parent == entry->parent->parent->left)
+ {
+ if (wine_rb_is_red(entry->parent->parent->right))
+ {
+ wine_rb_flip_color(entry->parent->parent);
+ entry = entry->parent->parent;
+ }
+ else
+ {
+ if (entry == entry->parent->right)
+ {
+ entry = entry->parent;
+ wine_rb_rotate_left(tree, entry);
+ }
+ entry->parent->flags &= ~WINE_RB_FLAG_RED;
+ entry->parent->parent->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_right(tree, entry->parent->parent);
+ }
+ }
+ else
+ {
+ if (wine_rb_is_red(entry->parent->parent->left))
+ {
+ wine_rb_flip_color(entry->parent->parent);
+ entry = entry->parent->parent;
+ }
+ else
+ {
+ if (entry == entry->parent->left)
+ {
+ entry = entry->parent;
+ wine_rb_rotate_right(tree, entry);
+ }
+ entry->parent->flags &= ~WINE_RB_FLAG_RED;
+ entry->parent->parent->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_left(tree, entry->parent->parent);
+ }
+ }
+ }
- 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)
+static inline void wine_rb_remove(struct wine_rb_tree *tree, struct wine_rb_entry *entry)
{
- struct wine_rb_entry **entry = &tree->root;
+ struct wine_rb_entry *iter, *child, *parent, *w;
+ int need_fixup;
+
+ if (entry->right && entry->left)
+ for(iter = entry->right; iter->left; iter = iter->left);
+ else
+ iter = entry;
- while (*entry)
+ child = iter->left ? iter->left : iter->right;
+
+ if (!iter->parent)
+ tree->root = child;
+ else if (iter == iter->parent->left)
+ iter->parent->left = child;
+ else
+ iter->parent->right = child;
+
+ if (child) child->parent = iter->parent;
+ parent = iter->parent;
+
+ need_fixup = !wine_rb_is_red(iter);
+
+ if (entry != iter)
{
- 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;
- }
+ *iter = *entry;
+ if (!iter->parent)
+ tree->root = iter;
+ else if (entry == iter->parent->left)
+ iter->parent->left = iter;
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;
+ iter->parent->right = iter;
- wine_rb_stack_push(&tree->stack, entry);
- (*entry)->flags |= WINE_RB_FLAG_STOP;
+ if (iter->right) iter->right->parent = iter;
+ if (iter->left) iter->left->parent = iter;
+ if (parent == entry) parent = iter;
+ }
- while ((*e)->left)
+ if (need_fixup)
+ {
+ while (parent && !wine_rb_is_red(child))
+ {
+ if (child == parent->left)
+ {
+ w = parent->right;
+ if (wine_rb_is_red(w))
{
- 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;
+ w->flags &= ~WINE_RB_FLAG_RED;
+ parent->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_left(tree, parent);
+ w = parent->right;
+ }
+ if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
+ {
+ if (!wine_rb_is_red(w->right))
+ {
+ w->left->flags &= ~WINE_RB_FLAG_RED;
+ w->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_right(tree, w);
+ w = parent->right;
+ }
+ w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
+ parent->flags &= ~WINE_RB_FLAG_RED;
+ if (w->right)
+ w->right->flags &= ~WINE_RB_FLAG_RED;
+ wine_rb_rotate_left(tree, parent);
+ child = NULL;
+ break;
}
- *e = NULL;
- wine_rb_fixup(&tree->stack);
-
- *m = **entry;
- *entry = m;
-
- break;
}
else
{
- wine_rb_stack_push(&tree->stack, entry);
- entry = &(*entry)->right;
+ w = parent->left;
+ if (wine_rb_is_red(w))
+ {
+ w->flags &= ~WINE_RB_FLAG_RED;
+ parent->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_right(tree, parent);
+ w = parent->left;
+ }
+ if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
+ {
+ if (!wine_rb_is_red(w->left))
+ {
+ w->right->flags &= ~WINE_RB_FLAG_RED;
+ w->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_left(tree, w);
+ w = parent->left;
+ }
+ w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
+ parent->flags &= ~WINE_RB_FLAG_RED;
+ if (w->left)
+ w->left->flags &= ~WINE_RB_FLAG_RED;
+ wine_rb_rotate_right(tree, parent);
+ child = NULL;
+ break;
+ }
}
+ w->flags |= WINE_RB_FLAG_RED;
+ child = parent;
+ parent = child->parent;
}
+ if (child) child->flags &= ~WINE_RB_FLAG_RED;
}
- wine_rb_fixup(&tree->stack);
if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
}
+static inline void wine_rb_remove_key(struct wine_rb_tree *tree, const void *key)
+{
+ struct wine_rb_entry *entry = wine_rb_get(tree, key);
+ if (entry) wine_rb_remove(tree, entry);
+}
+
#endif /* __WINE_WINE_RBTREE_H */