orte/liborte/ul_gavlprim.c

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