#include "hashmap.h"

static uint32_t djb_hash(const char *s, uint32_t n)
{
	register uint32_t x = 5381;
	while (n--) x = (x << 5) + x + (*s++);
	return x;
}

static item_t *allocate_item(hashmap_t *hashmap)
{
	item_t *ptr = ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * hashmap->capacity);

	if (hashmap->items < hashmap->capacity)
	{
		for (int i = 0; i < hashmap->capacity; i++, ptr = ptradd(ptr, hashmap->stride))
		{
			if (!ptr->used)
			{
				ptr->used = F_USED;
				return ptr;
			}
		}
	}

	return NULL;
}

static unit_t *find_bucket_unit(hashmap_t *hashmap, const void *key, uint32_t keySize)
{
	unit_t *bucket = ptradd(hashmap, sizeof(hashmap_t));
	return &bucket[djb_hash(key, keySize) % hashmap->capacity];
}

static char find_previous_item(hashmap_t *hashmap, unit_t *list, item_t **tail, const void *key, uint32_t keySize)
{
	item_t *current = (item_t *)list;
	item_t *nextItem = ptradd(hashmap, current->next);

	while (nextItem && (nextItem->keySize != keySize || memcmp(ptradd(nextItem, sizeof(item_t)), key, keySize)))
	{
		current = nextItem;
		nextItem = ptradd(hashmap, current->next);
	}

	*tail = current;
	return nextItem != NULL;
}

long hashmap_ref(hashmap_t *hashmap)
{
	return __sync_add_and_fetch(&(hashmap->ref), 1);
}

long hashmap_unref(hashmap_t *hashmap)
{
	return __sync_sub_and_fetch(&(hashmap->ref), 1);
}

void hashmap_wipe(hashmap_t *hashmap)
{
	while (__sync_lock_test_and_set(&(hashmap->lock), F_LOCKED));

	hashmap->items = 0;

	for (uint32_t i = 0; i < hashmap->capacity; i++)
	{
		((unit_t *)ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * i))->count = 0;
		((unit_t *)ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * i))->offset = INVALID_OFFSET;
	}

	for (uint32_t i = 0; i < hashmap->capacity; i++)
	{
		((item_t *)ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * hashmap->capacity + hashmap->stride * i))->used = 0;
		((item_t *)ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * hashmap->capacity + hashmap->stride * i))->next = INVALID_OFFSET;
	}

	__sync_lock_release(&(hashmap->lock));
}

void hashmap_init(hashmap_t *hashmap, uint32_t capacity, uint32_t itemSpace)
{
	hashmap->ref = 0;
	hashmap->lock = 0;
	hashmap->items = 0;
	hashmap->stride = sizeof(item_t) + itemSpace;
	hashmap->capacity = capacity;

	for (uint32_t i = 0; i < capacity; i++)
	{
		((unit_t *)ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * i))->count = 0;
		((unit_t *)ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * i))->offset = INVALID_OFFSET;
	}

	for (uint32_t i = 0; i < capacity; i++)
	{
		((item_t *)ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * capacity + hashmap->stride * i))->used = 0;
		((item_t *)ptradd(hashmap, sizeof(hashmap_t) + sizeof(unit_t) * capacity + hashmap->stride * i))->next = INVALID_OFFSET;
	}
}

int hashmap_enum(hashmap_t *hashmap, enumerator_t enumerator, void *context)
{
	while (__sync_lock_test_and_set(&(hashmap->lock), F_LOCKED));

	int count = 0;
	unit_t *bucket = ptradd(hashmap, sizeof(hashmap_t));

	for (int i = 0; i < hashmap->capacity; i++)
	{
		item_t *item = (item_t *)&bucket[i];

		for (int j = 0; j < bucket[i].count; j++, count++)
		{
			item = ptradd(hashmap, item->next);
			enumerator(ptradd(item, sizeof(item_t)), item->keySize, context);
		}
	}

	__sync_lock_release(&(hashmap->lock));
	return count;
}

int hashmap_find(hashmap_t *hashmap, const void *key, uint32_t keySize, enumerator_t enumerator, void *context)
{
	while (__sync_lock_test_and_set(&(hashmap->lock), F_LOCKED));

	item_t *item = NULL;
	unit_t *unit = find_bucket_unit(hashmap, key, keySize);

	if (!find_previous_item(hashmap, unit, &item, key, keySize))
	{
		__sync_lock_release(&(hashmap->lock));
		return E_NO_ENTRY;
	}

	item_t *node = ptradd(hashmap, item->next);

	if (enumerator != NULL)
		enumerator(ptradd(node, sizeof(item_t) + node->keySize), node->valueSize, context);

	__sync_lock_release(&(hashmap->lock));
	return E_OK;
}

int hashmap_insert(hashmap_t *hashmap, const void *key, uint32_t keySize, const void *value, uint32_t valueSize)
{
	if (keySize + valueSize > hashmap->stride - sizeof(item_t))
		return E_TOO_LONG;

	while (__sync_lock_test_and_set(&(hashmap->lock), F_LOCKED));

	item_t *node = NULL;
	unit_t *unit = find_bucket_unit(hashmap, key, keySize);

	if (find_previous_item(hashmap, unit, &node, key, keySize))
	{
		item_t *next = ptradd(hashmap, node->next);

		next->valueSize = valueSize;
		memcpy(ptradd(next, sizeof(item_t) + next->keySize), value, valueSize);
	}
	else
	{
		item_t *item = allocate_item(hashmap);

		if (item == NULL)
		{
			__sync_lock_release(&(hashmap->lock));
			return E_MAP_FULL;
		}

		unit->count++;
		hashmap->items++;

		item->next = INVALID_OFFSET;
		node->next = ptrsub(item, hashmap);

		item->keySize = keySize;
		item->valueSize = valueSize;

		memcpy(ptradd(item, sizeof(item_t)), key, item->keySize);
		memcpy(ptradd(item, sizeof(item_t) + item->keySize), value, item->valueSize);
	}

	__sync_lock_release(&(hashmap->lock));
	return E_OK;
}

int hashmap_remove(hashmap_t *hashmap, const void *key, uint32_t keySize, enumerator_t enumerator, void *context)
{
	while (__sync_lock_test_and_set(&(hashmap->lock), F_LOCKED));

	item_t *item = NULL;
	unit_t *unit = find_bucket_unit(hashmap, key, keySize);

	if (!find_previous_item(hashmap, unit, &item, key, keySize))
	{
		__sync_lock_release(&(hashmap->lock));
		return E_NO_ENTRY;
	}

	item_t *node = ptradd(hashmap, item->next);

	if (enumerator != NULL)
		enumerator(ptradd(node, sizeof(item_t) + node->keySize), node->valueSize, context);

	unit->count--;
	hashmap->items--;

	node->used = 0;
	item->next = node->next;

	__sync_lock_release(&(hashmap->lock));
	return E_OK;
}