summaryrefslogtreecommitdiff
path: root/utils
diff options
context:
space:
mode:
authorRob Kendrick <rjek@netsurf-browser.org>2006-10-13 15:50:11 +0000
committerRob Kendrick <rjek@netsurf-browser.org>2006-10-13 15:50:11 +0000
commit7711781f240a6aa1d89c2fbbbe0de11d66a688b7 (patch)
tree34e7c822643c26de8037025e6618f5ca7b3ba35c /utils
parenta8a944bd5211e82924dd2ba232f241d67d2b4055 (diff)
downloadnetsurf-7711781f240a6aa1d89c2fbbbe0de11d66a688b7.tar.gz
netsurf-7711781f240a6aa1d89c2fbbbe0de11d66a688b7.tar.bz2
Further hash table optimisations and tidies. Test rig now does more lookups to favour the more comment case for speed tests, etc.
svn path=/trunk/netsurf/; revision=3003
Diffstat (limited to 'utils')
-rw-r--r--utils/hashtable.c31
-rw-r--r--utils/hashtable.h2
2 files changed, 19 insertions, 14 deletions
diff --git a/utils/hashtable.c b/utils/hashtable.c
index 095419c47..967a8c651 100644
--- a/utils/hashtable.c
+++ b/utils/hashtable.c
@@ -123,7 +123,7 @@ bool hash_add(struct hash_table *ht, const char *key, const char *value)
return false;
}
- h = hash_string_fnv(key);
+ h = hash_string_fnv(key, &(e->key_length));
c = h % ht->nchains;
e->key = strdup(key);
@@ -141,7 +141,6 @@ bool hash_add(struct hash_table *ht, const char *key, const char *value)
return false;
}
- e->key_length = strlen(key);
e->next = ht->chain[c];
ht->chain[c] = e;
@@ -166,12 +165,12 @@ const char *hash_get(struct hash_table *ht, const char *key)
if (ht == NULL || key == NULL)
return NULL;
- h = hash_string_fnv(key);
+ h = hash_string_fnv(key, &key_length);
c = h % ht->nchains;
- key_length = strlen(key);
for (e = ht->chain[c]; e; e = e->next)
- if ((key_length == e->key_length) && (!strcmp(key, e->key)))
+ if ((key_length == e->key_length) &&
+ (memcmp(key, e->key, key_length) == 0))
return e->value;
return NULL;
@@ -184,12 +183,14 @@ const char *hash_get(struct hash_table *ht, const char *key)
* See http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash for more details.
*
* \param datum The string to hash.
+ * \param len Pointer to unsigned integer to record datum's length in.
* \return The calculated hash value for the datum.
*/
-unsigned int hash_string_fnv(const char *datum)
+unsigned int hash_string_fnv(const char *datum, unsigned int *len)
{
unsigned int z = 0x01000193;
+ *len = 0;
if (datum == NULL)
return 0;
@@ -197,6 +198,7 @@ unsigned int hash_string_fnv(const char *datum)
while (*datum) {
z *= 0x01000193;
z ^= *datum++;
+ (*len)++;
}
return z;
@@ -207,7 +209,7 @@ unsigned int hash_string_fnv(const char *datum)
*
* If you make changes to this hash table implementation, please rerun this
* test, and if possible, through valgrind to make sure there are no memory
- * leaks or invalid memory accesses.. If you add new functionality, please
+ * leaks or invalid memory accesses. If you add new functionality, please
* include a test for it that has good coverage along side the other tests.
*/
@@ -218,6 +220,7 @@ int main(int argc, char *argv[])
struct hash_table *a, *b;
FILE *dict;
char keybuf[BUFSIZ], valbuf[BUFSIZ];
+ int i;
a = hash_create(79);
assert(a != NULL);
@@ -275,13 +278,15 @@ int main(int argc, char *argv[])
hash_add(b, keybuf, valbuf);
}
- fseek(dict, 0, SEEK_SET);
+ for (i = 0; i < 5; i++) {
+ fseek(dict, 0, SEEK_SET);
- while (!feof(dict)) {
- fscanf(dict, "%s", keybuf);
- fscanf(dict, "%s", valbuf);
- assert(strcmp(hash_get(a, keybuf), valbuf) == 0);
- assert(strcmp(hash_get(b, keybuf), valbuf) == 0);
+ while (!feof(dict)) {
+ fscanf(dict, "%s", keybuf);
+ fscanf(dict, "%s", valbuf);
+ assert(strcmp(hash_get(a, keybuf), valbuf) == 0);
+ assert(strcmp(hash_get(b, keybuf), valbuf) == 0);
+ }
}
hash_destroy(a);
diff --git a/utils/hashtable.h b/utils/hashtable.h
index 6a7d312b6..e025a4865 100644
--- a/utils/hashtable.h
+++ b/utils/hashtable.h
@@ -19,6 +19,6 @@ struct hash_table *hash_create(unsigned int chains);
void hash_destroy(struct hash_table *ht);
bool hash_add(struct hash_table *ht, const char *key, const char *value);
const char *hash_get(struct hash_table *ht, const char *key);
-unsigned int hash_string_fnv(const char *datum);
+unsigned int hash_string_fnv(const char *datum, unsigned int *len);
#endif