summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorStephen Hemminger <shemminger@vyatta.com>2010-08-27 14:11:14 -0700
committerPaul Jakma <paul@quagga.net>2011-03-21 13:30:54 +0000
commit6392aa83c4f895ebbd23817c68d9b0da0de2e0f8 (patch)
tree535c89a194ec7fd3b9f4a6e33ceab10579e62329
parent25ff1e88bb5f1b0a16a364d7206db3ebdc5ecf52 (diff)
lib: Better hashing of string values using Bernstein hash
* hash.{h,c}: (string_hash_make) Hash optimised for strings, current implementation using Bernstein hash, which offers a good compromise between distribution and performance. * distribute.c: (distribute_hash_make) use previous instead of additive string hash. * if_rmap.c: (if_rmap_hash_make) ditto
-rw-r--r--lib/distribute.c13
-rw-r--r--lib/hash.c11
-rw-r--r--lib/hash.h2
-rw-r--r--lib/if_rmap.c9
4 files changed, 19 insertions, 16 deletions
diff --git a/lib/distribute.c b/lib/distribute.c
index 242a225c..420849da 100644
--- a/lib/distribute.c
+++ b/lib/distribute.c
@@ -114,16 +114,11 @@ distribute_get (const char *ifname)
}
static unsigned int
-distribute_hash_make (struct distribute *dist)
+distribute_hash_make (void *arg)
{
- unsigned int i, key;
+ const struct distribute *dist = arg;
- key = 0;
- if (dist->ifname)
- for (i = 0; i < strlen (dist->ifname); i++)
- key += dist->ifname[i];
-
- return key;
+ return dist->ifname ? string_hash_make (dist->ifname) : 0;
}
/* If two distribute-list have same value then return 1 else return
@@ -763,7 +758,7 @@ distribute_list_reset ()
void
distribute_list_init (int node)
{
- disthash = hash_create ((unsigned int (*) (void *)) distribute_hash_make,
+ disthash = hash_create (distribute_hash_make,
(int (*) (const void *, const void *)) distribute_cmp);
if(node==RIP_NODE) {
diff --git a/lib/hash.c b/lib/hash.c
index 672327ec..6db79ea7 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -101,6 +101,17 @@ hash_lookup (struct hash *hash, void *data)
return hash_get (hash, data, NULL);
}
+/* Simple Bernstein hash which is simple and fast for common case */
+unsigned int string_hash_make (const char *str)
+{
+ unsigned int hash = 0;
+
+ while (*str)
+ hash = (hash * 33) ^ (unsigned int) *str++;
+
+ return hash;
+}
+
/* This function release registered value from specified hash. When
release is successfully finished, return the data pointer in the
hash backet. */
diff --git a/lib/hash.h b/lib/hash.h
index f4b1c23e..4cb772e5 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -70,4 +70,6 @@ extern void hash_iterate (struct hash *,
extern void hash_clean (struct hash *, void (*) (void *));
extern void hash_free (struct hash *);
+extern unsigned int string_hash_make (const char *);
+
#endif /* _ZEBRA_HASH_H */
diff --git a/lib/if_rmap.c b/lib/if_rmap.c
index ddc62fd5..9774be4b 100644
--- a/lib/if_rmap.c
+++ b/lib/if_rmap.c
@@ -109,14 +109,9 @@ if_rmap_get (const char *ifname)
static unsigned int
if_rmap_hash_make (void *data)
{
- struct if_rmap *if_rmap = data;
- unsigned int i, key;
+ const struct if_rmap *if_rmap = data;
- key = 0;
- for (i = 0; i < strlen (if_rmap->ifname); i++)
- key += if_rmap->ifname[i];
-
- return key;
+ return string_hash_make (if_rmap->ifname);
}
static int