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 }