3 files changed, 424 insertions, 0 deletions
diff --git a/src/htgen.h b/src/htgen.h
new file mode 100644
index 0000000..0b03886
--- /dev/null
+++ b/src/htgen.h
@@ -0,0 +1,395 @@
+/* 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
diff --git a/src/libmain.c b/src/libmain.c
new file mode 100644
index 0000000..eca383a
--- /dev/null
+++ b/src/libmain.c
@@ -0,0 +1,28 @@
+#include "xxhash.h"
+#include <string.h>
+
+#include <stdint.h>
+#include <stdio.h>
+
+#define HT_IMPLEMENTATIONS
+#include "htgen.h"
+
+int main(int argc, char **argv) {
+	shash_t *hash = shash_create(8, 0.75f);
+	printf("%d\n", shash_put(hash, "test1", "test2"));
+	printf("%d\n", shash_put(hash, "abc", "def"));
+	printf("%d\n", shash_put(hash, "amingus", "val"));
+	printf("%d\n", shash_put(hash, "afungus", "val2"));
+	printf("%d\n", shash_put(hash, "abungus", "val3"));
+	printf("%d\n", shash_put(hash, "lethalbumpany", "crewmate_sus"));
+	printf("%d\n", shash_put(hash, "uuuu", "something"));
+	printf("%d\n", shash_put(hash, "99asdas", "please collide >:O"));
+
+	bool found = false;
+	char *val = shash_getn(hash, "99asdas", 0, &found);
+	printf("%s %d\n", val ? val : "(null)", found);
+
+	shash__debug_table(hash);
+	
+	return 0;
+}
diff --git a/src/meson.build b/src/meson.build
new file mode 100644
index 0000000..a2cf6d0
--- /dev/null
+++ b/src/meson.build
@@ -0,0 +1 @@
+libworld_sources = files('libmain.c')