|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2017 Olaf Wintermann. All rights reserved. |
|
5 * |
|
6 * Redistribution and use in source and binary forms, with or without |
|
7 * modification, are permitted provided that the following conditions are met: |
|
8 * |
|
9 * 1. Redistributions of source code must retain the above copyright |
|
10 * notice, this list of conditions and the following disclaimer. |
|
11 * |
|
12 * 2. Redistributions in binary form must reproduce the above copyright |
|
13 * notice, this list of conditions and the following disclaimer in the |
|
14 * documentation 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 HOLDER 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 #include "ucx/avl.h" |
|
30 |
|
31 #include <limits.h> |
|
32 |
|
33 #define ptrcast(ptr) ((void*)(ptr)) |
|
34 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) |
|
35 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) |
|
36 |
|
37 static void ucx_avl_connect(UcxAVLTree *tree, |
|
38 UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { |
|
39 if (child) { |
|
40 child->parent = node; |
|
41 } |
|
42 // if child is NULL, nullkey decides if left or right pointer is cleared |
|
43 if (tree->cmpfunc( |
|
44 ptrcast(child ? child->key : nullkey), |
|
45 ptrcast(node->key), tree->userdata) > 0) { |
|
46 node->right = child; |
|
47 } else { |
|
48 node->left = child; |
|
49 } |
|
50 size_t lh = node->left ? node->left->height : 0; |
|
51 size_t rh = node->right ? node->right->height : 0; |
|
52 node->height = 1 + (lh > rh ? lh : rh); |
|
53 } |
|
54 |
|
55 #define avlheight(node) ((node) ? (node)->height : 0) |
|
56 |
|
57 static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { |
|
58 UcxAVLNode *p = l0->parent; |
|
59 UcxAVLNode *l1 = l0->left; |
|
60 if (p) { |
|
61 ucx_avl_connect(tree, p, l1, 0); |
|
62 } else { |
|
63 l1->parent = NULL; |
|
64 } |
|
65 ucx_avl_connect(tree, l0, l1->right, l1->key); |
|
66 ucx_avl_connect(tree, l1, l0, 0); |
|
67 return l1; |
|
68 } |
|
69 |
|
70 static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { |
|
71 UcxAVLNode *p = l0->parent; |
|
72 UcxAVLNode *l1 = l0->right; |
|
73 if (p) { |
|
74 ucx_avl_connect(tree, p, l1, 0); |
|
75 } else { |
|
76 l1->parent = NULL; |
|
77 } |
|
78 ucx_avl_connect(tree, l0, l1->left, l1->key); |
|
79 ucx_avl_connect(tree, l1, l0, 0); |
|
80 return l1; |
|
81 } |
|
82 |
|
83 static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { |
|
84 int lh = avlheight(n->left); |
|
85 int rh = avlheight(n->right); |
|
86 n->height = 1 + (lh > rh ? lh : rh); |
|
87 |
|
88 if (lh - rh == 2) { |
|
89 UcxAVLNode *c = n->left; |
|
90 if (avlheight(c->right) - avlheight(c->left) == 1) { |
|
91 avl_rotleft(tree, c); |
|
92 } |
|
93 n = avl_rotright(tree, n); |
|
94 } else if (rh - lh == 2) { |
|
95 UcxAVLNode *c = n->right; |
|
96 if (avlheight(c->left) - avlheight(c->right) == 1) { |
|
97 avl_rotright(tree, c); |
|
98 } |
|
99 n = avl_rotleft(tree, n); |
|
100 } |
|
101 |
|
102 if (n->parent) { |
|
103 ucx_avl_balance(tree, n->parent); |
|
104 } else { |
|
105 tree->root = n; |
|
106 } |
|
107 } |
|
108 |
|
109 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
|
110 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
|
111 } |
|
112 |
|
113 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
|
114 UcxAVLTree* tree = alloc_tree(allocator); |
|
115 if (tree) { |
|
116 tree->allocator = allocator; |
|
117 tree->cmpfunc = cmpfunc; |
|
118 tree->root = NULL; |
|
119 tree->userdata = NULL; |
|
120 } |
|
121 |
|
122 return tree; |
|
123 } |
|
124 |
|
125 static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { |
|
126 if (node) { |
|
127 ucx_avl_free_node(al, node->left); |
|
128 ucx_avl_free_node(al, node->right); |
|
129 alfree(al, node); |
|
130 } |
|
131 } |
|
132 |
|
133 void ucx_avl_free(UcxAVLTree *tree) { |
|
134 UcxAllocator *al = tree->allocator; |
|
135 ucx_avl_free_node(al, tree->root); |
|
136 alfree(al, tree); |
|
137 } |
|
138 |
|
139 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) { |
|
140 UcxAVLNode *n = tree->root; |
|
141 int cmpresult; |
|
142 while (n && (cmpresult = tree->cmpfunc( |
|
143 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
|
144 n = cmpresult > 0 ? n->right : n->left; |
|
145 } |
|
146 return n; |
|
147 } |
|
148 |
|
149 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
|
150 UcxAVLNode *n = ucx_avl_get_node(tree, key); |
|
151 return n ? n->value : NULL; |
|
152 } |
|
153 |
|
154 UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, |
|
155 distance_func dfnc, int mode) { |
|
156 UcxAVLNode *n = tree->root; |
|
157 UcxAVLNode *closest = NULL; |
|
158 |
|
159 intmax_t cmpresult; |
|
160 intmax_t closest_dist; |
|
161 closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX; |
|
162 |
|
163 while (n && (cmpresult = dfnc( |
|
164 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
|
165 if (mode == UCX_AVL_FIND_CLOSEST) { |
|
166 intmax_t dist = cmpresult; |
|
167 if (dist < 0) dist *= -1; |
|
168 if (dist < closest_dist) { |
|
169 closest_dist = dist; |
|
170 closest = n; |
|
171 } |
|
172 } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) { |
|
173 if (cmpresult > closest_dist) { |
|
174 closest_dist = cmpresult; |
|
175 closest = n; |
|
176 } |
|
177 } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) { |
|
178 if (cmpresult < closest_dist) { |
|
179 closest_dist = cmpresult; |
|
180 closest = n; |
|
181 } |
|
182 } |
|
183 n = cmpresult > 0 ? n->right : n->left; |
|
184 } |
|
185 return n ? n : closest; |
|
186 } |
|
187 |
|
188 void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, |
|
189 distance_func dfnc, int mode) { |
|
190 UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode); |
|
191 return n ? n->value : NULL; |
|
192 } |
|
193 |
|
194 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
|
195 return ucx_avl_put_s(tree, key, value, NULL); |
|
196 } |
|
197 |
|
198 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, |
|
199 void **oldvalue) { |
|
200 if (tree->root) { |
|
201 UcxAVLNode *n = tree->root; |
|
202 int cmpresult; |
|
203 while ((cmpresult = tree->cmpfunc( |
|
204 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
|
205 UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; |
|
206 if (m) { |
|
207 n = m; |
|
208 } else { |
|
209 break; |
|
210 } |
|
211 } |
|
212 |
|
213 if (cmpresult) { |
|
214 UcxAVLNode* e = alloc_node(tree->allocator); |
|
215 if (e) { |
|
216 e->key = key; e->value = value; e->height = 1; |
|
217 e->parent = e->left = e->right = NULL; |
|
218 ucx_avl_connect(tree, n, e, 0); |
|
219 ucx_avl_balance(tree, n); |
|
220 return 0; |
|
221 } else { |
|
222 return 1; |
|
223 } |
|
224 } else { |
|
225 if (oldvalue) { |
|
226 *oldvalue = n->value; |
|
227 } |
|
228 n->value = value; |
|
229 return 0; |
|
230 } |
|
231 } else { |
|
232 tree->root = alloc_node(tree->allocator); |
|
233 if (tree->root) { |
|
234 tree->root->key = key; tree->root->value = value; |
|
235 tree->root->height = 1; |
|
236 tree->root->parent = tree->root->left = tree->root->right = NULL; |
|
237 |
|
238 if (oldvalue) { |
|
239 *oldvalue = NULL; |
|
240 } |
|
241 |
|
242 return 0; |
|
243 } else { |
|
244 return 1; |
|
245 } |
|
246 } |
|
247 } |
|
248 |
|
249 int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { |
|
250 return ucx_avl_remove_s(tree, key, NULL, NULL); |
|
251 } |
|
252 |
|
253 int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) { |
|
254 return ucx_avl_remove_s(tree, node->key, NULL, NULL); |
|
255 } |
|
256 |
|
257 int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, |
|
258 intptr_t *oldkey, void **oldvalue) { |
|
259 |
|
260 UcxAVLNode *n = tree->root; |
|
261 int cmpresult; |
|
262 while (n && (cmpresult = tree->cmpfunc( |
|
263 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
|
264 n = cmpresult > 0 ? n->right : n->left; |
|
265 } |
|
266 if (n) { |
|
267 if (oldkey) { |
|
268 *oldkey = n->key; |
|
269 } |
|
270 if (oldvalue) { |
|
271 *oldvalue = n->value; |
|
272 } |
|
273 |
|
274 UcxAVLNode *p = n->parent; |
|
275 if (n->left && n->right) { |
|
276 UcxAVLNode *s = n->right; |
|
277 while (s->left) { |
|
278 s = s->left; |
|
279 } |
|
280 ucx_avl_connect(tree, s->parent, s->right, s->key); |
|
281 n->key = s->key; n->value = s->value; |
|
282 p = s->parent; |
|
283 alfree(tree->allocator, s); |
|
284 } else { |
|
285 if (p) { |
|
286 ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
|
287 } else { |
|
288 tree->root = n->right ? n->right : n->left; |
|
289 if (tree->root) { |
|
290 tree->root->parent = NULL; |
|
291 } |
|
292 } |
|
293 alfree(tree->allocator, n); |
|
294 } |
|
295 |
|
296 if (p) { |
|
297 ucx_avl_balance(tree, p); |
|
298 } |
|
299 |
|
300 return 0; |
|
301 } else { |
|
302 return 1; |
|
303 } |
|
304 } |
|
305 |
|
306 static size_t ucx_avl_countn(UcxAVLNode *node) { |
|
307 if (node) { |
|
308 return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); |
|
309 } else { |
|
310 return 0; |
|
311 } |
|
312 } |
|
313 |
|
314 size_t ucx_avl_count(UcxAVLTree *tree) { |
|
315 return ucx_avl_countn(tree->root); |
|
316 } |
|
317 |
|
318 UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) { |
|
319 if (node->left) { |
|
320 UcxAVLNode* n = node->left; |
|
321 while (n->right) { |
|
322 n = n->right; |
|
323 } |
|
324 return n; |
|
325 } else { |
|
326 UcxAVLNode* n = node; |
|
327 while (n->parent) { |
|
328 if (n->parent->right == n) { |
|
329 return n->parent; |
|
330 } else { |
|
331 n = n->parent; |
|
332 } |
|
333 } |
|
334 return NULL; |
|
335 } |
|
336 } |
|
337 |
|
338 UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) { |
|
339 if (node->right) { |
|
340 UcxAVLNode* n = node->right; |
|
341 while (n->left) { |
|
342 n = n->left; |
|
343 } |
|
344 return n; |
|
345 } else { |
|
346 UcxAVLNode* n = node; |
|
347 while (n->parent) { |
|
348 if (n->parent->left == n) { |
|
349 return n->parent; |
|
350 } else { |
|
351 n = n->parent; |
|
352 } |
|
353 } |
|
354 return NULL; |
|
355 } |
|
356 } |