Mercurial > hg > ucx / file comparison

comparison: tests/test_tree.c

tests/test_tree.c

changeset 1681
56e76fbac167
parent 1675
36c0fb2b60b2
equal deleted inserted replaced
1680:1aa21afb8763 1681:56e76fbac167
39 struct tree_node *children; 39 struct tree_node *children;
40 int data; 40 int data;
41 } tree_node; 41 } tree_node;
42 42
43 typedef struct tree_node2 { 43 typedef struct tree_node2 {
44 CX_TREE_NODE_BASE(struct tree_node2); 44 CX_TREE_NODE(struct tree_node2);
45 int data; 45 int data;
46 } tree_node2; 46 } tree_node2;
47 47
48 typedef struct tree_node_file { 48 typedef struct tree_node_file {
49 struct tree_node_file *parent; 49 struct tree_node_file *parent;
52 struct tree_node_file *children; 52 struct tree_node_file *children;
53 struct tree_node_file *last_child; 53 struct tree_node_file *last_child;
54 const char *path; 54 const char *path;
55 } tree_node_file; 55 } tree_node_file;
56 56
57 static void *tree_node_file_create( 57 static int tree_node_file_search_func(const void *l, const void *d) {
58 const void *dptr,
59 void *allocator) {
60 if (allocator == NULL) allocator = (void*) cxDefaultAllocator;
61
62 tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file));
63 node->path = dptr;
64
65 // intentionally write garbage into the pointers, it's part of the test
66 node->parent = (void *) 0xf00ba1;
67 node->next = (void *) 0xf00ba2;
68 node->prev = (void *) 0xf00ba3;
69 node->children = (void *) 0xf00ba4;
70 node->last_child = (void *) 0xf00ba5;
71
72 return node;
73 }
74
75 static void *tree_node_file_create_hl(
76 const void *dptr,
77 void *tree) {
78 return tree_node_file_create(dptr, (void*)((CxTree*)tree)->collection.allocator);
79 }
80
81 static int tree_node_file_search(const void *l, const void *r) {
82 const tree_node_file *left = l; 58 const tree_node_file *left = l;
83 const tree_node_file *right = r; 59 const char *right = d;
84 size_t len1 = strlen(left->path); 60 size_t len1 = strlen(left->path);
85 size_t len2 = strlen(right->path); 61 size_t len2 = strlen(right);
86 if (len1 <= len2) { 62 if (len1 <= len2) {
87 if (memcmp(left->path, right->path, len1) == 0) { 63 if (memcmp(left->path, right, len1) == 0) {
88 return (int) (len2 - len1); 64 return (int) (len2 - len1);
89 } else { 65 } else {
90 return -1; 66 return -1;
91 } 67 }
92 } else { 68 } else {
93 return -1; 69 return -1;
94 } 70 }
95 }
96
97 static int tree_node_file_search_data(const void *l, const void *d) {
98 tree_node_file r;
99 r.path = d;
100 return tree_node_file_search(l, &r);
101 } 71 }
102 72
103 #define tree_node_layout \ 73 #define tree_node_layout \
104 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ 74 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \
105 offsetof(tree_node, prev), offsetof(tree_node, next) 75 offsetof(tree_node, prev), offsetof(tree_node, next)
106 #define tree_node_layout_no_prev \ 76 #define tree_node_layout_no_prev \
107 offsetof(tree_node, parent), offsetof(tree_node, children), -1, -1, \ 77 offsetof(tree_node, parent), offsetof(tree_node, children), -1, -1, \
108 offsetof(tree_node, next) 78 offsetof(tree_node, next)
109 #define tree_node_full_layout(structname) \
110 offsetof(structname, parent), offsetof(structname, children),\
111 offsetof(structname, last_child), \
112 offsetof(structname, prev), offsetof(structname, next)
113 #define tree_node2_layout cx_tree_node_base_layout
114 #define tree_node_file_layout tree_node_full_layout(tree_node_file)
115
116 #define tree_children(type) offsetof(type, children), offsetof(type, next) 79 #define tree_children(type) offsetof(type, children), offsetof(type, next)
117 80
118 CX_TEST(test_tree_link_new_child) { 81 CX_TEST(test_tree_add) {
119 tree_node parent = {0};
120 tree_node child = {0};
121
122 CX_TEST_DO {
123 cx_tree_link(&parent, &child, tree_node_layout);
124 CX_TEST_ASSERT(parent.next == NULL);
125 CX_TEST_ASSERT(parent.prev == NULL);
126 CX_TEST_ASSERT(parent.parent == NULL);
127 CX_TEST_ASSERT(parent.children == &child);
128 CX_TEST_ASSERT(child.parent == &parent);
129 CX_TEST_ASSERT(child.next == NULL);
130 CX_TEST_ASSERT(child.prev == NULL);
131 CX_TEST_ASSERT(child.children == NULL);
132 }
133 }
134
135 CX_TEST(test_tree_link_add_child) {
136 tree_node parent = {0}; 82 tree_node parent = {0};
137 tree_node child1 = {0}; 83 tree_node child1 = {0};
138 tree_node child2 = {0}; 84 tree_node child2 = {0};
139 tree_node child3 = {0}; 85 tree_node child3 = {0};
140 86
141 CX_TEST_DO { 87 CX_TEST_DO {
142 cx_tree_link(&parent, &child1, tree_node_layout); 88 cx_tree_add(&parent, &child1, tree_node_layout);
143 cx_tree_link(&parent, &child2, tree_node_layout); 89 CX_TEST_ASSERT(parent.next == NULL);
144 cx_tree_link(&parent, &child3, tree_node_layout); 90 CX_TEST_ASSERT(parent.prev == NULL);
91 CX_TEST_ASSERT(parent.parent == NULL);
92 CX_TEST_ASSERT(parent.children == &child1);
93 CX_TEST_ASSERT(child1.parent == &parent);
94 CX_TEST_ASSERT(child1.next == NULL);
95 CX_TEST_ASSERT(child1.prev == NULL);
96 CX_TEST_ASSERT(child1.children == NULL);
97
98 cx_tree_add(&parent, &child2, tree_node_layout);
99 cx_tree_add(&parent, &child3, tree_node_layout);
145 CX_TEST_ASSERT(parent.next == NULL); 100 CX_TEST_ASSERT(parent.next == NULL);
146 CX_TEST_ASSERT(parent.prev == NULL); 101 CX_TEST_ASSERT(parent.prev == NULL);
147 CX_TEST_ASSERT(parent.parent == NULL); 102 CX_TEST_ASSERT(parent.parent == NULL);
148 CX_TEST_ASSERT(parent.children == &child1); 103 CX_TEST_ASSERT(parent.children == &child1);
149 104
161 CX_TEST_ASSERT(child3.prev == &child2); 116 CX_TEST_ASSERT(child3.prev == &child2);
162 CX_TEST_ASSERT(child3.next == NULL); 117 CX_TEST_ASSERT(child3.next == NULL);
163 } 118 }
164 } 119 }
165 120
166 CX_TEST(test_tree_link_move_to_other_parent) { 121 CX_TEST(test_tree_add_move_to_other_parent) {
167 tree_node parent = {0}; 122 tree_node parent = {0};
168 tree_node child1 = {0}; 123 tree_node child1 = {0};
169 tree_node child2 = {0}; 124 tree_node child2 = {0};
170 tree_node child3 = {0}; 125 tree_node child3 = {0};
171 cx_tree_link(&parent, &child1, tree_node_layout); 126 cx_tree_add(&parent, &child1, tree_node_layout);
172 cx_tree_link(&parent, &child2, tree_node_layout); 127 cx_tree_add(&parent, &child2, tree_node_layout);
173 cx_tree_link(&parent, &child3, tree_node_layout); 128 cx_tree_add(&parent, &child3, tree_node_layout);
174 129
175 CX_TEST_DO { 130 CX_TEST_DO {
176 cx_tree_link(&child3, &child2, tree_node_layout); 131 cx_tree_add(&child3, &child2, tree_node_layout);
177 132
178 CX_TEST_ASSERT(parent.next == NULL); 133 CX_TEST_ASSERT(parent.next == NULL);
179 CX_TEST_ASSERT(parent.prev == NULL); 134 CX_TEST_ASSERT(parent.prev == NULL);
180 CX_TEST_ASSERT(parent.parent == NULL); 135 CX_TEST_ASSERT(parent.parent == NULL);
181 CX_TEST_ASSERT(parent.children == &child1); 136 CX_TEST_ASSERT(parent.children == &child1);
195 CX_TEST_ASSERT(child2.prev == NULL); 150 CX_TEST_ASSERT(child2.prev == NULL);
196 CX_TEST_ASSERT(child2.next == NULL); 151 CX_TEST_ASSERT(child2.next == NULL);
197 } 152 }
198 } 153 }
199 154
200 CX_TEST(test_tree_unlink) { 155 CX_TEST(test_tree_remove) {
201 tree_node parent = {0}; 156 tree_node parent = {0};
202 tree_node child1 = {0}; 157 tree_node child1 = {0};
203 tree_node child2 = {0}; 158 tree_node child2 = {0};
204 tree_node child3 = {0}; 159 tree_node child3 = {0};
205 tree_node child4 = {0}; 160 tree_node child4 = {0};
206 cx_tree_link(&parent, &child1, tree_node_layout); 161 cx_tree_add(&parent, &child1, tree_node_layout);
207 cx_tree_link(&parent, &child3, tree_node_layout); 162 cx_tree_add(&parent, &child3, tree_node_layout);
208 cx_tree_link(&parent, &child4, tree_node_layout); 163 cx_tree_add(&parent, &child4, tree_node_layout);
209 cx_tree_link(&child3, &child2, tree_node_layout); 164 cx_tree_add(&child3, &child2, tree_node_layout);
210 165
211 CX_TEST_DO { 166 CX_TEST_DO {
212 cx_tree_unlink(&child3, tree_node_layout); 167 cx_tree_remove(&child3, tree_node_layout);
213 168
214 CX_TEST_ASSERT(parent.next == NULL); 169 CX_TEST_ASSERT(parent.next == NULL);
215 CX_TEST_ASSERT(parent.prev == NULL); 170 CX_TEST_ASSERT(parent.prev == NULL);
216 CX_TEST_ASSERT(parent.parent == NULL); 171 CX_TEST_ASSERT(parent.parent == NULL);
217 CX_TEST_ASSERT(parent.children == &child1); 172 CX_TEST_ASSERT(parent.children == &child1);
237 CX_TEST_ASSERT(child2.children == NULL); 192 CX_TEST_ASSERT(child2.children == NULL);
238 CX_TEST_ASSERT(child2.prev == NULL); 193 CX_TEST_ASSERT(child2.prev == NULL);
239 CX_TEST_ASSERT(child2.next == NULL); 194 CX_TEST_ASSERT(child2.next == NULL);
240 195
241 // unlink first child from parent 196 // unlink first child from parent
242 cx_tree_unlink(&child1, tree_node_layout); 197 cx_tree_remove(&child1, tree_node_layout);
243 CX_TEST_ASSERT(parent.next == NULL); 198 CX_TEST_ASSERT(parent.next == NULL);
244 CX_TEST_ASSERT(parent.prev == NULL); 199 CX_TEST_ASSERT(parent.prev == NULL);
245 CX_TEST_ASSERT(parent.parent == NULL); 200 CX_TEST_ASSERT(parent.parent == NULL);
246 CX_TEST_ASSERT(parent.children == &child4); 201 CX_TEST_ASSERT(parent.children == &child4);
247 CX_TEST_ASSERT(child1.parent == NULL); 202 CX_TEST_ASSERT(child1.parent == NULL);
250 CX_TEST_ASSERT(child4.prev == NULL); 205 CX_TEST_ASSERT(child4.prev == NULL);
251 CX_TEST_ASSERT(child4.next == NULL); 206 CX_TEST_ASSERT(child4.next == NULL);
252 } 207 }
253 } 208 }
254 209
255 CX_TEST(test_tree_unlink_no_prev) { 210 CX_TEST(test_tree_remove_no_prev) {
256 tree_node parent = {0}; 211 tree_node parent = {0};
257 tree_node child1 = {0}; 212 tree_node child1 = {0};
258 tree_node child2 = {0}; 213 tree_node child2 = {0};
259 tree_node child3 = {0}; 214 tree_node child3 = {0};
260 tree_node child4 = {0}; 215 tree_node child4 = {0};
261 cx_tree_link(&parent, &child1, tree_node_layout_no_prev); 216 cx_tree_add(&parent, &child1, tree_node_layout_no_prev);
262 cx_tree_link(&parent, &child3, tree_node_layout_no_prev); 217 cx_tree_add(&parent, &child3, tree_node_layout_no_prev);
263 cx_tree_link(&parent, &child4, tree_node_layout_no_prev); 218 cx_tree_add(&parent, &child4, tree_node_layout_no_prev);
264 cx_tree_link(&child3, &child2, tree_node_layout_no_prev); 219 cx_tree_add(&child3, &child2, tree_node_layout_no_prev);
265 void * const marker = (void*) 0xc0ffee; 220 void * const marker = (void*) 0xc0ffee;
266 child1.prev = child2.prev = child3.prev = child4.prev = marker; 221 child1.prev = child2.prev = child3.prev = child4.prev = marker;
267 222
268 CX_TEST_DO { 223 CX_TEST_DO {
269 // in contrast to the other test we here remove child 4 instead of 3! 224 // in contrast to the other test we here remove child 4 instead of 3!
270 cx_tree_unlink(&child4, tree_node_layout_no_prev); 225 cx_tree_remove(&child4, tree_node_layout_no_prev);
271 226
272 CX_TEST_ASSERT(parent.next == NULL); 227 CX_TEST_ASSERT(parent.next == NULL);
273 CX_TEST_ASSERT(parent.prev == NULL); 228 CX_TEST_ASSERT(parent.prev == NULL);
274 CX_TEST_ASSERT(parent.parent == NULL); 229 CX_TEST_ASSERT(parent.parent == NULL);
275 CX_TEST_ASSERT(parent.children == &child1); 230 CX_TEST_ASSERT(parent.children == &child1);
284 CX_TEST_ASSERT(child4.children == NULL); 239 CX_TEST_ASSERT(child4.children == NULL);
285 CX_TEST_ASSERT(child4.prev == marker); 240 CX_TEST_ASSERT(child4.prev == marker);
286 CX_TEST_ASSERT(child4.next == NULL); 241 CX_TEST_ASSERT(child4.next == NULL);
287 242
288 // unlink first child from parent 243 // unlink first child from parent
289 cx_tree_unlink(&child1, tree_node_layout_no_prev); 244 cx_tree_remove(&child1, tree_node_layout_no_prev);
290 CX_TEST_ASSERT(parent.next == NULL); 245 CX_TEST_ASSERT(parent.next == NULL);
291 CX_TEST_ASSERT(parent.prev == NULL); 246 CX_TEST_ASSERT(parent.prev == NULL);
292 CX_TEST_ASSERT(parent.parent == NULL); 247 CX_TEST_ASSERT(parent.parent == NULL);
293 CX_TEST_ASSERT(parent.children == &child3); 248 CX_TEST_ASSERT(parent.children == &child3);
294 CX_TEST_ASSERT(child1.parent == NULL); 249 CX_TEST_ASSERT(child1.parent == NULL);
302 CX_TEST(test_tree2_link_new_child) { 257 CX_TEST(test_tree2_link_new_child) {
303 tree_node2 parent = {0}; 258 tree_node2 parent = {0};
304 tree_node2 child = {0}; 259 tree_node2 child = {0};
305 260
306 CX_TEST_DO { 261 CX_TEST_DO {
307 cx_tree_link(&parent, &child, tree_node2_layout); 262 cx_tree_add(&parent, &child, cx_tree_node_layout(tree_node2));
308 CX_TEST_ASSERT(parent.next == NULL); 263 CX_TEST_ASSERT(parent.next == NULL);
309 CX_TEST_ASSERT(parent.prev == NULL); 264 CX_TEST_ASSERT(parent.prev == NULL);
310 CX_TEST_ASSERT(parent.parent == NULL); 265 CX_TEST_ASSERT(parent.parent == NULL);
311 CX_TEST_ASSERT(parent.children == &child); 266 CX_TEST_ASSERT(parent.children == &child);
312 CX_TEST_ASSERT(parent.last_child == &child); 267 CX_TEST_ASSERT(parent.last_child == &child);
323 tree_node2 child1 = {0}; 278 tree_node2 child1 = {0};
324 tree_node2 child2 = {0}; 279 tree_node2 child2 = {0};
325 tree_node2 child3 = {0}; 280 tree_node2 child3 = {0};
326 281
327 CX_TEST_DO { 282 CX_TEST_DO {
328 cx_tree_link(&parent, &child1, tree_node2_layout); 283 cx_tree_add(&parent, &child1, cx_tree_node_layout(tree_node2));
329 cx_tree_link(&parent, &child2, tree_node2_layout); 284 cx_tree_add(&parent, &child2, cx_tree_node_layout(tree_node2));
330 cx_tree_link(&parent, &child3, tree_node2_layout); 285 cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));
331 CX_TEST_ASSERT(parent.next == NULL); 286 CX_TEST_ASSERT(parent.next == NULL);
332 CX_TEST_ASSERT(parent.prev == NULL); 287 CX_TEST_ASSERT(parent.prev == NULL);
333 CX_TEST_ASSERT(parent.parent == NULL); 288 CX_TEST_ASSERT(parent.parent == NULL);
334 CX_TEST_ASSERT(parent.children == &child1); 289 CX_TEST_ASSERT(parent.children == &child1);
335 CX_TEST_ASSERT(parent.last_child == &child3); 290 CX_TEST_ASSERT(parent.last_child == &child3);
356 CX_TEST(test_tree2_link_move_to_other_parent) { 311 CX_TEST(test_tree2_link_move_to_other_parent) {
357 tree_node2 parent = {0}; 312 tree_node2 parent = {0};
358 tree_node2 child1 = {0}; 313 tree_node2 child1 = {0};
359 tree_node2 child2 = {0}; 314 tree_node2 child2 = {0};
360 tree_node2 child3 = {0}; 315 tree_node2 child3 = {0};
361 cx_tree_link(&parent, &child1, tree_node2_layout); 316 cx_tree_add(&parent, &child1, cx_tree_node_layout(tree_node2));
362 cx_tree_link(&parent, &child2, tree_node2_layout); 317 cx_tree_add(&parent, &child2, cx_tree_node_layout(tree_node2));
363 cx_tree_link(&parent, &child3, tree_node2_layout); 318 cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));
364 319
365 CX_TEST_DO { 320 CX_TEST_DO {
366 cx_tree_link(&child3, &child2, tree_node2_layout); 321 cx_tree_add(&child3, &child2, cx_tree_node_layout(tree_node2));
367 322
368 CX_TEST_ASSERT(parent.next == NULL); 323 CX_TEST_ASSERT(parent.next == NULL);
369 CX_TEST_ASSERT(parent.prev == NULL); 324 CX_TEST_ASSERT(parent.prev == NULL);
370 CX_TEST_ASSERT(parent.parent == NULL); 325 CX_TEST_ASSERT(parent.parent == NULL);
371 CX_TEST_ASSERT(parent.children == &child1); 326 CX_TEST_ASSERT(parent.children == &child1);
394 CX_TEST(test_tree2_unlink) { 349 CX_TEST(test_tree2_unlink) {
395 tree_node2 parent = {0}; 350 tree_node2 parent = {0};
396 tree_node2 child1 = {0}; 351 tree_node2 child1 = {0};
397 tree_node2 child2 = {0}; 352 tree_node2 child2 = {0};
398 tree_node2 child3 = {0}; 353 tree_node2 child3 = {0};
399 cx_tree_link(&parent, &child1, tree_node2_layout); 354 cx_tree_add(&parent, &child1, cx_tree_node_layout(tree_node2));
400 cx_tree_link(&parent, &child3, tree_node2_layout); 355 cx_tree_add(&parent, &child3, cx_tree_node_layout(tree_node2));
401 cx_tree_link(&child3, &child2, tree_node2_layout); 356 cx_tree_add(&child3, &child2, cx_tree_node_layout(tree_node2));
402 357
403 CX_TEST_DO { 358 CX_TEST_DO {
404 cx_tree_unlink(&child3, tree_node2_layout); 359 cx_tree_remove(&child3, cx_tree_node_layout(tree_node2));
405 360
406 CX_TEST_ASSERT(parent.next == NULL); 361 CX_TEST_ASSERT(parent.next == NULL);
407 CX_TEST_ASSERT(parent.prev == NULL); 362 CX_TEST_ASSERT(parent.prev == NULL);
408 CX_TEST_ASSERT(parent.parent == NULL); 363 CX_TEST_ASSERT(parent.parent == NULL);
409 CX_TEST_ASSERT(parent.children == &child1); 364 CX_TEST_ASSERT(parent.children == &child1);
428 CX_TEST_ASSERT(child2.last_child == NULL); 383 CX_TEST_ASSERT(child2.last_child == NULL);
429 CX_TEST_ASSERT(child2.prev == NULL); 384 CX_TEST_ASSERT(child2.prev == NULL);
430 CX_TEST_ASSERT(child2.next == NULL); 385 CX_TEST_ASSERT(child2.next == NULL);
431 386
432 // unlink last child from parent 387 // unlink last child from parent
433 cx_tree_unlink(&child1, tree_node2_layout); 388 cx_tree_remove(&child1, cx_tree_node_layout(tree_node2));
434 CX_TEST_ASSERT(parent.next == NULL); 389 CX_TEST_ASSERT(parent.next == NULL);
435 CX_TEST_ASSERT(parent.prev == NULL); 390 CX_TEST_ASSERT(parent.prev == NULL);
436 CX_TEST_ASSERT(parent.parent == NULL); 391 CX_TEST_ASSERT(parent.parent == NULL);
437 CX_TEST_ASSERT(parent.children == NULL); 392 CX_TEST_ASSERT(parent.children == NULL);
438 CX_TEST_ASSERT(parent.last_child == NULL); 393 CX_TEST_ASSERT(parent.last_child == NULL);
467 422
468 for (unsigned i = 0 ; i <= 10 ; i++) { 423 for (unsigned i = 0 ; i <= 10 ; i++) {
469 testnodes[i]->data = testdata[i]; 424 testnodes[i]->data = testdata[i];
470 } 425 }
471 426
472 cx_tree_link(&root, &a, tree_node_layout); 427 cx_tree_add(&root, &a, tree_node_layout);
473 cx_tree_link(&root, &b, tree_node_layout); 428 cx_tree_add(&root, &b, tree_node_layout);
474 cx_tree_link(&root, &c, tree_node_layout); 429 cx_tree_add(&root, &c, tree_node_layout);
475 430
476 cx_tree_link(&a, &aa, tree_node_layout); 431 cx_tree_add(&a, &aa, tree_node_layout);
477 cx_tree_link(&a, &ab, tree_node_layout); 432 cx_tree_add(&a, &ab, tree_node_layout);
478 433
479 cx_tree_link(&b, &ba, tree_node_layout); 434 cx_tree_add(&b, &ba, tree_node_layout);
480 435
481 cx_tree_link(&c, &ca, tree_node_layout); 436 cx_tree_add(&c, &ca, tree_node_layout);
482 cx_tree_link(&c, &cb, tree_node_layout); 437 cx_tree_add(&c, &cb, tree_node_layout);
483 cx_tree_link(&c, &cc, tree_node_layout); 438 cx_tree_add(&c, &cc, tree_node_layout);
484 439
485 cx_tree_link(&cb, &cba, tree_node_layout); 440 cx_tree_add(&cb, &cba, tree_node_layout);
486 441
487 int s; 442 int s;
488 int r; 443 int r;
489 tree_node *n; 444 tree_node *n;
490 CX_TEST_DO { 445 CX_TEST_DO {
491 for (unsigned i = 0 ; i <= 10 ; i++) { 446 for (unsigned i = 0 ; i <= 10 ; i++) {
492 s = testdata[i]; 447 s = testdata[i];
493 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 448 r = cx_tree_search(&root, 0, &s, test_tree_search_function,
494 (void **) &n, tree_children(tree_node)); 449 (void **) &n, tree_children(tree_node));
495 CX_TEST_ASSERT(r == 0); 450 CX_TEST_ASSERT(r == 0);
496 CX_TEST_ASSERT(n == testnodes[i]); 451 CX_TEST_ASSERT(n == testnodes[i]);
497 } 452 }
498 453
499 s = -5; 454 s = -5;
500 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 455 r = cx_tree_search(&root, 0, &s, test_tree_search_function,
501 (void **) &n, tree_children(tree_node)); 456 (void **) &n, tree_children(tree_node));
502 CX_TEST_ASSERT(r < 0); 457 CX_TEST_ASSERT(r < 0);
503 CX_TEST_ASSERT(n == NULL); 458 CX_TEST_ASSERT(n == NULL);
504 459
505 s = 26; 460 s = 26;
506 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 461 r = cx_tree_search(&root, 0, &s, test_tree_search_function,
507 (void **) &n, tree_children(tree_node)); 462 (void **) &n, tree_children(tree_node));
508 CX_TEST_ASSERT(r > 0); 463 CX_TEST_ASSERT(r > 0);
509 CX_TEST_ASSERT(n == &ba); 464 CX_TEST_ASSERT(n == &ba);
510 465
511 s = 35; 466 s = 35;
512 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 467 r = cx_tree_search(&root, 0, &s, test_tree_search_function,
513 (void **) &n, tree_children(tree_node)); 468 (void **) &n, tree_children(tree_node));
514 CX_TEST_ASSERT(r > 0); 469 CX_TEST_ASSERT(r > 0);
515 CX_TEST_ASSERT(n == &cb); 470 CX_TEST_ASSERT(n == &cb);
516 471
517 s = 38; 472 s = 38;
518 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 473 r = cx_tree_search(&root, 0, &s, test_tree_search_function,
519 (void **) &n, tree_children(tree_node)); 474 (void **) &n, tree_children(tree_node));
520 CX_TEST_ASSERT(r > 0); 475 CX_TEST_ASSERT(r > 0);
521 CX_TEST_ASSERT(n == &cba); 476 CX_TEST_ASSERT(n == &cba);
522 477
523 s = 42; 478 s = 42;
524 r = cx_tree_search_data(&root, 0, &s, test_tree_search_function, 479 r = cx_tree_search(&root, 0, &s, test_tree_search_function,
525 (void **) &n, tree_children(tree_node)); 480 (void **) &n, tree_children(tree_node));
526 CX_TEST_ASSERT(r > 0); 481 CX_TEST_ASSERT(r > 0);
527 CX_TEST_ASSERT(n == &cc); 482 CX_TEST_ASSERT(n == &cc);
528 } 483 }
529 } 484 }
531 CX_TEST(test_tree_search_with_max_depth) { 486 CX_TEST(test_tree_search_with_max_depth) {
532 tree_node_file root = {0}; 487 tree_node_file root = {0};
533 root.path = "/"; 488 root.path = "/";
534 tree_node_file usr = {0}; 489 tree_node_file usr = {0};
535 usr.path = "/usr/"; 490 usr.path = "/usr/";
536 cx_tree_link(&root, &usr, tree_node_file_layout); 491 cx_tree_add(&root, &usr, cx_tree_node_layout(tree_node_file));
537 tree_node_file home = {0}; 492 tree_node_file home = {0};
538 home.path = "/home/"; 493 home.path = "/home/";
539 cx_tree_link(&root, &home, tree_node_file_layout); 494 cx_tree_add(&root, &home, cx_tree_node_layout(tree_node_file));
540 tree_node_file doe = {0}; 495 tree_node_file doe = {0};
541 doe.path = "/home/doe/"; 496 doe.path = "/home/doe/";
542 cx_tree_link(&home, &doe, tree_node_file_layout); 497 cx_tree_add(&home, &doe, cx_tree_node_layout(tree_node_file));
543 tree_node_file lib = {0}; 498 tree_node_file lib = {0};
544 lib.path = "/usr/lib/"; 499 lib.path = "/usr/lib/";
545 cx_tree_link(&usr, &lib, tree_node_file_layout); 500 cx_tree_add(&usr, &lib, cx_tree_node_layout(tree_node_file));
546 tree_node_file modules = {0}; 501 tree_node_file modules = {0};
547 modules.path = "/usr/lib/modules/"; 502 modules.path = "/usr/lib/modules/";
548 cx_tree_link(&lib, &modules, tree_node_file_layout); 503 cx_tree_add(&lib, &modules, cx_tree_node_layout(tree_node_file));
549 504
550 CX_TEST_DO { 505 CX_TEST_DO {
551 int result; 506 int result;
552 void *found; 507 void *found;
553 508
554 result = cx_tree_search_data( 509 result = cx_tree_search(
555 &root, 1, "/", 510 &root, 1, "/",
556 tree_node_file_search_data, &found, 511 tree_node_file_search_func, &found,
557 tree_children(tree_node_file) 512 tree_children(tree_node_file)
558 ); 513 );
559 CX_TEST_ASSERTM(result == 0, "root not found"); 514 CX_TEST_ASSERTM(result == 0, "root not found");
560 CX_TEST_ASSERT(found == &root); 515 CX_TEST_ASSERT(found == &root);
561 516
562 result = cx_tree_search_data( 517 result = cx_tree_search(
563 &root, 1, "/usr/", 518 &root, 1, "/usr/",
564 tree_node_file_search_data, &found, 519 tree_node_file_search_func, &found,
565 tree_children(tree_node_file) 520 tree_children(tree_node_file)
566 ); 521 );
567 CX_TEST_ASSERT(result > 0); 522 CX_TEST_ASSERT(result > 0);
568 CX_TEST_ASSERT(found == &root); 523 CX_TEST_ASSERT(found == &root);
569 524
570 result = cx_tree_search_data( 525 result = cx_tree_search(
571 &root, 2, "/usr/", 526 &root, 2, "/usr/",
572 tree_node_file_search_data, &found, 527 tree_node_file_search_func, &found,
573 tree_children(tree_node_file) 528 tree_children(tree_node_file)
574 ); 529 );
575 CX_TEST_ASSERT(result == 0); 530 CX_TEST_ASSERT(result == 0);
576 CX_TEST_ASSERT(found == &usr); 531 CX_TEST_ASSERT(found == &usr);
577 532
578 result = cx_tree_search_data( 533 result = cx_tree_search(
579 &root, 2, "/usr/lib/", 534 &root, 2, "/usr/lib/",
580 tree_node_file_search_data, &found, 535 tree_node_file_search_func, &found,
581 tree_children(tree_node_file) 536 tree_children(tree_node_file)
582 ); 537 );
583 CX_TEST_ASSERT(result > 0); 538 CX_TEST_ASSERT(result > 0);
584 CX_TEST_ASSERT(found == &usr); 539 CX_TEST_ASSERT(found == &usr);
585 540
586 result = cx_tree_search_data( 541 result = cx_tree_search(
587 &root, 3, "/usr/lib/", 542 &root, 3, "/usr/lib/",
588 tree_node_file_search_data, &found, 543 tree_node_file_search_func, &found,
589 tree_children(tree_node_file) 544 tree_children(tree_node_file)
590 ); 545 );
591 CX_TEST_ASSERTM(result == 0, "lib not found"); 546 CX_TEST_ASSERTM(result == 0, "lib not found");
592 CX_TEST_ASSERT(found == &lib); 547 CX_TEST_ASSERT(found == &lib);
593 548
594 result = cx_tree_search_data( 549 result = cx_tree_search(
595 &root, 1, "/home/", 550 &root, 1, "/home/",
596 tree_node_file_search_data, &found, 551 tree_node_file_search_func, &found,
597 tree_children(tree_node_file) 552 tree_children(tree_node_file)
598 ); 553 );
599 CX_TEST_ASSERT(result > 0); 554 CX_TEST_ASSERT(result > 0);
600 CX_TEST_ASSERT(found == &root); 555 CX_TEST_ASSERT(found == &root);
601 556
602 result = cx_tree_search_data( 557 result = cx_tree_search(
603 &root, 2, "/home/", 558 &root, 2, "/home/",
604 tree_node_file_search_data, &found, 559 tree_node_file_search_func, &found,
605 tree_children(tree_node_file) 560 tree_children(tree_node_file)
606 ); 561 );
607 CX_TEST_ASSERTM(result == 0, "home not found"); 562 CX_TEST_ASSERTM(result == 0, "home not found");
608 CX_TEST_ASSERT(found == &home); 563 CX_TEST_ASSERT(found == &home);
609 564
610 result = cx_tree_search_data( 565 result = cx_tree_search(
611 &root, 2, "/home/doe/", 566 &root, 2, "/home/doe/",
612 tree_node_file_search_data, &found, 567 tree_node_file_search_func, &found,
613 tree_children(tree_node_file) 568 tree_children(tree_node_file)
614 ); 569 );
615 CX_TEST_ASSERT(result > 0); 570 CX_TEST_ASSERT(result > 0);
616 CX_TEST_ASSERT(found == &home); 571 CX_TEST_ASSERT(found == &home);
617 572
618 result = cx_tree_search_data( 573 result = cx_tree_search(
619 &root, 3, "/home/doe/", 574 &root, 3, "/home/doe/",
620 tree_node_file_search_data, &found, 575 tree_node_file_search_func, &found,
621 tree_children(tree_node_file) 576 tree_children(tree_node_file)
622 ); 577 );
623 CX_TEST_ASSERTM(result == 0, "doe not found"); 578 CX_TEST_ASSERTM(result == 0, "doe not found");
624 CX_TEST_ASSERT(found == &doe); 579 CX_TEST_ASSERT(found == &doe);
625 580
626 result = cx_tree_search_data( 581 result = cx_tree_search(
627 &root, 3, "/usr/lib/modules/", 582 &root, 3, "/usr/lib/modules/",
628 tree_node_file_search_data, &found, 583 tree_node_file_search_func, &found,
629 tree_children(tree_node_file) 584 tree_children(tree_node_file)
630 ); 585 );
631 CX_TEST_ASSERT(result > 0); 586 CX_TEST_ASSERT(result > 0);
632 CX_TEST_ASSERT(found == &lib); 587 CX_TEST_ASSERT(found == &lib);
633 588
634 result = cx_tree_search_data( 589 result = cx_tree_search(
635 &root, 4, "/usr/lib/modules/", 590 &root, 4, "/usr/lib/modules/",
636 tree_node_file_search_data, &found, 591 tree_node_file_search_func, &found,
637 tree_children(tree_node_file) 592 tree_children(tree_node_file)
638 ); 593 );
639 CX_TEST_ASSERTM(result == 0, "modules not found (start=root)"); 594 CX_TEST_ASSERTM(result == 0, "modules not found (start=root)");
640 CX_TEST_ASSERT(found == &modules); 595 CX_TEST_ASSERT(found == &modules);
641 596
642 result = cx_tree_search_data( 597 result = cx_tree_search(
643 &usr, 3, "/usr/lib/modules/", 598 &usr, 3, "/usr/lib/modules/",
644 tree_node_file_search_data, &found, 599 tree_node_file_search_func, &found,
645 tree_children(tree_node_file) 600 tree_children(tree_node_file)
646 ); 601 );
647 CX_TEST_ASSERTM(result == 0, "modules not found (start=usr)"); 602 CX_TEST_ASSERTM(result == 0, "modules not found (start=usr)");
648 CX_TEST_ASSERT(found == &modules); 603 CX_TEST_ASSERT(found == &modules);
649 } 604 }
659 CX_TEST_ASSERT(iter.node == &root); 614 CX_TEST_ASSERT(iter.node == &root);
660 CX_TEST_ASSERT(!iter.base.allow_remove); 615 CX_TEST_ASSERT(!iter.base.allow_remove);
661 CX_TEST_ASSERT(!iter.base.remove); 616 CX_TEST_ASSERT(!iter.base.remove);
662 CX_TEST_ASSERT(iter.stack != NULL); 617 CX_TEST_ASSERT(iter.stack != NULL);
663 CX_TEST_ASSERT(iter.stack_capacity > 0); 618 CX_TEST_ASSERT(iter.stack_capacity > 0);
664 CX_TEST_ASSERT(iter.stack_size == 1);
665 CX_TEST_ASSERT(iter.depth == 1); 619 CX_TEST_ASSERT(iter.depth == 1);
666 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); 620 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
667 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); 621 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
668 cxTreeIteratorDispose(&iter); 622 cxTreeIteratorDispose(&iter);
669 CX_TEST_ASSERT(iter.stack == NULL); 623 CX_TEST_ASSERT(iter.stack == NULL);
679 CX_TEST_ASSERT(iter.node == NULL); 633 CX_TEST_ASSERT(iter.node == NULL);
680 CX_TEST_ASSERT(!iter.base.allow_remove); 634 CX_TEST_ASSERT(!iter.base.allow_remove);
681 CX_TEST_ASSERT(!iter.base.remove); 635 CX_TEST_ASSERT(!iter.base.remove);
682 CX_TEST_ASSERT(iter.stack == NULL); 636 CX_TEST_ASSERT(iter.stack == NULL);
683 CX_TEST_ASSERT(iter.stack_capacity == 0); 637 CX_TEST_ASSERT(iter.stack_capacity == 0);
684 CX_TEST_ASSERT(iter.stack_size == 0);
685 CX_TEST_ASSERT(iter.depth == 0); 638 CX_TEST_ASSERT(iter.depth == 0);
686 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); 639 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
687 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); 640 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
688 CX_TEST_ASSERT(!cxIteratorValid(iter)); 641 CX_TEST_ASSERT(!cxIteratorValid(iter));
689 // disposing this iterator should also be harmless 642 // disposing this iterator should also be harmless
710 &b, &ba, 663 &b, &ba,
711 &c, &ca, &cb, &cba, &cc, 664 &c, &ca, &cb, &cba, &cc,
712 }; 665 };
713 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 666 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
714 667
715 cx_tree_link(&root, &a, tree_node_layout); 668 cx_tree_add(&root, &a, tree_node_layout);
716 cx_tree_link(&root, &b, tree_node_layout); 669 cx_tree_add(&root, &b, tree_node_layout);
717 cx_tree_link(&root, &c, tree_node_layout); 670 cx_tree_add(&root, &c, tree_node_layout);
718 cx_tree_link(&a, &aa, tree_node_layout); 671 cx_tree_add(&a, &aa, tree_node_layout);
719 cx_tree_link(&a, &ab, tree_node_layout); 672 cx_tree_add(&a, &ab, tree_node_layout);
720 cx_tree_link(&b, &ba, tree_node_layout); 673 cx_tree_add(&b, &ba, tree_node_layout);
721 cx_tree_link(&c, &ca, tree_node_layout); 674 cx_tree_add(&c, &ca, tree_node_layout);
722 cx_tree_link(&c, &cb, tree_node_layout); 675 cx_tree_add(&c, &cb, tree_node_layout);
723 cx_tree_link(&c, &cc, tree_node_layout); 676 cx_tree_add(&c, &cc, tree_node_layout);
724 cx_tree_link(&cb, &cba, tree_node_layout); 677 cx_tree_add(&cb, &cba, tree_node_layout);
725 CX_TEST_DO { 678 CX_TEST_DO {
726 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node)); 679 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
727 unsigned chk = 0; 680 unsigned chk = 0;
728 cx_foreach(tree_node*, node, iter) { 681 cx_foreach(tree_node*, node, iter) {
729 CX_TEST_ASSERT(node->data == 0); 682 CX_TEST_ASSERT(node->data == 0);
763 tree_node ca = {0}; 716 tree_node ca = {0};
764 tree_node cb = {0}; 717 tree_node cb = {0};
765 tree_node cc = {0}; 718 tree_node cc = {0};
766 tree_node cba = {0}; 719 tree_node cba = {0};
767 720
768 cx_tree_link(&root, &a, tree_node_layout); 721 cx_tree_add(&root, &a, tree_node_layout);
769 cx_tree_link(&root, &b, tree_node_layout); 722 cx_tree_add(&root, &b, tree_node_layout);
770 cx_tree_link(&root, &c, tree_node_layout); 723 cx_tree_add(&root, &c, tree_node_layout);
771 cx_tree_link(&a, &aa, tree_node_layout); 724 cx_tree_add(&a, &aa, tree_node_layout);
772 cx_tree_link(&a, &ab, tree_node_layout); 725 cx_tree_add(&a, &ab, tree_node_layout);
773 cx_tree_link(&b, &ba, tree_node_layout); 726 cx_tree_add(&b, &ba, tree_node_layout);
774 cx_tree_link(&c, &ca, tree_node_layout); 727 cx_tree_add(&c, &ca, tree_node_layout);
775 cx_tree_link(&c, &cb, tree_node_layout); 728 cx_tree_add(&c, &cb, tree_node_layout);
776 cx_tree_link(&c, &cc, tree_node_layout); 729 cx_tree_add(&c, &cc, tree_node_layout);
777 cx_tree_link(&cb, &cba, tree_node_layout); 730 cx_tree_add(&cb, &cba, tree_node_layout);
778 CX_TEST_DO { 731 CX_TEST_DO {
779 CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node)); 732 CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node));
780 unsigned chk = 0; 733 unsigned chk = 0;
781 cx_foreach(tree_node*, node, iter) { 734 cx_foreach(tree_node*, node, iter) {
782 CX_TEST_ASSERT(iter.exiting || node->data == 0); 735 CX_TEST_ASSERT(iter.exiting || node->data == 0);
821 tree_node ca = { 0 }; 774 tree_node ca = { 0 };
822 tree_node cb = { 0 }; 775 tree_node cb = { 0 };
823 tree_node cc = { 0 }; 776 tree_node cc = { 0 };
824 tree_node cba = { 0 }; 777 tree_node cba = { 0 };
825 778
826 cx_tree_link(&root, &a, tree_node_layout); 779 cx_tree_add(&root, &a, tree_node_layout);
827 cx_tree_link(&root, &b, tree_node_layout); 780 cx_tree_add(&root, &b, tree_node_layout);
828 cx_tree_link(&root, &c, tree_node_layout); 781 cx_tree_add(&root, &c, tree_node_layout);
829 cx_tree_link(&a, &aa, tree_node_layout); 782 cx_tree_add(&a, &aa, tree_node_layout);
830 cx_tree_link(&a, &ab, tree_node_layout); 783 cx_tree_add(&a, &ab, tree_node_layout);
831 cx_tree_link(&b, &ba, tree_node_layout); 784 cx_tree_add(&b, &ba, tree_node_layout);
832 cx_tree_link(&c, &ca, tree_node_layout); 785 cx_tree_add(&c, &ca, tree_node_layout);
833 cx_tree_link(&c, &cb, tree_node_layout); 786 cx_tree_add(&c, &cb, tree_node_layout);
834 cx_tree_link(&c, &cc, tree_node_layout); 787 cx_tree_add(&c, &cc, tree_node_layout);
835 cx_tree_link(&cb, &cba, tree_node_layout); 788 cx_tree_add(&cb, &cba, tree_node_layout);
836 CX_TEST_DO{ 789 CX_TEST_DO{
837 CxTreeIterator iter = cx_tree_iterator(&b, true, tree_children(tree_node)); 790 CxTreeIterator iter = cx_tree_iterator(&b, true, tree_children(tree_node));
838 unsigned chk = 0; 791 unsigned chk = 0;
839 cx_foreach(tree_node*, node, iter) { 792 cx_foreach(tree_node*, node, iter) {
840 CX_TEST_ASSERT(iter.exiting || node->data == 0); 793 CX_TEST_ASSERT(iter.exiting || node->data == 0);
929 target.name = "target"; 882 target.name = "target";
930 target_feature.name = "feature"; 883 target_feature.name = "feature";
931 target_dependencies.name = "dependencies"; 884 target_dependencies.name = "dependencies";
932 target_feature_dependencies.name = "dependencies"; 885 target_feature_dependencies.name = "dependencies";
933 886
934 cx_tree_link(&project, &config, tree_node_layout); 887 cx_tree_add(&project, &config, tree_node_layout);
935 cx_tree_link(&project, &dependency1, tree_node_layout); 888 cx_tree_add(&project, &dependency1, tree_node_layout);
936 cx_tree_link(&project, &dependency2, tree_node_layout); 889 cx_tree_add(&project, &dependency2, tree_node_layout);
937 cx_tree_link(&project, &target, tree_node_layout); 890 cx_tree_add(&project, &target, tree_node_layout);
938 cx_tree_link(&config, &var1, tree_node_layout); 891 cx_tree_add(&config, &var1, tree_node_layout);
939 cx_tree_link(&config, &var2, tree_node_layout); 892 cx_tree_add(&config, &var2, tree_node_layout);
940 cx_tree_link(&config, &var3, tree_node_layout); 893 cx_tree_add(&config, &var3, tree_node_layout);
941 cx_tree_link(&dependency1, &dependency1make, tree_node_layout); 894 cx_tree_add(&dependency1, &dependency1make, tree_node_layout);
942 cx_tree_link(&dependency2, &dependency2lang, tree_node_layout); 895 cx_tree_add(&dependency2, &dependency2lang, tree_node_layout);
943 cx_tree_link(&dependency2, &dependency2make, tree_node_layout); 896 cx_tree_add(&dependency2, &dependency2make, tree_node_layout);
944 cx_tree_link(&target, &target_feature, tree_node_layout); 897 cx_tree_add(&target, &target_feature, tree_node_layout);
945 cx_tree_link(&target, &target_dependencies, tree_node_layout); 898 cx_tree_add(&target, &target_dependencies, tree_node_layout);
946 cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout); 899 cx_tree_add(&target_feature, &target_feature_dependencies, tree_node_layout);
947 900
948 const char *expected = 901 const char *expected =
949 "<project><config><var></var><var></var><var></var></config>" 902 "<project><config><var></var><var></var><var></var></config>"
950 "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>" 903 "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>"
951 "<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>"; 904 "<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>";
984 tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node)); 937 tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node));
985 tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node)); 938 tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node));
986 tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node)); 939 tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node));
987 tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node)); 940 tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node));
988 941
989 cx_tree_link(root, a, tree_node_layout); 942 cx_tree_add(root, a, tree_node_layout);
990 cx_tree_link(root, b, tree_node_layout); 943 cx_tree_add(root, b, tree_node_layout);
991 cx_tree_link(root, c, tree_node_layout); 944 cx_tree_add(root, c, tree_node_layout);
992 cx_tree_link(a, aa, tree_node_layout); 945 cx_tree_add(a, aa, tree_node_layout);
993 cx_tree_link(a, ab, tree_node_layout); 946 cx_tree_add(a, ab, tree_node_layout);
994 cx_tree_link(b, ba, tree_node_layout); 947 cx_tree_add(b, ba, tree_node_layout);
995 cx_tree_link(c, ca, tree_node_layout); 948 cx_tree_add(c, ca, tree_node_layout);
996 cx_tree_link(c, cb, tree_node_layout); 949 cx_tree_add(c, cb, tree_node_layout);
997 cx_tree_link(c, cc, tree_node_layout); 950 cx_tree_add(c, cc, tree_node_layout);
998 cx_tree_link(cb, cba, tree_node_layout); 951 cx_tree_add(cb, cba, tree_node_layout);
999 952
1000 CxTreeIterator iter = cx_tree_iterator(root, true, tree_children(tree_node)); 953 CxTreeIterator iter = cx_tree_iterator(root, true, tree_children(tree_node));
1001 cx_foreach(tree_node *, node, iter) { 954 cx_foreach(tree_node *, node, iter) {
1002 if (iter.exiting) { 955 if (iter.exiting) {
1003 cxFree(alloc,node); 956 cxFree(alloc,node);
1011 964
1012 CX_TEST(test_tree_visitor_create_and_dispose) { 965 CX_TEST(test_tree_visitor_create_and_dispose) {
1013 tree_node root = {0}; 966 tree_node root = {0};
1014 tree_node child = {0}; 967 tree_node child = {0};
1015 tree_node child2 = {0}; 968 tree_node child2 = {0};
1016 cx_tree_link(&root, &child, tree_node_layout); 969 cx_tree_add(&root, &child, tree_node_layout);
1017 cx_tree_link(&root, &child2, tree_node_layout); 970 cx_tree_add(&root, &child2, tree_node_layout);
1018 CX_TEST_DO { 971 CX_TEST_DO {
1019 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 972 CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
1020 CX_TEST_ASSERT(iter.counter == 1); 973 CX_TEST_ASSERT(iter.counter == 1);
1021 CX_TEST_ASSERT(iter.node == &root); 974 CX_TEST_ASSERT(iter.node == &root);
1022 CX_TEST_ASSERT(!iter.base.allow_remove); 975 CX_TEST_ASSERT(!iter.base.allow_remove);
1023 CX_TEST_ASSERT(!iter.base.remove); 976 CX_TEST_ASSERT(!iter.base.remove);
1024 CX_TEST_ASSERT(iter.depth == 1); 977 CX_TEST_ASSERT(iter.depth == 1);
1027 cxIteratorNext(iter); 980 cxIteratorNext(iter);
1028 CX_TEST_ASSERT(iter.queue_next != NULL); 981 CX_TEST_ASSERT(iter.queue_next != NULL);
1029 CX_TEST_ASSERT(iter.queue_last != NULL); 982 CX_TEST_ASSERT(iter.queue_last != NULL);
1030 CX_TEST_ASSERT(iter.queue_next->node == &child2); 983 CX_TEST_ASSERT(iter.queue_next->node == &child2);
1031 CX_TEST_ASSERT(iter.queue_last->node == &child2); 984 CX_TEST_ASSERT(iter.queue_last->node == &child2);
1032 cxTreeVisitorDispose(&iter); 985 cxTreeIteratorDispose(&iter);
1033 CX_TEST_ASSERT(iter.queue_next == NULL); 986 CX_TEST_ASSERT(iter.queue_next == NULL);
1034 CX_TEST_ASSERT(iter.queue_last == NULL); 987 CX_TEST_ASSERT(iter.queue_last == NULL);
1035 } 988 }
1036 } 989 }
1037 990
1054 &aa, &ab, &ba, &ca, &cb, &cc, 1007 &aa, &ab, &ba, &ca, &cb, &cc,
1055 &cba 1008 &cba
1056 }; 1009 };
1057 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 1010 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
1058 1011
1059 cx_tree_link(&root, &a, tree_node_layout); 1012 cx_tree_add(&root, &a, tree_node_layout);
1060 cx_tree_link(&root, &b, tree_node_layout); 1013 cx_tree_add(&root, &b, tree_node_layout);
1061 cx_tree_link(&root, &c, tree_node_layout); 1014 cx_tree_add(&root, &c, tree_node_layout);
1062 cx_tree_link(&a, &aa, tree_node_layout); 1015 cx_tree_add(&a, &aa, tree_node_layout);
1063 cx_tree_link(&a, &ab, tree_node_layout); 1016 cx_tree_add(&a, &ab, tree_node_layout);
1064 cx_tree_link(&b, &ba, tree_node_layout); 1017 cx_tree_add(&b, &ba, tree_node_layout);
1065 cx_tree_link(&c, &ca, tree_node_layout); 1018 cx_tree_add(&c, &ca, tree_node_layout);
1066 cx_tree_link(&c, &cb, tree_node_layout); 1019 cx_tree_add(&c, &cb, tree_node_layout);
1067 cx_tree_link(&c, &cc, tree_node_layout); 1020 cx_tree_add(&c, &cc, tree_node_layout);
1068 cx_tree_link(&cb, &cba, tree_node_layout); 1021 cx_tree_add(&cb, &cba, tree_node_layout);
1069 CX_TEST_DO { 1022 CX_TEST_DO {
1070 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1023 CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
1071 unsigned chk = 0; 1024 unsigned chk = 0;
1072 cx_foreach(tree_node*, node, iter) { 1025 cx_foreach(tree_node*, node, iter) {
1073 CX_TEST_ASSERT(node->data == 0); 1026 CX_TEST_ASSERT(node->data == 0);
1074 node->data++; 1027 node->data++;
1075 actual_order[chk] = node; 1028 actual_order[chk] = node;
1098 1051
1099 CX_TEST(test_tree_visitor_no_children) { 1052 CX_TEST(test_tree_visitor_no_children) {
1100 tree_node root = {0}; 1053 tree_node root = {0};
1101 1054
1102 CX_TEST_DO { 1055 CX_TEST_DO {
1103 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1056 CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
1104 unsigned chk = 0; 1057 unsigned chk = 0;
1105 cx_foreach(tree_node*, node, iter) { 1058 cx_foreach(tree_node*, node, iter) {
1106 CX_TEST_ASSERT(node == iter.node); 1059 CX_TEST_ASSERT(node == iter.node);
1107 chk++; 1060 chk++;
1108 } 1061 }
1122 tree_node* expected_order[] = { 1075 tree_node* expected_order[] = {
1123 &root, &a, &b, &c 1076 &root, &a, &b, &c
1124 }; 1077 };
1125 tree_node* actual_order[4]; 1078 tree_node* actual_order[4];
1126 1079
1127 cx_tree_link(&root, &a, tree_node_layout); 1080 cx_tree_add(&root, &a, tree_node_layout);
1128 cx_tree_link(&a, &b, tree_node_layout); 1081 cx_tree_add(&a, &b, tree_node_layout);
1129 cx_tree_link(&b, &c, tree_node_layout); 1082 cx_tree_add(&b, &c, tree_node_layout);
1130 1083
1131 CX_TEST_DO { 1084 CX_TEST_DO {
1132 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1085 CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
1133 unsigned chk = 0; 1086 unsigned chk = 0;
1134 cx_foreach(tree_node*, node, iter) { 1087 cx_foreach(tree_node*, node, iter) {
1135 CX_TEST_ASSERT(node == iter.node); 1088 CX_TEST_ASSERT(node == iter.node);
1136 CX_TEST_ASSERT(node->data == 0); 1089 CX_TEST_ASSERT(node->data == 0);
1137 node->data++; 1090 node->data++;
1162 tree_node* expected_order[] = { 1115 tree_node* expected_order[] = {
1163 &b, &ba, &bb, &bc, &bba 1116 &b, &ba, &bb, &bc, &bba
1164 }; 1117 };
1165 tree_node* actual_order[5]; 1118 tree_node* actual_order[5];
1166 1119
1167 cx_tree_link(&root, &a, tree_node_layout); 1120 cx_tree_add(&root, &a, tree_node_layout);
1168 cx_tree_link(&root, &b, tree_node_layout); 1121 cx_tree_add(&root, &b, tree_node_layout);
1169 cx_tree_link(&root, &c, tree_node_layout); 1122 cx_tree_add(&root, &c, tree_node_layout);
1170 cx_tree_link(&b, &ba, tree_node_layout); 1123 cx_tree_add(&b, &ba, tree_node_layout);
1171 cx_tree_link(&b, &bb, tree_node_layout); 1124 cx_tree_add(&b, &bb, tree_node_layout);
1172 cx_tree_link(&b, &bc, tree_node_layout); 1125 cx_tree_add(&b, &bc, tree_node_layout);
1173 cx_tree_link(&bb, &bba, tree_node_layout); 1126 cx_tree_add(&bb, &bba, tree_node_layout);
1174 1127
1175 CX_TEST_DO { 1128 CX_TEST_DO {
1176 CxTreeVisitor iter = cx_tree_visitor(&b, tree_children(tree_node)); 1129 CxTreeIterator iter = cx_tree_visitor(&b, tree_children(tree_node));
1177 unsigned chk = 0; 1130 unsigned chk = 0;
1178 cx_foreach(tree_node*, node, iter) { 1131 cx_foreach(tree_node*, node, iter) {
1179 CX_TEST_ASSERT(node == iter.node); 1132 CX_TEST_ASSERT(node == iter.node);
1180 CX_TEST_ASSERT(node->data == 0); 1133 CX_TEST_ASSERT(node->data == 0);
1181 node->data++; 1134 node->data++;
1211 &a, &b, &c, 1164 &a, &b, &c,
1212 &aa, &ab, &ba 1165 &aa, &ab, &ba
1213 }; 1166 };
1214 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 1167 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
1215 1168
1216 cx_tree_link(&root, &a, tree_node_layout); 1169 cx_tree_add(&root, &a, tree_node_layout);
1217 cx_tree_link(&root, &b, tree_node_layout); 1170 cx_tree_add(&root, &b, tree_node_layout);
1218 cx_tree_link(&root, &c, tree_node_layout); 1171 cx_tree_add(&root, &c, tree_node_layout);
1219 cx_tree_link(&a, &aa, tree_node_layout); 1172 cx_tree_add(&a, &aa, tree_node_layout);
1220 cx_tree_link(&a, &ab, tree_node_layout); 1173 cx_tree_add(&a, &ab, tree_node_layout);
1221 cx_tree_link(&b, &ba, tree_node_layout); 1174 cx_tree_add(&b, &ba, tree_node_layout);
1222 cx_tree_link(&c, &ca, tree_node_layout); 1175 cx_tree_add(&c, &ca, tree_node_layout);
1223 cx_tree_link(&c, &cb, tree_node_layout); 1176 cx_tree_add(&c, &cb, tree_node_layout);
1224 cx_tree_link(&c, &cc, tree_node_layout); 1177 cx_tree_add(&c, &cc, tree_node_layout);
1225 cx_tree_link(&cb, &cba, tree_node_layout); 1178 cx_tree_add(&cb, &cba, tree_node_layout);
1226 CX_TEST_DO { 1179 CX_TEST_DO {
1227 CxTreeVisitor iter = cx_tree_visitor(&root, tree_children(tree_node)); 1180 CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
1228 unsigned chk = 0; 1181 unsigned chk = 0;
1229 cx_foreach(tree_node*, node, iter) { 1182 cx_foreach(tree_node*, node, iter) {
1230 CX_TEST_ASSERT(node->data == 0); 1183 CX_TEST_ASSERT(node->data == 0);
1231 node->data++; 1184 node->data++;
1232 actual_order[chk] = node; 1185 actual_order[chk] = node;
1238 CX_TEST_ASSERT(iter.depth == 2); 1191 CX_TEST_ASSERT(iter.depth == 2);
1239 } else { 1192 } else {
1240 CX_TEST_ASSERT(iter.depth == 3); 1193 CX_TEST_ASSERT(iter.depth == 3);
1241 } 1194 }
1242 if (node == &c) { 1195 if (node == &c) {
1243 cxTreeVisitorContinue(iter); 1196 cxTreeIteratorContinue(iter);
1244 } 1197 }
1245 } 1198 }
1246 CX_TEST_ASSERT(iter.counter == 7); 1199 CX_TEST_ASSERT(iter.counter == 7);
1247 CX_TEST_ASSERT(chk == 7); 1200 CX_TEST_ASSERT(chk == 7);
1248 for (unsigned i = 0 ; i < chk ; i++) { 1201 for (unsigned i = 0 ; i < chk ; i++) {
1277 &b, &ba, 1230 &b, &ba,
1278 &c, 1231 &c,
1279 }; 1232 };
1280 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 1233 tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
1281 1234
1282 cx_tree_link(&root, &a, tree_node_layout); 1235 cx_tree_add(&root, &a, tree_node_layout);
1283 cx_tree_link(&root, &b, tree_node_layout); 1236 cx_tree_add(&root, &b, tree_node_layout);
1284 cx_tree_link(&root, &c, tree_node_layout); 1237 cx_tree_add(&root, &c, tree_node_layout);
1285 cx_tree_link(&a, &aa, tree_node_layout); 1238 cx_tree_add(&a, &aa, tree_node_layout);
1286 cx_tree_link(&a, &ab, tree_node_layout); 1239 cx_tree_add(&a, &ab, tree_node_layout);
1287 cx_tree_link(&b, &ba, tree_node_layout); 1240 cx_tree_add(&b, &ba, tree_node_layout);
1288 cx_tree_link(&c, &ca, tree_node_layout); 1241 cx_tree_add(&c, &ca, tree_node_layout);
1289 cx_tree_link(&c, &cb, tree_node_layout); 1242 cx_tree_add(&c, &cb, tree_node_layout);
1290 cx_tree_link(&c, &cc, tree_node_layout); 1243 cx_tree_add(&c, &cc, tree_node_layout);
1291 cx_tree_link(&cb, &cba, tree_node_layout); 1244 cx_tree_add(&cb, &cba, tree_node_layout);
1292 CX_TEST_DO { 1245 CX_TEST_DO {
1293 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node)); 1246 CxTreeIterator iter = cx_tree_iterator(&root, false, tree_children(tree_node));
1294 unsigned chk = 0; 1247 unsigned chk = 0;
1295 cx_foreach(tree_node*, node, iter) { 1248 cx_foreach(tree_node*, node, iter) {
1296 CX_TEST_ASSERT(node->data == 0); 1249 CX_TEST_ASSERT(node->data == 0);
1335 tree_node ca = {0}; 1288 tree_node ca = {0};
1336 tree_node cb = {0}; 1289 tree_node cb = {0};
1337 tree_node cc = {0}; 1290 tree_node cc = {0};
1338 tree_node cba = {0}; 1291 tree_node cba = {0};
1339 1292
1340 cx_tree_link(&root, &a, tree_node_layout); 1293 cx_tree_add(&root, &a, tree_node_layout);
1341 cx_tree_link(&root, &b, tree_node_layout); 1294 cx_tree_add(&root, &b, tree_node_layout);
1342 cx_tree_link(&root, &c, tree_node_layout); 1295 cx_tree_add(&root, &c, tree_node_layout);
1343 cx_tree_link(&a, &aa, tree_node_layout); 1296 cx_tree_add(&a, &aa, tree_node_layout);
1344 cx_tree_link(&a, &ab, tree_node_layout); 1297 cx_tree_add(&a, &ab, tree_node_layout);
1345 cx_tree_link(&b, &ba, tree_node_layout); 1298 cx_tree_add(&b, &ba, tree_node_layout);
1346 cx_tree_link(&c, &ca, tree_node_layout); 1299 cx_tree_add(&c, &ca, tree_node_layout);
1347 cx_tree_link(&c, &cb, tree_node_layout); 1300 cx_tree_add(&c, &cb, tree_node_layout);
1348 cx_tree_link(&c, &cc, tree_node_layout); 1301 cx_tree_add(&c, &cc, tree_node_layout);
1349 cx_tree_link(&cb, &cba, tree_node_layout); 1302 cx_tree_add(&cb, &cba, tree_node_layout);
1350 CX_TEST_DO { 1303 CX_TEST_DO {
1351 CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node)); 1304 CxTreeIterator iter = cx_tree_iterator(&root, true, tree_children(tree_node));
1352 unsigned chk = 0; 1305 unsigned chk = 0;
1353 cx_foreach(tree_node*, node, iter) { 1306 cx_foreach(tree_node*, node, iter) {
1354 CX_TEST_ASSERT(iter.exiting || node->data == 0); 1307 CX_TEST_ASSERT(iter.exiting || node->data == 0);
1381 CX_TEST_ASSERT(cc.data == 0); 1334 CX_TEST_ASSERT(cc.data == 0);
1382 CX_TEST_ASSERT(cba.data == 0); 1335 CX_TEST_ASSERT(cba.data == 0);
1383 } 1336 }
1384 } 1337 }
1385 1338
1386 CX_TEST(test_tree_add_one) {
1387 CxTestingAllocator talloc;
1388 cx_testing_allocator_init(&talloc);
1389 CxAllocator *alloc = &talloc.base;
1390
1391 tree_node_file root = {0};
1392 root.path = "/";
1393 tree_node_file usr = {0};
1394 usr.path = "/usr/";
1395 cx_tree_link(&root, &usr, tree_node_file_layout);
1396 tree_node_file home = {0};
1397 home.path = "/home/";
1398 cx_tree_link(&root, &home, tree_node_file_layout);
1399 tree_node_file lib = {0};
1400 lib.path = "/usr/lib/";
1401 cx_tree_link(&usr, &lib, tree_node_file_layout);
1402
1403 CX_TEST_DO {
1404 tree_node_file *foo;
1405 int result;
1406 result = cx_tree_add(
1407 "/home/foo/",
1408 tree_node_file_search,
1409 tree_node_file_create, alloc,
1410 (void **) &foo, &root,
1411 tree_node_file_layout
1412 );
1413 CX_TEST_ASSERT(result == 0);
1414 CX_TEST_ASSERT(foo != NULL);
1415 const char *bar_path = "/home/foo/bar/";
1416 void *failed;
1417 size_t added = cx_tree_add_array(
1418 bar_path, 1, sizeof(const char *),
1419 tree_node_file_search,
1420 tree_node_file_create, alloc,
1421 &failed, &root,
1422 tree_node_file_layout
1423 );
1424 CX_TEST_ASSERT(added == 1);
1425 CX_TEST_ASSERT(failed == NULL);
1426 tree_node_file *bar = foo->children;
1427 CX_TEST_ASSERT(bar != NULL);
1428 CX_TEST_ASSERT(bar->parent == foo);
1429 CX_TEST_ASSERT(bar->path == bar_path);
1430 CX_TEST_ASSERT(foo->parent == &home);
1431
1432 tree_node_file *new_node;
1433 result = cx_tree_add(
1434 "newroot",
1435 tree_node_file_search,
1436 tree_node_file_create, alloc,
1437 (void **) &new_node, &root,
1438 tree_node_file_layout
1439 );
1440 CX_TEST_ASSERT(0 != result);
1441 CX_TEST_ASSERT(NULL != new_node);
1442 CX_TEST_ASSERT(new_node->children == NULL);
1443 CX_TEST_ASSERT(new_node->parent == NULL);
1444
1445 CX_TEST_ASSERT(talloc.alloc_total == 3);
1446
1447 cxFree(alloc, foo);
1448 cxFree(alloc, bar);
1449 cxFree(alloc, new_node);
1450
1451 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1452 }
1453 cx_testing_allocator_destroy(&talloc);
1454 }
1455
1456 CX_TEST(test_tree_add_one_existing) {
1457 CxTestingAllocator talloc;
1458 cx_testing_allocator_init(&talloc);
1459 CxAllocator *alloc = &talloc.base;
1460
1461 tree_node_file root = {0};
1462 root.path = "/";
1463 tree_node_file usr = {0};
1464 usr.path = "/usr/";
1465 cx_tree_link(&root, &usr, tree_node_file_layout);
1466 tree_node_file home = {0};
1467 home.path = "/home/";
1468 cx_tree_link(&root, &home, tree_node_file_layout);
1469 tree_node_file lib = {0};
1470 lib.path = "/usr/lib/";
1471 cx_tree_link(&usr, &lib, tree_node_file_layout);
1472
1473 CX_TEST_DO {
1474 tree_node_file *node;
1475 int result = cx_tree_add(
1476 "/usr/lib/",
1477 tree_node_file_search,
1478 tree_node_file_create, alloc,
1479 (void **) &node, &root,
1480 tree_node_file_layout
1481 );
1482 CX_TEST_ASSERT(result == 0);
1483 CX_TEST_ASSERT(node != &lib);
1484 CX_TEST_ASSERT(node->prev == &lib);
1485 CX_TEST_ASSERT(lib.next == node);
1486 CX_TEST_ASSERT(node->parent == &usr);
1487 CX_TEST_ASSERT(talloc.alloc_total == 1);
1488 cxFree(alloc, node);
1489 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1490 }
1491 cx_testing_allocator_destroy(&talloc);
1492 }
1493
1494 CX_TEST(test_tree_add_one_no_match) {
1495 tree_node_file root = {0};
1496 root.path = "/mnt/";
1497
1498 CX_TEST_DO {
1499 tree_node_file *node = NULL;
1500 int result = cx_tree_add(
1501 "/usr/lib/",
1502 tree_node_file_search,
1503 tree_node_file_create, NULL,
1504 (void **) &node, &root,
1505 tree_node_file_layout
1506 );
1507 CX_TEST_ASSERT(result != 0);
1508 CX_TEST_ASSERT(node != NULL);
1509 CX_TEST_ASSERT(node->parent == NULL);
1510 CX_TEST_ASSERT(node->children == NULL);
1511 cxFreeDefault(node);
1512 node = NULL;
1513 size_t added = cx_tree_add_array(
1514 "/", 1, sizeof(const char *),
1515 tree_node_file_search,
1516 tree_node_file_create, NULL,
1517 (void **) &node, &root,
1518 tree_node_file_layout
1519 );
1520 CX_TEST_ASSERT(added == 0);
1521 CX_TEST_ASSERT(node != NULL);
1522 CX_TEST_ASSERT(node->parent == NULL);
1523 CX_TEST_ASSERT(node->children == NULL);
1524 cxFreeDefault(node);
1525 }
1526 }
1527
1528 CX_TEST(test_tree_add_duplicate_root) {
1529 tree_node_file root = {0};
1530 root.path = "/";
1531 CX_TEST_DO {
1532 tree_node_file *node;
1533 int result = cx_tree_add(
1534 "/",
1535 tree_node_file_search,
1536 tree_node_file_create, NULL,
1537 (void **) &node, &root,
1538 tree_node_file_layout
1539 );
1540 CX_TEST_ASSERT(result == 0);
1541 CX_TEST_ASSERT(root.children == node);
1542 CX_TEST_ASSERT(node->parent == &root);
1543 cxFreeDefault(node);
1544 }
1545 }
1546
1547 CX_TEST(test_tree_add_zero) {
1548 CxTestingAllocator talloc;
1549 cx_testing_allocator_init(&talloc);
1550 CxAllocator *alloc = &talloc.base;
1551
1552 tree_node_file root = {0};
1553 root.path = "/";
1554 CX_TEST_DO {
1555 void *failed;
1556
1557 size_t processed = cx_tree_add_array(
1558 (void *) 0xc0ffee, 0, sizeof(void *),
1559 tree_node_file_search,
1560 tree_node_file_create, alloc,
1561 &failed, &root, tree_node_file_layout
1562 );
1563 CX_TEST_ASSERT(failed == NULL);
1564 CX_TEST_ASSERT(processed == 0);
1565 CX_TEST_ASSERT(talloc.alloc_total == 0);
1566
1567 CxIterator iter = cxIterator(NULL, sizeof(void *), 0);
1568 processed = cx_tree_add_iter(
1569 cxIteratorRef(iter),
1570 10, // deliberately specify more than the iter has
1571 tree_node_file_search,
1572 tree_node_file_create, alloc,
1573 &failed, &root, tree_node_file_layout
1574 );
1575 CX_TEST_ASSERT(processed == 0);
1576 CX_TEST_ASSERT(failed == NULL);
1577 CX_TEST_ASSERT(talloc.alloc_total == 0);
1578
1579 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1580 }
1581 cx_testing_allocator_destroy(&talloc);
1582 }
1583
1584 CX_TEST(test_tree_add_many) {
1585 // adds many elements to an existing tree
1586
1587 CxTestingAllocator talloc;
1588 cx_testing_allocator_init(&talloc);
1589 CxAllocator *alloc = &talloc.base;
1590
1591 tree_node_file root = {0};
1592 root.path = "/";
1593 tree_node_file usr = {0};
1594 usr.path = "/usr/";
1595 cx_tree_link(&root, &usr, tree_node_file_layout);
1596 tree_node_file home = {0};
1597 home.path = "/home/";
1598 cx_tree_link(&root, &home, tree_node_file_layout);
1599 tree_node_file lib = {0};
1600 lib.path = "/usr/lib/";
1601 cx_tree_link(&usr, &lib, tree_node_file_layout);
1602
1603 CX_TEST_DO {
1604 void *failed;
1605
1606 const char *paths[] = {
1607 "/home/foo/",
1608 "/home/foo/bar",
1609 "/usr/lib64/",
1610 "/usr/lib/foo.so"
1611 };
1612
1613 size_t processed = cx_tree_add_array(
1614 paths, 4, sizeof(const char *),
1615 tree_node_file_search,
1616 tree_node_file_create, alloc,
1617 &failed, &root, tree_node_file_layout
1618 );
1619
1620 CX_TEST_ASSERT(failed == NULL);
1621 CX_TEST_ASSERT(processed == 4);
1622 CX_TEST_ASSERT(talloc.alloc_total == 4);
1623
1624 CX_TEST_ASSERT(home.children == home.last_child);
1625 tree_node_file *foo = home.children;
1626 CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
1627 CX_TEST_ASSERT(foo->children == foo->last_child);
1628 tree_node_file *bar = foo->children;
1629 CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
1630 CX_TEST_ASSERT(usr.children != usr.last_child);
1631 tree_node_file *lib64 = usr.last_child;
1632 CX_TEST_ASSERT(lib64 != NULL);
1633 CX_TEST_ASSERT(lib64->path == paths[2]);
1634 CX_TEST_ASSERT(lib64->prev == &lib);
1635 CX_TEST_ASSERT(lib64->parent == &usr);
1636 CX_TEST_ASSERT(lib.children != NULL);
1637 tree_node_file *libfoo = lib.children;
1638 CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
1639
1640 cxFree(alloc, foo);
1641 cxFree(alloc, bar);
1642 cxFree(alloc, lib64);
1643 cxFree(alloc, libfoo);
1644
1645 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1646 }
1647 cx_testing_allocator_destroy(&talloc);
1648 }
1649
1650 CX_TEST(test_tree_add_many_but_not_all) {
1651 CxTestingAllocator talloc;
1652 cx_testing_allocator_init(&talloc);
1653 CxAllocator *alloc = &talloc.base;
1654
1655 tree_node_file root = {0};
1656 root.path = "/";
1657 tree_node_file usr = {0};
1658 usr.path = "/usr/";
1659 cx_tree_link(&root, &usr, tree_node_file_layout);
1660 tree_node_file home = {0};
1661 home.path = "/home/";
1662 cx_tree_link(&root, &home, tree_node_file_layout);
1663 tree_node_file lib = {0};
1664 lib.path = "/usr/lib/";
1665 cx_tree_link(&usr, &lib, tree_node_file_layout);
1666
1667 CX_TEST_DO {
1668 void *failed;
1669
1670 const char *paths[] = {
1671 "/home/foo/",
1672 "/home/foo/bar",
1673 "/usr/lib64/",
1674 "/usr/lib/foo.so"
1675 };
1676 // create iterator for 4 elements, but choose to insert only 3 of them
1677 CxIterator iter = cxIterator(paths, sizeof(const char*), 4);
1678 size_t processed = cx_tree_add_iter(
1679 cxIteratorRef(iter), 3,
1680 tree_node_file_search,
1681 tree_node_file_create, alloc,
1682 &failed, &root, tree_node_file_layout
1683 );
1684
1685 CX_TEST_ASSERT(cxIteratorValid(iter));
1686 CX_TEST_ASSERT(cxIteratorCurrent(iter) == &paths[3]);
1687
1688 CX_TEST_ASSERT(failed == NULL);
1689 CX_TEST_ASSERT(processed == 3);
1690 CX_TEST_ASSERT(talloc.alloc_total == 3);
1691
1692 CX_TEST_ASSERT(home.children == home.last_child);
1693 tree_node_file *foo = home.children;
1694 CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
1695 CX_TEST_ASSERT(foo->children == foo->last_child);
1696 tree_node_file *bar = foo->children;
1697 CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
1698 CX_TEST_ASSERT(usr.children != usr.last_child);
1699 tree_node_file *lib64 = usr.last_child;
1700 CX_TEST_ASSERT(lib64 != NULL);
1701 CX_TEST_ASSERT(lib64->path == paths[2]);
1702 CX_TEST_ASSERT(lib64->prev == &lib);
1703 CX_TEST_ASSERT(lib64->parent == &usr);
1704 CX_TEST_ASSERT(lib.children == NULL);
1705
1706 cxFree(alloc, foo);
1707 cxFree(alloc, bar);
1708 cxFree(alloc, lib64);
1709
1710 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1711 }
1712 cx_testing_allocator_destroy(&talloc);
1713 }
1714
1715 CX_TEST(test_tree_add_many_with_dupl_and_no_match) {
1716 CxTestingAllocator talloc;
1717 cx_testing_allocator_init(&talloc);
1718 CxAllocator *alloc = &talloc.base;
1719
1720 tree_node_file root = {0};
1721 root.path = "/mnt/";
1722
1723 CX_TEST_DO {
1724 tree_node_file *failed;
1725
1726 const char *paths[] = {
1727 "/mnt/sdcard/",
1728 "/mnt/foo/",
1729 "/mnt/sdcard/",
1730 "/home/",
1731 "/usr/"
1732 };
1733
1734 size_t processed = cx_tree_add_array(
1735 paths, 5, sizeof(const char *),
1736 tree_node_file_search,
1737 tree_node_file_create, alloc,
1738 (void **) &failed, &root, tree_node_file_layout
1739 );
1740
1741 CX_TEST_ASSERT(processed == 3);
1742 CX_TEST_ASSERT(failed != NULL);
1743 CX_TEST_ASSERT(failed->parent == NULL);
1744 CX_TEST_ASSERT(failed->children == NULL);
1745 CX_TEST_ASSERT(strcmp(failed->path, "/home/") == 0);
1746 cxFree(alloc, failed);
1747
1748 CX_TEST_ASSERT(root.children != root.last_child);
1749 CX_TEST_ASSERT(strcmp(root.children->path, "/mnt/sdcard/") == 0);
1750 CX_TEST_ASSERT(strcmp(root.last_child->path, "/mnt/sdcard/") == 0);
1751 CX_TEST_ASSERT(strcmp(root.children->next->path, "/mnt/foo/") == 0);
1752 CX_TEST_ASSERT(strcmp(root.last_child->prev->path, "/mnt/foo/") == 0);
1753
1754 CxTreeIterator iter = cx_tree_iterator(
1755 &root, true,
1756 offsetof(tree_node_file, children),
1757 offsetof(tree_node_file, next)
1758 );
1759 cx_foreach(tree_node_file *, node, iter) {
1760 if (iter.exiting) {
1761 if (node != &root) {
1762 cxFree(alloc, node);
1763 }
1764 }
1765 }
1766
1767 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1768 }
1769 cx_testing_allocator_destroy(&talloc);
1770 }
1771
1772 static CX_TEST_SUBROUTINE(test_tree_add_create_from_array_impl,
1773 CxAllocator *alloc, const char **paths) {
1774 tree_node_file root = {0};
1775 root.path = "/";
1776
1777 void *failed;
1778 size_t processed = cx_tree_add_array(
1779 paths, 10, sizeof(const char *),
1780 tree_node_file_search,
1781 tree_node_file_create, alloc,
1782 &failed, &root, tree_node_file_layout
1783 );
1784
1785 CX_TEST_ASSERT(failed == NULL);
1786 CX_TEST_ASSERT(processed == 10);
1787
1788 const char *exp_order[] = {
1789 "/",
1790 "/usr/",
1791 "/usr/lib/",
1792 "/usr/lib/libbumm.so",
1793 "/home/",
1794 "/home/foo/",
1795 "/var/",
1796 "/var/www/",
1797 "/var/www/vhosts/",
1798 "/var/www/vhosts/live/",
1799 "/var/www/vhosts/live/htdocs/"
1800 };
1801 unsigned exp_depth[] = {
1802 1,
1803 2,
1804 3,
1805 4,
1806 2,
1807 3,
1808 2,
1809 3,
1810 4,
1811 5,
1812 6
1813 };
1814
1815 CxTreeIterator iter = cx_tree_iterator(
1816 &root, true,
1817 offsetof(tree_node_file, children),
1818 offsetof(tree_node_file, next)
1819 );
1820 cx_foreach(tree_node_file *, node, iter) {
1821 if (iter.exiting) {
1822 if (node != &root) {
1823 cxFree(alloc, node);
1824 }
1825 } else {
1826 CX_TEST_ASSERT(iter.counter <= 11);
1827 CX_TEST_ASSERT(iter.depth == exp_depth[iter.counter - 1]);
1828 CX_TEST_ASSERT(strcmp(node->path, exp_order[iter.counter - 1]) == 0);
1829 }
1830 }
1831 }
1832
1833 CX_TEST(test_tree_add_create_from_array) {
1834 // creates an entirely new tree from an array
1835
1836 CxTestingAllocator talloc;
1837 cx_testing_allocator_init(&talloc);
1838 CxAllocator *alloc = &talloc.base;
1839
1840 CX_TEST_DO {
1841 const char *paths[] = {
1842 "/usr/",
1843 "/home/",
1844 "/usr/lib/",
1845 "/usr/lib/libbumm.so",
1846 "/var/",
1847 "/var/www/",
1848 "/var/www/vhosts/",
1849 "/var/www/vhosts/live/",
1850 "/var/www/vhosts/live/htdocs/",
1851 "/home/foo/"
1852 };
1853
1854 const char *scrambled_paths[] = {
1855 "/usr/",
1856 "/home/",
1857 "/var/www/vhosts/live/",
1858 "/usr/lib/",
1859 "/var/",
1860 "/var/www/",
1861 "/usr/lib/libbumm.so",
1862 "/var/www/vhosts/",
1863 "/var/www/vhosts/live/htdocs/",
1864 "/home/foo/"
1865 };
1866
1867 // no matter how the original array is sorted,
1868 // the resulting tree should be the same
1869 CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
1870 paths);
1871 CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
1872 scrambled_paths);
1873
1874 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1875 }
1876 cx_testing_allocator_destroy(&talloc);
1877 }
1878
1879 CX_TEST(test_tree_high_create) { 1339 CX_TEST(test_tree_high_create) {
1880 CxTestingAllocator talloc; 1340 CxTestingAllocator talloc;
1881 cx_testing_allocator_init(&talloc); 1341 cx_testing_allocator_init(&talloc);
1882 CX_TEST_DO { 1342 CX_TEST_DO {
1883 CxTree *tree = cxTreeCreate( 1343 CxTree *tree = cxTreeCreate(
1884 &talloc.base, 1344 &talloc.base,
1885 tree_node_file_create_hl, 1345 sizeof(tree_node_file),
1886 tree_node_file_search, 1346 CX_STORE_POINTERS,
1887 tree_node_file_search_data, 1347 NULL, offsetof(tree_node_file, path),
1888 tree_node_file_layout 1348 cx_tree_node_layout(tree_node_file)
1889 ); 1349 );
1890 CX_TEST_ASSERT(tree->cl != NULL);
1891 CX_TEST_ASSERT(tree->collection.allocator == &talloc.base); 1350 CX_TEST_ASSERT(tree->collection.allocator == &talloc.base);
1892 CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); 1351 CX_TEST_ASSERT(tree->node_size == sizeof(tree_node_file));
1893 CX_TEST_ASSERT(tree->search == tree_node_file_search); 1352 CX_TEST_ASSERT(tree->collection.elem_size == sizeof(void*));
1894 CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data);
1895 CX_TEST_ASSERT(tree->collection.size == 0); 1353 CX_TEST_ASSERT(tree->collection.size == 0);
1896 CX_TEST_ASSERT(tree->collection.simple_destructor == NULL); 1354 CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
1897 CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree); 1355 CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree);
1898 CX_TEST_ASSERT(tree->collection.destructor_data == &talloc.base); 1356 CX_TEST_ASSERT(tree->collection.destructor_data == &talloc.base);
1899 CX_TEST_ASSERT(tree->collection.store_pointer == false); 1357 CX_TEST_ASSERT(tree->collection.store_pointer == true);
1900 CX_TEST_ASSERT(tree->collection.sorted == false); 1358 CX_TEST_ASSERT(tree->collection.sorted == false);
1901 CX_TEST_ASSERT(tree->root == NULL); 1359 CX_TEST_ASSERT(tree->root == NULL);
1902 CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node_file, parent)); 1360 CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node_file, parent));
1903 CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node_file, children)); 1361 CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node_file, children));
1904 CX_TEST_ASSERT(tree->loc_last_child == offsetof(tree_node_file, last_child)); 1362 CX_TEST_ASSERT(tree->loc_last_child == offsetof(tree_node_file, last_child));
1905 CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node_file, prev)); 1363 CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node_file, prev));
1906 CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node_file, next)); 1364 CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node_file, next));
1365 CX_TEST_ASSERT(tree->loc_data == offsetof(tree_node_file, path));
1907 1366
1908 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1367 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
1909 CX_TEST_ASSERT(talloc.alloc_total == 1); 1368 CX_TEST_ASSERT(talloc.alloc_total == 1);
1910 1369
1911 cxTreeFree(tree); 1370 cxTreeFree(tree);
1912 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1371 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1913 } 1372 }
1914 cx_testing_allocator_destroy(&talloc); 1373 cx_testing_allocator_destroy(&talloc);
1915 } 1374 }
1916 1375
1917 CX_TEST(test_tree_high_create_simple) {
1918 CX_TEST_DO {
1919 CxTree *tree = cxTreeCreateSimple(
1920 NULL, // shall fall back to the default allocator
1921 tree_node_file_create_hl,
1922 tree_node_file_search,
1923 tree_node_file_search_data
1924 );
1925 CX_TEST_ASSERT(tree->cl != NULL);
1926 CX_TEST_ASSERT(tree->collection.allocator == cxDefaultAllocator);
1927 CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
1928 CX_TEST_ASSERT(tree->search == tree_node_file_search);
1929 CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data);
1930 CX_TEST_ASSERT(tree->collection.size == 0);
1931 CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
1932 CX_TEST_ASSERT(tree->collection.advanced_destructor == (cx_destructor_func2) cxFree);
1933 CX_TEST_ASSERT(tree->collection.destructor_data == cxDefaultAllocator);
1934 CX_TEST_ASSERT(tree->root == NULL);
1935 CX_TEST_ASSERT(tree->loc_parent == offsetof(struct cx_tree_node_base_s, parent));
1936 CX_TEST_ASSERT(tree->loc_children == offsetof(struct cx_tree_node_base_s, children));
1937 CX_TEST_ASSERT(tree->loc_last_child == offsetof(struct cx_tree_node_base_s, last_child));
1938 CX_TEST_ASSERT(tree->loc_prev == offsetof(struct cx_tree_node_base_s, prev));
1939 CX_TEST_ASSERT(tree->loc_next == offsetof(struct cx_tree_node_base_s, next));
1940 cxTreeFree(tree);
1941 }
1942 }
1943
1944 CX_TEST(test_tree_high_create_wrapped) {
1945 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
1946 cx_tree_link(&root, &child1, tree_node_layout);
1947 cx_tree_link(&root, &child2, tree_node_layout);
1948 cx_tree_link(&child1, &child3, tree_node_layout);
1949 CX_TEST_DO {
1950 CxTree *tree = cxTreeCreateWrapped(NULL, &root, tree_node_layout);
1951 CX_TEST_ASSERT(tree->cl != NULL);
1952 CX_TEST_ASSERT(tree->collection.allocator == cxDefaultAllocator);
1953 CX_TEST_ASSERT(tree->node_create == NULL);
1954 CX_TEST_ASSERT(tree->search == NULL);
1955 CX_TEST_ASSERT(tree->search_data == NULL);
1956 CX_TEST_ASSERT(tree->root == &root);
1957 CX_TEST_ASSERT(tree->collection.size == 4);
1958 CX_TEST_ASSERT(tree->collection.simple_destructor == NULL);
1959 CX_TEST_ASSERT(tree->collection.advanced_destructor == NULL);
1960 CX_TEST_ASSERT(tree->collection.destructor_data == NULL);
1961 CX_TEST_ASSERT(tree->loc_parent == offsetof(tree_node, parent));
1962 CX_TEST_ASSERT(tree->loc_children == offsetof(tree_node, children));
1963 CX_TEST_ASSERT(tree->loc_last_child == -1);
1964 CX_TEST_ASSERT(tree->loc_prev == offsetof(tree_node, prev));
1965 CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next));
1966 cxTreeFree(tree);
1967 }
1968 }
1969
1970 CX_TEST(test_tree_high_tree_depth) { 1376 CX_TEST(test_tree_high_tree_depth) {
1971 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1377 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
1972 cx_tree_link(&root, &child1, tree_node_layout); 1378 cx_tree_add(&root, &child1, tree_node_layout);
1973 cx_tree_link(&root, &child2, tree_node_layout); 1379 cx_tree_add(&root, &child2, tree_node_layout);
1974 cx_tree_link(&child1, &child3, tree_node_layout); 1380 cx_tree_add(&child1, &child3, tree_node_layout);
1975 CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); 1381 CxTree *tree = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
1382 sizeof(int), &root, offsetof(tree_node, data), tree_node_layout);
1976 CX_TEST_DO { 1383 CX_TEST_DO {
1977 CX_TEST_ASSERT(cxTreeDepth(tree) == 3); 1384 CX_TEST_ASSERT(cxTreeDepth(tree) == 3);
1978 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); 1385 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3);
1979 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2); 1386 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2);
1980 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1); 1387 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1);
1981 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); 1388 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1);
1982 1389
1983 CxTree *empty = cxTreeCreate( 1390 CxTree *empty = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
1984 cxDefaultAllocator, 1391 sizeof(int), NULL, offsetof(tree_node, data), tree_node_layout);
1985 tree_node_file_create_hl,
1986 tree_node_file_search,
1987 tree_node_file_search_data,
1988 tree_node_file_layout
1989 );
1990 CX_TEST_ASSERT(cxTreeDepth(empty) == 0); 1392 CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
1991 cxTreeFree(empty); 1393 cxTreeFree(empty);
1992 } 1394 }
1993 cxTreeFree(tree); 1395 cxTreeFree(tree);
1994 } 1396 }
1995 1397
1996 CX_TEST(test_tree_high_set_parent) { 1398 CX_TEST(test_tree_high_set_parent) {
1997 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1399 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
1998 CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); 1400 CxTree *tree = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
1401 sizeof(int), &root, offsetof(tree_node, data), tree_node_layout);
1999 CX_TEST_DO { 1402 CX_TEST_DO {
2000 cxTreeSetParent(tree, &root, &child1); 1403 cxTreeSetParent(tree, &root, &child1);
2001 cxTreeSetParent(tree, &root, &child2); 1404 cxTreeSetParent(tree, &root, &child2);
2002 cxTreeSetParent(tree, &child1, &child3); 1405 cxTreeSetParent(tree, &child1, &child3);
2003 CX_TEST_ASSERT(cxTreeDepth(tree) == 3); 1406 CX_TEST_ASSERT(cxTreeDepth(tree) == 3);
2010 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); 1413 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3);
2011 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 1); 1414 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 1);
2012 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 2); 1415 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 2);
2013 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); 1416 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1);
2014 1417
2015 CxTree *empty = cxTreeCreate( 1418 CxTree *empty = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
2016 cxDefaultAllocator, 1419 sizeof(int), NULL, offsetof(tree_node, data), tree_node_layout);
2017 tree_node_file_create_hl,
2018 tree_node_file_search,
2019 tree_node_file_search_data,
2020 tree_node_file_layout
2021 );
2022 CX_TEST_ASSERT(cxTreeDepth(empty) == 0); 1420 CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
2023 cxTreeFree(empty); 1421 cxTreeFree(empty);
2024 } 1422 }
2025 cxTreeFree(tree); 1423 cxTreeFree(tree);
2026 }
2027
2028 CX_TEST(test_tree_high_insert_one) {
2029 CxTestingAllocator talloc;
2030 cx_testing_allocator_init(&talloc);
2031 CxAllocator *alloc = &talloc.base;
2032
2033 CX_TEST_DO {
2034 CxTree *tree = cxTreeCreate(
2035 alloc, tree_node_file_create_hl,
2036 tree_node_file_search, tree_node_file_search_data,
2037 tree_node_file_layout
2038 );
2039
2040 int result = 0;
2041 result |= cxTreeInsert(tree, "/");
2042 result |= cxTreeInsert(tree, "/usr/");
2043 result |= cxTreeInsert(tree, "/home/");
2044 result |= cxTreeInsert(tree, "/usr/lib/");
2045 result |= cxTreeInsert(tree, "/home/foo/");
2046 CX_TEST_ASSERT(result == 0);
2047 CX_TEST_ASSERT(1 == cxTreeInsertArray(tree, "/home/foo/bar/", sizeof(const char*), 1));
2048 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
2049 CX_TEST_ASSERT(0 != cxTreeInsert(tree, "newroot"));
2050 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
2051
2052 CX_TEST_ASSERT(talloc.alloc_total == 8);
2053 CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
2054
2055 cxTreeFree(tree);
2056 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
2057 }
2058 cx_testing_allocator_destroy(&talloc);
2059 }
2060
2061 CX_TEST(test_tree_high_insert_many) {
2062 CxTestingAllocator talloc;
2063 cx_testing_allocator_init(&talloc);
2064 CxAllocator *alloc = &talloc.base;
2065
2066 CX_TEST_DO {
2067 CxTree *tree = cxTreeCreate(
2068 alloc, tree_node_file_create_hl,
2069 tree_node_file_search, tree_node_file_search_data,
2070 tree_node_file_layout
2071 );
2072
2073 const char *paths[] = {
2074 "/",
2075 "/usr/",
2076 "/home/",
2077 "/usr/lib/",
2078 "/home/foo/",
2079 "/home/foo/bar/",
2080 "newroot"
2081 };
2082 CX_TEST_ASSERT(6 == cxTreeInsertArray(tree, paths, sizeof(const char*), 7));
2083 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
2084
2085 CX_TEST_ASSERT(talloc.alloc_total == 8);
2086 CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
2087
2088 cxTreeFree(tree);
2089 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
2090 }
2091 cx_testing_allocator_destroy(&talloc);
2092 } 1424 }
2093 1425
2094 static void test_tree_remove_node_relink_mock( 1426 static void test_tree_remove_node_relink_mock(
2095 void *node, 1427 void *node,
2096 CX_UNUSED const void *oldp, 1428 CX_UNUSED const void *oldp,
2103 } else if (strcmp(n->path, "/usr/lib/") == 0) { 1435 } else if (strcmp(n->path, "/usr/lib/") == 0) {
2104 n->path = "/lib/"; 1436 n->path = "/lib/";
2105 } 1437 }
2106 } 1438 }
2107 1439
1440 static CX_TEST_SUBROUTINE(validate_tree_high_add_find_remove_nodes,
1441 CxAllocator *alloc, bool use_dfs) {
1442 CxTree *tree = cxTreeCreate(alloc,
1443 sizeof(tree_node_file),
1444 CX_STORE_POINTERS,
1445 NULL, offsetof(tree_node_file, path),
1446 cx_tree_node_layout(tree_node_file)
1447 );
1448 cxSetCompareFunc(tree, strcmp);
1449
1450 {
1451 tree_node_file *root = cxTreeCreateRootData(tree, "/");
1452 tree_node_file *home = cxTreeAddData(tree, root, "/home/");
1453 tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
1454 cxTreeAddData(tree, foo, "/home/foo/bar/");
1455 tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
1456 cxTreeAddData(tree, usr, "/usr/lib/");
1457 }
1458
1459 tree_node_file *foo = cxTreeFind(tree, "/home/foo/", use_dfs);
1460 CX_TEST_ASSERT(NULL != foo);
1461 CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path));
1462 CX_TEST_ASSERT(NULL != foo->parent);
1463 CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path));
1464 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
1465
1466 CX_TEST_ASSERT(NULL != cxTreeAddData(tree, foo->parent, "/home/baz/"));
1467 tree_node_file *baz = cxTreeFind(tree, "/home/baz/", use_dfs);
1468 CX_TEST_ASSERT(NULL != baz);
1469 CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path));
1470 CX_TEST_ASSERT(NULL != baz->parent);
1471 CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path));
1472 CX_TEST_ASSERT(cxTreeSize(tree) == 7);
1473
1474 tree_node_file *home = cxTreeFind(tree, "/home/", use_dfs);
1475 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0, use_dfs));
1476 tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0, use_dfs);
1477 CX_TEST_ASSERT(NULL != bar);
1478 CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path));
1479 CX_TEST_ASSERT(bar->parent == foo);
1480
1481 tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
1482 share->path = "/usr/share/";
1483 tree_node_file *usr = cxTreeFind(tree, "/usr/", use_dfs);
1484 cxTreeAddNode(tree, usr, share);
1485 CX_TEST_ASSERT(cxTreeSize(tree) == 8);
1486
1487 cxTreeRemoveSubtree(tree, foo);
1488 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
1489 CX_TEST_ASSERT(foo->children == bar);
1490 CX_TEST_ASSERT(foo->last_child == bar);
1491 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/", use_dfs));
1492 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/", use_dfs));
1493 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/", use_dfs));
1494
1495 CX_TEST_ASSERT(0 == cxTreeRemoveNode(tree, usr, test_tree_remove_node_relink_mock));
1496 CX_TEST_ASSERT(cxTreeSize(tree) == 5);
1497 CX_TEST_ASSERT(usr->parent == NULL);
1498 CX_TEST_ASSERT(usr->children == NULL);
1499 CX_TEST_ASSERT(usr->last_child == NULL);
1500 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/", use_dfs));
1501 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/", use_dfs));
1502 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/", use_dfs));
1503 tree_node_file *relinked_share = cxTreeFind(tree, "/share/", use_dfs);
1504 tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/", use_dfs);
1505 CX_TEST_ASSERT(relinked_share != NULL);
1506 CX_TEST_ASSERT(relinked_share->parent == tree->root);
1507 CX_TEST_ASSERT(relinked_lib != NULL);
1508 CX_TEST_ASSERT(relinked_lib->parent == tree->root);
1509 CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/", use_dfs));
1510 cxTreeFree(tree);
1511
1512 // we are not done yet, because we need to free the removed stuff
1513 cxFree(alloc, usr);
1514 // for the subtree, we use a little trick and wrap it in a new tree
1515 CxTree *foo_tree = cxTreeCreate(alloc,
1516 sizeof(tree_node_file),
1517 CX_STORE_POINTERS,
1518 foo, offsetof(tree_node_file, path),
1519 cx_tree_node_layout(tree_node_file)
1520 );
1521 cxSetAdvancedDestructor(foo_tree, cxFree, alloc);
1522 cxTreeFree(foo_tree);
1523 }
1524
2108 CX_TEST(test_tree_high_add_find_remove_nodes) { 1525 CX_TEST(test_tree_high_add_find_remove_nodes) {
2109 CxTestingAllocator talloc; 1526 CxTestingAllocator talloc;
2110 cx_testing_allocator_init(&talloc); 1527 cx_testing_allocator_init(&talloc);
2111 CxAllocator *alloc = &talloc.base; 1528 CxAllocator *alloc = &talloc.base;
2112 1529
2113 CX_TEST_DO { 1530 CX_TEST_DO {
2114 CxTree *tree = cxTreeCreate( 1531 CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_remove_nodes, alloc, true);
2115 alloc, tree_node_file_create_hl,
2116 tree_node_file_search, tree_node_file_search_data,
2117 tree_node_file_layout
2118 );
2119
2120 const char *paths[] = {
2121 "/",
2122 "/usr/",
2123 "/home/",
2124 "/usr/lib/",
2125 "/home/foo/",
2126 "/home/foo/bar/"
2127 };
2128 cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
2129
2130 tree_node_file *foo = cxTreeFind(tree, "/home/foo/");
2131 CX_TEST_ASSERT(NULL != foo);
2132 CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path));
2133 CX_TEST_ASSERT(NULL != foo->parent);
2134 CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path));
2135 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
2136
2137 CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/"));
2138 tree_node_file *baz = cxTreeFind(tree, "/home/baz/");
2139 CX_TEST_ASSERT(NULL != baz);
2140 CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path));
2141 CX_TEST_ASSERT(NULL != baz->parent);
2142 CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path));
2143 CX_TEST_ASSERT(cxTreeSize(tree) == 7);
2144
2145 tree_node_file *home = cxTreeFind(tree, "/home/");
2146 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0));
2147 tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0);
2148 CX_TEST_ASSERT(NULL != bar);
2149 CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path));
2150 CX_TEST_ASSERT(bar->parent == foo);
2151
2152 tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
2153 share->path = "/usr/share/";
2154 tree_node_file *usr = cxTreeFind(tree, "/usr/");
2155 cxTreeAddChildNode(tree, usr, share);
2156 CX_TEST_ASSERT(cxTreeSize(tree) == 8);
2157
2158 cxTreeRemoveSubtree(tree, foo);
2159 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
2160 CX_TEST_ASSERT(foo->children == bar);
2161 CX_TEST_ASSERT(foo->last_child == bar);
2162 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/"));
2163 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/"));
2164 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/"));
2165
2166 CX_TEST_ASSERT(0 == cxTreeRemoveNode(tree, usr, test_tree_remove_node_relink_mock));
2167 CX_TEST_ASSERT(cxTreeSize(tree) == 5);
2168 CX_TEST_ASSERT(usr->parent == NULL);
2169 CX_TEST_ASSERT(usr->children == NULL);
2170 CX_TEST_ASSERT(usr->last_child == NULL);
2171 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/"));
2172 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/"));
2173 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/"));
2174 tree_node_file *relinked_share = cxTreeFind(tree, "/share/");
2175 tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/");
2176 CX_TEST_ASSERT(relinked_share != NULL);
2177 CX_TEST_ASSERT(relinked_share->parent == tree->root);
2178 CX_TEST_ASSERT(relinked_lib != NULL);
2179 CX_TEST_ASSERT(relinked_lib->parent == tree->root);
2180 CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/"));
2181
2182
2183 cxTreeFree(tree);
2184 // we are not done yet, because we need to free the removed stuff
2185 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
2186
2187 cxFree(alloc, usr);
2188 // for the subtree, we use a little trick and wrap it in a new tree
2189 CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout);
2190 foo_tree->collection.allocator = alloc;
2191 cxSetAdvancedDestructor(foo_tree, cxFree, alloc);
2192 cxTreeFree(foo_tree);
2193 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1532 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1533 CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_remove_nodes, alloc, false);
1534 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
2194 } 1535 }
2195 cx_testing_allocator_destroy(&talloc); 1536 cx_testing_allocator_destroy(&talloc);
1537 }
1538
1539 static CX_TEST_SUBROUTINE(validate_tree_high_add_find_destroy_nodes,
1540 CxAllocator *alloc, bool use_dfs) {
1541 CxTree *tree = cxTreeCreate(alloc,
1542 sizeof(tree_node_file),
1543 CX_STORE_POINTERS,
1544 NULL, offsetof(tree_node_file, path),
1545 cx_tree_node_layout(tree_node_file)
1546 );
1547 cxSetCompareFunc(tree, strcmp);
1548
1549 {
1550 tree_node_file *root = cxTreeCreateRootData(tree, "/");
1551 tree_node_file *home = cxTreeAddData(tree, root, "/home/");
1552 tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
1553 cxTreeAddData(tree, foo, "/home/foo/bar/");
1554 tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
1555 cxTreeAddData(tree, usr, "/usr/lib/");
1556 }
1557
1558 tree_node_file *foo = cxTreeFind(tree, "/home/foo/", use_dfs);
1559 CX_TEST_ASSERT(NULL != foo);
1560 CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path));
1561 CX_TEST_ASSERT(NULL != foo->parent);
1562 CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path));
1563 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
1564
1565 CX_TEST_ASSERT(NULL != cxTreeAddData(tree, foo->parent, "/home/baz/"));
1566 tree_node_file *baz = cxTreeFind(tree, "/home/baz/", use_dfs);
1567 CX_TEST_ASSERT(NULL != baz);
1568 CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path));
1569 CX_TEST_ASSERT(NULL != baz->parent);
1570 CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path));
1571 CX_TEST_ASSERT(cxTreeSize(tree) == 7);
1572
1573 tree_node_file *home = cxTreeFind(tree, "/home/", use_dfs);
1574 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0, use_dfs));
1575 tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0, use_dfs);
1576 CX_TEST_ASSERT(NULL != bar);
1577 CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path));
1578 CX_TEST_ASSERT(bar->parent == foo);
1579
1580 tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
1581 share->path = "/usr/share/";
1582 tree_node_file *usr = cxTreeFind(tree, "/usr/", use_dfs);
1583 cxTreeAddNode(tree, usr, share);
1584 CX_TEST_ASSERT(cxTreeSize(tree) == 8);
1585
1586 cxTreeDestroySubtree(tree, foo);
1587 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
1588 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/", use_dfs));
1589 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/", use_dfs));
1590 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/", use_dfs));
1591
1592 CX_TEST_ASSERT(0 == cxTreeDestroyNode(tree, usr, test_tree_remove_node_relink_mock));
1593 CX_TEST_ASSERT(cxTreeSize(tree) == 5);
1594 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/", use_dfs));
1595 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/", use_dfs));
1596 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/", use_dfs));
1597 tree_node_file *relinked_share = cxTreeFind(tree, "/share/", use_dfs);
1598 tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/", use_dfs);
1599 CX_TEST_ASSERT(relinked_share != NULL);
1600 CX_TEST_ASSERT(relinked_share->parent == tree->root);
1601 CX_TEST_ASSERT(relinked_lib != NULL);
1602 CX_TEST_ASSERT(relinked_lib->parent == tree->root);
1603 CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/", use_dfs));
1604
1605 cxTreeFree(tree);
2196 } 1606 }
2197 1607
2198 CX_TEST(test_tree_high_add_find_destroy_nodes) { 1608 CX_TEST(test_tree_high_add_find_destroy_nodes) {
2199 CxTestingAllocator talloc; 1609 CxTestingAllocator talloc;
2200 cx_testing_allocator_init(&talloc); 1610 cx_testing_allocator_init(&talloc);
2201 CxAllocator *alloc = &talloc.base; 1611 CxAllocator *alloc = &talloc.base;
2202 1612
2203 CX_TEST_DO { 1613 CX_TEST_DO {
2204 CxTree *tree = cxTreeCreate( 1614 CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, true);
2205 alloc, tree_node_file_create_hl, 1615 CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, false);
2206 tree_node_file_search, tree_node_file_search_data,
2207 tree_node_file_layout
2208 );
2209
2210 const char *paths[] = {
2211 "/",
2212 "/usr/",
2213 "/home/",
2214 "/usr/lib/",
2215 "/home/foo/",
2216 "/home/foo/bar/"
2217 };
2218 cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
2219
2220 tree_node_file *foo = cxTreeFind(tree, "/home/foo/");
2221 CX_TEST_ASSERT(NULL != foo);
2222 CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path));
2223 CX_TEST_ASSERT(NULL != foo->parent);
2224 CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path));
2225 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
2226
2227 CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/"));
2228 tree_node_file *baz = cxTreeFind(tree, "/home/baz/");
2229 CX_TEST_ASSERT(NULL != baz);
2230 CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path));
2231 CX_TEST_ASSERT(NULL != baz->parent);
2232 CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path));
2233 CX_TEST_ASSERT(cxTreeSize(tree) == 7);
2234
2235 tree_node_file *home = cxTreeFind(tree, "/home/");
2236 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo, 0));
2237 tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 0);
2238 CX_TEST_ASSERT(NULL != bar);
2239 CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path));
2240 CX_TEST_ASSERT(bar->parent == foo);
2241
2242 tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
2243 share->path = "/usr/share/";
2244 tree_node_file *usr = cxTreeFind(tree, "/usr/");
2245 cxTreeAddChildNode(tree, usr, share);
2246 CX_TEST_ASSERT(cxTreeSize(tree) == 8);
2247
2248 cxTreeDestroySubtree(tree, foo);
2249 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
2250 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/"));
2251 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/"));
2252 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/"));
2253
2254 CX_TEST_ASSERT(0 == cxTreeDestroyNode(tree, usr, test_tree_remove_node_relink_mock));
2255 CX_TEST_ASSERT(cxTreeSize(tree) == 5);
2256 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/"));
2257 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/lib/"));
2258 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/usr/share/"));
2259 tree_node_file *relinked_share = cxTreeFind(tree, "/share/");
2260 tree_node_file *relinked_lib = cxTreeFind(tree, "/lib/");
2261 CX_TEST_ASSERT(relinked_share != NULL);
2262 CX_TEST_ASSERT(relinked_share->parent == tree->root);
2263 CX_TEST_ASSERT(relinked_lib != NULL);
2264 CX_TEST_ASSERT(relinked_lib->parent == tree->root);
2265 CX_TEST_ASSERT(NULL != cxTreeFind(tree, "/home/"));
2266
2267 cxTreeFree(tree);
2268 // all memory should be free when using destroy instead of remove
2269 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1616 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
2270 } 1617 }
2271 cx_testing_allocator_destroy(&talloc); 1618 cx_testing_allocator_destroy(&talloc);
2272 } 1619 }
2273 1620
2275 CxTestingAllocator talloc; 1622 CxTestingAllocator talloc;
2276 cx_testing_allocator_init(&talloc); 1623 cx_testing_allocator_init(&talloc);
2277 CxAllocator *alloc = &talloc.base; 1624 CxAllocator *alloc = &talloc.base;
2278 1625
2279 CX_TEST_DO { 1626 CX_TEST_DO {
2280 CxTree *tree = cxTreeCreate( 1627 CxTree *tree = cxTreeCreate(alloc,
2281 alloc, tree_node_file_create_hl, 1628 sizeof(tree_node_file),
2282 tree_node_file_search, tree_node_file_search_data, 1629 CX_STORE_POINTERS,
2283 tree_node_file_layout 1630 NULL, offsetof(tree_node_file, path),
1631 cx_tree_node_layout(tree_node_file)
2284 ); 1632 );
2285 1633
2286 const char *paths[] = { 1634 {
2287 "/", 1635 tree_node_file *root = cxTreeCreateRootData(tree, "/");
2288 "/usr/", 1636 tree_node_file *home = cxTreeAddData(tree, root, "/home/");
2289 "/home/", 1637 tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
2290 "/usr/lib/", 1638 cxTreeAddData(tree, foo, "/home/foo/bar/");
2291 "/home/foo/", 1639 tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
2292 "/home/foo/bar/" 1640 cxTreeAddData(tree, usr, "/usr/lib/");
2293 }; 1641 }
2294 cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
2295 void *root = tree->root; 1642 void *root = tree->root;
2296 CX_TEST_ASSERT(0 != cxTreeRemoveNode(tree, root, NULL)); 1643 CX_TEST_ASSERT(0 != cxTreeRemoveNode(tree, root, NULL));
2297 CX_TEST_ASSERT(tree->root == root); 1644 CX_TEST_ASSERT(tree->root == root);
2298 CX_TEST_ASSERT(cxTreeSize(tree) == 6); 1645 CX_TEST_ASSERT(cxTreeSize(tree) == 6);
2299 CX_TEST_ASSERT(0 != cxTreeDestroyNode(tree, root, NULL)); 1646 CX_TEST_ASSERT(0 != cxTreeDestroyNode(tree, root, NULL));
2303 CX_TEST_ASSERT(cxTreeSize(tree) == 0); 1650 CX_TEST_ASSERT(cxTreeSize(tree) == 0);
2304 CX_TEST_ASSERT(tree->root == NULL); 1651 CX_TEST_ASSERT(tree->root == NULL);
2305 CX_TEST_ASSERT(cxTreeDepth(tree) == 0); 1652 CX_TEST_ASSERT(cxTreeDepth(tree) == 0);
2306 cxTreeFree(tree); 1653 cxTreeFree(tree);
2307 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1654 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
2308 CxTree *w = cxTreeCreateWrapped(alloc, root, tree_node_file_layout); 1655
1656 CxTree *w = cxTreeCreate(alloc,
1657 sizeof(tree_node_file),
1658 CX_STORE_POINTERS,
1659 root, offsetof(tree_node_file, path),
1660 cx_tree_node_layout(tree_node_file)
1661 );
2309 cxSetAdvancedDestructor(w, cxFree, alloc); 1662 cxSetAdvancedDestructor(w, cxFree, alloc);
2310 cxTreeDestroySubtree(w, w->root); 1663 cxTreeDestroySubtree(w, w->root);
2311 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1664 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
2312 cxTreeFree(w); 1665 cxTreeFree(w);
2313 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1666 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
2319 ((tree_node *)node)->data++; 1672 ((tree_node *)node)->data++;
2320 } 1673 }
2321 1674
2322 CX_TEST(test_tree_high_simple_destructor) { 1675 CX_TEST(test_tree_high_simple_destructor) {
2323 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1676 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
2324 cx_tree_link(&root, &child1, tree_node_layout); 1677 cx_tree_add(&root, &child1, tree_node_layout);
2325 cx_tree_link(&root, &child2, tree_node_layout); 1678 cx_tree_add(&root, &child2, tree_node_layout);
2326 cx_tree_link(&child1, &child3, tree_node_layout); 1679 cx_tree_add(&child1, &child3, tree_node_layout);
2327 CX_TEST_DO { 1680 CX_TEST_DO {
2328 CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout); 1681 CxTree *tree = cxTreeCreate(cxDefaultAllocator, sizeof(tree_node),
1682 sizeof(int), &root, offsetof(tree_node, data), tree_node_layout);
2329 cxSetDestructor(tree,test_tree_high_simple_destructor_func); 1683 cxSetDestructor(tree,test_tree_high_simple_destructor_func);
2330 cxTreeDestroyNode(tree, &child1, NULL); 1684 cxTreeDestroyNode(tree, &child1, NULL);
2331 cxTreeFree(tree); 1685 cxTreeFree(tree);
2332 CX_TEST_ASSERT(root.data == 1); 1686 CX_TEST_ASSERT(root.data == 1);
2333 CX_TEST_ASSERT(child1.data == 1); 1687 CX_TEST_ASSERT(child1.data == 1);
2335 CX_TEST_ASSERT(child3.data == 1); 1689 CX_TEST_ASSERT(child3.data == 1);
2336 } 1690 }
2337 } 1691 }
2338 1692
2339 CX_TEST(test_tree_high_iterator) { 1693 CX_TEST(test_tree_high_iterator) {
2340 CxTree *tree = cxTreeCreate( 1694 CxTree *tree = cxTreeCreate(NULL,
2341 NULL, tree_node_file_create_hl, 1695 sizeof(tree_node_file),
2342 tree_node_file_search, tree_node_file_search_data, 1696 CX_STORE_POINTERS,
2343 tree_node_file_layout 1697 NULL, offsetof(tree_node_file, path),
1698 cx_tree_node_layout(tree_node_file)
2344 ); 1699 );
2345 cxTreeInsert(tree, "/"); 1700 {
2346 cxTreeInsert(tree, "/etc"); 1701 tree_node_file *root = cxTreeCreateRootData(tree, "/");
2347 cxTreeInsert(tree, "/home"); 1702 cxTreeAddData(tree, root, "/etc");
2348 cxTreeInsert(tree, "/home/jane"); 1703 tree_node_file *home = cxTreeAddData(tree, root, "/home");
2349 cxTreeInsert(tree, "/usr"); 1704 cxTreeAddData(tree, home, "/home/jane");
2350 cxTreeInsert(tree, "/usr/local"); 1705 tree_node_file *usr = cxTreeAddData(tree, root, "/usr");
2351 cxTreeInsert(tree, "/usr/local/lib"); 1706 cxTreeAddData(tree, usr, "/usr/local");
2352 cxTreeInsert(tree, "/var"); 1707 cxTreeAddData(tree, usr, "/usr/local/lib");
2353 cxTreeInsert(tree, "/var/lib"); 1708 tree_node_file *var = cxTreeAddData(tree, root, "/var");
1709 cxTreeAddData(tree, var, "/var/lib");
1710 }
2354 CX_TEST_DO { 1711 CX_TEST_DO {
2355 const char *expected_order[] = { 1712 const char *expected_order[] = {
2356 "/", 1713 "/",
2357 "/etc", 1714 "/etc",
2358 "/home", 1715 "/home",
2375 } 1732 }
2376 cxTreeFree(tree); 1733 cxTreeFree(tree);
2377 } 1734 }
2378 1735
2379 CX_TEST(test_tree_high_visitor) { 1736 CX_TEST(test_tree_high_visitor) {
2380 CxTree *tree = cxTreeCreate( 1737 CxTree *tree = cxTreeCreate(NULL,
2381 NULL, tree_node_file_create_hl, 1738 sizeof(tree_node_file),
2382 tree_node_file_search, tree_node_file_search_data, 1739 CX_STORE_POINTERS,
2383 tree_node_file_layout 1740 NULL, offsetof(tree_node_file, path),
1741 cx_tree_node_layout(tree_node_file)
2384 ); 1742 );
2385 cxTreeInsert(tree, "/"); 1743 {
2386 cxTreeInsert(tree, "/etc"); 1744 tree_node_file *root = cxTreeCreateRootData(tree, "/");
2387 cxTreeInsert(tree, "/home"); 1745 cxTreeAddData(tree, root, "/etc");
2388 cxTreeInsert(tree, "/home/jane"); 1746 tree_node_file *home = cxTreeAddData(tree, root, "/home");
2389 cxTreeInsert(tree, "/usr"); 1747 cxTreeAddData(tree, home, "/home/jane");
2390 cxTreeInsert(tree, "/usr/local"); 1748 tree_node_file *usr = cxTreeAddData(tree, root, "/usr");
2391 cxTreeInsert(tree, "/usr/local/lib"); 1749 tree_node_file *usr_local = cxTreeAddData(tree, usr, "/usr/local");
2392 cxTreeInsert(tree, "/var"); 1750 cxTreeAddData(tree, usr_local, "/usr/local/lib");
2393 cxTreeInsert(tree, "/var/lib"); 1751 tree_node_file *var = cxTreeAddData(tree, root, "/var");
1752 cxTreeAddData(tree, var, "/var/lib");
1753 }
2394 CX_TEST_DO { 1754 CX_TEST_DO {
2395 const char *expected_order[] = { 1755 const char *expected_order[] = {
2396 "/", 1756 "/",
2397 "/etc", 1757 "/etc",
2398 "/home", 1758 "/home",
2402 "/usr/local", 1762 "/usr/local",
2403 "/var/lib", 1763 "/var/lib",
2404 "/usr/local/lib", 1764 "/usr/local/lib",
2405 }; 1765 };
2406 const char *actual_order[9]; 1766 const char *actual_order[9];
2407 CxTreeVisitor iter = cxTreeVisit(tree); 1767 CxTreeIterator iter = cxTreeVisit(tree);
2408 cx_foreach(tree_node_file*, p, iter) { 1768 cx_foreach(tree_node_file*, p, iter) {
2409 actual_order[iter.counter-1] = p->path; 1769 actual_order[iter.counter-1] = p->path;
2410 } 1770 }
2411 CX_TEST_ASSERT(iter.counter == 9); 1771 CX_TEST_ASSERT(iter.counter == 9);
2412 for (unsigned i = 0; i < 9; i++) { 1772 for (unsigned i = 0; i < 9; i++) {
2417 } 1777 }
2418 1778
2419 CxTestSuite *cx_test_suite_tree_low_level(void) { 1779 CxTestSuite *cx_test_suite_tree_low_level(void) {
2420 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); 1780 CxTestSuite *suite = cx_test_suite_new("tree (low level)");
2421 1781
2422 cx_test_register(suite, test_tree_link_new_child); 1782 cx_test_register(suite, test_tree_add);
2423 cx_test_register(suite, test_tree_link_add_child); 1783 cx_test_register(suite, test_tree_add_move_to_other_parent);
2424 cx_test_register(suite, test_tree_link_move_to_other_parent); 1784 cx_test_register(suite, test_tree_remove);
2425 cx_test_register(suite, test_tree_unlink); 1785 cx_test_register(suite, test_tree_remove_no_prev);
2426 cx_test_register(suite, test_tree_unlink_no_prev);
2427 cx_test_register(suite, test_tree2_link_new_child); 1786 cx_test_register(suite, test_tree2_link_new_child);
2428 cx_test_register(suite, test_tree2_link_add_child); 1787 cx_test_register(suite, test_tree2_link_add_child);
2429 cx_test_register(suite, test_tree2_link_move_to_other_parent); 1788 cx_test_register(suite, test_tree2_link_move_to_other_parent);
2430 cx_test_register(suite, test_tree2_unlink); 1789 cx_test_register(suite, test_tree2_unlink);
2431 cx_test_register(suite, test_tree_search); 1790 cx_test_register(suite, test_tree_search);
2443 cx_test_register(suite, test_tree_visitor_no_branching); 1802 cx_test_register(suite, test_tree_visitor_no_branching);
2444 cx_test_register(suite, test_tree_visitor_subtree); 1803 cx_test_register(suite, test_tree_visitor_subtree);
2445 cx_test_register(suite, test_tree_visitor_continue); 1804 cx_test_register(suite, test_tree_visitor_continue);
2446 cx_test_register(suite, test_tree_iterator_continue); 1805 cx_test_register(suite, test_tree_iterator_continue);
2447 cx_test_register(suite, test_tree_iterator_continue_with_exit); 1806 cx_test_register(suite, test_tree_iterator_continue_with_exit);
2448 cx_test_register(suite, test_tree_add_one);
2449 cx_test_register(suite, test_tree_add_one_existing);
2450 cx_test_register(suite, test_tree_add_one_no_match);
2451 cx_test_register(suite, test_tree_add_duplicate_root);
2452 cx_test_register(suite, test_tree_add_zero);
2453 cx_test_register(suite, test_tree_add_many);
2454 cx_test_register(suite, test_tree_add_many_but_not_all);
2455 cx_test_register(suite, test_tree_add_many_with_dupl_and_no_match);
2456 cx_test_register(suite, test_tree_add_create_from_array);
2457 1807
2458 return suite; 1808 return suite;
2459 } 1809 }
2460 1810
2461 CxTestSuite *cx_test_suite_tree_high_level(void) { 1811 CxTestSuite *cx_test_suite_tree_high_level(void) {
2462 CxTestSuite *suite = cx_test_suite_new("tree (high level)"); 1812 CxTestSuite *suite = cx_test_suite_new("tree (high level)");
2463 1813
2464 cx_test_register(suite, test_tree_high_create); 1814 cx_test_register(suite, test_tree_high_create);
2465 cx_test_register(suite, test_tree_high_create_simple);
2466 cx_test_register(suite, test_tree_high_create_wrapped);
2467 cx_test_register(suite, test_tree_high_tree_depth); 1815 cx_test_register(suite, test_tree_high_tree_depth);
2468 cx_test_register(suite, test_tree_high_set_parent); 1816 // cx_test_register(suite, test_tree_high_set_parent);
2469 cx_test_register(suite, test_tree_high_insert_one); 1817 // cx_test_register(suite, test_tree_high_add_find_remove_nodes);
2470 cx_test_register(suite, test_tree_high_insert_many); 1818 // cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
2471 cx_test_register(suite, test_tree_high_add_find_remove_nodes); 1819 // cx_test_register(suite, test_tree_high_remove_or_destroy_root);
2472 cx_test_register(suite, test_tree_high_add_find_destroy_nodes); 1820 // cx_test_register(suite, test_tree_high_simple_destructor);
2473 cx_test_register(suite, test_tree_high_remove_or_destroy_root); 1821 // cx_test_register(suite, test_tree_high_iterator);
2474 cx_test_register(suite, test_tree_high_simple_destructor); 1822 // cx_test_register(suite, test_tree_high_visitor);
2475 cx_test_register(suite, test_tree_high_iterator);
2476 cx_test_register(suite, test_tree_high_visitor);
2477 1823
2478 return suite; 1824 return suite;
2479 } 1825 }

Mercurial Repository: ucx

mercurial