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