1 files changed, 292 insertions, 0 deletions
diff --git a/third-party/tommyds/tommytree.c b/third-party/tommyds/tommytree.c
new file mode 100644
index 0000000..6b2f1a9
--- /dev/null
+++ b/third-party/tommyds/tommytree.c
@@ -0,0 +1,292 @@
+/*
+ * Copyright (c) 2015, 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 "tommytree.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* tree */
+
+void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp)
+{
+	tree->root = 0;
+	tree->count = 0;
+	tree->cmp = cmp;
+}
+
+static int tommy_tree_delta(tommy_tree_node* root)
+{
+	int left_height = root->prev ? root->prev->key : 0;
+	int right_height = root->next ? root->next->key : 0;
+
+	return left_height - right_height;
+}
+
+/* AVL tree operations */
+static tommy_tree_node* tommy_tree_balance(tommy_tree_node*);
+
+static tommy_tree_node* tommy_tree_rotate_left(tommy_tree_node* root)
+{
+	tommy_tree_node* next = root->next;
+
+	root->next = next->prev;
+
+	next->prev = tommy_tree_balance(root);
+
+	return tommy_tree_balance(next);
+}
+
+static tommy_tree_node* tommy_tree_rotate_right(tommy_tree_node* root)
+{
+	tommy_tree_node* prev = root->prev;
+
+	root->prev = prev->next;
+
+	prev->next = tommy_tree_balance(root);
+
+	return tommy_tree_balance(prev);
+}
+
+static tommy_tree_node* tommy_tree_move_right(tommy_tree_node* root, tommy_tree_node* node)
+{
+	if (!root)
+		return node;
+
+	root->next = tommy_tree_move_right(root->next, node);
+
+	return tommy_tree_balance(root);
+}
+
+static tommy_tree_node* tommy_tree_balance(tommy_tree_node* root)
+{
+	int delta = tommy_tree_delta(root);
+
+	if (delta < -1) {
+		if (tommy_tree_delta(root->next) > 0)
+			root->next = tommy_tree_rotate_right(root->next);
+		return tommy_tree_rotate_left(root);
+	}
+
+	if (delta > 1) {
+		if (tommy_tree_delta(root->prev) < 0)
+			root->prev = tommy_tree_rotate_left(root->prev);
+		return tommy_tree_rotate_right(root);
+	}
+
+	/* recompute key */
+	root->key = 0;
+
+	if (root->prev && root->prev->key > root->key)
+		root->key = root->prev->key;
+
+	if (root->next && root->next->key > root->key)
+		root->key = root->next->key;
+
+	/* count itself */
+	root->key += 1;
+
+	return root;
+}
+
+static tommy_tree_node* tommy_tree_insert_node(tommy_compare_func* cmp, tommy_tree_node* root, tommy_tree_node** let)
+{
+	int c;
+
+	if (!root)
+		return *let;
+
+	c = cmp((*let)->data, root->data);
+
+	if (c < 0) {
+		root->prev = tommy_tree_insert_node(cmp, root->prev, let);
+		return tommy_tree_balance(root);
+	}
+
+	if (c > 0) {
+		root->next = tommy_tree_insert_node(cmp, root->next, let);
+		return tommy_tree_balance(root);
+	}
+
+	/* already present, set the return pointer */
+	*let = root;
+
+	return root;
+}
+
+void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data)
+{
+	tommy_tree_node* insert = node;
+
+	insert->data = data;
+	insert->prev = 0;
+	insert->next = 0;
+	insert->key = 0;
+
+	tree->root = tommy_tree_insert_node(tree->cmp, tree->root, &insert);
+
+	if (insert == node)
+		++tree->count;
+
+	return insert->data;
+}
+
+static tommy_tree_node* tommy_tree_remove_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data, tommy_tree_node** let)
+{
+	int c;
+
+	if (!root)
+		return 0;
+
+	c = cmp(data, root->data);
+
+	if (c < 0) {
+		root->prev = tommy_tree_remove_node(cmp, root->prev, data, let);
+		return tommy_tree_balance(root);
+	}
+
+	if (c > 0) {
+		root->next = tommy_tree_remove_node(cmp, root->next, data, let);
+		return tommy_tree_balance(root);
+	}
+
+	/* found */
+	*let = root;
+
+	return tommy_tree_move_right(root->prev, root->next);
+}
+
+void* tommy_tree_remove(tommy_tree* tree, void* data)
+{
+	tommy_tree_node* node = 0;
+
+	tree->root = tommy_tree_remove_node(tree->cmp, tree->root, data, &node);
+
+	if (!node)
+		return 0;
+
+	--tree->count;
+
+	return node->data;
+}
+
+static tommy_tree_node* tommy_tree_search_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data)
+{
+	int c;
+
+	if (!root)
+		return 0;
+
+	c = cmp(data, root->data);
+
+	if (c < 0)
+		return tommy_tree_search_node(cmp, root->prev, data);
+
+	if (c > 0)
+		return tommy_tree_search_node(cmp, root->next, data);
+
+	return root;
+}
+
+void* tommy_tree_search(tommy_tree* tree, void* data)
+{
+	tommy_tree_node* node = tommy_tree_search_node(tree->cmp, tree->root, data);
+
+	if (!node)
+		return 0;
+
+	return node->data;
+}
+
+void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg)
+{
+	tommy_tree_node* node = tommy_tree_search_node(cmp, tree->root, cmp_arg);
+
+	if (!node)
+		return 0;
+
+	return node->data;
+}
+
+void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node)
+{
+	void* data = tommy_tree_remove(tree, node->data);
+
+	assert(data != 0);
+
+	return data;
+}
+
+static void tommy_tree_foreach_node(tommy_tree_node* root, tommy_foreach_func* func)
+{
+	tommy_tree_node* next;
+
+	if (!root)
+		return;
+
+	tommy_tree_foreach_node(root->prev, func);
+
+	/* make a copy in case func is free() */
+	next = root->next;
+
+	func(root->data);
+
+	tommy_tree_foreach_node(next, func);
+}
+
+void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func)
+{
+	tommy_tree_foreach_node(tree->root, func);
+}
+
+static void tommy_tree_foreach_arg_node(tommy_tree_node* root, tommy_foreach_arg_func* func, void* arg)
+{
+	tommy_tree_node* next;
+
+	if (!root)
+		return;
+
+	tommy_tree_foreach_arg_node(root->prev, func, arg);
+
+	/* make a copy in case func is free() */
+	next = root->next;
+
+	func(arg, root->data);
+
+	tommy_tree_foreach_arg_node(next, func, arg);
+}
+
+void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg)
+{
+	tommy_tree_foreach_arg_node(tree->root, func, arg);
+}
+
+tommy_size_t tommy_tree_memory_usage(tommy_tree* tree)
+{
+	return tommy_tree_count(tree) * sizeof(tommy_tree_node);
+}
+