Eric Pouech : dbghelp: Speed up source string creation (by using rb trees).

[Alexandre Julliard]

Module: wine
Branch: master
Commit: c7c8c0dea78f3f1f8a310b48fa41933e2d775e7f
URL:    http://source.winehq.org/git/wine.git/?a=commit;h=c7c8c0dea78f3f1f8a310b48fa...

Author: Eric Pouech <eric.pouech(a)orange.fr>
Date:   Sat Jan  8 14:15:31 2011 +0100

dbghelp: Speed up source string creation (by using rb trees).

---

 dlls/dbghelp/dbghelp_private.h |    3 ++
 dlls/dbghelp/module.c          |    2 +
 dlls/dbghelp/source.c          |   60 ++++++++++++++++++++++++++++++++++------
 3 files changed, 56 insertions(+), 9 deletions(-)

diff --git a/dlls/dbghelp/dbghelp_private.h b/dlls/dbghelp/dbghelp_private.h
index bb82ad3..fb91114 100644
--- a/dlls/dbghelp/dbghelp_private.h
+++ b/dlls/dbghelp/dbghelp_private.h
@@ -31,6 +31,7 @@
 #include "winnls.h"
 #include "wine/list.h"
 #include "wine/unicode.h"
+#include "wine/rbtree.h"
 
 #include "cvconst.h"
 
@@ -348,6 +349,7 @@ struct module_format
     } u;
 };
 
+extern const struct wine_rb_functions source_rb_functions;
 struct module
 {
     struct process*             process;
@@ -382,6 +384,7 @@ struct module
     unsigned                    sources_used;
     unsigned                    sources_alloc;
     char*                       sources;
+    struct wine_rb_tree         sources_offsets_tree;
 };
 
 struct process 
diff --git a/dlls/dbghelp/module.c b/dlls/dbghelp/module.c
index adadcb7..debfd5d 100644
--- a/dlls/dbghelp/module.c
+++ b/dlls/dbghelp/module.c
@@ -189,6 +189,7 @@ struct module* module_new(struct process* pcs, const WCHAR* name,
     module->sources_used      = 0;
     module->sources_alloc     = 0;
     module->sources           = 0;
+    wine_rb_init(&module->sources_offsets_tree, &source_rb_functions);
 
     return module;
 }
@@ -638,6 +639,7 @@ BOOL module_remove(struct process* pcs, struct module* module)
     }
     hash_table_destroy(&module->ht_symbols);
     hash_table_destroy(&module->ht_types);
+    wine_rb_destroy(&module->sources_offsets_tree, NULL, NULL);
     HeapFree(GetProcessHeap(), 0, module->sources);
     HeapFree(GetProcessHeap(), 0, module->addr_sorttab);
     pool_destroy(&module->pool);
diff --git a/dlls/dbghelp/source.c b/dlls/dbghelp/source.c
index 92c68b7..a5bb86f 100644
--- a/dlls/dbghelp/source.c
+++ b/dlls/dbghelp/source.c
@@ -29,21 +29,55 @@
 
 WINE_DEFAULT_DEBUG_CHANNEL(dbghelp);
 
+static struct module*   rb_module;
+struct source_rb
+{
+    struct wine_rb_entry        entry;
+    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)
+{
+    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
  *
  * check whether a source file has already been stored
  */
-static unsigned source_find(const struct module* module, const char* name)
+static unsigned source_find(const char* name)
 {
-    char*       ptr = module->sources;
+    struct wine_rb_entry*       e;
 
-    while (*ptr)
-    {
-        if (strcmp(ptr, name) == 0) return ptr - module->sources;
-        ptr += strlen(ptr) + 1;
-    }
-    return (unsigned)-1;
+    e = wine_rb_get(&rb_module->sources_offsets_tree, name);
+    if (!e) return -1;
+    return WINE_RB_ENTRY_VALUE(e, struct source_rb, entry)->source;
 }
 
 /******************************************************************
@@ -71,10 +105,13 @@ unsigned source_new(struct module* module, const char* base, const char* name)
         if (tmp[bsz - 1] != '/') tmp[bsz++] = '/';
         strcpy(&tmp[bsz], name);
     }
-    if (!module->sources || (ret = source_find(module, full)) == (unsigned)-1)
+    rb_module = module;
+    if (!module->sources || (ret = source_find(full)) == (unsigned)-1)
     {
         char* new;
         int len = strlen(full) + 1;
+        struct source_rb* rb;
+
         if (module->sources_used + len + 1 > module->sources_alloc)
         {
             if (!module->sources)
@@ -96,6 +133,11 @@ unsigned source_new(struct module* module, const char* base, const char* name)
         memcpy(module->sources + module->sources_used, full, len);
         module->sources_used += len;
         module->sources[module->sources_used] = '\0';
+        if ((rb = pool_alloc(&module->pool, sizeof(*rb))))
+        {
+            rb->source = ret;
+            wine_rb_put(&module->sources_offsets_tree, full, &rb->entry);
+        }
     }
 done:
     HeapFree(GetProcessHeap(), 0, tmp);