From 97c84db00c01b808337bedf69f696a1517e3d8c0 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger Date: Fri, 11 Jan 2013 18:25:26 +0000 Subject: 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 [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 --- lib/hash.h | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'lib/hash.h') 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 *); -- cgit v1.2.1