/*
 * 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);
}