orte/liborte/ul_gavl.c

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