orte/liborte/ul_gavlprim.c

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_gavlprim.c - primitives for generic AVL tree
   5
   6   (C) Copyright 2003 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 <orte_all.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  * gavl_next_node - Returns Next Node of GAVL Tree
  39  * @node:       node for which accessor is looked for
  40  *
  41  * Return Value: pointer to next node of tree according to ordering
  42  */
  43 gavl_node_t *
  44 gavl_next_node(const gavl_node_t *node)
  45 {
  46   gavl_node_t *n;
  47   if((n=node->right)){
  48     while(n->left) n=n->left;
  49     return n;
  50   } else {
  51     while((n=node->parent)){
  52       if(n->right!=node) break;
  53       node=n;
  54     }
  55     return n;
  56   }
  57 }
  58
  59 /**
  60  * gavl_prev_node - Returns Previous Node of GAVL Tree
  61  * @node:       node for which predecessor is looked for
  62  *
  63  * Return Value: pointer to previous node of tree according to ordering
  64  */
  65 gavl_node_t *
  66 gavl_prev_node(const gavl_node_t *node)
  67 {
  68   gavl_node_t *n;
  69   if((n=node->left)){
  70     while(n->right) n=n->right;
  71     return n;
  72   } else {
  73     while((n=node->parent)){
  74       if(n->left!=node) break;
  75       node=n;
  76     }
  77     return n;
  78   }
  79 }
  80
  81 #if defined(SDCC) || defined(__SDCC)
  82 #pragma save
  83 #pragma nogcse
  84 #endif /*SDCC*/
  85 /**
  86  * gavl_balance_one - Balance One Node to Enhance Balance Factor
  87  * @subtree:    pointer to pointer to node for which balance is enhanced
  88  *
  89  * Return Value: returns nonzero value if height of subtree is lowered by one
  90  */
  91 int
  92 gavl_balance_one(gavl_node_t **subtree)
  93 {
  94   int shdiff; int ret;
  95   gavl_node_t *n, *p, *parent;
  96
  97  #ifdef GAVL_UNBALANCED_SUPPORT
  98   if(!*subtree) return 0;
  99  #endif /* GAVL_UNBALANCED_SUPPORT */
 100   parent=(*subtree)->parent;
 101   shdiff=(*subtree)->hdiff;
 102
 103   if (shdiff>1)
 104   {
 105     n=(*subtree)->left;
 106    #ifdef GAVL_UNBALANCED_SUPPORT
 107     if(!n) return 0;
 108    #endif /* GAVL_UNBALANCED_SUPPORT */
 109     if (n->hdiff>=0) {
 110       /* ds1=ds-dn-1; */
 111       /* if(ds>dn) dn1=dn-1; else dn1=ds-2; */
 112       (*subtree)->hdiff=shdiff-n->hdiff-1;
 113       ret=n->hdiff>0;
 114      #ifdef GAVL_UNBALANCED_SUPPORT
 115       if(shdiff<=n->hdiff)
 116         n->hdiff=shdiff-2;
 117       else
 118      #endif /* GAVL_UNBALANCED_SUPPORT */
 119         n->hdiff--;
 120       p=n->right;
 121       n->right=*subtree; (*subtree)->parent=n;
 122       (*subtree)->left=p; if(p) p->parent=*subtree;
 123       *subtree=n; n->parent=parent;
 124       GAVL_HDIFF_DEBUG(*subtree, 0);
 125     }else{
 126       p=n->right;
 127      #ifdef GAVL_UNBALANCED_SUPPORT
 128       if(!p) return 0;
 129      #endif /* GAVL_UNBALANCED_SUPPORT */
 130       shdiff-=2;
 131       if(p->hdiff>=0){
 132         /* ds1=ds-2-dp; dn1=dn+1; dp1=min(dp;ds-2); */
 133         (*subtree)->hdiff=shdiff-p->hdiff;
 134         n->hdiff++;
 135        #ifndef GAVL_UNBALANCED_SUPPORT
 136         p->hdiff=0;
 137        #else /* GAVL_UNBALANCED_SUPPORT */
 138         if (p->hdiff>shdiff) p->hdiff=shdiff;
 139        #endif /* GAVL_UNBALANCED_SUPPORT */
 140       }else{
 141         /* ds1=ds-2; dn1=dn+1-dp; dp1=max(dn+1;dp); */
 142         (*subtree)->hdiff=shdiff;
 143         shdiff=n->hdiff; /* shdiff reused for nhdiff */
 144         n->hdiff=shdiff+1-p->hdiff;
 145        #ifndef GAVL_UNBALANCED_SUPPORT
 146         p->hdiff=0;
 147        #else /* GAVL_UNBALANCED_SUPPORT */
 148         if (p->hdiff<=shdiff) p->hdiff=shdiff+1;
 149        #endif /* GAVL_UNBALANCED_SUPPORT */
 150       }
 151       n->right=p->left; if(p->left) p->left->parent=n;
 152       (*subtree)->left=p->right; if(p->right) p->right->parent=*subtree;
 153       p->left=n; n->parent=p;
 154       p->right=*subtree; (*subtree)->parent=p;
 155       *subtree=p; p->parent=parent;
 156       GAVL_HDIFF_DEBUG(*subtree, 0);
 157       ret=1;
 158     }
 159   }
 160   else if (shdiff<-1)
 161   {
 162     n=(*subtree)->right;
 163    #ifdef GAVL_UNBALANCED_SUPPORT
 164     if(!n) return 0;
 165    #endif /* GAVL_UNBALANCED_SUPPORT */
 166     if (n->hdiff<=0) {
 167       /* ds1=ds-dn+1; */
 168       /* if(ds<dn) dn1=dn+1; else dn1=ds+2; */
 169       (*subtree)->hdiff=shdiff-n->hdiff+1;
 170       ret=n->hdiff<0;
 171      #ifdef GAVL_UNBALANCED_SUPPORT
 172       if(shdiff>=n->hdiff)
 173         n->hdiff=shdiff+2;
 174       else
 175      #endif /* GAVL_UNBALANCED_SUPPORT */
 176         n->hdiff++;
 177       p=n->left;
 178       n->left=*subtree; (*subtree)->parent=n;
 179       (*subtree)->right=p; if(p) p->parent=*subtree;
 180       *subtree=n; n->parent=parent;
 181       GAVL_HDIFF_DEBUG(*subtree, 0);
 182     }else{
 183       p=n->left;
 184      #ifdef GAVL_UNBALANCED_SUPPORT
 185       if(!p) return 0;
 186      #endif /* GAVL_UNBALANCED_SUPPORT */
 187       shdiff+=2;
 188       if(p->hdiff<=0){
 189         /* ds1=ds+2-dp; dn1=dn-1; dp1=max(dp;ds+2); */
 190         (*subtree)->hdiff=shdiff-p->hdiff;
 191         n->hdiff--;
 192        #ifndef GAVL_UNBALANCED_SUPPORT
 193         p->hdiff=0;
 194        #else /* GAVL_UNBALANCED_SUPPORT */
 195         if (p->hdiff<shdiff) p->hdiff=shdiff;
 196        #endif /* GAVL_UNBALANCED_SUPPORT */
 197       }else{
 198         /* ds1=ds+2; dn1=dn-1-dp; dp1=min(dn-1;dp); */
 199         (*subtree)->hdiff=shdiff;
 200         shdiff=n->hdiff; /* shdiff reused for nhdiff */
 201         n->hdiff=shdiff-1-p->hdiff;
 202        #ifndef GAVL_UNBALANCED_SUPPORT
 203         p->hdiff=0;
 204        #else /* GAVL_UNBALANCED_SUPPORT */
 205         if (p->hdiff>=shdiff) p->hdiff=shdiff-1;
 206        #endif /* GAVL_UNBALANCED_SUPPORT */
 207       }
 208       n->left=p->right; if(p->right) p->right->parent=n;
 209       (*subtree)->right=p->left; if(p->left) p->left->parent=*subtree;
 210       p->right=n; n->parent=p;
 211       p->left=*subtree; (*subtree)->parent=p;
 212       *subtree=p; p->parent=parent;
 213       GAVL_HDIFF_DEBUG(*subtree, 0);
 214       ret=1;
 215     }
 216   } else ret=0;
 217
 218   /*printf("#%d",ret);*/
 219   return(ret);
 220 }
 221 #if defined(SDCC) || defined(__SDCC)
 222 #pragma restore
 223 #endif /*SDCC*/
 224
 225 /**
 226  * gavl_insert_primitive_at - Low Lewel Routine to Insert Node into Tree
 227  * @root_nodep: pointer to pointer to GAVL tree root node
 228  * @node:       pointer to inserted node
 229  * @where:      pointer to found parent node
 230  * @leftright:  left (>=1) or right (<=0) branch
 231  *
 232  * This function can be used for implementing AVL trees with custom
 233  * root definition. The value of the selected @left or @right pointer
 234  * of provided @node has to be NULL before insert operation,
 235  * i.e. node has to be end node in the selected direction.
 236  * Return Value: positive value informs about success
 237  */
 238 int
 239 gavl_insert_primitive_at(gavl_node_t **root_nodep, gavl_node_t *node,
 240                     gavl_node_t *where, int leftright)
 241 {
 242   int hdiff;
 243
 244   node->hdiff=0;
 245   node->left=node->right=0;
 246   if(!*root_nodep){
 247     node->parent=NULL;
 248     *root_nodep=node;
 249     return 1;
 250   }
 251   node->parent=where;
 252   if(leftright>0)
 253     where->left=node;  /* where->avl+=1 */
 254   else
 255     where->right=node; /* where->avl-=1 */
 256
 257   do{
 258     hdiff=where->hdiff;
 259     if(where->left==node){
 260       /* break if balance enhanced */
 261       if(where->hdiff++ <0) break;
 262     }else{
 263       /* break if balance enhanced */
 264       if(where->hdiff-- >0) break;
 265     }
 266     node=where;
 267     where=where->parent;
 268     if(hdiff){
 269       gavl_node_t **np;
 270       if(!where)
 271         np=root_nodep;
 272       else if(where->left==node)
 273         np=&where->left;
 274       else
 275         np=&where->right;
 276       /* if only balanced trees are supposed, then next operation
 277          leads to loop break for all possible cases */
 278       if(gavl_balance_one(np)) break;
 279     }
 280   } while(where);
 281
 282   return 1;
 283 }
 284
 285 /**
 286  * gavl_delete_primitive - Low Lewel Deletes/Unlinks Node from GAVL Tree
 287  * @root_nodep: pointer to pointer to GAVL tree root node
 288  * @node:       pointer to deleted node
 289  *
 290  * Return Value: positive value informs about success.
 291  */
 292 int
 293 gavl_delete_primitive(gavl_node_t  **root_nodep, gavl_node_t *node)
 294 {
 295   int bal=0;
 296   int hdiff=1;
 297   int left_fl;
 298   gavl_node_t *p, *n;
 299   gavl_node_t **np;
 300
 301   p=node->parent;
 302   if(node==*root_nodep){
 303     np=root_nodep;
 304     left_fl=0;
 305   }else if(p->left==node){
 306     np=&p->left;
 307     left_fl=1;
 308   }else{
 309     np=&p->right;
 310     left_fl=0;
 311   }
 312   if(!node->left){
 313     if(!node->right){
 314       /* No child */
 315       *np=NULL;
 316     }else{
 317       /* Right child only */
 318       *np=node->right;
 319       node->right->parent=p;
 320     }
 321   }else{
 322     if(!node->right){
 323       /* Left child only */
 324       *np=node->left;
 325       node->left->parent=p;
 326     }else{
 327       gavl_node_t *neigh;
 328       if(node->hdiff>=0){
 329         gavl_node_t **np;
 330         /* Use nearest left node for top of subtree */
 331         np=&node->left; n=*np;
 332         while(n->right) {np=&n->right; n=*np;}
 333         neigh=n;
 334         if((*np=n->left)) n->left->parent=n->parent;
 335         while(n->parent!=node){
 336           n=n->parent;
 337           if(bal){
 338             bal=0;
 339             if(!gavl_balance_one(&n->right)) {hdiff=0; break;}
 340           }
 341           if(n->hdiff++ ==0) {hdiff=0; break;}
 342           bal=(n->hdiff>0);
 343         }
 344         if(bal)
 345           if(!gavl_balance_one(&node->left)) hdiff=0;
 346
 347         neigh->hdiff=node->hdiff;
 348         if(hdiff){
 349           if(!(neigh->hdiff--)) hdiff=0;
 350         }
 351       }else{
 352         gavl_node_t **np;
 353         /* Use nearest right node for top of subtree */
 354         np=&node->right; n=*np;
 355         while(n->left) {np=&n->left; n=*np;}
 356         neigh=n;
 357         if((*np=n->right)) n->right->parent=n->parent;
 358         while(n->parent!=node){
 359           n=n->parent;
 360           if(bal){
 361             bal=0;
 362             if(!gavl_balance_one(&n->left)) {hdiff=0; break;}
 363           }
 364           if(n->hdiff-- ==0) {hdiff=0; break;}
 365           bal=(n->hdiff<0);
 366         }
 367         if(bal)
 368           if(!gavl_balance_one(&node->right)) hdiff=0;
 369
 370         neigh->hdiff=node->hdiff;
 371         if(hdiff){
 372           if(!(neigh->hdiff++)) hdiff=0;
 373         }
 374       }
 375       if((neigh->left=node->left)) neigh->left->parent=neigh;
 376       if((neigh->right=node->right)) neigh->right->parent=neigh;
 377       neigh->parent=node->parent;
 378
 379       bal=0;
 380       p=node->parent;
 381       *np=neigh;
 382     }
 383   }
 384   if(hdiff) do{
 385     if(!p){
 386       if(bal)
 387         gavl_balance_one(root_nodep);
 388       break;
 389     }else if(left_fl){
 390       if(bal)
 391         if(!gavl_balance_one(&p->left)) break;
 392       /* three cases for hdiff--
 393        * +1 ->  0 => recurse
 394        *  0 -> -1 => break
 395        * -1 -> -2 => balance and recurse
 396        */
 397       bal=p->hdiff<0;
 398       if(!p->hdiff--) break;
 399     }else{
 400       if(bal)
 401         if(!gavl_balance_one(&p->right)) break;
 402       /* three cases for hdiff++
 403        * -1 ->  0 => recurse
 404        *  0 -> +1 => break
 405        * +1 -> +2 => balance and recurse
 406        */
 407       bal=p->hdiff>0;
 408       if(!p->hdiff++) break;
 409     }
 410     n=p;
 411     p=p->parent;
 412     if(p) left_fl=(p->left==n);
 413   }while(1);
 414
 415   node->parent=node->left=node->right=NULL;
 416   return 1;
 417 }
 418
 419 #ifdef GAVL_UNBALANCED_SUPPORT
 420
 421 /**
 422  * gavl_cut_first_primitive - Low Lewel Routine to Cut First Node from Tree
 423  * @root_nodep: pointer to pointer to GAVL tree root node
 424  *
 425  * This enables fast delete of the first node without tree balancing.
 426  * The resulting tree is degraded but height differences are kept consistent.
 427  * Use of this function can result in height of tree maximally one greater
 428  * the tree managed by optimal AVL functions.
 429  * Return Value: returns the first node or NULL if the tree is empty
 430  */
 431 gavl_node_t *
 432 gavl_cut_first_primitive(gavl_node_t **root_nodep)
 433 {
 434   gavl_node_t *n, *p;
 435   gavl_node_t **np=root_nodep;
 436   if(!*np) return NULL;
 437   while((n=*np)->left)
 438     np=&(n->left);
 439   if((*np=n->right)) n->right->parent=n->parent;
 440   for(p=n->parent;p;p=p->parent)
 441     if(p->hdiff++<0) break;
 442   n->parent=n->left=n->right=NULL;
 443   return n;
 444 }
 445
 446 #endif /*GAVL_UNBALANCED_SUPPORT*/