summaryrefslogtreecommitdiff
path: root/Algorithms/bplus-tree/src
diff options
context:
space:
mode:
Diffstat (limited to 'Algorithms/bplus-tree/src')
-rw-r--r--Algorithms/bplus-tree/src/bplus_foreach.c39
-rw-r--r--Algorithms/bplus-tree/src/bplus_foreach.h27
-rw-r--r--Algorithms/bplus-tree/src/bplus_insert.c58
-rw-r--r--Algorithms/bplus-tree/src/bplus_insert.h22
-rw-r--r--Algorithms/bplus-tree/src/bplus_iterator.c161
-rw-r--r--Algorithms/bplus-tree/src/bplus_iterator.h31
-rw-r--r--Algorithms/bplus-tree/src/bplus_leaf.c71
-rw-r--r--Algorithms/bplus-tree/src/bplus_leaf.h34
-rw-r--r--Algorithms/bplus-tree/src/bplus_node.c111
-rw-r--r--Algorithms/bplus-tree/src/bplus_node.h55
-rw-r--r--Algorithms/bplus-tree/src/bplus_rebalance.c279
-rw-r--r--Algorithms/bplus-tree/src/bplus_rebalance.h24
-rw-r--r--Algorithms/bplus-tree/src/bplus_remove.c60
-rw-r--r--Algorithms/bplus-tree/src/bplus_remove.h22
-rw-r--r--Algorithms/bplus-tree/src/bplus_search.c127
-rw-r--r--Algorithms/bplus-tree/src/bplus_search.h23
-rw-r--r--Algorithms/bplus-tree/src/bplus_tree.c202
-rw-r--r--Algorithms/bplus-tree/src/bplus_tree_private.h53
18 files changed, 1399 insertions, 0 deletions
diff --git a/Algorithms/bplus-tree/src/bplus_foreach.c b/Algorithms/bplus-tree/src/bplus_foreach.c
new file mode 100644
index 0000000..e9184b7
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_foreach.c
@@ -0,0 +1,39 @@
+/**
+ * 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_foreach.h"
+
+#include "bplus_node.h"
+
+void bplus_foreach_item_in_node(BplusTree* tree, BplusNode* node, BplusForeachItemFunc* foreach, void* argument)
+{
+ if (!node->is_leaf)
+ for (size_t i = 0; i < node->length; ++i)
+ bplus_foreach_item_in_node(tree, bplus_node_at(node, i), foreach, argument);
+
+ else
+ for (size_t i = 0; i < node->length; ++i)
+ foreach(tree, node->items + i, argument);
+
+}
+
+void bplus_foreach_item_in_tree(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument)
+{
+ bplus_foreach_item_in_node(tree, tree->root, foreach, argument);
+}
+
+void bplus_foreach_node_in_node(BplusTree* tree, BplusNode* node, BplusForeachNodeFunc* foreach, void* argument)
+{
+ if (!node->is_leaf)
+ for (size_t i = 0; i < node->length; ++i)
+ bplus_foreach_node_in_node(tree, bplus_node_at(node, i), foreach, argument);
+
+ foreach(tree, node, argument);
+}
+
+void bplus_foreach_node_in_tree(BplusTree* tree, BplusForeachNodeFunc* foreach, void* argument)
+{
+ bplus_foreach_node_in_node(tree, tree->root, foreach, argument);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_foreach.h b/Algorithms/bplus-tree/src/bplus_foreach.h
new file mode 100644
index 0000000..69849a6
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_foreach.h
@@ -0,0 +1,27 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_FOREACH_H__
+#define __BPLUS_FOREACH_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_foreach_item_in_node(BplusTree* tree, BplusNode* node, BplusForeachItemFunc* foreach, void* argument);
+void bplus_foreach_item_in_tree(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument);
+
+typedef void (BplusForeachNodeFunc)(BplusTree* tree, BplusNode* node, void* argument);
+void bplus_foreach_node_in_node(BplusTree* tree, BplusNode* node, BplusForeachNodeFunc* foreach, void* argument);
+void bplus_foreach_node_in_tree(BplusTree* tree, BplusForeachNodeFunc* foreach, void* argument);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_FOREACH_H__
diff --git a/Algorithms/bplus-tree/src/bplus_insert.c b/Algorithms/bplus-tree/src/bplus_insert.c
new file mode 100644
index 0000000..9cd3ea7
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_insert.c
@@ -0,0 +1,58 @@
+/**
+ * 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_insert.h"
+
+#include "bplus_node.h"
+#include "bplus_search.h"
+#include "bplus_rebalance.h"
+
+#include <string.h>
+
+static void bplus_leaf_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, BplusKey const key, BplusValue const value)
+{
+ g_return_if_fail(node != NULL);
+ g_return_if_fail(index <= node->length);
+
+ bplus_node_move_and_resize_data(tree, node, index + 1, index);
+ bplus_key_at(node, index) = key;
+ bplus_value_at(node, index) = value;
+}
+
+void bplus_node_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length, BplusItem const* const items)
+{
+ g_return_if_fail(node != NULL);
+ g_return_if_fail(index <= node->length);
+ g_return_if_fail(node->length + length <= BPLUS_TREE_ORDER);
+
+ bplus_node_move_and_resize_data(tree, node, index + length, index);
+ memcpy(node->items + index, items, length * sizeof(BplusItem));
+
+ if (node->is_leaf)
+ return;
+
+ for (size_t i = index; i < index + length; ++i)
+ bplus_node_at(node, i)->parent = node;
+}
+
+void bplus_tree_insert(BplusTree* tree, BplusKey const key, BplusValue const value)
+{
+ BplusPath path;
+ bplus_tree_get_path_to_key(tree, key, &path);
+
+ size_t index = path.index[0];
+ BplusNode* node = (BplusNode*) path.leaf;
+
+ /* If the node is not empty, we will insert it after the given index */
+ if ((index < node->length) && bplus_key_lte(tree, bplus_key_at(node, index), key))
+ index++;
+
+ bplus_leaf_insert_at(tree, node, index, key, value);
+ if (index == 0)
+ bplus_rebalance_propagate(tree, &path);
+
+ if (bplus_node_overfilled(node))
+ bplus_rebalance_overfilled(tree, &path);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_insert.h b/Algorithms/bplus-tree/src/bplus_insert.h
new file mode 100644
index 0000000..e73f963
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_insert.h
@@ -0,0 +1,22 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_INSERT_H__
+#define __BPLUS_INSERT_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_node_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length, BplusItem const* const items);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_INSERT_H__
diff --git a/Algorithms/bplus-tree/src/bplus_iterator.c b/Algorithms/bplus-tree/src/bplus_iterator.c
new file mode 100644
index 0000000..8ab796e
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_iterator.c
@@ -0,0 +1,161 @@
+/**
+ * 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_iterator.h"
+
+#include "bplus_leaf.h"
+#include "bplus_search.h"
+
+static BplusIterator* bplus_iterator_new_full(BplusTree const* tree,
+ BplusLeaf const* leaf_from, BplusItem const* item_from,
+ BplusLeaf const* leaf_to, BplusItem const* item_to)
+{
+ BplusIterator* iterator = g_slice_new(BplusIterator);
+
+ iterator->leaf_from = leaf_from;
+ iterator->item_from = item_from;
+ iterator->leaf_to = leaf_to;
+ iterator->item_to = item_to;
+ iterator->item = item_from;
+ iterator->leaf = leaf_from;
+
+ return iterator;
+}
+
+static BplusIterator* bplus_iterator_new_to_last(BplusTree const* tree, BplusLeaf const* leaf_from, BplusItem const* item_from)
+{
+ return bplus_iterator_new_full(tree, leaf_from, item_from, tree->last, tree->last->node.items + tree->last->node.length);
+}
+
+static BplusIterator* bplus_iterator_new_from_first(BplusTree const* tree, BplusLeaf const* leaf_to, BplusItem const* item_to)
+{
+ return bplus_iterator_new_full(tree, tree->first, tree->first->node.items, leaf_to, item_to);
+}
+
+BplusIterator* bplus_iterator_new(BplusTree const* tree)
+{
+ return bplus_iterator_new_to_last(tree, tree->first, tree->first->node.items);
+}
+
+void bplus_iterator_destroy(BplusIterator* iterator)
+{
+ g_return_if_fail(iterator != NULL);
+
+ g_slice_free(BplusIterator, iterator);
+}
+
+gboolean bplus_iterator_next(BplusIterator* iterator)
+{
+ g_return_val_if_fail(iterator != NULL, FALSE);
+
+ BplusItem const* const next = iterator->item + 1;
+ BplusLeaf const* const leaf = iterator->leaf;
+ if (next == iterator->item_to)
+ return FALSE;
+
+ if (next - leaf->node.items < leaf->node.length)
+ {
+ ++iterator->item;
+ }
+ else
+ {
+ if (leaf->right == NULL)
+ return FALSE;
+
+ iterator->leaf = leaf->right;
+ iterator->item = leaf->right->node.items;
+ }
+
+ return TRUE;
+}
+
+gboolean bplus_iterator_previous(BplusIterator* iterator)
+{
+ g_return_val_if_fail(iterator != NULL, FALSE);
+
+ BplusItem const* const item = iterator->item;
+ BplusLeaf const* const leaf = iterator->leaf;
+
+ if (item == iterator->item_from)
+ return FALSE;
+
+ if (item - leaf->node.items == 0)
+ {
+ if (leaf->left == NULL)
+ return FALSE;
+
+ iterator->leaf = leaf->left;
+ iterator->item = leaf->left->node.items + leaf->left->node.length;
+ }
+
+ --iterator->item;
+
+ return TRUE;
+}
+
+BplusItem const* bplus_iterator_get_item(BplusIterator const* iterator)
+{
+ g_return_val_if_fail(iterator != NULL, NULL);
+
+ if (iterator->item_from == iterator->item_to)
+ return NULL;
+
+ return iterator->item;
+}
+
+BplusIterator* bplus_tree_first(BplusTree const* tree)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ return bplus_iterator_new(tree);
+}
+
+BplusIterator* bplus_iterator_from_key(BplusTree const* tree, BplusKey const key)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ BplusPath path_from;
+ BplusPath path_to;
+ bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to);
+
+ return bplus_iterator_new_to_last(tree, (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0]);
+}
+
+BplusIterator* bplus_iterator_to_key(BplusTree const* tree, BplusKey const key)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ BplusPath path_from;
+ BplusPath path_to;
+ bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to);
+
+ return bplus_iterator_new_from_first(tree, (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]);
+}
+
+BplusIterator* bplus_iterator_for_key(BplusTree const* tree, BplusKey const key)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ BplusPath path_from;
+ BplusPath path_to;
+ bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to);
+
+ return bplus_iterator_new_full(tree,
+ (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0],
+ (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]);
+}
+
+BplusIterator* bplus_iterator_for_key_range(BplusTree const* tree, BplusKey const key_from, BplusKey const key_to)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ BplusPath path_from;
+ BplusPath path_to;
+ bplus_tree_get_paths_to_key_range(tree, key_from, key_to, &path_from, &path_to);
+
+ return bplus_iterator_new_full(tree,
+ (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0],
+ (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_iterator.h b/Algorithms/bplus-tree/src/bplus_iterator.h
new file mode 100644
index 0000000..c7ae9b2
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_iterator.h
@@ -0,0 +1,31 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_ITERATOR_H__
+#define __BPLUS_ITERATOR_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+struct _BplusIterator
+{
+ BplusItem const* item;
+ BplusLeaf const* leaf;
+
+ BplusLeaf const* leaf_from;
+ BplusItem const* item_from;
+ BplusLeaf const* leaf_to;
+ BplusItem const* item_to;
+};
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_ITERATOR_H__
diff --git a/Algorithms/bplus-tree/src/bplus_leaf.c b/Algorithms/bplus-tree/src/bplus_leaf.c
new file mode 100644
index 0000000..a6b6ae5
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_leaf.c
@@ -0,0 +1,71 @@
+/**
+ * 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_leaf.h"
+
+BplusLeaf* bplus_leaf_new(BplusTree* tree)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ BplusLeaf* leaf = g_slice_new(BplusLeaf);
+
+ bplus_node_init(&leaf->node, TRUE);
+ leaf->left = NULL;
+ leaf->right = NULL;
+
+#ifdef BPLUS_TREE_GATHER_STATS
+ tree->node_count++;
+ tree->leaf_count++;
+ tree->underflow_count++;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+ return leaf;
+}
+
+BplusLeaf* bplus_leaf_new_right(BplusTree* tree, BplusLeaf* leaf_left)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+ g_return_val_if_fail(leaf_left != NULL, NULL);
+
+ BplusLeaf* leaf_right = bplus_leaf_new(tree);
+
+ leaf_right->left = leaf_left;
+ leaf_right->right = leaf_left->right;
+ leaf_left->right = leaf_right;
+
+ if (leaf_right->right != NULL)
+ leaf_right->right->left = leaf_right;
+
+ if (tree->last == leaf_left)
+ tree->last = leaf_right;
+
+ return leaf_right;
+}
+
+void bplus_leaf_destroy(BplusTree* tree, BplusLeaf* leaf)
+{
+ g_return_if_fail(tree != NULL);
+ g_return_if_fail(leaf != NULL);
+
+ if (leaf->left != NULL)
+ leaf->left->right = leaf->right;
+
+ if (leaf->right != NULL)
+ leaf->right->left = leaf->left;
+
+ if (tree->first == leaf)
+ tree->first = leaf->right;
+
+ if (tree->last == leaf)
+ tree->last = leaf->left;
+
+#ifdef BPLUS_TREE_GATHER_STATS
+ tree->node_count--;
+ tree->leaf_count--;
+ tree->underflow_count--;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+ g_slice_free(BplusLeaf, leaf);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_leaf.h b/Algorithms/bplus-tree/src/bplus_leaf.h
new file mode 100644
index 0000000..482a933
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_leaf.h
@@ -0,0 +1,34 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_LEAF_H__
+#define __BPLUS_LEAF_H__
+
+#include "bplus_tree_private.h"
+
+#include "bplus_node.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+struct _BplusLeaf
+{
+ BplusNode node;
+
+ BplusLeaf* left;
+ BplusLeaf* right;
+};
+
+BplusLeaf* bplus_leaf_new(BplusTree* tree);
+BplusLeaf* bplus_leaf_new_right(BplusTree* tree, BplusLeaf* leaf_left);
+void bplus_leaf_destroy(BplusTree* tree, BplusLeaf* leaf);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_LEAF_H__
diff --git a/Algorithms/bplus-tree/src/bplus_node.c b/Algorithms/bplus-tree/src/bplus_node.c
new file mode 100644
index 0000000..6637367
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_node.c
@@ -0,0 +1,111 @@
+/**
+ * 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_node.h"
+
+#include "bplus_leaf.h"
+
+#include <string.h>
+
+BplusNode* bplus_node_new(BplusTree* tree)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ BplusNode* node = g_slice_new(BplusNode);
+
+ bplus_node_init(node, FALSE);
+
+#ifdef BPLUS_TREE_GATHER_STATS
+ tree->node_count++;
+ tree->underflow_count++;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+ return node;
+}
+
+BplusNode* bplus_node_new_right(BplusTree* tree, BplusNode* node_left)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+ g_return_val_if_fail(node_left != NULL, NULL);
+
+ BplusNode* node_right;
+
+ if (node_left->is_leaf)
+ node_right = (BplusNode*) bplus_leaf_new_right(tree, (BplusLeaf*) node_left);
+ else
+ node_right = bplus_node_new(tree);
+
+ node_right->parent = node_left->parent;
+
+ return node_right;
+}
+
+void bplus_node_init(BplusNode* node, gboolean is_leaf)
+{
+ g_return_if_fail(node != NULL);
+
+ node->parent = NULL;
+ node->is_leaf = is_leaf;
+
+ node->length = 0;
+}
+
+void bplus_node_destroy(BplusTree* tree, BplusNode* node)
+{
+ g_return_if_fail(tree != NULL);
+ g_return_if_fail(node != NULL);
+
+ if (node->is_leaf)
+ {
+ bplus_leaf_destroy(tree, (BplusLeaf*) node);
+ }
+ else
+ {
+#ifdef BPLUS_TREE_GATHER_STATS
+ tree->node_count--;
+ tree->underflow_count--;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+ g_slice_free(BplusNode, node);
+ }
+}
+
+void bplus_node_move_and_resize_data(BplusTree const* tree, BplusNode* node, size_t const index_to, size_t const index_from)
+{
+ g_return_if_fail(node != NULL);
+ g_return_if_fail(index_from <= node->length);
+
+#ifdef BPLUS_TREE_GATHER_STATS
+ int was_underfilled = bplus_node_underfilled(node);
+ int was_overfilled = bplus_node_overfilled(node);
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+ int64_t const resize_length = index_to - index_from;
+ if (resize_length == 0)
+ return;
+
+ int64_t const move_length = node->length - index_from;
+ if (move_length > 0)
+ memmove(node->items + index_to, node->items + index_from, move_length * sizeof(BplusItem));
+
+ if (resize_length > 0)
+ node->length += resize_length;
+
+ else if (resize_length < 0)
+ node->length -= -resize_length;
+
+#ifdef BPLUS_TREE_GATHER_STATS
+ if (!bplus_node_underfilled(node) && was_underfilled)
+ tree->underflow_count--;
+ else if (bplus_node_underfilled(node) && !was_underfilled)
+ tree->underflow_count++;
+
+ if (bplus_node_overfilled(node) && !was_overfilled)
+ tree->overflow_count++;
+ else if (!bplus_node_overfilled(node) && was_overfilled)
+ tree->overflow_count--;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+}
diff --git a/Algorithms/bplus-tree/src/bplus_node.h b/Algorithms/bplus-tree/src/bplus_node.h
new file mode 100644
index 0000000..83a4d9a
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_node.h
@@ -0,0 +1,55 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_NODE_H__
+#define __BPLUS_NODE_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+struct _BplusNode
+{
+ size_t length;
+ BplusItem items[BPLUS_TREE_ORDER];
+
+ uint8_t is_leaf;
+ BplusNode* parent;
+};
+
+#define bplus_key_gt(bplus_tree_m, k1, k2) ((k1) > (k2))
+#define bplus_key_gte(bplus_tree_m, k1, k2) ((k1) >= (k2))
+#define bplus_key_lt(bplus_tree_m, k1, k2) ((k1) < (k2))
+#define bplus_key_lte(bplus_tree_m, k1, k2) ((k1) <= (k2))
+#define bplus_key_eq(bplus_tree_m, k1, k2) ((k1) == (k2))
+#define bplus_key_neq(bplus_tree_m, k1, k2) ((k1) != (k2))
+
+#define bplus_key_at(node_m, index_m) (((BplusNode*) node_m)->items[(index_m)].key)
+#define bplus_key_first(node_m) bplus_key_at(node_m, 0)
+#define bplus_key_last(node_m) bplus_key_at(node_m, (node_m)->length - 1)
+#define bplus_value_at(node_m, index_m) (((BplusNode*) node_m)->items[(index_m)].value)
+#define bplus_value_first(node_m) bplus_value_at(node_m, 0)
+#define bplus_value_last(node_m) bplus_value_at(node_m, (node_m)->length - 1)
+#define bplus_node_at(node_m, index_m) ((BplusNode*) bplus_value_at(node_m, index_m))
+#define bplus_node_first(node_m) ((BplusNode*) bplus_value_first(node_m))
+#define bplus_node_last(node_m) ((BplusNode*) bplus_value_last(node_m))
+
+#define bplus_node_overfilled(node_m) ((node_m)->length > (BPLUS_TREE_ORDER - 1))
+#define bplus_node_underfilled(node_m) ((node_m)->length <= 1)
+
+BplusNode* bplus_node_new(BplusTree* tree);
+BplusNode* bplus_node_new_right(BplusTree* tree, BplusNode* node_left);
+void bplus_node_destroy(BplusTree* tree, BplusNode* node);
+void bplus_node_init(BplusNode* node, gboolean is_leaf);
+void bplus_node_move_and_resize_data(BplusTree const* tree, BplusNode* node, size_t const index_to, size_t const index_from);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_NODE_H__
diff --git a/Algorithms/bplus-tree/src/bplus_rebalance.c b/Algorithms/bplus-tree/src/bplus_rebalance.c
new file mode 100644
index 0000000..a3cf401
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_rebalance.c
@@ -0,0 +1,279 @@
+/**
+ * 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_rebalance.h"
+
+#include "bplus_node.h"
+#include "bplus_search.h"
+#include "bplus_insert.h"
+#include "bplus_remove.h"
+
+void bplus_rebalance_propagate(BplusTree const* tree, BplusPath* path)
+{
+ g_return_if_fail(tree != NULL);
+ g_return_if_fail(path != NULL);
+
+ BplusNode* node = path->leaf;
+ for (size_t i = 1; i < path->length; ++i)
+ {
+ size_t const index = path->index[i];
+ BplusKey const key = bplus_key_first(node);
+
+ if (bplus_key_gt(tree, bplus_key_at(node->parent, index), key))
+ bplus_key_at(node->parent, index) = key;
+ else
+ break;
+
+ node = node->parent;
+ }
+}
+
+static int64_t bplus_node_get_rebalance_amount(BplusTree const* tree, BplusNode const* node_left, BplusNode const* node_right)
+{
+ g_return_val_if_fail(tree != NULL, 0);
+ g_return_val_if_fail(node_left != NULL, 0);
+ g_return_val_if_fail(node_right != NULL, 0);
+
+ size_t const total = node_left->length + node_right->length;
+
+ /* If the nodes can be merged without overfilling */
+ if (total <= (BPLUS_TREE_ORDER / 3))
+ return -node_right->length;
+
+ /* If the data can be balanced over the two without overfilling */
+ else if (total < (BPLUS_TREE_ORDER * 5 / 3))
+ return node_left->length - (total + 1) / 2;
+
+ return 0;
+}
+
+static gboolean bplus_node_find_merge_candidate(BplusTree const* tree, size_t const index, BplusNode* node,
+ BplusNode** node_left, BplusNode** node_right)
+{
+ g_return_val_if_fail(tree != NULL, FALSE);
+ g_return_val_if_fail(node != NULL, FALSE);
+
+ *node_left = node;
+ *node_right = node;
+ if ((node->parent == NULL) || (node->parent->length <= 1))
+ return FALSE;
+
+ if (index == 0)
+ {
+ *node_right = bplus_node_at(node->parent, index + 1);
+ if (bplus_node_get_rebalance_amount(tree, node, *node_right) == 0)
+ *node_right = node;
+
+ }
+ else if (index == node->parent->length - 1)
+ {
+ *node_left = bplus_node_at(node->parent, index - 1);
+ if (bplus_node_get_rebalance_amount(tree, *node_left, node) == 0)
+ *node_left = node;
+
+ }
+ else
+ {
+ *node_left = bplus_node_at(node->parent, index - 1);
+ *node_right = bplus_node_at(node->parent, index + 1);
+
+ int64_t const merge_amount_right = bplus_node_get_rebalance_amount(tree, node, *node_right);
+ int64_t const merge_amount_left = bplus_node_get_rebalance_amount(tree, *node_left, node);
+
+ if (merge_amount_left < 0)
+ {
+ /* Merge with left copies data to the left.
+ * Prefer a merge with right only if it copies less data from the right.
+ */
+ if (merge_amount_right >= 0)
+ *node_right = node;
+ else if (merge_amount_right < merge_amount_left)
+ *node_right = node;
+ else
+ *node_left = node;
+ }
+ else if (merge_amount_left > 0)
+ {
+ /* Merge with left copies data from the left.
+ * Prefer a merge with right if it copies less data to the right or data from right.
+ */
+ if (merge_amount_right == 0)
+ *node_right = node;
+ else if (merge_amount_right > merge_amount_left)
+ *node_right = node;
+ else
+ *node_left = node;
+ }
+ else if (merge_amount_right != 0)
+ {
+ /* Merge with left is impossible.
+ * Prefer a merge with right.
+ */
+ *node_left = node;
+ }
+ else
+ {
+ *node_left = node;
+ *node_right = node;
+ }
+ }
+
+ return *node_left != *node_right;
+} /* bplus_node_find_merge_candidate */
+
+static size_t bplus_rebalance_data(BplusTree const* tree, BplusNode* node_left, BplusNode* node_right)
+{
+ g_return_val_if_fail(tree != NULL, 0);
+ g_return_val_if_fail(node_left != NULL, 0);
+ g_return_val_if_fail(node_right != NULL, 0);
+
+ int64_t const amount = bplus_node_get_rebalance_amount(tree, node_left, node_right);
+ g_return_val_if_fail(amount <= 0 || amount < node_left->length, 0);
+ g_return_val_if_fail(amount >= 0 || -amount <= node_right->length, 0);
+
+ if (amount > 0)
+ {
+ size_t const index = node_left->length - amount;
+ BplusItem const* items = node_left->items + index;
+
+ bplus_node_insert_at(tree, node_right, 0, amount, items);
+ bplus_node_remove_at(tree, node_left, index, amount);
+
+ }
+ else if (amount < 0)
+ {
+ size_t const index = node_left->length;
+ BplusItem const* items = node_right->items;
+
+ bplus_node_insert_at(tree, node_left, index, -amount, items);
+ bplus_node_remove_at(tree, node_right, 0, -amount);
+ }
+
+ return 0;
+} /* bplus_rebalance_data */
+
+static void bplus_rebalance_split_node(BplusTree* tree, BplusNode* node_left, size_t const index)
+{
+ g_return_if_fail(tree != NULL);
+ g_return_if_fail(node_left != NULL);
+
+ BplusNode* const node_right = bplus_node_new_right(tree, node_left);
+ bplus_rebalance_data(tree, node_left, node_right);
+
+ BplusItem const item = { .key = bplus_key_first(node_right), .value = node_right };
+ bplus_node_insert_at(tree, node_left->parent, index + 1, 1, &item);
+}
+
+static void bplus_rebalance_new_root(BplusTree* tree)
+{
+ g_return_if_fail(tree != NULL);
+
+ BplusNode* const node = tree->root;
+ BplusNode* const root = bplus_node_new(tree);
+ bplus_key_first(root) = bplus_key_first(node);
+ bplus_value_first(root) = node;
+ root->length = 1;
+ node->parent = root;
+ tree->root = root;
+ tree->height++;
+}
+
+static int bplus_rebalance_try_merge(BplusTree* tree, BplusNode* node, size_t const index)
+{
+ g_return_val_if_fail(tree != NULL, 0);
+ g_return_val_if_fail(node != NULL, 0);
+
+ BplusNode* node_left;
+ BplusNode* node_right;
+ if (!bplus_node_find_merge_candidate(tree, index, node, &node_left, &node_right))
+ return 0;
+
+ size_t const index_right = (node == node_left) ? index + 1 : index;
+ bplus_rebalance_data(tree, node_left, node_right);
+
+ if (node_right->length == 0)
+ {
+ bplus_node_remove_at(tree, node->parent, index_right, 1);
+ bplus_node_destroy(tree, node_right);
+ }
+ else
+ {
+ bplus_key_at(node->parent, index_right) = bplus_key_first(node_right);
+ }
+
+ return 1;
+}
+
+void bplus_rebalance_overfilled(BplusTree* tree, BplusPath const* path)
+{
+ g_return_if_fail(tree != NULL);
+ g_return_if_fail(path != NULL);
+
+ BplusNode* node = (BplusNode*) path->leaf;
+ for (size_t i = 1; i < path->length; ++i)
+ {
+ if (!bplus_node_overfilled(node))
+ break;
+
+ size_t const index = path->index[i];
+ if (!bplus_rebalance_try_merge(tree, node, index))
+ bplus_rebalance_split_node(tree, node, index);
+
+ node = node->parent;
+ }
+
+ if (bplus_node_overfilled(node))
+ {
+ bplus_rebalance_new_root(tree);
+ bplus_rebalance_split_node(tree, node, 0);
+ }
+}
+
+static void bplus_rebalance_shrink_tree(BplusTree* tree)
+{
+ g_return_if_fail(tree != NULL);
+ g_return_if_fail(tree->root != NULL);
+
+ size_t i = 0;
+ for (; i < tree->height; ++i)
+ {
+ if (tree->root->length != 1)
+ break;
+ if (tree->root->is_leaf)
+ break;
+
+ BplusNode* node = tree->root;
+ tree->root = bplus_node_first(tree->root);
+ tree->root->parent = NULL;
+ node->length = 0;
+ bplus_node_destroy(tree, node);
+ }
+
+ tree->height -= i;
+}
+
+void bplus_rebalance_underfilled(BplusTree* tree, BplusPath const* path)
+{
+ g_return_if_fail(tree != NULL);
+ g_return_if_fail(path != NULL);
+
+ BplusNode* node = (BplusNode*) path->leaf;
+ for (size_t i = 1; i < path->length; ++i)
+ {
+ if (!bplus_node_underfilled(node))
+ break;
+
+ size_t const index = path->index[i];
+ if (!bplus_rebalance_try_merge(tree, node, index) && (node->length == 0))
+ {
+ bplus_node_remove_at(tree, node->parent, index, 1);
+ bplus_node_destroy(tree, node);
+ }
+
+ node = node->parent;
+ }
+
+ bplus_rebalance_shrink_tree(tree);
+}
diff --git a/Algorithms/bplus-tree/src/bplus_rebalance.h b/Algorithms/bplus-tree/src/bplus_rebalance.h
new file mode 100644
index 0000000..3872f4d
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_rebalance.h
@@ -0,0 +1,24 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_REBALANCE_H__
+#define __BPLUS_REBALANCE_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_rebalance_propagate(BplusTree const* tree, BplusPath* path);
+void bplus_rebalance_overfilled(BplusTree* tree, BplusPath const* path);
+void bplus_rebalance_underfilled(BplusTree* tree, BplusPath const* path);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_REBALANCE_H__
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;
+}
diff --git a/Algorithms/bplus-tree/src/bplus_remove.h b/Algorithms/bplus-tree/src/bplus_remove.h
new file mode 100644
index 0000000..81b94d3
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_remove.h
@@ -0,0 +1,22 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_REMOVE_H__
+#define __BPLUS_REMOVE_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_node_remove_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_REMOVE_H__
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;
+ }
+ }
+}
diff --git a/Algorithms/bplus-tree/src/bplus_search.h b/Algorithms/bplus-tree/src/bplus_search.h
new file mode 100644
index 0000000..3e76a39
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_search.h
@@ -0,0 +1,23 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_SEARCH_H__
+#define __BPLUS_SEARCH_H__
+
+#include "bplus_tree_private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+void bplus_tree_get_path_to_key(BplusTree const* tree, BplusKey const key, BplusPath* path);
+void bplus_tree_get_paths_to_key_range(BplusTree const* tree, BplusKey key_from, BplusKey key_to, BplusPath* path_from, BplusPath* path_to);
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_SEARCH_H__
diff --git a/Algorithms/bplus-tree/src/bplus_tree.c b/Algorithms/bplus-tree/src/bplus_tree.c
new file mode 100644
index 0000000..fc8bb8e
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_tree.c
@@ -0,0 +1,202 @@
+/**
+ * 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_tree_private.h"
+
+#include "bplus_leaf.h"
+#include "bplus_search.h"
+#include "bplus_iterator.h"
+#include "bplus_foreach.h"
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+int bplus_tree_print(BplusTree const* const tree, char const* format, ...) __attribute__((format(printf, 2, 3)));
+
+BplusTree* bplus_tree_new()
+{
+ return bplus_tree_new_full(1);
+}
+
+BplusTree* bplus_tree_new_full(gboolean allow_duplicate_keys)
+{
+ BplusTree* tree = malloc(sizeof(BplusTree));
+
+ tree->first = bplus_leaf_new(tree);
+ tree->last = tree->first;
+ tree->root = (BplusNode*) tree->first;
+
+ tree->height = 1;
+ tree->allow_duplicate_keys = allow_duplicate_keys;
+
+ return tree;
+}
+
+void bplus_tree_print_stats(BplusTree* tree);
+
+static void bplus_foreach_node_destroy(BplusTree* tree, BplusNode* node, void* argument)
+{
+ bplus_node_destroy(tree, node);
+}
+
+void bplus_tree_destroy(BplusTree* tree)
+{
+ g_return_if_fail(tree != NULL);
+
+#ifdef BPLUS_TREE_GATHER_STATS
+ bplus_tree_print_stats(tree);
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+ bplus_foreach_node_in_tree(tree, &bplus_foreach_node_destroy, NULL);
+ free(tree);
+}
+
+void bplus_tree_destroy_each(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument)
+{
+ bplus_foreach_item_in_tree(tree, foreach, argument);
+ bplus_tree_destroy(tree);
+}
+
+#ifdef BPLUS_TREE_GATHER_STATS
+
+void bplus_tree_print_stats(BplusTree* tree)
+{
+ printf("tree height: %zu\n", tree->height);
+ printf("node count: %zu\n", tree->node_count);
+ printf("leaf count: %zu\n", tree->leaf_count);
+ printf("underflow count: %zu\n", tree->underflow_count);
+ printf("overflow count: %zu\n", tree->overflow_count);
+}
+
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+
+BplusValue bplus_tree_get(BplusTree* tree, BplusKey key)
+{
+ BplusPath path;
+ bplus_tree_get_path_to_key(tree, key, &path);
+
+ size_t const index = path.index[0];
+ BplusNode const* node = path.leaf;
+ BplusValue value = NULL;
+
+ if ((index < node->length) && bplus_key_eq(tree, bplus_key_at(node, index), key))
+ value = bplus_value_at(node, index);
+
+ return value;
+}
+
+BplusValue bplus_tree_get_first(BplusTree const* tree)
+{
+ if (tree->first->node.length == 0)
+ return NULL;
+
+ return tree->first->node.items[0].value;
+}
+
+BplusValue bplus_tree_get_nth(BplusTree const* tree, size_t position)
+{
+ BplusLeaf* leaf = tree->first;
+ if (leaf->node.length == 0)
+ return NULL;
+
+ while (leaf != NULL && position >= leaf->node.length)
+ {
+ position -= leaf->node.length;
+ leaf = leaf->right;
+ }
+
+ if (leaf != NULL)
+ return leaf->node.items[position].value;
+
+ return NULL;
+}
+
+void bplus_value_print(BplusNode* node, size_t const index, BplusKey key, BplusValue value, int depth)
+{
+ static char const* indent = " ";
+
+ fprintf(stderr, "%*.s n%p_%zu[label=\"%lu\",fontcolor=\"#000099\"];", 0, indent, node, index, key);
+ fprintf(stderr, "%*.s n%p->n%p_%zu;", 0, indent, node, node, index);
+}
+
+void bplus_node_print(BplusNode* parent, BplusKey key, BplusNode* node, int depth)
+{
+ static char const* indent = " ";
+
+ fprintf(stderr, "%*.s n%p[label=\"%lu\"];", 0, indent, node, key);
+ fprintf(stderr, "%*.s n%p->n%p;", 0, indent, parent, node);
+
+ if (node->is_leaf)
+ {
+ if (((BplusLeaf*) node)->right != NULL)
+ fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->right);
+ if (((BplusLeaf*) node)->left != NULL)
+ fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->left);
+ }
+
+ for (size_t i = 0; i < node->length; ++i)
+ {
+ if (node->is_leaf)
+ bplus_value_print(node, i, bplus_key_at(node, i), bplus_value_at(node, i), 2);
+ else
+ bplus_node_print(node, bplus_key_at(node, i), bplus_node_at(node, i), depth + 2);
+
+ }
+}
+
+int bplus_tree_print(BplusTree const* const tree, char const* format, ...)
+{
+ static int count = 0;
+
+ fprintf(stderr, "echo 'digraph {");
+ fprintf(stderr, "graph[ordering=\"out\"];\n");
+ fprintf(stderr, "node[width=0.2,height=0.2,fixedsize=true,fontsize=6,fontcolor=\"#990000\",shape=plaintext];");
+ fprintf(stderr, "edge[arrowsize=0.1,fontsize=6];");
+
+ BplusNode* node = tree->root;
+ fprintf(stderr, "n%p[label=\"0\"];", node);
+ if (node->is_leaf)
+ {
+ if (((BplusLeaf*) node)->right != NULL)
+ fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->right);
+ if (((BplusLeaf*) node)->left != NULL)
+ fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->left);
+ }
+
+ for (size_t i = 0; i < node->length; ++i)
+ {
+ if (node->is_leaf)
+ bplus_value_print(node, i, bplus_key_at(node, i), bplus_value_at(node, i), 2);
+ else
+ bplus_node_print(node, bplus_key_at(node, i), bplus_node_at(node, i), 2);
+
+ }
+
+ va_list vargs;
+ va_start(vargs, format);
+ vfprintf(stderr, format, vargs);
+ va_end(vargs);
+
+ fprintf(stderr, "}'| dot -T png -o tree-%d.png\n", count);
+ count++;
+ return 0;
+}
+
+int bplus_iterator_print(BplusTree const* tree, BplusIterator const* iterator)
+{
+ bplus_tree_print(tree,
+ "label=\"iterator\"; i[fontcolor=\"#009900\",label=\"i\"];"
+ "n%p_%zu->i[label=\"from\"];"
+ "n%p_%zu->i[color=\"#009900\"];"
+ "n%p_%zu->i[label=\"to\"];",
+ iterator->leaf_from, iterator->item_from - iterator->leaf_from->node.items,
+ iterator->leaf, iterator->item - iterator->leaf->node.items,
+ iterator->leaf_to, iterator->item_to - iterator->leaf_to->node.items - 1);
+
+ return 0;
+}
diff --git a/Algorithms/bplus-tree/src/bplus_tree_private.h b/Algorithms/bplus-tree/src/bplus_tree_private.h
new file mode 100644
index 0000000..97b873f
--- /dev/null
+++ b/Algorithms/bplus-tree/src/bplus_tree_private.h
@@ -0,0 +1,53 @@
+/**
+ * Distributed under the Boost Software License, Version 1.0.
+ * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt
+ */
+
+#ifndef __BPLUS_TREE_PRIVATE_H__
+#define __BPLUS_TREE_PRIVATE_H__
+
+#include "bplus_tree.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif // ifdef __cplusplus
+
+#ifndef BPLUS_TREE_ORDER
+# define BPLUS_TREE_ORDER 32
+#endif /* ifndef BPLUS_TREE_ORDER */
+
+typedef struct _BplusNode BplusNode;
+typedef struct _BplusLeaf BplusLeaf;
+typedef struct _BplusPath BplusPath;
+
+struct _BplusPath
+{
+ size_t length;
+ size_t index[16];
+ BplusNode* leaf;
+};
+
+struct _BplusTree
+{
+ BplusNode* root;
+
+ BplusLeaf* first;
+ BplusLeaf* last;
+
+ size_t height;
+ gboolean allow_duplicate_keys;
+
+#ifdef BPLUS_TREE_GATHER_STATS
+ size_t node_count;
+ size_t leaf_count;
+ size_t underflow_count;
+ size_t overflow_count;
+#endif /* ifdef BPLUS_TREE_GATHER_STATS */
+};
+
+#ifdef __cplusplus
+}
+#endif // ifdef __cplusplus
+
+#endif // ifndef __BPLUS_TREE_PRIVATE_H__
generated by cgit v1.2.3 (git 2.25.1) at 2026-06-13 11:56:26 +0000