1 files changed, 250 insertions, 0 deletions
diff --git a/example_hashmap/old/map.h b/example_hashmap/old/map.h
new file mode 100644
index 0000000..db1e386
--- /dev/null
+++ b/example_hashmap/old/map.h
@@ -0,0 +1,250 @@
+#ifndef MAP_KEY
+#error "Need map key"
+#endif
+
+#ifndef MAP_TYPE
+#error "Need map type"
+#endif
+
+#ifndef MAP_CMP
+#error "Need map cmp"
+#endif
+
+#ifndef MAP_HASH
+#error "Need map hash"
+#endif
+
+#ifndef MAP_NAME
+#error "Need map name"
+#endif
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+#include "conts.h"
+
+#define MAP(a) CONTS_JOIN(MAP_NAME, a)
+
+#define MAP_TUPLE MAP(tuple)
+#define MAP_NODE MAP(node)
+#define MAP_BUCKET MAP(bucket)
+#define MAP_ROOT MAP_NAME
+
+#ifndef CONTS_MAP_H
+#define CONTS_MAP_H
+
+static inline size_t conts_map_generic_hash(const char *s, size_t l)
+{
+	/* djb2 */
+	size_t hash = 5381;
+	for (size_t i = 0; i < l; ++i)
+		hash = ((hash << 5) + hash) + s[i];
+
+	return hash;
+}
+
+#define CONTS_MAP_NO_HASH(a) (a)
+#define CONTS_MAP_STR_HASH(a) conts_map_generic_hash(a, strlen(a))
+
+/* fast modulo pow2 */
+#define CONTS_BUCKET_IDX(hash, pow2, bucket) \
+	((hash) & (((pow2) << bucket) - 1))
+
+#endif /* CONTS_MAP_H */
+
+static inline size_t MAP(generic_hash)(MAP_KEY *key)
+{
+	return conts_map_generic_hash((const char *)key, sizeof(*key));
+}
+
+struct MAP_TUPLE {
+	MAP_KEY key;
+	MAP_TYPE data;
+};
+
+typedef struct MAP_TUPLE *MAP(iter);
+
+struct MAP_NODE {
+	struct MAP_BUCKET *bucket;
+	size_t hash;
+	struct MAP_TUPLE t;
+};
+
+struct MAP_BUCKET {
+	size_t size; /* bucket size */
+	struct MAP_BUCKET *next;
+	struct MAP_NODE nodes[];
+};
+
+struct MAP_ROOT {
+	size_t len; /* number of items */
+	size_t count; /* bucket count */
+	size_t pow2; /* how many nodes in smallest bucket */
+	struct MAP_BUCKET **buckets;
+};
+
+static inline struct MAP_ROOT MAP(create)(size_t count)
+{
+	size_t pow2 = 1;
+	while (pow2 < count)
+		pow2 <<= 1;
+
+	return (struct MAP_ROOT){
+		.len = 0,
+		.count = 0,
+		.pow2 = pow2,
+		.buckets = NULL
+	};
+}
+
+static inline void MAP(destroy)(struct MAP_ROOT *root)
+{
+	for (size_t i = 0; i < root->count; ++i)
+		free(root->buckets[i]);
+
+	free(root->buckets);
+}
+
+static inline MAP_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY key, MAP_TYPE data)
+{
+	size_t hash = MAP_HASH(key);
+	/* look through buckets in order */
+	for (size_t b = 0; b < root->count; ++b) {
+		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;
+		}
+
+		/* 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 */
+	size_t size = root->pow2 << root->count;
+	size_t bytes = sizeof(struct MAP_BUCKET) + sizeof(struct MAP_NODE) * size;
+	struct MAP_BUCKET *bucket = calloc(1, bytes);
+	bucket->size = size;
+
+	size_t buckets_bytes = sizeof(struct MAP_BUCKET *) * (root->count + 1);
+	root->buckets = realloc(root->buckets, buckets_bytes);
+	if (root->count != 0)
+		root->buckets[root->count - 1]->next = bucket;
+
+	root->buckets[root->count] = bucket;
+
+	/* populate node */
+	size_t idx = CONTS_BUCKET_IDX(hash, root->pow2, root->count);
+	struct MAP_NODE *node = &bucket->nodes[idx];
+	node->bucket = bucket;
+	node->hash = hash;
+	node->t.key = key;
+	node->t.data = data;
+	root->count++;
+	root->len++;
+	return &node->t.data;
+}
+
+static inline MAP_TYPE *MAP(find)(struct MAP_ROOT *root, MAP_KEY key)
+{
+	if (root->len == 0)
+		return NULL;
+
+	size_t hash = MAP_HASH(key);
+	for (size_t b = 0; b < root->count; ++b) {
+		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;
+
+		if (MAP_CMP(node->t.key, key) != 0)
+			continue;
+
+		return &node->t.data;
+	}
+
+	return NULL;
+}
+
+static inline void MAP(remove_found)(struct MAP_ROOT *root, MAP_TYPE *data)
+{
+	struct MAP_TUPLE *tuple = CONTAINER_OF(data, struct MAP_TUPLE, data);
+	struct MAP_NODE *node = CONTAINER_OF(tuple, struct MAP_NODE, t);
+	node->bucket = NULL;
+	root->len--;
+}
+
+static inline void MAP(remove)(struct MAP_ROOT *root, MAP_KEY key)
+{
+	MAP_TYPE *found = MAP(find)(root, key);
+	if (!found)
+		return;
+
+	MAP(remove_found)(root, found);
+}
+
+static inline struct MAP_TUPLE *MAP(find_next)(struct MAP_BUCKET *bucket, struct MAP_TUPLE *tuple)
+{
+	struct MAP_NODE *node = CONTAINER_OF(tuple, struct MAP_NODE, t);
+	size_t idx = node - bucket->nodes;
+	for (; idx < bucket->size; ++idx) {
+		struct MAP_NODE *candidate = &bucket->nodes[idx];
+		if (candidate->bucket)
+			return &candidate->t;
+	}
+
+	struct MAP_BUCKET *next = bucket->next;
+	if (!next)
+		return NULL;
+
+	return MAP(find_next)(next, &next->nodes[0].t);
+}
+
+static inline struct MAP_TUPLE *MAP(begin)(struct MAP_ROOT *root)
+{
+	if (root->len == 0)
+		return NULL;
+
+	struct MAP_BUCKET *bucket = root->buckets[0];
+	return MAP(find_next)(bucket, &bucket->nodes[0].t);
+}
+
+static inline struct MAP_TUPLE *MAP(next)(struct MAP_TUPLE *t)
+{
+	struct MAP_NODE *node = CONTAINER_OF(t, struct MAP_NODE, t);
+	return MAP(find_next)(node->bucket, &(node + 1)->t);
+}
+
+static inline bool MAP(end)(struct MAP_ROOT *root, struct MAP_TUPLE *t)
+{
+	(void)root;
+	return t == NULL;
+}
+
+static inline size_t MAP(len)(struct MAP_ROOT *root)
+{
+	return root->len;
+}
+
+#undef MAP
+#undef MAP_NODE
+#undef MAP_TUPLE
+#undef MAP_BUCKET
+#undef MAP_ROOT
+#undef MAP_KEY
+#undef MAP_TYPE
+#undef MAP_CMP
+#undef MAP_HASH
+#undef MAP_NAME