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 "tree.h" |
10 | | |
11 | | #include "basics.h" |
12 | | #include "system.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 | 14.3k | { |
18 | 14.3k | if (*rootp == NULL) { |
19 | 594 | if (!insert) { |
20 | 292 | return NULL; |
21 | 302 | } else { |
22 | 302 | struct tree_node *n = |
23 | 302 | reftable_calloc(sizeof(struct tree_node)); |
24 | 302 | n->key = key; |
25 | 302 | *rootp = n; |
26 | 302 | return *rootp; |
27 | 302 | } |
28 | 13.7k | } |
29 | 13.7k | |
30 | 13.7k | { |
31 | 13.7k | int res = compare(key, (*rootp)->key); |
32 | 13.7k | if (res < 0) { |
33 | 44 | return tree_search(key, &(*rootp)->left, compare, |
34 | 44 | insert); |
35 | 13.7k | } else if (res > 0) { |
36 | 13.5k | return tree_search(key, &(*rootp)->right, compare, |
37 | 13.5k | insert); |
38 | 13.5k | } |
39 | 180 | } |
40 | 180 | return *rootp; |
41 | 180 | } |
42 | | |
43 | | void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), |
44 | | void *arg) |
45 | 866 | { |
46 | 866 | if (t->left != NULL) { |
47 | 11 | infix_walk(t->left, action, arg); |
48 | 11 | } |
49 | 866 | action(arg, t->key); |
50 | 866 | if (t->right != NULL) { |
51 | 825 | infix_walk(t->right, action, arg); |
52 | 825 | } |
53 | 866 | } |
54 | | |
55 | | void tree_free(struct tree_node *t) |
56 | 302 | { |
57 | 302 | if (t == NULL) { |
58 | 0 | return; |
59 | 0 | } |
60 | 302 | if (t->left != NULL) { |
61 | 7 | tree_free(t->left); |
62 | 7 | } |
63 | 302 | if (t->right != NULL) { |
64 | 279 | tree_free(t->right); |
65 | 279 | } |
66 | 302 | reftable_free(t); |
67 | 302 | } |