[INCLUDES/WINE] Update rbtree.h. [D3DCOMPILER_43][DBGHELP][WINED3D] Reflect the rbtre...

svn path=/trunk/; revision=73348

diff --git a/reactos/dll/directx/wine/d3dcompiler_43/reflection.c b/reactos/dll/directx/wine/d3dcompiler_43/reflection.c
index becdee3..3376f22 100644 (file)
--- a/reactos/dll/directx/wine/d3dcompiler_43/reflection.c
+++ b/reactos/dll/directx/wine/d3dcompiler_43/reflection.c
@@ -188,21 +188,6 @@ static BOOL copy_value(const char *ptr, void **value, DWORD size)
     return TRUE;
 }
 
     return TRUE;
 }
 

-static void *d3dcompiler_rb_alloc(size_t size)
-{
-    return HeapAlloc(GetProcessHeap(), 0, size);
-}
-
-static void *d3dcompiler_rb_realloc(void *ptr, size_t size)
-{
-    return HeapReAlloc(GetProcessHeap(), 0, ptr, size);
-}
-
-static void d3dcompiler_rb_free(void *ptr)
-{
-    HeapFree(GetProcessHeap(), 0, ptr);
-}
-

 static int d3dcompiler_shader_reflection_type_compare(const void *key, const struct wine_rb_entry *entry)
 {
     const struct d3dcompiler_shader_reflection_type *t = WINE_RB_ENTRY_VALUE(entry, const struct d3dcompiler_shader_reflection_type, entry);
 static int d3dcompiler_shader_reflection_type_compare(const void *key, const struct wine_rb_entry *entry)
 {
     const struct d3dcompiler_shader_reflection_type *t = WINE_RB_ENTRY_VALUE(entry, const struct d3dcompiler_shader_reflection_type, entry);


@@ -238,14 +223,6 @@ static void d3dcompiler_shader_reflection_type_destroy(struct wine_rb_entry *ent
     HeapFree(GetProcessHeap(), 0, t);
 }
 
     HeapFree(GetProcessHeap(), 0, t);
 }
 

-static const struct wine_rb_functions d3dcompiler_shader_reflection_type_rb_functions =
-{
-    d3dcompiler_rb_alloc,
-    d3dcompiler_rb_realloc,
-    d3dcompiler_rb_free,
-    d3dcompiler_shader_reflection_type_compare,
-};
-

 static void free_signature(struct d3dcompiler_shader_signature *sig)
 {
     TRACE("Free signature %p\n", sig);
 static void free_signature(struct d3dcompiler_shader_signature *sig)
 {
     TRACE("Free signature %p\n", sig);


@@ -1683,11 +1660,7 @@ static HRESULT d3dcompiler_shader_reflection_init(struct d3dcompiler_shader_refl
     reflection->ID3D11ShaderReflection_iface.lpVtbl = &d3dcompiler_shader_reflection_vtbl;
     reflection->refcount = 1;
 
     reflection->ID3D11ShaderReflection_iface.lpVtbl = &d3dcompiler_shader_reflection_vtbl;
     reflection->refcount = 1;
 

-    if (wine_rb_init(&reflection->types, &d3dcompiler_shader_reflection_type_rb_functions) == -1)
-    {
-        ERR("Failed to initialize type rbtree.\n");
-        return E_FAIL;
-    }
+    wine_rb_init(&reflection->types, d3dcompiler_shader_reflection_type_compare);

 
     hr = dxbc_parse(data, data_size, &src_dxbc);
     if (FAILED(hr))
 
     hr = dxbc_parse(data, data_size, &src_dxbc);
     if (FAILED(hr))

diff --git a/reactos/dll/directx/wine/d3dcompiler_43/utils.c b/reactos/dll/directx/wine/d3dcompiler_43/utils.c
index aedfdce..fb4f0b7 100644 (file)
--- a/reactos/dll/directx/wine/d3dcompiler_43/utils.c
+++ b/reactos/dll/directx/wine/d3dcompiler_43/utils.c
@@ -1696,28 +1696,6 @@ static int compare_hlsl_types_rb(const void *key, const struct wine_rb_entry *en
     return strcmp(name, type->name);
 }
 
     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));
 void push_scope(struct hlsl_parse_ctx *ctx)
 {
     struct hlsl_scope *new_scope = d3dcompiler_alloc(sizeof(*new_scope));


@@ -1729,12 +1707,7 @@ void push_scope(struct hlsl_parse_ctx *ctx)
     }
     TRACE("Pushing a new scope\n");
     list_init(&new_scope->vars);
     }
     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);
     new_scope->upper = ctx->cur_scope;
     ctx->cur_scope = new_scope;
     list_add_tail(&ctx->scopes, &new_scope->entry);


