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 | */ |
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 | |
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 | |
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 | |
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 | |
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 |
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 | |
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 | |