diff options
| author | Junio C Hamano <gitster@pobox.com> | 2021-12-07 12:44:49 -0800 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2021-12-07 12:44:49 -0800 |
| commit | bb4921cf45e11d063e7bbe55f594adf8f0077d5d (patch) | |
| tree | eae48e5666c03586904f835e45d70fe40d61977e /reftable/tree.c | |
| parent | abe6bb3905392d5eb6b01fa6e54d7e784e0522aa (diff) | |
| parent | d860c86ba545920342cbc507fc34af461ab99152 (diff) | |
| download | git-bb4921cf45e11d063e7bbe55f594adf8f0077d5d.tar.gz | |
Merge branch 'hn/reftable' into hn/reftable-coverity-fixes
* hn/reftable:
Add "test-tool dump-reftable" command.
reftable: add dump utility
reftable: implement stack, a mutable database of reftable files.
reftable: implement refname validation
reftable: add merged table view
reftable: add a heap-based priority queue for reftable records
reftable: reftable file level tests
reftable: read reftable files
reftable: generic interface to tables
reftable: write reftable files
reftable: a generic binary tree implementation
reftable: reading/writing blocks
Provide zlib's uncompress2 from compat/zlib-compat.c
reftable: (de)serialization for the polymorphic record type.
reftable: add blocksource, an abstraction for random access reads
reftable: utility functions
reftable: add error related functionality
reftable: add LICENSE
hash.h: provide constants for the hash IDs
Diffstat (limited to 'reftable/tree.c')
| -rw-r--r-- | reftable/tree.c | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/reftable/tree.c b/reftable/tree.c new file mode 100644 index 0000000000..82db7995dd --- /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 "tree.h" + +#include "basics.h" +#include "system.h" + +struct tree_node *tree_search(void *key, struct tree_node **rootp, + int (*compare)(const void *, const void *), + int insert) +{ + int res; + if (*rootp == NULL) { + 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 == NULL) { + return; + } + if (t->left) { + tree_free(t->left); + } + if (t->right) { + tree_free(t->right); + } + reftable_free(t); +} |