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