9 #include "ul_utmalloc.h"
12 /*===========================================================*/
15 #define GAVL_CHECK_NOBAL 0x0020
17 #define GAVL_ERR_PARENT 0x0001
18 #define GAVL_ERR_HDIFF 0x0002
19 #define GAVL_ERR_HEIGHT 0x0010
20 #define GAVL_ERR_BALANCE 0x0020
22 typedef struct gavl_check_st{
29 int (*node_fnc)(gavl_node_t *node, struct gavl_check_st *check) UL_ATTR_REENTRANT;
35 gavl_hdiff_check_recurse(gavl_node_t *node, gavl_node_t *parent,
36 gavl_check_st_t* check)
42 if(node->parent!=parent) check->err|=GAVL_ERR_PARENT;
43 lh=gavl_hdiff_check_recurse(node->left, node, check);
45 check->err|=check->node_fnc(node, check);
46 rh=gavl_hdiff_check_recurse(node->right, node, check);
48 if((rh>lh+1) || (rh+1<lh)){
49 if(!(check->mode&GAVL_CHECK_NOBAL)){
50 check->err|=GAVL_ERR_BALANCE;
53 if(node->hdiff!=lh-rh){
54 check->err|=GAVL_ERR_HDIFF;
57 if(check->err && !check->node) check->node=node;
59 return lh>rh?lh+1:rh+1;
63 gavl_hdiff_check_reperr(gavl_node_t *node, gavl_check_st_t* check)
70 gavl_hdiff_check(gavl_node_t *node, int mode)
74 gavl_check_st_t check;
84 h=gavl_hdiff_check_recurse(node, node->parent,&check);
86 if(!(check.mode&GAVL_CHECK_NOBAL)){
87 for(i=0;(1<<i)<=check.count;i++);
88 if(h>i+1) check.err|=GAVL_ERR_HEIGHT;
92 gavl_hdiff_check_reperr(node,&check);
97 /*===========================================================*/
98 /* custom tree definition */
100 #include "ul_gavlcust.h"
101 #include "ul_gavlrepcust.h"
102 #include "ul_gavlflesint.h"
104 #undef GAVL_TEST_FLES
106 typedef struct cust2_item {
112 typedef struct cust2_root {
113 #ifndef GAVL_TEST_FLES
114 gavl_cust_root_field_t my_root;
115 #else /*GAVL_TEST_FLES*/
116 gavl_fles_int_root_field_t my_root;
117 #endif /*GAVL_TEST_FLES*/
123 typedef int cust2_key_t;
125 /* Custom tree declarations */
126 /* GAVL_CUST_NODE_INT_DEC - standard custom tree with internal node */
127 /* GAVL_FLES_INT_DEC - tree with enhanced first last access speed */
129 #ifndef GAVL_TEST_FLES
130 GAVL_CUST_NODE_INT_DEC(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
131 my_root, my_node, my_val, cust2_cmp_fnc)
132 #else /*GAVL_TEST_FLES*/
133 GAVL_FLES_INT_DEC(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
134 my_root, my_node, my_val, cust2_cmp_fnc)
135 #endif /*GAVL_TEST_FLES*/
138 cust2_cmp_fnc(const cust2_key_t *a, const cust2_key_t *b)
141 if (*a<*b) return -1;
145 /* Custom tree implementation */
146 /* GAVL_CUST_NODE_INT_IMP - version with strict ordering */
147 /* GAVL_CUST_NODE_INT_REP_IMP - version without strict ordering */
148 /* GAVL_FLES_INT_IMP - tree with enhanced first last access speed */
150 #ifndef GAVL_TEST_FLES
151 GAVL_CUST_NODE_INT_IMP(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
152 my_root, my_node, my_val, cust2_cmp_fnc)
153 #else /*GAVL_TEST_FLES*/
154 GAVL_FLES_INT_IMP(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
155 my_root, my_node, my_val, cust2_cmp_fnc, 0,
156 root->my_first_val=cust2_first(root)->my_val,
157 root->my_last_val=cust2_first(root)->my_val,
159 #endif /*GAVL_TEST_FLES*/
161 cust2_root_t cust2_root;
164 void test_cust_tree(void)
168 cust2_item_t *item, *item2;
170 item=malloc(sizeof(cust2_item_t));
172 if(cust2_insert(&cust2_root,item)<0)
173 printf("cust2_insert error\n");
175 printf("Custom tree cust2 for_each:\n");
176 gavl_cust_for_each(cust2, &cust2_root, item)
177 printf("%d ",item->my_val);
181 printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
182 gavl_cust_for_each_from(cust2, &cust2_root, &k, item){
183 printf("After %d : ",item->my_val);
184 gavl_cust_for_each_after(cust2, &cust2_root, &item->my_val, item2)
185 printf(" %d",item2->my_val);
189 printf("Custom tree cust2 delete 1-90:\n");
190 for(i=1;i<=100-10;i++){
191 item=cust2_find(&cust2_root,&i);
192 if(cust2_delete(&cust2_root,item)<0)
193 printf("cust2_delete error\n");
197 printf("Custom tree cust2 for_each_rev:\n");
198 gavl_cust_for_each_rev(cust2,&cust2_root,item)
199 printf("%d ",item->my_val);
202 printf("Custom tree cust2 for_each_cut:\n");
203 gavl_cust_for_each_cut(cust2,&cust2_root,item){
204 printf("%d ",item->my_val);
210 void test_cust_tree_it(void)
218 item=malloc(sizeof(cust2_item_t));
220 if(cust2_insert(&cust2_root,item)<0)
221 printf("cust2_insert error\n");
223 printf("Custom tree cust2 for each with iterator:\n");
224 for(cust2_first_it(&cust2_root, &it1);
225 (item=cust2_it2item(&it1));cust2_next_it(&it1))
226 printf("%d ",item->my_val);
230 printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
231 for(cust2_find_first_it(&cust2_root, &k, &it1);
232 (item=cust2_it2item(&it1));cust2_next_it(&it1)){
233 printf("After %d : ",item->my_val);
234 for(cust2_find_after_it(&cust2_root, &item->my_val, &it2);
235 (item=cust2_it2item(&it2));cust2_next_it(&it2))
236 printf(" %d",item->my_val);
240 printf("Custom tree cust2 delete 1-90:\n");
241 for(i=1;i<=100-10;i++){
242 item=cust2_find(&cust2_root,&i);
243 if(cust2_delete(&cust2_root,item)<0)
244 printf("cust2_delete error\n");
248 printf("Custom tree cust2 for_each_rev:\n");
249 for(cust2_last_it(&cust2_root, &it1);
250 (item=cust2_it2item(&it1));cust2_prev_it(&it1))
251 printf("%d ",item->my_val);
254 printf("Custom tree cust2 for_each_cut:\n");
255 gavl_cust_for_each_cut(cust2,&cust2_root,item){
256 printf("%d ",item->my_val);
262 void test_cust_tree_macro_it(void)
270 item=malloc(sizeof(cust2_item_t));
272 if(cust2_insert(&cust2_root,item)<0)
273 printf("cust2_insert error\n");
275 printf("Custom tree cust2 for each with iterator:\n");
276 ul_for_each_it(cust2, &cust2_root, it1){
277 item=cust2_it2item(&it1);
278 printf("%d ",item->my_val);
283 printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
284 ul_for_each_from_it(cust2, &cust2_root, &k, it1){
285 item=cust2_it2item(&it1);
286 printf("After %d : ",item->my_val);
287 ul_for_each_after_it(cust2, &cust2_root, &item->my_val, it2){
288 item=cust2_it2item(&it2);
289 printf(" %d",item->my_val);
294 printf("Custom tree cust2 delete 1-90:\n");
295 for(i=1;i<=100-10;i++){
296 item=cust2_find(&cust2_root,&i);
297 if(cust2_delete(&cust2_root,item)<0)
298 printf("cust2_delete error\n");
302 printf("Custom tree cust2 for_each_rev:\n");
303 ul_for_each_rev_it(cust2, &cust2_root, it1){
304 item=cust2_it2item(&it1);
305 printf("%d ",item->my_val);
309 printf("Custom tree cust2 for_each_cut:\n");
310 gavl_cust_for_each_cut(cust2,&cust2_root,item){
311 printf("%d ",item->my_val);
317 /*===========================================================*/
320 void timing_test_print(struct timeval *start, struct timeval *stop, char *s)
323 sec=stop->tv_sec-start->tv_sec;
324 usec=stop->tv_usec-start->tv_usec;
333 printf("%s :\t%4ld.%06ld\n",s,sec,usec);
336 void cust_timing_test(void)
339 int items_cnt=100000;
340 cust2_item_t *items, *item;
341 struct timeval time_start, time_stop;
343 printf("\nRunning custom tree timing test for %d items\n",items_cnt);
345 items=malloc(items_cnt*sizeof(cust2_item_t));
347 printf("malloc failed\n");
351 for(i=0;i<items_cnt;i++){
353 items[i].more_data=0;
356 gettimeofday(&time_start,NULL);
357 for(i=0;i<items_cnt;i++){
358 if(cust2_insert(&cust2_root,items+i)<0)
359 printf("cust2_insert error\n");
361 gettimeofday(&time_stop,NULL);
362 timing_test_print(&time_start,&time_stop,"cust insert");
364 gettimeofday(&time_start,NULL);
365 for(i=0;i<items_cnt;i++){
366 if(!(item=cust2_find(&cust2_root,&i)))
367 printf("cust2_find error\n");
370 printf("gavl_find mismatch\n");
372 gettimeofday(&time_stop,NULL);
373 timing_test_print(&time_start,&time_stop,"cust find");
375 gettimeofday(&time_start,NULL);
376 for(i=0;i<items_cnt;i++){
378 if(cust2_delete(&cust2_root,items+i)<0)
379 printf("cust2_delete error\n");
381 if(!cust2_cut_first(&cust2_root))
382 printf("cust2_cut_first NULL\n");
385 gettimeofday(&time_stop,NULL);
386 timing_test_print(&time_start,&time_stop,"cust delete");
391 void timing_test(void)
394 int items_cnt=100000;
397 struct timeval time_start, time_stop;
400 tt_root.root_node = NULL;
401 tt_root.node_offs = UL_OFFSETOF(cust2_item_t, my_node);
402 /*tt_root.node_offs = -1;*/
403 tt_root.key_offs = UL_OFFSETOF(cust2_item_t, my_val);
404 tt_root.cmp_fnc = gavl_cmp_int;
406 printf("\nRunning generic tree timing test for %d items\n",items_cnt);
408 items=malloc(items_cnt*sizeof(cust2_item_t));
410 printf("malloc failed\n");
414 for(i=0;i<items_cnt;i++){
416 items[i].more_data=0;
419 gettimeofday(&time_start,NULL);
420 for(i=0;i<items_cnt;i++){
421 if(gavl_insert(&tt_root,items+i,0)<0)
422 printf("gavl_insert error\n");
424 gettimeofday(&time_stop,NULL);
425 timing_test_print(&time_start,&time_stop,"GAVL insert");
427 gettimeofday(&time_start,NULL);
428 for(i=0;i<items_cnt;i++){
429 if(!(item=gavl_find(&tt_root,&i)))
430 printf("gavl_find error\n");
433 printf("gavl_find mismatch\n");
435 gettimeofday(&time_stop,NULL);
436 timing_test_print(&time_start,&time_stop,"GAVL find");
438 gettimeofday(&time_start,NULL);
439 for(i=0;i<items_cnt;i++){
440 if(gavl_delete(&tt_root,items+i)<0)
441 printf("gavl_delete error\n");
443 gettimeofday(&time_stop,NULL);
444 timing_test_print(&time_start,&time_stop,"GAVL delete");
449 /*===========================================================*/
452 typedef struct test_item1 {
456 gavl_root_t test_gavl1={
459 .key_offs = UL_OFFSETOF(test_item1_t, val),
460 .cmp_fnc = gavl_cmp_int
463 int gavl_print_tree1(gavl_root_t *root, gavl_node_t *node,
464 int lev, gavl_node_t *parent, int mode)
477 lh=gavl_print_tree1(root, node->left,lev+1, node, mode);
479 val=*(int*)gavl_node2key(root,node);
481 for(i=0;i++<lev;) printf(" ");
482 printf(">%d %d\n",val,node->hdiff);
484 if(node->parent!=parent) printf("Parent error\n");
485 rh=gavl_print_tree1(root, node->right,lev+1, node, mode);
486 if((rh>lh+1) || (rh+1<lh)){
488 printf("Balance error for value %d, lh %d, rd %d, hdiff %d\n",val,lh,rh,node->hdiff);
492 if(node->hdiff!=lh-rh){
493 printf("HDIFF error for value %d, lh %d, rd %d, hdiff %d\n",val,lh,rh,node->hdiff);
499 for(i=0;(1<<i)<=cnt;i++);
501 printf("Count %d log %d max %d\n",cnt,i,ret);
503 if(ret>i+1) printf("Tree height >log2(n)+1\n");
505 printf("Error %d\n",err);
512 int gavl_check(gavl_root_t *root)
517 ret=gavl_print_tree1(root, root->root_node, 0, NULL, 0xc0);
522 void gavl_foreach_test1(gavl_root_t *root)
524 int val, prev=-INT_MAX;
526 for(n=gavl_first_node(root);n;n=gavl_next_node(n)){
527 val=*(int*)gavl_node2key(&test_gavl1,n);
529 if(prev>val) printf("\nError in ordering\n");
537 void gavl_foreach_test2(gavl_root_t *root)
539 int val, prev=-INT_MAX;
542 printf("gavl_generic_for_each:\n");
543 gavl_generic_for_each(test_item1_t, root, item1){
545 printf("after %d:",val);
546 if(prev>val) printf("\nError in ordering\n");
548 gavl_generic_for_each_after(test_item1_t, root, &val, item2)
550 printf(" %d",item2->val);
557 int main(int argc, char *argv[])
564 gavl_node_t *node, *node1, *node2;
574 printf("\nTree edit: a <val>|d <val>|x..exit > ");
579 if (scanf("%d",&val)==1){
580 item=malloc(sizeof(test_item1_t));
582 ret=gavl_insert(&test_gavl1,item,0);
583 printf("gavl_insert of val %d returned %d\n\n",val,ret);
584 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
588 if (scanf("%d",&val)==1){
589 ret=gavl_search_node(&test_gavl1, &val, GAVL_FANY, &node);
591 printf("No node with key %d\n",val);
594 item=gavl_node2item(&test_gavl1,node);
595 ret=gavl_delete_node(&test_gavl1,node);
597 printf("gavl_delete_node of val %d returned %d\n\n",val,ret);
598 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
602 if (scanf("%d",&val)==1){
603 item=gavl_find_first(&test_gavl1, &val);
605 printf("gavl_find_first find item with value %d\n", item->val);
607 printf("gavl_find_first found no item\n");
608 item=gavl_find_after(&test_gavl1, &val);
610 printf("gavl_find_after find item with value %d\n", item->val);
612 printf("gavl_find_after found no item\n");
616 gavl_foreach_test1(&test_gavl1);
620 gavl_foreach_test2(&test_gavl1);
624 ret=scanf("%d %d %d",&val, &n, &i);
628 item=malloc(sizeof(test_item1_t));
630 ret=gavl_insert(&test_gavl1,item,0);
632 printf("gavl_insert of val %d returned %d\n\n",val,ret);
633 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
637 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
638 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
644 node=gavl_last_node(&test_gavl1);
646 node1=gavl_prev_node(node);
647 gavl_delete_node(&test_gavl1,node);
648 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
650 node->right=node2; if(node2) node2->parent=node;
654 test_gavl1.root_node=node2;
655 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
660 node=gavl_first_node(&test_gavl1);
662 node1=gavl_next_node(node);
663 gavl_delete_node(&test_gavl1,node);
664 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
666 node->left=node2; if(node2) node2->parent=node;
670 test_gavl1.root_node=node2;
671 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
674 gavl_balance_enhance(&test_gavl1.root_node);
675 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
678 for(node1=gavl_first_node(&test_gavl1);node1;node1=node2){
679 /*This is test code and it doesnot free node or item */
680 node2=gavl_delete_and_next_node(&test_gavl1, node1);
681 printf("Value of node %d\n",*(int*)gavl_node2key(&test_gavl1, node1));
682 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
686 gavl_balance(&test_gavl1);
687 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x00);
690 if (scanf("%d",&val)==1){
691 ret=gavl_search_node(&test_gavl1, &val, GAVL_FANY, &node);
693 printf("No node with key %d\n",val);
698 if(node1->hdiff>0) node1=node1->left;
699 else node1=node1->right;
701 gavl_adjust_hdiff(node,-i);
702 if(!node->parent) test_gavl1.root_node=NULL;
703 else if(node==node->parent->left) node->parent->left=NULL;
704 else node->parent->right=NULL;
707 gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
710 printf("\nCheck of custom tree for_each\n");
712 printf("\nCheck of custom tree iterators\n");
713 test_cust_tree_macro_it();
714 printf("\nCheck of custom tree for_each iterators\n");