types/tree.c at master · toomish/types · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#define _GNU_SOURCE

#include <assert.h>
#include <search.h>
#include <string.h>

#include "tree.h"

void tree_init(tree_t *tree, cmp_func_t cmp)
{
	memset(tree, 0, sizeof(*tree));

	tree->cmp = cmp;
}

void tree_init_full(tree_t *tree, cmp_func_t cmp, free_func_t destroy)
{
	tree_init(tree, cmp);
	tree->destroy = destroy;
}

bool tree_add(tree_t *tree, const void *key)
{
	bool is_new_item = true;

	void **node = tsearch(key, &tree->root, tree->cmp);

	assert(node);

	if (*node != key) {
		if (tree->destroy)
			tree->destroy(*node);

		*node = (void *) key;
		is_new_item = false;
	}

	return is_new_item;;
}

void *tree_find(tree_t *tree, const void *key)
{
	void **node = tfind(key, &tree->root, tree->cmp);

	return node ? *node : NULL;
}

bool tree_remove(tree_t *tree, const void *key)
{
	if (! tree->destroy)
		return tdelete(key, &tree->root, tree->cmp) != NULL;

	void **node = tfind(key, &tree->root, tree->cmp);

	if (! node)
		return false;

	void *tmp = *node;

	tdelete(key, &tree->root, tree->cmp);
	tree->destroy(tmp);

	return true;
}

void tree_foreach(tree_t *tree, tree_walker_t walk, void *data)
{
	__extension__
	void action(const void *nodep, const VISIT which, const int depth)
	{
		if (which == postorder || which == leaf)
			walk(*(void **) nodep, data);
	}

	twalk(tree->root, action);
}

static void nothing(void *data) { (void) data; }

void tree_clean(tree_t *tree)
{
	tdestroy(tree->root, tree->destroy ? tree->destroy : nothing);
	tree->root = NULL;
}