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