ulut/ul_gavlchk.c

   1 #include <string.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <limits.h>
   5 #if !defined(SDCC) && !defined(__SDCC)
   6 #include <sys/time.h>
   7 #endif
   8
   9 #include "ul_utmalloc.h"
  10 #include "ul_gavl.h"
  11
  12 /*===========================================================*/
  13 /* checking code */
  14
  15 #define GAVL_CHECK_NOBAL 0x0020
  16
  17 #define GAVL_ERR_PARENT  0x0001
  18 #define GAVL_ERR_HDIFF   0x0002
  19 #define GAVL_ERR_HEIGHT  0x0010
  20 #define GAVL_ERR_BALANCE 0x0020
  21
  22 typedef struct gavl_check_st{
  23   int mode;
  24   int err;
  25   int count;
  26   int depth;
  27   gavl_node_t *node;
  28   gavl_root_t *root;
  29   int (*node_fnc)(gavl_node_t *node, struct gavl_check_st *check) UL_ATTR_REENTRANT;
  30   void *context;
  31   int *status;
  32 } gavl_check_st_t;
  33
  34 int
  35 gavl_hdiff_check_recurse(gavl_node_t *node, gavl_node_t *parent,
  36                          gavl_check_st_t* check)
  37 {
  38   int lh, rh;
  39
  40   if(!node) return 0;
  41   check->depth++;
  42   if(node->parent!=parent) check->err|=GAVL_ERR_PARENT;
  43   lh=gavl_hdiff_check_recurse(node->left, node, check);
  44   if(check->node_fnc)
  45     check->err|=check->node_fnc(node, check);
  46   rh=gavl_hdiff_check_recurse(node->right, node, check);
  47   check->count++;
  48   if((rh>lh+1) || (rh+1<lh)){
  49     if(!(check->mode&GAVL_CHECK_NOBAL)){
  50       check->err|=GAVL_ERR_BALANCE;
  51     }
  52   }
  53   if(node->hdiff!=lh-rh){
  54     check->err|=GAVL_ERR_HDIFF;
  55   }
  56
  57   if(check->err && !check->node) check->node=node;
  58   check->depth--;
  59   return lh>rh?lh+1:rh+1;
  60 }
  61
  62 void
  63 gavl_hdiff_check_reperr(gavl_node_t *node, gavl_check_st_t* check)
  64 {
  65   volatile int i;
  66   for(i=0;i<1000;i++);
  67 }
  68
  69 int
  70 gavl_hdiff_check(gavl_node_t *node, int mode)
  71 {
  72   int i;
  73   int h=0;
  74   gavl_check_st_t check;
  75   check.mode=mode;
  76   check.err=0;
  77   check.count=0;
  78   check.node=NULL;
  79   check.depth=0;
  80   check.node_fnc=NULL;
  81   check.root=NULL;
  82
  83   if(node)
  84     h=gavl_hdiff_check_recurse(node, node->parent,&check);
  85
  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;
  89   }
  90
  91   if(check.err){
  92     gavl_hdiff_check_reperr(node,&check);
  93   }
  94   return check.err;
  95 }
  96
  97 /*===========================================================*/
  98 /* custom tree definition */
  99
 100 #include "ul_gavlcust.h"
 101 #include "ul_gavlrepcust.h"
 102 #include "ul_gavlflesint.h"
 103
 104 #undef GAVL_TEST_FLES
 105
 106 typedef struct cust2_item {
 107   int my_val;
 108   gavl_node_t my_node;
 109   int more_data;
 110 } cust2_item_t;
 111
 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*/
 118   int my_info;
 119   int my_first_val;
 120   int my_last_val;
 121 } cust2_root_t;
 122
 123 typedef int cust2_key_t;
 124
 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  */
 128
 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*/
 136
 137 inline int
 138 cust2_cmp_fnc(const cust2_key_t *a, const cust2_key_t *b)
 139 {
 140   if (*a>*b) return 1;
 141   if (*a<*b) return -1;
 142   return 0;
 143 }
 144
 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  */
 149
 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,
 158         )
 159 #endif /*GAVL_TEST_FLES*/
 160
 161 cust2_root_t cust2_root;
 162
 163
 164 void test_cust_tree(void)
 165 {
 166   int i;
 167   cust2_key_t k;
 168   cust2_item_t *item, *item2;
 169   for(i=1;i<=100;i++){
 170     item=malloc(sizeof(cust2_item_t));
 171     item->my_val=i;
 172     if(cust2_insert(&cust2_root,item)<0)
 173       printf("cust2_insert error\n");
 174   }
 175   printf("Custom tree cust2 for_each:\n");
 176   gavl_cust_for_each(cust2, &cust2_root, item)
 177     printf("%d ",item->my_val);
 178   printf("\n");
 179
 180   k=90;
 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);
 186     printf("\n");
 187   }
 188
 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");
 194     free(item);
 195   }
 196
 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);
 200   printf("\n");
 201
 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);
 205     free(item);
 206   }
 207   printf("\n");
 208 }
 209
 210 void test_cust_tree_it(void)
 211 {
 212   int i;
 213   cust2_key_t k;
 214   cust2_item_t *item;
 215   cust2_it_t it1, it2;
 216
 217   for(i=1;i<=100;i++){
 218     item=malloc(sizeof(cust2_item_t));
 219     item->my_val=i;
 220     if(cust2_insert(&cust2_root,item)<0)
 221       printf("cust2_insert error\n");
 222   }
 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);
 227   printf("\n");
 228
 229   k=90;
 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);
 237     printf("\n");
 238   }
 239
 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");
 245     free(item);
 246   }
 247
 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);
 252   printf("\n");
 253
 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);
 257     free(item);
 258   }
 259   printf("\n");
 260 }
 261
 262 void test_cust_tree_macro_it(void)
 263 {
 264   int i;
 265   cust2_key_t k;
 266   cust2_item_t *item;
 267   cust2_it_t it1, it2;
 268
 269   for(i=1;i<=100;i++){
 270     item=malloc(sizeof(cust2_item_t));
 271     item->my_val=i;
 272     if(cust2_insert(&cust2_root,item)<0)
 273       printf("cust2_insert error\n");
 274   }
 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);
 279   }
 280   printf("\n");
 281
 282   k=90;
 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);
 290     }
 291     printf("\n");
 292   }
 293
 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");
 299     free(item);
 300   }
 301
 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);
 306   }
 307   printf("\n");
 308
 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);
 312     free(item);
 313   }
 314   printf("\n");
 315 }
 316
 317 /*===========================================================*/
 318 /* timing tests */
 319
 320 void timing_test_print(struct timeval *start, struct timeval *stop, char *s)
 321 {
 322   long sec, usec;
 323   sec=stop->tv_sec-start->tv_sec;
 324   usec=stop->tv_usec-start->tv_usec;
 325   if(usec>=1000000) {
 326     usec-=1000000;
 327     sec++;
 328   }
 329   if(usec<0) {
 330     usec+=1000000;
 331     sec--;
 332   }
 333   printf("%s :\t%4ld.%06ld\n",s,sec,usec);
 334 }
 335
 336 void cust_timing_test(void)
 337 {
 338   int i;
 339   int items_cnt=100000;
 340   cust2_item_t *items, *item;
 341   struct timeval time_start, time_stop;
 342
 343   printf("\nRunning custom tree timing test for %d items\n",items_cnt);
 344
 345   items=malloc(items_cnt*sizeof(cust2_item_t));
 346   if(!items){
 347     printf("malloc failed\n");
 348     return;
 349   }
 350
 351   for(i=0;i<items_cnt;i++){
 352     items[i].my_val=i;
 353     items[i].more_data=0;
 354   }
 355
 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");
 360   }
 361   gettimeofday(&time_stop,NULL);
 362   timing_test_print(&time_start,&time_stop,"cust insert");
 363
 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");
 368     else
 369       if(item->my_val!=i)
 370         printf("gavl_find mismatch\n");
 371   }
 372   gettimeofday(&time_stop,NULL);
 373   timing_test_print(&time_start,&time_stop,"cust find");
 374
 375   gettimeofday(&time_start,NULL);
 376   for(i=0;i<items_cnt;i++){
 377     if(1){
 378       if(cust2_delete(&cust2_root,items+i)<0)
 379         printf("cust2_delete error\n");
 380     }else{
 381       if(!cust2_cut_first(&cust2_root))
 382         printf("cust2_cut_first NULL\n");
 383     }
 384   }
 385   gettimeofday(&time_stop,NULL);
 386   timing_test_print(&time_start,&time_stop,"cust delete");
 387
 388   free(items);
 389 }
 390
 391 void timing_test(void)
 392 {
 393   int i;
 394   int items_cnt=100000;
 395   cust2_item_t *items;
 396   cust2_item_t *item;
 397   struct timeval time_start, time_stop;
 398   gavl_root_t tt_root;
 399
 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;
 405
 406   printf("\nRunning generic tree timing test for %d items\n",items_cnt);
 407
 408   items=malloc(items_cnt*sizeof(cust2_item_t));
 409   if(!items){
 410     printf("malloc failed\n");
 411     return;
 412   }
 413
 414   for(i=0;i<items_cnt;i++){
 415     items[i].my_val=i;
 416     items[i].more_data=0;
 417   }
 418
 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");
 423   }
 424   gettimeofday(&time_stop,NULL);
 425   timing_test_print(&time_start,&time_stop,"GAVL insert");
 426
 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");
 431     else
 432       if(item->my_val!=i)
 433         printf("gavl_find mismatch\n");
 434   }
 435   gettimeofday(&time_stop,NULL);
 436   timing_test_print(&time_start,&time_stop,"GAVL find");
 437
 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");
 442   }
 443   gettimeofday(&time_stop,NULL);
 444   timing_test_print(&time_start,&time_stop,"GAVL delete");
 445
 446   free(items);
 447 }
 448
 449 /*===========================================================*/
 450 /* test code */
 451
 452 typedef struct test_item1 {
 453   int val;
 454 } test_item1_t;
 455
 456 gavl_root_t test_gavl1={
 457   .root_node = NULL,
 458   .node_offs = -1,
 459   .key_offs = UL_OFFSETOF(test_item1_t, val),
 460   .cmp_fnc = gavl_cmp_int
 461 };
 462
 463 int gavl_print_tree1(gavl_root_t *root, gavl_node_t *node,
 464                 int lev, gavl_node_t *parent, int mode)
 465 {
 466   static int cnt;
 467   static int err;
 468   int i, val;
 469   int lh, rh;
 470   int ret;
 471   if(!parent){
 472     cnt=0;
 473     err=0;
 474   }
 475   if(node!=NULL)
 476   {
 477     lh=gavl_print_tree1(root, node->left,lev+1, node, mode);
 478     cnt++;
 479     val=*(int*)gavl_node2key(root,node);
 480     if(!(mode&0x80)){
 481       for(i=0;i++<lev;) printf(" ");
 482       printf(">%d  %d\n",val,node->hdiff);
 483     }
 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)){
 487       if(!(mode&0x20)){
 488         printf("Balance error for value %d, lh %d, rd %d, hdiff %d\n",val,lh,rh,node->hdiff);
 489         err=2;
 490       }
 491     }
 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);
 494       err=1;
 495     }
 496     ret=lh>rh?lh+1:rh+1;
 497   } else ret=0;
 498   if(!parent){
 499     for(i=0;(1<<i)<=cnt;i++);
 500     if(!(mode&0x40)){
 501       printf("Count %d log %d max %d\n",cnt,i,ret);
 502     }
 503     if(ret>i+1) printf("Tree height >log2(n)+1\n");
 504     if(err){
 505       printf("Error %d\n",err);
 506       ret=-1;
 507     }
 508   }
 509   return ret;
 510 }
 511
 512 int gavl_check(gavl_root_t *root)
 513 {
 514   int ret;
 515   if(!root)
 516     root=&test_gavl1;
 517   ret=gavl_print_tree1(root, root->root_node, 0, NULL, 0xc0);
 518   return ret;
 519 }
 520
 521
 522 void gavl_foreach_test1(gavl_root_t *root)
 523 {
 524   int val, prev=-INT_MAX;
 525   gavl_node_t *n;
 526   for(n=gavl_first_node(root);n;n=gavl_next_node(n)){
 527     val=*(int*)gavl_node2key(&test_gavl1,n);
 528     printf(" %d",val);
 529     if(prev>val) printf("\nError in ordering\n");
 530     prev=val;
 531   }
 532   printf("\n");
 533
 534 }
 535
 536 #ifdef WITH_C99
 537 void gavl_foreach_test2(gavl_root_t *root)
 538 {
 539   int val, prev=-INT_MAX;
 540   test_item1_t *item1;
 541   test_item1_t *item2;
 542   printf("gavl_generic_for_each:\n");
 543   gavl_generic_for_each(test_item1_t, root, item1){
 544     val=item1->val;
 545     printf("after %d:",val);
 546     if(prev>val) printf("\nError in ordering\n");
 547     prev=val;
 548     gavl_generic_for_each_after(test_item1_t, root, &val, item2)
 549     {
 550       printf(" %d",item2->val);
 551     }
 552     printf("\n");
 553   }
 554 }
 555 #endif /*WITH_C99*/
 556
 557 int main(int argc, char *argv[])
 558 {
 559   int val;
 560   int n, i;
 561   int ret;
 562   char c;
 563   test_item1_t *item;
 564   gavl_node_t *node, *node1, *node2;
 565
 566   if(0){
 567     cust_timing_test();
 568     return 0;
 569   }
 570
 571   c=0;
 572   do{
 573     if(!c || (c=='\n'))
 574       printf("\nTree edit: a <val>|d <val>|x..exit > ");
 575     c=0;
 576     scanf("%c",&c);
 577     switch(c){
 578       case 'a':
 579         if (scanf("%d",&val)==1){
 580           item=malloc(sizeof(test_item1_t));
 581           item->val=val;
 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);
 585         }
 586         break;
 587       case 'd':
 588         if (scanf("%d",&val)==1){
 589           ret=gavl_search_node(&test_gavl1, &val, GAVL_FANY, &node);
 590           if(!ret){
 591             printf("No node with key %d\n",val);
 592             break;
 593           }
 594           item=gavl_node2item(&test_gavl1,node);
 595           ret=gavl_delete_node(&test_gavl1,node);
 596           free(item);
 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);
 599         }
 600         break;
 601       case 'S':
 602         if (scanf("%d",&val)==1){
 603           item=gavl_find_first(&test_gavl1, &val);
 604           if(item)
 605             printf("gavl_find_first find item with value %d\n", item->val);
 606           else
 607             printf("gavl_find_first found no item\n");
 608           item=gavl_find_after(&test_gavl1, &val);
 609           if(item)
 610             printf("gavl_find_after find item with value %d\n", item->val);
 611           else
 612             printf("gavl_find_after found no item\n");
 613         }
 614         break;
 615       case 'f':
 616         gavl_foreach_test1(&test_gavl1);
 617         break;
 618      #ifdef WITH_C99
 619       case 'F':
 620         gavl_foreach_test2(&test_gavl1);
 621         break;
 622      #endif /*WITH_C99*/
 623       case 's':
 624         ret=scanf("%d %d %d",&val, &n, &i);
 625         if(ret<3) i=1;
 626         if (ret>=2){
 627           while(n--){
 628             item=malloc(sizeof(test_item1_t));
 629             item->val=val;
 630             ret=gavl_insert(&test_gavl1,item,0);
 631             if(ret<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);
 634             val+=i;
 635           }
 636           printf("\n");
 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);
 639         }
 640         break;
 641       case 'l':
 642         i=0;
 643         node2=NULL;
 644         node=gavl_last_node(&test_gavl1);
 645         while(node){
 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);
 649           node->hdiff=i; i--;
 650           node->right=node2; if(node2) node2->parent=node;
 651           node2=node;
 652           node=node1;
 653         }
 654         test_gavl1.root_node=node2;
 655         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 656         break;
 657       case 'L':
 658         i=0;
 659         node2=NULL;
 660         node=gavl_first_node(&test_gavl1);
 661         while(node){
 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);
 665           node->hdiff=i; i++;
 666           node->left=node2; if(node2) node2->parent=node;
 667           node2=node;
 668           node=node1;
 669         }
 670         test_gavl1.root_node=node2;
 671         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 672         break;
 673       case 'r':
 674         gavl_balance_enhance(&test_gavl1.root_node);
 675         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 676         break;
 677       case 'k':
 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);
 683         }
 684         break;
 685       case 'b':
 686         gavl_balance(&test_gavl1);
 687         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x00);
 688         break;
 689       case 'c':
 690         if (scanf("%d",&val)==1){
 691           ret=gavl_search_node(&test_gavl1, &val, GAVL_FANY, &node);
 692           if(!ret){
 693             printf("No node with key %d\n",val);
 694             break;
 695           }
 696           node1=node;
 697           for(i=0;node1;i++){
 698             if(node1->hdiff>0) node1=node1->left;
 699             else node1=node1->right;
 700           }
 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;
 705
 706         }
 707         gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
 708         break;
 709       case 'C':
 710         printf("\nCheck of custom tree for_each\n");
 711         test_cust_tree();
 712         printf("\nCheck of custom tree iterators\n");
 713         test_cust_tree_macro_it();
 714         printf("\nCheck of custom tree for_each iterators\n");
 715         test_cust_tree_it();
 716         break;
 717       case 't':
 718         timing_test();
 719         break;
 720       case 'T':
 721         cust_timing_test();
 722         break;
 723     }
 724   } while(c!='x');
 725   return 0;
 726 }
 727