[sdk] Fix incorrect assumptions in the AVL binary search routines
authorcoderain <coderain@sdf.org>
Sun, 2 Dec 2018 23:45:09 +0000 (00:45 +0100)
committercoderain <coderain@sdf.org>
Sun, 2 Dec 2018 23:45:09 +0000 (00:45 +0100)
sdk/avltree.h

index e389fba7dc38642639a60b55cb03ea68eeb58870..4f8658af348d45dc23aeaca6134ef1aa958ecc6d 100644 (file)
@@ -77,23 +77,43 @@ static inline avl_node_t *avl_tree_lookup(const avl_tree_t *tree, const void *ke
 static inline avl_node_t *avl_tree_lower_bound(const avl_tree_t *tree, const void *key)
 {
     avl_node_t *node = tree->root;
+    avl_node_t *best = NULL;
 
-    while (node && tree->compare(avl_get_keyptr(tree, node), key) > 0) node = node->left;
-    if (!node) return NULL;
+    while (node)
+    {
+        if (tree->compare(avl_get_keyptr(tree, node), key) <= 0)
+        {
+            if (!best || tree->compare(avl_get_keyptr(tree, node), avl_get_keyptr(tree, best)) > 0) best = node;
+            node = node->right;
+        }
+        else
+        {
+            node = node->left;
+        }
+    }
 
-    while (node->right && tree->compare(avl_get_keyptr(tree, node->right), key) <= 0) node = node->right;
-    return node;
+    return best;
 }
 
 static inline avl_node_t *avl_tree_upper_bound(const avl_tree_t *tree, const void *key)
 {
     avl_node_t *node = tree->root;
+    avl_node_t *best = NULL;
 
-    while (node && tree->compare(avl_get_keyptr(tree, node), key) < 0) node = node->right;
-    if (!node) return NULL;
+    while (node)
+    {
+        if (tree->compare(avl_get_keyptr(tree, node), key) >= 0)
+        {
+            if (!best || tree->compare(avl_get_keyptr(tree, node), avl_get_keyptr(tree, best)) < 0) best = node;
+            node = node->left;
+        }
+        else
+        {
+            node = node->right;
+        }
+    }
 
-    while (node->left && tree->compare(avl_get_keyptr(tree, node->left), key) >= 0) node = node->left;
-    return node;
+    return best;
 }
 
 static inline avl_node_t *avl_get_next_node(const avl_node_t *node)