-
Notifications
You must be signed in to change notification settings - Fork 14
/
avl.h
153 lines (120 loc) · 4.27 KB
/
avl.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
/*
* Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
#ifndef CCAN_AVL_H
#define CCAN_AVL_H
#include <stdbool.h>
#include <stddef.h>
struct sm_state;
typedef struct AvlNode AvlNode;
typedef struct AvlIter AvlIter;
struct stree {
AvlNode *root;
struct stree *base_stree;
char *has_states;
size_t count;
int stree_id;
int references;
};
void free_stree(struct stree **avl);
/* Free an stree tree. */
struct sm_state *avl_lookup(const struct stree *avl, const struct sm_state *sm);
/* O(log n). Lookup a sm. Return NULL if the sm is not present. */
#define avl_member(avl, sm) (!!avl_lookup_node(avl, sm))
/* O(log n). See if a sm is present. */
size_t stree_count(const struct stree *avl);
/* O(1). Return the number of elements in the tree. */
bool avl_insert(struct stree **avl, const struct sm_state *sm);
/*
* O(log n). Insert an sm or replace it if already present.
*
* Return false if the insertion replaced an existing sm.
*/
bool avl_remove(struct stree **avl, const struct sm_state *sm);
/*
* O(log n). Remove an sm (if present).
*
* Return true if it was removed.
*/
bool avl_check_invariants(struct stree *avl);
/* For testing purposes. This function will always return true :-) */
/************************* Traversal *************************/
#define avl_foreach(iter, avl) avl_traverse(iter, avl, FORWARD)
/*
* O(n). Traverse an stree tree in order.
*
* Example:
*
* AvlIter i;
*
* avl_foreach(i, avl)
* printf("%s -> %s\n", i.sm->name, i.sm->state->name);
*/
#define FOR_EACH_SM(avl, _sm) { \
AvlIter _i; \
avl_foreach(_i, avl) { \
_sm = _i.sm;
#define END_FOR_EACH_SM(_sm) }}
#define FOR_EACH_SM_SAFE(avl, _sm) { \
struct stree *_copy = clone_stree(avl); \
AvlIter _i; \
avl_foreach(_i, avl) { \
_sm = _i.sm;
#define END_FOR_EACH_SM_SAFE(_sm) } \
free_stree(&_copy); }
#define FOR_EACH_MY_SM(_owner, avl, _sm) { \
bool __has_state = has_states(avl, _owner); \
AvlIter _i; \
avl_foreach(_i, avl) { \
if (!__has_state) \
break; \
_sm = _i.sm; \
if (_sm->owner != _owner) \
continue; \
#define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
/* O(n). Traverse an stree tree in reverse order. */
typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
struct AvlIter {
struct sm_state *sm;
AvlNode *node;
/* private */
AvlNode *stack[100];
int stack_index;
AvlDirection direction;
};
void avl_iter_begin(AvlIter *iter, struct stree *avl, AvlDirection dir);
void avl_iter_next(AvlIter *iter);
#define avl_traverse(iter, avl, direction) \
for (avl_iter_begin(&(iter), avl, direction); \
(iter).node != NULL; \
avl_iter_next(&iter))
/***************** Internal data structures ******************/
struct AvlNode {
const struct sm_state *sm;
AvlNode *lr[2];
int balance; /* -1, 0, or 1 */
};
AvlNode *avl_lookup_node(const struct stree *avl, const struct sm_state *sm);
/* O(log n). Lookup an stree node by sm. Return NULL if not present. */
struct stree *clone_stree(struct stree *orig);
void set_stree_id(struct stree **stree, int id);
int get_stree_id(struct stree *stree);
#endif