1 files changed, 270 insertions, 0 deletions
diff --git a/third-party/tommyds/tommytrieinp.c b/third-party/tommyds/tommytrieinp.c
new file mode 100644
index 0000000..26ec2c3
--- /dev/null
+++ b/third-party/tommyds/tommytrieinp.c
@@ -0,0 +1,270 @@
+/*
+ * 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 "tommytrieinp.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* trie_inplace */
+
+/**
+ * Mask for the inner branches.
+ */
+#define TOMMY_TRIE_INPLACE_TREE_MASK (TOMMY_TRIE_INPLACE_TREE_MAX - 1)
+
+/**
+ * Shift for the first level of branches.
+ */
+#define TOMMY_TRIE_INPLACE_BUCKET_SHIFT (TOMMY_KEY_BIT - TOMMY_TRIE_INPLACE_BUCKET_BIT)
+
+/**
+ * Create a new list with a single element.
+ */
+tommy_inline tommy_trie_inplace_node* tommy_trie_inplace_list_insert_first(tommy_trie_inplace_node* node)
+{
+	/* one element "circular" prev list */
+	node->prev = node;
+
+	/* one element "0 terminated" next list */
+	node->next = 0;
+
+	return node;
+}
+
+/**
+ * Add an element to an existing list.
+ * \note The element is inserted at the end of the list.
+ */
+tommy_inline void tommy_trie_inplace_list_insert_tail_not_empty(tommy_trie_inplace_node* head, tommy_trie_inplace_node* node)
+{
+	/* insert in the list in the last position */
+
+	/* insert in the "circular" prev list */
+	node->prev = head->prev;
+	head->prev = node;
+
+	/* insert in the "0 terminated" next list */
+	node->next = 0;
+	node->prev->next = node;
+}
+
+/**
+ * Remove an element from the list.
+ */
+tommy_inline void tommy_trie_inplace_list_remove(tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* node)
+{
+	tommy_trie_inplace_node* head = *let_ptr;
+
+	/* remove from the "circular" prev list */
+	if (node->next)
+		node->next->prev = node->prev;
+	else
+		head->prev = node->prev; /* the last */
+
+	/* remove from the "0 terminated" next list */
+	if (head == node)
+		*let_ptr = node->next; /* the new first */
+	else
+		node->prev->next = node->next;
+}
+
+void tommy_trie_inplace_init(tommy_trie_inplace* trie_inplace)
+{
+	tommy_uint_t i;
+
+	for (i = 0; i < TOMMY_TRIE_INPLACE_BUCKET_MAX; ++i)
+		trie_inplace->bucket[i] = 0;
+
+	trie_inplace->count = 0;
+}
+
+static void trie_inplace_bucket_insert(tommy_uint_t shift, tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* insert, tommy_key_t key)
+{
+	tommy_trie_inplace_node* node;
+
+	node = *let_ptr;
+	while (node && node->key != key) {
+		let_ptr = &node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
+		node = *let_ptr;
+		shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
+	}
+
+	/* if null, just insert the node */
+	if (!node) {
+		/* setup the node as a list */
+		*let_ptr = tommy_trie_inplace_list_insert_first(insert);
+	} else {
+		/* if it's the same key, insert in the list */
+		tommy_trie_inplace_list_insert_tail_not_empty(node, insert);
+	}
+}
+
+void tommy_trie_inplace_insert(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node, void* data, tommy_key_t key)
+{
+	tommy_trie_inplace_node** let_ptr;
+	tommy_uint_t i;
+
+	node->data = data;
+	node->key = key;
+	/* clear the child pointers */
+	for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
+		node->map[i] = 0;
+
+	let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
+
+	trie_inplace_bucket_insert(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, node, key);
+
+	++trie_inplace->count;
+}
+
+static tommy_trie_inplace_node* trie_inplace_bucket_remove(tommy_uint_t shift, tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* remove, tommy_key_t key)
+{
+	tommy_trie_inplace_node* node;
+	int i;
+	tommy_trie_inplace_node** leaf_let_ptr;
+	tommy_trie_inplace_node* leaf;
+
+	node = *let_ptr;
+	while (node && node->key != key) {
+		let_ptr = &node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
+		node = *let_ptr;
+		shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
+	}
+
+	if (!node)
+		return 0;
+
+	/* if the node to remove is not specified */
+	if (!remove)
+		remove = node; /* remove the first */
+
+	tommy_trie_inplace_list_remove(let_ptr, remove);
+
+	/* if not change in the node, nothing more to do */
+	if (*let_ptr == node)
+		return remove;
+
+	/* if we have a substitute */
+	if (*let_ptr != 0) {
+		/* copy the child pointers to the new one */
+		node = *let_ptr;
+		for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
+			node->map[i] = remove->map[i];
+
+		return remove;
+	}
+
+	/* find a leaf */
+	leaf_let_ptr = 0;
+	leaf = remove;
+
+	/* search backward, statistically we have more zeros than ones */
+	i = TOMMY_TRIE_INPLACE_TREE_MAX - 1;
+	while (i >= 0) {
+		if (leaf->map[i]) {
+			leaf_let_ptr = &leaf->map[i];
+			leaf = *leaf_let_ptr;
+			i = TOMMY_TRIE_INPLACE_TREE_MAX - 1;
+			continue;
+		}
+		--i;
+	}
+
+	/* if it's itself a leaf */
+	if (!leaf_let_ptr)
+		return remove;
+
+	/* remove the leaf */
+	*leaf_let_ptr = 0;
+
+	/* copy the child pointers */
+	for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
+		leaf->map[i] = remove->map[i];
+
+	/* put it in place */
+	*let_ptr = leaf;
+
+	return remove;
+}
+
+void* tommy_trie_inplace_remove(tommy_trie_inplace* trie_inplace, tommy_key_t key)
+{
+	tommy_trie_inplace_node* ret;
+	tommy_trie_inplace_node** let_ptr;
+
+	let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
+
+	ret = trie_inplace_bucket_remove(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, 0, key);
+
+	if (!ret)
+		return 0;
+
+	--trie_inplace->count;
+
+	return ret->data;
+}
+
+void* tommy_trie_inplace_remove_existing(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node)
+{
+	tommy_trie_inplace_node* ret;
+	tommy_key_t key = node->key;
+	tommy_trie_inplace_node** let_ptr;
+
+	let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
+
+	ret = trie_inplace_bucket_remove(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, node, key);
+
+	/* the element removed must match the one passed */
+	assert(ret == node);
+
+	--trie_inplace->count;
+
+	return ret->data;
+}
+
+tommy_trie_inplace_node* tommy_trie_inplace_bucket(tommy_trie_inplace* trie_inplace, tommy_key_t key)
+{
+	tommy_trie_inplace_node* node;
+	tommy_uint_t shift;
+
+	node = trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
+	shift = TOMMY_TRIE_INPLACE_BUCKET_SHIFT;
+
+	while (node && node->key != key) {
+		node = node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
+		shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
+	}
+
+	return node;
+}
+
+tommy_size_t tommy_trie_inplace_memory_usage(tommy_trie_inplace* trie_inplace)
+{
+	return tommy_trie_inplace_count(trie_inplace) * (tommy_size_t)sizeof(tommy_trie_inplace_node);
+}
+