Mercurial > hg > dav / file diff

--- a/ucx/avl.c	Fri Sep 22 20:19:00 2017 +0200
+++ b/ucx/avl.c	Fri Sep 22 20:42:33 2017 +0200
@@ -26,6 +26,8 @@
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
+#include <limits.h>
+
 #include "avl.h"
 
 #define ptrcast(ptr) ((void*)(ptr))
@@ -149,6 +151,46 @@
     return n ? n->value : NULL;
 }
 
+UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
+        distance_func dfnc, int mode) {
+    UcxAVLNode *n = tree->root;
+    UcxAVLNode *closest = NULL;
+
+    intmax_t cmpresult;
+    intmax_t closest_dist;
+    closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX;
+    
+    while (n && (cmpresult = dfnc(
+            ptrcast(key), ptrcast(n->key), tree->userdata))) {
+        if (mode == UCX_AVL_FIND_CLOSEST) {
+            intmax_t dist = cmpresult;
+            if (dist < 0) dist *= -1;
+            if (dist < closest_dist) {
+                closest_dist = dist;
+                closest = n;
+            }
+        } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) {
+            if (cmpresult > closest_dist) {
+                closest_dist = cmpresult;
+                closest = n;
+            }
+        } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) {
+            if (cmpresult < closest_dist) {
+                closest_dist = cmpresult;
+                closest = n;
+            }
+        }
+        n = cmpresult > 0 ? n->right : n->left;
+    }
+    return n ? n : closest;
+}
+
+void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
+        distance_func dfnc, int mode) {
+    UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode);
+    return n ? n->value : NULL;
+}
+
 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
     return ucx_avl_put_s(tree, key, value, NULL);
 }
@@ -272,3 +314,43 @@
 size_t ucx_avl_count(UcxAVLTree *tree) {
     return ucx_avl_countn(tree->root);
 }
+
+UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
+    if (node->left) {
+        UcxAVLNode* n = node->left;
+        while (n->right) {
+            n = n->right;
+        }
+        return n;
+    } else {
+        UcxAVLNode* n = node;
+        while (n->parent) {
+            if (n->parent->right == n) {
+                return n->parent;
+            } else {
+                n = n->parent;
+            }
+        }
+        return NULL;
+    }
+}
+
+UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
+    if (node->right) {
+        UcxAVLNode* n = node->right;
+        while (n->left) {
+            n = n->left;
+        }
+        return n;
+    } else {
+        UcxAVLNode* n = node;
+        while (n->parent) {
+            if (n->parent->left == n) {
+                return n->parent;
+            } else {
+                n = n->parent;
+            }
+        }
+        return NULL;
+    }
+}