@@ -1844,14 +1817,6 @@ static int compare_function_decl_rb(const void *key, const struct wine_rb_entry
     return 0;
 }
 
     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;
 static int compare_function_rb(const void *key, const struct wine_rb_entry *entry)
 {
     const char *name = key;


@@ -1860,18 +1825,9 @@ static int compare_function_rb(const void *key, const struct wine_rb_entry *entr
     return strcmp(name, func->name);
 }
 
     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)
 {
 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)
 }
 
 static const char *debug_base_type(const struct hlsl_type *type)


@@ -2508,11 +2464,7 @@ void add_function_decl(struct wine_rb_tree *funcs, char *name, struct hlsl_ir_fu
             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);
             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)))
         }
         decl->func = func;
         if ((old_entry = wine_rb_get(&func->overloads, decl->parameters)))


@@ -2526,7 +2478,7 @@ void add_function_decl(struct wine_rb_tree *funcs, char *name, struct hlsl_ir_fu
                 d3dcompiler_free(name);
                 return;
             }
                 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);
             free_function_decl(old_decl);
         }
         wine_rb_put(&func->overloads, decl->parameters, &decl->entry);


@@ -2535,13 +2487,7 @@ void add_function_decl(struct wine_rb_tree *funcs, char *name, struct hlsl_ir_fu
     }
     func = d3dcompiler_alloc(sizeof(*func));
     func->name = name;
     }
     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;
     decl->func = func;
     wine_rb_put(&func->overloads, decl->parameters, &decl->entry);
     func->intrinsic = intrinsic;

diff --git a/reactos/dll/directx/wine/wined3d/arb_program_shader.c b/reactos/dll/directx/wine/wined3d/arb_program_shader.c
index 094e836..7802fc9 100644 (file)
--- a/reactos/dll/directx/wine/wined3d/arb_program_shader.c
+++ b/reactos/dll/directx/wine/wined3d/arb_program_shader.c
@@ -4948,14 +4948,6 @@ static int sig_tree_compare(const void *key, const struct wine_rb_entry *entry)
     return compare_sig(key, &e->sig);
 }
 
     return compare_sig(key, &e->sig);
 }
 

-static const struct wine_rb_functions sig_tree_functions =
-{
-    wined3d_rb_alloc,
-    wined3d_rb_realloc,
-    wined3d_rb_free,
-    sig_tree_compare
-};
-

 static HRESULT shader_arb_alloc(struct wined3d_device *device, const struct wined3d_vertex_pipe_ops *vertex_pipe,
         const struct fragment_pipeline *fragment_pipe)
 {
 static HRESULT shader_arb_alloc(struct wined3d_device *device, const struct wined3d_vertex_pipe_ops *vertex_pipe,
         const struct fragment_pipeline *fragment_pipe)
 {


@@ -4993,11 +4985,7 @@ static HRESULT shader_arb_alloc(struct wined3d_device *device, const struct wine
     memset(priv->pshader_const_dirty, 1,
             sizeof(*priv->pshader_const_dirty) * d3d_info->limits.ps_uniform_count);
 
     memset(priv->pshader_const_dirty, 1,
             sizeof(*priv->pshader_const_dirty) * d3d_info->limits.ps_uniform_count);
 

-    if(wine_rb_init(&priv->signature_tree, &sig_tree_functions) == -1)
-    {
-        ERR("RB tree init failed\n");
-        goto fail;
-    }
+    wine_rb_init(&priv->signature_tree, sig_tree_compare);

 
     priv->vertex_pipe = vertex_pipe;
     priv->fragment_pipe = fragment_pipe;
 
     priv->vertex_pipe = vertex_pipe;
     priv->fragment_pipe = fragment_pipe;


@@ -5836,13 +5824,7 @@ static void *arbfp_alloc(const struct wined3d_shader_backend_ops *shader_backend
     else if (!(priv = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*priv))))
         return NULL;
 
     else if (!(priv = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*priv))))
         return NULL;
 

