expressions: introduce compare_expression()
[smatch.git] / avl.h
blob81d80a0537cae9e4b33ebea1b4b891f749847cd4
1 /*
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
20 * THE SOFTWARE.
23 #ifndef CCAN_AVL_H
24 #define CCAN_AVL_H
26 #include <stdbool.h>
27 #include <stddef.h>
29 struct sm_state;
31 typedef struct AvlNode AvlNode;
32 typedef struct AvlIter AvlIter;
34 struct stree {
35 AvlNode *root;
36 size_t count;
37 int stree_id;
38 int references;
41 void free_stree(struct stree **avl);
42 /* Free an stree tree. */
44 struct sm_state *avl_lookup(const struct stree *avl, const struct sm_state *sm);
45 /* O(log n). Lookup a sm. Return NULL if the sm is not present. */
47 #define avl_member(avl, sm) (!!avl_lookup_node(avl, sm))
48 /* O(log n). See if a sm is present. */
50 size_t stree_count(const struct stree *avl);
51 /* O(1). Return the number of elements in the tree. */
53 bool avl_insert(struct stree **avl, const struct sm_state *sm);
55 * O(log n). Insert an sm or replace it if already present.
57 * Return false if the insertion replaced an existing sm.
60 bool avl_remove(struct stree **avl, const struct sm_state *sm);
62 * O(log n). Remove an sm (if present).
64 * Return true if it was removed.
67 bool avl_check_invariants(struct stree *avl);
68 /* For testing purposes. This function will always return true :-) */
71 /************************* Traversal *************************/
73 #define avl_foreach(iter, avl) avl_traverse(iter, avl, FORWARD)
75 * O(n). Traverse an stree tree in order.
77 * Example:
79 * AvlIter i;
81 * avl_foreach(i, avl)
82 * printf("%s -> %s\n", i.sm->name, i.sm->state->name);
85 #define FOR_EACH_SM(avl, _sm) { \
86 AvlIter _i; \
87 avl_foreach(_i, avl) { \
88 _sm = _i.sm;
90 #define END_FOR_EACH_SM(_sm) }}
92 #define FOR_EACH_MY_SM(_owner, avl, _sm) { \
93 AvlIter _i; \
94 avl_foreach(_i, avl) { \
95 _sm = _i.sm; \
96 if (_sm->owner != _owner) \
97 continue; \
99 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
100 /* O(n). Traverse an stree tree in reverse order. */
102 typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
104 struct AvlIter {
105 struct sm_state *sm;
106 AvlNode *node;
108 /* private */
109 AvlNode *stack[100];
110 int stack_index;
111 AvlDirection direction;
114 void avl_iter_begin(AvlIter *iter, struct stree *avl, AvlDirection dir);
115 void avl_iter_next(AvlIter *iter);
116 #define avl_traverse(iter, avl, direction) \
117 for (avl_iter_begin(&(iter), avl, direction); \
118 (iter).node != NULL; \
119 avl_iter_next(&iter))
122 /***************** Internal data structures ******************/
124 struct AvlNode {
125 const struct sm_state *sm;
127 AvlNode *lr[2];
128 int balance; /* -1, 0, or 1 */
131 AvlNode *avl_lookup_node(const struct stree *avl, const struct sm_state *sm);
132 /* O(log n). Lookup an stree node by sm. Return NULL if not present. */
134 struct stree *clone_stree(struct stree *orig);
136 void set_stree_id(struct stree **stree, int id);
137 int get_stree_id(struct stree *stree);
139 #endif