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>

1 files changed, 5 insertions, 1 deletions

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 *);