-    if (wine_rb_init(&priv->fragment_shaders, &wined3d_ffp_frag_program_rb_functions) == -1)
-    {
-        ERR("Failed to initialize rbtree.\n");
-        if (priv != shader_priv)
-            HeapFree(GetProcessHeap(), 0, priv);
-        return NULL;
-    }
+    wine_rb_init(&priv->fragment_shaders, wined3d_ffp_frag_program_key_compare);

     priv->use_arbfp_fixed_func = TRUE;
 
     return priv;
     priv->use_arbfp_fixed_func = TRUE;
 
     return priv;


@@ -6970,14 +6952,6 @@ static void arbfp_free_blit_shader(struct wine_rb_entry *entry, void *context)
     HeapFree(GetProcessHeap(), 0, entry_arb);
 }
 
     HeapFree(GetProcessHeap(), 0, entry_arb);
 }
 

-static const struct wine_rb_functions wined3d_arbfp_blit_rb_functions =
-{
-    wined3d_rb_alloc,
-    wined3d_rb_realloc,
-    wined3d_rb_free,
-    arbfp_blit_type_compare,
-};
-

 static HRESULT arbfp_blit_alloc(struct wined3d_device *device)
 {
     struct arbfp_blit_priv *priv;
 static HRESULT arbfp_blit_alloc(struct wined3d_device *device)
 {
     struct arbfp_blit_priv *priv;


@@ -6985,12 +6959,7 @@ static HRESULT arbfp_blit_alloc(struct wined3d_device *device)
     if (!(priv = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*priv))))
         return E_OUTOFMEMORY;
 
     if (!(priv = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*priv))))
         return E_OUTOFMEMORY;
 

-    if (wine_rb_init(&priv->shaders, &wined3d_arbfp_blit_rb_functions) == -1)
-    {
-        ERR("Failed to initialize rbtree.\n");
-        HeapFree(GetProcessHeap(), 0, priv);
-        return E_OUTOFMEMORY;
-    }
+    wine_rb_init(&priv->shaders, arbfp_blit_type_compare);

 
     device->blit_priv = priv;
 
 
     device->blit_priv = priv;
 

diff --git a/reactos/dll/directx/wine/wined3d/ati_fragment_shader.c b/reactos/dll/directx/wine/wined3d/ati_fragment_shader.c
index cad4e8a..5b0cde0 100644 (file)
--- a/reactos/dll/directx/wine/wined3d/ati_fragment_shader.c
+++ b/reactos/dll/directx/wine/wined3d/ati_fragment_shader.c
@@ -1317,13 +1317,7 @@ static void *atifs_alloc(const struct wined3d_shader_backend_ops *shader_backend
     if (!(priv = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*priv))))
         return NULL;
 
     if (!(priv = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*priv))))
         return NULL;
 

-    if (wine_rb_init(&priv->fragment_shaders, &wined3d_ffp_frag_program_rb_functions) == -1)
-    {
-        ERR("Failed to initialize rbtree.\n");
-        HeapFree(GetProcessHeap(), 0, priv);
-        return NULL;
-    }
-
+    wine_rb_init(&priv->fragment_shaders, wined3d_ffp_frag_program_key_compare);

     return priv;
 }
 
     return priv;
 }
 

diff --git a/reactos/dll/directx/wine/wined3d/device.c b/reactos/dll/directx/wine/wined3d/device.c
index cf6b180..f4db593 100644 (file)
--- a/reactos/dll/directx/wine/wined3d/device.c
+++ b/reactos/dll/directx/wine/wined3d/device.c
@@ -5622,14 +5622,6 @@ static int wined3d_sampler_compare(const void *key, const struct wine_rb_entry *
     return memcmp(&sampler->desc, key, sizeof(sampler->desc));
 }
 
     return memcmp(&sampler->desc, key, sizeof(sampler->desc));
 }
 

