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
|
/*
* KPL tree
*/
#pragma once
// tree_duplicates is a linked stack
#define KPL_TREE_HEADER(STRUCT_NAME) \
struct STRUCT_NAME *tree_left, *tree_right, *tree_duplicates; \
int32_t tree_height
/*
* Recursive AVL saves 8 bytes per object (no need for parent pointer) and keeps the insertion and finding simple
*/
typedef struct _kpl_tree_node {
KPL_TREE_HEADER(_kpl_tree_node);
} kpl_tree_node;
typedef enum : int32_t {
KPL_TREE_TREE_HEIGHT_INIT = 1
} kpl_tree_enum;
/*
* -1 search left, 1 search right, 0 found
*/
typedef int32_t kpl_tree_node_compare_fn(const void *node_a, const void *node_b);
typedef void kpl_tree_node_free_fn(void *node);
/*
* KPL needs trees with insertion and find operations, deletion is not needed, all nodes are freed on tree free
*/
typedef struct {
kpl_tree_node *root_node;
kpl_tree_node_compare_fn *node_compare_fn;
kpl_tree_node_free_fn *node_free_fn;
} kpl_tree;
#define KPL_TREE_INIT_STATIC(COMPARE_FN, FREE_FN) \
(kpl_tree) { .root_node = NULL, .node_compare_fn = COMPARE_FN, .node_free_fn = FREE_FN }
inline void kpl_tree_init(kpl_tree *tree, kpl_tree_node_compare_fn node_compare_fn,
kpl_tree_node_free_fn node_free_fn) {
tree->root_node = NULL;
tree->node_compare_fn = node_compare_fn;
tree->node_free_fn = node_free_fn;
}
void kpl_tree_free(kpl_tree *tree);
/*
* *find is stack allocated
* NULL for not found
*/
void *kpl_tree_find(kpl_tree *tree, const void *find_node);
/*
* *insert is heap allocated
* All inserts succeed, duplicates are added to *tree_duplicates
*/
void kpl_tree_insert(kpl_tree *tree, void *insert_node);
|
