Line | Count | Source (jump to first uncovered line) |
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 | | |
14 | | struct tree_node *tree_search(void *key, struct tree_node **rootp, |
15 | | int (*compare)(const void *, const void *), |
16 | | int insert) |
17 | 0 | { |
18 | 0 | int res; |
19 | 0 | if (!*rootp) { |
20 | 0 | if (!insert) { |
21 | 0 | return NULL; |
22 | 0 | } else { |
23 | 0 | struct tree_node *n; |
24 | 0 | REFTABLE_CALLOC_ARRAY(n, 1); |
25 | 0 | n->key = key; |
26 | 0 | *rootp = n; |
27 | 0 | return *rootp; |
28 | 0 | } |
29 | 0 | } |
30 | | |
31 | 0 | res = compare(key, (*rootp)->key); |
32 | 0 | if (res < 0) |
33 | 0 | return tree_search(key, &(*rootp)->left, compare, insert); |
34 | 0 | else if (res > 0) |
35 | 0 | return tree_search(key, &(*rootp)->right, compare, insert); |
36 | 0 | return *rootp; |
37 | 0 | } |
38 | | |
39 | | void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), |
40 | | void *arg) |
41 | 0 | { |
42 | 0 | if (t->left) |
43 | 0 | infix_walk(t->left, action, arg); |
44 | 0 | action(arg, t->key); |
45 | 0 | if (t->right) |
46 | 0 | infix_walk(t->right, action, arg); |
47 | 0 | } |
48 | | |
49 | | void tree_free(struct tree_node *t) |
50 | 0 | { |
51 | 0 | if (!t) |
52 | 0 | return; |
53 | 0 | if (t->left) |
54 | 0 | tree_free(t->left); |
55 | 0 | if (t->right) |
56 | 0 | tree_free(t->right); |
57 | 0 | reftable_free(t); |
58 | 0 | } |