1 /*
2 * librd - Rapid Development C library
3 *
4 * Copyright (c) 2012-2016, Magnus Edenhill
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29
30 /*
31 * AVL tree.
32 * Inspired by Ian Piumarta's tree.h implementation.
33 */
34
35 #ifndef _RDAVL_H_
36 #define _RDAVL_H_
37
38 #include "tinycthread.h"
39
40
41 typedef enum {
42 RD_AVL_LEFT,
43 RD_AVL_RIGHT,
44 } rd_avl_dir_t;
45
46 /**
47 * AVL tree node.
48 * Add 'rd_avl_node_t ..' as field to your element's struct and
49 * provide it as the 'field' argument in the API below.
50 */
51 typedef struct rd_avl_node_s {
52 struct rd_avl_node_s *ran_p[2]; /* RD_AVL_LEFT and RD_AVL_RIGHT */
53 int ran_height; /* Sub-tree height */
54 void *ran_elm; /* Backpointer to the containing
55 * element. This could be considered
56 * costly but is convenient for the
57 * caller: RAM is cheap,
58 * development time isn't*/
59 } rd_avl_node_t;
60
61
62
63 /**
64 * Per-AVL application-provided element comparator.
65 */
66 typedef int (*rd_avl_cmp_t) (const void *, const void *);
67
68
69 /**
70 * AVL tree
71 */
72 typedef struct rd_avl_s {
73 rd_avl_node_t *ravl_root; /* Root node */
74 rd_avl_cmp_t ravl_cmp; /* Comparator */
75 int ravl_flags; /* Flags */
76 #define RD_AVL_F_LOCKS 0x1 /* Enable thread-safeness */
77 #define RD_AVL_F_OWNER 0x2 /* internal: rd_avl_init() allocated ravl */
78 rwlock_t ravl_rwlock; /* Mutex when .._F_LOCKS is set. */
79 } rd_avl_t;
80
81
82
83
84 /**
85 *
86 *
87 * Public API
88 *
89 *
90 */
91
92 /**
93 * Insert 'elm' into AVL tree.
94 * In case of collision the previous entry is overwritten by the
95 * new one and the previous element is returned, else NULL.
96 */
97 #define RD_AVL_INSERT(ravl,elm,field) \
98 rd_avl_insert(ravl, elm, &(elm)->field)
99
100
101 /**
102 * Remove element by matching value 'elm' using compare function.
103 */
104 #define RD_AVL_REMOVE_ELM(ravl,elm) \
105 rd_avl_remove_elm(ravl, elm)
106
107 /**
108 * Search for (by value using compare function) and return matching elm.
109 */
110 #define RD_AVL_FIND(ravl,elm) \
111 rd_avl_find(ravl, elm, 1)
112
113
114 /**
115 * Search (by value using compare function) for and return matching elm.
116 * Same as RD_AVL_FIND_NL() but assumes 'ravl' ís already locked
117 * by 'rd_avl_*lock()'.
118 *
119 * NOTE: rd_avl_wrlock() must be held.
120 */
121 #define RD_AVL_FIND_NL(ravl,elm) \
122 rd_avl_find_node(ravl, (ravl)->ravl_root, elm, 0)
123
124
125 /**
126 * Search (by value using compare function) for elm and return its AVL node.
127 *
128 * NOTE: rd_avl_wrlock() must be held.
129 */
130 #define RD_AVL_FIND_NODE_NL(ravl,elm) \
131 rd_avl_find(ravl, elm, 0)
132
133
134 /**
135 * Changes the element pointer for an existing AVL node in the tree.
136 * The new element must be identical (according to the comparator)
137 * to the previous element.
138 *
139 * NOTE: rd_avl_wrlock() must be held.
140 */
141 #define RD_AVL_ELM_SET_NL(ran,elm) ((ran)->ran_elm = (elm))
142
143 /**
144 * Returns the current element pointer for an existing AVL node in the tree
145 *
146 * NOTE: rd_avl_*lock() must be held.
147 */
148 #define RD_AVL_ELM_GET_NL(ran) ((ran)->ran_elm)
149
150
151
152 /**
153 * Destroy previously initialized (by rd_avl_init()) AVL tree.
154 */
155 void rd_avl_destroy (rd_avl_t *ravl);
156
157 /**
158 * Initialize (and optionally allocate if 'ravl' is NULL) AVL tree.
159 * 'cmp' is the comparison function that takes two const pointers
160 * pointing to the elements being compared (rather than the avl_nodes).
161 * 'flags' is zero or more of the RD_AVL_F_.. flags.
162 *
163 * For thread-safe AVL trees supply RD_AVL_F_LOCKS in 'flags'.
164 */
165 rd_avl_t *rd_avl_init (rd_avl_t *ravl, rd_avl_cmp_t cmp, int flags);
166
167
168 /**
169 * 'ravl' locking functions.
170 * Locking is performed automatically for all methods except for
171 * those with the "_NL"/"_nl" suffix ("not locked") which expects
172 * either read or write lock to be held.
173 *
174 * rdavl utilizes rwlocks to allow multiple concurrent read threads.
175 */
rd_avl_rdlock(rd_avl_t * ravl)176 static RD_INLINE RD_UNUSED void rd_avl_rdlock (rd_avl_t *ravl) {
177 if (ravl->ravl_flags & RD_AVL_F_LOCKS)
178 rwlock_rdlock(&ravl->ravl_rwlock);
179 }
180
rd_avl_wrlock(rd_avl_t * ravl)181 static RD_INLINE RD_UNUSED void rd_avl_wrlock (rd_avl_t *ravl) {
182 if (ravl->ravl_flags & RD_AVL_F_LOCKS)
183 rwlock_wrlock(&ravl->ravl_rwlock);
184 }
185
rd_avl_rdunlock(rd_avl_t * ravl)186 static RD_INLINE RD_UNUSED void rd_avl_rdunlock (rd_avl_t *ravl) {
187 if (ravl->ravl_flags & RD_AVL_F_LOCKS)
188 rwlock_rdunlock(&ravl->ravl_rwlock);
189 }
190
rd_avl_wrunlock(rd_avl_t * ravl)191 static RD_INLINE RD_UNUSED void rd_avl_wrunlock (rd_avl_t *ravl) {
192 if (ravl->ravl_flags & RD_AVL_F_LOCKS)
193 rwlock_wrunlock(&ravl->ravl_rwlock);
194 }
195
196
197
198
199 /**
200 * Private API, dont use directly.
201 */
202
203 rd_avl_node_t *rd_avl_insert_node (rd_avl_t *ravl,
204 rd_avl_node_t *parent,
205 rd_avl_node_t *ran,
206 rd_avl_node_t **existing);
207
rd_avl_insert(rd_avl_t * ravl,void * elm,rd_avl_node_t * ran)208 static RD_UNUSED void *rd_avl_insert (rd_avl_t *ravl, void *elm,
209 rd_avl_node_t *ran) {
210 rd_avl_node_t *existing = NULL;
211
212 memset(ran, 0, sizeof(*ran));
213 ran->ran_elm = elm;
214
215 rd_avl_wrlock(ravl);
216 ravl->ravl_root = rd_avl_insert_node(ravl, ravl->ravl_root,
217 ran, &existing);
218 rd_avl_wrunlock(ravl);
219
220 return existing ? existing->ran_elm : NULL;
221 }
222
223 rd_avl_node_t *rd_avl_remove_elm0 (rd_avl_t *ravl, rd_avl_node_t *parent,
224 const void *elm);
225
226 static RD_INLINE RD_UNUSED
rd_avl_remove_elm(rd_avl_t * ravl,const void * elm)227 void rd_avl_remove_elm (rd_avl_t *ravl, const void *elm) {
228 rd_avl_wrlock(ravl);
229 ravl->ravl_root = rd_avl_remove_elm0(ravl, ravl->ravl_root, elm);
230 rd_avl_wrunlock(ravl);
231 }
232
233
234 rd_avl_node_t *rd_avl_find_node (const rd_avl_t *ravl,
235 const rd_avl_node_t *begin,
236 const void *elm);
237
238
rd_avl_find(rd_avl_t * ravl,const void * elm,int dolock)239 static RD_INLINE RD_UNUSED void *rd_avl_find (rd_avl_t *ravl, const void *elm,
240 int dolock) {
241 const rd_avl_node_t *ran;
242 void *ret;
243
244 if (dolock)
245 rd_avl_rdlock(ravl);
246
247 ran = rd_avl_find_node(ravl, ravl->ravl_root, elm);
248 ret = ran ? ran->ran_elm : NULL;
249
250 if (dolock)
251 rd_avl_rdunlock(ravl);
252
253 return ret;
254 }
255
256 #endif /* _RDAVL_H_ */
257