summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorStephen Hemminger <shemminger@vyatta.com>2013-01-11 18:25:26 +0000
committerDavid Lamparter <equinox@opensourcerouting.org>2013-02-24 20:48:16 +0100
commit97c84db00c01b808337bedf69f696a1517e3d8c0 (patch)
tree1af03fc32c0fc938c148ebdf3ad1eb812e254efc /lib
parent90645f5598ca8b25cd2692f2ac0d2778a3fd2755 (diff)
hash: dynamically grow hash table
Dynamically grow the hash table index if the chains get too long. If expansion doesn't help keep chain length short, then stop expanding, to avoid bad behavior if there is a poor hash function. Not a new idea, based on concepts in uthash. Depends on my previous patch to restrict hash to power of 2. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> [profiling results: sum of cycles spent in hash_get/jhash with RIPE RIS test data (single simple BGP peer) improved to 69% of previously spent] Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/hash.c65
-rw-r--r--lib/hash.h6
2 files changed, 66 insertions, 5 deletions
diff --git a/lib/hash.c b/lib/hash.c
index 1e097f28..987012a5 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -48,7 +48,7 @@ struct hash *
hash_create (unsigned int (*hash_key) (void *),
int (*hash_cmp) (const void *, const void *))
{
- return hash_create_size (HASHTABSIZE, hash_key, hash_cmp);
+ return hash_create_size (HASH_INITIAL_SIZE, hash_key, hash_cmp);
}
/* Utility function for hash_get(). When this function is specified
@@ -60,6 +60,52 @@ hash_alloc_intern (void *arg)
return arg;
}
+/* Expand hash if the chain length exceeds the threshold. */
+static void hash_expand (struct hash *hash)
+{
+ unsigned int i, new_size, losers;
+ struct hash_backet *hb, *hbnext, **new_index;
+
+ new_size = hash->size * 2;
+ new_index = XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_backet *) * new_size);
+ if (new_index == NULL)
+ return;
+
+ for (i = 0; i < hash->size; i++)
+ for (hb = hash->index[i]; hb; hb = hbnext)
+ {
+ unsigned int h = hb->key & (new_size - 1);
+
+ hbnext = hb->next;
+ hb->next = new_index[h];
+ new_index[h] = hb;
+ }
+
+ /* Switch to new table */
+ XFREE(MTYPE_HASH_INDEX, hash->index);
+ hash->size = new_size;
+ hash->index = new_index;
+
+ /* Ideally, new index should have chains half as long as the original.
+ If expansion didn't help, then not worth expanding again,
+ the problem is the hash function. */
+ losers = 0;
+ for (i = 0; i < hash->size; i++)
+ {
+ unsigned int len = 0;
+ for (hb = hash->index[i]; hb; hb = hb->next)
+ {
+ if (++len > HASH_THRESHOLD/2)
+ ++losers;
+ if (len >= HASH_THRESHOLD)
+ hash->no_expand = 1;
+ }
+ }
+
+ if (losers > hash->count / 2)
+ hash->no_expand = 1;
+}
+
/* Lookup and return hash backet in hash. If there is no
corresponding hash backet and alloc_func is specified, create new
hash backet. */
@@ -69,14 +115,19 @@ hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
unsigned int key;
unsigned int index;
void *newdata;
+ unsigned int len;
struct hash_backet *backet;
key = (*hash->hash_key) (data);
index = key & (hash->size - 1);
+ len = 0;
- for (backet = hash->index[index]; backet != NULL; backet = backet->next)
- if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
- return backet->data;
+ for (backet = hash->index[index]; backet != NULL; backet = backet->next)
+ {
+ if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
+ return backet->data;
+ ++len;
+ }
if (alloc_func)
{
@@ -84,6 +135,12 @@ hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
if (newdata == NULL)
return NULL;
+ if (len > HASH_THRESHOLD && !hash->no_expand)
+ {
+ hash_expand (hash);
+ index = key & (hash->size - 1);
+ }
+
backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
backet->data = newdata;
backet->key = key;
diff --git a/lib/hash.h b/lib/hash.h
index a6dd5319..920c6685 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -22,7 +22,8 @@ Boston, MA 02111-1307, USA. */
#define _ZEBRA_HASH_H
/* Default hash table size. */
-#define HASHTABSIZE 1024
+#define HASH_INITIAL_SIZE 256 /* initial number of backets. */
+#define HASH_THRESHOLD 10 /* expand when backet. */
struct hash_backet
{
@@ -44,6 +45,9 @@ struct hash
/* Hash table size. Must be power of 2 */
unsigned int size;
+ /* If expansion failed. */
+ int no_expand;
+
/* Key make function. */
unsigned int (*hash_key) (void *);