From d98f46ce647846b0aa30b2e16a30fd4e152a1bf5 Mon Sep 17 00:00:00 2001 From: Carlos Maiolino Date: Thu, 10 Jul 2025 22:55:07 +0200 Subject: Add new code Signed-off-by: Carlos Maiolino --- Algorithms/bplus-tree/src/bplus_remove.c | 60 ++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 Algorithms/bplus-tree/src/bplus_remove.c (limited to 'Algorithms/bplus-tree/src/bplus_remove.c') 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; +} -- cgit v1.2.3