avl.c

   1 /*
   2  * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20  * THE SOFTWARE.
  21  */
  22
  23 #include <assert.h>
  24 #include <stdlib.h>
  25
  26 #include "smatch.h"
  27 #include "smatch_slist.h"
  28
  29 static AvlNode *mkNode(const struct sm_state *sm);
  30 static void freeNode(AvlNode *node);
  31
  32 static AvlNode *lookup(const AVL *avl, AvlNode *node, const struct sm_state *sm);
  33
  34 static bool insert_sm(AVL *avl, AvlNode **p, const struct sm_state *sm);
  35 static bool remove_sm(AVL *avl, AvlNode **p, const struct sm_state *sm, AvlNode **ret);
  36 static bool removeExtremum(AvlNode **p, int side, AvlNode **ret);
  37
  38 static int sway(AvlNode **p, int sway);
  39 static void balance(AvlNode **p, int side);
  40
  41 static bool checkBalances(AvlNode *node, int *height);
  42 static bool checkOrder(AVL *avl);
  43 static size_t countNode(AvlNode *node);
  44
  45 /*
  46  * Utility macros for converting between
  47  * "balance" values (-1 or 1) and "side" values (0 or 1).
  48  *
  49  * bal(0)   == -1
  50  * bal(1)   == +1
  51  * side(-1) == 0
  52  * side(+1) == 1
  53  */
  54 #define bal(side) ((side) == 0 ? -1 : 1)
  55 #define side(bal) ((bal)  == 1 ?  1 : 0)
  56
  57 static int sign(int cmp)
  58 {
  59         if (cmp < 0)
  60                 return -1;
  61         if (cmp == 0)
  62                 return 0;
  63         return 1;
  64 }
  65
  66 AVL *avl_new(void)
  67 {
  68         AVL *avl = malloc(sizeof(*avl));
  69
  70         assert(avl != NULL);
  71
  72         avl->root = NULL;
  73         avl->count = 0;
  74         return avl;
  75 }
  76
  77 void avl_free(AVL **avl)
  78 {
  79         if (*avl) {
  80                 freeNode((*avl)->root);
  81                 free(*avl);
  82         }
  83         *avl = NULL;
  84 }
  85
  86 struct sm_state *avl_lookup(const AVL *avl, const struct sm_state *sm)
  87 {
  88         AvlNode *found;
  89
  90         if (!avl)
  91                 return NULL;
  92         found = lookup(avl, avl->root, sm);
  93         if (!found)
  94                 return NULL;
  95         return (struct sm_state *)found->sm;
  96 }
  97
  98 AvlNode *avl_lookup_node(const AVL *avl, const struct sm_state *sm)
  99 {
 100         return lookup(avl, avl->root, sm);
 101 }
 102
 103 size_t avl_count(const AVL *avl)
 104 {
 105         return avl->count;
 106 }
 107
 108 bool avl_insert(AVL **avl, const struct sm_state *sm)
 109 {
 110         size_t old_count;
 111
 112         if (!*avl)
 113                 *avl = avl_new();
 114         old_count = (*avl)->count;
 115         insert_sm(*avl, &(*avl)->root, sm);
 116         return (*avl)->count != old_count;
 117 }
 118
 119 bool avl_remove(AVL **avl, const struct sm_state *sm)
 120 {
 121         AvlNode *node = NULL;
 122
 123         if (!*avl)
 124                 return false;
 125
 126         remove_sm(*avl, &(*avl)->root, sm, &node);
 127
 128         if ((*avl)->count == 0)
 129                 avl_free(avl);
 130
 131         if (node == NULL) {
 132                 return false;
 133         } else {
 134                 free(node);
 135                 return true;
 136         }
 137 }
 138
 139 static AvlNode *mkNode(const struct sm_state *sm)
 140 {
 141         AvlNode *node = malloc(sizeof(*node));
 142
 143         assert(node != NULL);
 144
 145         node->sm = sm;
 146         node->lr[0] = NULL;
 147         node->lr[1] = NULL;
 148         node->balance = 0;
 149         return node;
 150 }
 151
 152 static void freeNode(AvlNode *node)
 153 {
 154         if (node) {
 155                 freeNode(node->lr[0]);
 156                 freeNode(node->lr[1]);
 157                 free(node);
 158         }
 159 }
 160
 161 static AvlNode *lookup(const AVL *avl, AvlNode *node, const struct sm_state *sm)
 162 {
 163         int cmp;
 164
 165         if (node == NULL)
 166                 return NULL;
 167
 168         cmp = cmp_tracker(sm, node->sm);
 169
 170         if (cmp < 0)
 171                 return lookup(avl, node->lr[0], sm);
 172         if (cmp > 0)
 173                 return lookup(avl, node->lr[1], sm);
 174         return node;
 175 }
 176
 177 /*
 178  * Insert an sm into a subtree, rebalancing if necessary.
 179  *
 180  * Return true if the subtree's height increased.
 181  */
 182 static bool insert_sm(AVL *avl, AvlNode **p, const struct sm_state *sm)
 183 {
 184         if (*p == NULL) {
 185                 *p = mkNode(sm);
 186                 avl->count++;
 187                 return true;
 188         } else {
 189                 AvlNode *node = *p;
 190                 int      cmp  = sign(cmp_tracker(sm, node->sm));
 191
 192                 if (cmp == 0) {
 193                         node->sm = sm;
 194                         return false;
 195                 }
 196
 197                 if (!insert_sm(avl, &node->lr[side(cmp)], sm))
 198                         return false;
 199
 200                 /* If tree's balance became -1 or 1, it means the tree's height grew due to insertion. */
 201                 return sway(p, cmp) != 0;
 202         }
 203 }
 204
 205 /*
 206  * Remove the node matching the given sm.
 207  * If present, return the removed node through *ret .
 208  * The returned node's lr and balance are meaningless.
 209  *
 210  * Return true if the subtree's height decreased.
 211  */
 212 static bool remove_sm(AVL *avl, AvlNode **p, const struct sm_state *sm, AvlNode **ret)
 213 {
 214         if (p == NULL || *p == NULL) {
 215                 return false;
 216         } else {
 217                 AvlNode *node = *p;
 218                 int      cmp  = sign(cmp_tracker(sm, node->sm));
 219
 220                 if (cmp == 0) {
 221                         *ret = node;
 222                         avl->count--;
 223
 224                         if (node->lr[0] != NULL && node->lr[1] != NULL) {
 225                                 AvlNode *replacement;
 226                                 int      side;
 227                                 bool     shrunk;
 228
 229                                 /* Pick a subtree to pull the replacement from such that
 230                                  * this node doesn't have to be rebalanced. */
 231                                 side = node->balance <= 0 ? 0 : 1;
 232
 233                                 shrunk = removeExtremum(&node->lr[side], 1 - side, &replacement);
 234
 235                                 replacement->lr[0]   = node->lr[0];
 236                                 replacement->lr[1]   = node->lr[1];
 237                                 replacement->balance = node->balance;
 238                                 *p = replacement;
 239
 240                                 if (!shrunk)
 241                                         return false;
 242
 243                                 replacement->balance -= bal(side);
 244
 245                                 /* If tree's balance became 0, it means the tree's height shrank due to removal. */
 246                                 return replacement->balance == 0;
 247                         }
 248
 249                         if (node->lr[0] != NULL)
 250                                 *p = node->lr[0];
 251                         else
 252                                 *p = node->lr[1];
 253
 254                         return true;
 255
 256                 } else {
 257                         if (!remove_sm(avl, &node->lr[side(cmp)], sm, ret))
 258                                 return false;
 259
 260                         /* If tree's balance became 0, it means the tree's height shrank due to removal. */
 261                         return sway(p, -cmp) == 0;
 262                 }
 263         }
 264 }
 265
 266 /*
 267  * Remove either the left-most (if side == 0) or right-most (if side == 1)
 268  * node in a subtree, returning the removed node through *ret .
 269  * The returned node's lr and balance are meaningless.
 270  *
 271  * The subtree must not be empty (i.e. *p must not be NULL).
 272  *
 273  * Return true if the subtree's height decreased.
 274  */
 275 static bool removeExtremum(AvlNode **p, int side, AvlNode **ret)
 276 {
 277         AvlNode *node = *p;
 278
 279         if (node->lr[side] == NULL) {
 280                 *ret = node;
 281                 *p = node->lr[1 - side];
 282                 return true;
 283         }
 284
 285         if (!removeExtremum(&node->lr[side], side, ret))
 286                 return false;
 287
 288         /* If tree's balance became 0, it means the tree's height shrank due to removal. */
 289         return sway(p, -bal(side)) == 0;
 290 }
 291
 292 /*
 293  * Rebalance a node if necessary.  Think of this function
 294  * as a higher-level interface to balance().
 295  *
 296  * sway must be either -1 or 1, and indicates what was added to
 297  * the balance of this node by a prior operation.
 298  *
 299  * Return the new balance of the subtree.
 300  */
 301 static int sway(AvlNode **p, int sway)
 302 {
 303         if ((*p)->balance != sway)
 304                 (*p)->balance += sway;
 305         else
 306                 balance(p, side(sway));
 307
 308         return (*p)->balance;
 309 }
 310
 311 /*
 312  * Perform tree rotations on an unbalanced node.
 313  *
 314  * side == 0 means the node's balance is -2 .
 315  * side == 1 means the node's balance is +2 .
 316  */
 317 static void balance(AvlNode **p, int side)
 318 {
 319         AvlNode  *node  = *p,
 320                  *child = node->lr[side];
 321         int opposite    = 1 - side;
 322         int bal         = bal(side);
 323
 324         if (child->balance != -bal) {
 325                 /* Left-left (side == 0) or right-right (side == 1) */
 326                 node->lr[side]      = child->lr[opposite];
 327                 child->lr[opposite] = node;
 328                 *p = child;
 329
 330                 child->balance -= bal;
 331                 node->balance = -child->balance;
 332
 333         } else {
 334                 /* Left-right (side == 0) or right-left (side == 1) */
 335                 AvlNode *grandchild = child->lr[opposite];
 336
 337                 node->lr[side]           = grandchild->lr[opposite];
 338                 child->lr[opposite]      = grandchild->lr[side];
 339                 grandchild->lr[side]     = child;
 340                 grandchild->lr[opposite] = node;
 341                 *p = grandchild;
 342
 343                 node->balance       = 0;
 344                 child->balance      = 0;
 345
 346                 if (grandchild->balance == bal)
 347                         node->balance  = -bal;
 348                 else if (grandchild->balance == -bal)
 349                         child->balance = bal;
 350
 351                 grandchild->balance = 0;
 352         }
 353 }
 354
 355
 356 /************************* avl_check_invariants() *************************/
 357
 358 bool avl_check_invariants(AVL *avl)
 359 {
 360         int    dummy;
 361
 362         return checkBalances(avl->root, &dummy)
 363             && checkOrder(avl)
 364             && countNode(avl->root) == avl->count;
 365 }
 366
 367 static bool checkBalances(AvlNode *node, int *height)
 368 {
 369         if (node) {
 370                 int h0, h1;
 371
 372                 if (!checkBalances(node->lr[0], &h0))
 373                         return false;
 374                 if (!checkBalances(node->lr[1], &h1))
 375                         return false;
 376
 377                 if (node->balance != h1 - h0 || node->balance < -1 || node->balance > 1)
 378                         return false;
 379
 380                 *height = (h0 > h1 ? h0 : h1) + 1;
 381                 return true;
 382         } else {
 383                 *height = 0;
 384                 return true;
 385         }
 386 }
 387
 388 static bool checkOrder(AVL *avl)
 389 {
 390         AvlIter     i;
 391         const struct sm_state *last = NULL;
 392         bool        last_set = false;
 393
 394         avl_foreach(i, avl) {
 395                 if (last_set && cmp_tracker(last, i.sm) >= 0)
 396                         return false;
 397                 last     = i.sm;
 398                 last_set = true;
 399         }
 400
 401         return true;
 402 }
 403
 404 static size_t countNode(AvlNode *node)
 405 {
 406         if (node)
 407                 return 1 + countNode(node->lr[0]) + countNode(node->lr[1]);
 408         else
 409                 return 0;
 410 }
 411
 412
 413 /************************* Traversal *************************/
 414
 415 void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir)
 416 {
 417         AvlNode *node;
 418
 419         iter->stack_index = 0;
 420         iter->direction   = dir;
 421
 422         if (!avl || !avl->root) {
 423                 iter->sm      = NULL;
 424                 iter->node     = NULL;
 425                 return;
 426         }
 427         node = avl->root;
 428
 429         while (node->lr[dir] != NULL) {
 430                 iter->stack[iter->stack_index++] = node;
 431                 node = node->lr[dir];
 432         }
 433
 434         iter->sm   = (struct sm_state *) node->sm;
 435         iter->node  = node;
 436 }
 437
 438 void avl_iter_next(AvlIter *iter)
 439 {
 440         AvlNode     *node = iter->node;
 441         AvlDirection dir  = iter->direction;
 442
 443         if (node == NULL)
 444                 return;
 445
 446         node = node->lr[1 - dir];
 447         if (node != NULL) {
 448                 while (node->lr[dir] != NULL) {
 449                         iter->stack[iter->stack_index++] = node;
 450                         node = node->lr[dir];
 451                 }
 452         } else if (iter->stack_index > 0) {
 453                 node = iter->stack[--iter->stack_index];
 454         } else {
 455                 iter->sm      = NULL;
 456                 iter->node     = NULL;
 457                 return;
 458         }
 459
 460         iter->node  = node;
 461         iter->sm   = (struct sm_state *) node->sm;
 462 }
 463
 464 AVL *avl_clone(AVL *orig)
 465 {
 466         AVL *new = NULL;
 467         AvlIter i;
 468
 469         avl_foreach(i, orig)
 470                 avl_insert(&new, i.sm);
 471
 472         return new;
 473 }