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 struct stree *avl, AvlNode *node, const struct sm_state *sm); 33 34 static bool insert_sm(struct stree *avl, AvlNode **p, const struct sm_state *sm); 35 static bool remove_sm(struct stree *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(struct stree *avl); 43 static size_t countNode(AvlNode *node); 44 45 int unfree_stree; 46 47 /* 48 * Utility macros for converting between 49 * "balance" values (-1 or 1) and "side" values (0 or 1). 50 * 51 * bal(0) == -1 52 * bal(1) == +1 53 * side(-1) == 0 54 * side(+1) == 1 55 */ 56 #define bal(side) ((side) == 0 ? -1 : 1) 57 #define side(bal) ((bal) == 1 ? 1 : 0) 58 59 static struct stree *avl_new(void) 60 { 61 struct stree *avl = malloc(sizeof(*avl)); 62 63 unfree_stree++; 64 assert(avl != NULL); 65 66 avl->root = NULL; 67 avl->base_stree = NULL; 68 avl->has_states = calloc(num_checks + 1, sizeof(char)); 69 avl->count = 0; 70 avl->stree_id = 0; 71 avl->references = 1; 72 return avl; 73 } 74 75 void free_stree(struct stree **avl) 76 { 77 if (!*avl) 78 return; 79 80 assert((*avl)->references > 0); 81 82 (*avl)->references--; 83 if ((*avl)->references != 0) { 84 *avl = NULL; 85 return; 86 } 87 88 unfree_stree--; 89 90 freeNode((*avl)->root); 91 free(*avl); 92 *avl = NULL; 93 } 94 95 struct sm_state *avl_lookup(const struct stree *avl, const struct sm_state *sm) 96 { 97 AvlNode *found; 98 99 if (!avl) 100 return NULL; 101 if (sm->owner != USHRT_MAX && 102 !avl->has_states[sm->owner]) 103 return NULL; 104 found = lookup(avl, avl->root, sm); 105 if (!found) 106 return NULL; 107 return (struct sm_state *)found->sm; 108 } 109 110 AvlNode *avl_lookup_node(const struct stree *avl, const struct sm_state *sm) 111 { 112 return lookup(avl, avl->root, sm); 113 } 114 115 size_t stree_count(const struct stree *avl) 116 { 117 if (!avl) 118 return 0; 119 return avl->count; 120 } 121 122 static struct stree *clone_stree_real(struct stree *orig) 123 { 124 struct stree *new = avl_new(); 125 AvlIter i; 126 127 avl_foreach(i, orig) 128 avl_insert(&new, i.sm); 129 130 new->base_stree = orig->base_stree; 131 return new; 132 } 133 134 bool avl_insert(struct stree **avl, const struct sm_state *sm) 135 { 136 size_t old_count; 137 138 if (!*avl) 139 *avl = avl_new(); 140 if ((*avl)->references > 1) { 141 (*avl)->references--; 142 *avl = clone_stree_real(*avl); 143 } 144 old_count = (*avl)->count; 145 /* fortunately we never call get_state() on "unnull_path" */ 146 if (sm->owner != USHRT_MAX) 147 (*avl)->has_states[sm->owner] = 1; 148 insert_sm(*avl, &(*avl)->root, sm); 149 return (*avl)->count != old_count; 150 } 151 152 bool avl_remove(struct stree **avl, const struct sm_state *sm) 153 { 154 AvlNode *node = NULL; 155 156 if (!*avl) 157 return false; 158 /* it's fairly rare for smatch to call avl_remove */ 159 if ((*avl)->references > 1) { 160 (*avl)->references--; 161 *avl = clone_stree_real(*avl); 162 } 163 164 remove_sm(*avl, &(*avl)->root, sm, &node); 165 166 if ((*avl)->count == 0) 167 free_stree(avl); 168 169 if (node == NULL) { 170 return false; 171 } else { 172 free(node); 173 return true; 174 } 175 } 176 177 static AvlNode *mkNode(const struct sm_state *sm) 178 { 179 AvlNode *node = malloc(sizeof(*node)); 180 181 assert(node != NULL); 182 183 node->sm = sm; 184 node->lr[0] = NULL; 185 node->lr[1] = NULL; 186 node->balance = 0; 187 return node; 188 } 189 190 static void freeNode(AvlNode *node) 191 { 192 if (node) { 193 freeNode(node->lr[0]); 194 freeNode(node->lr[1]); 195 free(node); 196 } 197 } 198 199 static AvlNode *lookup(const struct stree *avl, AvlNode *node, const struct sm_state *sm) 200 { 201 int cmp; 202 203 if (node == NULL) 204 return NULL; 205 206 cmp = cmp_tracker(sm, node->sm); 207 208 if (cmp < 0) 209 return lookup(avl, node->lr[0], sm); 210 if (cmp > 0) 211 return lookup(avl, node->lr[1], sm); 212 return node; 213 } 214 215 /* 216 * Insert an sm into a subtree, rebalancing if necessary. 217 * 218 * Return true if the subtree's height increased. 219 */ 220 static bool insert_sm(struct stree *avl, AvlNode **p, const struct sm_state *sm) 221 { 222 if (*p == NULL) { 223 *p = mkNode(sm); 224 avl->count++; 225 return true; 226 } else { 227 AvlNode *node = *p; 228 int cmp = cmp_tracker(sm, node->sm); 229 230 if (cmp == 0) { 231 node->sm = sm; 232 return false; 233 } 234 235 if (!insert_sm(avl, &node->lr[side(cmp)], sm)) 236 return false; 237 238 /* If tree's balance became -1 or 1, it means the tree's height grew due to insertion. */ 239 return sway(p, cmp) != 0; 240 } 241 } 242 243 /* 244 * Remove the node matching the given sm. 245 * If present, return the removed node through *ret . 246 * The returned node's lr and balance are meaningless. 247 * 248 * Return true if the subtree's height decreased. 249 */ 250 static bool remove_sm(struct stree *avl, AvlNode **p, const struct sm_state *sm, AvlNode **ret) 251 { 252 if (p == NULL || *p == NULL) { 253 return false; 254 } else { 255 AvlNode *node = *p; 256 int cmp = cmp_tracker(sm, node->sm); 257 258 if (cmp == 0) { 259 *ret = node; 260 avl->count--; 261 262 if (node->lr[0] != NULL && node->lr[1] != NULL) { 263 AvlNode *replacement; 264 int side; 265 bool shrunk; 266 267 /* Pick a subtree to pull the replacement from such that 268 * this node doesn't have to be rebalanced. */ 269 side = node->balance <= 0 ? 0 : 1; 270 271 shrunk = removeExtremum(&node->lr[side], 1 - side, &replacement); 272 273 replacement->lr[0] = node->lr[0]; 274 replacement->lr[1] = node->lr[1]; 275 replacement->balance = node->balance; 276 *p = replacement; 277 278 if (!shrunk) 279 return false; 280 281 replacement->balance -= bal(side); 282 283 /* If tree's balance became 0, it means the tree's height shrank due to removal. */ 284 return replacement->balance == 0; 285 } 286 287 if (node->lr[0] != NULL) 288 *p = node->lr[0]; 289 else 290 *p = node->lr[1]; 291 292 return true; 293 294 } else { 295 if (!remove_sm(avl, &node->lr[side(cmp)], sm, ret)) 296 return false; 297 298 /* If tree's balance became 0, it means the tree's height shrank due to removal. */ 299 return sway(p, -cmp) == 0; 300 } 301 } 302 } 303 304 /* 305 * Remove either the left-most (if side == 0) or right-most (if side == 1) 306 * node in a subtree, returning the removed node through *ret . 307 * The returned node's lr and balance are meaningless. 308 * 309 * The subtree must not be empty (i.e. *p must not be NULL). 310 * 311 * Return true if the subtree's height decreased. 312 */ 313 static bool removeExtremum(AvlNode **p, int side, AvlNode **ret) 314 { 315 AvlNode *node = *p; 316 317 if (node->lr[side] == NULL) { 318 *ret = node; 319 *p = node->lr[1 - side]; 320 return true; 321 } 322 323 if (!removeExtremum(&node->lr[side], side, ret)) 324 return false; 325 326 /* If tree's balance became 0, it means the tree's height shrank due to removal. */ 327 return sway(p, -bal(side)) == 0; 328 } 329 330 /* 331 * Rebalance a node if necessary. Think of this function 332 * as a higher-level interface to balance(). 333 * 334 * sway must be either -1 or 1, and indicates what was added to 335 * the balance of this node by a prior operation. 336 * 337 * Return the new balance of the subtree. 338 */ 339 static int sway(AvlNode **p, int sway) 340 { 341 if ((*p)->balance != sway) 342 (*p)->balance += sway; 343 else 344 balance(p, side(sway)); 345 346 return (*p)->balance; 347 } 348 349 /* 350 * Perform tree rotations on an unbalanced node. 351 * 352 * side == 0 means the node's balance is -2 . 353 * side == 1 means the node's balance is +2 . 354 */ 355 static void balance(AvlNode **p, int side) 356 { 357 AvlNode *node = *p, 358 *child = node->lr[side]; 359 int opposite = 1 - side; 360 int bal = bal(side); 361 362 if (child->balance != -bal) { 363 /* Left-left (side == 0) or right-right (side == 1) */ 364 node->lr[side] = child->lr[opposite]; 365 child->lr[opposite] = node; 366 *p = child; 367 368 child->balance -= bal; 369 node->balance = -child->balance; 370 371 } else { 372 /* Left-right (side == 0) or right-left (side == 1) */ 373 AvlNode *grandchild = child->lr[opposite]; 374 375 node->lr[side] = grandchild->lr[opposite]; 376 child->lr[opposite] = grandchild->lr[side]; 377 grandchild->lr[side] = child; 378 grandchild->lr[opposite] = node; 379 *p = grandchild; 380 381 node->balance = 0; 382 child->balance = 0; 383 384 if (grandchild->balance == bal) 385 node->balance = -bal; 386 else if (grandchild->balance == -bal) 387 child->balance = bal; 388 389 grandchild->balance = 0; 390 } 391 } 392 393 394 /************************* avl_check_invariants() *************************/ 395 396 bool avl_check_invariants(struct stree *avl) 397 { 398 int dummy; 399 400 return checkBalances(avl->root, &dummy) 401 && checkOrder(avl) 402 && countNode(avl->root) == avl->count; 403 } 404 405 static bool checkBalances(AvlNode *node, int *height) 406 { 407 if (node) { 408 int h0, h1; 409 410 if (!checkBalances(node->lr[0], &h0)) 411 return false; 412 if (!checkBalances(node->lr[1], &h1)) 413 return false; 414 415 if (node->balance != h1 - h0 || node->balance < -1 || node->balance > 1) 416 return false; 417 418 *height = (h0 > h1 ? h0 : h1) + 1; 419 return true; 420 } else { 421 *height = 0; 422 return true; 423 } 424 } 425 426 static bool checkOrder(struct stree *avl) 427 { 428 AvlIter i; 429 const struct sm_state *last = NULL; 430 bool last_set = false; 431 432 avl_foreach(i, avl) { 433 if (last_set && cmp_tracker(last, i.sm) >= 0) 434 return false; 435 last = i.sm; 436 last_set = true; 437 } 438 439 return true; 440 } 441 442 static size_t countNode(AvlNode *node) 443 { 444 if (node) 445 return 1 + countNode(node->lr[0]) + countNode(node->lr[1]); 446 else 447 return 0; 448 } 449 450 451 /************************* Traversal *************************/ 452 453 void avl_iter_begin(AvlIter *iter, struct stree *avl, AvlDirection dir) 454 { 455 AvlNode *node; 456 457 iter->stack_index = 0; 458 iter->direction = dir; 459 460 if (!avl || !avl->root) { 461 iter->sm = NULL; 462 iter->node = NULL; 463 return; 464 } 465 node = avl->root; 466 467 while (node->lr[dir] != NULL) { 468 iter->stack[iter->stack_index++] = node; 469 node = node->lr[dir]; 470 } 471 472 iter->sm = (struct sm_state *) node->sm; 473 iter->node = node; 474 } 475 476 void avl_iter_next(AvlIter *iter) 477 { 478 AvlNode *node = iter->node; 479 AvlDirection dir = iter->direction; 480 481 if (node == NULL) 482 return; 483 484 node = node->lr[1 - dir]; 485 if (node != NULL) { 486 while (node->lr[dir] != NULL) { 487 iter->stack[iter->stack_index++] = node; 488 node = node->lr[dir]; 489 } 490 } else if (iter->stack_index > 0) { 491 node = iter->stack[--iter->stack_index]; 492 } else { 493 iter->sm = NULL; 494 iter->node = NULL; 495 return; 496 } 497 498 iter->node = node; 499 iter->sm = (struct sm_state *) node->sm; 500 } 501 502 struct stree *clone_stree(struct stree *orig) 503 { 504 if (!orig) 505 return NULL; 506 507 orig->references++; 508 return orig; 509 } 510 511 void set_stree_id(struct stree **stree, int stree_id) 512 { 513 if ((*stree)->stree_id != 0) 514 *stree = clone_stree_real(*stree); 515 516 (*stree)->stree_id = stree_id; 517 } 518 519 int get_stree_id(struct stree *stree) 520 { 521 if (!stree) 522 return -1; 523 return stree->stree_id; 524 } 525