1 files changed, 323 insertions, 0 deletions
diff --git a/third-party/tommyds/tommytrie.c b/third-party/tommyds/tommytrie.c
new file mode 100644
index 0000000..35ac219
--- /dev/null
+++ b/third-party/tommyds/tommytrie.c
@@ -0,0 +1,323 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommytrie.h"
+#include "tommylist.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* trie */
+
+/**
+ * Mask for the inner branches.
+ */
+#define TOMMY_TRIE_TREE_MASK (TOMMY_TRIE_TREE_MAX - 1)
+
+/**
+ * Shift for the first level of branches.
+ */
+#define TOMMY_TRIE_BUCKET_SHIFT (TOMMY_KEY_BIT - TOMMY_TRIE_BUCKET_BIT)
+
+/**
+ * Max number of levels.
+ */
+#define TOMMY_TRIE_LEVEL_MAX ((TOMMY_KEY_BIT - TOMMY_TRIE_BUCKET_BIT) / TOMMY_TRIE_TREE_BIT)
+
+/**
+ * Hashtrie tree.
+ * A tree contains TOMMY_TRIE_TREE_MAX ordered pointers to <null/node/tree>.
+ *
+ * Each tree level uses exactly TOMMY_TRIE_TREE_BIT bits from the key.
+ */
+struct tommy_trie_tree_struct {
+	tommy_trie_node* map[TOMMY_TRIE_TREE_MAX];
+};
+typedef struct tommy_trie_tree_struct tommy_trie_tree;
+
+/**
+ * Kinds of an trie node.
+ */
+#define TOMMY_TRIE_TYPE_NODE 0 /**< The node is of type ::tommy_trie_node. */
+#define TOMMY_TRIE_TYPE_TREE 1 /**< The node is of type ::tommy_trie_tree. */
+
+/**
+ * Get and set pointer of trie nodes.
+ *
+ * The pointer type is stored in the lower bit.
+ */
+#define trie_get_type(ptr) (((tommy_uintptr_t)(ptr)) & 1)
+#define trie_get_tree(ptr) ((tommy_trie_tree*)(((tommy_uintptr_t)(ptr)) - TOMMY_TRIE_TYPE_TREE))
+#define trie_set_tree(ptr) (void*)(((tommy_uintptr_t)(ptr)) + TOMMY_TRIE_TYPE_TREE)
+
+void tommy_trie_init(tommy_trie* trie, tommy_allocator* alloc)
+{
+	tommy_uint_t i;
+
+	for (i = 0; i < TOMMY_TRIE_BUCKET_MAX; ++i)
+		trie->bucket[i] = 0;
+
+	trie->count = 0;
+	trie->node_count = 0;
+
+	trie->alloc = alloc;
+}
+
+static void trie_bucket_insert(tommy_trie* trie, tommy_uint_t shift, tommy_trie_node** let_ptr, tommy_trie_node* insert, tommy_key_t key)
+{
+	tommy_trie_tree* tree;
+	tommy_trie_node* node;
+	void* ptr;
+	tommy_uint_t i;
+	tommy_uint_t j;
+
+recurse:
+	ptr = *let_ptr;
+
+	/* if null, just insert the node */
+	if (!ptr) {
+		/* setup the node as a list */
+		tommy_list_insert_first(let_ptr, insert);
+		return;
+	}
+
+	if (trie_get_type(ptr) == TOMMY_TRIE_TYPE_TREE) {
+		/* repeat the process one level down */
+		let_ptr = &trie_get_tree(ptr)->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
+		shift -= TOMMY_TRIE_TREE_BIT;
+		goto recurse;
+	}
+
+	node = tommy_cast(tommy_trie_node*, ptr);
+
+	/* if it's the same key, insert in the list */
+	if (node->key == key) {
+		tommy_list_insert_tail_not_empty(node, insert);
+		return;
+	}
+
+expand:
+	/* convert to a tree */
+	tree = tommy_cast(tommy_trie_tree*, tommy_allocator_alloc(trie->alloc));
+	++trie->node_count;
+	*let_ptr = tommy_cast(tommy_trie_node*, trie_set_tree(tree));
+
+	/* initialize it */
+	for (i = 0; i < TOMMY_TRIE_TREE_MAX; ++i)
+		tree->map[i] = 0;
+
+	/* get the position of the two elements */
+	i = (node->key >> shift) & TOMMY_TRIE_TREE_MASK;
+	j = (key >> shift) & TOMMY_TRIE_TREE_MASK;
+
+	/* if they don't collide */
+	if (i != j) {
+		/* insert the already existing element */
+		tree->map[i] = node;
+
+		/* insert the new node */
+		tommy_list_insert_first(&tree->map[j], insert);
+		return;
+	}
+
+	/* expand one more level */
+	let_ptr = &tree->map[i];
+	shift -= TOMMY_TRIE_TREE_BIT;
+	goto expand;
+}
+
+void tommy_trie_insert(tommy_trie* trie, tommy_trie_node* node, void* data, tommy_key_t key)
+{
+	tommy_trie_node** let_ptr;
+
+	node->data = data;
+	node->key = key;
+
+	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
+
+	trie_bucket_insert(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, node, key);
+
+	++trie->count;
+}
+
+static tommy_trie_node* trie_bucket_remove_existing(tommy_trie* trie, tommy_uint_t shift, tommy_trie_node** let_ptr, tommy_trie_node* remove, tommy_key_t key)
+{
+	tommy_trie_node* node;
+	tommy_trie_tree* tree;
+	void* ptr;
+	tommy_trie_node** let_back[TOMMY_TRIE_LEVEL_MAX + 1];
+	tommy_uint_t level;
+	tommy_uint_t i;
+	tommy_uint_t count;
+	tommy_uint_t last;
+
+	level = 0;
+recurse:
+	ptr = *let_ptr;
+
+	if (!ptr)
+		return 0;
+
+	if (trie_get_type(ptr) == TOMMY_TRIE_TYPE_TREE) {
+		tree = trie_get_tree(ptr);
+
+		/* save the path */
+		let_back[level++] = let_ptr;
+
+		/* go down one level */
+		let_ptr = &tree->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
+		shift -= TOMMY_TRIE_TREE_BIT;
+
+		goto recurse;
+	}
+
+	node = tommy_cast(tommy_trie_node*, ptr);
+
+	/* if the node to remove is not specified */
+	if (!remove) {
+		/* remove the first */
+		remove = node;
+
+		/* check if it's really the element to remove */
+		if (remove->key != key)
+			return 0;
+	}
+
+	tommy_list_remove_existing(let_ptr, remove);
+
+	/* if the list is not empty, try to reduce */
+	if (*let_ptr || !level)
+		return remove;
+
+reduce:
+	/* go one level up */
+	let_ptr = let_back[--level];
+
+	tree = trie_get_tree(*let_ptr);
+
+	/* check if there is only one child node */
+	count = 0;
+	last = 0;
+	for (i = 0; i < TOMMY_TRIE_TREE_MAX; ++i) {
+		if (tree->map[i]) {
+			/* if we have a sub tree, we cannot reduce */
+			if (trie_get_type(tree->map[i]) != TOMMY_TRIE_TYPE_NODE)
+				return remove;
+			/* if more than one node, we cannot reduce */
+			if (++count > 1)
+				return remove;
+			last = i;
+		}
+	}
+
+	/* here count is never 0, as we cannot have a tree with only one sub node */
+	assert(count == 1);
+
+	*let_ptr = tree->map[last];
+
+	tommy_allocator_free(trie->alloc, tree);
+	--trie->node_count;
+
+	/* repeat until more level */
+	if (level)
+		goto reduce;
+
+	return remove;
+}
+
+void* tommy_trie_remove(tommy_trie* trie, tommy_key_t key)
+{
+	tommy_trie_node* ret;
+	tommy_trie_node** let_ptr;
+
+	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
+
+	ret = trie_bucket_remove_existing(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, 0, key);
+
+	if (!ret)
+		return 0;
+
+	--trie->count;
+
+	return ret->data;
+}
+
+void* tommy_trie_remove_existing(tommy_trie* trie, tommy_trie_node* node)
+{
+	tommy_trie_node* ret;
+	tommy_key_t key = node->key;
+	tommy_trie_node** let_ptr;
+
+	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
+
+	ret = trie_bucket_remove_existing(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, node, key);
+
+	/* the element removed must match the one passed */
+	assert(ret == node);
+
+	--trie->count;
+
+	return ret->data;
+}
+
+tommy_trie_node* tommy_trie_bucket(tommy_trie* trie, tommy_key_t key)
+{
+	tommy_trie_node* node;
+	void* ptr;
+	tommy_uint_t type;
+	tommy_uint_t shift;
+
+	ptr = trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
+
+	shift = TOMMY_TRIE_BUCKET_SHIFT;
+
+recurse:
+	if (!ptr)
+		return 0;
+
+	type = trie_get_type(ptr);
+
+	switch (type) {
+	case TOMMY_TRIE_TYPE_NODE :
+		node = tommy_cast(tommy_trie_node*, ptr);
+		if (node->key != key)
+			return 0;
+		return node;
+	default :
+	case TOMMY_TRIE_TYPE_TREE :
+		ptr = trie_get_tree(ptr)->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
+		shift -= TOMMY_TRIE_TREE_BIT;
+		goto recurse;
+	}
+}
+
+tommy_size_t tommy_trie_memory_usage(tommy_trie* trie)
+{
+	return tommy_trie_count(trie) * (tommy_size_t)sizeof(tommy_trie_node)
+	       + trie->node_count * (tommy_size_t)TOMMY_TRIE_BLOCK_SIZE;
+}
+