From 90645f5598ca8b25cd2692f2ac0d2778a3fd2755 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger Date: Fri, 4 Jan 2013 22:29:21 +0000 Subject: hash: force size to be a power of 2 By forcing the hash table size to be a power of 2, a potentially expensive divide can be replaced by a mask operation. Almost all usage of the hash table was using default size of 1024. Only places with different size was thread library (1011) and bgp aspath. Signed-off-by: David Lamparter --- lib/hash.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'lib/hash.c') diff --git a/lib/hash.c b/lib/hash.c index 6db79ea7..1e097f28 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -31,6 +31,7 @@ hash_create_size (unsigned int size, unsigned int (*hash_key) (void *), { struct hash *hash; + assert ((size & (size-1)) == 0); hash = XMALLOC (MTYPE_HASH, sizeof (struct hash)); hash->index = XCALLOC (MTYPE_HASH_INDEX, sizeof (struct hash_backet *) * size); @@ -71,7 +72,7 @@ hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *)) struct hash_backet *backet; key = (*hash->hash_key) (data); - index = key % hash->size; + index = key & (hash->size - 1); for (backet = hash->index[index]; backet != NULL; backet = backet->next) if (backet->key == key && (*hash->hash_cmp) (backet->data, data)) @@ -125,7 +126,7 @@ hash_release (struct hash *hash, void *data) struct hash_backet *pp; key = (*hash->hash_key) (data); - index = key % hash->size; + index = key & (hash->size - 1); for (backet = pp = hash->index[index]; backet; backet = backet->next) { -- cgit v1.2.1