Add new code

Signed-off-by: Carlos Maiolino <[email protected]>

1 files changed, 127 insertions, 0 deletions

diff --git a/Algorithms/bplus-tree/src/bplus_search.c b/Algorithms/bplus-tree/src/bplus_search.c
new file mode 100644
index 0000000..a1e7c3b
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_search.c
@@ -0,0 +1,127 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#include "bplus_search.h"
+
+#include "bplus_node.h"
+#include "bplus_leaf.h"
+
+#define bplus_node_get_key_index_op(operator_m, tree_m, node_m, key_m)      \
+    do                                                                      \
+    {                                                                       \
+        size_t index = 1;                                                   \
+        while (index < (node_m)->length)                                    \
+        {                                                                   \
+            if (operator_m((tree_m), bplus_key_at(node_m, index), (key_m))) \
+                break;                                                      \
+            ++index;                                                        \
+        }                                                                   \
+                                                                            \
+        return --index;                                                     \
+    }                                                                       \
+    while (0)
+
+static size_t bplus_node_get_key_index(BplusTree const* tree, BplusNode const* node, BplusKey const key)
+{
+    g_return_val_if_fail(tree != NULL, 0);
+    g_return_val_if_fail(node != NULL, 0);
+
+    bplus_node_get_key_index_op(bplus_key_gt, tree, node, key);
+}
+
+static size_t bplus_node_get_key_index_before(BplusTree const* tree, BplusNode const* node, BplusKey const key)
+{
+    g_return_val_if_fail(tree != NULL, 0);
+    g_return_val_if_fail(node != NULL, 0);
+
+    bplus_node_get_key_index_op(bplus_key_gte, tree, node, key);
+}
+
+#define bplus_tree_get_path_to_key_op(operator_m, tree_m, key_m, path_m)           \
+    do                                                                             \
+    {                                                                              \
+        if (__builtin_expect(((tree_m)->root->length == 0), 0))                    \
+        {                                                                          \
+            (path_m)->length   = 1;                                                \
+            (path_m)->index[0] = 0;                                                \
+            (path_m)->leaf     = tree->root;                                       \
+            return;                                                                \
+        }                                                                          \
+                                                                                   \
+        BplusNode const* node   = (tree_m)->root;                                  \
+        size_t const     length = (tree_m)->height;                                \
+        for (size_t i = length; i > 0; --i)                                        \
+        {                                                                          \
+            for (int i = 0; i < BPLUS_TREE_ORDER * sizeof(*node->items) / 64; ++i) \
+            {                                                                      \
+                __builtin_prefetch(node->items + i * 64 / sizeof(*node->items));   \
+            }                                                                      \
+                                                                                   \
+            size_t const index = operator_m((tree_m), node, (key_m));              \
+            (path_m)->index[i - 1] = index;                                        \
+                                                                                   \
+            if (i == 1)                                                            \
+                break;                                                             \
+                                                                                   \
+            node = bplus_node_at(node, index);                                     \
+        }                                                                          \
+                                                                                   \
+        (path_m)->length = length;                                                 \
+        (path_m)->leaf   = (BplusNode*) node;                                      \
+    }                                                                              \
+    while (0)
+
+void bplus_tree_get_path_to_key(BplusTree const* tree, BplusKey const key, BplusPath* path)
+{
+    g_return_if_fail(tree != NULL);
+    g_assert(tree->height < sizeof((path)->index) / sizeof(*(path)->index));
+
+    bplus_tree_get_path_to_key_op(bplus_node_get_key_index, tree, key, path);
+}
+
+static void bplus_tree_get_path_to_key_before(BplusTree const* tree, BplusKey const key, BplusPath* path)
+{
+    g_return_if_fail(tree != NULL);
+    g_assert(tree->height < sizeof((path)->index) / sizeof(*(path)->index));
+
+    bplus_tree_get_path_to_key_op(bplus_node_get_key_index_before, tree, key, path);
+}
+
+void bplus_tree_get_paths_to_key_range(BplusTree const* tree, BplusKey key_from, BplusKey key_to, BplusPath* path_from, BplusPath* path_to)
+{
+    g_return_if_fail(tree != NULL);
+    g_assert(tree->height < sizeof((path_from)->index) / sizeof(*(path_from)->index));
+    g_assert(tree->height < sizeof((path_to)->index) / sizeof(*(path_to)->index));
+
+    if (bplus_key_gt(tree, key_from, key_to))
+    {
+        BplusKey tmp = key_to;
+        key_to   = key_from;
+        key_from = tmp;
+    }
+
+    bplus_tree_get_path_to_key(tree, key_to, path_to);
+    if (!bplus_key_gt(tree, bplus_key_at(path_to->leaf, path_to->index[0]), key_to))
+        path_to->index[0]++;
+
+    bplus_tree_get_path_to_key_before(tree, key_from, path_from);
+    if (!bplus_key_gte(tree, bplus_key_at(path_from->leaf, path_from->index[0]), key_from))
+        path_from->index[0]++;
+
+    BplusLeaf const* const leaf = (BplusLeaf*) path_from->leaf;
+    if (path_from->index[0] == leaf->node.length)
+    {
+        if (leaf->right == NULL)
+        {
+            path_from->leaf     = path_to->leaf;
+            path_from->index[0] = path_to->index[0];
+        }
+        else
+        {
+            path_from->leaf     = (BplusNode*) leaf->right;
+            path_from->index[0] = 0;
+        }
+    }
+}