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 <equinox@opensourcerouting.org>
diff --git a/lib/hash.c b/lib/hash.c
index 6db79ea..1e097f2 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -31,6 +31,7 @@
{
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 @@
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 @@
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)
{