-static const struct wine_rb_functions wined3d_sampler_rb_functions =
-{
-    wined3d_rb_alloc,
-    wined3d_rb_realloc,
-    wined3d_rb_free,
-    wined3d_sampler_compare,
-};
-

 HRESULT device_init(struct wined3d_device *device, struct wined3d *wined3d,
         UINT adapter_idx, enum wined3d_device_type device_type, HWND focus_window, DWORD flags,
         BYTE surface_alignment, struct wined3d_device_parent *device_parent)
 HRESULT device_init(struct wined3d_device *device, struct wined3d *wined3d,
         UINT adapter_idx, enum wined3d_device_type device_type, HWND focus_window, DWORD flags,
         BYTE surface_alignment, struct wined3d_device_parent *device_parent)


@@ -5661,11 +5653,7 @@ HRESULT device_init(struct wined3d_device *device, struct wined3d *wined3d,
 
     fragment_pipeline = adapter->fragment_pipe;
 
 
     fragment_pipeline = adapter->fragment_pipe;
 

-    if (wine_rb_init(&device->samplers, &wined3d_sampler_rb_functions) == -1)
-    {
-        ERR("Failed to initialize sampler rbtree.\n");
-        return E_OUTOFMEMORY;
-    }
+    wine_rb_init(&device->samplers, wined3d_sampler_compare);

 
     if (vertex_pipeline->vp_states && fragment_pipeline->states
             && FAILED(hr = compile_state_table(device->StateTable, device->multistate_funcs,
 
     if (vertex_pipeline->vp_states && fragment_pipeline->states
             && FAILED(hr = compile_state_table(device->StateTable, device->multistate_funcs,

diff --git a/reactos/dll/directx/wine/wined3d/glsl_shader.c b/reactos/dll/directx/wine/wined3d/glsl_shader.c
index 0630c4a..d5724a0 100644 (file)
--- a/reactos/dll/directx/wine/wined3d/glsl_shader.c
+++ b/reactos/dll/directx/wine/wined3d/glsl_shader.c
@@ -5048,12 +5048,7 @@ static struct glsl_shader_prog_link *get_glsl_program_entry(const struct shader_
 static void delete_glsl_program_entry(struct shader_glsl_priv *priv, const struct wined3d_gl_info *gl_info,
         struct glsl_shader_prog_link *entry)
 {
 static void delete_glsl_program_entry(struct shader_glsl_priv *priv, const struct wined3d_gl_info *gl_info,
         struct glsl_shader_prog_link *entry)
 {

-    struct glsl_program_key key;
-
-    key.vs_id = entry->vs.id;
-    key.gs_id = entry->gs.id;
-    key.ps_id = entry->ps.id;
-    wine_rb_remove(&priv->program_lookup, &key);
+    wine_rb_remove(&priv->program_lookup, &entry->program_lookup_entry);

 
     GL_EXTCALL(glDeleteProgram(entry->id));
     if (entry->vs.id)
 
     GL_EXTCALL(glDeleteProgram(entry->id));
     if (entry->vs.id)


@@ -7823,14 +7818,6 @@ static void constant_heap_free(struct constant_heap *heap)
     HeapFree(GetProcessHeap(), 0, heap->entries);
 }
 
     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(struct wined3d_device *device, const struct wined3d_vertex_pipe_ops *vertex_pipe,
         const struct fragment_pipeline *fragment_pipe)
 {
 static HRESULT shader_glsl_alloc(struct wined3d_device *device, const struct wined3d_vertex_pipe_ops *vertex_pipe,
         const struct fragment_pipeline *fragment_pipe)
 {


@@ -7883,11 +7870,7 @@ static HRESULT shader_glsl_alloc(struct wined3d_device *device, const struct win
         goto fail;
     }
 
         goto fail;
     }
 

-    if (wine_rb_init(&priv->program_lookup, &wined3d_glsl_program_rb_functions) == -1)
-    {
-        ERR("Failed to initialize rbtree.\n");
-        goto fail;
-    }
+    wine_rb_init(&priv->program_lookup, glsl_program_key_compare);

 
     priv->next_constant_version = 1;
     priv->vertex_pipe = vertex_pipe;
 
     priv->next_constant_version = 1;
     priv->vertex_pipe = vertex_pipe;


@@ -8257,13 +8240,7 @@ static void *glsl_vertex_pipe_vp_alloc(const struct wined3d_shader_backend_ops *
     if (shader_backend == &glsl_shader_backend)
     {
         priv = shader_priv;
     if (shader_backend == &glsl_shader_backend)
     {
         priv = shader_priv;

-
-        if (wine_rb_init(&priv->ffp_vertex_shaders, &wined3d_ffp_vertex_program_rb_functions) == -1)
-        {
-            ERR("Failed to initialize rbtree.\n");
-            return NULL;
-        }
-
+        wine_rb_init(&priv->ffp_vertex_shaders, wined3d_ffp_vertex_program_key_compare);

         return priv;
     }
 
         return priv;
     }
 


@@ -8692,13 +8669,7 @@ static void *glsl_fragment_pipe_alloc(const struct wined3d_shader_backend_ops *s
     if (shader_backend == &glsl_shader_backend)
     {
         priv = shader_priv;
     if (shader_backend == &glsl_shader_backend)
     {
         priv = shader_priv;

-
-        if (wine_rb_init(&priv->ffp_fragment_shaders, &wined3d_ffp_frag_program_rb_functions) == -1)
-        {
-            ERR("Failed to initialize rbtree.\n");
-            return NULL;
-        }
-
+        wine_rb_init(&priv->ffp_fragment_shaders, wined3d_ffp_frag_program_key_compare);

         return priv;
     }
 
         return priv;
     }
 

diff --git a/reactos/dll/directx/wine/wined3d/utils.c b/reactos/dll/directx/wine/wined3d/utils.c
index 666e2f6..4f8c0ae 100644 (file)
--- a/reactos/dll/directx/wine/wined3d/utils.c
+++ b/reactos/dll/directx/wine/wined3d/utils.c
@@ -5162,22 +5162,7 @@ void sampler_texdim(struct wined3d_context *context, const struct wined3d_state
     texture_activate_dimensions(state->textures[sampler], context->gl_info);
 }
 
     texture_activate_dimensions(state->textures[sampler], context->gl_info);
 }
 

-void *wined3d_rb_alloc(size_t size)
-{
-    return HeapAlloc(GetProcessHeap(), 0, size);
-}
-
-void *wined3d_rb_realloc(void *ptr, size_t size)
-{
-    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)
+int wined3d_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;
 {
     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;


@@ -5185,14 +5170,6 @@ static int ffp_frag_program_key_compare(const void *key, const struct wine_rb_en
     return memcmp(ka, kb, sizeof(*ka));
 }
 
     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,
-};
-

 void wined3d_ffp_get_vs_settings(const struct wined3d_context *context,
         const struct wined3d_state *state, struct wined3d_ffp_vs_settings *settings)
 {
 void wined3d_ffp_get_vs_settings(const struct wined3d_context *context,
         const struct wined3d_state *state, struct wined3d_ffp_vs_settings *settings)
 {


@@ -5318,7 +5295,7 @@ void wined3d_ffp_get_vs_settings(const struct wined3d_context *context,
     settings->padding = 0;
 }
 
     settings->padding = 0;
 }
 

-static int wined3d_ffp_vertex_program_key_compare(const void *key, const struct wine_rb_entry *entry)
+int wined3d_ffp_vertex_program_key_compare(const void *key, const struct wine_rb_entry *entry)

 {
     const struct wined3d_ffp_vs_settings *ka = key;
     const struct wined3d_ffp_vs_settings *kb = &WINE_RB_ENTRY_VALUE(entry,
 {
     const struct wined3d_ffp_vs_settings *ka = key;
     const struct wined3d_ffp_vs_settings *kb = &WINE_RB_ENTRY_VALUE(entry,


@@ -5327,14 +5304,6 @@ static int wined3d_ffp_vertex_program_key_compare(const void *key, const struct
     return memcmp(ka, kb, sizeof(*ka));
 }
 
     return memcmp(ka, kb, sizeof(*ka));
 }
 

-const struct wine_rb_functions wined3d_ffp_vertex_program_rb_functions =
-{
-    wined3d_rb_alloc,
-    wined3d_rb_realloc,
-    wined3d_rb_free,
-    wined3d_ffp_vertex_program_key_compare,
-};
-

 const struct blit_shader *wined3d_select_blitter(const struct wined3d_gl_info *gl_info,
         const struct wined3d_d3d_info *d3d_info, enum wined3d_blit_op blit_op,
         const RECT *src_rect, DWORD src_usage, enum wined3d_pool src_pool, const struct wined3d_format *src_format,
 const struct blit_shader *wined3d_select_blitter(const struct wined3d_gl_info *gl_info,
         const struct wined3d_d3d_info *d3d_info, enum wined3d_blit_op blit_op,
         const RECT *src_rect, DWORD src_usage, enum wined3d_pool src_pool, const struct wined3d_format *src_format,

diff --git a/reactos/dll/directx/wine/wined3d/wined3d_private.h b/reactos/dll/directx/wine/wined3d/wined3d_private.h
index 6d389de..639dc70 100644 (file)
--- a/reactos/dll/directx/wine/wined3d/wined3d_private.h
+++ b/reactos/dll/directx/wine/wined3d/wined3d_private.h
@@ -2078,8 +2078,9 @@ struct ffp_frag_desc
     struct ffp_frag_settings    settings;
 };
 
     struct ffp_frag_settings    settings;
 };
 

-extern const struct wine_rb_functions wined3d_ffp_frag_program_rb_functions DECLSPEC_HIDDEN;
-extern const struct wine_rb_functions wined3d_ffp_vertex_program_rb_functions DECLSPEC_HIDDEN;
+int wined3d_ffp_frag_program_key_compare(const void *key, const struct wine_rb_entry *entry) DECLSPEC_HIDDEN;
+int wined3d_ffp_vertex_program_key_compare(const void *key, const struct wine_rb_entry *entry) DECLSPEC_HIDDEN;
+

 extern const struct wined3d_parent_ops wined3d_null_parent_ops DECLSPEC_HIDDEN;
 
 unsigned int wined3d_max_compat_varyings(const struct wined3d_gl_info *gl_info) DECLSPEC_HIDDEN;
 extern const struct wined3d_parent_ops wined3d_null_parent_ops DECLSPEC_HIDDEN;
 
 unsigned int wined3d_max_compat_varyings(const struct wined3d_gl_info *gl_info) DECLSPEC_HIDDEN;

diff --git a/reactos/dll/win32/dbghelp/dbghelp_private.h b/reactos/dll/win32/dbghelp/dbghelp_private.h
index c7b4d58..5154636 100644 (file)
--- a/reactos/dll/win32/dbghelp/dbghelp_private.h
+++ b/reactos/dll/win32/dbghelp/dbghelp_private.h
@@ -696,6 +696,7 @@ extern const char*  pe_map_directory(struct module* module, int dirno, DWORD* si
 /* source.c */
 extern unsigned     source_new(struct module* module, const char* basedir, const char* source) DECLSPEC_HIDDEN;
 extern const char*  source_get(const struct module* module, unsigned idx) DECLSPEC_HIDDEN;
 /* source.c */
 extern unsigned     source_new(struct module* module, const char* basedir, const char* source) DECLSPEC_HIDDEN;
 extern const char*  source_get(const struct module* module, unsigned idx) DECLSPEC_HIDDEN;

+extern int          source_rb_compare(const void *key, const struct wine_rb_entry *entry) DECLSPEC_HIDDEN;

 
 /* stabs.c */
 typedef void (*stabs_def_cb)(struct module* module, unsigned long load_offset,
 
 /* stabs.c */
 typedef void (*stabs_def_cb)(struct module* module, unsigned long load_offset,

diff --git a/reactos/dll/win32/dbghelp/module.c b/reactos/dll/win32/dbghelp/module.c
index b90fe96..5845237 100644 (file)
--- a/reactos/dll/win32/dbghelp/module.c
+++ b/reactos/dll/win32/dbghelp/module.c
@@ -219,7 +219,7 @@ struct module* module_new(struct process* pcs, const WCHAR* name,
     module->sources_used      = 0;
     module->sources_alloc     = 0;
     module->sources           = 0;
     module->sources_used      = 0;
     module->sources_alloc     = 0;
     module->sources           = 0;

-    wine_rb_init(&module->sources_offsets_tree, &source_rb_functions);
+    wine_rb_init(&module->sources_offsets_tree, source_rb_compare);

 
     return module;
 }
 
     return module;
 }

diff --git a/reactos/dll/win32/dbghelp/source.c b/reactos/dll/win32/dbghelp/source.c
index 829a10d..29123e1 100644 (file)
--- a/reactos/dll/win32/dbghelp/source.c
+++ b/reactos/dll/win32/dbghelp/source.c
@@ -30,36 +30,13 @@ struct source_rb
     unsigned                    source;
 };
 
     unsigned                    source;
 };
 

-static void *source_rb_alloc(size_t size)
-{
-    return HeapAlloc(GetProcessHeap(), 0, size);
-}
-
-static void *source_rb_realloc(void *ptr, size_t size)
-{
-    return HeapReAlloc(GetProcessHeap(), 0, ptr, size);
-}
-
-static void source_rb_free(void *ptr)
-{
-    HeapFree(GetProcessHeap(), 0, ptr);
-}
-
-static int source_rb_compare(const void *key, const struct wine_rb_entry *entry)
+int source_rb_compare(const void *key, const struct wine_rb_entry *entry)

 {
     const struct source_rb *t = WINE_RB_ENTRY_VALUE(entry, const struct source_rb, entry);
 
     return strcmp((const char*)key, rb_module->sources + t->source);
 }
 
 {
     const struct source_rb *t = WINE_RB_ENTRY_VALUE(entry, const struct source_rb, entry);
 
     return strcmp((const char*)key, rb_module->sources + t->source);
 }
 

-const struct wine_rb_functions source_rb_functions =
-{
-    source_rb_alloc,
-    source_rb_realloc,
-    source_rb_free,
-    source_rb_compare,
-};
-

 /******************************************************************
  *             source_find
  *
 /******************************************************************
  *             source_find
  *

diff --git a/reactos/sdk/include/reactos/wine/rbtree.h b/reactos/sdk/include/reactos/wine/rbtree.h
index 71437c4..441e039 100644 (file)
--- a/reactos/sdk/include/reactos/wine/rbtree.h
+++ b/reactos/sdk/include/reactos/wine/rbtree.h
@@ -3,6 +3,7 @@
  *
  * Copyright 2009 Henri Verbeet
  * Copyright 2009 Andrew Riedi
  *
  * 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
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public


@@ -22,103 +23,74 @@
 #ifndef __WINE_WINE_RBTREE_H
 #define __WINE_WINE_RBTREE_H
 
 #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
 {

+    struct wine_rb_entry *parent;

     struct wine_rb_entry *left;
     struct wine_rb_entry *right;
     unsigned int flags;
 };
 
     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
 {
 
 struct wine_rb_tree
 {

-    const struct wine_rb_functions *functions;
+    wine_rb_compare_func_t compare;

     struct wine_rb_entry *root;
     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
 };
 
 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 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;
 
     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;
     e->right = right->left;

+    if (e->right) e->right->parent = e;

     right->left = 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;
 
     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;
     e->left = left->right;

+    if (e->left) e->left->parent = e;

     left->right = 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)
 }
 
 static inline void wine_rb_flip_color(struct wine_rb_entry *entry)


@@ -128,96 +100,70 @@ static inline void wine_rb_flip_color(struct wine_rb_entry *entry)
     entry->right->flags ^= WINE_RB_FLAG_RED;
 }
 
     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->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)
 {
 }
 
 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_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)


@@ -230,7 +176,6 @@ static inline void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_fun
 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);
 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)
 }
 
 static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)


@@ -238,7 +183,7 @@ static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree,
     struct wine_rb_entry *entry = tree->root;
     while (entry)
     {
     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;
     }
         if (!c) return entry;
         entry = c < 0 ? entry->left : entry->right;
     }


@@ -247,100 +192,185 @@ static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree,
 
 static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
 {
 
 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;
 
     {
         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->flags = WINE_RB_FLAG_RED;

+    entry->parent = parent;

     entry->left = NULL;
     entry->right = NULL;
     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;
 }
 
     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
         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
             {
             }
             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;
 }
 
     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 */
 #endif  /* __WINE_WINE_RBTREE_H */