diff options
author | 2007-01-17 02:37:07 +1000 | |
---|---|---|
committer | 2007-01-17 02:37:07 +1000 | |
commit | 54e19b1efbc3a959f4d5207bc9faeab2f4b25aab (patch) | |
tree | e5d7e4bdb2dcfe9302855a691bb5ba037aa3ab2e /util.c | |
parent | f603b6ef68696be0f90a5fe6c834665d6e2670bb (diff) |
Add a one-item cache into the hash table. This reduces the number of hash computations by roughly 20%
darcs-hash:20070116163707-ac50b-214a16d4210d32fb50693e71a14b6b8f3fededfe.gz
Diffstat (limited to 'util.c')
-rw-r--r-- | util.c | 12 |
1 files changed, 12 insertions, 0 deletions
@@ -208,6 +208,7 @@ void hash_init2( hash_table_t *h, h->count=0; h->hash_func = hash_func; h->compare_func = compare_func; + h->cache=-1; } void hash_init( hash_table_t *h, @@ -219,6 +220,7 @@ void hash_init( hash_table_t *h, h->count=0; h->hash_func = hash_func; h->compare_func = compare_func; + h->cache=-1; } @@ -237,6 +239,14 @@ static int hash_search( hash_table_t *h, int hv; int pos; + if( h->cache>=0 && h->arr[h->cache].key) + { + if( h->compare_func( h->arr[h->cache].key, key ) ) + { + return h->cache; + } + } + hv = h->hash_func( key ); pos = (hv & 0x7fffffff) % h->size; while(1) @@ -244,6 +254,7 @@ static int hash_search( hash_table_t *h, if( (h->arr[pos].key == 0 ) || ( h->compare_func( h->arr[pos].key, key ) ) ) { + h->cache = pos; return pos; } pos++; @@ -268,6 +279,7 @@ static int hash_realloc( hash_table_t *h, int i; + h->cache = -1; h->arr = malloc( sizeof( hash_struct_t) * sz ); if( h->arr == 0 ) { |