wined3d: Replace the wined3d hash table with the generic red-black tree.
diff --git a/dlls/wined3d/arb_program_shader.c b/dlls/wined3d/arb_program_shader.c index f977583..8cfb639 100644 --- a/dlls/wined3d/arb_program_shader.c +++ b/dlls/wined3d/arb_program_shader.c
@@ -80,7 +80,7 @@ GLuint depth_blt_vprogram_id; GLuint depth_blt_fprogram_id[tex_type_count]; BOOL use_arbfp_fixed_func; - struct hash_table_t *fragment_shaders; + struct wine_rb_tree fragment_shaders; }; struct if_frame { @@ -3090,14 +3090,20 @@ if(!This->fragment_priv) return E_OUTOFMEMORY; } priv = This->fragment_priv; - priv->fragment_shaders = hash_table_create(ffp_frag_program_key_hash, ffp_frag_program_key_compare); + if (wine_rb_init(&priv->fragment_shaders, &wined3d_ffp_frag_program_rb_functions) == -1) + { + ERR("Failed to initialize rbtree.\n"); + HeapFree(GetProcessHeap(), 0, This->fragment_priv); + return E_OUTOFMEMORY; + } priv->use_arbfp_fixed_func = TRUE; return WINED3D_OK; } -static void arbfp_free_ffpshader(void *value, void *gli) { - const WineD3D_GL_Info *gl_info = gli; - struct arbfp_ffp_desc *entry_arb = value; +static void arbfp_free_ffpshader(struct wine_rb_entry *entry, void *context) +{ + const WineD3D_GL_Info *gl_info = context; + struct arbfp_ffp_desc *entry_arb = WINE_RB_ENTRY_VALUE(entry, struct arbfp_ffp_desc, parent.entry); ENTER_GL(); GL_EXTCALL(glDeleteProgramsARB(1, &entry_arb->shader)); @@ -3110,7 +3116,7 @@ IWineD3DDeviceImpl *This = (IWineD3DDeviceImpl *) iface; struct shader_arb_priv *priv = This->fragment_priv; - hash_table_destroy(priv->fragment_shaders, arbfp_free_ffpshader, &This->adapter->gl_info); + wine_rb_destroy(&priv->fragment_shaders, arbfp_free_ffpshader, &This->adapter->gl_info); priv->use_arbfp_fixed_func = FALSE; if(This->shader_backend != &arb_program_shader_backend) { @@ -3766,7 +3772,7 @@ if(!use_pshader) { /* Find or create a shader implementing the fixed function pipeline settings, then activate it */ gen_ffp_frag_op(stateblock, &settings, FALSE); - desc = (const struct arbfp_ffp_desc *)find_ffp_frag_shader(priv->fragment_shaders, &settings); + desc = (const struct arbfp_ffp_desc *)find_ffp_frag_shader(&priv->fragment_shaders, &settings); if(!desc) { struct arbfp_ffp_desc *new_desc = HeapAlloc(GetProcessHeap(), 0, sizeof(*new_desc)); if (!new_desc) @@ -3782,7 +3788,7 @@ memcpy(&new_desc->parent.settings, &settings, sizeof(settings)); new_desc->shader = gen_arbfp_ffp_shader(&settings, stateblock); - add_ffp_frag_shader(priv->fragment_shaders, &new_desc->parent); + add_ffp_frag_shader(&priv->fragment_shaders, &new_desc->parent); TRACE("Allocated fixed function replacement shader descriptor %p\n", new_desc); desc = new_desc; }
diff --git a/dlls/wined3d/ati_fragment_shader.c b/dlls/wined3d/ati_fragment_shader.c index 1fd3459..06b663e 100644 --- a/dlls/wined3d/ati_fragment_shader.c +++ b/dlls/wined3d/ati_fragment_shader.c
@@ -53,8 +53,7 @@ struct atifs_private_data { - struct hash_table_t *fragment_shaders; /* A hashtable to track fragment pipeline replacement shaders */ - + struct wine_rb_tree fragment_shaders; /* A rb-tree to track fragment pipeline replacement shaders */ }; static const char *debug_dstmod(GLuint mod) { @@ -810,7 +809,7 @@ unsigned int i; gen_ffp_frag_op(stateblock, &settings, TRUE); - desc = (const struct atifs_ffp_desc *)find_ffp_frag_shader(priv->fragment_shaders, &settings); + desc = (const struct atifs_ffp_desc *)find_ffp_frag_shader(&priv->fragment_shaders, &settings); if(!desc) { struct atifs_ffp_desc *new_desc = HeapAlloc(GetProcessHeap(), 0, sizeof(*new_desc)); if (!new_desc) @@ -826,7 +825,7 @@ memcpy(&new_desc->parent.settings, &settings, sizeof(settings)); new_desc->shader = gen_ati_shader(settings.op, &GLINFO_LOCATION); - add_ffp_frag_shader(priv->fragment_shaders, &new_desc->parent); + add_ffp_frag_shader(&priv->fragment_shaders, &new_desc->parent); TRACE("Allocated fixed function replacement shader descriptor %p\n", new_desc); desc = new_desc; } @@ -1114,14 +1113,20 @@ return E_OUTOFMEMORY; } priv = This->fragment_priv; - priv->fragment_shaders = hash_table_create(ffp_frag_program_key_hash, ffp_frag_program_key_compare); + if (wine_rb_init(&priv->fragment_shaders, &wined3d_ffp_frag_program_rb_functions) == -1) + { + ERR("Failed to initialize rbtree.\n"); + HeapFree(GetProcessHeap(), 0, This->fragment_priv); + return E_OUTOFMEMORY; + } return WINED3D_OK; } #define GLINFO_LOCATION This->adapter->gl_info -static void atifs_free_ffpshader(void *value, void *device) { - IWineD3DDeviceImpl *This = device; - struct atifs_ffp_desc *entry_ati = value; +static void atifs_free_ffpshader(struct wine_rb_entry *entry, void *context) +{ + IWineD3DDeviceImpl *This = context; + struct atifs_ffp_desc *entry_ati = WINE_RB_ENTRY_VALUE(entry, struct atifs_ffp_desc, parent.entry); ENTER_GL(); GL_EXTCALL(glDeleteFragmentShaderATI(entry_ati->shader)); @@ -1134,7 +1139,7 @@ IWineD3DDeviceImpl *This = (IWineD3DDeviceImpl *) iface; struct atifs_private_data *priv = This->fragment_priv; - hash_table_destroy(priv->fragment_shaders, atifs_free_ffpshader, This); + wine_rb_destroy(&priv->fragment_shaders, atifs_free_ffpshader, This); HeapFree(GetProcessHeap(), 0, priv); This->fragment_priv = NULL;
diff --git a/dlls/wined3d/glsl_shader.c b/dlls/wined3d/glsl_shader.c index d7a8835..d33a3ff 100644 --- a/dlls/wined3d/glsl_shader.c +++ b/dlls/wined3d/glsl_shader.c
@@ -83,7 +83,7 @@ /* GLSL shader private data */ struct shader_glsl_priv { - struct hash_table_t *glsl_program_lookup; + struct wine_rb_tree program_lookup; struct glsl_shader_prog_link *glsl_program; struct constant_heap vconst_heap; struct constant_heap pconst_heap; @@ -94,6 +94,7 @@ /* Struct to maintain data about a linked GLSL program */ struct glsl_shader_prog_link { + struct wine_rb_entry program_lookup_entry; struct list vshader_entry; struct list pshader_entry; GLhandleARB programId; @@ -543,10 +544,9 @@ } } -static void reset_program_constant_version(void *value, void *context) +static void reset_program_constant_version(struct wine_rb_entry *entry, void *context) { - struct glsl_shader_prog_link *entry = value; - entry->constant_version = 0; + WINE_RB_ENTRY_VALUE(entry, struct glsl_shader_prog_link, program_lookup_entry)->constant_version = 0; } /** @@ -696,7 +696,7 @@ if (priv->next_constant_version == UINT_MAX) { TRACE("Max constant version reached, resetting to 0.\n"); - hash_table_for_each_entry(priv->glsl_program_lookup, reset_program_constant_version, NULL); + wine_rb_for_each_entry(&priv->program_lookup, reset_program_constant_version, NULL); priv->next_constant_version = 1; } else @@ -3261,15 +3261,17 @@ ********************************************/ static void add_glsl_program_entry(struct shader_glsl_priv *priv, struct glsl_shader_prog_link *entry) { - glsl_program_key_t *key; + glsl_program_key_t key; - key = HeapAlloc(GetProcessHeap(), 0, sizeof(glsl_program_key_t)); - key->vshader = entry->vshader; - key->pshader = entry->pshader; - key->vs_args = entry->vs_args; - key->ps_args = entry->ps_args; + key.vshader = entry->vshader; + key.pshader = entry->pshader; + key.vs_args = entry->vs_args; + key.ps_args = entry->ps_args; - hash_table_put(priv->glsl_program_lookup, key, entry); + if (wine_rb_put(&priv->program_lookup, &key, &entry->program_lookup_entry) == -1) + { + ERR("Failed to insert program entry.\n"); + } } static struct glsl_shader_prog_link *get_glsl_program_entry(struct shader_glsl_priv *priv, @@ -3282,21 +3284,21 @@ key.vs_args = *vs_args; key.ps_args = *ps_args; - return hash_table_get(priv->glsl_program_lookup, &key); + return WINE_RB_ENTRY_VALUE(wine_rb_get(&priv->program_lookup, &key), + struct glsl_shader_prog_link, program_lookup_entry); } /* GL locking is done by the caller */ static void delete_glsl_program_entry(struct shader_glsl_priv *priv, const WineD3D_GL_Info *gl_info, struct glsl_shader_prog_link *entry) { - glsl_program_key_t *key; + glsl_program_key_t key; - key = HeapAlloc(GetProcessHeap(), 0, sizeof(glsl_program_key_t)); - key->vshader = entry->vshader; - key->pshader = entry->pshader; - key->vs_args = entry->vs_args; - key->ps_args = entry->ps_args; - hash_table_remove(priv->glsl_program_lookup, key); + key.vshader = entry->vshader; + key.pshader = entry->pshader; + key.vs_args = entry->vs_args; + key.ps_args = entry->ps_args; + wine_rb_remove(&priv->program_lookup, &key); GL_EXTCALL(glDeleteObjectARB(entry->programId)); if (entry->vshader) list_remove(&entry->vshader_entry); @@ -4383,29 +4385,24 @@ } } -static unsigned int glsl_program_key_hash(const void *key) +static int glsl_program_key_compare(const void *key, const struct wine_rb_entry *entry) { const glsl_program_key_t *k = key; + const struct glsl_shader_prog_link *prog = WINE_RB_ENTRY_VALUE(entry, + const struct glsl_shader_prog_link, program_lookup_entry); + int cmp; - unsigned int hash = ((DWORD_PTR) k->vshader) | ((DWORD_PTR) k->pshader) << 16; - hash += ~(hash << 15); - hash ^= (hash >> 10); - hash += (hash << 3); - hash ^= (hash >> 6); - hash += ~(hash << 11); - hash ^= (hash >> 16); + if (k->vshader > prog->vshader) return 1; + else if (k->vshader < prog->vshader) return -1; - return hash; -} + if (k->pshader > prog->pshader) return 1; + else if (k->pshader < prog->pshader) return -1; -static BOOL glsl_program_key_compare(const void *keya, const void *keyb) -{ - const glsl_program_key_t *ka = keya; - const glsl_program_key_t *kb = keyb; + cmp = memcmp(&k->vs_args, &prog->vs_args, sizeof(prog->vs_args)); + if (cmp) return cmp; - return ka->vshader == kb->vshader && ka->pshader == kb->pshader && - (memcmp(&ka->ps_args, &kb->ps_args, sizeof(kb->ps_args)) == 0) && - (memcmp(&ka->vs_args, &kb->vs_args, sizeof(kb->vs_args)) == 0); + cmp = memcmp(&k->ps_args, &prog->ps_args, sizeof(prog->ps_args)); + return cmp; } static BOOL constant_heap_init(struct constant_heap *heap, unsigned int constant_count) @@ -4432,6 +4429,14 @@ HeapFree(GetProcessHeap(), 0, heap->entries); } +static const struct wine_rb_functions wined3d_glsl_program_rb_functions = +{ + wined3d_rb_alloc, + wined3d_rb_realloc, + wined3d_rb_free, + glsl_program_key_compare, +}; + static HRESULT shader_glsl_alloc(IWineD3DDevice *iface) { IWineD3DDeviceImpl *This = (IWineD3DDeviceImpl *)iface; const WineD3D_GL_Info *gl_info = &This->adapter->gl_info; @@ -4463,7 +4468,16 @@ return E_OUTOFMEMORY; } - priv->glsl_program_lookup = hash_table_create(glsl_program_key_hash, glsl_program_key_compare); + if (wine_rb_init(&priv->program_lookup, &wined3d_glsl_program_rb_functions) == -1) + { + ERR("Failed to initialize rbtree.\n"); + constant_heap_free(&priv->pconst_heap); + constant_heap_free(&priv->vconst_heap); + HeapFree(GetProcessHeap(), 0, priv->stack); + HeapFree(GetProcessHeap(), 0, priv); + return E_OUTOFMEMORY; + } + priv->next_constant_version = 1; This->shader_priv = priv; @@ -4486,7 +4500,7 @@ } LEAVE_GL(); - hash_table_destroy(priv->glsl_program_lookup, NULL, NULL); + wine_rb_destroy(&priv->program_lookup, NULL, NULL); constant_heap_free(&priv->pconst_heap); constant_heap_free(&priv->vconst_heap);
diff --git a/dlls/wined3d/utils.c b/dlls/wined3d/utils.c index cce4920..858e3ca 100644 --- a/dlls/wined3d/utils.c +++ b/dlls/wined3d/utils.c
@@ -1901,238 +1901,6 @@ } #undef GLINFO_LOCATION -/* Hash table functions */ - -struct hash_table_t *hash_table_create(hash_function_t *hash_function, compare_function_t *compare_function) -{ - struct hash_table_t *table; - unsigned int initial_size = 8; - - table = HeapAlloc(GetProcessHeap(), 0, sizeof(struct hash_table_t) + (initial_size * sizeof(struct list))); - if (!table) - { - ERR("Failed to allocate table, returning NULL.\n"); - return NULL; - } - - table->hash_function = hash_function; - table->compare_function = compare_function; - - table->grow_size = initial_size - (initial_size >> 2); - table->shrink_size = 0; - - table->buckets = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, initial_size * sizeof(struct list)); - if (!table->buckets) - { - ERR("Failed to allocate table buckets, returning NULL.\n"); - HeapFree(GetProcessHeap(), 0, table); - return NULL; - } - table->bucket_count = initial_size; - - table->entries = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, table->grow_size * sizeof(struct hash_table_entry_t)); - if (!table->entries) - { - ERR("Failed to allocate table entries, returning NULL.\n"); - HeapFree(GetProcessHeap(), 0, table->buckets); - HeapFree(GetProcessHeap(), 0, table); - return NULL; - } - table->entry_count = 0; - - list_init(&table->free_entries); - table->count = 0; - - return table; -} - -void hash_table_destroy(struct hash_table_t *table, void (*free_value)(void *value, void *cb), void *cb) -{ - unsigned int i = 0; - - for (i = 0; i < table->entry_count; ++i) - { - if(free_value) { - free_value(table->entries[i].value, cb); - } - HeapFree(GetProcessHeap(), 0, table->entries[i].key); - } - - HeapFree(GetProcessHeap(), 0, table->entries); - HeapFree(GetProcessHeap(), 0, table->buckets); - HeapFree(GetProcessHeap(), 0, table); -} - -void hash_table_for_each_entry(struct hash_table_t *table, void (*callback)(void *value, void *context), void *context) -{ - unsigned int i = 0; - - for (i = 0; i < table->entry_count; ++i) - { - callback(table->entries[i].value, context); - } -} - -static inline struct hash_table_entry_t *hash_table_get_by_idx(const struct hash_table_t *table, const void *key, - unsigned int idx) -{ - struct hash_table_entry_t *entry; - - if (table->buckets[idx].next) - LIST_FOR_EACH_ENTRY(entry, &(table->buckets[idx]), struct hash_table_entry_t, entry) - if (table->compare_function(entry->key, key)) return entry; - - return NULL; -} - -static BOOL hash_table_resize(struct hash_table_t *table, unsigned int new_bucket_count) -{ - unsigned int new_entry_count = 0; - struct hash_table_entry_t *new_entries; - struct list *new_buckets; - unsigned int grow_size = new_bucket_count - (new_bucket_count >> 2); - unsigned int i; - - new_buckets = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, new_bucket_count * sizeof(struct list)); - if (!new_buckets) - { - ERR("Failed to allocate new buckets, returning FALSE.\n"); - return FALSE; - } - - new_entries = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, grow_size * sizeof(struct hash_table_entry_t)); - if (!new_entries) - { - ERR("Failed to allocate new entries, returning FALSE.\n"); - HeapFree(GetProcessHeap(), 0, new_buckets); - return FALSE; - } - - for (i = 0; i < table->bucket_count; ++i) - { - if (table->buckets[i].next) - { - struct hash_table_entry_t *entry, *entry2; - - LIST_FOR_EACH_ENTRY_SAFE(entry, entry2, &table->buckets[i], struct hash_table_entry_t, entry) - { - int j; - struct hash_table_entry_t *new_entry = new_entries + (new_entry_count++); - *new_entry = *entry; - - j = new_entry->hash & (new_bucket_count - 1); - - if (!new_buckets[j].next) list_init(&new_buckets[j]); - list_add_head(&new_buckets[j], &new_entry->entry); - } - } - } - - HeapFree(GetProcessHeap(), 0, table->buckets); - table->buckets = new_buckets; - - HeapFree(GetProcessHeap(), 0, table->entries); - table->entries = new_entries; - - table->entry_count = new_entry_count; - list_init(&table->free_entries); - - table->bucket_count = new_bucket_count; - table->grow_size = grow_size; - table->shrink_size = new_bucket_count > 8 ? new_bucket_count >> 2 : 0; - - return TRUE; -} - -void hash_table_put(struct hash_table_t *table, void *key, void *value) -{ - unsigned int idx; - unsigned int hash; - struct hash_table_entry_t *entry; - - hash = table->hash_function(key); - idx = hash & (table->bucket_count - 1); - entry = hash_table_get_by_idx(table, key, idx); - - if (entry) - { - HeapFree(GetProcessHeap(), 0, key); - entry->value = value; - - if (!value) - { - HeapFree(GetProcessHeap(), 0, entry->key); - entry->key = NULL; - - /* Remove the entry */ - list_remove(&entry->entry); - list_add_head(&table->free_entries, &entry->entry); - - --table->count; - - /* Shrink if necessary */ - if (table->count < table->shrink_size) { - if (!hash_table_resize(table, table->bucket_count >> 1)) - { - ERR("Failed to shrink the table...\n"); - } - } - } - - return; - } - - if (!value) return; - - /* Grow if necessary */ - if (table->count >= table->grow_size) - { - if (!hash_table_resize(table, table->bucket_count << 1)) - { - ERR("Failed to grow the table, returning.\n"); - return; - } - - idx = hash & (table->bucket_count - 1); - } - - /* Find an entry to insert */ - if (!list_empty(&table->free_entries)) - { - struct list *elem = list_head(&table->free_entries); - - list_remove(elem); - entry = LIST_ENTRY(elem, struct hash_table_entry_t, entry); - } else { - entry = table->entries + (table->entry_count++); - } - - /* Insert the entry */ - entry->key = key; - entry->value = value; - entry->hash = hash; - if (!table->buckets[idx].next) list_init(&table->buckets[idx]); - list_add_head(&table->buckets[idx], &entry->entry); - - ++table->count; -} - -void hash_table_remove(struct hash_table_t *table, void *key) -{ - hash_table_put(table, key, NULL); -} - -void *hash_table_get(const struct hash_table_t *table, const void *key) -{ - unsigned int idx; - struct hash_table_entry_t *entry; - - idx = table->hash_function(key) & (table->bucket_count - 1); - entry = hash_table_get_by_idx(table, key, idx); - - return entry ? entry->value : NULL; -} - #define GLINFO_LOCATION stateblock->wineD3DDevice->adapter->gl_info void gen_ffp_frag_op(IWineD3DStateBlockImpl *stateblock, struct ffp_frag_settings *settings, BOOL ignore_textype) { #define ARG1 0x01 @@ -2366,20 +2134,20 @@ } #undef GLINFO_LOCATION -const struct ffp_frag_desc *find_ffp_frag_shader(const struct hash_table_t *fragment_shaders, +const struct ffp_frag_desc *find_ffp_frag_shader(const struct wine_rb_tree *fragment_shaders, const struct ffp_frag_settings *settings) { - return hash_table_get(fragment_shaders, settings); + return WINE_RB_ENTRY_VALUE(wine_rb_get(fragment_shaders, settings), struct ffp_frag_desc, entry); } -void add_ffp_frag_shader(struct hash_table_t *shaders, struct ffp_frag_desc *desc) { - struct ffp_frag_settings *key = HeapAlloc(GetProcessHeap(), 0, sizeof(*key)); +void add_ffp_frag_shader(struct wine_rb_tree *shaders, struct ffp_frag_desc *desc) +{ /* Note that the key is the implementation independent part of the ffp_frag_desc structure, - * whereas desc points to an extended structure with implementation specific parts. - * Make a copy of the key because hash_table_put takes ownership of it - */ - *key = desc->settings; - hash_table_put(shaders, key, desc); + * whereas desc points to an extended structure with implementation specific parts. */ + if (wine_rb_put(shaders, &desc->settings, &desc->entry) == -1) + { + ERR("Failed to insert ffp frag shader.\n"); + } } /* Activates the texture dimension according to the bound D3D texture. @@ -2478,41 +2246,37 @@ } #undef GLINFO_LOCATION -unsigned int ffp_frag_program_key_hash(const void *key) +void *wined3d_rb_alloc(size_t size) { - const struct ffp_frag_settings *k = key; - unsigned int hash = 0, i; - const DWORD *blob; - - /* This takes the texture op settings of stage 0 and 1 into account. - * how exactly depends on the memory laybout of the compiler, but it - * should not matter too much. Stages > 1 are used rarely, so there's - * no need to process them. Even if they're used it is likely that - * the ffp setup has distinct stage 0 and 1 settings. - */ - for(i = 0; i < 2; i++) { - blob = (const DWORD *)&k->op[i]; - hash ^= blob[0] ^ blob[1]; - } - - hash += ~(hash << 15); - hash ^= (hash >> 10); - hash += (hash << 3); - hash ^= (hash >> 6); - hash += ~(hash << 11); - hash ^= (hash >> 16); - - return hash; + return HeapAlloc(GetProcessHeap(), 0, size); } -BOOL ffp_frag_program_key_compare(const void *keya, const void *keyb) +void *wined3d_rb_realloc(void *ptr, size_t size) { - const struct ffp_frag_settings *ka = keya; - const struct ffp_frag_settings *kb = keyb; - - return memcmp(ka, kb, sizeof(*ka)) == 0; + return HeapReAlloc(GetProcessHeap(), 0, ptr, size); } +void wined3d_rb_free(void *ptr) +{ + HeapFree(GetProcessHeap(), 0, ptr); +} + +static int ffp_frag_program_key_compare(const void *key, const struct wine_rb_entry *entry) +{ + const struct ffp_frag_settings *ka = key; + const struct ffp_frag_settings *kb = &WINE_RB_ENTRY_VALUE(entry, const struct ffp_frag_desc, entry)->settings; + + return memcmp(ka, kb, sizeof(*ka)); +} + +const struct wine_rb_functions wined3d_ffp_frag_program_rb_functions = +{ + wined3d_rb_alloc, + wined3d_rb_realloc, + wined3d_rb_free, + ffp_frag_program_key_compare, +}; + UINT wined3d_log2i(UINT32 x) { static const BYTE l[] =
diff --git a/dlls/wined3d/wined3d_private.h b/dlls/wined3d/wined3d_private.h index e673055..a610b7a 100644 --- a/dlls/wined3d/wined3d_private.h +++ b/dlls/wined3d/wined3d_private.h
@@ -41,6 +41,7 @@ #include "wine/wined3d.h" #include "wined3d_gl.h" #include "wine/list.h" +#include "wine/rbtree.h" /* Texture format fixups */ @@ -126,36 +127,9 @@ return yuv_fixup; } -/* Hash table functions */ -typedef unsigned int (hash_function_t)(const void *key); -typedef BOOL (compare_function_t)(const void *keya, const void *keyb); - -struct hash_table_entry_t { - void *key; - void *value; - unsigned int hash; - struct list entry; -}; - -struct hash_table_t { - hash_function_t *hash_function; - compare_function_t *compare_function; - struct list *buckets; - unsigned int bucket_count; - struct hash_table_entry_t *entries; - unsigned int entry_count; - struct list free_entries; - unsigned int count; - unsigned int grow_size; - unsigned int shrink_size; -}; - -struct hash_table_t *hash_table_create(hash_function_t *hash_function, compare_function_t *compare_function); -void hash_table_destroy(struct hash_table_t *table, void (*free_value)(void *value, void *cb), void *cb); -void hash_table_for_each_entry(struct hash_table_t *table, void (*callback)(void *value, void *context), void *context); -void *hash_table_get(const struct hash_table_t *table, const void *key); -void hash_table_put(struct hash_table_t *table, void *key, void *value); -void hash_table_remove(struct hash_table_t *table, void *key); +void *wined3d_rb_alloc(size_t size); +void *wined3d_rb_realloc(void *ptr, size_t size); +void wined3d_rb_free(void *ptr); /* Device caps */ #define MAX_PALETTES 65536 @@ -1384,15 +1358,16 @@ struct ffp_frag_desc { + struct wine_rb_entry entry; struct ffp_frag_settings settings; }; +extern const struct wine_rb_functions wined3d_ffp_frag_program_rb_functions; + void gen_ffp_frag_op(IWineD3DStateBlockImpl *stateblock, struct ffp_frag_settings *settings, BOOL ignore_textype); -const struct ffp_frag_desc *find_ffp_frag_shader(const struct hash_table_t *fragment_shaders, +const struct ffp_frag_desc *find_ffp_frag_shader(const struct wine_rb_tree *fragment_shaders, const struct ffp_frag_settings *settings); -void add_ffp_frag_shader(struct hash_table_t *shaders, struct ffp_frag_desc *desc); -BOOL ffp_frag_program_key_compare(const void *keya, const void *keyb); -unsigned int ffp_frag_program_key_hash(const void *key); +void add_ffp_frag_shader(struct wine_rb_tree *shaders, struct ffp_frag_desc *desc); /***************************************************************************** * IWineD3D implementation structure