#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