From 4dbdc42d9e7c3968ff7f690d00680419c9b8cb0f Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 9 Apr 2024 15:34:27 +0200 Subject: Adding upstream version 1:2.43.0. Signed-off-by: Daniel Baumann --- reftable/tree.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) create mode 100644 reftable/tree.c (limited to 'reftable/tree.c') diff --git a/reftable/tree.c b/reftable/tree.c new file mode 100644 index 0000000..a5bf880 --- /dev/null +++ b/reftable/tree.c @@ -0,0 +1,63 @@ +/* +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(void *key, struct tree_node **rootp, + int (*compare)(const void *, const void *), + int insert) +{ + int res; + if (!*rootp) { + if (!insert) { + return NULL; + } else { + struct tree_node *n = + reftable_calloc(sizeof(struct tree_node)); + n->key = key; + *rootp = n; + return *rootp; + } + } + + res = compare(key, (*rootp)->key); + if (res < 0) + return tree_search(key, &(*rootp)->left, compare, insert); + else if (res > 0) + return tree_search(key, &(*rootp)->right, compare, insert); + 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); +} -- cgit v1.2.3