From 537bc37805a5f33fe00a9b119ed218defae8232a Mon Sep 17 00:00:00 2001 From: Rob Kendrick Date: Sat, 19 Aug 2006 23:37:58 +0000 Subject: Slightly improve hash table for Messages file. Paves way for more generic use of it, as well as more constant performance. svn path=/trunk/netsurf/; revision=2870 --- utils/messages.c | 19 ++++++++++++++----- 1 file changed, 14 insertions(+), 5 deletions(-) (limited to 'utils/messages.c') diff --git a/utils/messages.c b/utils/messages.c index 3b5b6d662..05aae858f 100644 --- a/utils/messages.c +++ b/utils/messages.c @@ -21,7 +21,7 @@ #include "netsurf/utils/utils.h" /** We store the messages in a fixed-size hash table. */ -#define HASH_SIZE 77 +#define HASH_SIZE 101 /** Maximum length of a key. */ #define MAX_KEY_LENGTH 24 @@ -126,13 +126,22 @@ const char *messages_get(const char *key) * Hash function for keys. */ +/* This is Fowler Noll Vo - a very fast and simple hash ideal for short + * strings. See http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash for more + * details. + */ unsigned int messages_hash(const char *s) { - unsigned int i, z = 0; - if (!s) + unsigned int z = 0x01000193, i; + + if (s == NULL) return 0; - for (i = 0; i != MAX_KEY_LENGTH && s[i]; i++) - z += s[i] & 0x1f; /* lower 5 bits, case insensitive */ + + for (i = 0; i != MAX_KEY_LENGTH && s[i]; i++) { + z *= 0x01000193; + z ^= (s[i] & 0x1f); /* lower 5 bits, case insensitive */ + } + return z % HASH_SIZE; } -- cgit v1.2.3