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