|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2015 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 "avl.h" |
|
30 |
|
31 #define ptrcast(ptr) ((void*)(ptr)) |
|
32 |
|
33 static void ucx_avl_connect(UcxAVLTree *tree, |
|
34 UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { |
|
35 if (child) { |
|
36 child->parent = node; |
|
37 } |
|
38 // if child is NULL, nullkey decides if left or right pointer is cleared |
|
39 if (tree->cmpfunc( |
|
40 ptrcast(child ? child->key : nullkey), |
|
41 ptrcast(node->key), tree->userdata) > 0) { |
|
42 node->right = child; |
|
43 } else { |
|
44 node->left = child; |
|
45 } |
|
46 size_t lh = node->left ? node->left->height : 0; |
|
47 size_t rh = node->right ? node->right->height : 0; |
|
48 node->height = 1 + (lh > rh ? lh : rh); |
|
49 } |
|
50 |
|
51 #define avlheight(node) ((node) ? (node)->height : 0) |
|
52 |
|
53 static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { |
|
54 UcxAVLNode *p = l0->parent; |
|
55 UcxAVLNode *l1 = l0->left; |
|
56 if (p) { |
|
57 ucx_avl_connect(tree, p, l1, 0); |
|
58 } else { |
|
59 l1->parent = NULL; |
|
60 } |
|
61 ucx_avl_connect(tree, l0, l1->right, l1->key); |
|
62 ucx_avl_connect(tree, l1, l0, 0); |
|
63 return l1; |
|
64 } |
|
65 |
|
66 static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { |
|
67 UcxAVLNode *p = l0->parent; |
|
68 UcxAVLNode *l1 = l0->right; |
|
69 if (p) { |
|
70 ucx_avl_connect(tree, p, l1, 0); |
|
71 } else { |
|
72 l1->parent = NULL; |
|
73 } |
|
74 ucx_avl_connect(tree, l0, l1->left, l1->key); |
|
75 ucx_avl_connect(tree, l1, l0, 0); |
|
76 return l1; |
|
77 } |
|
78 |
|
79 static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { |
|
80 int lh = avlheight(n->left); |
|
81 int rh = avlheight(n->right); |
|
82 n->height = 1 + (lh > rh ? lh : rh); |
|
83 |
|
84 if (lh - rh == 2) { |
|
85 UcxAVLNode *c = n->left; |
|
86 if (avlheight(c->right) - avlheight(c->left) == 1) { |
|
87 avl_rotleft(tree, c); |
|
88 } |
|
89 n = avl_rotright(tree, n); |
|
90 } else if (rh - lh == 2) { |
|
91 UcxAVLNode *c = n->right; |
|
92 if (avlheight(c->left) - avlheight(c->right) == 1) { |
|
93 avl_rotright(tree, c); |
|
94 } |
|
95 n = avl_rotleft(tree, n); |
|
96 } |
|
97 |
|
98 if (n->parent) { |
|
99 ucx_avl_balance(tree, n->parent); |
|
100 } else { |
|
101 tree->root = n; |
|
102 } |
|
103 } |
|
104 |
|
105 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
|
106 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
|
107 } |
|
108 |
|
109 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
|
110 UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree)); |
|
111 if (tree) { |
|
112 tree->allocator = allocator; |
|
113 tree->cmpfunc = cmpfunc; |
|
114 tree->root = NULL; |
|
115 tree->userdata = NULL; |
|
116 } |
|
117 |
|
118 return tree; |
|
119 } |
|
120 |
|
121 static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { |
|
122 if (node) { |
|
123 ucx_avl_free_node(al, node->left); |
|
124 ucx_avl_free_node(al, node->right); |
|
125 alfree(al, node); |
|
126 } |
|
127 } |
|
128 |
|
129 void ucx_avl_free(UcxAVLTree *tree) { |
|
130 UcxAllocator *al = tree->allocator; |
|
131 ucx_avl_free_node(al, tree->root); |
|
132 alfree(al, tree); |
|
133 } |
|
134 |
|
135 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) { |
|
136 UcxAVLNode *n = tree->root; |
|
137 int cmpresult; |
|
138 while (n && (cmpresult = tree->cmpfunc( |
|
139 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
|
140 n = cmpresult > 0 ? n->right : n->left; |
|
141 } |
|
142 return n; |
|
143 } |
|
144 |
|
145 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
|
146 UcxAVLNode *n = ucx_avl_get_node(tree, key); |
|
147 return n ? n->value : NULL; |
|
148 } |
|
149 |
|
150 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
|
151 return ucx_avl_put_s(tree, key, value, NULL); |
|
152 } |
|
153 |
|
154 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, |
|
155 void **oldvalue) { |
|
156 if (tree->root) { |
|
157 UcxAVLNode *n = tree->root; |
|
158 int cmpresult; |
|
159 while ((cmpresult = tree->cmpfunc( |
|
160 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
|
161 UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; |
|
162 if (m) { |
|
163 n = m; |
|
164 } else { |
|
165 break; |
|
166 } |
|
167 } |
|
168 |
|
169 if (cmpresult) { |
|
170 UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
|
171 if (e) { |
|
172 e->key = key; e->value = value; e->height = 1; |
|
173 e->parent = e->left = e->right = NULL; |
|
174 ucx_avl_connect(tree, n, e, 0); |
|
175 ucx_avl_balance(tree, n); |
|
176 return 0; |
|
177 } else { |
|
178 return 1; |
|
179 } |
|
180 } else { |
|
181 if (oldvalue) { |
|
182 *oldvalue = n->value; |
|
183 } |
|
184 n->value = value; |
|
185 return 0; |
|
186 } |
|
187 } else { |
|
188 tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
|
189 if (tree->root) { |
|
190 tree->root->key = key; tree->root->value = value; |
|
191 tree->root->height = 1; |
|
192 tree->root->parent = tree->root->left = tree->root->right = NULL; |
|
193 |
|
194 if (oldvalue) { |
|
195 *oldvalue = NULL; |
|
196 } |
|
197 |
|
198 return 0; |
|
199 } else { |
|
200 return 1; |
|
201 } |
|
202 } |
|
203 } |
|
204 |
|
205 int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { |
|
206 return ucx_avl_remove_s(tree, key, NULL, NULL); |
|
207 } |
|
208 |
|
209 int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) { |
|
210 return ucx_avl_remove_s(tree, node->key, NULL, NULL); |
|
211 } |
|
212 |
|
213 int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, |
|
214 intptr_t *oldkey, void **oldvalue) { |
|
215 |
|
216 UcxAVLNode *n = tree->root; |
|
217 int cmpresult; |
|
218 while (n && (cmpresult = tree->cmpfunc( |
|
219 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
|
220 n = cmpresult > 0 ? n->right : n->left; |
|
221 } |
|
222 if (n) { |
|
223 if (oldkey) { |
|
224 *oldkey = n->key; |
|
225 } |
|
226 if (oldvalue) { |
|
227 *oldvalue = n->value; |
|
228 } |
|
229 |
|
230 UcxAVLNode *p = n->parent; |
|
231 if (n->left && n->right) { |
|
232 UcxAVLNode *s = n->right; |
|
233 while (s->left) { |
|
234 s = s->left; |
|
235 } |
|
236 ucx_avl_connect(tree, s->parent, s->right, s->key); |
|
237 n->key = s->key; n->value = s->value; |
|
238 p = s->parent; |
|
239 alfree(tree->allocator, s); |
|
240 } else { |
|
241 if (p) { |
|
242 ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
|
243 } else { |
|
244 tree->root = n->right ? n->right : n->left; |
|
245 if (tree->root) { |
|
246 tree->root->parent = NULL; |
|
247 } |
|
248 } |
|
249 alfree(tree->allocator, n); |
|
250 } |
|
251 |
|
252 if (p) { |
|
253 ucx_avl_balance(tree, p); |
|
254 } |
|
255 |
|
256 return 0; |
|
257 } else { |
|
258 return 1; |
|
259 } |
|
260 } |
|
261 |
|
262 static size_t ucx_avl_countn(UcxAVLNode *node) { |
|
263 if (node) { |
|
264 return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); |
|
265 } else { |
|
266 return 0; |
|
267 } |
|
268 } |
|
269 |
|
270 size_t ucx_avl_count(UcxAVLTree *tree) { |
|
271 return ucx_avl_countn(tree->root); |
|
272 } |