summaryrefslogtreecommitdiff
path: root/Algorithms/bplus-tree/test
diff options
context:
space:
mode:
Diffstat (limited to 'Algorithms/bplus-tree/test')
-rw-r--r--Algorithms/bplus-tree/test/bplus_tree_all.c14
-rw-r--r--Algorithms/bplus-tree/test/bplus_tree_test.c560
2 files changed, 574 insertions, 0 deletions
diff --git a/Algorithms/bplus-tree/test/bplus_tree_all.c b/Algorithms/bplus-tree/test/bplus_tree_all.c
new file mode 100644
index 0000000..1186dc8
--- /dev/null
+++ b/Algorithms/bplus-tree/test/bplus_tree_all.c
@@ -0,0 +1,14 @@
+/**
+ * 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.c"
+#include "bplus_search.c"
+#include "bplus_remove.c"
+#include "bplus_rebalance.c"
+#include "bplus_node.c"
+#include "bplus_leaf.c"
+#include "bplus_iterator.c"
+#include "bplus_insert.c"
+#include "bplus_foreach.c"
diff --git a/Algorithms/bplus-tree/test/bplus_tree_test.c b/Algorithms/bplus-tree/test/bplus_tree_test.c
new file mode 100644
index 0000000..5ddd69f
--- /dev/null
+++ b/Algorithms/bplus-tree/test/bplus_tree_test.c
@@ -0,0 +1,560 @@
+/**
+ * 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_ORDER
+# define BPLUS_TREE_ORDER 4
+#endif /* ifndef BPLUS_TREE_ORDER */
+
+#include "bplus_tree_all.c"
+
+void test_search_key_index(void)
+{
+ BplusTree tree;
+ BplusNode node;
+
+ node.length = 0;
+ g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0);
+
+ g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0);
+
+ bplus_key_at(&node, 0) = 1;
+ node.length++;
+ g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 1) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 2) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0);
+
+ bplus_key_at(&node, 0) = 1;
+ bplus_key_at(&node, 1) = 1;
+ node.length++;
+ g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1);
+ g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1);
+ g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 1);
+
+ bplus_key_at(&node, 0) = 1;
+ bplus_key_at(&node, 1) = 1;
+ bplus_key_at(&node, 2) = 2;
+ node.length++;
+ g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1);
+ g_assert(bplus_node_get_key_index(&tree, &node, 2) == 2);
+ g_assert(bplus_node_get_key_index(&tree, &node, 3) == 2);
+ g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 2);
+
+ bplus_key_at(&node, 0) = 1;
+ bplus_key_at(&node, 1) = 1;
+ bplus_key_at(&node, 2) = 3;
+ bplus_key_at(&node, 3) = 3;
+ node.length++;
+ g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1);
+ g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1);
+ g_assert(bplus_node_get_key_index(&tree, &node, 3) == 3);
+ g_assert(bplus_node_get_key_index(&tree, &node, 4) == 3);
+ g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 3);
+
+ bplus_key_at(&node, 0) = 1;
+ bplus_key_at(&node, 1) = 1;
+ bplus_key_at(&node, 2) = 1;
+ bplus_key_at(&node, 3) = 1;
+ g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0);
+ g_assert(bplus_node_get_key_index(&tree, &node, 1) == 3);
+ g_assert(bplus_node_get_key_index(&tree, &node, 2) == 3);
+ g_assert(bplus_node_get_key_index(&tree, &node, 3) == 3);
+ g_assert(bplus_node_get_key_index(&tree, &node, 4) == 3);
+ g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 3);
+
+ // bplus_key_at(&node, 0) = 1;
+ // bplus_key_at(&node, 1) = 2;
+ // bplus_key_at(&node, 2) = 3;
+ // bplus_key_at(&node, 3) = 4;
+ // bplus_key_at(&node, 4) = 4;
+ // bplus_key_at(&node, 5) = 4;
+ // bplus_key_at(&node, 6) = 6;
+ // bplus_key_at(&node, 7) = 6;
+ // bplus_key_at(&node, 8) = 9;
+ // node.length = 9;
+ // g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0);
+ // g_assert(bplus_node_get_key_index(&tree, &node, 1) == 0);
+ // g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1);
+ // g_assert(bplus_node_get_key_index(&tree, &node, 3) == 2);
+ // g_assert(bplus_node_get_key_index(&tree, &node, 4) == 5);
+ // g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 8);
+} /* test_search_key_index */
+
+void test_search_bplus_tree_new(void)
+{
+ BplusTree* tree = bplus_tree_new();
+
+ g_assert(tree != NULL);
+ g_assert(tree->root != NULL);
+ g_assert((void*) tree->root == (void*) tree->first);
+ g_assert((void*) tree->root == (void*) tree->last);
+
+ g_assert(tree->root->is_leaf);
+ g_assert(tree->root->parent == NULL);
+ g_assert(tree->root->length == 0);
+
+ g_assert(tree->first->left == NULL);
+ g_assert(tree->first->right == NULL);
+
+ bplus_tree_destroy(tree);
+}
+
+void test_search_bplus_node_insert_at(void)
+{
+ // BplusTree* tree = bplus_tree_new();
+
+ // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 1);
+
+ // g_assert(tree->root->is_leaf);
+ // g_assert(tree->root->parent == NULL);
+ // g_assert(tree->root->length == 1);
+
+ // g_assert(bplus_key_first(tree->root) == 0);
+ // g_assert(bplus_value_first(tree->root) == (void*) 1);
+
+ // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 2);
+ // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 3);
+
+ // g_assert(bplus_value_first(tree->root) == (void*) 3);
+ // g_assert(bplus_value_at(tree->root, 1) == (void*) 2);
+ // g_assert(bplus_value_at(tree->root, 2) == (void*) 1);
+
+ // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 4);
+
+ // /* We should have splitted here */
+ // g_assert(!tree->root->is_leaf);
+ // g_assert(tree->root->parent == NULL);
+ // g_assert(tree->root->length == 2);
+
+ // g_assert(bplus_key_first(tree->root) == 0);
+ // BplusNode* left = (BplusNode*) bplus_value_first(tree->root);
+ // g_assert(left != NULL);
+
+ // g_assert(bplus_key_at(tree->root, 1) == 0);
+ // BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1);
+ // g_assert(right != NULL);
+
+ // g_assert(left->is_leaf);
+ // g_assert(left->parent == tree->root);
+ // g_assert(left->length == 2);
+ // g_assert(bplus_key_first(left) == 0);
+ // g_assert(bplus_value_first(left) == (void*) 4);
+ // g_assert(bplus_key_at(left, 1) == 0);
+ // g_assert(bplus_value_at(left, 1) == (void*) 3);
+
+ // g_assert(right->is_leaf);
+ // g_assert(right->parent == tree->root);
+ // g_assert(right->length == 2);
+ // g_assert(bplus_key_first(right) == 0);
+ // g_assert(bplus_value_first(right) == (void*) 2);
+ // g_assert(bplus_key_at(right, 1) == 0);
+ // g_assert(bplus_value_at(right, 1) == (void*) 1);
+
+ // bplus_node_insert_at(tree, left, 2, 0, (void*) 1);
+ // bplus_node_insert_at(tree, left, 2, 0, (void*) 2);
+
+ // g_assert(tree->root->length == 3);
+
+ // g_assert(bplus_key_at(tree->root, 1) == 0);
+ // BplusNode* middle = (BplusNode*) bplus_value_at(tree->root, 1);
+ // g_assert(middle != NULL);
+ // g_assert(middle != left);
+ // g_assert(middle != right);
+
+ // g_assert(bplus_key_first(tree->root) == 0);
+ // g_assert(bplus_value_first(tree->root) == left);
+ // g_assert(bplus_key_at(tree->root, 1) == 0);
+ // g_assert(bplus_value_at(tree->root, 1) == middle);
+ // g_assert(bplus_key_at(tree->root, 2) == 0);
+ // g_assert(bplus_value_at(tree->root, 2) == right);
+
+ // g_assert(middle->is_leaf);
+ // g_assert(middle->parent == tree->root);
+ // g_assert(middle->length == 2);
+ // g_assert(bplus_key_first(middle) == 0);
+ // g_assert(bplus_value_first(middle) == (void*) 2);
+ // g_assert(bplus_key_at(middle, 1) == 0);
+ // g_assert(bplus_value_at(middle, 1) == (void*) 1);
+
+ // g_assert(tree->first == (BplusLeaf*) left);
+ // g_assert(tree->last == (BplusLeaf*) right);
+ // g_assert(((BplusLeaf*) left)->right == (BplusLeaf*) middle);
+ // g_assert(((BplusLeaf*) right)->left == (BplusLeaf*) middle);
+ // g_assert(((BplusLeaf*) left)->left == NULL);
+ // g_assert(((BplusLeaf*) right)->right == NULL);
+ // g_assert(((BplusLeaf*) middle)->left == (BplusLeaf*) left);
+ // g_assert(((BplusLeaf*) middle)->right == (BplusLeaf*) right);
+
+ // bplus_tree_destroy(tree);
+} /* test_search_bplus_node_insert_at */
+
+void test_search_bplus_tree_insert_k0(void)
+{
+ BplusTree* tree = bplus_tree_new();
+
+ bplus_tree_insert(tree, 0, (void*) 1);
+
+ g_assert(tree->root->is_leaf);
+ g_assert(tree->root->parent == NULL);
+ g_assert(tree->root->length == 1);
+
+ g_assert(bplus_key_first(tree->root) == 0);
+ g_assert(bplus_value_first(tree->root) == (void*) 1);
+
+ bplus_tree_insert(tree, 0, (void*) 2);
+ bplus_tree_insert(tree, 0, (void*) 3);
+
+ g_assert(bplus_value_first(tree->root) == (void*) 1);
+ g_assert(bplus_value_at(tree->root, 1) == (void*) 2);
+ g_assert(bplus_value_at(tree->root, 2) == (void*) 3);
+
+ bplus_tree_insert(tree, 0, (void*) 4);
+
+ /* We should have splitted here */
+ g_assert(!tree->root->is_leaf);
+ g_assert(tree->root->parent == NULL);
+ g_assert(tree->root->length == 2);
+
+ g_assert(bplus_key_first(tree->root) == 0);
+ BplusNode* left = (BplusNode*) bplus_value_first(tree->root);
+ g_assert(left != NULL);
+
+ g_assert(bplus_key_at(tree->root, 1) == 0);
+ BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1);
+ g_assert(right != NULL);
+
+ g_assert(left->is_leaf);
+ g_assert(left->parent == tree->root);
+ g_assert(left->length == 2);
+ g_assert(bplus_key_first(left) == 0);
+ g_assert(bplus_value_first(left) == (void*) 1);
+ g_assert(bplus_key_at(left, 1) == 0);
+ g_assert(bplus_value_at(left, 1) == (void*) 2);
+
+ g_assert(right->is_leaf);
+ g_assert(right->parent == tree->root);
+ g_assert(right->length == 2);
+ g_assert(bplus_key_first(right) == 0);
+ g_assert(bplus_value_first(right) == (void*) 3);
+ g_assert(bplus_key_at(right, 1) == 0);
+ g_assert(bplus_value_at(right, 1) == (void*) 4);
+
+ bplus_tree_insert(tree, 0, (void*) 5);
+ bplus_tree_insert(tree, 0, (void*) 6);
+
+ g_assert(tree->root->length == 3);
+
+ g_assert(bplus_key_at(tree->root, 2) == 0);
+ BplusNode* middle = right;
+ right = (BplusNode*) bplus_value_at(tree->root, 2);
+ g_assert(middle != NULL);
+ g_assert(middle != left);
+ g_assert(middle != right);
+
+ g_assert(bplus_key_first(tree->root) == 0);
+ g_assert(bplus_value_first(tree->root) == left);
+ g_assert(bplus_key_at(tree->root, 1) == 0);
+ g_assert(bplus_value_at(tree->root, 1) == middle);
+ g_assert(bplus_key_at(tree->root, 2) == 0);
+ g_assert(bplus_value_at(tree->root, 2) == right);
+
+ g_assert(right->is_leaf);
+ g_assert(right->parent == tree->root);
+ g_assert(right->length == 2);
+ g_assert(bplus_key_first(right) == 0);
+ g_assert(bplus_value_first(right) == (void*) 5);
+ g_assert(bplus_key_at(right, 1) == 0);
+ g_assert(bplus_value_at(right, 1) == (void*) 6);
+
+ g_assert(tree->first == (BplusLeaf*) left);
+ g_assert(tree->last == (BplusLeaf*) right);
+ g_assert(((BplusLeaf*) left)->right == (BplusLeaf*) middle);
+ g_assert(((BplusLeaf*) right)->left == (BplusLeaf*) middle);
+ g_assert(((BplusLeaf*) left)->left == NULL);
+ g_assert(((BplusLeaf*) right)->right == NULL);
+ g_assert(((BplusLeaf*) middle)->left == (BplusLeaf*) left);
+ g_assert(((BplusLeaf*) middle)->right == (BplusLeaf*) right);
+
+ bplus_tree_destroy(tree);
+} /* test_search_bplus_tree_insert_k0 */
+
+void test_search_bplus_tree_insert_k(void)
+{
+ BplusTree* tree = bplus_tree_new();
+
+ bplus_tree_insert(tree, 3, (void*) 1);
+
+ g_assert(tree->root->is_leaf);
+ g_assert(tree->root->parent == NULL);
+ g_assert(tree->root->length == 1);
+
+ g_assert(bplus_key_first(tree->root) == 3);
+ g_assert(bplus_value_first(tree->root) == (void*) 1);
+
+ bplus_tree_insert(tree, 1, (void*) 2);
+ g_assert(bplus_value_first(tree->root) == (void*) 2);
+ g_assert(bplus_value_at(tree->root, 1) == (void*) 1);
+
+ bplus_tree_insert(tree, 2, (void*) 3);
+
+ g_assert(bplus_value_first(tree->root) == (void*) 2);
+ g_assert(bplus_value_at(tree->root, 1) == (void*) 3);
+ g_assert(bplus_value_at(tree->root, 2) == (void*) 1);
+
+ bplus_tree_insert(tree, 2, (void*) 4);
+
+ /* We should have splitted here */
+ g_assert(!tree->root->is_leaf);
+ g_assert(tree->root->parent == NULL);
+ g_assert(tree->root->length == 2);
+
+ g_assert(bplus_key_first(tree->root) == 1);
+ BplusNode* left = (BplusNode*) bplus_value_first(tree->root);
+ g_assert(left != NULL);
+
+ g_assert(bplus_key_at(tree->root, 1) == 2);
+ BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1);
+ g_assert(right != NULL);
+
+ g_assert(left->is_leaf);
+ g_assert(left->parent == tree->root);
+ g_assert(left->length == 2);
+ g_assert(bplus_key_first(left) == 1);
+ g_assert(bplus_value_first(left) == (void*) 2);
+ g_assert(bplus_key_at(left, 1) == 2);
+ g_assert(bplus_value_at(left, 1) == (void*) 3);
+
+ g_assert(right->is_leaf);
+ g_assert(right->parent == tree->root);
+ g_assert(right->length == 2);
+ g_assert(bplus_key_first(right) == 2);
+ g_assert(bplus_value_first(right) == (void*) 4);
+ g_assert(bplus_key_at(right, 1) == 3);
+ g_assert(bplus_value_at(right, 1) == (void*) 1);
+
+ g_assert(bplus_key_first(tree->root) == 1);
+ g_assert(bplus_key_at(tree->root, 1) == 2);
+
+ bplus_tree_insert(tree, 3, (void*) 5);
+ bplus_tree_insert(tree, 3, (void*) 6);
+ g_assert(tree->root->length == 3);
+
+ /* Should not have splitted */
+ g_assert(bplus_value_first(tree->root) == (void*) left);
+ g_assert(bplus_value_at(tree->root, 1) == (void*) right);
+
+ bplus_tree_insert(tree, 2, (void*) 7);
+ g_assert(tree->root->length == 3);
+ g_assert(bplus_key_first(tree->root) == 1);
+ g_assert(bplus_key_at(tree->root, 1) == 2);
+ g_assert(bplus_key_at(tree->root, 2) == 3);
+
+ // /* Should split root again */
+ // bplus_tree_insert(tree, 4, (void*) 8);
+ // g_assert(tree->root->length == 3);
+ // g_assert(bplus_value_first(tree->root) != (void*) left);
+ // g_assert(bplus_value_at(tree->root, 1) != (void*) right);
+
+ // g_assert(bplus_key_first(tree->root) == 1);
+ // g_assert(bplus_key_at(tree->root, 1) == 3);
+
+ /* This should propagate 0 up to root */
+ bplus_tree_insert(tree, 0, (void*) 9);
+ g_assert((bplus_key_first(tree->root) == 0));
+
+ // for (int i = 0; i < 10000; ++i) {
+ // bplus_tree_insert(tree, random(), (void*) i + 1);
+ // }
+
+ bplus_tree_destroy(tree);
+} /* test_search_bplus_tree_insert_k */
+
+void test_search_bplus_tree_remove_k(void)
+{
+ BplusTree* tree = bplus_tree_new();
+
+ bplus_tree_insert(tree, 3, (void*) 1);
+ bplus_tree_insert(tree, 1, (void*) 2);
+ bplus_tree_insert(tree, 2, (void*) 3);
+ bplus_tree_insert(tree, 2, (void*) 4);
+ bplus_tree_insert(tree, 3, (void*) 5);
+ bplus_tree_insert(tree, 3, (void*) 6);
+ bplus_tree_insert(tree, 2, (void*) 7);
+ bplus_tree_insert(tree, 4, (void*) 8);
+ bplus_tree_insert(tree, 0, (void*) 9);
+
+ // bplus_tree_print(tree, "label=\"remove(0)\";");
+ bplus_tree_remove(tree, 0);
+
+ // bplus_tree_print(tree, "label=\"remove(1)\";");
+ bplus_tree_remove(tree, 1);
+
+ // bplus_tree_print(tree, "label=\"remove(4)\";");
+ bplus_tree_remove(tree, 4);
+
+ // bplus_tree_print(tree, "label=\"remove(3)\";");
+ bplus_tree_remove(tree, 3);
+
+ // bplus_tree_print(tree, "label=\"remove(2)\";");
+ bplus_tree_remove(tree, 2);
+
+ // bplus_tree_print(tree, "label=\"remove(3)\";");
+ bplus_tree_remove(tree, 3);
+
+ // bplus_tree_print(tree, "label=\"remove(3)\";");
+ bplus_tree_remove(tree, 3);
+
+ // bplus_tree_print(tree, "label=\"remove(2)\";");
+ bplus_tree_remove(tree, 2);
+
+ // bplus_tree_print(tree, "label=\"remove(2)\";");
+ bplus_tree_remove(tree, 2);
+
+ // bplus_tree_print(tree, "");
+
+ bplus_tree_destroy(tree);
+} /* test_search_bplus_tree_insert_k */
+
+void test_search_bplus_tree_iterator(void)
+{
+ BplusTree* tree = bplus_tree_new();
+
+ bplus_tree_insert(tree, 3, (void*) 1);
+ bplus_tree_insert(tree, 1, (void*) 2);
+ bplus_tree_insert(tree, 2, (void*) 3);
+ bplus_tree_insert(tree, 2, (void*) 4);
+ bplus_tree_insert(tree, 3, (void*) 5);
+ bplus_tree_insert(tree, 3, (void*) 6);
+ bplus_tree_insert(tree, 2, (void*) 7);
+ bplus_tree_insert(tree, 4, (void*) 8);
+ bplus_tree_insert(tree, 0, (void*) 9);
+
+ BplusKey keys[] = { 0, 1, 2, 2, 2, 3, 3, 3, 4 };
+ BplusValue values[] = { (BplusValue*) 9, (BplusValue*) 2, (BplusValue*) 3, (BplusValue*) 4, (BplusValue*) 7, (BplusValue*) 1, (BplusValue*) 5, (BplusValue*) 6, (BplusValue*) 8 };
+
+ BplusIterator* iterator = bplus_tree_first(tree);
+ for (int i = 0; i < 9; ++i)
+ {
+ BplusItem const* item = bplus_iterator_get_item(iterator);
+ g_assert(item->key == keys[i]);
+ g_assert(item->value == values[i]);
+ if (i < 8)
+ bplus_iterator_next(iterator);
+ }
+ g_assert(!bplus_iterator_next(iterator));
+ bplus_iterator_destroy(iterator);
+
+ iterator = bplus_iterator_to_key(tree, 2);
+ for (int i = 0; i < 5; ++i)
+ {
+ BplusItem const* item = bplus_iterator_get_item(iterator);
+ g_assert(item->key == keys[i]);
+ g_assert(item->value == values[i]);
+ if (i < 4)
+ bplus_iterator_next(iterator);
+ }
+ g_assert(!bplus_iterator_next(iterator));
+ for (int i = 4; i >= 0; --i)
+ {
+ BplusItem const* item = bplus_iterator_get_item(iterator);
+ g_assert(item->key == keys[i]);
+ g_assert(item->value == values[i]);
+ if (i > 0)
+ bplus_iterator_previous(iterator);
+ }
+ g_assert(!bplus_iterator_previous(iterator));
+ bplus_iterator_destroy(iterator);
+
+ iterator = bplus_iterator_for_key(tree, 2);
+ for (int i = 0; i < 3; ++i)
+ {
+ BplusItem const* item = bplus_iterator_get_item(iterator);
+ g_assert(item->key == keys[i + 2]);
+ g_assert(item->value == values[i + 2]);
+ if (i < 2)
+ bplus_iterator_next(iterator);
+ }
+ g_assert(!bplus_iterator_next(iterator));
+ bplus_iterator_destroy(iterator);
+
+ iterator = bplus_iterator_from_key(tree, 2);
+ for (int i = 0; i < 7; ++i)
+ {
+ BplusItem const* item = bplus_iterator_get_item(iterator);
+ g_assert(item->key == keys[i + 2]);
+ g_assert(item->value == values[i + 2]);
+ if (i < 6)
+ bplus_iterator_next(iterator);
+ }
+ g_assert(!bplus_iterator_next(iterator));
+ bplus_iterator_destroy(iterator);
+
+ iterator = bplus_iterator_for_key_range(tree, 2, 3);
+ for (int i = 0; i < 6; ++i)
+ {
+ BplusItem const* item = bplus_iterator_get_item(iterator);
+ g_assert(item->key == keys[i + 2]);
+ g_assert(item->value == values[i + 2]);
+ if (i < 5)
+ bplus_iterator_next(iterator);
+ }
+ g_assert(!bplus_iterator_next(iterator));
+ bplus_iterator_destroy(iterator);
+
+ iterator = bplus_iterator_for_key_range(tree, 3, 2);
+ for (int i = 0; i < 6; ++i)
+ {
+ BplusItem const* item = bplus_iterator_get_item(iterator);
+ g_assert(item->key == keys[i + 2]);
+ g_assert(item->value == values[i + 2]);
+ if (i < 5)
+ bplus_iterator_next(iterator);
+ }
+ g_assert(!bplus_iterator_next(iterator));
+ bplus_iterator_destroy(iterator);
+
+ iterator = bplus_iterator_for_key_range(tree, 4, 5);
+ for (int i = 0; i < 1; ++i)
+ {
+ BplusItem const* item = bplus_iterator_get_item(iterator);
+ g_assert(item->key == keys[i + 8]);
+ g_assert(item->value == values[i + 8]);
+ }
+ g_assert(!bplus_iterator_next(iterator));
+ bplus_iterator_destroy(iterator);
+
+ iterator = bplus_iterator_for_key_range(tree, 5, 5);
+ g_assert(bplus_iterator_get_item(iterator) == NULL);
+ g_assert(!bplus_iterator_next(iterator));
+ bplus_iterator_destroy(iterator);
+
+ iterator = bplus_iterator_for_key_range(tree, 5, 6);
+ g_assert(bplus_iterator_get_item(iterator) == NULL);
+ g_assert(!bplus_iterator_next(iterator));
+ bplus_iterator_destroy(iterator);
+
+ bplus_tree_destroy(tree);
+} /* test_search_bplus_tree_iterator */
+
+int main(int argc, char** argv)
+{
+ g_test_init(&argc, &argv, NULL);
+
+ g_test_add_func("/tree/search_key_index", test_search_key_index);
+ g_test_add_func("/tree/new", test_search_bplus_tree_new);
+ g_test_add_func("/tree/insert_at", test_search_bplus_node_insert_at);
+ g_test_add_func("/tree/insert_k0", test_search_bplus_tree_insert_k0);
+ g_test_add_func("/tree/insert_k", test_search_bplus_tree_insert_k);
+ g_test_add_func("/tree/remove_k", test_search_bplus_tree_remove_k);
+ g_test_add_func("/tree/iterator", test_search_bplus_tree_iterator);
+
+ g_test_run();
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-06-13 13:23:35 +0000