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 AVL
*avl
, AvlNode
*node
, const struct sm_state
*sm
);
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
);
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(AVL
*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
)
68 AVL
*avl
= malloc(sizeof(*avl
));
77 void avl_free(AVL
**avl
)
79 freeNode((*avl
)->root
);
84 struct sm_state
*avl_lookup(const AVL
*avl
, const struct sm_state
*sm
)
86 AvlNode
*found
= lookup(avl
, avl
->root
, sm
);
87 return found
? (struct sm_state
*) found
->sm
: NULL
;
90 AvlNode
*avl_lookup_node(const AVL
*avl
, const struct sm_state
*sm
)
92 return lookup(avl
, avl
->root
, sm
);
95 size_t avl_count(const AVL
*avl
)
100 bool avl_insert(AVL
**avl
, const struct sm_state
*sm
)
106 old_count
= (*avl
)->count
;
107 insert_sm(*avl
, &(*avl
)->root
, sm
);
108 return (*avl
)->count
!= old_count
;
111 bool avl_remove(AVL
**avl
, const struct sm_state
*sm
)
113 AvlNode
*node
= NULL
;
115 remove_sm(*avl
, &(*avl
)->root
, sm
, &node
);
117 if ((*avl
)->count
== 0)
128 static AvlNode
*mkNode(const struct sm_state
*sm
)
130 AvlNode
*node
= malloc(sizeof(*node
));
132 assert(node
!= NULL
);
141 static void freeNode(AvlNode
*node
)
144 freeNode(node
->lr
[0]);
145 freeNode(node
->lr
[1]);
150 static AvlNode
*lookup(const AVL
*avl
, AvlNode
*node
, const struct sm_state
*sm
)
157 cmp
= cmp_tracker(sm
, node
->sm
);
160 return lookup(avl
, node
->lr
[0], sm
);
162 return lookup(avl
, node
->lr
[1], sm
);
167 * Insert an sm into a subtree, rebalancing if necessary.
169 * Return true if the subtree's height increased.
171 static bool insert_sm(AVL
*avl
, AvlNode
**p
, const struct sm_state
*sm
)
179 int cmp
= sign(cmp_tracker(sm
, node
->sm
));
186 if (!insert_sm(avl
, &node
->lr
[side(cmp
)], sm
))
189 /* If tree's balance became -1 or 1, it means the tree's height grew due to insertion. */
190 return sway(p
, cmp
) != 0;
195 * Remove the node matching the given sm.
196 * If present, return the removed node through *ret .
197 * The returned node's lr and balance are meaningless.
199 * Return true if the subtree's height decreased.
201 static bool remove_sm(AVL
*avl
, AvlNode
**p
, const struct sm_state
*sm
, AvlNode
**ret
)
207 int cmp
= sign(cmp_tracker(sm
, node
->sm
));
213 if (node
->lr
[0] != NULL
&& node
->lr
[1] != NULL
) {
214 AvlNode
*replacement
;
218 /* Pick a subtree to pull the replacement from such that
219 * this node doesn't have to be rebalanced. */
220 side
= node
->balance
<= 0 ? 0 : 1;
222 shrunk
= removeExtremum(&node
->lr
[side
], 1 - side
, &replacement
);
224 replacement
->lr
[0] = node
->lr
[0];
225 replacement
->lr
[1] = node
->lr
[1];
226 replacement
->balance
= node
->balance
;
232 replacement
->balance
-= bal(side
);
234 /* If tree's balance became 0, it means the tree's height shrank due to removal. */
235 return replacement
->balance
== 0;
238 if (node
->lr
[0] != NULL
)
246 if (!remove_sm(avl
, &node
->lr
[side(cmp
)], sm
, ret
))
249 /* If tree's balance became 0, it means the tree's height shrank due to removal. */
250 return sway(p
, -cmp
) == 0;
256 * Remove either the left-most (if side == 0) or right-most (if side == 1)
257 * node in a subtree, returning the removed node through *ret .
258 * The returned node's lr and balance are meaningless.
260 * The subtree must not be empty (i.e. *p must not be NULL).
262 * Return true if the subtree's height decreased.
264 static bool removeExtremum(AvlNode
**p
, int side
, AvlNode
**ret
)
268 if (node
->lr
[side
] == NULL
) {
270 *p
= node
->lr
[1 - side
];
274 if (!removeExtremum(&node
->lr
[side
], side
, ret
))
277 /* If tree's balance became 0, it means the tree's height shrank due to removal. */
278 return sway(p
, -bal(side
)) == 0;
282 * Rebalance a node if necessary. Think of this function
283 * as a higher-level interface to balance().
285 * sway must be either -1 or 1, and indicates what was added to
286 * the balance of this node by a prior operation.
288 * Return the new balance of the subtree.
290 static int sway(AvlNode
**p
, int sway
)
292 if ((*p
)->balance
!= sway
)
293 (*p
)->balance
+= sway
;
295 balance(p
, side(sway
));
297 return (*p
)->balance
;
301 * Perform tree rotations on an unbalanced node.
303 * side == 0 means the node's balance is -2 .
304 * side == 1 means the node's balance is +2 .
306 static void balance(AvlNode
**p
, int side
)
309 *child
= node
->lr
[side
];
310 int opposite
= 1 - side
;
313 if (child
->balance
!= -bal
) {
314 /* Left-left (side == 0) or right-right (side == 1) */
315 node
->lr
[side
] = child
->lr
[opposite
];
316 child
->lr
[opposite
] = node
;
319 child
->balance
-= bal
;
320 node
->balance
= -child
->balance
;
323 /* Left-right (side == 0) or right-left (side == 1) */
324 AvlNode
*grandchild
= child
->lr
[opposite
];
326 node
->lr
[side
] = grandchild
->lr
[opposite
];
327 child
->lr
[opposite
] = grandchild
->lr
[side
];
328 grandchild
->lr
[side
] = child
;
329 grandchild
->lr
[opposite
] = node
;
335 if (grandchild
->balance
== bal
)
336 node
->balance
= -bal
;
337 else if (grandchild
->balance
== -bal
)
338 child
->balance
= bal
;
340 grandchild
->balance
= 0;
345 /************************* avl_check_invariants() *************************/
347 bool avl_check_invariants(AVL
*avl
)
351 return checkBalances(avl
->root
, &dummy
)
353 && countNode(avl
->root
) == avl
->count
;
356 static bool checkBalances(AvlNode
*node
, int *height
)
361 if (!checkBalances(node
->lr
[0], &h0
))
363 if (!checkBalances(node
->lr
[1], &h1
))
366 if (node
->balance
!= h1
- h0
|| node
->balance
< -1 || node
->balance
> 1)
369 *height
= (h0
> h1
? h0
: h1
) + 1;
377 static bool checkOrder(AVL
*avl
)
380 const struct sm_state
*last
= NULL
;
381 bool last_set
= false;
383 avl_foreach(i
, avl
) {
384 if (last_set
&& cmp_tracker(last
, i
.sm
) >= 0)
393 static size_t countNode(AvlNode
*node
)
396 return 1 + countNode(node
->lr
[0]) + countNode(node
->lr
[1]);
402 /************************* Traversal *************************/
404 void avl_iter_begin(AvlIter
*iter
, AVL
*avl
, AvlDirection dir
)
406 AvlNode
*node
= avl
->root
;
408 iter
->stack_index
= 0;
409 iter
->direction
= dir
;
417 while (node
->lr
[dir
] != NULL
) {
418 iter
->stack
[iter
->stack_index
++] = node
;
419 node
= node
->lr
[dir
];
422 iter
->sm
= (struct sm_state
*) node
->sm
;
426 void avl_iter_next(AvlIter
*iter
)
428 AvlNode
*node
= iter
->node
;
429 AvlDirection dir
= iter
->direction
;
434 node
= node
->lr
[1 - dir
];
436 while (node
->lr
[dir
] != NULL
) {
437 iter
->stack
[iter
->stack_index
++] = node
;
438 node
= node
->lr
[dir
];
440 } else if (iter
->stack_index
> 0) {
441 node
= iter
->stack
[--iter
->stack_index
];
449 iter
->sm
= (struct sm_state
*) node
->sm
;