src/fcavl.c

   1 /*
   2  * $XFree86: $
   3  *
   4  * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
   5  *
   6  * Permission to use, copy, modify, distribute, and sell this software and its
   7  * documentation for any purpose is hereby granted without fee, provided that
   8  * the above copyright notice appear in all copies and that both that
   9  * copyright notice and this permission notice appear in supporting
  10  * documentation, and that the name of Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes no
  13  * representations about the suitability of this software for any purpose.  It
  14  * is provided "as is" without express or implied warranty.
  15  *
  16  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  19  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  20  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  21  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  22  * PERFORMANCE OF THIS SOFTWARE.
  23  */
  24
  25 /*
  26  * Semi-Balanced trees (avl).  This only contains two
  27  * routines - insert and delete.  Searching is
  28  * reserved for the client to write.
  29  */
  30
  31 #include        "fcint.h"
  32 #include        "fcavl.h"
  33
  34 static FcBool
  35 FcAvlRebalanceRight (FcAvlNode **);
  36
  37 static FcBool
  38 FcAvlRebalanceLeft (FcAvlNode **);
  39
  40 /*
  41  * insert a new node
  42  *
  43  * this routine returns FcTrue if the tree has grown
  44  * taller
  45  */
  46
  47 FcBool
  48 FcAvlInsert (FcAvlMore more, FcAvlNode **treep, FcAvlNode *new)
  49 {
  50     if (!(*treep))
  51     {
  52         new->left = 0;
  53         new->right = 0;
  54         new->balance = 0;
  55         *treep = new;
  56         return FcTrue;
  57     }
  58     else
  59     {
  60         if ((*more) (new, *treep))
  61         {
  62             if (FcAvlInsert (more, &(*treep)->right, new))
  63                 switch (++(*treep)->balance) {
  64                 case 0:
  65                     return FcFalse;
  66                 case 1:
  67                     return FcTrue;
  68                 case 2:
  69                     (void) FcAvlRebalanceRight (treep);
  70                 }
  71         }
  72         else
  73         {
  74             if (FcAvlInsert (more, &(*treep)->left, new))
  75                 switch (--(*treep)->balance) {
  76                 case 0:
  77                     return FcFalse;
  78                 case -1:
  79                     return FcTrue;
  80                 case -2:
  81                     (void) FcAvlRebalanceLeft (treep);
  82                 }
  83         }
  84     }
  85     return 0;
  86 }
  87
  88 /*
  89  * delete a node from a tree
  90  *
  91  * this routine return FcTrue if the tree has been shortened
  92  */
  93
  94 FcBool
  95 FcAvlDelete (FcAvlMore more, FcAvlNode **treep, FcAvlNode *old)
  96 {
  97     if (!*treep)
  98         return FcFalse; /* node not found */
  99     if (old == *treep)
 100     {
 101         FcAvlNode       *replacement;
 102         FcAvlNode       *replacement_parent;
 103         int             replacement_direction;
 104         int             delete_direction;
 105         FcAvlNode       *swap_temp;
 106         int             balance_temp;
 107
 108         /*
 109          * find an empty down pointer (if any)
 110          * and rehook the tree
 111          */
 112         if (!old->right) {
 113             (*treep) = old->left;
 114             return FcTrue;
 115         } else if (!old->left) {
 116             (*treep) = old->right;
 117             return FcTrue;
 118         } else {
 119             /*
 120              * if both down pointers are full, then
 121              * move a node from the bottom of the tree up here.
 122              *
 123              * This builds an incorrect tree -- the replacement
 124              * node and the old node will not
 125              * be in correct order.  This doesn't matter as
 126              * the old node will obviously not leave
 127              * this routine alive.
 128              */
 129             /*
 130              * if the tree is left heavy, then go left
 131              * else go right
 132              */
 133             replacement_parent = old;
 134             if (old->balance == -1) {
 135                 delete_direction = -1;
 136                 replacement_direction = -1;
 137                 replacement = old->left;
 138                 while (replacement->right) {
 139                     replacement_parent = replacement;
 140                     replacement_direction = 1;
 141                     replacement = replacement->right;
 142                 }
 143             } else {
 144                 delete_direction = 1;
 145                 replacement_direction = 1;
 146                 replacement = old->right;
 147                 while (replacement->left) {
 148                     replacement_parent = replacement;
 149                     replacement_direction = -1;
 150                     replacement = replacement->left;
 151                 }
 152             }
 153             /*
 154              * swap the replacement node into
 155              * the tree where the node is to be removed
 156              *
 157              * this would be faster if only the data
 158              * element was swapped -- but that
 159              * won't work for kalypso.  The alternate
 160              * code would be:
 161              data_temp = old->data;
 162              to _be_deleted->data = replacement->data;
 163              replacement->data = data_temp;
 164              */
 165             swap_temp = old->left;
 166             old->left = replacement->left;
 167             replacement->left = swap_temp;
 168
 169             swap_temp = old->right;
 170             old->right = replacement->right;
 171             replacement->right = swap_temp;
 172
 173             balance_temp = old->balance;
 174             old->balance = replacement->balance;
 175             replacement->balance = balance_temp;
 176             /*
 177              * if the replacement node is directly below
 178              * the to-be-removed node, hook the old
 179              * node below it (instead of below itself!)
 180              */
 181             if (replacement_parent == old)
 182                 replacement_parent = replacement;
 183             if (replacement_direction == -1)
 184                 replacement_parent->left = old;
 185             else
 186                 replacement_parent->right = old;
 187             (*treep) = replacement;
 188             /*
 189              * delete the node from the sub-tree
 190              */
 191             if (delete_direction == -1)
 192             {
 193                 if (FcAvlDelete (more, &(*treep)->left, old))
 194                 {
 195                     switch (++(*treep)->balance) {
 196                     case 2:
 197                         abort ();
 198                     case 1:
 199                         return FcFalse;
 200                     case 0:
 201                         return FcTrue;
 202                     }
 203                 }
 204                 return 0;
 205             }
 206             else
 207             {
 208                 if (FcAvlDelete (more, &(*treep)->right, old))
 209                 {
 210                     switch (--(*treep)->balance) {
 211                     case -2:
 212                         abort ();
 213                     case -1:
 214                         return FcFalse;
 215                     case 0:
 216                         return FcTrue;
 217                     }
 218                 }
 219                 return 0;
 220             }
 221         }
 222     }
 223     else if ((*more) (old, *treep))
 224     {
 225         if (FcAvlDelete (more, &(*treep)->right, old))
 226         {
 227             /*
 228              * check the balance factors
 229              * Note that the conditions are
 230              * inverted from the insertion case
 231              */
 232             switch (--(*treep)->balance) {
 233             case 0:
 234                 return FcFalse;
 235             case -1:
 236                 return FcTrue;
 237             case -2:
 238                 return FcAvlRebalanceLeft (treep);
 239             }
 240         }
 241         return 0;
 242     }
 243     else
 244     {
 245         if (FcAvlDelete (more, &(*treep)->left, old))
 246         {
 247             switch (++(*treep)->balance) {
 248             case 0:
 249                 return FcTrue;
 250             case 1:
 251                 return FcFalse;
 252             case 2:
 253                 return FcAvlRebalanceRight (treep);
 254             }
 255         }
 256         return 0;
 257     }
 258     /*NOTREACHED*/
 259 }
 260
 261 /*
 262  * two routines to rebalance the tree.
 263  *
 264  * rebalance_right -- the right sub-tree is too long
 265  * rebalance_left --  the left sub-tree is too long
 266  *
 267  * These routines are the heart of avl trees, I've tried
 268  * to make their operation reasonably clear with comments,
 269  * but some study will be necessary to understand the
 270  * algorithm.
 271  *
 272  * these routines return FcTrue if the resultant
 273  * tree is shorter than the un-balanced version.  This
 274  * is only of interest to the delete routine as the
 275  * balance after insertion can never actually shorten
 276  * the tree.
 277  */
 278
 279 static FcBool
 280 FcAvlRebalanceRight (FcAvlNode **treep)
 281 {
 282     FcAvlNode   *temp;
 283     /*
 284      * rebalance the tree
 285      */
 286     if ((*treep)->right->balance == -1) {
 287         /*
 288          * double whammy -- the inner sub-sub tree
 289          * is longer than the outer sub-sub tree
 290          *
 291          * this is the "double rotation" from
 292          * knuth.  Scheme:  replace the tree top node
 293          * with the inner sub-tree top node and
 294          * adjust the maze of pointers and balance
 295          * factors accordingly.
 296          */
 297         temp = (*treep)->right->left;
 298         (*treep)->right->left = temp->right;
 299         temp->right = (*treep)->right;
 300         switch (temp->balance) {
 301         case -1:
 302             temp->right->balance = 1;
 303             (*treep)->balance = 0;
 304             break;
 305         case 0:
 306             temp->right->balance = 0;
 307             (*treep)->balance = 0;
 308             break;
 309         case 1:
 310             temp->right->balance = 0;
 311             (*treep)->balance = -1;
 312             break;
 313         }
 314         temp->balance = 0;
 315         (*treep)->right = temp->left;
 316         temp->left = (*treep);
 317         (*treep) = temp;
 318         return FcTrue;
 319     } else {
 320         /*
 321          * a simple single rotation
 322          *
 323          * Scheme:  replace the tree top node
 324          * with the sub-tree top node
 325          */
 326         temp = (*treep)->right->left;
 327         (*treep)->right->left = (*treep);
 328         (*treep) = (*treep)->right;
 329         (*treep)->left->right = temp;
 330         /*
 331          * only two possible configurations --
 332          * if the right sub-tree was balanced, then
 333          * *both* sides of it were longer than the
 334          * left side, so the resultant tree will
 335          * have a long leg (the left inner leg being
 336                             * the same length as the right leg)
 337          */
 338         if ((*treep)->balance == 0) {
 339             (*treep)->balance = -1;
 340             (*treep)->left->balance = 1;
 341             return FcFalse;
 342         } else {
 343             (*treep)->balance = 0;
 344             (*treep)->left->balance = 0;
 345             return FcTrue;
 346         }
 347     }
 348 }
 349
 350 static FcBool
 351 FcAvlRebalanceLeft (FcAvlNode **treep)
 352 {
 353     FcAvlNode   *temp;
 354     /*
 355      * rebalance the tree
 356      */
 357     if ((*treep)->left->balance == 1) {
 358         /*
 359          * double whammy -- the inner sub-sub tree
 360          * is longer than the outer sub-sub tree
 361          *
 362          * this is the "double rotation" from
 363          * knuth.  Scheme:  replace the tree top node
 364          * with the inner sub-tree top node and
 365          * adjust the maze of pointers and balance
 366          * factors accordingly.
 367          */
 368         temp = (*treep)->left->right;
 369         (*treep)->left->right = temp->left;
 370         temp->left = (*treep)->left;
 371         switch (temp->balance) {
 372         case 1:
 373             temp->left->balance = -1;
 374             (*treep)->balance = 0;
 375             break;
 376         case 0:
 377             temp->left->balance = 0;
 378             (*treep)->balance = 0;
 379             break;
 380         case -1:
 381             temp->left->balance = 0;
 382             (*treep)->balance = 1;
 383             break;
 384         }
 385         temp->balance = 0;
 386         (*treep)->left = temp->right;
 387         temp->right = (*treep);
 388         (*treep) = temp;
 389         return FcTrue;
 390     } else {
 391         /*
 392          * a simple single rotation
 393          *
 394          * Scheme:  replace the tree top node
 395          * with the sub-tree top node
 396          */
 397         temp = (*treep)->left->right;
 398         (*treep)->left->right = (*treep);
 399         (*treep) = (*treep)->left;
 400         (*treep)->right->left = temp;
 401         /*
 402          * only two possible configurations --
 403          * if the left sub-tree was balanced, then
 404          * *both* sides of it were longer than the
 405          * right side, so the resultant tree will
 406          * have a long leg (the right inner leg being
 407          * the same length as the left leg)
 408          */
 409         if ((*treep)->balance == 0) {
 410             (*treep)->balance = 1;
 411             (*treep)->right->balance = -1;
 412             return FcTrue;
 413         } else {
 414             (*treep)->balance = 0;
 415             (*treep)->right->balance = 0;
 416             return FcFalse;
 417         }
 418     }
 419 }