1 files changed, 74 insertions, 0 deletions
diff --git a/reftable/tree.c b/reftable/tree.c
new file mode 100644
index 0000000000..a52f7c0c7d
--- /dev/null
+++ b/reftable/tree.c
@@ -0,0 +1,74 @@
+/*
+ * Copyright 2020 Google LLC
+ *
+ * Use of this source code is governed by a BSD-style
+ * license that can be found in the LICENSE file or at
+ * https://developers.google.com/open-source/licenses/bsd
+ */
+
+#include "system.h"
+#include "tree.h"
+
+#include "basics.h"
+
+struct tree_node *tree_search(struct tree_node *tree,
+			      void *key,
+			      int (*compare)(const void *, const void *))
+{
+	int res;
+	if (!tree)
+		return NULL;
+	res = compare(key, tree->key);
+	if (res < 0)
+		return tree_search(tree->left, key, compare);
+	else if (res > 0)
+		return tree_search(tree->right, key, compare);
+	return tree;
+}
+
+struct tree_node *tree_insert(struct tree_node **rootp,
+			      void *key,
+			      int (*compare)(const void *, const void *))
+{
+	int res;
+
+	if (!*rootp) {
+		struct tree_node *n;
+
+		REFTABLE_CALLOC_ARRAY(n, 1);
+		if (!n)
+			return NULL;
+
+		n->key = key;
+		*rootp = n;
+		return *rootp;
+	}
+
+	res = compare(key, (*rootp)->key);
+	if (res < 0)
+		return tree_insert(&(*rootp)->left, key, compare);
+	else if (res > 0)
+		return tree_insert(&(*rootp)->right, key, compare);
+	return *rootp;
+}
+
+void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key),
+		void *arg)
+{
+	if (t->left)
+		infix_walk(t->left, action, arg);
+	action(arg, t->key);
+	if (t->right)
+		infix_walk(t->right, action, arg);
+}
+
+void tree_free(struct tree_node *t)
+{
+	if (!t)
+		return;
+	if (t->left)
+		tree_free(t->left);
+	if (t->right)
+		tree_free(t->right);
+	reftable_free(t);
+}