ulan/host/libs4c/ulut/ul_gavlchk.c

   1 #include <string.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <limits.h>
   5 #include <sys/time.h>
   6
   7 #include "ul_utmalloc.h"
   8 #include "ul_gavl.h"
   9
  10 /*===========================================================*/
  11 /* checking code */
  12
  13 #define GAVL_CHECK_NOBAL 0x0020
  14
  15 #define GAVL_ERR_PARENT  0x0001
  16 #define GAVL_ERR_HDIFF   0x0002
  17 #define GAVL_ERR_HEIGHT  0x0010
  18 #define GAVL_ERR_BALANCE 0x0020
  19
  20 typedef struct gavl_check_st{
  21   int mode;
  22   int err;
  23   int count;
  24   int depth;
  25   gavl_node_t *node;
  26   gavl_root_t *root;
  27   int (*node_fnc)(gavl_node_t *node, struct gavl_check_st *check);
  28   void *context;
  29   int *status;
  30 } gavl_check_st_t;
  31
  32 int
  33 gavl_hdiff_check_recurse(gavl_node_t *node, gavl_node_t *parent,
  34                          gavl_check_st_t* check)
  35 {
  36   int lh, rh;
  37
  38   if(!node) return 0;
  39   check->depth++;
  40   if(node->parent!=parent) check->err|=GAVL_ERR_PARENT;
  41   lh=gavl_hdiff_check_recurse(node->left, node, check);
  42   if(check->node_fnc)
  43     check->err|=check->node_fnc(node, check);
  44   rh=gavl_hdiff_check_recurse(node->right, node, check);
  45   check->count++;
  46   if((rh>lh+1) || (rh+1<lh)){
  47     if(!(check->mode&GAVL_CHECK_NOBAL)){
  48       check->err|=GAVL_ERR_BALANCE;
  49     }
  50   }
  51   if(node->hdiff!=lh-rh){
  52     check->err|=GAVL_ERR_HDIFF;
  53   }
  54
  55   if(check->err && !check->node) check->node=node;
  56   check->depth--;
  57   return lh>rh?lh+1:rh+1;
  58 }
  59
  60 void
  61 gavl_hdiff_check_reperr(gavl_node_t *node, gavl_check_st_t* check)
  62 {
  63   volatile int i;
  64   for(i=0;i<1000;i++);
  65 }
  66
  67 int
  68 gavl_hdiff_check(gavl_node_t *node, int mode)
  69 {
  70   int i;
  71   int h=0;
  72   gavl_check_st_t check;
  73   check.mode=mode;
  74   check.err=0;
  75   check.count=0;
  76   check.node=NULL;
  77   check.depth=0;
  78   check.node_fnc=NULL;
  79   check.root=NULL;
  80
  81   if(node)
  82     h=gavl_hdiff_check_recurse(node, node->parent,&check);
  83
  84   if(!(check.mode&GAVL_CHECK_NOBAL)){
  85     for(i=0;(1<<i)<=check.count;i++);
  86     if(h>i+1) check.err|=GAVL_ERR_HEIGHT;
  87   }
  88
  89   if(check.err){
  90     gavl_hdiff_check_reperr(node,&check);
  91   }
  92   return check.err;
  93 }
  94
  95 /*===========================================================*/
  96 /* custom tree definition */
  97
  98 #include "ul_gavlcust.h"
  99 #include "ul_gavlrepcust.h"
 100 #include "ul_gavlflesint.h"
 101
 102 #undef GAVL_TEST_FLES
 103
 104 typedef struct cust2_item {
 105   int my_val;
 106   gavl_node_t my_node;
 107   int more_data;
 108 } cust2_item_t;
 109
 110 typedef struct cust2_root {
 111  #ifndef GAVL_TEST_FLES
 112   gavl_cust_root_field_t my_root;
 113  #else /*GAVL_TEST_FLES*/
 114   gavl_fles_int_root_field_t my_root;
 115  #endif /*GAVL_TEST_FLES*/
 116   int my_info;
 117   int my_first_val;
 118   int my_last_val;
 119 } cust2_root_t;
 120
 121 typedef int cust2_key_t;
 122
 123 /* Custom tree declarations */
 124 /* GAVL_CUST_NODE_INT_DEC - standard custom tree with internal node */
 125 /* GAVL_FLES_INT_DEC      - tree with enhanced first last access speed  */
 126
 127 #ifndef GAVL_TEST_FLES
 128 GAVL_CUST_NODE_INT_DEC(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
 129         my_root, my_node, my_val, cust2_cmp_fnc)
 130 #else /*GAVL_TEST_FLES*/
 131 GAVL_FLES_INT_DEC(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
 132         my_root, my_node, my_val, cust2_cmp_fnc)
 133 #endif /*GAVL_TEST_FLES*/
 134
 135 inline int
 136 cust2_cmp_fnc(const cust2_key_t *a, const cust2_key_t *b)
 137 {
 138   if (*a>*b) return 1;
 139   if (*a<*b) return -1;
 140   return 0;
 141 }
 142
 143 /* Custom tree implementation */
 144 /* GAVL_CUST_NODE_INT_IMP - version with strict ordering */
 145 /* GAVL_CUST_NODE_INT_REP_IMP - version without strict ordering */
 146 /* GAVL_FLES_INT_IMP      - tree with enhanced first last access speed  */
 147
 148 #ifndef GAVL_TEST_FLES
 149 GAVL_CUST_NODE_INT_IMP(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
 150         my_root, my_node, my_val, cust2_cmp_fnc)
 151 #else /*GAVL_TEST_FLES*/
 152 GAVL_FLES_INT_IMP(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
 153         my_root, my_node, my_val, cust2_cmp_fnc, 0,
 154         root->my_first_val=cust2_first(root)->my_val,
 155         root->my_last_val=cust2_first(root)->my_val,
 156         )
 157 #endif /*GAVL_TEST_FLES*/
 158
 159 cust2_root_t cust2_root;
 160
 161
 162 void test_cust_tree(void)
 163 {
 164   int i;
 165   cust2_key_t k;
 166   cust2_item_t *item, *item2;
 167   for(i=1;i<=100;i++){
 168     item=malloc(sizeof(cust2_item_t));
 169     item->my_val=i;
 170     if(cust2_insert(&cust2_root,item)<0)
 171       printf("cust2_insert error\n");
 172   }
 173   printf("Custom tree cust2 for_each:\n");
 174   gavl_cust_for_each(cust2, &cust2_root, item)
 175     printf("%d ",item->my_val);
 176   printf("\n");
 177
 178   k=90;
 179   printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
 180   gavl_cust_for_each_from(cust2, &cust2_root, &k, item){
 181     printf("After %d : ",item->my_val);
 182     gavl_cust_for_each_after(cust2, &cust2_root, &item->my_val, item2)
 183       printf(" %d",item2->my_val);
 184     printf("\n");
 185   }
 186
 187   printf("Custom tree cust2 delete 1-90:\n");
 188   for(i=1;i<=100-10;i++){
 189     item=cust2_find(&cust2_root,&i);
 190     if(cust2_delete(&cust2_root,item)<0)
 191       printf("cust2_delete error\n");
 192     free(item);
 193   }
 194
 195   printf("Custom tree cust2 for_each_rev:\n");
 196   gavl_cust_for_each_rev(cust2,&cust2_root,item)
 197     printf("%d ",item->my_val);
 198   printf("\n");
 199
 200   printf("Custom tree cust2 for_each_cut:\n");
 201   gavl_cust_for_each_cut(cust2,&cust2_root,item){
 202     printf("%d ",item->my_val);
 203     free(item);
 204   }
 205   printf("\n");
 206 }
 207
 208 void test_cust_tree_it(void)
 209 {
 210   int i;
 211   cust2_key_t k;
 212   cust2_item_t *item;
 213   cust2_it_t it1, it2;
 214
 215   for(i=1;i<=100;i++){
 216     item=malloc(sizeof(cust2_item_t));
 217     item->my_val=i;
 218     if(cust2_insert(&cust2_root,item)<0)
 219       printf("cust2_insert error\n");
 220   }
 221   printf("Custom tree cust2 for each with iterator:\n");
 222   for(cust2_first_it(&cust2_root, &it1);
 223       (item=cust2_it2item(&it1));cust2_next_it(&it1))
 224     printf("%d ",item->my_val);
 225   printf("\n");
 226
 227   k=90;
 228   printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
 229   for(cust2_find_first_it(&cust2_root, &k, &it1);
 230       (item=cust2_it2item(&it1));cust2_next_it(&it1)){
 231     printf("After %d : ",item->my_val);
 232     for(cust2_find_after_it(&cust2_root, &item->my_val, &it2);
 233         (item=cust2_it2item(&it2));cust2_next_it(&it2))
 234       printf(" %d",item->my_val);
 235     printf("\n");
 236   }
 237
 238   printf("Custom tree cust2 delete 1-90:\n");
 239   for(i=1;i<=100-10;i++){
 240     item=cust2_find(&cust2_root,&i);
 241     if(cust2_delete(&cust2_root,item)<0)
 242       printf("cust2_delete error\n");
 243     free(item);
 244   }
 245
 246   printf("Custom tree cust2 for_each_rev:\n");
 247   for(cust2_last_it(&cust2_root, &it1);
 248       (item=cust2_it2item(&it1));cust2_prev_it(&it1))
 249     printf("%d ",item->my_val);
 250   printf("\n");
 251
 252   printf("Custom tree cust2 for_each_cut:\n");
 253   gavl_cust_for_each_cut(cust2,&cust2_root,item){
 254     printf("%d ",item->my_val);
 255     free(item);
 256   }
 257   printf("\n");
 258 }
 259
 260 void test_cust_tree_macro_it(void)
 261 {
 262   int i;
 263   cust2_key_t k;
 264   cust2_item_t *item;
 265   cust2_it_t it1, it2;
 266
 267   for(i=1;i<=100;i++){
 268     item=malloc(sizeof(cust2_item_t));
 269     item->my_val=i;
 270     if(cust2_insert(&cust2_root,item)<0)
 271       printf("cust2_insert error\n");
 272   }
 273   printf("Custom tree cust2 for each with iterator:\n");
 274   ul_for_each_it(cust2, &cust2_root, it1){
 275     item=cust2_it2item(&it1);
 276     printf("%d ",item->my_val);
 277   }
 278   printf("\n");
 279
 280   k=90;
 281   printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
 282   ul_for_each_from_it(cust2, &cust2_root, &k, it1){
 283     item=cust2_it2item(&it1);
 284     printf("After %d : ",item->my_val);
 285     ul_for_each_after_it(cust2, &cust2_root, &item->my_val, it2){
 286       item=cust2_it2item(&it2);
 287       printf(" %d",item->my_val);
 288     }
 289     printf("\n");
 290   }
 291
 292   printf("Custom tree cust2 delete 1-90:\n");
 293   for(i=1;i<=100-10;i++){
 294     item=cust2_find(&cust2_root,&i);
 295     if(cust2_delete(&cust2_root,item)<0)
 296       printf("cust2_delete error\n");
 297     free(item);
 298   }
 299
 300   printf("Custom tree cust2 for_each_rev:\n");
 301   ul_for_each_rev_it(cust2, &cust2_root, it1){
 302     item=cust2_it2item(&it1);
 303     printf("%d ",item->my_val);
 304   }
 305   printf("\n");
 306
 307   printf("Custom tree cust2 for_each_cut:\n");
 308   gavl_cust_for_each_cut(cust2,&cust2_root,item){
 309     printf("%d ",item->my_val);
 310     free(item);
 311   }
 312   printf("\n");
 313 }
 314
 315 /*===========================================================*/
 316 /* timing tests */
 317
 318 void timing_test_print(struct timeval *start, struct timeval *stop, char *s)
 319 {
 320   long sec, usec;
 321   sec=stop->tv_sec-start->tv_sec;
 322   usec=stop->tv_usec-start->tv_usec;
 323   if(usec>=1000000) {
 324     usec-=1000000;
 325     sec++;
 326   }
 327   if(usec<0) {
 328     usec+=1000000;
 329     sec--;
 330   }
 331   printf("%s :\t%4ld.%06ld\n",s,sec,usec);
 332 }
 333
 334 void cust_timing_test(void)
 335 {
 336   int i;
 337   int items_cnt=100000;
 338   cust2_item_t *items, *item;
 339   struct timeval time_start, time_stop;
 340
 341   printf("\nRunning custom tree timing test for %d items\n",items_cnt);
 342
 343   items=malloc(items_cnt*sizeof(cust2_item_t));
 344   if(!items){
 345     printf("malloc failed\n");
 346     return;
 347   }
 348
 349   for(i=0;i<items_cnt;i++){
 350     items[i].my_val=i;
 351     items[i].more_data=0;
 352   }
 353
 354   gettimeofday(&time_start,NULL);
 355   for(i=0;i<items_cnt;i++){
 356     if(cust2_insert(&cust2_root,items+i)<0)
 357       printf("cust2_insert error\n");
 358   }
 359   gettimeofday(&time_stop,NULL);
 360   timing_test_print(&time_start,&time_stop,"cust insert");
 361
 362   gettimeofday(&time_start,NULL);
 363   for(i=0;i<items_cnt;i++){
 364     if(!(item=cust2_find(&cust2_root,&i)))
 365       printf("cust2_find error\n");
 366     else
 367       if(item->my_val!=i)
 368         printf("gavl_find mismatch\n");
 369   }
 370   gettimeofday(&time_stop,NULL);
 371   timing_test_print(&time_start,&time_stop,"cust find");
 372
 373   gettimeofday(&time_start,NULL);
 374   for(i=0;i<items_cnt;i++){
 375     if(1){
 376       if(cust2_delete(&cust2_root,items+i)<0)
 377         printf("cust2_delete error\n");
 378     }else{
 379       if(!cust2_cut_first(&cust2_root))
 380         printf("cust2_cut_first NULL\n");
 381     }
 382   }
 383   gettimeofday(&time_stop,NULL);
 384   timing_test_print(&time_start,&time_stop,"cust delete");
 385
 386   free(items);
 387 }
 388
 389 void timing_test(void)
 390 {
 391   int i;
 392   int items_cnt=100000;
 393   cust2_item_t *items;
 394   cust2_item_t *item;
 395   struct timeval time_start, time_stop;
 396   gavl_root_t tt_root;
 397
 398   tt_root.root_node = NULL;
 399   tt_root.node_offs = UL_OFFSETOF(cust2_item_t, my_node);
 400   /*tt_root.node_offs = -1;*/
 401   tt_root.key_offs = UL_OFFSETOF(cust2_item_t, my_val);
 402   tt_root.cmp_fnc = gavl_cmp_int;
 403
 404   printf("\nRunning generic tree timing test for %d items\n",items_cnt);
 405
 406   items=malloc(items_cnt*sizeof(cust2_item_t));
 407   if(!items){
 408     printf("malloc failed\n");
 409     return;
 410   }
 411
 412   for(i=0;i<items_cnt;i++){
 413     items[i].my_val=i;
 414     items[i].more_data=0;
 415   }
 416
 417   gettimeofday(&time_start,NULL);
 418   for(i=0;i<items_cnt;i++){
 419     if(gavl_insert(&tt_root,items+i,0)<0)
 420       printf("gavl_insert error\n");
 421   }
 422   gettimeofday(&time_stop,NULL);
 423   timing_test_print(&time_start,&time_stop,"GAVL insert");
 424
 425   gettimeofday(&time_start,NULL);
 426   for(i=0;i<items_cnt;i++){
 427     if(!(item=gavl_find(&tt_root,&i)))
 428       printf("gavl_find error\n");
 429     else
 430       if(item->my_val!=i)
 431         printf("gavl_find mismatch\n");
 432   }
 433   gettimeofday(&time_stop,NULL);
 434   timing_test_print(&time_start,&time_stop,"GAVL find");
 435
 436   gettimeofday(&time_start,NULL);
 437   for(i=0;i<items_cnt;i++){
 438     if(gavl_delete(&tt_root,items+i)<0)
 439       printf("gavl_delete error\n");
 440   }
 441   gettimeofday(&time_stop,NULL);
 442   timing_test_print(&time_start,&time_stop,"GAVL delete");
 443
 444   free(items);
 445 }
 446
 447 /*===========================================================*/
 448 /* test code */
 449
 450 typedef struct test_item1 {
 451   int val;
 452 } test_item1_t;
 453
 454 gavl_root_t test_gavl1={
 455   .root_node = NULL,
 456   .node_offs = -1,
 457   .key_offs = UL_OFFSETOF(test_item1_t, val),
 458   .cmp_fnc = gavl_cmp_int
 459 };
 460
 461 int gavl_print_tree1(gavl_root_t *root, gavl_node_t *node,
 462                 int lev, gavl_node_t *parent, int mode)
 463 {
 464   static int cnt;
 465   static int err;
 466   int i, val;
 467   int lh, rh;
 468   int ret;
 469   if(!parent){
 470     cnt=0;
 471     err=0;
 472   }
 473   if(node!=NULL)
 474   {
 475     lh=gavl_print_tree1(root, node->left,lev+1, node, mode);
 476     cnt++;
 477     val=*(int*)gavl_node2key(root,node);
 478     if(!(mode&0x80)){
 479       for(i=0;i++<lev;) printf(" ");
 480       printf(">%d  %d\n",val,node->hdiff);
 481     }
 482     if(node->parent!=parent) printf("Parent error\n");
 483     rh=gavl_print_tree1(root, node->right,lev+1, node, mode);
 484     if((rh>lh+1) || (rh+1<lh)){
 485       if(!(mode&0x20)){
 486         printf("Balance error for value %d, lh %d, rd %d, hdiff %d\n",val,lh,rh,node->hdiff);
 487         err=2;
 488       }
 489     }
 490     if(node->hdiff!=lh-rh){
 491       printf("HDIFF error for value %d, lh %d, rd %d, hdiff %d\n",val,lh,rh,node->hdiff);
 492       err=1;
 493     }
 494     ret=lh>rh?lh+1:rh+1;
 495   } else ret=0;
 496   if(!parent){
 497     for(i=0;(1<<i)<=cnt;i++);
 498     if(!(mode&0x40)){
 499       printf("Count %d log %d max %d\n",cnt,i,ret);
 500     }
 501     if(ret>i+1) printf("Tree height >log2(n)+1\n");
 502     if(err){
 503       printf("Error %d\n",err);
 504       ret=-1;
 505     }
 506   }
 507   return ret;
 508 }
 509
 510 int gavl_check(gavl_root_t *root)
 511 {
 512   int ret;
 513   if(!root)
 514     root=&test_gavl1;
 515   ret=gavl_print_tree1(root, root->root_node, 0, NULL, 0xc0);
 516   return ret;
 517 }
 518
 519
 520 void gavl_foreach_test1(gavl_root_t *root)
 521 {
 522   int val, prev=-INT_MAX;
 523   gavl_node_t *n;
 524   for(n=gavl_first_node(root);n;n=gavl_next_node(n)){
 525     val=*(int*)gavl_node2key(&test_gavl1,n);
 526     printf(" %d",val);
 527     if(prev>val) printf("\nError in ordering\n");
 528     prev=val;
 529   }
 530   printf("\n");
 531
 532 }
 533
 534 #ifdef WITH_C99
 535 void gavl_foreach_test2(gavl_root_t *root)
 536 {
 537   int val, prev=-INT_MAX;
 538   test_item1_t *item1;
 539   test_item1_t *item2;
 540   printf("gavl_generic_for_each:\n");
 541   gavl_generic_for_each(test_item1_t, root, item1){
 542     val=item1->val;
 543     printf("after %d:",val);
 544     if(prev>val) printf("\nError in ordering\n");
 545     prev=val;
 546     gavl_generic_for_each_after(test_item1_t, root, &val, item2)
 547     {
 548       printf(" %d",item2->val);
 549     }
 550     printf("\n");
 551   }
 552 }
 553 #endif /*WITH_C99*/
 554
 555 int main(int argc, char *argv[])
 556 {
 557   int val;
 558   int n, i;
 559   int ret;
 560   char c;
 561   test_item1_t *item;
 562   gavl_node_t *node, *node1, *node2;
 563
 564   if(0){
 565     cust_timing_test();
 566     return 0;
 567   }
 568
 569   c=0;
 570   do{
 571     if(!c || (c=='\n'))
 572       printf("\nTree edit: a <val>|d <val>|x..exit > ");
 573     c=0;
 574     scanf("%c",&c);
 575     switch(c){
 576       case 'a':
 577         if (scanf("%d",&val)==1){
 578           item=malloc(sizeof(test_item1_t));
 579           item->val=val;
 580           ret=gavl_insert(&test_gavl1,item,0);
 581           printf("gavl_insert of val %d returned %d\n\n",val,ret);
 582           gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
 583         }
 584         break;
 585       case 'd':
 586         if (scanf("%d",&val)==1){
 587           ret=gavl_search_node(&test_gavl1, &val, GAVL_FANY, &node);
 588           if(!ret){
 589             printf("No node with key %d\n",val);
 590             break;
 591           }
 592           item=gavl_node2item(&test_gavl1,node);
 593           ret=gavl_delete_node(&test_gavl1,node);
 594           free(item);
 595           printf("gavl_delete_node of val %d returned %d\n\n",val,ret);
 596           gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
 597         }
 598         break;
 599       case 'S':
 600         if (scanf("%d",&val)==1){
 601           item=gavl_find_first(&test_gavl1, &val);
 602           if(item)
 603             printf("gavl_find_first find item with value %d\n", item->val);
 604           else
 605             printf("gavl_find_first found no item\n");
 606           item=gavl_find_after(&test_gavl1, &val);
 607           if(item)
 608             printf("gavl_find_after find item with value %d\n", item->val);
 609           else
 610             printf("gavl_find_after found no item\n");
 611         }
 612         break;
 613       case 'f':
 614         gavl_foreach_test1(&test_gavl1);
 615         break;
 616      #ifdef WITH_C99
 617       case 'F':
 618         gavl_foreach_test2(&test_gavl1);
 619         break;
 620      #endif /*WITH_C99*/
 621       case 's':
 622         ret=scanf("%d %d %d",&val, &n, &i);
 623         if(ret<3) i=1;
 624         if (ret>=2){
 625           while(n--){
 626             item=malloc(sizeof(test_item1_t));
 627             item->val=val;
 628             ret=gavl_insert(&test_gavl1,item,0);
 629             if(ret<0)
 630               printf("gavl_insert of val %d returned %d\n\n",val,ret);
 631             gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
 632             val+=i;
 633           }
 634           printf("\n");
 635           gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
 636           gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
 637         }
 638         break;
 639       case 'l':
 640         i=0;
 641         node2=NULL;
 642         node=gavl_last_node(&test_gavl1);
 643         while(node){
 644           node1=gavl_prev_node(node);
 645           gavl_delete_node(&test_gavl1,node);
 646           gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
 647           node->hdiff=i; i--;
 648           node->right=node2; if(node2) node2->parent=node;
 649           node2=node;
 650           node=node1;
 651         }
 652         test_gavl1.root_node=node2;
 653         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 654         break;
 655       case 'L':
 656         i=0;
 657         node2=NULL;
 658         node=gavl_first_node(&test_gavl1);
 659         while(node){
 660           node1=gavl_next_node(node);
 661           gavl_delete_node(&test_gavl1,node);
 662           gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
 663           node->hdiff=i; i++;
 664           node->left=node2; if(node2) node2->parent=node;
 665           node2=node;
 666           node=node1;
 667         }
 668         test_gavl1.root_node=node2;
 669         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 670         break;
 671       case 'r':
 672         gavl_balance_enhance(&test_gavl1.root_node);
 673         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 674         break;
 675       case 'k':
 676         for(node1=gavl_first_node(&test_gavl1);node1;node1=node2){
 677           /*This is test code and it doesnot free node or item */
 678           node2=gavl_delete_and_next_node(&test_gavl1, node1);
 679           printf("Value of node %d\n",*(int*)gavl_node2key(&test_gavl1, node1));
 680           gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 681         }
 682         break;
 683       case 'b':
 684         gavl_balance(&test_gavl1);
 685         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x00);
 686         break;
 687       case 'c':
 688         if (scanf("%d",&val)==1){
 689           ret=gavl_search_node(&test_gavl1, &val, GAVL_FANY, &node);
 690           if(!ret){
 691             printf("No node with key %d\n",val);
 692             break;
 693           }
 694           node1=node;
 695           for(i=0;node1;i++){
 696             if(node1->hdiff>0) node1=node1->left;
 697             else node1=node1->right;
 698           }
 699           gavl_adjust_hdiff(node,-i);
 700           if(!node->parent) test_gavl1.root_node=NULL;
 701           else if(node==node->parent->left) node->parent->left=NULL;
 702           else node->parent->right=NULL;
 703
 704         }
 705         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 706         break;
 707       case 'C':
 708         printf("\nCheck of custom tree for_each\n");
 709         test_cust_tree();
 710         printf("\nCheck of custom tree iterators\n");
 711         test_cust_tree_macro_it();
 712         printf("\nCheck of custom tree for_each iterators\n");
 713         test_cust_tree_it();
 714         break;
 715       case 't':
 716         timing_test();
 717         break;
 718       case 'T':
 719         cust_timing_test();
 720         break;
 721     }
 722   } while(c!='x');
 723   return 0;
 724 }
 725