[PATCH 2/5] d3dcompiler: Store data types in a RB tree for faster search.
Matteo Bruni
mbruni at codeweavers.com
Wed Sep 19 12:46:12 CDT 2012
---
dlls/d3dcompiler_43/d3dcompiler_private.h | 4 +-
dlls/d3dcompiler_43/hlsl.y | 3 +-
dlls/d3dcompiler_43/utils.c | 54 +++++++++++++++++++++++++----
3 files changed, 51 insertions(+), 10 deletions(-)
diff --git a/dlls/d3dcompiler_43/d3dcompiler_private.h b/dlls/d3dcompiler_43/d3dcompiler_private.h
index 5171abe..fffb6c6 100644
--- a/dlls/d3dcompiler_43/d3dcompiler_private.h
+++ b/dlls/d3dcompiler_43/d3dcompiler_private.h
@@ -662,7 +662,7 @@ enum hlsl_matrix_majority
struct hlsl_type
{
struct list entry;
- struct list scope_entry;
+ struct wine_rb_entry scope_entry;
enum hlsl_type_class type;
enum hlsl_base_type base_type;
enum hlsl_sampler_dim sampler_dim;
@@ -924,7 +924,7 @@ struct hlsl_scope
{
struct list entry;
struct list vars;
- struct list types;
+ struct wine_rb_tree types;
struct hlsl_scope *upper;
};
diff --git a/dlls/d3dcompiler_43/hlsl.y b/dlls/d3dcompiler_43/hlsl.y
index 97a1d62..486c9a8 100644
--- a/dlls/d3dcompiler_43/hlsl.y
+++ b/dlls/d3dcompiler_43/hlsl.y
@@ -180,7 +180,7 @@ BOOL add_type_to_scope(struct hlsl_scope *scope, struct hlsl_type *def)
if (get_type(scope, def->name, FALSE))
return FALSE;
- list_add_tail(&scope->types, &def->scope_entry);
+ wine_rb_put(&scope->types, def->name, &def->scope_entry);
return TRUE;
}
@@ -1658,6 +1658,7 @@ struct bwriter_shader *parse_hlsl(enum shader_type type, DWORD major, DWORD mino
{
free_declaration(var);
}
+ wine_rb_destroy(&scope->types, NULL, NULL);
d3dcompiler_free(scope);
}
diff --git a/dlls/d3dcompiler_43/utils.c b/dlls/d3dcompiler_43/utils.c
index 05f769c..8aaa675 100644
--- a/dlls/d3dcompiler_43/utils.c
+++ b/dlls/d3dcompiler_43/utils.c
@@ -860,13 +860,10 @@ struct hlsl_type *new_array_type(struct hlsl_type *basic_type, unsigned int arra
struct hlsl_type *get_type(struct hlsl_scope *scope, const char *name, BOOL recursive)
{
- struct hlsl_type *type;
+ struct wine_rb_entry *entry = wine_rb_get(&scope->types, name);
+ if (entry)
+ return WINE_RB_ENTRY_VALUE(entry, struct hlsl_type, scope_entry);
- LIST_FOR_EACH_ENTRY(type, &scope->types, struct hlsl_type, scope_entry)
- {
- if (strcmp(type->name, name) == 0)
- return type;
- }
if (recursive && scope->upper)
return get_type(scope->upper, name, recursive);
return NULL;
@@ -1599,6 +1596,44 @@ struct hlsl_ir_node *make_assignment(struct hlsl_ir_node *left, enum parse_assig
return &assign->node;
}
+int compare_hlsl_types_rb(const void *key, const struct wine_rb_entry *entry)
+{
+ const char *name = (const char *)key;
+ const struct hlsl_type *type = WINE_RB_ENTRY_VALUE(entry, const struct hlsl_type, scope_entry);
+
+ if (name == type->name)
+ return 0;
+
+ if (!name || !type->name)
+ {
+ ERR("hlsl_type without a name in a scope?\n");
+ return -1;
+ }
+ 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));
@@ -1610,7 +1645,12 @@ void push_scope(struct hlsl_parse_ctx *ctx)
}
TRACE("Pushing a new scope\n");
list_init(&new_scope->vars);
- list_init(&new_scope->types);
+ if (wine_rb_init(&new_scope->types, &hlsl_type_rb_funcs) == -1)
+ {
+ ERR("Failed to initialize types rbtree.\n");
+ d3dcompiler_free(new_scope);
+ return;
+ }
new_scope->upper = ctx->cur_scope;
ctx->cur_scope = new_scope;
list_add_tail(&ctx->scopes, &new_scope->entry);
--
1.7.8.6
More information about the wine-patches
mailing list