xref: /illumos-gate/usr/src/tools/smatch/src/avl.h (revision 1f5207b7)
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 #ifndef CCAN_AVL_H
24 #define CCAN_AVL_H
25 
26 #include <stdbool.h>
27 #include <stddef.h>
28 
29 struct sm_state;
30 
31 typedef struct AvlNode       AvlNode;
32 typedef struct AvlIter       AvlIter;
33 
34 struct stree {
35 	AvlNode    *root;
36 	struct stree *base_stree;
37 	char *has_states;
38 	size_t      count;
39 	int stree_id;
40 	int references;
41 };
42 
43 void free_stree(struct stree **avl);
44 	/* Free an stree tree. */
45 
46 struct sm_state *avl_lookup(const struct stree *avl, const struct sm_state *sm);
47 	/* O(log n). Lookup a sm.  Return NULL if the sm is not present. */
48 
49 #define avl_member(avl, sm) (!!avl_lookup_node(avl, sm))
50 	/* O(log n). See if a sm is present. */
51 
52 size_t stree_count(const struct stree *avl);
53 	/* O(1). Return the number of elements in the tree. */
54 
55 bool avl_insert(struct stree **avl, const struct sm_state *sm);
56 	/*
57 	 * O(log n). Insert an sm or replace it if already present.
58 	 *
59 	 * Return false if the insertion replaced an existing sm.
60 	 */
61 
62 bool avl_remove(struct stree **avl, const struct sm_state *sm);
63 	/*
64 	 * O(log n). Remove an sm (if present).
65 	 *
66 	 * Return true if it was removed.
67 	 */
68 
69 bool avl_check_invariants(struct stree *avl);
70 	/* For testing purposes.  This function will always return true :-) */
71 
72 
73 /************************* Traversal *************************/
74 
75 #define avl_foreach(iter, avl)         avl_traverse(iter, avl, FORWARD)
76 	/*
77 	 * O(n). Traverse an stree tree in order.
78 	 *
79 	 * Example:
80 	 *
81 	 * AvlIter i;
82 	 *
83 	 * avl_foreach(i, avl)
84 	 *     printf("%s -> %s\n", i.sm->name, i.sm->state->name);
85 	 */
86 
87 #define FOR_EACH_SM(avl, _sm) {			\
88 	AvlIter _i;				\
89 	avl_foreach(_i, avl) {			\
90 		_sm = _i.sm;
91 
92 #define END_FOR_EACH_SM(_sm) }}
93 
94 #define FOR_EACH_MY_SM(_owner, avl, _sm) {	\
95 	AvlIter _i;				\
96 	avl_foreach(_i, avl) {			\
97 		_sm = _i.sm;			\
98 		if (_sm->owner != _owner)	\
99 			continue;		\
100 
101 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
102 	/* O(n). Traverse an stree tree in reverse order. */
103 
104 typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
105 
106 struct AvlIter {
107 	struct sm_state *sm;
108 	AvlNode      *node;
109 
110 	/* private */
111 	AvlNode      *stack[100];
112 	int           stack_index;
113 	AvlDirection  direction;
114 };
115 
116 void avl_iter_begin(AvlIter *iter, struct stree *avl, AvlDirection dir);
117 void avl_iter_next(AvlIter *iter);
118 #define avl_traverse(iter, avl, direction)        \
119 	for (avl_iter_begin(&(iter), avl, direction); \
120 	     (iter).node != NULL;                     \
121 	     avl_iter_next(&iter))
122 
123 
124 /***************** Internal data structures ******************/
125 
126 struct AvlNode {
127 	const struct sm_state *sm;
128 
129 	AvlNode    *lr[2];
130 	int         balance; /* -1, 0, or 1 */
131 };
132 
133 AvlNode *avl_lookup_node(const struct stree *avl, const struct sm_state *sm);
134 	/* O(log n). Lookup an stree node by sm.  Return NULL if not present. */
135 
136 struct stree *clone_stree(struct stree *orig);
137 
138 void set_stree_id(struct stree **stree, int id);
139 int get_stree_id(struct stree *stree);
140 
141 #endif
142