summaryrefslogtreecommitdiffstats
path: root/vespalib/src/tests/btree
diff options
context:
space:
mode:
Diffstat (limited to 'vespalib/src/tests/btree')
-rw-r--r--vespalib/src/tests/btree/.gitignore5
-rw-r--r--vespalib/src/tests/btree/CMakeLists.txt29
-rw-r--r--vespalib/src/tests/btree/btree_test.cpp1526
-rw-r--r--vespalib/src/tests/btree/btreeaggregation_test.cpp1157
-rw-r--r--vespalib/src/tests/btree/frozenbtree_test.cpp469
-rw-r--r--vespalib/src/tests/btree/iteratespeed.cpp212
6 files changed, 3398 insertions, 0 deletions
diff --git a/vespalib/src/tests/btree/.gitignore b/vespalib/src/tests/btree/.gitignore
new file mode 100644
index 00000000000..4dc55d5704a
--- /dev/null
+++ b/vespalib/src/tests/btree/.gitignore
@@ -0,0 +1,5 @@
+iteratespeed
+vespalib_btree_test_app
+vespalib_btreeaggregation_test_app
+vespalib_frozenbtree_test_app
+vespalib_iteratespeed_app
diff --git a/vespalib/src/tests/btree/CMakeLists.txt b/vespalib/src/tests/btree/CMakeLists.txt
new file mode 100644
index 00000000000..b6bdcb5160e
--- /dev/null
+++ b/vespalib/src/tests/btree/CMakeLists.txt
@@ -0,0 +1,29 @@
+# Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_btree_test_app TEST
+ SOURCES
+ btree_test.cpp
+ DEPENDS
+ vespalib
+)
+vespa_add_test(NAME vespalib_btree_test_app COMMAND vespalib_btree_test_app)
+vespa_add_executable(vespalib_frozenbtree_test_app TEST
+ SOURCES
+ frozenbtree_test.cpp
+ DEPENDS
+ vespalib
+)
+vespa_add_test(NAME vespalib_frozenbtree_test_app COMMAND vespalib_frozenbtree_test_app)
+vespa_add_executable(vespalib_btreeaggregation_test_app TEST
+ SOURCES
+ btreeaggregation_test.cpp
+ DEPENDS
+ vespalib
+)
+vespa_add_test(NAME vespalib_btreeaggregation_test_app COMMAND vespalib_btreeaggregation_test_app)
+vespa_add_executable(vespalib_iteratespeed_app
+ SOURCES
+ iteratespeed.cpp
+ DEPENDS
+ vespalib
+)
+vespa_add_test(NAME vespalib_iteratespeed_app COMMAND vespalib_iteratespeed_app BENCHMARK)
diff --git a/vespalib/src/tests/btree/btree_test.cpp b/vespalib/src/tests/btree/btree_test.cpp
new file mode 100644
index 00000000000..4090283c10f
--- /dev/null
+++ b/vespalib/src/tests/btree/btree_test.cpp
@@ -0,0 +1,1526 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+#include <vespa/log/log.h>
+LOG_SETUP("btree_test");
+#include <vespa/vespalib/testkit/testapp.h>
+#include <string>
+#include <vespa/vespalib/btree/btreeroot.h>
+#include <vespa/vespalib/btree/btreebuilder.h>
+#include <vespa/vespalib/btree/btreenodeallocator.h>
+#include <vespa/vespalib/btree/btree.h>
+#include <vespa/vespalib/btree/btreestore.h>
+#include <vespa/vespalib/util/rand48.h>
+
+#include <vespa/vespalib/btree/btreenodeallocator.hpp>
+#include <vespa/vespalib/btree/btreenode.hpp>
+#include <vespa/vespalib/btree/btreenodestore.hpp>
+#include <vespa/vespalib/btree/btreeiterator.hpp>
+#include <vespa/vespalib/btree/btreeroot.hpp>
+#include <vespa/vespalib/btree/btreebuilder.hpp>
+#include <vespa/vespalib/btree/btree.hpp>
+#include <vespa/vespalib/btree/btreestore.hpp>
+#include <vespa/vespalib/test/btree/btree_printer.h>
+
+using vespalib::GenerationHandler;
+using search::datastore::EntryRef;
+
+namespace search {
+namespace btree {
+
+namespace {
+
+template <typename T>
+std::string
+toStr(const T & v)
+{
+ std::stringstream ss;
+ ss << v;
+ return ss.str();
+}
+
+}
+
+typedef BTreeTraits<4, 4, 31, false> MyTraits;
+
+#define KEYWRAP
+
+#ifdef KEYWRAP
+
+// Force use of functor to compare keys.
+class WrapInt
+{
+public:
+ int _val;
+ WrapInt(int val) : _val(val) {}
+ WrapInt() : _val(0) {}
+ bool operator==(const WrapInt & rhs) const { return _val == rhs._val; }
+};
+
+std::ostream &
+operator<<(std::ostream &s, const WrapInt &i)
+{
+ s << i._val;
+ return s;
+}
+
+typedef WrapInt MyKey;
+class MyComp
+{
+public:
+ bool
+ operator()(const WrapInt &a, const WrapInt &b) const
+ {
+ return a._val < b._val;
+ }
+};
+
+#define UNWRAP(key) (key._val)
+#else
+typedef int MyKey;
+typedef std::less<int> MyComp;
+#define UNWRAP(key) (key)
+#endif
+
+typedef BTree<MyKey, std::string,
+ btree::NoAggregated,
+ MyComp, MyTraits> MyTree;
+typedef BTreeStore<MyKey, std::string,
+ btree::NoAggregated,
+ MyComp, MyTraits> MyTreeStore;
+typedef MyTree::Builder MyTreeBuilder;
+typedef MyTree::LeafNodeType MyLeafNode;
+typedef MyTree::InternalNodeType MyInternalNode;
+typedef MyTree::NodeAllocatorType MyNodeAllocator;
+typedef std::pair<MyKey, std::string> LeafPair;
+typedef MyTreeStore::KeyDataType MyKeyData;
+typedef MyTreeStore::KeyDataTypeRefPair MyKeyDataRefPair;
+
+typedef BTree<int, BTreeNoLeafData, btree::NoAggregated> SetTreeB;
+
+typedef BTreeTraits<16, 16, 10, false> LSeekTraits;
+typedef BTree<int, BTreeNoLeafData, btree::NoAggregated,
+ std::less<int>, LSeekTraits> SetTreeL;
+
+struct LeafPairLess {
+ bool operator()(const LeafPair & lhs, const LeafPair & rhs) const {
+ return UNWRAP(lhs.first) < UNWRAP(rhs.first);
+ }
+};
+
+template <typename ManagerType>
+void
+cleanup(GenerationHandler & g, ManagerType & m)
+{
+ m.freeze();
+ m.transferHoldLists(g.getCurrentGeneration());
+ g.incGeneration();
+ m.trimHoldLists(g.getFirstUsedGeneration());
+}
+
+template <typename ManagerType, typename NodeType>
+void
+cleanup(GenerationHandler & g,
+ ManagerType & m,
+ BTreeNode::Ref n1Ref, NodeType * n1,
+ BTreeNode::Ref n2Ref = BTreeNode::Ref(), NodeType * n2 = NULL)
+{
+ assert(ManagerType::isValidRef(n1Ref));
+ m.holdNode(n1Ref, n1);
+ if (n2 != NULL) {
+ assert(ManagerType::isValidRef(n2Ref));
+ m.holdNode(n2Ref, n2);
+ } else {
+ assert(!ManagerType::isValidRef(n2Ref));
+ }
+ cleanup(g, m);
+}
+
+template<typename Tree>
+bool
+assertTree(const std::string &exp, const Tree &t)
+{
+ std::stringstream ss;
+ test::BTreePrinter<std::stringstream, typename Tree::NodeAllocatorType> printer(ss, t.getAllocator());
+ printer.print(t.getRoot());
+ if (!EXPECT_EQUAL(exp, ss.str())) return false;
+ return true;
+}
+
+template <typename Tree>
+void
+populateTree(Tree &t, uint32_t count, uint32_t delta)
+{
+ uint32_t key = 1;
+ int32_t value = 101;
+ for (uint32_t i = 0; i < count; ++i) {
+ t.insert(key, value);
+ key += delta;
+ value += delta;
+ }
+}
+
+template <typename Tree>
+void
+populateLeafNode(Tree &t)
+{
+ populateTree(t, 4, 2);
+}
+
+
+class Test : public vespalib::TestApp {
+private:
+ template <typename LeafNodeType>
+ bool assertLeafNode(const std::string & exp, const LeafNodeType & n);
+ bool assertSeek(int skey, int ekey, const MyTree & tree);
+ bool assertSeek(int skey, int ekey, MyTree::Iterator & itr);
+ bool assertMemoryUsage(const vespalib::MemoryUsage & exp, const vespalib::MemoryUsage & act);
+
+ void
+ buildSubTree(const std::vector<LeafPair> &sub,
+ size_t numEntries);
+
+ void requireThatNodeInsertWorks();
+ void requireThatTreeInsertWorks();
+ void requireThatNodeSplitInsertWorks();
+ void requireThatNodeStealWorks();
+ void requireThatTreeRemoveStealWorks();
+ void requireThatNodeRemoveWorks();
+ void requireThatNodeLowerBoundWorks();
+ void requireThatWeCanInsertAndRemoveFromTree();
+ void requireThatSortedTreeInsertWorks();
+ void requireThatCornerCaseTreeFindWorks();
+ void requireThatBasicTreeIteratorWorks();
+ void requireThatTreeIteratorSeekWorks();
+ void requireThatTreeIteratorAssignWorks();
+ void requireThatMemoryUsageIsCalculated();
+ template <typename TreeType>
+ void requireThatLowerBoundWorksT();
+ void requireThatLowerBoundWorks();
+ template <typename TreeType>
+ void requireThatUpperBoundWorksT();
+ void requireThatUpperBoundWorks();
+ void requireThatUpdateOfKeyWorks();
+
+ void
+ requireThatSmallNodesWorks();
+
+ void
+ requireThatApplyWorks();
+
+ void
+ requireThatIteratorDistanceWorks(int numEntries);
+
+ void
+ requireThatIteratorDistanceWorks();
+public:
+ int Main() override;
+};
+
+template <typename LeafNodeType>
+bool
+Test::assertLeafNode(const std::string & exp, const LeafNodeType & n)
+{
+ std::stringstream ss;
+ ss << "[";
+ for (uint32_t i = 0; i < n.validSlots(); ++i) {
+ if (i > 0) ss << ",";
+ ss << n.getKey(i) << ":" << n.getData(i);
+ }
+ ss << "]";
+ if (!EXPECT_EQUAL(exp, ss.str())) return false;
+ return true;
+}
+
+bool
+Test::assertSeek(int skey, int ekey, const MyTree & tree)
+{
+ MyTree::Iterator itr = tree.begin();
+ return assertSeek(skey, ekey, itr);
+}
+
+bool
+Test::assertSeek(int skey, int ekey, MyTree::Iterator & itr)
+{
+ MyTree::Iterator bseekItr = itr;
+ MyTree::Iterator lseekItr = itr;
+ bseekItr.binarySeek(skey);
+ lseekItr.linearSeek(skey);
+ if (!EXPECT_EQUAL(ekey, UNWRAP(bseekItr.getKey()))) return false;
+ if (!EXPECT_EQUAL(ekey, UNWRAP(lseekItr.getKey()))) return false;
+ itr = bseekItr;
+ return true;
+}
+
+bool
+Test::assertMemoryUsage(const vespalib::MemoryUsage & exp, const vespalib::MemoryUsage & act)
+{
+ if (!EXPECT_EQUAL(exp.allocatedBytes(), act.allocatedBytes())) return false;
+ if (!EXPECT_EQUAL(exp.usedBytes(), act.usedBytes())) return false;
+ if (!EXPECT_EQUAL(exp.deadBytes(), act.deadBytes())) return false;
+ if (!EXPECT_EQUAL(exp.allocatedBytesOnHold(), act.allocatedBytesOnHold())) return false;
+ return true;
+}
+
+void
+Test::requireThatNodeInsertWorks()
+{
+ GenerationHandler g;
+ MyNodeAllocator m;
+ MyLeafNode::RefPair nPair = m.allocLeafNode();
+ MyLeafNode *n = nPair.data;
+ EXPECT_TRUE(n->isLeaf());
+ EXPECT_EQUAL(0u, n->validSlots());
+ n->insert(0, 20, "b");
+ EXPECT_TRUE(!n->isFull());
+ EXPECT_TRUE(!n->isAtLeastHalfFull());
+ EXPECT_TRUE(assertLeafNode("[20:b]", *n));
+ n->insert(0, 10, "a");
+ EXPECT_TRUE(!n->isFull());
+ EXPECT_TRUE(n->isAtLeastHalfFull());
+ EXPECT_TRUE(assertLeafNode("[10:a,20:b]", *n));
+ EXPECT_EQUAL(20, UNWRAP(n->getLastKey()));
+ EXPECT_EQUAL("b", n->getLastData());
+ n->insert(2, 30, "c");
+ EXPECT_TRUE(!n->isFull());
+ n->insert(3, 40, "d");
+ EXPECT_TRUE(n->isFull());
+ EXPECT_TRUE(n->isAtLeastHalfFull());
+ EXPECT_TRUE(assertLeafNode("[10:a,20:b,30:c,40:d]", *n));
+ cleanup(g, m, nPair.ref, n);
+}
+
+void
+Test::requireThatTreeInsertWorks()
+{
+ using Tree = BTree<MyKey, int32_t, btree::NoAggregated, MyComp, MyTraits>;
+ {
+ Tree t;
+ EXPECT_TRUE(assertTree("{}", t));
+ t.insert(20, 102);
+ EXPECT_TRUE(assertTree("{{20:102}}", t));
+ t.insert(10, 101);
+ EXPECT_TRUE(assertTree("{{10:101,20:102}}", t));
+ t.insert(30, 103);
+ t.insert(40, 104);
+ EXPECT_TRUE(assertTree("{{10:101,20:102,30:103,40:104}}", t));
+ }
+ { // new entry in current node
+ Tree t;
+ populateLeafNode(t);
+ t.insert(4, 104);
+ EXPECT_TRUE(assertTree("{{4,7}} -> "
+ "{{1:101,3:103,4:104},"
+ "{5:105,7:107}}", t));
+ }
+ { // new entry in split node
+ Tree t;
+ populateLeafNode(t);
+ t.insert(6, 106);
+ EXPECT_TRUE(assertTree("{{5,7}} -> "
+ "{{1:101,3:103,5:105},"
+ "{6:106,7:107}}", t));
+ }
+ { // new entry at end
+ Tree t;
+ populateLeafNode(t);
+ t.insert(8, 108);
+ EXPECT_TRUE(assertTree("{{5,8}} -> "
+ "{{1:101,3:103,5:105},"
+ "{7:107,8:108}}", t));
+ }
+ { // multi level node split
+ Tree t;
+ populateTree(t, 16, 2);
+ EXPECT_TRUE(assertTree("{{7,15,23,31}} -> "
+ "{{1:101,3:103,5:105,7:107},"
+ "{9:109,11:111,13:113,15:115},"
+ "{17:117,19:119,21:121,23:123},"
+ "{25:125,27:127,29:129,31:131}}", t));
+ t.insert(33, 133);
+ EXPECT_TRUE(assertTree("{{23,33}} -> "
+ "{{7,15,23},{29,33}} -> "
+ "{{1:101,3:103,5:105,7:107},"
+ "{9:109,11:111,13:113,15:115},"
+ "{17:117,19:119,21:121,23:123},"
+ "{25:125,27:127,29:129},"
+ "{31:131,33:133}}", t));
+ }
+ { // give to left node to avoid split
+ Tree t;
+ populateTree(t, 8, 2);
+ t.remove(5);
+ EXPECT_TRUE(assertTree("{{7,15}} -> "
+ "{{1:101,3:103,7:107},"
+ "{9:109,11:111,13:113,15:115}}", t));
+ t.insert(10, 110);
+ EXPECT_TRUE(assertTree("{{9,15}} -> "
+ "{{1:101,3:103,7:107,9:109},"
+ "{10:110,11:111,13:113,15:115}}", t));
+ }
+ { // give to left node to avoid split, and move to left node
+ Tree t;
+ populateTree(t, 8, 2);
+ t.remove(3);
+ t.remove(5);
+ EXPECT_TRUE(assertTree("{{7,15}} -> "
+ "{{1:101,7:107},"
+ "{9:109,11:111,13:113,15:115}}", t));
+ t.insert(8, 108);
+ EXPECT_TRUE(assertTree("{{9,15}} -> "
+ "{{1:101,7:107,8:108,9:109},"
+ "{11:111,13:113,15:115}}", t));
+ }
+ { // not give to left node to avoid split, but insert at end at left node
+ Tree t;
+ populateTree(t, 8, 2);
+ t.remove(5);
+ EXPECT_TRUE(assertTree("{{7,15}} -> "
+ "{{1:101,3:103,7:107},"
+ "{9:109,11:111,13:113,15:115}}", t));
+ t.insert(8, 108);
+ EXPECT_TRUE(assertTree("{{8,15}} -> "
+ "{{1:101,3:103,7:107,8:108},"
+ "{9:109,11:111,13:113,15:115}}", t));
+ }
+ { // give to right node to avoid split
+ Tree t;
+ populateTree(t, 8, 2);
+ t.remove(13);
+ EXPECT_TRUE(assertTree("{{7,15}} -> "
+ "{{1:101,3:103,5:105,7:107},"
+ "{9:109,11:111,15:115}}", t));
+ t.insert(4, 104);
+ EXPECT_TRUE(assertTree("{{5,15}} -> "
+ "{{1:101,3:103,4:104,5:105},"
+ "{7:107,9:109,11:111,15:115}}", t));
+ }
+ { // give to right node to avoid split and move to right node
+ using MyTraits6 = BTreeTraits<6, 6, 31, false>;
+ using Tree6 = BTree<MyKey, int32_t, btree::NoAggregated, MyComp, MyTraits6>;
+
+ Tree6 t;
+ populateTree(t, 12, 2);
+ t.remove(19);
+ t.remove(21);
+ t.remove(23);
+ EXPECT_TRUE(assertTree("{{11,17}} -> "
+ "{{1:101,3:103,5:105,7:107,9:109,11:111},"
+ "{13:113,15:115,17:117}}", t));
+ t.insert(10, 110);
+ EXPECT_TRUE(assertTree("{{7,17}} -> "
+ "{{1:101,3:103,5:105,7:107},"
+ "{9:109,10:110,11:111,13:113,15:115,17:117}}", t));
+ }
+}
+
+MyLeafNode::RefPair
+getLeafNode(MyNodeAllocator &allocator)
+{
+ MyLeafNode::RefPair nPair = allocator.allocLeafNode();
+ MyLeafNode *n = nPair.data;
+ n->insert(0, 1, "a");
+ n->insert(1, 3, "c");
+ n->insert(2, 5, "e");
+ n->insert(3, 7, "g");
+ return nPair;
+}
+
+void
+Test::requireThatNodeSplitInsertWorks()
+{
+ { // new entry in current node
+ GenerationHandler g;
+ MyNodeAllocator m;
+ MyLeafNode::RefPair nPair = getLeafNode(m);
+ MyLeafNode *n = nPair.data;
+ MyLeafNode::RefPair sPair = m.allocLeafNode();
+ MyLeafNode *s = sPair.data;
+ n->splitInsert(s, 2, 4, "d");
+ EXPECT_TRUE(assertLeafNode("[1:a,3:c,4:d]", *n));
+ EXPECT_TRUE(assertLeafNode("[5:e,7:g]", *s));
+ cleanup(g, m, nPair.ref, n, sPair.ref, s);
+ }
+ { // new entry in split node
+ GenerationHandler g;
+ MyNodeAllocator m;
+ MyLeafNode::RefPair nPair = getLeafNode(m);
+ MyLeafNode *n = nPair.data;
+ MyLeafNode::RefPair sPair = m.allocLeafNode();
+ MyLeafNode *s = sPair.data;
+ n->splitInsert(s, 3, 6, "f");
+ EXPECT_TRUE(assertLeafNode("[1:a,3:c,5:e]", *n));
+ EXPECT_TRUE(assertLeafNode("[6:f,7:g]", *s));
+ cleanup(g, m, nPair.ref, n, sPair.ref, s);
+ }
+ { // new entry at end
+ GenerationHandler g;
+ MyNodeAllocator m;
+ MyLeafNode::RefPair nPair = getLeafNode(m);
+ MyLeafNode *n = nPair.data;
+ MyLeafNode::RefPair sPair = m.allocLeafNode();
+ MyLeafNode *s = sPair.data;
+ n->splitInsert(s, 4, 8, "h");
+ EXPECT_TRUE(assertLeafNode("[1:a,3:c,5:e]", *n));
+ EXPECT_TRUE(assertLeafNode("[7:g,8:h]", *s));
+ cleanup(g, m, nPair.ref, n, sPair.ref, s);
+ }
+}
+
+struct BTreeStealTraits
+{
+ static const size_t LEAF_SLOTS = 6;
+ static const size_t INTERNAL_SLOTS = 6;
+ static const size_t PATH_SIZE = 20;
+ static const bool BINARY_SEEK = true;
+};
+
+void
+Test::requireThatNodeStealWorks()
+{
+ typedef BTreeLeafNode<int, std::string,
+ btree::NoAggregated, 6> MyStealNode;
+ typedef BTreeNodeAllocator<int, std::string,
+ btree::NoAggregated,
+ BTreeStealTraits::INTERNAL_SLOTS, BTreeStealTraits::LEAF_SLOTS>
+ MyStealManager;
+ { // steal all from left
+ GenerationHandler g;
+ MyStealManager m;
+ MyStealNode::RefPair nPair = m.allocLeafNode();
+ MyStealNode *n = nPair.data;
+ n->insert(0, 4, "d");
+ n->insert(1, 5, "e");
+ EXPECT_TRUE(!n->isAtLeastHalfFull());
+ MyStealNode::RefPair vPair = m.allocLeafNode();
+ MyStealNode *v = vPair.data;
+ v->insert(0, 1, "a");
+ v->insert(1, 2, "b");
+ v->insert(2, 3, "c");
+ n->stealAllFromLeftNode(v);
+ EXPECT_TRUE(n->isAtLeastHalfFull());
+ EXPECT_TRUE(assertLeafNode("[1:a,2:b,3:c,4:d,5:e]", *n));
+ cleanup(g, m, nPair.ref, n, vPair.ref, v);
+ }
+ { // steal all from right
+ GenerationHandler g;
+ MyStealManager m;
+ MyStealNode::RefPair nPair = m.allocLeafNode();
+ MyStealNode *n = nPair.data;
+ n->insert(0, 1, "a");
+ n->insert(1, 2, "b");
+ EXPECT_TRUE(!n->isAtLeastHalfFull());
+ MyStealNode::RefPair vPair = m.allocLeafNode();
+ MyStealNode *v = vPair.data;
+ v->insert(0, 3, "c");
+ v->insert(1, 4, "d");
+ v->insert(2, 5, "e");
+ n->stealAllFromRightNode(v);
+ EXPECT_TRUE(n->isAtLeastHalfFull());
+ EXPECT_TRUE(assertLeafNode("[1:a,2:b,3:c,4:d,5:e]", *n));
+ cleanup(g, m, nPair.ref, n, vPair.ref, v);
+ }
+ { // steal some from left
+ GenerationHandler g;
+ MyStealManager m;
+ MyStealNode::RefPair nPair = m.allocLeafNode();
+ MyStealNode *n = nPair.data;
+ n->insert(0, 5, "e");
+ n->insert(1, 6, "f");
+ EXPECT_TRUE(!n->isAtLeastHalfFull());
+ MyStealNode::RefPair vPair = m.allocLeafNode();
+ MyStealNode *v = vPair.data;
+ v->insert(0, 1, "a");
+ v->insert(1, 2, "b");
+ v->insert(2, 3, "c");
+ v->insert(3, 4, "d");
+ n->stealSomeFromLeftNode(v);
+ EXPECT_TRUE(n->isAtLeastHalfFull());
+ EXPECT_TRUE(v->isAtLeastHalfFull());
+ EXPECT_TRUE(assertLeafNode("[4:d,5:e,6:f]", *n));
+ EXPECT_TRUE(assertLeafNode("[1:a,2:b,3:c]", *v));
+ cleanup(g, m, nPair.ref, n, vPair.ref, v);
+ }
+ { // steal some from right
+ GenerationHandler g;
+ MyStealManager m;
+ MyStealNode::RefPair nPair = m.allocLeafNode();
+ MyStealNode *n = nPair.data;
+ n->insert(0, 1, "a");
+ n->insert(1, 2, "b");
+ EXPECT_TRUE(!n->isAtLeastHalfFull());
+ MyStealNode::RefPair vPair = m.allocLeafNode();
+ MyStealNode *v = vPair.data;
+ v->insert(0, 3, "c");
+ v->insert(1, 4, "d");
+ v->insert(2, 5, "e");
+ v->insert(3, 6, "f");
+ n->stealSomeFromRightNode(v);
+ EXPECT_TRUE(n->isAtLeastHalfFull());
+ EXPECT_TRUE(v->isAtLeastHalfFull());
+ EXPECT_TRUE(assertLeafNode("[1:a,2:b,3:c]", *n));
+ EXPECT_TRUE(assertLeafNode("[4:d,5:e,6:f]", *v));
+ cleanup(g, m, nPair.ref, n, vPair.ref, v);
+ }
+}
+
+void
+Test::requireThatTreeRemoveStealWorks()
+{
+ using MyStealTree = BTree<MyKey, int32_t,btree::NoAggregated, MyComp, BTreeStealTraits, NoAggrCalc>;
+ { // steal all from left
+ MyStealTree t;
+ t.insert(10, 110);
+ t.insert(20, 120);
+ t.insert(30, 130);
+ t.insert(40, 140);
+ t.insert(50, 150);
+ t.insert(60, 160);
+ t.insert(35, 135);
+ t.remove(35);
+ EXPECT_TRUE(assertTree("{{30,60}} -> "
+ "{{10:110,20:120,30:130},"
+ "{40:140,50:150,60:160}}", t));
+ t.remove(50);
+ EXPECT_TRUE(assertTree("{{10:110,20:120,30:130,40:140,60:160}}", t));
+ }
+ { // steal all from right
+ MyStealTree t;
+ t.insert(10, 110);
+ t.insert(20, 120);
+ t.insert(30, 130);
+ t.insert(40, 140);
+ t.insert(50, 150);
+ t.insert(60, 160);
+ t.insert(35, 135);
+ t.remove(35);
+ EXPECT_TRUE(assertTree("{{30,60}} -> "
+ "{{10:110,20:120,30:130},"
+ "{40:140,50:150,60:160}}", t));
+ t.remove(20);
+ EXPECT_TRUE(assertTree("{{10:110,30:130,40:140,50:150,60:160}}", t));
+ }
+ { // steal some from left
+ MyStealTree t;
+ t.insert(10, 110);
+ t.insert(20, 120);
+ t.insert(30, 130);
+ t.insert(60, 160);
+ t.insert(70, 170);
+ t.insert(80, 180);
+ t.insert(50, 150);
+ t.insert(40, 140);
+ EXPECT_TRUE(assertTree("{{50,80}} -> "
+ "{{10:110,20:120,30:130,40:140,50:150},"
+ "{60:160,70:170,80:180}}", t));
+ t.remove(60);
+ EXPECT_TRUE(assertTree("{{30,80}} -> "
+ "{{10:110,20:120,30:130},"
+ "{40:140,50:150,70:170,80:180}}", t));
+ }
+ { // steal some from right
+ MyStealTree t;
+ t.insert(10, 110);
+ t.insert(20, 120);
+ t.insert(30, 130);
+ t.insert(40, 140);
+ t.insert(50, 150);
+ t.insert(60, 160);
+ t.insert(70, 170);
+ t.insert(80, 180);
+ t.insert(90, 190);
+ t.remove(40);
+ EXPECT_TRUE(assertTree("{{30,90}} -> "
+ "{{10:110,20:120,30:130},"
+ "{50:150,60:160,70:170,80:180,90:190}}", t));
+ t.remove(20);
+ EXPECT_TRUE(assertTree("{{60,90}} -> "
+ "{{10:110,30:130,50:150,60:160},"
+ "{70:170,80:180,90:190}}", t));
+ }
+}
+
+void
+Test::requireThatNodeRemoveWorks()
+{
+ GenerationHandler g;
+ MyNodeAllocator m;
+ MyLeafNode::RefPair nPair = getLeafNode(m);
+ MyLeafNode *n = nPair.data;
+ n->remove(1);
+ EXPECT_TRUE(assertLeafNode("[1:a,5:e,7:g]", *n));
+ cleanup(g, m, nPair.ref, n);
+}
+
+void
+Test::requireThatNodeLowerBoundWorks()
+{
+ GenerationHandler g;
+ MyNodeAllocator m;
+ MyLeafNode::RefPair nPair = getLeafNode(m);
+ MyLeafNode *n = nPair.data;
+ EXPECT_EQUAL(1u, n->lower_bound(3, MyComp()));
+ EXPECT_FALSE(MyComp()(3, n->getKey(1u)));
+ EXPECT_EQUAL(0u, n->lower_bound(0, MyComp()));
+ EXPECT_TRUE(MyComp()(0, n->getKey(0u)));
+ EXPECT_EQUAL(1u, n->lower_bound(2, MyComp()));
+ EXPECT_TRUE(MyComp()(2, n->getKey(1u)));
+ EXPECT_EQUAL(3u, n->lower_bound(6, MyComp()));
+ EXPECT_TRUE(MyComp()(6, n->getKey(3u)));
+ EXPECT_EQUAL(4u, n->lower_bound(8, MyComp()));
+ cleanup(g, m, nPair.ref, n);
+}
+
+void
+generateData(std::vector<LeafPair> & data, size_t numEntries)
+{
+ data.reserve(numEntries);
+ Rand48 rnd;
+ rnd.srand48(10);
+ for (size_t i = 0; i < numEntries; ++i) {
+ int num = rnd.lrand48() % 10000000;
+ std::string str = toStr(num);
+ data.push_back(std::make_pair(num, str));
+ }
+}
+
+
+void
+Test::buildSubTree(const std::vector<LeafPair> &sub,
+ size_t numEntries)
+{
+ GenerationHandler g;
+ MyTree tree;
+ MyTreeBuilder builder(tree.getAllocator());
+
+ std::vector<LeafPair> sorted(sub.begin(), sub.begin() + numEntries);
+ std::sort(sorted.begin(), sorted.end(), LeafPairLess());
+ for (size_t i = 0; i < numEntries; ++i) {
+ int num = UNWRAP(sorted[i].first);
+ const std::string & str = sorted[i].second;
+ builder.insert(num, str);
+ }
+ tree.assign(builder);
+ assert(numEntries == tree.size());
+ assert(tree.isValid());
+ EXPECT_EQUAL(numEntries, tree.size());
+ EXPECT_TRUE(tree.isValid());
+ MyTree::Iterator itr = tree.begin();
+ MyTree::Iterator ritr = itr;
+ if (numEntries > 0) {
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ --ritr;
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(numEntries, ritr.position());
+ --ritr;
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(numEntries - 1, ritr.position());
+ } else {
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ --ritr;
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ }
+ for (size_t i = 0; i < numEntries; ++i) {
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(sorted[i].first, itr.getKey());
+ EXPECT_EQUAL(sorted[i].second, itr.getData());
+ ++itr;
+ }
+ EXPECT_TRUE(!itr.valid());
+ ritr = itr;
+ EXPECT_TRUE(!ritr.valid());
+ --ritr;
+ for (size_t i = 0; i < numEntries; ++i) {
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(sorted[numEntries - 1 - i].first, ritr.getKey());
+ EXPECT_EQUAL(sorted[numEntries - 1 - i].second, ritr.getData());
+ --ritr;
+ }
+ EXPECT_TRUE(!ritr.valid());
+}
+
+void
+Test::requireThatWeCanInsertAndRemoveFromTree()
+{
+ GenerationHandler g;
+ MyTree tree;
+ std::vector<LeafPair> exp;
+ std::vector<LeafPair> sorted;
+ size_t numEntries = 1000;
+ generateData(exp, numEntries);
+ sorted = exp;
+ std::sort(sorted.begin(), sorted.end(), LeafPairLess());
+ // insert entries
+ for (size_t i = 0; i < numEntries; ++i) {
+ int num = UNWRAP(exp[i].first);
+ const std::string & str = exp[i].second;
+ EXPECT_TRUE(!tree.find(num).valid());
+ //LOG(info, "insert[%zu](%d, %s)", i, num, str.c_str());
+ EXPECT_TRUE(tree.insert(num, str));
+ EXPECT_TRUE(!tree.insert(num, str));
+ for (size_t j = 0; j <= i; ++j) {
+ //LOG(info, "find[%zu](%d)", j, exp[j].first._val);
+ MyTree::Iterator itr = tree.find(exp[j].first);
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(exp[j].first, itr.getKey());
+ EXPECT_EQUAL(exp[j].second, itr.getData());
+ }
+ EXPECT_EQUAL(i + 1u, tree.size());
+ EXPECT_TRUE(tree.isValid());
+ buildSubTree(exp, i + 1);
+ }
+ //std::cout << "tree: " << tree.toString() << std::endl;
+
+ {
+ MyTree::Iterator itr = tree.begin();
+ MyTree::Iterator itre = itr;
+ MyTree::Iterator itre2;
+ MyTree::Iterator ritr = itr;
+ while (itre.valid())
+ ++itre;
+ if (numEntries > 0) {
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ --ritr;
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(numEntries, ritr.position());
+ --ritr;
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(numEntries - 1, ritr.position());
+ } else {
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ --ritr;
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ }
+ MyTree::Iterator pitr = itr;
+ for (size_t i = 0; i < numEntries; ++i) {
+ ssize_t si = i;
+ ssize_t sileft = numEntries - i;
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(i, itr.position());
+ EXPECT_EQUAL(sileft, itre - itr);
+ EXPECT_EQUAL(-sileft, itr - itre);
+ EXPECT_EQUAL(sileft, itre2 - itr);
+ EXPECT_EQUAL(-sileft, itr - itre2);
+ EXPECT_EQUAL(si, itr - tree.begin());
+ EXPECT_EQUAL(-si, tree.begin() - itr);
+ EXPECT_EQUAL(i != 0, itr - pitr);
+ EXPECT_EQUAL(-(i != 0), pitr - itr);
+ EXPECT_EQUAL(sorted[i].first, itr.getKey());
+ EXPECT_EQUAL(sorted[i].second, itr.getData());
+ pitr = itr;
+ ++itr;
+ ritr = itr;
+ --ritr;
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_TRUE(ritr == pitr);
+ }
+ EXPECT_TRUE(!itr.valid());
+ EXPECT_EQUAL(numEntries, itr.position());
+ ssize_t sNumEntries = numEntries;
+ EXPECT_EQUAL(sNumEntries, itr - tree.begin());
+ EXPECT_EQUAL(-sNumEntries, tree.begin() - itr);
+ EXPECT_EQUAL(1, itr - pitr);
+ EXPECT_EQUAL(-1, pitr - itr);
+ }
+ // compact full tree by calling incremental compaction methods in a loop
+ {
+ MyTree::NodeAllocatorType &manager = tree.getAllocator();
+ std::vector<uint32_t> toHold = manager.startCompact();
+ MyTree::Iterator itr = tree.begin();
+ tree.setRoot(itr.moveFirstLeafNode(tree.getRoot()));
+ while (itr.valid()) {
+ // LOG(info, "Leaf moved to %d", UNWRAP(itr.getKey()));
+ itr.moveNextLeafNode();
+ }
+ manager.finishCompact(toHold);
+ manager.freeze();
+ manager.transferHoldLists(g.getCurrentGeneration());
+ g.incGeneration();
+ manager.trimHoldLists(g.getFirstUsedGeneration());
+ }
+ // remove entries
+ for (size_t i = 0; i < numEntries; ++i) {
+ int num = UNWRAP(exp[i].first);
+ //LOG(info, "remove[%zu](%d)", i, num);
+ //std::cout << "tree: " << tree.toString() << std::endl;
+ EXPECT_TRUE(tree.remove(num));
+ EXPECT_TRUE(!tree.find(num).valid());
+ EXPECT_TRUE(!tree.remove(num));
+ EXPECT_TRUE(tree.isValid());
+ for (size_t j = i + 1; j < numEntries; ++j) {
+ MyTree::Iterator itr = tree.find(exp[j].first);
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(exp[j].first, itr.getKey());
+ EXPECT_EQUAL(exp[j].second, itr.getData());
+ }
+ EXPECT_EQUAL(numEntries - 1 - i, tree.size());
+ }
+}
+
+void
+Test::requireThatSortedTreeInsertWorks()
+{
+ {
+ GenerationHandler g;
+ MyTree tree;
+ for (int i = 0; i < 1000; ++i) {
+ EXPECT_TRUE(tree.insert(i, toStr(i)));
+ MyTree::Iterator itr = tree.find(i);
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(toStr(i), itr.getData());
+ EXPECT_TRUE(tree.isValid());
+ }
+ }
+ {
+ GenerationHandler g;
+ MyTree tree;
+ for (int i = 1000; i > 0; --i) {
+ EXPECT_TRUE(tree.insert(i, toStr(i)));
+ MyTree::Iterator itr = tree.find(i);
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(toStr(i), itr.getData());
+ EXPECT_TRUE(tree.isValid());
+ }
+ }
+}
+
+void
+Test::requireThatCornerCaseTreeFindWorks()
+{
+ GenerationHandler g;
+ MyTree tree;
+ for (int i = 1; i < 100; ++i) {
+ tree.insert(i, toStr(i));
+ }
+ EXPECT_TRUE(!tree.find(0).valid()); // lower than lowest
+ EXPECT_TRUE(!tree.find(1000).valid()); // higher than highest
+}
+
+void
+Test::requireThatBasicTreeIteratorWorks()
+{
+ GenerationHandler g;
+ MyTree tree;
+ EXPECT_TRUE(!tree.begin().valid());
+ std::vector<LeafPair> exp;
+ size_t numEntries = 1000;
+ generateData(exp, numEntries);
+ for (size_t i = 0; i < numEntries; ++i) {
+ tree.insert(exp[i].first, exp[i].second);
+ }
+ std::sort(exp.begin(), exp.end(), LeafPairLess());
+ size_t ei = 0;
+ MyTree::Iterator itr = tree.begin();
+ MyTree::Iterator ritr;
+ EXPECT_EQUAL(1000u, itr.size());
+ for (; itr.valid(); ++itr) {
+ //LOG(info, "itr(%d, %s)", itr.getKey(), itr.getData().c_str());
+ EXPECT_EQUAL(UNWRAP(exp[ei].first), UNWRAP(itr.getKey()));
+ EXPECT_EQUAL(exp[ei].second, itr.getData());
+ ei++;
+ ritr = itr;
+ }
+ EXPECT_EQUAL(numEntries, ei);
+ for (; ritr.valid(); --ritr) {
+ --ei;
+ //LOG(info, "itr(%d, %s)", itr.getKey(), itr.getData().c_str());
+ EXPECT_EQUAL(UNWRAP(exp[ei].first), UNWRAP(ritr.getKey()));
+ EXPECT_EQUAL(exp[ei].second, ritr.getData());
+ }
+}
+
+void
+Test::requireThatTreeIteratorSeekWorks()
+{
+ GenerationHandler g;
+ MyTree tree;
+ for (int i = 0; i < 40; i += 2) {
+ tree.insert(i, toStr(i));
+ }
+ //std::cout << tree.toString() << std::endl;
+ EXPECT_TRUE(assertSeek(2, 2, tree)); // next key
+ EXPECT_TRUE(assertSeek(10, 10, tree)); // skip to existing
+ EXPECT_TRUE(assertSeek(26, 26, tree)); // skip to existing
+ EXPECT_TRUE(assertSeek(11, 12, tree)); // skip to non-existing
+ EXPECT_TRUE(assertSeek(23, 24, tree)); // skip to non-existing
+ {
+ MyTree::Iterator itr = tree.begin();
+ EXPECT_TRUE(assertSeek(4, 4, itr));
+ EXPECT_TRUE(assertSeek(14, 14, itr));
+ EXPECT_TRUE(assertSeek(18, 18, itr));
+ EXPECT_TRUE(assertSeek(36, 36, itr));
+ }
+ {
+ MyTree::Iterator itr = tree.begin();
+ EXPECT_TRUE(assertSeek(3, 4, itr));
+ EXPECT_TRUE(assertSeek(13, 14, itr));
+ EXPECT_TRUE(assertSeek(17, 18, itr));
+ EXPECT_TRUE(assertSeek(35, 36, itr));
+ }
+ {
+ MyTree::Iterator itr = tree.begin();
+ MyTree::Iterator itr2 = tree.begin();
+ itr.binarySeek(40); // outside
+ itr2.linearSeek(40); // outside
+ EXPECT_TRUE(!itr.valid());
+ EXPECT_TRUE(!itr2.valid());
+ }
+ {
+ MyTree::Iterator itr = tree.begin();
+ EXPECT_TRUE(assertSeek(8, 8, itr));
+ for (int i = 10; i < 40; i += 2) {
+ ++itr;
+ EXPECT_EQUAL(i, UNWRAP(itr.getKey()));
+ }
+ }
+ {
+ MyTree::Iterator itr = tree.begin();
+ EXPECT_TRUE(assertSeek(26, 26, itr));
+ for (int i = 28; i < 40; i += 2) {
+ ++itr;
+ EXPECT_EQUAL(i, UNWRAP(itr.getKey()));
+ }
+ }
+ GenerationHandler g2;
+ MyTree tree2; // only leaf node
+ tree2.insert(0, "0");
+ tree2.insert(2, "2");
+ tree2.insert(4, "4");
+ EXPECT_TRUE(assertSeek(1, 2, tree2));
+ EXPECT_TRUE(assertSeek(2, 2, tree2));
+ {
+ MyTree::Iterator itr = tree2.begin();
+ MyTree::Iterator itr2 = tree2.begin();
+ itr.binarySeek(5); // outside
+ itr2.linearSeek(5); // outside
+ EXPECT_TRUE(!itr.valid());
+ EXPECT_TRUE(!itr2.valid());
+ }
+}
+
+void
+Test::requireThatTreeIteratorAssignWorks()
+{
+ GenerationHandler g;
+ MyTree tree;
+ for (int i = 0; i < 1000; ++i) {
+ tree.insert(i, toStr(i));
+ }
+ for (int i = 0; i < 1000; ++i) {
+ MyTree::Iterator itr = tree.find(i);
+ MyTree::Iterator itr2 = itr;
+ EXPECT_TRUE(itr == itr2);
+ int expNum = i;
+ for (; itr2.valid(); ++itr2) {
+ EXPECT_EQUAL(expNum++, UNWRAP(itr2.getKey()));
+ }
+ EXPECT_EQUAL(1000, expNum);
+ }
+}
+
+size_t
+adjustAllocatedBytes(size_t nodeCount, size_t nodeSize)
+{
+ // Note: Sizes of underlying data store buffers are power of 2.
+ size_t allocatedBytes = vespalib::roundUp2inN(nodeCount * nodeSize);
+ size_t adjustedNodeCount = allocatedBytes / nodeSize;
+ return adjustedNodeCount * nodeSize;
+}
+
+void
+Test::requireThatMemoryUsageIsCalculated()
+{
+ typedef BTreeNodeAllocator<int32_t, int8_t,
+ btree::NoAggregated,
+ MyTraits::INTERNAL_SLOTS, MyTraits::LEAF_SLOTS> NodeAllocator;
+ typedef NodeAllocator::InternalNodeType INode;
+ typedef NodeAllocator::LeafNodeType LNode;
+ typedef NodeAllocator::InternalNodeTypeRefPair IRef;
+ typedef NodeAllocator::LeafNodeTypeRefPair LRef;
+ LOG(info, "sizeof(BTreeNode)=%zu, sizeof(INode)=%zu, sizeof(LNode)=%zu",
+ sizeof(BTreeNode), sizeof(INode), sizeof(LNode));
+ EXPECT_GREATER(sizeof(INode), sizeof(LNode));
+ GenerationHandler gh;
+ gh.incGeneration();
+ NodeAllocator tm;
+ vespalib::MemoryUsage mu;
+ const uint32_t initialInternalNodes = 128u;
+ const uint32_t initialLeafNodes = 128u;
+ mu.incAllocatedBytes(adjustAllocatedBytes(initialInternalNodes, sizeof(INode)));
+ mu.incAllocatedBytes(adjustAllocatedBytes(initialLeafNodes, sizeof(LNode)));
+ mu.incUsedBytes(sizeof(INode));
+ mu.incDeadBytes(sizeof(INode));
+ EXPECT_TRUE(assertMemoryUsage(mu, tm.getMemoryUsage()));
+
+ // add internal node
+ IRef ir = tm.allocInternalNode(1);
+ mu.incUsedBytes(sizeof(INode));
+ EXPECT_TRUE(assertMemoryUsage(mu, tm.getMemoryUsage()));
+
+ // add leaf node
+ LRef lr = tm.allocLeafNode();
+ mu.incUsedBytes(sizeof(LNode));
+ EXPECT_TRUE(assertMemoryUsage(mu, tm.getMemoryUsage()));
+
+ // move nodes to hold list
+ tm.freeze(); // mark allocated nodes as frozen so we can hold them later on
+ tm.holdNode(ir.ref, ir.data);
+ mu.incAllocatedBytesOnHold(sizeof(INode));
+ EXPECT_TRUE(assertMemoryUsage(mu, tm.getMemoryUsage()));
+ tm.holdNode(lr.ref, lr.data);
+ mu.incAllocatedBytesOnHold(sizeof(LNode));
+ EXPECT_TRUE(assertMemoryUsage(mu, tm.getMemoryUsage()));
+
+ // trim hold lists
+ tm.transferHoldLists(gh.getCurrentGeneration());
+ gh.incGeneration();
+ tm.trimHoldLists(gh.getFirstUsedGeneration());
+ mu = vespalib::MemoryUsage();
+ mu.incAllocatedBytes(adjustAllocatedBytes(initialInternalNodes, sizeof(INode)));
+ mu.incAllocatedBytes(adjustAllocatedBytes(initialLeafNodes, sizeof(LNode)));
+ mu.incUsedBytes(sizeof(INode) * 2);
+ mu.incDeadBytes(sizeof(INode) * 2);
+ mu.incUsedBytes(sizeof(LNode));
+ mu.incDeadBytes(sizeof(LNode));
+ EXPECT_TRUE(assertMemoryUsage(mu, tm.getMemoryUsage()));
+}
+
+template <typename TreeType>
+void
+Test::requireThatLowerBoundWorksT()
+{
+ GenerationHandler g;
+ TreeType t;
+ EXPECT_TRUE(t.insert(10, BTreeNoLeafData()));
+ EXPECT_TRUE(t.insert(20, BTreeNoLeafData()));
+ EXPECT_TRUE(t.insert(30, BTreeNoLeafData()));
+ EXPECT_EQUAL(10, t.lowerBound(9).getKey());
+ EXPECT_EQUAL(20, t.lowerBound(20).getKey());
+ EXPECT_EQUAL(30, t.lowerBound(21).getKey());
+ EXPECT_EQUAL(30, t.lowerBound(30).getKey());
+ EXPECT_TRUE(!t.lowerBound(31).valid());
+ for (int i = 40; i < 1000; i+=10) {
+ EXPECT_TRUE(t.insert(i, BTreeNoLeafData()));
+ }
+ for (int i = 9; i < 990; i+=10) {
+ EXPECT_EQUAL(i + 1, t.lowerBound(i).getKey());
+ EXPECT_EQUAL(i + 1, t.lowerBound(i + 1).getKey());
+ }
+ EXPECT_TRUE(!t.lowerBound(991).valid());
+}
+
+void
+Test::requireThatLowerBoundWorks()
+{
+ requireThatLowerBoundWorksT<SetTreeB>();
+ requireThatLowerBoundWorksT<SetTreeL>();
+}
+
+template <typename TreeType>
+void
+Test::requireThatUpperBoundWorksT()
+{
+ GenerationHandler g;
+ TreeType t;
+ EXPECT_TRUE(t.insert(10, BTreeNoLeafData()));
+ EXPECT_TRUE(t.insert(20, BTreeNoLeafData()));
+ EXPECT_TRUE(t.insert(30, BTreeNoLeafData()));
+ EXPECT_EQUAL(10, t.upperBound(9).getKey());
+ EXPECT_EQUAL(30, t.upperBound(20).getKey());
+ EXPECT_EQUAL(30, t.upperBound(21).getKey());
+ EXPECT_TRUE(!t.upperBound(30).valid());
+ for (int i = 40; i < 1000; i+=10) {
+ EXPECT_TRUE(t.insert(i, BTreeNoLeafData()));
+ }
+ for (int i = 9; i < 980; i+=10) {
+ EXPECT_EQUAL(i + 1, t.upperBound(i).getKey());
+ EXPECT_EQUAL(i + 11, t.upperBound(i + 1).getKey());
+ }
+ EXPECT_TRUE(!t.upperBound(990).valid());
+}
+
+void
+Test::requireThatUpperBoundWorks()
+{
+ requireThatUpperBoundWorksT<SetTreeB>();
+ requireThatUpperBoundWorksT<SetTreeL>();
+}
+
+struct UpdKeyComp {
+ int _remainder;
+ mutable size_t _numErrors;
+ UpdKeyComp(int remainder) : _remainder(remainder), _numErrors(0) {}
+ bool operator() (const int & lhs, const int & rhs) const {
+ if (lhs % 2 != _remainder) ++_numErrors;
+ if (rhs % 2 != _remainder) ++_numErrors;
+ return lhs < rhs;
+ }
+};
+
+void
+Test::requireThatUpdateOfKeyWorks()
+{
+ typedef BTree<int, BTreeNoLeafData,
+ btree::NoAggregated,
+ UpdKeyComp &> UpdKeyTree;
+ typedef UpdKeyTree::Iterator UpdKeyTreeIterator;
+ GenerationHandler g;
+ UpdKeyTree t;
+ UpdKeyComp cmp1(0);
+ for (int i = 0; i < 1000; i+=2) {
+ EXPECT_TRUE(t.insert(i, BTreeNoLeafData(), cmp1));
+ }
+ EXPECT_EQUAL(0u, cmp1._numErrors);
+ for (int i = 0; i < 1000; i+=2) {
+ UpdKeyTreeIterator itr = t.find(i, cmp1);
+ itr.writeKey(i + 1);
+ }
+ UpdKeyComp cmp2(1);
+ for (int i = 1; i < 1000; i+=2) {
+ UpdKeyTreeIterator itr = t.find(i, cmp2);
+ EXPECT_TRUE(itr.valid());
+ }
+ EXPECT_EQUAL(0u, cmp2._numErrors);
+}
+
+
+void
+Test::requireThatSmallNodesWorks()
+{
+ typedef BTreeStore<MyKey, std::string, btree::NoAggregated, MyComp,
+ BTreeDefaultTraits> TreeStore;
+ GenerationHandler g;
+ TreeStore s;
+
+ EntryRef root;
+ EXPECT_EQUAL(0u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ EXPECT_TRUE(s.insert(root, 40, "fourty"));
+ EXPECT_TRUE(!s.insert(root, 40, "fourty.not"));
+ EXPECT_EQUAL(1u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ EXPECT_TRUE(s.insert(root, 20, "twenty"));
+ EXPECT_TRUE(!s.insert(root, 20, "twenty.not"));
+ EXPECT_TRUE(!s.insert(root, 40, "fourty.not"));
+ EXPECT_EQUAL(2u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ EXPECT_TRUE(s.insert(root, 60, "sixty"));
+ EXPECT_TRUE(!s.insert(root, 60, "sixty.not"));
+ EXPECT_TRUE(!s.insert(root, 20, "twenty.not"));
+ EXPECT_TRUE(!s.insert(root, 40, "fourty.not"));
+ EXPECT_EQUAL(3u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ EXPECT_TRUE(s.insert(root, 50, "fifty"));
+ EXPECT_TRUE(!s.insert(root, 50, "fifty.not"));
+ EXPECT_TRUE(!s.insert(root, 60, "sixty.not"));
+ EXPECT_TRUE(!s.insert(root, 20, "twenty.not"));
+ EXPECT_TRUE(!s.insert(root, 40, "fourty.not"));
+ EXPECT_EQUAL(4u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ for (uint32_t i = 0; i < 100; ++i) {
+ EXPECT_TRUE(s.insert(root, 1000 + i, "big"));
+ if (i > 0) {
+ EXPECT_TRUE(!s.insert(root, 1000 + i - 1, "big"));
+ }
+ EXPECT_EQUAL(5u + i, s.size(root));
+ EXPECT_EQUAL(5u + i <= 8u, s.isSmallArray(root));
+ }
+ EXPECT_TRUE(s.remove(root, 40));
+ EXPECT_TRUE(!s.remove(root, 40));
+ EXPECT_EQUAL(103u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+ EXPECT_TRUE(s.remove(root, 20));
+ EXPECT_TRUE(!s.remove(root, 20));
+ EXPECT_EQUAL(102u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+ EXPECT_TRUE(s.remove(root, 50));
+ EXPECT_TRUE(!s.remove(root, 50));
+ EXPECT_EQUAL(101u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+ for (uint32_t i = 0; i < 100; ++i) {
+ EXPECT_TRUE(s.remove(root, 1000 + i));
+ if (i > 0) {
+ EXPECT_TRUE(!s.remove(root, 1000 + i - 1));
+ }
+ EXPECT_EQUAL(100 - i, s.size(root));
+ EXPECT_EQUAL(100 - i <= 8u, s.isSmallArray(root));
+ }
+ EXPECT_EQUAL(1u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ s.clear(root);
+ s.clearBuilder();
+ s.freeze();
+ s.transferHoldLists(g.getCurrentGeneration());
+ g.incGeneration();
+ s.trimHoldLists(g.getFirstUsedGeneration());
+}
+
+
+void
+Test::requireThatApplyWorks()
+{
+ typedef BTreeStore<MyKey, std::string, btree::NoAggregated, MyComp,
+ BTreeDefaultTraits> TreeStore;
+ typedef TreeStore::KeyType KeyType;
+ typedef TreeStore::KeyDataType KeyDataType;
+ GenerationHandler g;
+ TreeStore s;
+ std::vector<KeyDataType> additions;
+ std::vector<KeyType> removals;
+
+ EntryRef root;
+ EXPECT_EQUAL(0u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ additions.clear();
+ removals.clear();
+ additions.push_back(KeyDataType(40, "fourty"));
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(1u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ additions.clear();
+ removals.clear();
+ additions.push_back(KeyDataType(20, "twenty"));
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(2u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ additions.clear();
+ removals.clear();
+ additions.push_back(KeyDataType(60, "sixty"));
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(3u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ additions.clear();
+ removals.clear();
+ additions.push_back(KeyDataType(50, "fifty"));
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(4u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ for (uint32_t i = 0; i < 100; ++i) {
+ additions.clear();
+ removals.clear();
+ additions.push_back(KeyDataType(1000 + i, "big"));
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(5u + i, s.size(root));
+ EXPECT_EQUAL(5u + i <= 8u, s.isSmallArray(root));
+ }
+
+ additions.clear();
+ removals.clear();
+ removals.push_back(40);
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(103u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+
+ additions.clear();
+ removals.clear();
+ removals.push_back(20);
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(102u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+
+ additions.clear();
+ removals.clear();
+ removals.push_back(50);
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(101u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+ for (uint32_t i = 0; i < 100; ++i) {
+ additions.clear();
+ removals.clear();
+ removals.push_back(1000 +i);
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(100 - i, s.size(root));
+ EXPECT_EQUAL(100 - i <= 8u, s.isSmallArray(root));
+ }
+ EXPECT_EQUAL(1u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ additions.clear();
+ removals.clear();
+ for (uint32_t i = 0; i < 20; ++i)
+ additions.push_back(KeyDataType(1000 + i, "big"));
+ removals.push_back(60);
+ removals.push_back(1002);
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(20u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+
+ additions.clear();
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(19u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+
+ additions.clear();
+ removals.clear();
+ for (uint32_t i = 0; i < 20; ++i)
+ additions.push_back(KeyDataType(1100 + i, "big"));
+ for (uint32_t i = 0; i < 10; ++i)
+ removals.push_back(1000 + i);
+ s.apply(root, &additions[0], &additions[0] + additions.size(),
+ &removals[0], &removals[0] + removals.size());
+ EXPECT_EQUAL(30u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+
+ s.clear(root);
+ s.clearBuilder();
+ s.freeze();
+ s.transferHoldLists(g.getCurrentGeneration());
+ g.incGeneration();
+ s.trimHoldLists(g.getFirstUsedGeneration());
+}
+
+class MyTreeTestIterator : public MyTree::Iterator
+{
+public:
+ MyTreeTestIterator(const MyTree::Iterator &rhs)
+ : MyTree::Iterator(rhs)
+ {
+ }
+
+ int getPathSize() const { return _pathSize; }
+};
+
+
+void
+Test::requireThatIteratorDistanceWorks(int numEntries)
+{
+ GenerationHandler g;
+ MyTree tree;
+ typedef MyTree::Iterator Iterator;
+ for (int i = 0; i < numEntries; ++i) {
+ tree.insert(i, toStr(i));
+ }
+ MyTreeTestIterator tit = tree.begin();
+ LOG(info,
+ "numEntries=%d, iterator pathSize=%d",
+ numEntries, tit.getPathSize());
+ Iterator it = tree.begin();
+ for (int i = 0; i <= numEntries; ++i) {
+ Iterator iit = tree.lowerBound(i);
+ Iterator iitn = tree.lowerBound(i + 1);
+ Iterator iitu = tree.upperBound(i);
+ Iterator iitls = tree.begin();
+ Iterator iitbs = tree.begin();
+ Iterator iitlsp = tree.begin();
+ Iterator iitbsp = tree.begin();
+ Iterator iitlb(tree.getRoot(), tree.getAllocator());
+ iitlb.lower_bound(i);
+ Iterator iitlb2(BTreeNode::Ref(), tree.getAllocator());
+ iitlb2.lower_bound(tree.getRoot(), i);
+ if (i > 0) {
+ iitls.linearSeek(i);
+ iitbs.binarySeek(i);
+ ++it;
+ }
+ iitlsp.linearSeekPast(i);
+ iitbsp.binarySeekPast(i);
+ Iterator iitlsp2 = iitls;
+ Iterator iitbsp2 = iitbs;
+ Iterator iitnr = i < numEntries ? iitn : tree.begin();
+ --iitnr;
+ if (i < numEntries) {
+ iitlsp2.linearSeekPast(i);
+ iitbsp2.binarySeekPast(i);
+ }
+ EXPECT_EQUAL(i, static_cast<int>(iit.position()));
+ EXPECT_EQUAL(i < numEntries, iit.valid());
+ EXPECT_TRUE(iit.identical(it));
+ EXPECT_TRUE(iit.identical(iitls));
+ EXPECT_TRUE(iit.identical(iitbs));
+ EXPECT_TRUE(iit.identical(iitnr));
+ EXPECT_TRUE(iit.identical(iitlb));
+ EXPECT_TRUE(iit.identical(iitlb2));
+ EXPECT_TRUE(iitn.identical(iitu));
+ EXPECT_TRUE(iitn.identical(iitlsp));
+ EXPECT_TRUE(iitn.identical(iitbsp));
+ EXPECT_TRUE(iitn.identical(iitlsp2));
+ EXPECT_TRUE(iitn.identical(iitbsp2));
+ if (i < numEntries) {
+ EXPECT_EQUAL(i + 1, static_cast<int>(iitn.position()));
+ EXPECT_EQUAL(i + 1 < numEntries, iitn.valid());
+ }
+ for (int j = 0; j <= numEntries; ++j) {
+ Iterator jit = tree.lowerBound(j);
+ EXPECT_EQUAL(j, static_cast<int>(jit.position()));
+ EXPECT_EQUAL(j < numEntries, jit.valid());
+ EXPECT_EQUAL(i - j, iit - jit);
+ EXPECT_EQUAL(j - i, jit - iit);
+
+ Iterator jit2 = jit;
+ jit2.setupEnd();
+ EXPECT_EQUAL(numEntries - j, jit2 - jit);
+ EXPECT_EQUAL(numEntries - i, jit2 - iit);
+ EXPECT_EQUAL(j - numEntries, jit - jit2);
+ EXPECT_EQUAL(i - numEntries, iit - jit2);
+ }
+ }
+}
+
+
+void
+Test::requireThatIteratorDistanceWorks()
+{
+ requireThatIteratorDistanceWorks(1);
+ requireThatIteratorDistanceWorks(3);
+ requireThatIteratorDistanceWorks(8);
+ requireThatIteratorDistanceWorks(20);
+ requireThatIteratorDistanceWorks(100);
+ requireThatIteratorDistanceWorks(400);
+}
+
+
+int
+Test::Main()
+{
+ TEST_INIT("btree_test");
+
+ requireThatNodeInsertWorks();
+ requireThatTreeInsertWorks();
+ requireThatNodeSplitInsertWorks();
+ requireThatNodeStealWorks();
+ requireThatTreeRemoveStealWorks();
+ requireThatNodeRemoveWorks();
+ requireThatNodeLowerBoundWorks();
+ requireThatWeCanInsertAndRemoveFromTree();
+ requireThatSortedTreeInsertWorks();
+ requireThatCornerCaseTreeFindWorks();
+ requireThatBasicTreeIteratorWorks();
+ requireThatTreeIteratorSeekWorks();
+ requireThatTreeIteratorAssignWorks();
+ requireThatMemoryUsageIsCalculated();
+ requireThatLowerBoundWorks();
+ requireThatUpperBoundWorks();
+ requireThatUpdateOfKeyWorks();
+ requireThatSmallNodesWorks();
+ requireThatApplyWorks();
+ requireThatIteratorDistanceWorks();
+
+ TEST_DONE();
+}
+
+}
+}
+
+TEST_APPHOOK(search::btree::Test);
diff --git a/vespalib/src/tests/btree/btreeaggregation_test.cpp b/vespalib/src/tests/btree/btreeaggregation_test.cpp
new file mode 100644
index 00000000000..0ce3d2c7d04
--- /dev/null
+++ b/vespalib/src/tests/btree/btreeaggregation_test.cpp
@@ -0,0 +1,1157 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+#include <vespa/log/log.h>
+LOG_SETUP("btreeaggregation_test");
+#include <vespa/vespalib/testkit/testapp.h>
+#include <vespa/vespalib/btree/btreeroot.h>
+#include <vespa/vespalib/btree/btreebuilder.h>
+#include <vespa/vespalib/btree/btreenodeallocator.h>
+#include <vespa/vespalib/btree/btree.h>
+#include <vespa/vespalib/btree/btreestore.h>
+#include <vespa/vespalib/btree/btreenodeallocator.hpp>
+#include <vespa/vespalib/btree/btreenode.hpp>
+#include <vespa/vespalib/btree/btreenodestore.hpp>
+#include <vespa/vespalib/btree/btreeiterator.hpp>
+#include <vespa/vespalib/btree/btreeroot.hpp>
+#include <vespa/vespalib/btree/btreebuilder.hpp>
+#include <vespa/vespalib/btree/btree.hpp>
+#include <vespa/vespalib/btree/btreestore.hpp>
+#include <vespa/vespalib/btree/btreeaggregator.hpp>
+#include <vespa/vespalib/test/btree/btree_printer.h>
+#include <vespa/vespalib/util/rand48.h>
+
+#include <iostream>
+#include <map>
+#include <set>
+#include <string>
+
+using vespalib::GenerationHandler;
+using search::datastore::EntryRef;
+
+namespace search {
+namespace btree {
+
+namespace {
+
+int32_t
+toVal(uint32_t key)
+{
+ return key + 1000;
+}
+
+int32_t
+toHighVal(uint32_t key)
+{
+ return toVal(key) + 1000;
+}
+
+int32_t
+toLowVal(uint32_t key)
+{
+ return toVal(key) - 1000000;
+}
+
+int32_t
+toNotVal(uint32_t key)
+{
+ return key + 2000;
+}
+
+}
+
+typedef BTreeTraits<4, 4, 31, false> MyTraits;
+
+#define KEYWRAP
+
+#ifdef KEYWRAP
+
+// Force use of functor to compare keys.
+class WrapInt
+{
+public:
+ int _val;
+ WrapInt(int val) : _val(val) {}
+ WrapInt() : _val(0) {}
+ bool operator==(const WrapInt & rhs) const { return _val == rhs._val; }
+};
+
+std::ostream &
+operator<<(std::ostream &s, const WrapInt &i)
+{
+ s << i._val;
+ return s;
+}
+
+typedef WrapInt MyKey;
+class MyComp
+{
+public:
+ bool
+ operator()(const WrapInt &a, const WrapInt &b) const
+ {
+ return a._val < b._val;
+ }
+};
+
+#define UNWRAP(key) (key._val)
+#else
+typedef int MyKey;
+typedef std::less<int> MyComp;
+#define UNWRAP(key) (key)
+#endif
+
+typedef BTree<MyKey, int32_t,
+ btree::MinMaxAggregated,
+ MyComp, MyTraits,
+ MinMaxAggrCalc> MyTree;
+typedef BTreeStore<MyKey, int32_t,
+ btree::MinMaxAggregated,
+ MyComp,
+ BTreeDefaultTraits,
+ MinMaxAggrCalc> MyTreeStore;
+typedef MyTree::Builder MyTreeBuilder;
+typedef MyTree::LeafNodeType MyLeafNode;
+typedef MyTree::InternalNodeType MyInternalNode;
+typedef MyTree::NodeAllocatorType MyNodeAllocator;
+typedef MyTree::Builder::Aggregator MyAggregator;
+typedef MyTree::AggrCalcType MyAggrCalc;
+typedef std::pair<MyKey, int32_t> LeafPair;
+typedef MyTreeStore::KeyDataType MyKeyData;
+typedef MyTreeStore::KeyDataTypeRefPair MyKeyDataRefPair;
+
+typedef BTree<int, BTreeNoLeafData, btree::NoAggregated> SetTreeB;
+
+typedef BTreeTraits<16, 16, 10, false> LSeekTraits;
+typedef BTree<int, BTreeNoLeafData, btree::NoAggregated,
+ std::less<int>, LSeekTraits> SetTreeL;
+
+struct LeafPairLess {
+ bool operator()(const LeafPair & lhs, const LeafPair & rhs) const {
+ return UNWRAP(lhs.first) < UNWRAP(rhs.first);
+ }
+};
+
+
+class MockTree
+{
+public:
+ typedef std::map<uint32_t, int32_t> MTree;
+ typedef std::map<int32_t, std::set<uint32_t> > MRTree;
+ MTree _tree;
+ MRTree _rtree;
+
+ MockTree();
+ ~MockTree();
+
+
+ void
+ erase(uint32_t key)
+ {
+ MTree::iterator it(_tree.find(key));
+ if (it == _tree.end())
+ return;
+ int32_t oval = it->second;
+ MRTree::iterator rit(_rtree.find(oval));
+ assert(rit != _rtree.end());
+ size_t ecount = rit->second.erase(key);
+ assert(ecount == 1);
+ (void) ecount;
+ if (rit->second.empty()) {
+ _rtree.erase(oval);
+ }
+ _tree.erase(key);
+ }
+
+ void
+ insert(uint32_t key, int32_t val)
+ {
+ erase(key);
+ _tree[key] = val;
+ _rtree[val].insert(key);
+ }
+};
+
+
+MockTree::MockTree()
+ : _tree(),
+ _rtree()
+{}
+MockTree::~MockTree() {}
+
+class MyTreeForceApplyStore : public MyTreeStore
+{
+public:
+ typedef MyComp CompareT;
+
+ bool
+ insert(EntryRef &ref, const KeyType &key, const DataType &data,
+ CompareT comp = CompareT());
+
+ bool
+ remove(EntryRef &ref, const KeyType &key, CompareT comp = CompareT());
+};
+
+
+bool
+MyTreeForceApplyStore::insert(EntryRef &ref,
+ const KeyType &key, const DataType &data,
+ CompareT comp)
+{
+ bool retVal = true;
+ if (ref.valid()) {
+ RefType iRef(ref);
+ uint32_t clusterSize = getClusterSize(iRef);
+ if (clusterSize == 0) {
+ const BTreeType *tree = getTreeEntry(iRef);
+ const NodeAllocatorType &allocator = getAllocator();
+ Iterator itr = tree->find(key, allocator, comp);
+ if (itr.valid())
+ retVal = false;
+ } else {
+ const KeyDataType *old = getKeyDataEntry(iRef, clusterSize);
+ const KeyDataType *olde = old + clusterSize;
+ const KeyDataType *oldi = lower_bound(old, olde, key, comp);
+ if (oldi < olde && !comp(key, oldi->_key))
+ retVal = false; // key already present
+ }
+ }
+ KeyDataType addition(key, data);
+ if (retVal) {
+ apply(ref, &addition, &addition+1, NULL, NULL, comp);
+ }
+ return retVal;
+}
+
+
+bool
+MyTreeForceApplyStore::remove(EntryRef &ref, const KeyType &key,
+ CompareT comp)
+{
+ bool retVal = true;
+ if (!ref.valid())
+ retVal = false; // not found
+ else {
+ RefType iRef(ref);
+ uint32_t clusterSize = getClusterSize(iRef);
+ if (clusterSize == 0) {
+ const BTreeType *tree = getTreeEntry(iRef);
+ const NodeAllocatorType &allocator = getAllocator();
+ Iterator itr = tree->find(key, allocator, comp);
+ if (!itr.valid())
+ retVal = false;
+ } else {
+ const KeyDataType *old = getKeyDataEntry(iRef, clusterSize);
+ const KeyDataType *olde = old + clusterSize;
+ const KeyDataType *oldi = lower_bound(old, olde, key, comp);
+ if (oldi == olde || comp(key, oldi->_key))
+ retVal = false; // not found
+ }
+ }
+ std::vector<KeyDataType> additions;
+ std::vector<KeyType> removals;
+ removals.push_back(key);
+ apply(ref,
+ &additions[0], &additions[additions.size()],
+ &removals[0], &removals[removals.size()],
+ comp);
+ return retVal;
+}
+
+
+template <typename ManagerType>
+void
+freezeTree(GenerationHandler &g, ManagerType &m)
+{
+ m.freeze();
+ m.transferHoldLists(g.getCurrentGeneration());
+ g.incGeneration();
+ m.trimHoldLists(g.getFirstUsedGeneration());
+}
+
+template <typename ManagerType>
+void
+cleanup(GenerationHandler &g, ManagerType &m)
+{
+ freezeTree(g, m);
+}
+
+template <typename ManagerType, typename NodeType>
+void
+cleanup(GenerationHandler & g,
+ ManagerType & m,
+ BTreeNode::Ref n1Ref, NodeType * n1,
+ BTreeNode::Ref n2Ref = BTreeNode::Ref(), NodeType * n2 = NULL)
+{
+ assert(ManagerType::isValidRef(n1Ref));
+ m.holdNode(n1Ref, n1);
+ if (n2 != NULL) {
+ assert(ManagerType::isValidRef(n2Ref));
+ m.holdNode(n2Ref, n2);
+ } else {
+ assert(!ManagerType::isValidRef(n2Ref));
+ }
+ cleanup(g, m);
+}
+
+class Test : public vespalib::TestApp {
+private:
+ template <typename Tree>
+ bool
+ assertTree(const std::string & exp, const Tree &t);
+
+ template <typename Tree>
+ bool
+ assertAggregated(const MockTree &m, const Tree &t);
+
+ template <typename TreeStore>
+ bool
+ assertAggregated(const MockTree &m, const TreeStore &s, EntryRef ref);
+
+ void
+ buildSubTree(const std::vector<LeafPair> &sub,
+ size_t numEntries);
+
+ void requireThatNodeInsertWorks();
+ void requireThatNodeSplitInsertWorks();
+ void requireThatTreeInsertWorks();
+ void requireThatNodeStealWorks();
+ void requireThatNodeRemoveWorks();
+ void requireThatWeCanInsertAndRemoveFromTree();
+ void requireThatSortedTreeInsertWorks();
+ void requireThatCornerCaseTreeFindWorks();
+ void requireThatBasicTreeIteratorWorks();
+ void requireThatTreeIteratorAssignWorks();
+ void requireThatUpdateOfKeyWorks();
+ void requireThatUpdateOfDataWorks();
+
+ template <typename TreeStore>
+ void
+ requireThatSmallNodesWorks();
+public:
+ int Main() override;
+};
+
+
+template<typename Tree>
+bool
+Test::assertTree(const std::string &exp, const Tree &t)
+{
+ std::stringstream ss;
+ test::BTreePrinter<std::stringstream, typename Tree::NodeAllocatorType> printer(ss, t.getAllocator());
+ printer.print(t.getRoot());
+ if (!EXPECT_EQUAL(exp, ss.str())) return false;
+ return true;
+}
+
+
+template <typename Tree>
+bool
+Test::assertAggregated(const MockTree &m, const Tree &t)
+{
+ const MinMaxAggregated &ta(t.getAggregated());
+ if (t.getRoot().valid()) {
+ return
+ EXPECT_FALSE(m._rtree.empty()) &&
+ EXPECT_EQUAL(m._rtree.rbegin()->first,
+ ta.getMax()) &&
+ EXPECT_EQUAL(m._rtree.begin()->first,
+ ta.getMin());
+ } else {
+ return EXPECT_TRUE(m._rtree.empty()) &&
+ EXPECT_EQUAL(std::numeric_limits<int32_t>::min(),
+ ta.getMax()) &&
+ EXPECT_EQUAL(std::numeric_limits<int32_t>::max(),
+ ta.getMin());
+ }
+}
+
+template <typename TreeStore>
+bool
+Test::assertAggregated(const MockTree &m, const TreeStore &s, EntryRef ref)
+{
+ typename TreeStore::Iterator i(s.begin(ref));
+ MinMaxAggregated sa(s.getAggregated(ref));
+ const MinMaxAggregated &ia(i.getAggregated());
+ if (ref.valid()) {
+ return
+ EXPECT_FALSE(m._rtree.empty()) &&
+ EXPECT_EQUAL(m._rtree.rbegin()->first,
+ ia.getMax()) &&
+ EXPECT_EQUAL(m._rtree.begin()->first,
+ ia.getMin()) &&
+ EXPECT_EQUAL(m._rtree.rbegin()->first,
+ sa.getMax()) &&
+ EXPECT_EQUAL(m._rtree.begin()->first,
+ sa.getMin());
+ } else {
+ return EXPECT_TRUE(m._rtree.empty()) &&
+ EXPECT_EQUAL(std::numeric_limits<int32_t>::min(),
+ ia.getMax()) &&
+ EXPECT_EQUAL(std::numeric_limits<int32_t>::max(),
+ ia.getMin()) &&
+ EXPECT_EQUAL(std::numeric_limits<int32_t>::min(),
+ sa.getMax()) &&
+ EXPECT_EQUAL(std::numeric_limits<int32_t>::max(),
+ sa.getMin());
+ }
+}
+
+
+void
+Test::requireThatNodeInsertWorks()
+{
+ MyTree t;
+ t.insert(20, 102);
+ EXPECT_TRUE(assertTree("{{20:102[min=102,max=102]}}", t));
+ t.insert(10, 101);
+ EXPECT_TRUE(assertTree("{{10:101,20:102[min=101,max=102]}}", t));
+ t.insert(30, 103);
+ t.insert(40, 104);
+ EXPECT_TRUE(assertTree("{{10:101,20:102,30:103,40:104[min=101,max=104]}}", t));
+}
+
+template <typename Tree>
+void
+populateTree(Tree &t, uint32_t count, uint32_t delta)
+{
+ uint32_t key = 1;
+ int32_t value = 101;
+ for (uint32_t i = 0; i < count; ++i) {
+ t.insert(key, value);
+ key += delta;
+ value += delta;
+ }
+}
+
+void
+populateLeafNode(MyTree &t)
+{
+ populateTree(t, 4, 2);
+}
+
+void
+Test::requireThatNodeSplitInsertWorks()
+{
+ { // new entry in current node
+ MyTree t;
+ populateLeafNode(t);
+ t.insert(4, 104);
+ EXPECT_TRUE(assertTree("{{4,7[min=101,max=107]}} -> "
+ "{{1:101,3:103,4:104[min=101,max=104]},"
+ "{5:105,7:107[min=105,max=107]}}", t));
+ }
+ { // new entry in split node
+ MyTree t;
+ populateLeafNode(t);
+ t.insert(6, 106);
+ EXPECT_TRUE(assertTree("{{5,7[min=101,max=107]}} -> "
+ "{{1:101,3:103,5:105[min=101,max=105]},"
+ "{6:106,7:107[min=106,max=107]}}", t));
+ }
+ { // new entry at end
+ MyTree t;
+ populateLeafNode(t);
+ t.insert(8, 108);
+ EXPECT_TRUE(assertTree("{{5,8[min=101,max=108]}} -> "
+ "{{1:101,3:103,5:105[min=101,max=105]},"
+ "{7:107,8:108[min=107,max=108]}}", t));
+ }
+}
+
+void
+Test::requireThatTreeInsertWorks()
+{
+ { // multi level node split
+ MyTree t;
+ populateTree(t, 16, 2);
+ EXPECT_TRUE(assertTree("{{7,15,23,31[min=101,max=131]}} -> "
+ "{{1:101,3:103,5:105,7:107[min=101,max=107]},"
+ "{9:109,11:111,13:113,15:115[min=109,max=115]},"
+ "{17:117,19:119,21:121,23:123[min=117,max=123]},"
+ "{25:125,27:127,29:129,31:131[min=125,max=131]}}", t));
+ t.insert(33, 133);
+ EXPECT_TRUE(assertTree("{{23,33[min=101,max=133]}} -> "
+ "{{7,15,23[min=101,max=123]},{29,33[min=125,max=133]}} -> "
+ "{{1:101,3:103,5:105,7:107[min=101,max=107]},"
+ "{9:109,11:111,13:113,15:115[min=109,max=115]},"
+ "{17:117,19:119,21:121,23:123[min=117,max=123]},"
+ "{25:125,27:127,29:129[min=125,max=129]},"
+ "{31:131,33:133[min=131,max=133]}}", t));
+ }
+ { // give to left node to avoid split
+ MyTree t;
+ populateTree(t, 8, 2);
+ t.remove(5);
+ EXPECT_TRUE(assertTree("{{7,15[min=101,max=115]}} -> "
+ "{{1:101,3:103,7:107[min=101,max=107]},"
+ "{9:109,11:111,13:113,15:115[min=109,max=115]}}", t));
+ t.insert(10, 110);
+ EXPECT_TRUE(assertTree("{{9,15[min=101,max=115]}} -> "
+ "{{1:101,3:103,7:107,9:109[min=101,max=109]},"
+ "{10:110,11:111,13:113,15:115[min=110,max=115]}}", t));
+ }
+ { // give to left node to avoid split, and move to left node
+ MyTree t;
+ populateTree(t, 8, 2);
+ t.remove(3);
+ t.remove(5);
+ EXPECT_TRUE(assertTree("{{7,15[min=101,max=115]}} -> "
+ "{{1:101,7:107[min=101,max=107]},"
+ "{9:109,11:111,13:113,15:115[min=109,max=115]}}", t));
+ t.insert(8, 108);
+ EXPECT_TRUE(assertTree("{{9,15[min=101,max=115]}} -> "
+ "{{1:101,7:107,8:108,9:109[min=101,max=109]},"
+ "{11:111,13:113,15:115[min=111,max=115]}}", t));
+ }
+ { // not give to left node to avoid split, but insert at end at left node
+ MyTree t;
+ populateTree(t, 8, 2);
+ t.remove(5);
+ EXPECT_TRUE(assertTree("{{7,15[min=101,max=115]}} -> "
+ "{{1:101,3:103,7:107[min=101,max=107]},"
+ "{9:109,11:111,13:113,15:115[min=109,max=115]}}", t));
+ t.insert(8, 108);
+ EXPECT_TRUE(assertTree("{{8,15[min=101,max=115]}} -> "
+ "{{1:101,3:103,7:107,8:108[min=101,max=108]},"
+ "{9:109,11:111,13:113,15:115[min=109,max=115]}}", t));
+ }
+ { // give to right node to avoid split
+ MyTree t;
+ populateTree(t, 8, 2);
+ t.remove(13);
+ EXPECT_TRUE(assertTree("{{7,15[min=101,max=115]}} -> "
+ "{{1:101,3:103,5:105,7:107[min=101,max=107]},"
+ "{9:109,11:111,15:115[min=109,max=115]}}", t));
+ t.insert(4, 104);
+ EXPECT_TRUE(assertTree("{{5,15[min=101,max=115]}} -> "
+ "{{1:101,3:103,4:104,5:105[min=101,max=105]},"
+ "{7:107,9:109,11:111,15:115[min=107,max=115]}}", t));
+ }
+ { // give to right node to avoid split and move to right node
+ using MyTraits6 = BTreeTraits<6, 6, 31, false>;
+ using Tree6 = BTree<MyKey, int32_t, btree::MinMaxAggregated, MyComp, MyTraits6, MinMaxAggrCalc>;
+
+ Tree6 t;
+ populateTree(t, 12, 2);
+ t.remove(19);
+ t.remove(21);
+ t.remove(23);
+ EXPECT_TRUE(assertTree("{{11,17[min=101,max=117]}} -> "
+ "{{1:101,3:103,5:105,7:107,9:109,11:111[min=101,max=111]},"
+ "{13:113,15:115,17:117[min=113,max=117]}}", t));
+ t.insert(10, 110);
+ EXPECT_TRUE(assertTree("{{7,17[min=101,max=117]}} -> "
+ "{{1:101,3:103,5:105,7:107[min=101,max=107]},"
+ "{9:109,10:110,11:111,13:113,15:115,17:117[min=109,max=117]}}", t));
+ }
+}
+
+struct BTreeStealTraits
+{
+ static const size_t LEAF_SLOTS = 6;
+ static const size_t INTERNAL_SLOTS = 6;
+ static const size_t PATH_SIZE = 20;
+ static const bool BINARY_SEEK = true;
+};
+
+void
+Test::requireThatNodeStealWorks()
+{
+ typedef BTree<MyKey, int32_t,
+ btree::MinMaxAggregated,
+ MyComp, BTreeStealTraits,
+ MinMaxAggrCalc> MyStealTree;
+ { // steal all from left
+ MyStealTree t;
+ t.insert(10, 110);
+ t.insert(20, 120);
+ t.insert(30, 130);
+ t.insert(40, 140);
+ t.insert(50, 150);
+ t.insert(60, 160);
+ t.insert(35, 135);
+ t.remove(35);
+ EXPECT_TRUE(assertTree("{{30,60[min=110,max=160]}} -> "
+ "{{10:110,20:120,30:130[min=110,max=130]},"
+ "{40:140,50:150,60:160[min=140,max=160]}}", t));
+ t.remove(50);
+ EXPECT_TRUE(assertTree("{{10:110,20:120,30:130,40:140,60:160[min=110,max=160]}}", t));
+ }
+ { // steal all from right
+ MyStealTree t;
+ t.insert(10, 110);
+ t.insert(20, 120);
+ t.insert(30, 130);
+ t.insert(40, 140);
+ t.insert(50, 150);
+ t.insert(60, 160);
+ t.insert(35, 135);
+ t.remove(35);
+ EXPECT_TRUE(assertTree("{{30,60[min=110,max=160]}} -> "
+ "{{10:110,20:120,30:130[min=110,max=130]},"
+ "{40:140,50:150,60:160[min=140,max=160]}}", t));
+ t.remove(20);
+ EXPECT_TRUE(assertTree("{{10:110,30:130,40:140,50:150,60:160[min=110,max=160]}}", t));
+ }
+ { // steal some from left
+ MyStealTree t;
+ t.insert(10, 110);
+ t.insert(20, 120);
+ t.insert(30, 130);
+ t.insert(60, 160);
+ t.insert(70, 170);
+ t.insert(80, 180);
+ t.insert(50, 150);
+ t.insert(40, 140);
+ EXPECT_TRUE(assertTree("{{50,80[min=110,max=180]}} -> "
+ "{{10:110,20:120,30:130,40:140,50:150[min=110,max=150]},"
+ "{60:160,70:170,80:180[min=160,max=180]}}", t));
+ t.remove(60);
+ EXPECT_TRUE(assertTree("{{30,80[min=110,max=180]}} -> "
+ "{{10:110,20:120,30:130[min=110,max=130]},"
+ "{40:140,50:150,70:170,80:180[min=140,max=180]}}", t));
+ }
+ { // steal some from right
+ MyStealTree t;
+ t.insert(10, 110);
+ t.insert(20, 120);
+ t.insert(30, 130);
+ t.insert(40, 140);
+ t.insert(50, 150);
+ t.insert(60, 160);
+ t.insert(70, 170);
+ t.insert(80, 180);
+ t.insert(90, 190);
+ t.remove(40);
+ EXPECT_TRUE(assertTree("{{30,90[min=110,max=190]}} -> "
+ "{{10:110,20:120,30:130[min=110,max=130]},"
+ "{50:150,60:160,70:170,80:180,90:190[min=150,max=190]}}", t));
+ t.remove(20);
+ EXPECT_TRUE(assertTree("{{60,90[min=110,max=190]}} -> "
+ "{{10:110,30:130,50:150,60:160[min=110,max=160]},"
+ "{70:170,80:180,90:190[min=170,max=190]}}", t));
+ }
+}
+
+void
+Test::requireThatNodeRemoveWorks()
+{
+ MyTree t;
+ populateLeafNode(t);
+ t.remove(3);
+ EXPECT_TRUE(assertTree("{{1:101,5:105,7:107[min=101,max=107]}}", t));
+ t.remove(1);
+ EXPECT_TRUE(assertTree("{{5:105,7:107[min=105,max=107]}}", t));
+ t.remove(7);
+ EXPECT_TRUE(assertTree("{{5:105[min=105,max=105]}}", t));
+}
+
+void
+generateData(std::vector<LeafPair> & data, size_t numEntries)
+{
+ data.reserve(numEntries);
+ Rand48 rnd;
+ rnd.srand48(10);
+ for (size_t i = 0; i < numEntries; ++i) {
+ int num = rnd.lrand48() % 10000000;
+ uint32_t val = toVal(num);
+ data.push_back(std::make_pair(num, val));
+ }
+}
+
+void
+Test::buildSubTree(const std::vector<LeafPair> &sub,
+ size_t numEntries)
+{
+ GenerationHandler g;
+ MyTree tree;
+ MyTreeBuilder builder(tree.getAllocator());
+ MockTree mock;
+
+ std::vector<LeafPair> sorted(sub.begin(), sub.begin() + numEntries);
+ std::sort(sorted.begin(), sorted.end(), LeafPairLess());
+ for (size_t i = 0; i < numEntries; ++i) {
+ int num = UNWRAP(sorted[i].first);
+ const uint32_t & val = sorted[i].second;
+ builder.insert(num, val);
+ mock.insert(num, val);
+ }
+ tree.assign(builder);
+ assert(numEntries == tree.size());
+ assert(tree.isValid());
+
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree)));
+ EXPECT_EQUAL(numEntries, tree.size());
+ EXPECT_TRUE(tree.isValid());
+ MyTree::Iterator itr = tree.begin();
+ MyTree::Iterator ritr = itr;
+ if (numEntries > 0) {
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ --ritr;
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(numEntries, ritr.position());
+ --ritr;
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(numEntries - 1, ritr.position());
+ } else {
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ --ritr;
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ }
+ for (size_t i = 0; i < numEntries; ++i) {
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(sorted[i].first, itr.getKey());
+ EXPECT_EQUAL(sorted[i].second, itr.getData());
+ ++itr;
+ }
+ EXPECT_TRUE(!itr.valid());
+ ritr = itr;
+ EXPECT_TRUE(!ritr.valid());
+ --ritr;
+ for (size_t i = 0; i < numEntries; ++i) {
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(sorted[numEntries - 1 - i].first, ritr.getKey());
+ EXPECT_EQUAL(sorted[numEntries - 1 - i].second, ritr.getData());
+ --ritr;
+ }
+ EXPECT_TRUE(!ritr.valid());
+}
+
+void
+Test::requireThatWeCanInsertAndRemoveFromTree()
+{
+ GenerationHandler g;
+ MyTree tree;
+ MockTree mock;
+ std::vector<LeafPair> exp;
+ std::vector<LeafPair> sorted;
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree)));
+ size_t numEntries = 1000;
+ generateData(exp, numEntries);
+ sorted = exp;
+ std::sort(sorted.begin(), sorted.end(), LeafPairLess());
+ // insert entries
+ for (size_t i = 0; i < numEntries; ++i) {
+ int num = UNWRAP(exp[i].first);
+ const uint32_t & val = exp[i].second;
+ EXPECT_TRUE(!tree.find(num).valid());
+ //LOG(info, "insert[%zu](%d, %s)", i, num, str.c_str());
+ EXPECT_TRUE(tree.insert(num, val));
+ EXPECT_TRUE(!tree.insert(num, val));
+ mock.insert(num, val);
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree)));
+ for (size_t j = 0; j <= i; ++j) {
+ //LOG(info, "find[%zu](%d)", j, exp[j].first._val);
+ MyTree::Iterator itr = tree.find(exp[j].first);
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(exp[j].first, itr.getKey());
+ EXPECT_EQUAL(exp[j].second, itr.getData());
+ }
+ EXPECT_EQUAL(i + 1u, tree.size());
+ EXPECT_TRUE(tree.isValid());
+ buildSubTree(exp, i + 1);
+ }
+ //std::cout << "tree: " << tree.toString() << std::endl;
+
+ {
+ MyTree::Iterator itr = tree.begin();
+ MyTree::Iterator itre = itr;
+ MyTree::Iterator itre2;
+ MyTree::Iterator ritr = itr;
+ while (itre.valid())
+ ++itre;
+ if (numEntries > 0) {
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ --ritr;
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(numEntries, ritr.position());
+ --ritr;
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_EQUAL(numEntries - 1, ritr.position());
+ } else {
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ --ritr;
+ EXPECT_TRUE(!ritr.valid());
+ EXPECT_EQUAL(0u, ritr.position());
+ }
+ MyTree::Iterator pitr = itr;
+ for (size_t i = 0; i < numEntries; ++i) {
+ ssize_t si = i;
+ ssize_t sileft = numEntries - i;
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(i, itr.position());
+ EXPECT_EQUAL(sileft, itre - itr);
+ EXPECT_EQUAL(-sileft, itr - itre);
+ EXPECT_EQUAL(sileft, itre2 - itr);
+ EXPECT_EQUAL(-sileft, itr - itre2);
+ EXPECT_EQUAL(si, itr - tree.begin());
+ EXPECT_EQUAL(-si, tree.begin() - itr);
+ EXPECT_EQUAL(i != 0, itr - pitr);
+ EXPECT_EQUAL(-(i != 0), pitr - itr);
+ EXPECT_EQUAL(sorted[i].first, itr.getKey());
+ EXPECT_EQUAL(sorted[i].second, itr.getData());
+ pitr = itr;
+ ++itr;
+ ritr = itr;
+ --ritr;
+ EXPECT_TRUE(ritr.valid());
+ EXPECT_TRUE(ritr == pitr);
+ }
+ EXPECT_TRUE(!itr.valid());
+ EXPECT_EQUAL(numEntries, itr.position());
+ ssize_t sNumEntries = numEntries;
+ EXPECT_EQUAL(sNumEntries, itr - tree.begin());
+ EXPECT_EQUAL(-sNumEntries, tree.begin() - itr);
+ EXPECT_EQUAL(1, itr - pitr);
+ EXPECT_EQUAL(-1, pitr - itr);
+ }
+ // compact full tree by calling incremental compaction methods in a loop
+ {
+ MyTree::NodeAllocatorType &manager = tree.getAllocator();
+ std::vector<uint32_t> toHold = manager.startCompact();
+ MyTree::Iterator itr = tree.begin();
+ tree.setRoot(itr.moveFirstLeafNode(tree.getRoot()));
+ while (itr.valid()) {
+ // LOG(info, "Leaf moved to %d", UNWRAP(itr.getKey()));
+ itr.moveNextLeafNode();
+ }
+ manager.finishCompact(toHold);
+ manager.freeze();
+ manager.transferHoldLists(g.getCurrentGeneration());
+ g.incGeneration();
+ manager.trimHoldLists(g.getFirstUsedGeneration());
+ }
+ // remove entries
+ for (size_t i = 0; i < numEntries; ++i) {
+ int num = UNWRAP(exp[i].first);
+ //LOG(info, "remove[%zu](%d)", i, num);
+ //std::cout << "tree: " << tree.toString() << std::endl;
+ EXPECT_TRUE(tree.remove(num));
+ EXPECT_TRUE(!tree.find(num).valid());
+ EXPECT_TRUE(!tree.remove(num));
+ EXPECT_TRUE(tree.isValid());
+ mock.erase(num);
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree)));
+ for (size_t j = i + 1; j < numEntries; ++j) {
+ MyTree::Iterator itr = tree.find(exp[j].first);
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(exp[j].first, itr.getKey());
+ EXPECT_EQUAL(exp[j].second, itr.getData());
+ }
+ EXPECT_EQUAL(numEntries - 1 - i, tree.size());
+ }
+}
+
+void
+Test::requireThatSortedTreeInsertWorks()
+{
+ {
+ MyTree tree;
+ MockTree mock;
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree)));
+ for (int i = 0; i < 1000; ++i) {
+ EXPECT_TRUE(tree.insert(i, toVal(i)));
+ mock.insert(i, toVal(i));
+ MyTree::Iterator itr = tree.find(i);
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(toVal(i), itr.getData());
+ EXPECT_TRUE(tree.isValid());
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree)));
+ }
+ }
+ {
+ MyTree tree;
+ MockTree mock;
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree)));
+ for (int i = 1000; i > 0; --i) {
+ EXPECT_TRUE(tree.insert(i, toVal(i)));
+ mock.insert(i, toVal(i));
+ MyTree::Iterator itr = tree.find(i);
+ EXPECT_TRUE(itr.valid());
+ EXPECT_EQUAL(toVal(i), itr.getData());
+ EXPECT_TRUE(tree.isValid());
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree)));
+ }
+ }
+}
+
+void
+Test::requireThatCornerCaseTreeFindWorks()
+{
+ GenerationHandler g;
+ MyTree tree;
+ for (int i = 1; i < 100; ++i) {
+ tree.insert(i, toVal(i));
+ }
+ EXPECT_TRUE(!tree.find(0).valid()); // lower than lowest
+ EXPECT_TRUE(!tree.find(1000).valid()); // higher than highest
+}
+
+void
+Test::requireThatBasicTreeIteratorWorks()
+{
+ GenerationHandler g;
+ MyTree tree;
+ EXPECT_TRUE(!tree.begin().valid());
+ std::vector<LeafPair> exp;
+ size_t numEntries = 1000;
+ generateData(exp, numEntries);
+ for (size_t i = 0; i < numEntries; ++i) {
+ tree.insert(exp[i].first, exp[i].second);
+ }
+ std::sort(exp.begin(), exp.end(), LeafPairLess());
+ size_t ei = 0;
+ MyTree::Iterator itr = tree.begin();
+ MyTree::Iterator ritr;
+ EXPECT_EQUAL(1000u, itr.size());
+ for (; itr.valid(); ++itr) {
+ //LOG(info, "itr(%d, %s)", itr.getKey(), itr.getData().c_str());
+ EXPECT_EQUAL(UNWRAP(exp[ei].first), UNWRAP(itr.getKey()));
+ EXPECT_EQUAL(exp[ei].second, itr.getData());
+ ei++;
+ ritr = itr;
+ }
+ EXPECT_EQUAL(numEntries, ei);
+ for (; ritr.valid(); --ritr) {
+ --ei;
+ //LOG(info, "itr(%d, %s)", itr.getKey(), itr.getData().c_str());
+ EXPECT_EQUAL(UNWRAP(exp[ei].first), UNWRAP(ritr.getKey()));
+ EXPECT_EQUAL(exp[ei].second, ritr.getData());
+ }
+}
+
+
+
+void
+Test::requireThatTreeIteratorAssignWorks()
+{
+ GenerationHandler g;
+ MyTree tree;
+ for (int i = 0; i < 1000; ++i) {
+ tree.insert(i, toVal(i));
+ }
+ for (int i = 0; i < 1000; ++i) {
+ MyTree::Iterator itr = tree.find(i);
+ MyTree::Iterator itr2 = itr;
+ EXPECT_TRUE(itr == itr2);
+ int expNum = i;
+ for (; itr2.valid(); ++itr2) {
+ EXPECT_EQUAL(expNum++, UNWRAP(itr2.getKey()));
+ }
+ EXPECT_EQUAL(1000, expNum);
+ }
+}
+
+struct UpdKeyComp {
+ int _remainder;
+ mutable size_t _numErrors;
+ UpdKeyComp(int remainder) : _remainder(remainder), _numErrors(0) {}
+ bool operator() (const int & lhs, const int & rhs) const {
+ if (lhs % 2 != _remainder) ++_numErrors;
+ if (rhs % 2 != _remainder) ++_numErrors;
+ return lhs < rhs;
+ }
+};
+
+void
+Test::requireThatUpdateOfKeyWorks()
+{
+ typedef BTree<int, BTreeNoLeafData,
+ btree::NoAggregated,
+ UpdKeyComp &> UpdKeyTree;
+ typedef UpdKeyTree::Iterator UpdKeyTreeIterator;
+ GenerationHandler g;
+ UpdKeyTree t;
+ UpdKeyComp cmp1(0);
+ for (int i = 0; i < 1000; i+=2) {
+ EXPECT_TRUE(t.insert(i, BTreeNoLeafData(), cmp1));
+ }
+ EXPECT_EQUAL(0u, cmp1._numErrors);
+ for (int i = 0; i < 1000; i+=2) {
+ UpdKeyTreeIterator itr = t.find(i, cmp1);
+ itr.writeKey(i + 1);
+ }
+ UpdKeyComp cmp2(1);
+ for (int i = 1; i < 1000; i+=2) {
+ UpdKeyTreeIterator itr = t.find(i, cmp2);
+ EXPECT_TRUE(itr.valid());
+ }
+ EXPECT_EQUAL(0u, cmp2._numErrors);
+}
+
+
+void
+Test::requireThatUpdateOfDataWorks()
+{
+ // typedef MyTree::Iterator Iterator;
+ GenerationHandler g;
+ MyTree t;
+ MockTree mock;
+ MyAggrCalc ac;
+ MyTree::NodeAllocatorType &manager = t.getAllocator();
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, t)));
+ for (int i = 0; i < 1000; i+=2) {
+ EXPECT_TRUE(t.insert(i, toVal(i)));
+ mock.insert(i, toVal(i));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, t)));
+ }
+ freezeTree(g, manager);
+ for (int i = 0; i < 1000; i+=2) {
+ MyTree::Iterator itr = t.find(i);
+ MyTree::Iterator itr2 = itr;
+ t.thaw(itr);
+ itr.updateData(toHighVal(i), ac);
+ EXPECT_EQUAL(toHighVal(i), itr.getData());
+ EXPECT_EQUAL(toVal(i), itr2.getData());
+ mock.erase(i);
+ mock.insert(i, toHighVal(i));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, t)));
+ freezeTree(g, manager);
+ itr = t.find(i);
+ itr2 = itr;
+ t.thaw(itr);
+ itr.updateData(toLowVal(i), ac);
+ EXPECT_EQUAL(toLowVal(i), itr.getData());
+ EXPECT_EQUAL(toHighVal(i), itr2.getData());
+ mock.erase(i);
+ mock.insert(i, toLowVal(i));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, t)));
+ freezeTree(g, manager);
+ itr = t.find(i);
+ itr2 = itr;
+ t.thaw(itr);
+ itr.updateData(toVal(i), ac);
+ EXPECT_EQUAL(toVal(i), itr.getData());
+ EXPECT_EQUAL(toLowVal(i), itr2.getData());
+ mock.erase(i);
+ mock.insert(i, toVal(i));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, t)));
+ freezeTree(g, manager);
+ }
+}
+
+
+template <typename TreeStore>
+void
+Test::requireThatSmallNodesWorks()
+{
+ GenerationHandler g;
+ TreeStore s;
+ MockTree mock;
+
+ EntryRef root;
+ EXPECT_EQUAL(0u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ EXPECT_TRUE(s.insert(root, 40, toVal(40)));
+ mock.insert(40, toVal(40));
+ EXPECT_TRUE(!s.insert(root, 40, toNotVal(40)));
+ EXPECT_EQUAL(1u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ EXPECT_TRUE(s.insert(root, 20, toVal(20)));
+ mock.insert(20, toVal(20));
+ EXPECT_TRUE(!s.insert(root, 20, toNotVal(20)));
+ EXPECT_TRUE(!s.insert(root, 40, toNotVal(40)));
+ EXPECT_EQUAL(2u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ EXPECT_TRUE(s.insert(root, 60, toVal(60)));
+ mock.insert(60, toVal(60));
+ EXPECT_TRUE(!s.insert(root, 60, toNotVal(60)));
+ EXPECT_TRUE(!s.insert(root, 20, toNotVal(20)));
+ EXPECT_TRUE(!s.insert(root, 40, toNotVal(40)));
+ EXPECT_EQUAL(3u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ EXPECT_TRUE(s.insert(root, 50, toVal(50)));
+ mock.insert(50, toVal(50));
+ EXPECT_TRUE(!s.insert(root, 50, toNotVal(50)));
+ EXPECT_TRUE(!s.insert(root, 60, toNotVal(60)));
+ EXPECT_TRUE(!s.insert(root, 20, toNotVal(20)));
+ EXPECT_TRUE(!s.insert(root, 40, toNotVal(40)));
+ EXPECT_EQUAL(4u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+
+ for (uint32_t i = 0; i < 100; ++i) {
+ EXPECT_TRUE(s.insert(root, 1000 + i, 42));
+ mock.insert(1000 + i, 42);
+ if (i > 0) {
+ EXPECT_TRUE(!s.insert(root, 1000 + i - 1, 42));
+ }
+ EXPECT_EQUAL(5u + i, s.size(root));
+ EXPECT_EQUAL(5u + i <= 8u, s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ }
+ EXPECT_TRUE(s.remove(root, 40));
+ mock.erase(40);
+ EXPECT_TRUE(!s.remove(root, 40));
+ EXPECT_EQUAL(103u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ EXPECT_TRUE(s.remove(root, 20));
+ mock.erase(20);
+ EXPECT_TRUE(!s.remove(root, 20));
+ EXPECT_EQUAL(102u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ EXPECT_TRUE(s.remove(root, 50));
+ mock.erase(50);
+ EXPECT_TRUE(!s.remove(root, 50));
+ EXPECT_EQUAL(101u, s.size(root));
+ EXPECT_TRUE(!s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ for (uint32_t i = 0; i < 100; ++i) {
+ EXPECT_TRUE(s.remove(root, 1000 + i));
+ mock.erase(1000 + i);
+ if (i > 0) {
+ EXPECT_TRUE(!s.remove(root, 1000 + i - 1));
+ }
+ EXPECT_EQUAL(100 - i, s.size(root));
+ EXPECT_EQUAL(100 - i <= 8u, s.isSmallArray(root));
+ TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root)));
+ }
+ EXPECT_EQUAL(1u, s.size(root));
+ EXPECT_TRUE(s.isSmallArray(root));
+
+ s.clear(root);
+ s.clearBuilder();
+ s.freeze();
+ s.transferHoldLists(g.getCurrentGeneration());
+ g.incGeneration();
+ s.trimHoldLists(g.getFirstUsedGeneration());
+}
+
+
+int
+Test::Main()
+{
+ TEST_INIT("btreeaggregation_test");
+
+ requireThatNodeInsertWorks();
+ requireThatNodeSplitInsertWorks();
+ requireThatTreeInsertWorks();
+ requireThatNodeStealWorks();
+ requireThatNodeRemoveWorks();
+ requireThatWeCanInsertAndRemoveFromTree();
+ requireThatSortedTreeInsertWorks();
+ requireThatCornerCaseTreeFindWorks();
+ requireThatBasicTreeIteratorWorks();
+ requireThatTreeIteratorAssignWorks();
+ requireThatUpdateOfKeyWorks();
+ requireThatUpdateOfDataWorks();
+ TEST_DO(requireThatSmallNodesWorks<MyTreeStore>());
+ TEST_DO(requireThatSmallNodesWorks<MyTreeForceApplyStore>());
+
+ TEST_DONE();
+}
+
+}
+}
+
+TEST_APPHOOK(search::btree::Test);
diff --git a/vespalib/src/tests/btree/frozenbtree_test.cpp b/vespalib/src/tests/btree/frozenbtree_test.cpp
new file mode 100644
index 00000000000..597c2ffdc90
--- /dev/null
+++ b/vespalib/src/tests/btree/frozenbtree_test.cpp
@@ -0,0 +1,469 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#define DEBUG_FROZENBTREE
+#define LOG_FROZENBTREEXX
+#include <vespa/vespalib/testkit/testapp.h>
+#include <vespa/vespalib/btree/btreeroot.h>
+#include <vespa/vespalib/btree/btreeiterator.hpp>
+#include <vespa/vespalib/btree/btreeroot.hpp>
+#include <vespa/vespalib/btree/btreenodeallocator.hpp>
+#include <vespa/vespalib/util/rand48.h>
+#include <map>
+
+#include <vespa/log/log.h>
+LOG_SETUP("frozenbtree_test");
+
+using search::btree::BTreeRoot;
+using search::btree::BTreeNode;
+using search::btree::BTreeInternalNode;
+using search::btree::BTreeLeafNode;
+using search::btree::BTreeDefaultTraits;
+using vespalib::GenerationHandler;
+
+namespace search {
+
+
+class FrozenBTreeTest : public vespalib::TestApp
+{
+public:
+ typedef int KeyType;
+private:
+ std::vector<KeyType> _randomValues;
+ std::vector<KeyType> _sortedRandomValues;
+
+public:
+ typedef int DataType;
+ typedef BTreeRoot<KeyType, DataType,
+ btree::NoAggregated,
+ std::less<KeyType>,
+ BTreeDefaultTraits> Tree;
+ typedef Tree::NodeAllocatorType NodeAllocator;
+ typedef Tree::InternalNodeType InternalNodeType;
+ typedef Tree::LeafNodeType LeafNodeType;
+ typedef Tree::Iterator Iterator;
+ typedef Tree::ConstIterator ConstIterator;
+private:
+ GenerationHandler *_generationHandler;
+ NodeAllocator *_allocator;
+ Tree *_tree;
+
+ Rand48 _randomGenerator;
+
+ void allocTree();
+ void freeTree(bool verbose);
+ void fillRandomValues(unsigned int count);
+ void insertRandomValues(Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
+ void removeRandomValues(Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
+ void lookupRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
+ void lookupGoneRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
+ void lookupFrozenRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
+ void sortRandomValues();
+ void traverseTreeIterator(const Tree &tree, NodeAllocator &allocator,
+ const std::vector<KeyType> &sorted, bool frozen);
+
+ void printSubEnumTree(BTreeNode::Ref node, NodeAllocator &allocator, int indent) const;
+ void printEnumTree(const Tree *tree, NodeAllocator &allocator);
+
+ static const char *frozenName(bool frozen) {
+ return frozen ? "frozen" : "thawed";
+ }
+public:
+ FrozenBTreeTest();
+ ~FrozenBTreeTest();
+
+ int Main() override;
+};
+
+FrozenBTreeTest::FrozenBTreeTest()
+ : vespalib::TestApp(),
+ _randomValues(),
+ _sortedRandomValues(),
+ _generationHandler(NULL),
+ _allocator(NULL),
+ _tree(NULL),
+ _randomGenerator()
+{}
+FrozenBTreeTest::~FrozenBTreeTest() {}
+
+void
+FrozenBTreeTest::allocTree()
+{
+ assert(_generationHandler == NULL);
+ assert(_allocator == NULL);
+ assert(_tree == NULL);
+ _generationHandler = new GenerationHandler;
+ _allocator = new NodeAllocator();
+ _tree = new Tree;
+}
+
+
+void
+FrozenBTreeTest::freeTree(bool verbose)
+{
+#if 0
+ LOG(info,
+ "freeTree before clear: %" PRIu64 " (%" PRIu64 " held)"
+ ", %" PRIu32 " leaves",
+ static_cast<uint64_t>(_intTree->getUsedMemory()),
+ static_cast<uint64_t>(_intTree->getHeldMemory()),
+ _intTree->validLeaves());
+ _intTree->clear();
+ LOG(info,
+ "freeTree before unhold: %" PRIu64 " (%" PRIu64 " held)",
+ static_cast<uint64_t>(_intTree->getUsedMemory()),
+ static_cast<uint64_t>(_intTree->getHeldMemory()));
+ _intTree->dropFrozen();
+ _intTree->removeOldGenerations(_intTree->getGeneration() + 1);
+ LOG(info,
+ "freeTree after unhold: %" PRIu64 " (%" PRIu64 " held)",
+ static_cast<uint64_t>(_intTree->getUsedMemory()),
+ static_cast<uint64_t>(_intTree->getHeldMemory()));
+ if (verbose)
+ LOG(info,
+ "%d+%d leftover tree nodes",
+ _intTree->getNumInternalNodes(),
+ _intTree->getNumLeafNodes());
+ EXPECT_TRUE(_intTree->getNumInternalNodes() == 0 &&
+ _intTree->getNumLeafNodes() == 0);
+ delete _intTree;
+ _intTree = NULL;
+ delete _intKeyStore;
+ _intKeyStore = NULL;
+#endif
+ (void) verbose;
+ _tree->clear(*_allocator);
+ _allocator->freeze();
+ _allocator->transferHoldLists(_generationHandler->getCurrentGeneration());
+ _generationHandler->incGeneration();
+ _allocator->trimHoldLists(_generationHandler->getFirstUsedGeneration());
+ delete _tree;
+ _tree = NULL;
+ delete _allocator;
+ _allocator = NULL;
+ delete _generationHandler;
+ _generationHandler = NULL;
+}
+
+
+void
+FrozenBTreeTest::fillRandomValues(unsigned int count)
+{
+ unsigned int i;
+
+ LOG(info, "Filling %u random values", count);
+ _randomValues.clear();
+ _randomValues.reserve(count);
+ _randomGenerator.srand48(42);
+ for (i = 0; i <count; i++)
+ _randomValues.push_back(_randomGenerator.lrand48());
+
+ EXPECT_TRUE(_randomValues.size() == count);
+}
+
+
+void
+FrozenBTreeTest::
+insertRandomValues(Tree &tree,
+ NodeAllocator &allocator,
+ const std::vector<KeyType> &values)
+{
+ std::vector<KeyType>::const_iterator i(values.begin());
+ std::vector<KeyType>::const_iterator ie(values.end());
+ Iterator p;
+
+ LOG(info, "insertRandomValues start");
+ for (; i != ie; ++i) {
+#ifdef LOG_FROZENBTREE
+ LOG(info, "Try lookup %d before insert", *i);
+#endif
+ p = tree.find(*i, allocator);
+ if (!p.valid()) {
+ DataType val = *i + 42;
+ if (tree.insert(*i, val, allocator))
+ p = tree.find(*i, allocator);
+ }
+ ASSERT_TRUE(p.valid() && p.getKey() == *i && p.getData() == *i + 42);
+#ifdef DEBUG_FROZENBTREEX
+ printEnumTree(&tree);
+#endif
+ }
+ ASSERT_TRUE(tree.isValid(allocator));
+ ASSERT_TRUE(tree.isValidFrozen(allocator));
+ LOG(info, "insertRandomValues done");
+}
+
+
+void
+FrozenBTreeTest::
+removeRandomValues(Tree &tree,
+ NodeAllocator &allocator,
+ const std::vector<KeyType> & values)
+{
+ std::vector<KeyType>::const_iterator i(values.begin());
+ std::vector<KeyType>::const_iterator ie(values.end());
+ Iterator p;
+
+ LOG(info, "removeRandomValues start");
+ for (; i != ie; ++i) {
+#ifdef LOG_FROZENBTREE
+ LOG(info, "Try lookup %d before remove", *i);
+#endif
+ p = tree.find(*i, allocator);
+ if (p.valid()) {
+ if (tree.remove(*i, allocator))
+ p = tree.find(*i, allocator);
+ }
+ ASSERT_TRUE(!p.valid());
+#ifdef DEBUG_FROZENBTREEX
+ tree.printTree();
+#endif
+ }
+ ASSERT_TRUE(tree.isValid(allocator));
+ ASSERT_TRUE(tree.isValidFrozen(allocator));
+ LOG(info, "removeRandomValues done");
+}
+
+
+void
+FrozenBTreeTest::
+lookupRandomValues(const Tree &tree,
+ NodeAllocator &allocator,
+ const std::vector<KeyType> &values)
+{
+ std::vector<KeyType>::const_iterator i(values.begin());
+ std::vector<KeyType>::const_iterator ie(values.end());
+ Iterator p;
+
+ LOG(info, "lookupRandomValues start");
+ for (; i != ie; ++i) {
+ p = tree.find(*i, allocator);
+ ASSERT_TRUE(p.valid() && p.getKey() == *i);
+ }
+ LOG(info, "lookupRandomValues done");
+}
+
+
+void
+FrozenBTreeTest::
+lookupGoneRandomValues(const Tree &tree,
+ NodeAllocator &allocator,
+ const std::vector<KeyType> &values)
+{
+ std::vector<KeyType>::const_iterator i(values.begin());
+ std::vector<KeyType>::const_iterator ie(values.end());
+ Iterator p;
+
+ LOG(info, "lookupGoneRandomValues start");
+ for (; i != ie; ++i) {
+ p = tree.find(*i, allocator);
+ ASSERT_TRUE(!p.valid());
+ }
+ LOG(info, "lookupGoneRandomValues done");
+}
+
+
+void
+FrozenBTreeTest::
+lookupFrozenRandomValues(const Tree &tree,
+ NodeAllocator &allocator,
+ const std::vector<KeyType> &values)
+{
+ std::vector<KeyType>::const_iterator i(values.begin());
+ std::vector<KeyType>::const_iterator ie(values.end());
+ ConstIterator p;
+
+ LOG(info, "lookupFrozenRandomValues start");
+ for (; i != ie; ++i) {
+ p = tree.getFrozenView(allocator).find(*i, std::less<int>());
+ ASSERT_TRUE(p.valid() && p.getKey() == *i && p.getData() == *i + 42);
+ }
+ LOG(info, "lookupFrozenRandomValues done");
+}
+
+
+void
+FrozenBTreeTest::sortRandomValues()
+{
+ std::vector<KeyType>::iterator i;
+ std::vector<KeyType>::iterator ie;
+ uint32_t okcnt;
+ int prevVal;
+ std::vector<KeyType> sorted;
+
+ LOG(info, "sortRandomValues start");
+ sorted = _randomValues;
+ std::sort(sorted.begin(), sorted.end());
+ _sortedRandomValues.clear();
+ _sortedRandomValues.reserve(sorted.size());
+
+ okcnt = 0;
+ prevVal = 0;
+ ie = sorted.end();
+ for (i = sorted.begin(); i != ie; ++i) {
+ if (i == _sortedRandomValues.begin() || *i > prevVal) {
+ okcnt++;
+ _sortedRandomValues.push_back(*i);
+ } else if (*i == prevVal)
+ okcnt++;
+ else
+ LOG_ABORT("should not be reached");
+ prevVal = *i;
+ }
+ EXPECT_TRUE(okcnt == sorted.size());
+ LOG(info, "sortRandomValues done");
+}
+
+
+void
+FrozenBTreeTest::
+traverseTreeIterator(const Tree &tree,
+ NodeAllocator &allocator,
+ const std::vector<KeyType> &sorted,
+ bool frozen)
+{
+ LOG(info,
+ "traverseTreeIterator %s start",
+ frozenName(frozen));
+
+ std::vector<KeyType>::const_iterator i;
+
+ i = sorted.begin();
+ if (frozen) {
+ ConstIterator ai;
+ ai = tree.getFrozenView(allocator).begin();
+ for (;ai.valid(); ++ai, ++i)
+ {
+ ASSERT_TRUE(ai.getKey() == *i);
+ }
+ } else {
+ Iterator ai;
+ ai = tree.begin(allocator);
+ for (;ai.valid(); ++ai, ++i)
+ {
+ ASSERT_TRUE(ai.getKey() == *i);
+ }
+ }
+
+
+ ASSERT_TRUE(i == sorted.end());
+
+ LOG(info,
+ "traverseTreeIterator %s done",
+ frozenName(frozen));
+}
+
+
+void
+FrozenBTreeTest::
+printSubEnumTree(BTreeNode::Ref node,
+ NodeAllocator &allocator,
+ int indent) const
+{
+ // typedef BTreeNode Node;
+ typedef LeafNodeType LeafNode;
+ typedef InternalNodeType InternalNode;
+ BTreeNode::Ref subNode;
+ unsigned int i;
+
+ if (allocator.isLeafRef(node)) {
+ const LeafNode *lnode = allocator.mapLeafRef(node);
+ printf("%*s LeafNode %s valid=%d\n",
+ indent, "",
+ lnode->getFrozen() ? "frozen" : "thawed",
+ lnode->validSlots());
+ for (i = 0; i < lnode->validSlots(); i++) {
+
+ KeyType k = lnode->getKey(i);
+ DataType d = lnode->getData(i);
+ printf("leaf value %3d %d %d\n",
+ (int) i,
+ (int) k,
+ (int) d);
+ }
+ return;
+ }
+ const InternalNode *inode = allocator.mapInternalRef(node);
+ printf("%*s IntermediteNode %s valid=%d\n",
+ indent, "",
+ inode->getFrozen() ? "frozen" : "thawed",
+ inode->validSlots());
+ for (i = 0; i < inode->validSlots(); i++) {
+ subNode = inode->getChild(i);
+ assert(subNode != BTreeNode::Ref());
+ printSubEnumTree(subNode, allocator, indent + 4);
+ }
+}
+
+
+void
+FrozenBTreeTest::printEnumTree(const Tree *tree,
+ NodeAllocator &allocator)
+{
+ printf("Tree Dump start\n");
+ if (!NodeAllocator::isValidRef(tree->getRoot())) {
+ printf("EMPTY\n");
+ } else {
+ printSubEnumTree(tree->getRoot(), allocator, 0);
+ }
+ printf("Tree Dump done\n");
+}
+
+
+
+int
+FrozenBTreeTest::Main()
+{
+ TEST_INIT("frozenbtree_test");
+
+ fillRandomValues(1000);
+ sortRandomValues();
+
+ allocTree();
+ insertRandomValues(*_tree, *_allocator, _randomValues);
+ lookupRandomValues(*_tree, *_allocator, _randomValues);
+ _allocator->freeze();
+ _allocator->transferHoldLists(_generationHandler->getCurrentGeneration());
+ lookupFrozenRandomValues(*_tree, *_allocator, _randomValues);
+ traverseTreeIterator(*_tree,
+ *_allocator,
+ _sortedRandomValues,
+ false);
+ traverseTreeIterator(*_tree,
+ *_allocator,
+ _sortedRandomValues,
+ true);
+ traverseTreeIterator(*_tree,
+ *_allocator,
+ _sortedRandomValues,
+ false);
+ traverseTreeIterator(*_tree,
+ *_allocator,
+ _sortedRandomValues,
+ true);
+ removeRandomValues(*_tree, *_allocator, _randomValues);
+ lookupGoneRandomValues(*_tree, *_allocator, _randomValues);
+ lookupFrozenRandomValues(*_tree, *_allocator,_randomValues);
+ traverseTreeIterator(*_tree,
+ *_allocator,
+ _sortedRandomValues,
+ true);
+ insertRandomValues(*_tree, *_allocator, _randomValues);
+ freeTree(true);
+
+ fillRandomValues(1000000);
+ sortRandomValues();
+
+ allocTree();
+ insertRandomValues(*_tree, *_allocator, _randomValues);
+ traverseTreeIterator(*_tree,
+ *_allocator,
+ _sortedRandomValues,
+ false);
+ freeTree(false);
+
+ TEST_DONE();
+}
+
+}
+
+TEST_APPHOOK(search::FrozenBTreeTest);
diff --git a/vespalib/src/tests/btree/iteratespeed.cpp b/vespalib/src/tests/btree/iteratespeed.cpp
new file mode 100644
index 00000000000..d1b9b3d7b1d
--- /dev/null
+++ b/vespalib/src/tests/btree/iteratespeed.cpp
@@ -0,0 +1,212 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/btree/btreeroot.h>
+#include <vespa/vespalib/btree/btreebuilder.h>
+#include <vespa/vespalib/btree/btreenodeallocator.h>
+#include <vespa/vespalib/btree/btree.h>
+#include <vespa/vespalib/btree/btreestore.h>
+#include <vespa/vespalib/btree/btreenodeallocator.hpp>
+#include <vespa/vespalib/btree/btreenode.hpp>
+#include <vespa/vespalib/btree/btreenodestore.hpp>
+#include <vespa/vespalib/btree/btreeiterator.hpp>
+#include <vespa/vespalib/btree/btreeroot.hpp>
+#include <vespa/vespalib/btree/btreebuilder.hpp>
+#include <vespa/vespalib/btree/btree.hpp>
+#include <vespa/vespalib/btree/btreestore.hpp>
+#include <vespa/vespalib/util/rand48.h>
+
+#include <vespa/fastos/app.h>
+#include <vespa/fastos/timestamp.h>
+
+#include <vespa/log/log.h>
+LOG_SETUP("iteratespeed");
+
+namespace search {
+namespace btree {
+
+enum class IterateMethod
+{
+ FORWARD,
+ BACKWARDS,
+ LAMBDA
+};
+
+class IterateSpeed : public FastOS_Application
+{
+ template <typename Traits, IterateMethod iterateMethod>
+ void
+ workLoop(int loops, bool enableForward, bool enableBackwards,
+ bool enableLambda, int leafSlots);
+ void usage();
+ int Main() override;
+};
+
+
+namespace {
+
+const char *iterateMethodName(IterateMethod iterateMethod)
+{
+ switch (iterateMethod) {
+ case IterateMethod::FORWARD:
+ return "forward";
+ case IterateMethod::BACKWARDS:
+ return "backwards";
+ default:
+ return "lambda";
+ }
+}
+
+}
+
+template <typename Traits, IterateMethod iterateMethod>
+void
+IterateSpeed::workLoop(int loops, bool enableForward, bool enableBackwards,
+ bool enableLambda, int leafSlots)
+{
+ if ((iterateMethod == IterateMethod::FORWARD && !enableForward) ||
+ (iterateMethod == IterateMethod::BACKWARDS && !enableBackwards) ||
+ (iterateMethod == IterateMethod::LAMBDA && !enableLambda) ||
+ (leafSlots != 0 &&
+ leafSlots != static_cast<int>(Traits::LEAF_SLOTS)))
+ return;
+ vespalib::GenerationHandler g;
+ using Tree = BTree<int, int, btree::NoAggregated, std::less<int>, Traits>;
+ using Builder = typename Tree::Builder;
+ using ConstIterator = typename Tree::ConstIterator;
+ Tree tree;
+ Builder builder(tree.getAllocator());
+ size_t numEntries = 1000000;
+ size_t numInnerLoops = 1000;
+ for (size_t i = 0; i < numEntries; ++i) {
+ builder.insert(i, 0);
+ }
+ tree.assign(builder);
+ assert(numEntries == tree.size());
+ assert(tree.isValid());
+ for (int l = 0; l < loops; ++l) {
+ fastos::TimeStamp before = fastos::ClockSystem::now();
+ uint64_t sum = 0;
+ for (size_t innerl = 0; innerl < numInnerLoops; ++innerl) {
+ if (iterateMethod == IterateMethod::FORWARD) {
+ ConstIterator itr(BTreeNode::Ref(), tree.getAllocator());
+ itr.begin(tree.getRoot());
+ while (itr.valid()) {
+ sum += itr.getKey();
+ ++itr;
+ }
+ } else if (iterateMethod == IterateMethod::BACKWARDS) {
+ ConstIterator itr(BTreeNode::Ref(), tree.getAllocator());
+ itr.end(tree.getRoot());
+ --itr;
+ while (itr.valid()) {
+ sum += itr.getKey();
+ --itr;
+ }
+ } else {
+ tree.getAllocator().foreach_key(tree.getRoot(),
+ [&](int key) { sum += key; } );
+ }
+ }
+ fastos::TimeStamp after = fastos::ClockSystem::now();
+ double used = after.sec() - before.sec();
+ printf("Elapsed time for iterating %ld steps is %8.5f, "
+ "direction=%s, fanout=%u,%u, sum=%" PRIu64 "\n",
+ numEntries * numInnerLoops,
+ used,
+ iterateMethodName(iterateMethod),
+ static_cast<int>(Traits::LEAF_SLOTS),
+ static_cast<int>(Traits::INTERNAL_SLOTS),
+ sum);
+ fflush(stdout);
+ }
+}
+
+
+void
+IterateSpeed::usage()
+{
+ printf("iteratspeed "
+ "[-F <leafSlots>] "
+ "[-b] "
+ "[-c <numLoops>] "
+ "[-f] "
+ "[-l]\n");
+}
+
+int
+IterateSpeed::Main()
+{
+ int argi;
+ char c;
+ const char *optArg;
+ argi = 1;
+ int loops = 1;
+ bool backwards = false;
+ bool forwards = false;
+ bool lambda = false;
+ int leafSlots = 0;
+ while ((c = GetOpt("F:bc:fl", optArg, argi)) != -1) {
+ switch (c) {
+ case 'F':
+ leafSlots = atoi(optArg);
+ break;
+ case 'b':
+ backwards = true;
+ break;
+ case 'c':
+ loops = atoi(optArg);
+ break;
+ case 'f':
+ forwards = true;
+ break;
+ case 'l':
+ lambda = true;
+ break;
+ default:
+ usage();
+ return 1;
+ }
+ }
+ if (!backwards && !forwards && !lambda) {
+ backwards = true;
+ forwards = true;
+ lambda = true;
+ }
+
+ using SmallTraits = BTreeTraits<4, 4, 31, false>;
+ using DefTraits = BTreeDefaultTraits;
+ using LargeTraits = BTreeTraits<32, 16, 10, true>;
+ using HugeTraits = BTreeTraits<64, 16, 10, true>;
+ workLoop<SmallTraits, IterateMethod::FORWARD>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<DefTraits, IterateMethod::FORWARD>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<LargeTraits, IterateMethod::FORWARD>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<HugeTraits, IterateMethod::FORWARD>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<SmallTraits, IterateMethod::BACKWARDS>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<DefTraits, IterateMethod::BACKWARDS>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<LargeTraits, IterateMethod::BACKWARDS>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<HugeTraits, IterateMethod::BACKWARDS>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<SmallTraits, IterateMethod::LAMBDA>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<DefTraits, IterateMethod::LAMBDA>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<LargeTraits, IterateMethod::LAMBDA>(loops, forwards, backwards,
+ lambda, leafSlots);
+ workLoop<HugeTraits, IterateMethod::LAMBDA>(loops, forwards, backwards,
+ lambda, leafSlots);
+ return 0;
+}
+
+}
+}
+
+FASTOS_MAIN(search::btree::IterateSpeed);
+
+