From b37996305d1c64c908ea6a125ac60ca4bfec903f Mon Sep 17 00:00:00 2001
From: Eric Pouech <eric.pouech@orange.fr>
Date: Sun, 14 Jun 2009 09:19:08 +0200
Subject: [PATCH] dbghelp: Improve speed of our hashtable implementation by
 remembering the last element added to every bucket.

---
 dlls/dbghelp/dbghelp_private.h |  8 +++++++-
 dlls/dbghelp/storage.c         | 20 +++++++++++++-------
 2 files changed, 20 insertions(+), 8 deletions(-)

diff --git a/dlls/dbghelp/dbghelp_private.h b/dlls/dbghelp/dbghelp_private.h
index e1941bef05f..9f8a612c374 100644
--- a/dlls/dbghelp/dbghelp_private.h
+++ b/dlls/dbghelp/dbghelp_private.h
@@ -80,11 +80,17 @@ struct hash_table_elt
     struct hash_table_elt*      next;
 };
 
+struct hash_table_bucket
+{
+    struct hash_table_elt*      first;
+    struct hash_table_elt*      last;
+};
+
 struct hash_table
 {
     unsigned                    num_elts;
     unsigned                    num_buckets;
-    struct hash_table_elt**     buckets;
+    struct hash_table_bucket*   buckets;
     struct pool*                pool;
 };
 
diff --git a/dlls/dbghelp/storage.c b/dlls/dbghelp/storage.c
index d6878625b90..4e62f114cb0 100644
--- a/dlls/dbghelp/storage.c
+++ b/dlls/dbghelp/storage.c
@@ -378,20 +378,26 @@ void hash_table_destroy(struct hash_table* ht)
 void hash_table_add(struct hash_table* ht, struct hash_table_elt* elt)
 {
     unsigned                    hash = hash_table_hash(elt->name, ht->num_buckets);
-    struct hash_table_elt**     p;
 
     if (!ht->buckets)
     {
-        ht->buckets = pool_alloc(ht->pool, ht->num_buckets * sizeof(struct hash_table_elt*));
+        ht->buckets = pool_alloc(ht->pool, ht->num_buckets * sizeof(struct hash_table_bucket));
         assert(ht->buckets);
-        memset(ht->buckets, 0, ht->num_buckets * sizeof(struct hash_table_elt*));
+        memset(ht->buckets, 0, ht->num_buckets * sizeof(struct hash_table_bucket));
     }
 
     /* in some cases, we need to get back the symbols of same name in the order
      * in which they've been inserted. So insert new elements at the end of the list.
      */
-    for (p = &ht->buckets[hash]; *p; p = &((*p)->next));
-    *p = elt;
+    if (!ht->buckets[hash].first)
+    {
+        ht->buckets[hash].first = elt;
+    }
+    else
+    {
+        ht->buckets[hash].last->next = elt;
+    }
+    ht->buckets[hash].last = elt;
     elt->next = NULL;
     ht->num_elts++;
 }
@@ -415,10 +421,10 @@ void hash_table_iter_init(const struct hash_table* ht,
 
 void* hash_table_iter_up(struct hash_table_iter* hti)
 {
-    if(!hti->ht->buckets) return NULL;
+    if (!hti->ht->buckets) return NULL;
 
     if (hti->element) hti->element = hti->element->next;
     while (!hti->element && hti->index < hti->last) 
-        hti->element = hti->ht->buckets[++hti->index];
+        hti->element = hti->ht->buckets[++hti->index].first;
     return hti->element;
 }
-- 
2.11.4.GIT