freshlybakedca.ke
Git fork
1/*
2 * Copyright 2020 Google LLC
3 *
4 * Use of this source code is governed by a BSD-style
5 * license that can be found in the LICENSE file or at
6 * https://developers.google.com/open-source/licenses/bsd
7 */
8
9#include "system.h"
10#include "tree.h"
11
12#include "basics.h"
13
14struct tree_node *tree_search(struct tree_node *tree,
15 void *key,
16 int (*compare)(const void *, const void *))
17{
18 int res;
19 if (!tree)
20 return NULL;
21 res = compare(key, tree->key);
22 if (res < 0)
23 return tree_search(tree->left, key, compare);
24 else if (res > 0)
25 return tree_search(tree->right, key, compare);
26 return tree;
27}
28
29struct tree_node *tree_insert(struct tree_node **rootp,
30 void *key,
31 int (*compare)(const void *, const void *))
32{
33 int res;
34
35 if (!*rootp) {
36 struct tree_node *n;
37
38 REFTABLE_CALLOC_ARRAY(n, 1);
39 if (!n)
40 return NULL;
41
42 n->key = key;
43 *rootp = n;
44 return *rootp;
45 }
46
47 res = compare(key, (*rootp)->key);
48 if (res < 0)
49 return tree_insert(&(*rootp)->left, key, compare);
50 else if (res > 0)
51 return tree_insert(&(*rootp)->right, key, compare);
52 return *rootp;
53}
54
55void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key),
56 void *arg)
57{
58 if (t->left)
59 infix_walk(t->left, action, arg);
60 action(arg, t->key);
61 if (t->right)
62 infix_walk(t->right, action, arg);
63}
64
65void tree_free(struct tree_node *t)
66{
67 if (!t)
68 return;
69 if (t->left)
70 tree_free(t->left);
71 if (t->right)
72 tree_free(t->right);
73 reftable_free(t);
74}