[akhaldi] 73348: [INCLUDES/WINE] Update rbtree.h. [D3DCOMPILER_43][DBGHELP][WINED3D] Reflect the rbtree.h changes. CORE-12409

Author: akhaldi
Date: Tue Nov 22 17:23:40 2016
New Revision: 73348

URL: http://svn.reactos.org/svn/reactos?rev=73348&view=rev
Log:
[INCLUDES/WINE] Update rbtree.h. [D3DCOMPILER_43][DBGHELP][WINED3D] Reflect the rbtree.h changes. CORE-12409

Modified:
    trunk/reactos/dll/directx/wine/d3dcompiler_43/reflection.c
    trunk/reactos/dll/directx/wine/d3dcompiler_43/utils.c
    trunk/reactos/dll/directx/wine/wined3d/arb_program_shader.c
    trunk/reactos/dll/directx/wine/wined3d/ati_fragment_shader.c
    trunk/reactos/dll/directx/wine/wined3d/device.c
    trunk/reactos/dll/directx/wine/wined3d/glsl_shader.c
    trunk/reactos/dll/directx/wine/wined3d/utils.c
    trunk/reactos/dll/directx/wine/wined3d/wined3d_private.h
    trunk/reactos/dll/win32/dbghelp/dbghelp_private.h
    trunk/reactos/dll/win32/dbghelp/module.c
    trunk/reactos/dll/win32/dbghelp/source.c
    trunk/reactos/sdk/include/reactos/wine/rbtree.h

Modified: trunk/reactos/dll/directx/wine/d3dcompiler_43/reflection.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/directx/wine/d3dcompile...
==============================================================================
--- trunk/reactos/dll/directx/wine/d3dcompiler_43/reflection.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/directx/wine/d3dcompiler_43/reflection.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -188,21 +188,6 @@
     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);
@@ -237,14 +222,6 @@

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)
 {
@@ -1683,11 +1660,7 @@
     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))

Modified: trunk/reactos/dll/directx/wine/d3dcompiler_43/utils.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/directx/wine/d3dcompile...
==============================================================================
--- trunk/reactos/dll/directx/wine/d3dcompiler_43/utils.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/directx/wine/d3dcompiler_43/utils.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -1696,28 +1696,6 @@
     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));
@@ -1729,12 +1707,7 @@
     }
     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);
@@ -1844,14 +1817,6 @@
     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;
@@ -1860,18 +1825,9 @@
     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)
@@ -2508,11 +2464,7 @@
             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)))
@@ -2526,7 +2478,7 @@
                 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);
@@ -2535,13 +2487,7 @@
     }
     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;

Modified: trunk/reactos/dll/directx/wine/wined3d/arb_program_shader.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/directx/wine/wined3d/ar...
==============================================================================
--- trunk/reactos/dll/directx/wine/wined3d/arb_program_shader.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/directx/wine/wined3d/arb_program_shader.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -4948,14 +4948,6 @@
     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)
 {
@@ -4993,11 +4985,7 @@
     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;
@@ -5836,13 +5824,7 @@
     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;
@@ -6970,14 +6952,6 @@
     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;
@@ -6985,12 +6959,7 @@
     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;

Modified: trunk/reactos/dll/directx/wine/wined3d/ati_fragment_shader.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/directx/wine/wined3d/at...
==============================================================================
--- trunk/reactos/dll/directx/wine/wined3d/ati_fragment_shader.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/directx/wine/wined3d/ati_fragment_shader.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -1317,13 +1317,7 @@
     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;
 }

Modified: trunk/reactos/dll/directx/wine/wined3d/device.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/directx/wine/wined3d/de...
==============================================================================
--- trunk/reactos/dll/directx/wine/wined3d/device.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/directx/wine/wined3d/device.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -5622,14 +5622,6 @@
     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)
@@ -5661,11 +5653,7 @@

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,

Modified: trunk/reactos/dll/directx/wine/wined3d/glsl_shader.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/directx/wine/wined3d/gl...
==============================================================================
--- trunk/reactos/dll/directx/wine/wined3d/glsl_shader.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/directx/wine/wined3d/glsl_shader.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -5048,12 +5048,7 @@
 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)
