1 /**
2 * @file lv_tree.c
3 * Tree.
4 * The nodes are dynamically allocated by the 'lv_mem' module,
5 */
6
7 /*********************
8 * INCLUDES
9 *********************/
10 #include "lv_tree.h"
11 #include "../stdlib/lv_mem.h"
12 #include "../stdlib/lv_string.h"
13
14 #include "lv_assert.h"
15
16 /*********************
17 * DEFINES
18 *********************/
19 #define INIT_CHILDREN_CAP 4
20
21 /**********************
22 * TYPEDEFS
23 **********************/
24
25 /**********************
26 * STATIC PROTOTYPES
27 **********************/
28
29 /**********************
30 * STATIC VARIABLES
31 **********************/
32
33 const lv_tree_class_t lv_tree_node_class = {
34 .base_class = NULL,
35 .instance_size = sizeof(lv_tree_node_t),
36 .constructor_cb = NULL,
37 .destructor_cb = NULL,
38 };
39
40 /**********************
41 * MACROS
42 **********************/
43
44 /**********************
45 * GLOBAL FUNCTIONS
46 **********************/
47
_lv_tree_node_construct(const lv_tree_class_t * class_p,lv_tree_node_t * node)48 static void _lv_tree_node_construct(const lv_tree_class_t * class_p, lv_tree_node_t * node)
49 {
50 if(node->class_p->base_class) {
51 const lv_tree_class_t * original_class_p = node->class_p;
52
53 node->class_p = node->class_p->base_class;
54
55 _lv_tree_node_construct(class_p, node);
56
57 node->class_p = original_class_p;
58 }
59
60 if(node->class_p->constructor_cb) node->class_p->constructor_cb(class_p, node);
61 }
62
_lv_tree_node_destruct(lv_tree_node_t * node)63 static void _lv_tree_node_destruct(lv_tree_node_t * node)
64 {
65 if(node->class_p->destructor_cb) node->class_p->destructor_cb(node->class_p, node);
66
67 if(node->class_p->base_class) {
68 node->class_p = node->class_p->base_class;
69
70 _lv_tree_node_destruct(node);
71 }
72 }
73
get_instance_size(const lv_tree_class_t * class_p)74 static uint32_t get_instance_size(const lv_tree_class_t * class_p)
75 {
76 const lv_tree_class_t * base = class_p;
77 while(base && base->instance_size == 0)
78 base = base->base_class;
79
80 return base->instance_size;
81 }
82
_lv_tree_class_create_node(const lv_tree_class_t * class_p,lv_tree_node_t * parent)83 static lv_tree_node_t * _lv_tree_class_create_node(const lv_tree_class_t * class_p, lv_tree_node_t * parent)
84 {
85 uint32_t s = get_instance_size(class_p);
86 lv_tree_node_t * node = lv_malloc(s);
87 if(node == NULL) return NULL;
88 lv_memzero(node, s);
89 node->class_p = class_p;
90 node->parent = parent;
91 node->child_cap = INIT_CHILDREN_CAP;
92 node->children = lv_malloc(sizeof(lv_tree_node_t *) * node->child_cap);
93 if(parent != NULL) {
94 parent->child_cnt++;
95 if(parent->child_cnt == parent->child_cap) {
96 parent->child_cap <<= 1;
97 parent->children = lv_realloc(parent->children, sizeof(lv_tree_node_t *) * parent->child_cap);
98 }
99 parent->children[parent->child_cnt - 1] = node;
100 }
101 return node;
102 }
103
lv_tree_node_create(const lv_tree_class_t * class_p,lv_tree_node_t * parent)104 lv_tree_node_t * lv_tree_node_create(const lv_tree_class_t * class_p, lv_tree_node_t * parent)
105 {
106 LV_ASSERT_NULL(class_p);
107 lv_tree_node_t * node = _lv_tree_class_create_node(class_p, parent);
108 LV_ASSERT_NULL(node);
109 _lv_tree_node_construct(node->class_p, node);
110 return node;
111 }
112
_lv_tree_node_destructor_cb(const lv_tree_node_t * n,void * user_data)113 static bool _lv_tree_node_destructor_cb(const lv_tree_node_t * n, void * user_data)
114 {
115 LV_UNUSED(user_data);
116 if(n) {
117 lv_tree_node_t * node = (lv_tree_node_t *)n;
118 _lv_tree_node_destruct(node);
119 lv_free(node->children);
120 lv_free(node);
121 }
122 return true;
123 }
124
lv_tree_node_delete(lv_tree_node_t * node)125 void lv_tree_node_delete(lv_tree_node_t * node)
126 {
127 if(node) {
128 if(node->parent) {
129 /* Remove from parent */
130 lv_tree_node_t * parent = node->parent;
131 for(uint32_t i = 0; i < parent->child_cnt; i++) {
132 if(parent->children[i] == node) {
133 parent->children[i] = NULL;
134 }
135 }
136 }
137 lv_tree_walk(node, LV_TREE_WALK_POST_ORDER, _lv_tree_node_destructor_cb, NULL, NULL, NULL);
138 }
139 }
140
lv_tree_walk(const lv_tree_node_t * node,lv_tree_walk_mode_t mode,lv_tree_traverse_cb_t cb,lv_tree_before_cb_t bcb,lv_tree_after_cb_t acb,void * user_data)141 bool lv_tree_walk(const lv_tree_node_t * node,
142 lv_tree_walk_mode_t mode,
143 lv_tree_traverse_cb_t cb,
144 lv_tree_before_cb_t bcb,
145 lv_tree_after_cb_t acb,
146 void * user_data)
147 {
148 if(node && cb) {
149 if(mode == LV_TREE_WALK_PRE_ORDER) {
150 if(bcb && !bcb(node, user_data)) {
151 return false;
152 }
153 if(!cb(node, user_data)) {
154 return false;
155 }
156 }
157 for(uint32_t i = 0; i < node->child_cnt; i++) {
158 if(!lv_tree_walk(node->children[i], mode, cb, bcb, acb, user_data)) {
159 return false;
160 }
161 }
162 if(mode == LV_TREE_WALK_PRE_ORDER) {
163 if(acb) {
164 acb(node, user_data);
165 }
166 }
167
168 if(mode == LV_TREE_WALK_POST_ORDER) {
169 if(bcb && !bcb(node, user_data)) {
170 return false;
171 }
172 if(!cb(node, user_data)) {
173 return false;
174 }
175 if(acb) {
176 acb(node, user_data);
177 }
178 return true;
179 }
180 else {
181 return true;
182 }
183 }
184 else {
185 return true;
186 }
187 }
188
