path: root/src/htgen.h

/* config */

#include "xxhash.h"
#include <stdlib.h>
#include <string.h>

#if 1
#define HT_PREFIX  shash_
#define HT_VALTYPE char *
#define HT_VALTYPE_CREF const char *

/* should be able to be cast to uintmax_t without losing information */
#define HT_HASHTYPE XXH64_hash_t
#define HT_KEY_HASH(_val, _sz) XXH3_64bits(_val, _sz)

/* default load factor if variable: #define HT_LOADFACTOR_DEF (0.75f) */
/* or define a static load factor: #define HT_LOADFACTOR (0.75f) */

/* should take HT_VALTYPE_CREF and return HT_VALTYPE */
#define HT_VAL_COPY(_val, _sz) _strdup(_val)

/* #define HT_VAL_STATIC_LEN sizeof(int) */
#define HT_VAL_GUESS_LEN(_val) strlen(_val)
#define HT_VAL_FREE(_val) free(_val)

#define HT_VAL_SENTINEL NULL

#define HT_KEYTYPE char *
#define HT_KEYTYPE_CREF const char *

/* will receive two HT_KEYTYPEs */
/* bad equality function LOL */
#define HT_KEY_EQ(_val1, _len1, _val2, _len2) (((_len1) == (_len2)) && !strcmp(_val1, _val2))

#define HT_KEY_COPY(_key, _sz) (_strdup(_key))
#define HT_KEY_FREE(_key) free(_key)

/* #define HT_KEY_STATIC_LEN sizeof(int) */
#define HT_KEY_GUESS_LEN(_val) strlen(_val)
#else

XXH64_hash_t ihash_hash_int(int i)
{
	return XXH3_64bits(&i, sizeof(int));
}

#define HT_PREFIX ihash_
#define HT_VALTYPE int
#define HT_VALTYPE_CREF int

#define HT_HASHTYPE XXH64_hash_t
#define HT_VAL_HASH(_val, _sz) ihash_hash_int(_val)

#define HT_VAL_COPY(_val, _sz) _val

/* #define HT_VAL_STATIC_LEN sizeof(int) */
#define HT_VAL_STATIC_LEN sizeof(int)

/* will receive two HT_KEYTYPEs */
#define HT_KEY_EQ(_val1, _val2) ((_val1) == (_val2))

#define HT_KEYTYPE int
#define HT_KEYTYPE_CREF int
#endif

#define HT_MALLOC(_sz) malloc(_sz)
#define HT_CALLOC(_num, _sz) calloc(_num, _sz)
#define HT_REALLOC(_ptr, _newsz) realloc(_ptr, _newsz)
#define HT_FREE(_p) free(_p)

/* declarations */

#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>

#define HT__CONCAT(_t1, _t2)  HT__CONCAT2(_t1, _t2)
#define HT__CONCAT2(_t1, _t2) _t1 ## _t2

#define HT__STR(_x) HT__STR2(_x)
#define HT__STR2(_x) #_x

#define HT__NS(_n) HT__CONCAT(HT_PREFIX, _n)
#define HT__TYPE HT__NS(t)
#define HT__TAG HT__NS(_ht_tag)

typedef struct HT__TAG HT__TYPE;

HT__TYPE *HT__NS(new)(void);

#ifdef HT_LOADFACTOR
#define HT__CREATE_SIG size_t cap
#else
#define HT__CREATE_SIG size_t cap, float load_factor
#endif

HT__TYPE *HT__NS(create)(HT__CREATE_SIG);

void HT__NS(free)(HT__TYPE *ht);

HT_VALTYPE HT__NS(get)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found);
HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found);

int HT__NS(put)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val);
int HT__NS(putn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen);

HT_VALTYPE HT__NS(swap)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val);
HT_VALTYPE HT__NS(swapn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t *vallen);

/* implementations */

#if defined(HT_IMPLEMENTATIONS) || 1

#define HT__NODE HT__NS(_node)

#ifdef HT_LOADFACTOR
#define HT__LOADFACTOR_FIXED HT_LOADFACTOR
#define HT__LOADFACTOR(_unused) HT_LOADFACTOR
#else
#define HT__LOADFACTOR(_ht) ((_ht)->load_factor)
#endif

