reduce map memory usage significantly

+ Comes at some runtime cost, unfortunately

1 files changed, 37 insertions, 19 deletions

diff --git a/include/conts/map.h b/include/conts/map.h
index e3f0b2f..6b62498 100644
--- a/include/conts/map.h
+++ b/include/conts/map.h
@@ -50,6 +50,9 @@
 #ifndef CONTS_MAP_H
 #define CONTS_MAP_H
 
+/* how many times to retry placing an element in a bucket */
+#define CONTS_MAP_PACKING 4
+
 static inline size_t conts_map_generic_hash(const char *s, size_t l)
 {
 	/* djb2 */
@@ -130,20 +133,26 @@ static inline MAP_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY key, MAP_TYPE
 		struct MAP_BUCKET *bucket = root->buckets[b];
 		size_t idx = CONTS_BUCKET_IDX(hash, root->pow2, b);
 
-		struct MAP_NODE *node = &bucket->nodes[idx];
-		/* free to use this slot */
-		if (!node->bucket) {
-			node->bucket = bucket;
-			node->hash = hash;
-			node->t.data = data;
-			node->t.key = key;
-			root->len++;
-			return &node->t.data;
+		for (size_t p = 0; p < CONTS_MAP_PACKING; ++p) {
+			size_t n = idx + p;
+			if (n >= bucket->size)
+				break;
+
+			struct MAP_NODE *node = &bucket->nodes[n];
+			/* free to use this slot */
+			if (!node->bucket) {
+				node->bucket = bucket;
+				node->hash = hash;
+				node->t.data = data;
+				node->t.key = key;
+				root->len++;
+				return &node->t.data;
+			}
+
+			/* there already exists a node like this */
+			if (node->hash == hash && MAP_CMP(node->t.key, key) == 0)
+				return &node->t.data;
 		}
-
-		/* there already exists a node like this */
-		if (node->hash == hash && MAP_CMP(node->t.key, key) == 0)
-			return &node->t.data;
 	}
 
 	/* no bucket available, create new one */
@@ -190,14 +199,23 @@ static inline MAP_TYPE *MAP(find)(struct MAP_ROOT *root, MAP_KEY key)
 		struct MAP_BUCKET *bucket = root->buckets[b];
 		size_t idx = CONTS_BUCKET_IDX(hash, root->pow2, b);
 
-		struct MAP_NODE *node = &bucket->nodes[idx];
-		if (node->hash != hash)
-			continue;
+		for (size_t p = 0; p < CONTS_MAP_PACKING; ++p) {
+			size_t n = idx + p;
+			if (n >= bucket->size)
+				break;
+
+			struct MAP_NODE *node = &bucket->nodes[n];
 
-		if (MAP_CMP(node->t.key, key) != 0)
-			continue;
+			/* note no gravestones */
 
-		return &node->t.data;
+			if (node->hash != hash)
+				continue;
+
+			if (MAP_CMP(node->t.key, key) != 0)
+				continue;
+
+			return &node->t.data;
+		}
 	}
 
 	return NULL;