1.1 --- a/ucx/avl.c Mon Mar 06 16:22:42 2017 +0100
1.2 +++ b/ucx/avl.c Sat Jul 15 19:20:06 2017 +0200
1.3 @@ -26,6 +26,8 @@
1.4 * POSSIBILITY OF SUCH DAMAGE.
1.5 */
1.6
1.7 +#include <limits.h>
1.8 +
1.9 #include "avl.h"
1.10
1.11 #define ptrcast(ptr) ((void*)(ptr))
1.12 @@ -149,6 +151,46 @@
1.13 return n ? n->value : NULL;
1.14 }
1.15
1.16 +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
1.17 + distance_func dfnc, int mode) {
1.18 + UcxAVLNode *n = tree->root;
1.19 + UcxAVLNode *closest = NULL;
1.20 +
1.21 + intmax_t cmpresult;
1.22 + intmax_t closest_dist;
1.23 + closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX;
1.24 +
1.25 + while (n && (cmpresult = dfnc(
1.26 + ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.27 + if (mode == UCX_AVL_FIND_CLOSEST) {
1.28 + intmax_t dist = cmpresult;
1.29 + if (dist < 0) dist *= -1;
1.30 + if (dist < closest_dist) {
1.31 + closest_dist = dist;
1.32 + closest = n;
1.33 + }
1.34 + } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) {
1.35 + if (cmpresult > closest_dist) {
1.36 + closest_dist = cmpresult;
1.37 + closest = n;
1.38 + }
1.39 + } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) {
1.40 + if (cmpresult < closest_dist) {
1.41 + closest_dist = cmpresult;
1.42 + closest = n;
1.43 + }
1.44 + }
1.45 + n = cmpresult > 0 ? n->right : n->left;
1.46 + }
1.47 + return n ? n : closest;
1.48 +}
1.49 +
1.50 +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
1.51 + distance_func dfnc, int mode) {
1.52 + UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode);
1.53 + return n ? n->value : NULL;
1.54 +}
1.55 +
1.56 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
1.57 return ucx_avl_put_s(tree, key, value, NULL);
1.58 }
