1 files changed, 0 insertions, 461 deletions

diff --git a/src/hamt.c b/src/hamt.c
deleted file mode 100644
index f9bd8b2..0000000
--- a/src/hamt.c
+++ /dev/null
@@ -1,461 +0,0 @@
-#include "hamt.h"
-
-#include <assert.h>
-#include <stdbool.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-/* Pointer tagging */
-#define HAMT_TAG_MASK 0x3 /* last two bits */
-#define HAMT_TAG_VALUE 0x1
-#define tagged(__p) (hamt_node *)((uintptr_t)__p | HAMT_TAG_VALUE)
-#define untagged(__p) (hamt_node *)((uintptr_t)__p & ~HAMT_TAG_MASK)
-#define is_value(__p) (((uintptr_t)__p & HAMT_TAG_MASK) == HAMT_TAG_VALUE)
-
-/* Bit fiddling */
-#define index_clear_bit(_index, _n) _index & ~(1ul << _n)
-#define index_set_bit(_index, _n) _index | (1ul << _n)
-
-/* Node data structure */
-#define TABLE(a) a->as.table.ptr
-#define INDEX(a) a->as.table.index
-#define VALUE(a) a->as.kv.value
-#define KEY(a) a->as.kv.key
-
-/* Memory management */
-#define mem_alloc(ator, size) (ator)->malloc(size)
-#define mem_realloc(ator, ptr, size) (ator)->realloc(ptr, size)
-#define mem_free(ator, ptr) (ator)->free(ptr)
-/* Default allocator uses system malloc */
-struct hamt_allocator hamt_allocator_default = { malloc, realloc, free };
-
-typedef struct hamt_node {
-	union {
-		struct {
-			void *value; /* tagged pointer */
-			const void *key;
-		} kv;
-		struct {
-			struct hamt_node *ptr;
-			uint32_t index;
-		} table;
-	} as;
-} hamt_node;
-
-struct hamt_stats {
-	size_t table_sizes[32];
-};
-
-/* Opaque user-facing implementation */
-struct hamt_impl {
-	struct hamt_node *root;
-	size_t size;
-	hamt_key_hash_fn key_hash;
-	hamt_cmp_fn key_cmp;
-	struct hamt_allocator *ator;
-	struct hamt_stats stats;
-};
-
-/* hash_stateing w/ state management */
-typedef struct hash_state {
-	const void *key;
-	hamt_key_hash_fn hash_fn;
-	uint32_t hash;
-	size_t depth;
-	size_t shift;
-} hash_state;
-
-/* Search results */
-typedef enum {
-	SEARCH_SUCCESS,
-	SEARCH_FAIL_NOTFOUND,
-	SEARCH_FAIL_KEYMISMATCH
-} search_status;
-
-typedef struct search_result {
-	search_status status;
-	hamt_node *anchor;
-	hamt_node *value;
-	hash_state *hash;
-} search_result;
-
-/* Removal results */
-typedef enum { REMOVE_SUCCESS, REMOVE_GATHERED, REMOVE_NOTFOUND } remove_status;
-
-typedef struct remove_result {
-	remove_status status;
-	void *value;
-} remove_result;
-
-typedef struct path_result {
-	union {
-		search_result sr;
-		remove_result rr;
-	} u;
-	hamt_node *root;
-} path_result;
-
-static inline hash_state *hash_next(hash_state *h)
-{
-	h->depth += 1;
-	h->shift += 5;
-	if (h->shift > 30) {
-		h->hash = h->hash_fn(h->key, h->depth / 5);
-		h->shift = 0;
-	}
-	return h;
-}
-
-static inline uint32_t hash_get_index(const hash_state *h)
-{
-	return (h->hash >> h->shift) & 0x1f;
-}
-
-static int get_popcount(uint32_t n)
-{
-	return __builtin_popcount(n);
-}
-
-static int get_pos(uint32_t sparse_index, uint32_t bitmap)
-{
-	return get_popcount(bitmap & ((1ul << sparse_index) - 1));
-}
-
-static inline bool has_index(const hamt_node *anchor, size_t index)
-{
-	assert(anchor && "anchor must not be NULL");
-	assert(index < 32 && "index must not be larger than 31");
-	return INDEX(anchor) & (1ul << index);
-}
-
-static hamt_node *table_allocate(struct hamt_impl *h, size_t size)
-{
-	if (size)
-		h->stats.table_sizes[size - 1] += 1;
-	return (hamt_node *)mem_alloc(h->ator, (size * sizeof(hamt_node)));
-}
-
-static void table_free(struct hamt_impl *h, hamt_node *ptr, size_t size)
-{
-	mem_free(h->ator, ptr);
-	if (size)
-		h->stats.table_sizes[size - 1] -= 1;
-}
-
-static hamt_node *table_extend(struct hamt_impl *h, hamt_node *anchor,
-			       size_t n_rows, uint32_t index, uint32_t pos)
-{
-	hamt_node *new_table = table_allocate(h, n_rows + 1);
-	if (!new_table)
-		return NULL;
-	if (n_rows > 0) {
-		/* copy over table */
-		memcpy(&new_table[0], &TABLE(anchor)[0],
-		       pos * sizeof(hamt_node));
-		/* note: this works since (n_rows - pos) == 0 for cases
-         * where we're adding the new k/v pair at the end (i.e. memcpy(a, b, 0)
-         * is a nop) */
-		memcpy(&new_table[pos + 1], &TABLE(anchor)[pos],
-		       (n_rows - pos) * sizeof(hamt_node));
-	}
-	assert(!is_value(VALUE(anchor)) && "URGS");
-	table_free(h, TABLE(anchor), n_rows);
-	TABLE(anchor) = new_table;
-	INDEX(anchor) |= (1ul << index);
-	return anchor;
-}
-
-static hamt_node *table_shrink(struct hamt_impl *h, hamt_node *anchor,
-			       size_t n_rows, uint32_t index, uint32_t pos)
-{
-	/* debug assertions */
-	assert(anchor && "Anchor cannot be NULL");
-	assert(!is_value(VALUE(anchor)) &&
-	       "Invariant: shrinking a table requires an internal node");
-
-	hamt_node *new_table = NULL;
-	uint32_t new_index = 0;
-	if (n_rows > 0) {
-		new_table = table_allocate(h, n_rows - 1);
-		if (!new_table)
-			return NULL;
-		new_index = INDEX(anchor) & ~(1ul << index);
-		memcpy(&new_table[0], &TABLE(anchor)[0],
-		       pos * sizeof(hamt_node));
-		memcpy(&new_table[pos], &TABLE(anchor)[pos + 1],
-		       (n_rows - pos - 1) * sizeof(hamt_node));
-	}
-	table_free(h, TABLE(anchor), n_rows);
-	INDEX(anchor) = new_index;
-	TABLE(anchor) = new_table;
-	return anchor;
-}
-
-static hamt_node *table_gather(struct hamt_impl *h, hamt_node *anchor,
-			       uint32_t pos)
-{
-	/* debug assertions */
-	assert(anchor && "Anchor cannot be NULL");
-	assert(!is_value(VALUE(anchor)) &&
-	       "Invariant: gathering a table requires an internal anchor");
-	assert((pos == 0 || pos == 1) && "pos must be 0 or 1");
-
-	int n_rows = get_popcount(INDEX(anchor));
-	assert((n_rows == 2 || n_rows == 1) &&
-	       "Table must have size 1 or 2 to gather");
-	hamt_node *table = TABLE(anchor);
-	KEY(anchor) = table[pos].as.kv.key;
-	VALUE(anchor) = table[pos].as.kv.value; /* already tagged */
-	table_free(h, table, n_rows);
-	return anchor;
-}
-
-static hamt_node *table_dup(struct hamt_impl *h, hamt_node *anchor)
-{
-	int n_rows = get_popcount(INDEX(anchor));
-	hamt_node *new_table = table_allocate(h, n_rows);
-	if (new_table && TABLE(anchor)) {
-		memcpy(&new_table[0], &TABLE(anchor)[0],
-		       n_rows * sizeof(hamt_node));
-	}
-	return new_table;
-}
-
-HAMT hamt_create(hamt_key_hash_fn key_hash, hamt_cmp_fn key_cmp,
-		 struct hamt_allocator *ator)
-{
-	struct hamt_impl *trie = mem_alloc(ator, sizeof(struct hamt_impl));
-	trie->ator = ator;
-	trie->root = mem_alloc(ator, sizeof(hamt_node));
-	memset(trie->root, 0, sizeof(hamt_node));
-	trie->size = 0;
-	trie->key_hash = key_hash;
-	trie->key_cmp = key_cmp;
-	// memset(trie->stats.table_sizes, 0, 32*sizeof(size_t));
-	trie->stats = (struct hamt_stats){ .table_sizes = { 0 } };
-	return trie;
-}
-
-static HAMT hamt_dup(HAMT h)
-{
-	struct hamt_impl *trie = mem_alloc(h->ator, sizeof(struct hamt_impl));
-	trie->ator = h->ator;
-	trie->root = mem_alloc(h->ator, sizeof(hamt_node));
-	memcpy(trie->root, h->root, sizeof(hamt_node));
-	trie->size = h->size;
-	trie->key_hash = h->key_hash;
-	trie->key_cmp = h->key_cmp;
-	memcpy(&trie->stats, &h->stats, sizeof(struct hamt_stats));
-	return trie;
-}
-
-static const hamt_node *insert_kv(struct hamt_impl *h, hamt_node *anchor,
-				  hash_state *hash, void *key, void *value)
-{
-	/* calculate position in new table */
-	uint32_t ix = hash_get_index(hash);
-	uint32_t new_index = INDEX(anchor) | (1ul << ix);
-	int pos = get_pos(ix, new_index);
-	/* extend table */
-	size_t n_rows = get_popcount(INDEX(anchor));
-	anchor = table_extend(h, anchor, n_rows, ix, pos);
-	if (!anchor)
-		return NULL;
-	hamt_node *new_table = TABLE(anchor);
-	/* set new k/v pair */
-	new_table[pos].as.kv.key = key;
-	new_table[pos].as.kv.value = tagged(value);
-	/* return a pointer to the inserted k/v pair */
-	return &new_table[pos];
-}
-
-static const hamt_node *insert_table(struct hamt_impl *h, hamt_node *anchor,
-				     hash_state *hash, void *key, void *value)
-{
-	/* FIXME: check for alloc failure and bail out correctly (deleting the
-     *        incomplete subtree */
-
-	/* Collect everything we know about the existing value */
-	hash_state *x_hash =
-		&(hash_state){ .key = KEY(anchor),
-			       .hash_fn = hash->hash_fn,
-			       .hash = hash->hash_fn(KEY(anchor),
-						     hash->depth / 5),
-			       .depth = hash->depth,
-			       .shift = hash->shift };
-	void *x_value = VALUE(anchor); /* tagged (!) value ptr */
-	/* increase depth until the hashes diverge, building a list
-     * of tables along the way */
-	hash_state *next_hash = hash_next(hash);
-	hash_state *x_next_hash = hash_next(x_hash);
-	uint32_t next_index = hash_get_index(next_hash);
-	uint32_t x_next_index = hash_get_index(x_next_hash);
-	while (x_next_index == next_index) {
-		TABLE(anchor) = table_allocate(h, 1);
-		INDEX(anchor) = (1ul << next_index);
-		next_hash = hash_next(next_hash);
-		x_next_hash = hash_next(x_next_hash);
-		next_index = hash_get_index(next_hash);
-		x_next_index = hash_get_index(x_next_hash);
-		anchor = TABLE(anchor);
-	}
-	/* the hashes are different, let's allocate a table with two
-     * entries to store the existing and new values */
-	TABLE(anchor) = table_allocate(h, 2);
-	INDEX(anchor) = (1ul << next_index) | (1ul << x_next_index);
-	/* determine the proper position in the allocated table */
-	int x_pos = get_pos(x_next_index, INDEX(anchor));
-	int pos = get_pos(next_index, INDEX(anchor));
-	/* fill in the existing value; no need to tag the value pointer
-     * since it is already tagged. */
-	TABLE(anchor)[x_pos].as.kv.key = (const void *)x_hash->key;
-	TABLE(anchor)[x_pos].as.kv.value = x_value;
-	/* fill in the new key/value pair, tagging the pointer to the
-     * new value to mark it as a value ptr */
-	TABLE(anchor)[pos].as.kv.key = key;
-	TABLE(anchor)[pos].as.kv.value = tagged(value);
-
-	return &TABLE(anchor)[pos];
-}
-
-static search_result search_recursive(struct hamt_impl *h, hamt_node *anchor,
-				      hash_state *hash, hamt_cmp_fn cmp_eq,
-				      const void *key, hamt_node *path)
-{
-	assert(!is_value(VALUE(anchor)) &&
-	       "Invariant: path copy requires an internal node");
-	hamt_node *copy = path;
-	if (path) {
-		/* copy the table we're pointing to */
-		TABLE(copy) = table_dup(h, anchor);
-		INDEX(copy) = INDEX(anchor);
-		assert(!is_value(VALUE(copy)) &&
-		       "Copy caused a leaf/internal switch");
-	} else {
-		copy = anchor;
-	}
-
-	/* determine the expected index in table */
-	uint32_t expected_index = hash_get_index(hash);
-	/* check if the expected index is set */
-	if (has_index(copy, expected_index)) {
-		/* if yes, get the compact index to address the array */
-		int pos = get_pos(expected_index, INDEX(copy));
-		/* index into the table and check what type of entry we're looking at */
-		hamt_node *next = &TABLE(copy)[pos];
-		if (is_value(VALUE(next))) {
-			if ((*cmp_eq)(key, KEY(next)) == 0) {
-				/* keys match */
-				search_result result = { .status =
-								 SEARCH_SUCCESS,
-							 .anchor = copy,
-							 .value = next,
-							 .hash = hash };
-				return result;
-			}
-			/* not found: same hash but different key */
-			search_result result = {
-				.status = SEARCH_FAIL_KEYMISMATCH,
-				.anchor = copy,
-				.value = next,
-				.hash = hash
-			};
-			return result;
-		} else {
-			/* For table entries, recurse to the next level */
-			assert(TABLE(next) != NULL &&
-			       "invariant: table ptrs must not be NULL");
-			return search_recursive(h, next, hash_next(hash),
-						cmp_eq, key,
-						path ? next : NULL);
-		}
-	}
-	/* expected index is not set, terminate search */
-	search_result result = { .status = SEARCH_FAIL_NOTFOUND,
-				 .anchor = copy,
-				 .value = NULL,
-				 .hash = hash };
-	return result;
-}
-
-void *hamt_get(const HAMT trie, void *key)
-{
-	hash_state *hash = &(hash_state){ .key = key,
-					  .hash_fn = trie->key_hash,
-					  .hash = trie->key_hash(key, 0),
-					  .depth = 0,
-					  .shift = 0 };
-	search_result sr = search_recursive(trie, trie->root, hash,
-					    trie->key_cmp, key, NULL);
-	if (sr.status == SEARCH_SUCCESS) {
-		return untagged(sr.VALUE(value));
-	}
-	return NULL;
-}
-
-static path_result search(struct hamt_impl *h, hamt_node *anchor,
-			  hash_state *hash, hamt_cmp_fn cmp_eq, const void *key)
-{
-	path_result pr;
-	pr.root = mem_alloc(h->ator, sizeof(hamt_node));
-	pr.u.sr = search_recursive(h, anchor, hash, cmp_eq, key, pr.root);
-	return pr;
-}
-
-HAMT hamt_pset(HAMT h, void *key, void *value)
-{
-	hash_state *hash = &(hash_state){ .key = key,
-					  .hash_fn = h->key_hash,
-					  .hash = h->key_hash(key, 0),
-					  .depth = 0,
-					  .shift = 0 };
-	HAMT cp = hamt_dup(h);
-	path_result pr = search(h, h->root, hash, h->key_cmp, key);
-	cp->root = pr.root;
-	switch (pr.u.sr.status) {
-	case SEARCH_SUCCESS:
-		pr.u.sr.VALUE(value) = tagged(value);
-		break;
-	case SEARCH_FAIL_NOTFOUND:
-		if (insert_kv(h, pr.u.sr.anchor, pr.u.sr.hash, key, value) !=
-		    NULL) {
-			cp->size += 1;
-		}
-		break;
-	case SEARCH_FAIL_KEYMISMATCH:
-		if (insert_table(h, pr.u.sr.value, pr.u.sr.hash, key, value) !=
-		    NULL) {
-			cp->size += 1;
-		}
-		break;
-	default:
-		fprintf(stderr, "Invalid result status\n");
-	}
-	return cp;
-}
-
-/* delete recursively from anchor */
-static void delete_recursive(struct hamt_impl *h, hamt_node *anchor)
-{
-	if (TABLE(anchor)) {
-		assert(!is_value(VALUE(anchor)) &&
-		       "delete requires an internal node");
-		size_t n = get_popcount(INDEX(anchor));
-		for (size_t i = 0; i < n; ++i) {
-			if (!is_value(TABLE(anchor)[i].as.kv.value)) {
-				delete_recursive(h, &TABLE(anchor)[i]);
-			}
-		}
-		table_free(h, TABLE(anchor), n);
-		TABLE(anchor) = NULL;
-	}
-}
-
-void hamt_delete(HAMT h)
-{
-	delete_recursive(h, h->root);
-	mem_free(h->ator, h->root);
-	mem_free(h->ator, h);
-}