@@ -7823,14 +7818,6 @@
     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)
 {
@@ -7883,11 +7870,7 @@
         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;
@@ -8257,13 +8240,7 @@
     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;
     }

@@ -8692,13 +8669,7 @@
     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;
     }

Modified: trunk/reactos/dll/directx/wine/wined3d/utils.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/directx/wine/wined3d/ut...
==============================================================================
--- trunk/reactos/dll/directx/wine/wined3d/utils.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/directx/wine/wined3d/utils.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -5162,36 +5162,13 @@
     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;

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)
@@ -5318,7 +5295,7 @@
     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,
@@ -5326,14 +5303,6 @@

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,

Modified: trunk/reactos/dll/directx/wine/wined3d/wined3d_private.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/directx/wine/wined3d/wi...
==============================================================================
--- trunk/reactos/dll/directx/wine/wined3d/wined3d_private.h	[iso-8859-1] (original)
+++ trunk/reactos/dll/directx/wine/wined3d/wined3d_private.h	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -2078,8 +2078,9 @@
     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;

Modified: trunk/reactos/dll/win32/dbghelp/dbghelp_private.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/win32/dbghelp/dbghelp_p...
==============================================================================
--- trunk/reactos/dll/win32/dbghelp/dbghelp_private.h	[iso-8859-1] (original)
+++ trunk/reactos/dll/win32/dbghelp/dbghelp_private.h	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -696,6 +696,7 @@
 /* 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,

Modified: trunk/reactos/dll/win32/dbghelp/module.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/win32/dbghelp/module.c?...
==============================================================================
--- trunk/reactos/dll/win32/dbghelp/module.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/win32/dbghelp/module.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -219,7 +219,7 @@
     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;
 }

Modified: trunk/reactos/dll/win32/dbghelp/source.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/dll/win32/dbghelp/source.c?...
==============================================================================
--- trunk/reactos/dll/win32/dbghelp/source.c	[iso-8859-1] (original)
+++ trunk/reactos/dll/win32/dbghelp/source.c	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -30,35 +30,12 @@
     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 wine_rb_functions source_rb_functions =
-{
-    source_rb_alloc,
-    source_rb_realloc,
-    source_rb_free,
-    source_rb_compare,
-};

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

Modified: trunk/reactos/sdk/include/reactos/wine/rbtree.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/sdk/include/reactos/wine/rb...
==============================================================================
--- trunk/reactos/sdk/include/reactos/wine/rbtree.h	[iso-8859-1] (original)
+++ trunk/reactos/sdk/include/reactos/wine/rbtree.h	[iso-8859-1] Tue Nov 22 17:23:40 2016
@@ -3,6 +3,7 @@
  *
  * 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
@@ -22,103 +23,74 @@
 #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;
+typedef int (*wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry);
+
+struct wine_rb_tree
+{
+    wine_rb_compare_func_t compare;
+    struct wine_rb_entry *root;
 };

-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);
-};
-
-struct wine_rb_tree
-{
-    const struct wine_rb_functions *functions;
-    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)
-{
-    struct wine_rb_entry *e = *entry;
+static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
+{
     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;
-}
-
-static inline void wine_rb_rotate_right(struct wine_rb_entry **entry)
-{
-    struct wine_rb_entry *e = *entry;
+    right->parent = e->parent;
+    e->parent = right;
+}
+
+static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
+{
     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)
@@ -128,96 +100,70 @@
     entry->right->flags ^= WINE_RB_FLAG_RED;
 }

-static inline void wine_rb_fixup(struct wine_rb_stack *stack)
-{
-    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;
-    }
-}
-
-static inline void wine_rb_move_red_left(struct wine_rb_entry **entry)
-{
-    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);
-    }
-}
-
-static inline void wine_rb_move_red_right(struct wine_rb_entry **entry)
-{
-    wine_rb_flip_color(*entry);
-    if (wine_rb_is_red((*entry)->left->left))
-    {
-        wine_rb_rotate_right(entry);
-        wine_rb_flip_color(*entry);
-    }
-}
+static inline struct wine_rb_entry *wine_rb_head(struct wine_rb_entry *iter)
+{
+    if (!iter) return NULL;
+    while (iter->left) iter = iter->left;
+    return iter;
+}
+
+static inline struct wine_rb_entry *wine_rb_next(struct wine_rb_entry *iter)
+{
+    if (iter->right) return wine_rb_head(iter->right);
+    while (iter->parent && iter->parent->right == iter) iter = iter->parent;
+    return iter->parent;
+}
+
+static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter)
+{
+    if (!iter) return NULL;
+
+    for (;;) {
+        while (iter->left) iter = iter->left;
+        if (!iter->right) return iter;
+        iter = iter->right;
+    }
+}
+
+static inline struct wine_rb_entry *wine_rb_postorder_next(struct wine_rb_entry *iter)
+{
+    if (!iter->parent) return NULL;
+    if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
+    return wine_rb_postorder_head(iter->parent->right);
+}
+
+/* iterate through the tree */
+#define WINE_RB_FOR_EACH(cursor, tree) \
+    for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))
+
+/* 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))
+

static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 {
-    struct wine_rb_entry **entry;
-
-    if (!tree->root) return;
-
-    for (entry = &tree->root;;)
-    {
-        struct wine_rb_entry *e = *entry;
-
-        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);
-
-        if (!tree->stack.count) break;
-        entry = tree->stack.entries[--tree->stack.count];
-    }
-}
-
-static inline int wine_rb_init(struct wine_rb_tree *tree, const struct wine_rb_functions *functions)
-{
-    tree->functions = functions;
+    struct wine_rb_entry *iter, *next;
+
+    for (iter = wine_rb_postorder_head(tree->root); iter; iter = next)
+    {
+        next = wine_rb_postorder_next(iter);
+        callback(iter, context);
+    }
+}
+
+static inline void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t compare)
+{
+    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)
@@ -230,7 +176,6 @@
 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)
@@ -238,7 +183,7 @@
     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;
     }
@@ -247,100 +192,185 @@

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;
-
-    while (*parent)
+    struct wine_rb_entry **iter = &tree->root, *parent = tree->root;
+
+    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;
-
-    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)
-{
-    struct wine_rb_entry **entry = &tree->root;
-
-    while (*entry)
-    {
-        if (tree->functions->compare(key, *entry) < 0)
+    *iter = entry;
+
+    while (wine_rb_is_red(entry->parent))
+    {
+        if (entry->parent == entry->parent->parent->left)
         {
-            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;
+            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)->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;
-
-                wine_rb_stack_push(&tree->stack, entry);
-                (*entry)->flags |= WINE_RB_FLAG_STOP;
-
-                while ((*e)->left)
-                {
-                    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;
-                }
-                *e = NULL;
-                wine_rb_fixup(&tree->stack);
-
-                *m = **entry;
-                *entry = m;
-
-                break;
+            if (wine_rb_is_red(entry->parent->parent->left))
+            {
+                wine_rb_flip_color(entry->parent->parent);
+                entry = entry->parent->parent;
             }
             else
             {
-                wine_rb_stack_push(&tree->stack, entry);
-                entry = &(*entry)->right;
+                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, struct wine_rb_entry *entry)
+{
+    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;
+
+    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)
+    {
+        *iter = *entry;
+        if (!iter->parent)
+            tree->root = iter;
+        else if (entry == iter->parent->left)
+            iter->parent->left = iter;
+        else
+            iter->parent->right = iter;
+
+        if (iter->right) iter->right->parent = iter;
+        if (iter->left)  iter->left->parent = iter;
+        if (parent == entry) parent = iter;
+    }
+
+    if (need_fixup)
+    {
+        while (parent && !wine_rb_is_red(child))
+        {
+            if (child == parent->left)
+            {
+                w = parent->right;
+                if (wine_rb_is_red(w))
+                {
+                    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;
+                }
+            }
+            else
+            {
+                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;
+    }
+
     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 */