#ifdef HT_KEY_STATIC_LEN
#define HT__NODE_KEYLEN(_node) HT_KEY_STATIC_LEN
#define HT__NODE_KEYLEN_SET(_node, _unused)
#define HT__GUESS_KEYLEN(_node) HT_KEY_STATIC_LEN
#else
#define HT__NODE_KEYLEN(_node) ((_node)->keylen)
#define HT__NODE_KEYLEN_SET(_node, _len) (((_node)->keylen) = (_len))
#define HT__GUESS_KEYLEN(_key) HT_KEY_GUESS_LEN(_key)
#endif

#ifdef HT_VAL_STATIC_LEN
#define HT__NODE_VALLEN(_node) HT_VAL_STATIC_LEN
#define HT__NODE_VALLEN_SET(_node, _unused)
#define HT__GUESS_VALLEN(_val) HT_VAL_STATIC_LEN
#else
#define HT__NODE_VALLEN(_node) ((_node)->vallen)
#define HT__NODE_VALLEN_SET(_node, _len) (((_node)->vallen) = (_len))
#define HT__GUESS_VALLEN(_val) HT_VAL_GUESS_LEN(_val)
#endif

#ifndef HT_VAL_FREE
#define HT_VAL_FREE(_val)
#endif

#ifndef HT_LOADFACTOR_DEF
#define HT_LOADFACTOR_DEF (0.75f)
#endif

#ifndef HT_VAL_SENTINEL
#define HT_VAL_SENTINEL((HT_VALTYPE)0)
#endif

#define HT__HASHTYPE HT__NS(_hash_t)
typedef HT_HASHTYPE HT__HASHTYPE;
#undef HT_HASHTYPE /* use the typedef (it acts better) */

typedef struct {
#ifndef HT_VAL_STATIC_LEN
	size_t vallen;
#endif

	HT_VALTYPE val;

#ifndef HT_KEY_STATIC_LEN
	size_t keylen;
#endif

	HT_KEYTYPE key;
	HT__HASHTYPE hash;

	bool full:1;
	bool deleted:1;
} HT__NODE;


struct HT__TAG {
	size_t capacity; /* hash table capacity (number of elements in table) */
	size_t rsize;    /* real size (number of elements full) */
	size_t asize;    /* active size (number of elements full and not deleted) */

#ifndef HT__LOADFACTOR_FIXED
	float load_factor;
#endif

	HT__NODE *table;
};

HT__TYPE *HT__NS(new)(void)
{
#ifdef HT__LOADFACTOR_FIXED
	return HT__NS(create)(0);
#else
	return HT__NS(create)(0, HT_LOADFACTOR_DEF);
#endif
}

HT__TYPE *HT__NS(create)(HT__CREATE_SIG)
{
	HT__TYPE *ht = HT_CALLOC(1, sizeof(HT__TYPE));
	if (!ht) return NULL;

#ifndef HT_LOADFACTOR
	if (load_factor < 0.0f || load_factor > 1.0f) {
		goto cleanup;
	} else if (load_factor == 0.0f) {
		load_factor = HT_LOADFACTOR_DEF;
	}

	ht->load_factor = load_factor;
#endif

	if (cap == 0) cap = 16;

	ht->capacity = cap;
	ht->table = HT_CALLOC(cap, sizeof(HT__NODE));
	if (!ht->table) {
		goto cleanup;
	}

	return ht;

cleanup:
	HT_FREE(ht->table);
	HT_FREE(ht);
	return NULL;
}

void HT__NS(free)(HT__TYPE *ht)
{
	/* TODO: free all elements */
	if (!ht) return;

	free(ht->table);
	free(ht);
}

