src/ucx/avl.c

branch
config
changeset 254
4784c14aa639
parent 135
471e28cca288
equal deleted inserted replaced
253:ddfead6ea863 254:4784c14aa639
1 /* 1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 * 3 *
4 * Copyright 2016 Olaf Wintermann. All rights reserved. 4 * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
5 * 5 *
6 * Redistribution and use in source and binary forms, with or without 6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met: 7 * modification, are permitted provided that the following conditions are met:
8 * 8 *
9 * 1. Redistributions of source code must retain the above copyright 9 * 1. Redistributions of source code must retain the above copyright
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 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 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "avl.h" 29 #include "ucx/avl.h"
30
31 #include <limits.h>
30 32
31 #define ptrcast(ptr) ((void*)(ptr)) 33 #define ptrcast(ptr) ((void*)(ptr))
32 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) 34 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree))
33 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) 35 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode))
34 36
132 UcxAllocator *al = tree->allocator; 134 UcxAllocator *al = tree->allocator;
133 ucx_avl_free_node(al, tree->root); 135 ucx_avl_free_node(al, tree->root);
134 alfree(al, tree); 136 alfree(al, tree);
135 } 137 }
136 138
139 static void ucx_avl_free_content_node(UcxAllocator *al, UcxAVLNode *node,
140 ucx_destructor destr) {
141 if (node) {
142 ucx_avl_free_content_node(al, node->left, destr);
143 ucx_avl_free_content_node(al, node->right, destr);
144 if (destr) {
145 destr(node->value);
146 } else {
147 alfree(al, node->value);
148 }
149 }
150 }
151
152 void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr) {
153 ucx_avl_free_content_node(tree->allocator, tree->root, destr);
154 }
155
137 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) { 156 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) {
138 UcxAVLNode *n = tree->root; 157 UcxAVLNode *n = tree->root;
139 int cmpresult; 158 int cmpresult;
140 while (n && (cmpresult = tree->cmpfunc( 159 while (n && (cmpresult = tree->cmpfunc(
141 ptrcast(key), ptrcast(n->key), tree->userdata))) { 160 ptrcast(key), ptrcast(n->key), tree->userdata))) {
144 return n; 163 return n;
145 } 164 }
146 165
147 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { 166 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
148 UcxAVLNode *n = ucx_avl_get_node(tree, key); 167 UcxAVLNode *n = ucx_avl_get_node(tree, key);
168 return n ? n->value : NULL;
169 }
170
171 UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
172 distance_func dfnc, int mode) {
173 UcxAVLNode *n = tree->root;
174 UcxAVLNode *closest = NULL;
175
176 intmax_t cmpresult;
177 intmax_t closest_dist;
178 closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX;
179
180 while (n && (cmpresult = dfnc(
181 ptrcast(key), ptrcast(n->key), tree->userdata))) {
182 if (mode == UCX_AVL_FIND_CLOSEST) {
183 intmax_t dist = cmpresult;
184 if (dist < 0) dist *= -1;
185 if (dist < closest_dist) {
186 closest_dist = dist;
187 closest = n;
188 }
189 } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) {
190 if (cmpresult > closest_dist) {
191 closest_dist = cmpresult;
192 closest = n;
193 }
194 } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) {
195 if (cmpresult < closest_dist) {
196 closest_dist = cmpresult;
197 closest = n;
198 }
199 }
200 n = cmpresult > 0 ? n->right : n->left;
201 }
202 return n ? n : closest;
203 }
204
205 void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
206 distance_func dfnc, int mode) {
207 UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode);
149 return n ? n->value : NULL; 208 return n ? n->value : NULL;
150 } 209 }
151 210
152 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { 211 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
153 return ucx_avl_put_s(tree, key, value, NULL); 212 return ucx_avl_put_s(tree, key, value, NULL);
270 } 329 }
271 330
272 size_t ucx_avl_count(UcxAVLTree *tree) { 331 size_t ucx_avl_count(UcxAVLTree *tree) {
273 return ucx_avl_countn(tree->root); 332 return ucx_avl_countn(tree->root);
274 } 333 }
334
335 UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
336 if (node->left) {
337 UcxAVLNode* n = node->left;
338 while (n->right) {
339 n = n->right;
340 }
341 return n;
342 } else {
343 UcxAVLNode* n = node;
344 while (n->parent) {
345 if (n->parent->right == n) {
346 return n->parent;
347 } else {
348 n = n->parent;
349 }
350 }
351 return NULL;
352 }
353 }
354
355 UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
356 if (node->right) {
357 UcxAVLNode* n = node->right;
358 while (n->left) {
359 n = n->left;
360 }
361 return n;
362 } else {
363 UcxAVLNode* n = node;
364 while (n->parent) {
365 if (n->parent->left == n) {
366 return n->parent;
367 } else {
368 n = n->parent;
369 }
370 }
371 return NULL;
372 }
373 }

mercurial