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