diff options
author | Stephen Hemminger <shemminger@vyatta.com> | 2013-01-04 22:29:21 +0000 |
---|---|---|
committer | David Lamparter <equinox@opensourcerouting.org> | 2013-02-24 20:42:40 +0100 |
commit | 90645f5598ca8b25cd2692f2ac0d2778a3fd2755 (patch) | |
tree | 2b5e67b020eb3f7a2fd9df4faf2f0914e0cbf0cf | |
parent | 44a86a0278c1678fd4b8dfa56c4f5f2feb6df3ad (diff) |
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>
-rw-r--r-- | bgpd/bgp_aspath.c | 2 | ||||
-rw-r--r-- | lib/hash.c | 5 | ||||
-rw-r--r-- | lib/hash.h | 2 | ||||
-rw-r--r-- | lib/thread.c | 4 |
4 files changed, 7 insertions, 6 deletions
diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c index c37a8897..a8b078ff 100644 --- a/bgpd/bgp_aspath.c +++ b/bgpd/bgp_aspath.c @@ -1856,7 +1856,7 @@ aspath_cmp (const void *arg1, const void *arg2) void aspath_init (void) { - ashash = hash_create_size (32767, aspath_key_make, aspath_cmp); + ashash = hash_create_size (32768, aspath_key_make, aspath_cmp); } void @@ -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) { @@ -41,7 +41,7 @@ struct hash /* Hash backet. */ struct hash_backet **index; - /* Hash table size. */ + /* Hash table size. Must be power of 2 */ unsigned int size; /* Key make function. */ diff --git a/lib/thread.c b/lib/thread.c index 16c92c24..27c29d6c 100644 --- a/lib/thread.c +++ b/lib/thread.c @@ -531,8 +531,8 @@ thread_master_create () { if (cpu_record == NULL) cpu_record - = hash_create_size (1011, (unsigned int (*) (void *))cpu_record_hash_key, - (int (*) (const void *, const void *))cpu_record_hash_cmp); + = hash_create ((unsigned int (*) (void *))cpu_record_hash_key, + (int (*) (const void *, const void *))cpu_record_hash_cmp); return (struct thread_master *) XCALLOC (MTYPE_THREAD_MASTER, sizeof (struct thread_master)); |