git

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
{
18
	int res;
19
	if (!*rootp) {
20
		if (!insert) {
21
			return NULL;
22
		} else {
23
			struct tree_node *n;
24
			REFTABLE_CALLOC_ARRAY(n, 1);
25
			n->key = key;
26
			*rootp = n;
27
			return *rootp;
28
		}
29
	}
30

31
	res = compare(key, (*rootp)->key);
32
	if (res < 0)
33
		return tree_search(key, &(*rootp)->left, compare, insert);
34
	else if (res > 0)
35
		return tree_search(key, &(*rootp)->right, compare, insert);
36
	return *rootp;
37
}
38

39
void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key),
40
		void *arg)
41
{
42
	if (t->left)
43
		infix_walk(t->left, action, arg);
44
	action(arg, t->key);
45
	if (t->right)
46
		infix_walk(t->right, action, arg);
47
}
48

49
void tree_free(struct tree_node *t)
50
{
51
	if (!t)
52
		return;
53
	if (t->left)
54
		tree_free(t->left);
55
	if (t->right)
56
		tree_free(t->right);
57
	reftable_free(t);
58
}
59