Mercurial > hg > toolkit / file diff

--- a/ucx/avl.c	Wed Nov 22 12:59:13 2017 +0100
+++ b/ucx/avl.c	Sun Jan 21 12:13:09 2018 +0100
@@ -1,7 +1,7 @@
 /*
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
  *
- * Copyright 2015 Olaf Wintermann. All rights reserved.
+ * Copyright 2016 Olaf Wintermann. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
@@ -26,9 +26,13 @@
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
+#include <limits.h>
+
 #include "avl.h"
 
 #define ptrcast(ptr) ((void*)(ptr))
+#define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree))
+#define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode))
 
 static void ucx_avl_connect(UcxAVLTree *tree,
         UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) {
@@ -107,7 +111,7 @@
 }
 
 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) {
-    UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree));
+    UcxAVLTree* tree = alloc_tree(allocator);
     if (tree) {
         tree->allocator = allocator;
         tree->cmpfunc = cmpfunc;
@@ -147,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);
 }
@@ -167,7 +211,7 @@
         }
 
         if (cmpresult) {
-            UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode));
+            UcxAVLNode* e = alloc_node(tree->allocator);
             if (e) {
                 e->key = key; e->value = value; e->height = 1;
                 e->parent = e->left = e->right = NULL;
@@ -185,7 +229,7 @@
             return 0;
         }
     } else {
-        tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode));
+        tree->root = alloc_node(tree->allocator);
         if (tree->root) {
             tree->root->key = key; tree->root->value = value;
             tree->root->height = 1;
@@ -270,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;
+    }
+}