1 files changed, 60 insertions, 0 deletions
diff --git a/Algorithms/bplus-tree/src/bplus_remove.c b/Algorithms/bplus-tree/src/bplus_remove.c
new file mode 100644
index 0000000..9265ce1
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_remove.c
@@ -0,0 +1,60 @@
+/**
+ * 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_remove.h"
+
+#include "bplus_node.h"
+#include "bplus_search.h"
+#include "bplus_rebalance.h"
+
+void bplus_node_remove_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length)
+{
+    g_return_if_fail(node != NULL);
+    g_return_if_fail(index < node->length);
+    g_return_if_fail(index + length <= node->length);
+
+    bplus_node_move_and_resize_data(tree, node, index, index + length);
+}
+
+BplusValue bplus_tree_remove_first(BplusTree* tree)
+{
+    BplusPath    path  = { .leaf = (BplusNode*) tree->first };
+    BplusNode*   node  = (BplusNode*) path.leaf;
+    size_t const index = path.index[0];
+
+    BplusValue value = bplus_value_at(node, 0);
+    bplus_node_remove_at(tree, node, index, 1);
+    if (index == 0)
+        bplus_rebalance_propagate(tree, &path);
+
+    if (bplus_node_underfilled(node))
+        bplus_rebalance_underfilled(tree, &path);
+
+    return value;
+}
+
+BplusValue bplus_tree_remove(BplusTree* tree, BplusKey const key)
+{
+    BplusPath path;
+    bplus_tree_get_path_to_key(tree, key, &path);
+
+    size_t const index = path.index[0];
+    BplusNode*   node  = (BplusNode*) path.leaf;
+
+    if (bplus_key_eq(tree, bplus_key_at(node, index), key))
+    {
+        BplusValue value = bplus_value_at(node, index);
+        bplus_node_remove_at(tree, node, index, 1);
+        if (index == 0)
+            bplus_rebalance_propagate(tree, &path);
+
+        if (bplus_node_underfilled(node))
+            bplus_rebalance_underfilled(tree, &path);
+
+        return value;
+    }
+
+    return NULL;
+}