2 * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
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:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
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
27 #include "smatch_slist.h"
29 static AvlNode
*mkNode(const struct sm_state
*sm
);
30 static void freeNode(AvlNode
*node
);
32 static AvlNode
*lookup(const struct stree
*avl
, AvlNode
*node
, const struct sm_state
*sm
);
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
);
38 static int sway(AvlNode
**p
, int sway
);
39 static void balance(AvlNode
**p
, int side
);
41 static bool checkBalances(AvlNode
*node
, int *height
);
42 static bool checkOrder(struct stree
*avl
);
43 static size_t countNode(AvlNode
*node
);
46 * Utility macros for converting between
47 * "balance" values (-1 or 1) and "side" values (0 or 1).
54 #define bal(side) ((side) == 0 ? -1 : 1)
55 #define side(bal) ((bal) == 1 ? 1 : 0)
57 static int sign(int cmp
)
66 struct stree
*avl_new(void)
68 struct stree
*avl
= malloc(sizeof(*avl
));
78 void free_stree(struct stree
**avl
)
81 freeNode((*avl
)->root
);
87 struct sm_state
*avl_lookup(const struct stree
*avl
, const struct sm_state
*sm
)
93 found
= lookup(avl
, avl
->root
, sm
);
96 return (struct sm_state
*)found
->sm
;
99 AvlNode
*avl_lookup_node(const struct stree
*avl
, const struct sm_state
*sm
)
101 return lookup(avl
, avl
->root
, sm
);
104 size_t stree_count(const struct stree
*avl
)
111 bool avl_insert(struct stree
**avl
, const struct sm_state
*sm
)
117 old_count
= (*avl
)->count
;
118 insert_sm(*avl
, &(*avl
)->root
, sm
);
119 return (*avl
)->count
!= old_count
;
122 bool avl_remove(struct stree
**avl
, const struct sm_state
*sm
)
124 AvlNode
*node
= NULL
;
129 remove_sm(*avl
, &(*avl
)->root
, sm
, &node
);
131 if ((*avl
)->count
== 0)
142 static AvlNode
*mkNode(const struct sm_state
*sm
)
144 AvlNode
*node
= malloc(sizeof(*node
));
146 assert(node
!= NULL
);
155 static void freeNode(AvlNode
*node
)
158 freeNode(node
->lr
[0]);
159 freeNode(node
->lr
[1]);
164 static AvlNode
*lookup(const struct stree
*avl
, AvlNode
*node
, const struct sm_state
*sm
)
171 cmp
= cmp_tracker(sm
, node
->sm
);
174 return lookup(avl
, node
->lr
[0], sm
);
176 return lookup(avl
, node
->lr
[1], sm
);
181 * Insert an sm into a subtree, rebalancing if necessary.
183 * Return true if the subtree's height increased.
185 static bool insert_sm(struct stree
*avl
, AvlNode
**p
, const struct sm_state
*sm
)
193 int cmp
= sign(cmp_tracker(sm
, node
->sm
));
200 if (!insert_sm(avl
, &node
->lr
[side(cmp
)], sm
))
203 /* If tree's balance became -1 or 1, it means the tree's height grew due to insertion. */
204 return sway(p
, cmp
) != 0;
209 * Remove the node matching the given sm.
210 * If present, return the removed node through *ret .
211 * The returned node's lr and balance are meaningless.
213 * Return true if the subtree's height decreased.
215 static bool remove_sm(struct stree
*avl
, AvlNode
**p
, const struct sm_state
*sm
, AvlNode
**ret
)
217 if (p
== NULL
|| *p
== NULL
) {
221 int cmp
= sign(cmp_tracker(sm
, node
->sm
));
227 if (node
->lr
[0] != NULL
&& node
->lr
[1] != NULL
) {
228 AvlNode
*replacement
;
232 /* Pick a subtree to pull the replacement from such that
233 * this node doesn't have to be rebalanced. */
234 side
= node
->balance
<= 0 ? 0 : 1;
236 shrunk
= removeExtremum(&node
->lr
[side
], 1 - side
, &replacement
);
238 replacement
->lr
[0] = node
->lr
[0];
239 replacement
->lr
[1] = node
->lr
[1];
240 replacement
->balance
= node
->balance
;
246 replacement
->balance
-= bal(side
);
248 /* If tree's balance became 0, it means the tree's height shrank due to removal. */
249 return replacement
->balance
== 0;
252 if (node
->lr
[0] != NULL
)
260 if (!remove_sm(avl
, &node
->lr
[side(cmp
)], sm
, ret
))
263 /* If tree's balance became 0, it means the tree's height shrank due to removal. */
264 return sway(p
, -cmp
) == 0;
270 * Remove either the left-most (if side == 0) or right-most (if side == 1)
271 * node in a subtree, returning the removed node through *ret .
272 * The returned node's lr and balance are meaningless.
274 * The subtree must not be empty (i.e. *p must not be NULL).
276 * Return true if the subtree's height decreased.
278 static bool removeExtremum(AvlNode
**p
, int side
, AvlNode
**ret
)
282 if (node
->lr
[side
] == NULL
) {
284 *p
= node
->lr
[1 - side
];
288 if (!removeExtremum(&node
->lr
[side
], side
, ret
))
291 /* If tree's balance became 0, it means the tree's height shrank due to removal. */
292 return sway(p
, -bal(side
)) == 0;
296 * Rebalance a node if necessary. Think of this function
297 * as a higher-level interface to balance().
299 * sway must be either -1 or 1, and indicates what was added to
300 * the balance of this node by a prior operation.
302 * Return the new balance of the subtree.
304 static int sway(AvlNode
**p
, int sway
)
306 if ((*p
)->balance
!= sway
)
307 (*p
)->balance
+= sway
;
309 balance(p
, side(sway
));
311 return (*p
)->balance
;
315 * Perform tree rotations on an unbalanced node.
317 * side == 0 means the node's balance is -2 .
318 * side == 1 means the node's balance is +2 .
320 static void balance(AvlNode
**p
, int side
)
323 *child
= node
->lr
[side
];
324 int opposite
= 1 - side
;
327 if (child
->balance
!= -bal
) {
328 /* Left-left (side == 0) or right-right (side == 1) */
329 node
->lr
[side
] = child
->lr
[opposite
];
330 child
->lr
[opposite
] = node
;
333 child
->balance
-= bal
;
334 node
->balance
= -child
->balance
;
337 /* Left-right (side == 0) or right-left (side == 1) */
338 AvlNode
*grandchild
= child
->lr
[opposite
];
340 node
->lr
[side
] = grandchild
->lr
[opposite
];
341 child
->lr
[opposite
] = grandchild
->lr
[side
];
342 grandchild
->lr
[side
] = child
;
343 grandchild
->lr
[opposite
] = node
;
349 if (grandchild
->balance
== bal
)
350 node
->balance
= -bal
;
351 else if (grandchild
->balance
== -bal
)
352 child
->balance
= bal
;
354 grandchild
->balance
= 0;
359 /************************* avl_check_invariants() *************************/
361 bool avl_check_invariants(struct stree
*avl
)
365 return checkBalances(avl
->root
, &dummy
)
367 && countNode(avl
->root
) == avl
->count
;
370 static bool checkBalances(AvlNode
*node
, int *height
)
375 if (!checkBalances(node
->lr
[0], &h0
))
377 if (!checkBalances(node
->lr
[1], &h1
))
380 if (node
->balance
!= h1
- h0
|| node
->balance
< -1 || node
->balance
> 1)
383 *height
= (h0
> h1
? h0
: h1
) + 1;
391 static bool checkOrder(struct stree
*avl
)
394 const struct sm_state
*last
= NULL
;
395 bool last_set
= false;
397 avl_foreach(i
, avl
) {
398 if (last_set
&& cmp_tracker(last
, i
.sm
) >= 0)
407 static size_t countNode(AvlNode
*node
)
410 return 1 + countNode(node
->lr
[0]) + countNode(node
->lr
[1]);
416 /************************* Traversal *************************/
418 void avl_iter_begin(AvlIter
*iter
, struct stree
*avl
, AvlDirection dir
)
422 iter
->stack_index
= 0;
423 iter
->direction
= dir
;
425 if (!avl
|| !avl
->root
) {
432 while (node
->lr
[dir
] != NULL
) {
433 iter
->stack
[iter
->stack_index
++] = node
;
434 node
= node
->lr
[dir
];
437 iter
->sm
= (struct sm_state
*) node
->sm
;
441 void avl_iter_next(AvlIter
*iter
)
443 AvlNode
*node
= iter
->node
;
444 AvlDirection dir
= iter
->direction
;
449 node
= node
->lr
[1 - dir
];
451 while (node
->lr
[dir
] != NULL
) {
452 iter
->stack
[iter
->stack_index
++] = node
;
453 node
= node
->lr
[dir
];
455 } else if (iter
->stack_index
> 0) {
456 node
= iter
->stack
[--iter
->stack_index
];
464 iter
->sm
= (struct sm_state
*) node
->sm
;
467 struct stree
*clone_stree(struct stree
*orig
)
469 struct stree
*new = NULL
;
473 avl_insert(&new, i
.sm
);
478 void set_stree_id(struct stree
*stree
, int stree_id
)
480 assert(stree
->stree_id
== 0);
482 stree
->stree_id
= stree_id
;
485 int get_stree_id(struct stree
*stree
)
489 return stree
->stree_id
;