orte/liborte/ul_gavl.c

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_gavl.c     - generic AVL tree
   5
   6   (C) Copyright 2003-2004 by Pavel Pisa - Originator
   7
   8   The uLan utilities library can be used, copied and modified under
   9   next licenses
  10     - GPL - GNU General Public License
  11     - LGPL - GNU Lesser General Public License
  12     - MPL - Mozilla Public License
  13     - and other licenses added by project originators
  14   Code can be modified and re-distributed under any combination
  15   of the above listed licenses. If contributor does not agree with
  16   some of the licenses, he/she can delete appropriate line.
  17   Warning, if you delete all lines, you are not allowed to
  18   distribute source code and/or binaries utilizing code.
  19
  20   See files COPYING and README for details.
  21
  22  *******************************************************************/
  23
  24 #include <orte_all.h>
  25 //#include <string.h>
  26 //#include "ul_utmalloc.h"
  27
  28 #include "ul_gavl.h"
  29
  30 int
  31 gavl_hdiff_check(gavl_node_t *node, int mode);
  32
  33 #if 0
  34  #define GAVL_HDIFF_DEBUG(tree, mode) gavl_hdiff_check(tree, mode)
  35 #else
  36  #define GAVL_HDIFF_DEBUG(tree, mode)
  37 #endif
  38
  39
  40 /**
  41  * gavl_first_node - Returns First Node of GAVL Tree
  42  * @root:       GAVL tree root
  43  *
  44  * Return Value: pointer to the first node of tree according to ordering
  45  */
  46 gavl_node_t *
  47 gavl_first_node(const gavl_root_t *root)
  48 {
  49   gavl_node_t *n=root->root_node;
  50   if(!n) return NULL;
  51   while(n->left)
  52     n=n->left;
  53   return n;
  54 }
  55
  56 /**
  57  * gavl_last_node - Returns Last Node of GAVL Tree
  58  * @root:       GAVL tree root
  59  *
  60  * Return Value: pointer to the last node of tree according to ordering
  61  */
  62 gavl_node_t *
  63 gavl_last_node(const gavl_root_t *root)
  64 {
  65   gavl_node_t *n=root->root_node;
  66   if(!n) return NULL;
  67   while(n->right)
  68     n=n->right;
  69   return n;
  70 }
  71
  72 /**
  73  * gavl_is_empty - Check for Empty GAVL Tree
  74  * @root:       GAVL tree root
  75  *
  76  * Return Value: returns non-zero value if there is no node in the tree
  77  */
  78 int
  79 gavl_is_empty(const gavl_root_t *root)
  80 {
  81   return !root->root_node;
  82 }
  83
  84 /**
  85  * gavl_search_node - Search for Node or Place for Node by Key
  86  * @root:       GAVL tree root
  87  * @key:        key value searched for
  88  * @mode:       mode of the search operation
  89  * @nodep:      pointer to place for storing of pointer to found node
  90  *              or pointer to node which should be parent of inserted node
  91  *
  92  * Core search routine for GAVL trees
  93  * searches in tree starting at @root for node of item
  94  * with value of item field at offset @key_off
  95  * equal to provided *@key value. Values are compared by function
  96  * pointed by *@cmp_fnc field in the tree @root.
  97  * Integer @mode modifies search algorithm:
  98  *   %GAVL_FANY   .. finds node of any item with field value *@key,
  99  *   %GAVL_FFIRST .. finds node of first item with *@key,
 100  *   %GAVL_FAFTER .. node points after last item with *@key value,
 101  *        reworded - index points at first item with higher
 102  *        value of field or after last item
 103  * Return Value: Return of nonzero value indicates match found.
 104  *      If the @mode is ored with %GAVL_FCMP, result of last compare
 105  *      is returned.
 106  */
 107 int
 108 gavl_search_node(const gavl_root_t *root, const void *key,
 109                  int mode, gavl_node_t **nodep)
 110 {
 111   int cmp=1;
 112   gavl_node_t *n, *p;
 113   n=p=root->root_node;
 114   while(n){
 115     p=n;
 116     /*If external int than equivalent to cmp=*(int*)(n)-*(int*)key;*/
 117     cmp=root->cmp_fnc(gavl_node2key(root,n),key);
 118     if(cmp>0){
 119       n=n->left;
 120     }else if((cmp<0)||(mode&GAVL_FAFTER)){
 121       n=n->right;
 122     }else{
 123       break;
 124     }
 125   }
 126   if(mode&GAVL_FAFTER){
 127     if(cmp<=0)
 128       if(p) p=gavl_next_node(p);
 129     *nodep=p;
 130     return p!=NULL;
 131   }
 132   if(cmp&&!(mode&GAVL_FCMP)){
 133     *nodep=0;
 134     return 0;
 135   }
 136   if(mode&GAVL_FFIRST){
 137     while((n=p->left)){
 138       cmp=root->cmp_fnc(gavl_node2key(root,n),key);
 139       if(!cmp){
 140         p=n;
 141       }else{
 142         while((n=n->right)){
 143           cmp=root->cmp_fnc(gavl_node2key(root,n),key);
 144           if(!cmp){
 145             p=n;
 146             break;
 147           }
 148         }
 149         if(cmp) break;
 150       }
 151     }
 152     cmp=0;
 153   }
 154   *nodep=p;
 155   return (mode&GAVL_FCMP)?cmp:1;
 156 }
 157
 158 /**
 159  * gavl_find - Find Item for Provided Key
 160  * @root:       GAVL tree root
 161  * @key:        key value searched for
 162  *
 163  * Return Value: pointer to item associated to key value.
 164  */
 165 void *
 166 gavl_find(const gavl_root_t *root, const void *key)
 167 {
 168   gavl_node_t *n;
 169   int ret;
 170   ret=gavl_search_node(root, key, GAVL_FANY, &n);
 171   if(!ret) return NULL;
 172   return gavl_node2item(root,n);
 173 }
 174
 175 /**
 176  * gavl_find_first - Find the First Item with Provided Key Value
 177  * @root:       GAVL tree root
 178  * @key:        key value searched for
 179  *
 180  * same as above, but first matching item is found.
 181  * Return Value: pointer to the first item associated to key value.
 182  */
 183 void *
 184 gavl_find_first(const gavl_root_t *root, const void *key)
 185 {
 186   gavl_node_t *n;
 187   n=gavl_find_first_node(root, key);
 188   return n?gavl_node2item(root,n):NULL;
 189 }
 190
 191 /**
 192  * gavl_find_after - Find the First Item with Higher Key Value
 193  * @root:       GAVL tree root
 194  * @key:        key value searched for
 195  *
 196  * same as above, but points to item with first key value above searched @key.
 197  * Return Value: pointer to the first item associated to key value.
 198  */
 199 void *
 200 gavl_find_after(const gavl_root_t *root, const void *key)
 201 {
 202   gavl_node_t *n;
 203   n=gavl_find_after_node(root, key);
 204   return n?gavl_node2item(root,n):NULL;
 205 }
 206
 207 /**
 208  * gavl_insert_node_at - Insert Existing Node to Already Computed Place into GAVL Tree
 209  * @root:       GAVL tree root
 210  * @node:       pointer to inserted node
 211  * @where:      pointer to found parent node
 212  * @leftright:  left (1) or right (0) branch
 213  *
 214  * Return Value: positive value informs about success
 215  */
 216 int
 217 gavl_insert_node_at(gavl_root_t *root, gavl_node_t *node,
 218                     gavl_node_t *where, int leftright)
 219 {
 220   return gavl_insert_primitive_at(&root->root_node, node, where, leftright);
 221 }
 222
 223 /**
 224  * gavl_insert_node - Insert Existing Node into GAVL Tree
 225  * @root:       GAVL tree root
 226  * @node:       pointer to inserted node
 227  * @mode:       if mode is %GAVL_FAFTER, multiple items with same key can
 228  *              be used, else strict ordering is required
 229  *
 230  * Return Value: positive value informs about success
 231  */
 232 int
 233 gavl_insert_node(gavl_root_t *root, gavl_node_t *node, int mode)
 234 {
 235   int cmp;
 236   gavl_node_t *where;
 237
 238   cmp=gavl_search_node(root, gavl_node2key(root, node),
 239                         (mode|GAVL_FCMP), &where);
 240   if((mode!=GAVL_FAFTER) && !cmp) return -1;
 241   /*return gavl_insert_node_at(root, node, where, cmp);*/
 242   /* insert_primitive called directly for speedup */
 243   return gavl_insert_primitive_at(&root->root_node, node, where, cmp);
 244 }
 245
 246 /**
 247  * gavl_insert - Insert New Item into GAVL Tree
 248  * @root:       GAVL tree root
 249  * @item:       pointer to inserted item
 250  * @mode:       if mode is GAVL_FAFTER, multiple items with same key can
 251  *              be used, else strict ordering is required
 252  *
 253  * Return Value: positive value informs about success, negative
 254  *      value indicates malloc fail or attempt to insert item
 255  *      with already defined key.
 256  */
 257 int
 258 gavl_insert(gavl_root_t *root, void *item, int mode)
 259 {
 260   int cmp;
 261   gavl_node_t *where, *n2add;
 262
 263   cmp=gavl_search_node(root, (char*)item+root->key_offs,
 264                         (mode|GAVL_FCMP), &where);
 265   if((mode!=GAVL_FAFTER) && !cmp) return -1;
 266   if(root->node_offs<0){
 267     n2add=MALLOC(sizeof(gavl_node_t)+sizeof(void*));
 268     if(!n2add) return -1;
 269     *(void**)(n2add+1)=item;
 270   } else {
 271     n2add=(gavl_node_t*)((char*)item+root->node_offs);
 272   }
 273   /*return gavl_insert_node_at(root, n2add, where, cmp);*/
 274   /* insert_primitive called directly for speedup */
 275   return gavl_insert_primitive_at(&root->root_node, n2add, where, cmp);
 276 }
 277
 278 /**
 279  * gavl_delete_node - Deletes/Unlinks Node from GAVL Tree
 280  * @root:       GAVL tree root
 281  * @node:       pointer to deleted node
 282  *
 283  * Return Value: positive value informs about success.
 284  */
 285 int
 286 gavl_delete_node(gavl_root_t *root, gavl_node_t *node)
 287 {
 288   return gavl_delete_primitive(&root->root_node, node);
 289 }
 290
 291 /**
 292  * gavl_delete - Delete/Unlink Item from GAVL Tree
 293  * @root:       GAVL tree root
 294  * @item:       pointer to deleted item
 295  *
 296  * Return Value: positive value informs about success, negative
 297  *      value indicates that item is not found in tree defined by root
 298  */
 299 int
 300 gavl_delete(gavl_root_t *root, void *item)
 301 {
 302   int ret;
 303   gavl_node_t *n, *p;
 304   if(!item) return -1;
 305   if(root->node_offs>=0){
 306     n=(gavl_node_t*)((char*)item+root->node_offs);
 307     for(p=n; p->parent; p=p->parent);
 308     if(p!=root->root_node)
 309       return -1;
 310   } else {
 311     if(!gavl_search_node(root, (char*)item+root->key_offs, GAVL_FFIRST, &n))
 312       return -1;
 313     while(gavl_node2item(root,n)!=item){
 314       n=gavl_next_node(n);
 315       if(!n) return -1;
 316       if(root->cmp_fnc(gavl_node2key(root,n),(char*)item+root->key_offs))
 317         return -1;
 318     }
 319   }
 320   /*ret=gavl_delete_node(root, n);*/
 321   /* delete_primitive called directly for speedup */
 322   ret=gavl_delete_primitive(&root->root_node, n);
 323   if(root->node_offs<0)
 324     FREE(n);
 325   return ret;
 326 }
 327
 328 /**
 329  * gavl_delete_and_next_node - Delete/Unlink Item from GAVL Tree
 330  * @root:       GAVL tree root
 331  * @node:       pointer to actual node which is unlinked from tree
 332  *              after function call, it can be unalocated or reused
 333  *              by application code after this call.
 334  *
 335  * This function can be used after call gavl_first_node() for destructive
 336  * traversal through the tree, it cannot be combined with gavl_next_node()
 337  * or gavl_prev_node() and root is emptied after the end of traversal.
 338  * If the tree is used after unsuccessful/unfinished traversal, it
 339  * must be balanced again. The height differences are inconsistent in other
 340  * case. If traversal could be interrupted, the function gavl_cut_first()
 341  * could be better choice.
 342  * Return Value: pointer to next node or NULL, when all nodes are deleted
 343  */
 344 gavl_node_t *
 345 gavl_delete_and_next_node(gavl_root_t *root, gavl_node_t *node)
 346 {
 347   gavl_node_t *n, **np;
 348   if(!node) node=gavl_first_node(root);
 349   /* We are in big troubles if there is left child, somebody misused
 350      this function => stop an pray, something bad happens in future */
 351   if(node->left) return NULL;
 352   if((n=node->parent)){
 353     if(n->left==node) np=&n->left;
 354     else np=&n->right;
 355   } else if(node==root->root_node) {
 356     np=&root->root_node;
 357   }else {
 358     /* Cross tree arguments or corrupted tree */
 359     return NULL;
 360   }
 361   if((n=node->right)){
 362     *np=n;
 363     n->parent=node->parent;
 364     while(n->left) n=n->left;
 365   } else {
 366     if(!node->parent){
 367       *np=NULL;
 368       return NULL;
 369     }
 370     /* Again, this cannot happen */
 371     if(node->parent->left!=node) return NULL;
 372     *np=NULL;
 373     n=node->parent;
 374   }
 375   node->left=node->right=NULL;
 376   node->parent=NULL;
 377   return n;
 378 }
 379
 380 /*===========================================================*/
 381 /* basic types compare functions */
 382
 383 int gavl_cmp_int(const void *a, const void *b)
 384 {
 385   if (*(int*)a>*(int*)b) return 1;
 386   if (*(int*)a<*(int*)b) return -1;
 387   return 0;
 388 }
 389
 390 int gavl_cmp_long(const void *a, const void *b)
 391 {
 392   if (*(long*)a>*(long*)b) return 1;
 393   if (*(long*)a<*(long*)b) return -1;
 394   return 0;
 395 }
 396
 397 int gavl_cmp_ptr(const void *a, const void *b)
 398 {
 399   if (*(void**)a>*(void**)b) return 1;
 400   if (*(void**)a<*(void**)b) return -1;
 401   return 0;
 402 }
 403
 404 /*===========================================================*/
 405 /* support for unbalanced trees */
 406
 407 #ifdef GAVL_UNBALANCED_SUPPORT
 408
 409 int
 410 gavl_adjust_hdiff(gavl_node_t *node, int adj)
 411 {
 412   gavl_node_t *p;
 413   int hdiff;
 414   while((p=node->parent)&&adj){
 415     if(p->left==node){
 416       hdiff=p->hdiff;
 417       /*printf("L%d ",adj);*/
 418       p->hdiff=hdiff+adj;
 419       if(adj>0){
 420         if(hdiff<0)
 421           if((adj+=hdiff)<=0) break;
 422       }else{
 423         if(hdiff<=0) break;
 424         if(adj<-hdiff) adj=-hdiff;
 425       }
 426     }else{
 427       hdiff=p->hdiff;
 428       p->hdiff=hdiff-adj;
 429       /*printf("R%d ",adj);*/
 430       if(adj>0){
 431         if(hdiff>0)
 432           if((adj-=hdiff)<=0) break;
 433       }else{
 434         if(hdiff>=0) break;
 435         if(adj<hdiff) adj=hdiff;
 436       }
 437     }
 438     node=p;
 439   }
 440   return adj;
 441 }
 442
 443 /* Partial balance - reduces number of nodes with hdiff >1 or <-1 */
 444 int
 445 gavl_balance_enhance(gavl_node_t **subtree)
 446 {
 447   gavl_node_t *n, *p;
 448   int ret=0;
 449   if(!*subtree) return 0;
 450   p=*subtree;
 451   while(p->left) p=p->left;
 452   do{
 453     if((n=p->right)){
 454       while(n->left) n=n->left;
 455       p=n;
 456     } else {
 457       while(p){
 458         n=p->parent;
 459         if(!n || (p==*subtree)){
 460           if((p->hdiff>1)||((p->hdiff<-1))){
 461             gavl_balance_one(subtree);
 462             ret=1;
 463           }
 464           break;
 465         }
 466         if(n->right!=p){
 467           if((p->hdiff>1)||((p->hdiff<-1))){
 468             if(gavl_balance_one(&n->left))
 469               gavl_adjust_hdiff(n->left,-1);
 470             ret=1;
 471           }
 472           break;
 473         }
 474         if((p->hdiff>1)||((p->hdiff<-1))){
 475           if(gavl_balance_one(&n->right))
 476             gavl_adjust_hdiff(n->right,-1);
 477           ret=1;
 478         }
 479         p=n;
 480       }
 481       p=n;
 482     }
 483   } while(p);
 484   return ret;
 485 }
 486
 487 /* Full tree balance */
 488 int
 489 gavl_balance(gavl_root_t *root)
 490 {
 491   int height=0;
 492   gavl_node_t *n1,*n2;
 493   gavl_node_t *s=NULL;
 494   gavl_node_t **np;
 495   if(!root->root_node) return 0;
 496   for(n1=gavl_first_node(root);n1;n1=n2){
 497     n2=gavl_delete_and_next_node(root, n1);
 498     if(!s){
 499       s=n1; height=1;
 500       n1->hdiff=1;
 501     } else {
 502       for(;;) {
 503         if(s->left && !s->right){
 504           s->right=n1; n1->parent=s;
 505           s=n1; height--;
 506           n1->hdiff=1;
 507           break;
 508         } else if(!s->parent || (s->parent->hdiff>s->hdiff+1)){
 509           n1->left=s;
 510           n1->parent=s->parent;
 511           if(s->parent) s->parent->right=n1;
 512           s->parent=n1;
 513           n1->hdiff=s->hdiff+1;
 514           s=n1;
 515           break;
 516         }
 517         height++;
 518         if(s->parent->hdiff<s->hdiff+1) s->parent->hdiff=s->hdiff+1;
 519         s=s->parent;
 520       }
 521     }
 522   }
 523   while(s->parent){
 524     height++;
 525     if(s->parent->hdiff<s->hdiff+1) s->parent->hdiff=s->hdiff+1;
 526     s=s->parent;
 527   }
 528   root->root_node=s;
 529   for(n1=s;n1;){
 530     if(!n1->right) n1->hdiff=0;
 531     else n1->hdiff=-n1->right->hdiff;
 532     if(n1->left){
 533       n1->hdiff+=n1->left->hdiff;
 534       n1=n1->left;
 535     }else{
 536       n2=n1->right;
 537       do{
 538         if(n2){ n1=n2; break;}
 539         n2=n1;
 540         n1=n1->parent;
 541         if(!n1) np=&s;
 542         else{
 543           if(n1->left==n2) {np=&n1->left; n2=n1->right;}
 544           else {np=&n1->right; n2=NULL;}
 545         }
 546       }while(n1);
 547     }
 548   }
 549   {
 550     int adj,hdiff, balfl;
 551     do{
 552       for(n1=s;n1->right;n1=n1->right);
 553       adj=0;
 554       balfl=0;
 555       do{
 556         n1=n1->parent;
 557         if(n1) np=&n1->right;
 558         else np=&s;
 559         hdiff=(*np)->hdiff;
 560         (*np)->hdiff+=adj;
 561         if(hdiff<0){
 562           if(adj>-hdiff) adj=-hdiff;
 563         }else adj=0;
 564         while((*np)->hdiff>1){
 565           if(gavl_balance_one(np))
 566             adj++;
 567           balfl=1;
 568         }
 569       }while(n1);
 570     }while(balfl);
 571   }
 572   root->root_node=s;
 573   return 1;
 574 }
 575
 576 /**
 577  * gavl_cut_first - Cut First Item from Tree
 578  * @root:       GAVL tree root
 579  *
 580  * This enables fast delete of the first item without tree balancing.
 581  * The resulting tree is degraded but height differences are kept consistent.
 582  * Use of this function can result in height of tree maximally one greater
 583  * the tree managed by optimal AVL functions.
 584  * Return Value: returns the first item or NULL if the tree is empty
 585  */
 586 void *
 587 gavl_cut_first(gavl_root_t *root)
 588 {
 589   gavl_node_t *n;
 590   void *item;
 591   if(!(n=gavl_cut_first_primitive(&root->root_node)))
 592     return NULL;
 593   item=gavl_node2item(root,n);
 594   if(root->node_offs<0)
 595     FREE(n);
 596   return item;
 597 }
 598
 599 #endif /*GAVL_UNBALANCED_SUPPORT*/
 600