HT__NODE *HT__NS(_search)(HT__TYPE *ht, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, bool vacant)
{
	size_t tryidx = (size_t)((uintmax_t)hash % ht->capacity);
	size_t start = tryidx;

	HT__NODE *node;

	fprintf(stderr, "debug: trying %zu for %s\n", tryidx, key);

	do {
		node = ht->table + tryidx;

		if (node->full && !node->deleted && node->hash == hash && HT_KEY_EQ(node->key, HT__NODE_KEYLEN(node), key, keylen)) {
			fprintf(stderr, "found node %zu: matches\n", tryidx);
			return node;
		}

		if (vacant) {
			if (!node->full || node->deleted) {
				fprintf(stderr, "found node %zu: empty\n", tryidx);
				return node;
			}
		}

		tryidx = (tryidx + 1) % ht->capacity;
	} while (tryidx != start);

	return NULL;
}

int HT__NS(_node_set)(HT__TYPE *ht, HT__NODE *node, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen)
{
	if (node->full) {
		if (!node->deleted) {
			/* same key already present! replace */
			HT_VAL_FREE(node->val);

			node->val = HT_VAL_COPY(val, vallen);
			if (!node->val) return -1;

			HT__NODE_VALLEN_SET(node, vallen);

			/* size left unchanged (key replaced) */
			return 0;
		}

		node->key = HT_KEY_COPY(key, keylen);
		HT__NODE_KEYLEN_SET(node, keylen);
		node->hash = hash;

		node->val = HT_VAL_COPY(val, vallen);
		HT__NODE_VALLEN_SET(node, vallen);

		if (!node->val || !node->key) {
			HT_KEY_FREE(node->key);
			HT_VAL_FREE(node->val);
			return -1;
		}

		node->deleted = false; /* node is now filled */
		++ht->asize;
		return 0;
	}

	/* fully new key */

	node->key = HT_KEY_COPY(key, keylen);
	HT__NODE_KEYLEN_SET(node, keylen);
	node->hash = hash;

	node->val = HT_VAL_COPY(val, vallen);
	HT__NODE_VALLEN_SET(node, vallen);

	if (!node->val || !node->key) {
		HT_KEY_FREE(node->key);
		HT_VAL_FREE(node->val);
		return -1;
	}

	node->deleted = false;
	node->full = true;

	++ht->rsize;
	++ht->asize;

	if (!node->val) return -1;

	return 0;
}

int HT__NS(put)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val)
{
	return HT__NS(putn)(ht, key, 0, val, 0);
}

int HT__NS(putn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen)
{
	if (!keylen) keylen = HT__GUESS_KEYLEN(key);
	if (!vallen) vallen = HT__GUESS_VALLEN(val);

	const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen);

	if (ht->capacity * HT__LOADFACTOR(ht) < (ht->asize + 1)) {
		/* TODO: rehash */
		fprintf(stderr, "Not rehashing (cap %zu, asize %zu)\n", ht->capacity, ht->asize);
	}

	HT__NODE *node = HT__NS(_search)(ht, hash, key, keylen, true);

	if (!node) { /* no vacant slots found */
		return -1; /* table is full or something! */
	}

	return HT__NS(_node_set)(ht, node, hash, key, keylen, val, vallen);
}

HT_VALTYPE HT__NS(get)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found)
{
	return HT__NS(getn)(ht, key, 0, found);
}

HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found)
{
	if (!keylen) keylen = HT__GUESS_KEYLEN(key);

	const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen);
	HT__NODE *node = HT__NS(_search)(ht, hash, key, keylen, false);

	if (!node) {
		if (found) *found = false;
		return HT_VAL_SENTINEL;
	}

	*found = true;
	return node->val;
}

void HT__NS(_debug_table)(HT__TYPE *ht)
{
	fprintf(stderr, HT__STR(HT__TYPE) " debug: cap: %zu, asize: %zu, rsize: %zu, lf: %f\n",
		ht->capacity, ht->asize, ht->rsize, HT__LOADFACTOR(ht));
	
	for (size_t n = 0; n < ht->capacity; ++n) {
		fprintf(stderr, "%zu: ", n);
		if (ht->table[n].full) {
			if (ht->table[n].deleted) {
				fprintf(stderr, "(deleted)\n");
			} else {
				fprintf(stderr, "(full %s:%s)\n", ht->table[n].key, ht->table[n].val);
			}
		} else {
			fprintf(stderr, "(empty)\n");
		}
	}
}

#endif