Eric Pouech : dbghelp: Improve speed of our hashtable implementation by remembering the last element added to every bucket .
Alexandre Julliard
julliard at winehq.org
Mon Jun 15 07:59:05 CDT 2009
Module: wine
Branch: master
Commit: b37996305d1c64c908ea6a125ac60ca4bfec903f
URL: http://source.winehq.org/git/wine.git/?a=commit;h=b37996305d1c64c908ea6a125ac60ca4bfec903f
Author: Eric Pouech <eric.pouech at orange.fr>
Date: Sun Jun 14 09:19:08 2009 +0200
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 e1941be..9f8a612 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 d687862..4e62f11 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;
}
More information about the wine-cvs
mailing list