From feeb84678fbdc38dc4e3ec5ec266ab1f85608027 Mon Sep 17 00:00:00 2001 From: Tor Egge Date: Wed, 21 Jun 2017 09:17:52 +0000 Subject: Move btree unit tests to proper location. --- searchlib/src/tests/btree/.gitignore | 2 + searchlib/src/tests/btree/CMakeLists.txt | 14 + searchlib/src/tests/btree/DESC | 1 - searchlib/src/tests/btree/FILES | 1 - searchlib/src/tests/btree/btree_test.cpp | 1278 ++++++++++++++++++++ searchlib/src/tests/btree/frozenbtree_test.cpp | 469 +++++++ searchlib/src/tests/memoryindex/btree/.gitignore | 6 - .../src/tests/memoryindex/btree/CMakeLists.txt | 15 - searchlib/src/tests/memoryindex/btree/DESC | 1 - searchlib/src/tests/memoryindex/btree/FILES | 1 - .../src/tests/memoryindex/btree/btree_test.cpp | 1278 -------------------- .../tests/memoryindex/btree/frozenbtree_test.cpp | 469 ------- 12 files changed, 1763 insertions(+), 1772 deletions(-) delete mode 100644 searchlib/src/tests/btree/DESC delete mode 100644 searchlib/src/tests/btree/FILES create mode 100644 searchlib/src/tests/btree/btree_test.cpp create mode 100644 searchlib/src/tests/btree/frozenbtree_test.cpp delete mode 100644 searchlib/src/tests/memoryindex/btree/.gitignore delete mode 100644 searchlib/src/tests/memoryindex/btree/CMakeLists.txt delete mode 100644 searchlib/src/tests/memoryindex/btree/DESC delete mode 100644 searchlib/src/tests/memoryindex/btree/FILES delete mode 100644 searchlib/src/tests/memoryindex/btree/btree_test.cpp delete mode 100644 searchlib/src/tests/memoryindex/btree/frozenbtree_test.cpp (limited to 'searchlib/src') diff --git a/searchlib/src/tests/btree/.gitignore b/searchlib/src/tests/btree/.gitignore index a6bdd572c7d..0cc4519cf9c 100644 --- a/searchlib/src/tests/btree/.gitignore +++ b/searchlib/src/tests/btree/.gitignore @@ -1,3 +1,5 @@ iteratespeed +searchlib_btree_test_app searchlib_btreeaggregation_test_app +searchlib_frozenbtree_test_app searchlib_iteratespeed_app diff --git a/searchlib/src/tests/btree/CMakeLists.txt b/searchlib/src/tests/btree/CMakeLists.txt index dbd631ca353..9817f2b9079 100644 --- a/searchlib/src/tests/btree/CMakeLists.txt +++ b/searchlib/src/tests/btree/CMakeLists.txt @@ -1,4 +1,18 @@ # Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +vespa_add_executable(searchlib_btree_test_app TEST + SOURCES + btree_test.cpp + DEPENDS + searchlib +) +vespa_add_test(NAME searchlib_btree_test_app COMMAND searchlib_btree_test_app) +vespa_add_executable(searchlib_frozenbtree_test_app TEST + SOURCES + frozenbtree_test.cpp + DEPENDS + searchlib +) +vespa_add_test(NAME searchlib_frozenbtree_test_app COMMAND searchlib_frozenbtree_test_app) vespa_add_executable(searchlib_btreeaggregation_test_app TEST SOURCES btreeaggregation_test.cpp diff --git a/searchlib/src/tests/btree/DESC b/searchlib/src/tests/btree/DESC deleted file mode 100644 index da074ca2c45..00000000000 --- a/searchlib/src/tests/btree/DESC +++ /dev/null @@ -1 +0,0 @@ -btree aggregation test. Take a look at btreeaggregation_test.cpp for details. diff --git a/searchlib/src/tests/btree/FILES b/searchlib/src/tests/btree/FILES deleted file mode 100644 index 45756255961..00000000000 --- a/searchlib/src/tests/btree/FILES +++ /dev/null @@ -1 +0,0 @@ -btreeaggregation_test.cpp diff --git a/searchlib/src/tests/btree/btree_test.cpp b/searchlib/src/tests/btree/btree_test.cpp new file mode 100644 index 00000000000..bd84ea09be6 --- /dev/null +++ b/searchlib/src/tests/btree/btree_test.cpp @@ -0,0 +1,1278 @@ +// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#include +LOG_SETUP("btree_test"); +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +using vespalib::GenerationHandler; +using search::datastore::EntryRef; + +namespace search { +namespace btree { + +namespace { + +template +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 MyComp; +#define UNWRAP(key) (key) +#endif + +typedef BTree MyTree; +typedef BTreeStore MyTreeStore; +typedef MyTree::Builder MyTreeBuilder; +typedef MyTree::LeafNodeType MyLeafNode; +typedef MyTree::InternalNodeType MyInternalNode; +typedef MyTree::NodeAllocatorType MyNodeAllocator; +typedef std::pair LeafPair; +typedef MyTreeStore::KeyDataType MyKeyData; +typedef MyTreeStore::KeyDataTypeRefPair MyKeyDataRefPair; + +typedef BTree SetTreeB; + +typedef BTreeTraits<16, 16, 10, false> LSeekTraits; +typedef BTree, LSeekTraits> SetTreeL; + +struct LeafPairLess { + bool operator()(const LeafPair & lhs, const LeafPair & rhs) const { + return UNWRAP(lhs.first) < UNWRAP(rhs.first); + } +}; + +template +void +cleanup(GenerationHandler & g, ManagerType & m) +{ + m.freeze(); + m.transferHoldLists(g.getCurrentGeneration()); + g.incGeneration(); + m.trimHoldLists(g.getFirstUsedGeneration()); +} + +template +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 + 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 MemoryUsage & exp, const MemoryUsage & act); + + void + buildSubTree(const std::vector &sub, + size_t numEntries); + + void requireThatNodeInsertWorks(); + void requireThatNodeSplitInsertWorks(); + void requireThatNodeStealWorks(); + void requireThatNodeRemoveWorks(); + void requireThatNodeLowerBoundWorks(); + void requireThatWeCanInsertAndRemoveFromTree(); + void requireThatSortedTreeInsertWorks(); + void requireThatCornerCaseTreeFindWorks(); + void requireThatBasicTreeIteratorWorks(); + void requireThatTreeIteratorSeekWorks(); + void requireThatTreeIteratorAssignWorks(); + void requireThatMemoryUsageIsCalculated(); + template + void requireThatLowerBoundWorksT(); + void requireThatLowerBoundWorks(); + template + void requireThatUpperBoundWorksT(); + void requireThatUpperBoundWorks(); + void requireThatUpdateOfKeyWorks(); + + void + requireThatSmallNodesWorks(); + + void + requireThatApplyWorks(); + + void + requireThatIteratorDistanceWorks(int numEntries); + + void + requireThatIteratorDistanceWorks(); +public: + int Main() override; +}; + +template +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 MemoryUsage & exp, const 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); +} + +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; +}; + +void +Test::requireThatNodeStealWorks() +{ + typedef BTreeLeafNode MyStealNode; + typedef BTreeNodeAllocator + 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::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 & 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 &sub, + size_t numEntries) +{ + GenerationHandler g; + MyTree tree; + MyTreeBuilder builder(tree.getAllocator()); + + std::vector 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 exp; + std::vector 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 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 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); + } +} + +void +Test::requireThatMemoryUsageIsCalculated() +{ + typedef BTreeNodeAllocator 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; + MemoryUsage mu; + const uint32_t initialInternalNodes = 128u; + const uint32_t initialLeafNodes = 128u; + mu.incAllocatedBytes(sizeof(INode) * initialInternalNodes); + mu.incAllocatedBytes(sizeof(LNode) * initialLeafNodes); + 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 = MemoryUsage(); + mu.incAllocatedBytes(sizeof(INode) * initialInternalNodes); + mu.incAllocatedBytes(sizeof(LNode) * initialLeafNodes); + 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 +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(); + requireThatLowerBoundWorksT(); +} + +template +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(); + requireThatUpperBoundWorksT(); +} + +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 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 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 TreeStore; + typedef TreeStore::KeyType KeyType; + typedef TreeStore::KeyDataType KeyDataType; + GenerationHandler g; + TreeStore s; + std::vector additions; + std::vector 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(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(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(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(); + requireThatNodeSplitInsertWorks(); + requireThatNodeStealWorks(); + 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/searchlib/src/tests/btree/frozenbtree_test.cpp b/searchlib/src/tests/btree/frozenbtree_test.cpp new file mode 100644 index 00000000000..399c20f53cc --- /dev/null +++ b/searchlib/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 +#include +#include +#include +#include +#include +#include + +#include +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 _randomValues; + std::vector _sortedRandomValues; + +public: + typedef int DataType; + typedef BTreeRoot, + 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 &values); + void removeRandomValues(Tree &tree, NodeAllocator &allocator, const std::vector &values); + void lookupRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector &values); + void lookupGoneRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector &values); + void lookupFrozenRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector &values); + void sortRandomValues(); + void traverseTreeIterator(const Tree &tree, NodeAllocator &allocator, + const std::vector &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(_intTree->getUsedMemory()), + static_cast(_intTree->getHeldMemory()), + _intTree->validLeaves()); + _intTree->clear(); + LOG(info, + "freeTree before unhold: %" PRIu64 " (%" PRIu64 " held)", + static_cast(_intTree->getUsedMemory()), + static_cast(_intTree->getHeldMemory())); + _intTree->dropFrozen(); + _intTree->removeOldGenerations(_intTree->getGeneration() + 1); + LOG(info, + "freeTree after unhold: %" PRIu64 " (%" PRIu64 " held)", + static_cast(_intTree->getUsedMemory()), + static_cast(_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 &values) +{ + std::vector::const_iterator i(values.begin()); + std::vector::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 & values) +{ + std::vector::const_iterator i(values.begin()); + std::vector::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 &values) +{ + std::vector::const_iterator i(values.begin()); + std::vector::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 &values) +{ + std::vector::const_iterator i(values.begin()); + std::vector::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 &values) +{ + std::vector::const_iterator i(values.begin()); + std::vector::const_iterator ie(values.end()); + ConstIterator p; + + LOG(info, "lookupFrozenRandomValues start"); + for (; i != ie; ++i) { + p = tree.getFrozenView(allocator).find(*i, std::less()); + ASSERT_TRUE(p.valid() && p.getKey() == *i && p.getData() == *i + 42); + } + LOG(info, "lookupFrozenRandomValues done"); +} + + +void +FrozenBTreeTest::sortRandomValues() +{ + std::vector::iterator i; + std::vector::iterator ie; + uint32_t okcnt; + int prevVal; + std::vector 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 + abort(); + prevVal = *i; + } + EXPECT_TRUE(okcnt == sorted.size()); + LOG(info, "sortRandomValues done"); +} + + +void +FrozenBTreeTest:: +traverseTreeIterator(const Tree &tree, + NodeAllocator &allocator, + const std::vector &sorted, + bool frozen) +{ + LOG(info, + "traverseTreeIterator %s start", + frozenName(frozen)); + + std::vector::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/searchlib/src/tests/memoryindex/btree/.gitignore b/searchlib/src/tests/memoryindex/btree/.gitignore deleted file mode 100644 index 94440affa90..00000000000 --- a/searchlib/src/tests/memoryindex/btree/.gitignore +++ /dev/null @@ -1,6 +0,0 @@ -.depend -Makefile -btree_test -frozenbtree_test -searchlib_btree_test_app -searchlib_frozenbtree_test_app diff --git a/searchlib/src/tests/memoryindex/btree/CMakeLists.txt b/searchlib/src/tests/memoryindex/btree/CMakeLists.txt deleted file mode 100644 index 55b01f353aa..00000000000 --- a/searchlib/src/tests/memoryindex/btree/CMakeLists.txt +++ /dev/null @@ -1,15 +0,0 @@ -# Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -vespa_add_executable(searchlib_btree_test_app TEST - SOURCES - btree_test.cpp - DEPENDS - searchlib -) -vespa_add_test(NAME searchlib_btree_test_app COMMAND searchlib_btree_test_app) -vespa_add_executable(searchlib_frozenbtree_test_app TEST - SOURCES - frozenbtree_test.cpp - DEPENDS - searchlib -) -vespa_add_test(NAME searchlib_frozenbtree_test_app COMMAND searchlib_frozenbtree_test_app) diff --git a/searchlib/src/tests/memoryindex/btree/DESC b/searchlib/src/tests/memoryindex/btree/DESC deleted file mode 100644 index 02739da7527..00000000000 --- a/searchlib/src/tests/memoryindex/btree/DESC +++ /dev/null @@ -1 +0,0 @@ -btree test. Take a look at btree_test.cpp for details. diff --git a/searchlib/src/tests/memoryindex/btree/FILES b/searchlib/src/tests/memoryindex/btree/FILES deleted file mode 100644 index e63a2f68eb4..00000000000 --- a/searchlib/src/tests/memoryindex/btree/FILES +++ /dev/null @@ -1 +0,0 @@ -btree_test.cpp diff --git a/searchlib/src/tests/memoryindex/btree/btree_test.cpp b/searchlib/src/tests/memoryindex/btree/btree_test.cpp deleted file mode 100644 index bd84ea09be6..00000000000 --- a/searchlib/src/tests/memoryindex/btree/btree_test.cpp +++ /dev/null @@ -1,1278 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include -LOG_SETUP("btree_test"); -#include -#include -#include -#include -#include -#include -#include -#include - -#include -#include -#include -#include -#include -#include -#include -#include - -using vespalib::GenerationHandler; -using search::datastore::EntryRef; - -namespace search { -namespace btree { - -namespace { - -template -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 MyComp; -#define UNWRAP(key) (key) -#endif - -typedef BTree MyTree; -typedef BTreeStore MyTreeStore; -typedef MyTree::Builder MyTreeBuilder; -typedef MyTree::LeafNodeType MyLeafNode; -typedef MyTree::InternalNodeType MyInternalNode; -typedef MyTree::NodeAllocatorType MyNodeAllocator; -typedef std::pair LeafPair; -typedef MyTreeStore::KeyDataType MyKeyData; -typedef MyTreeStore::KeyDataTypeRefPair MyKeyDataRefPair; - -typedef BTree SetTreeB; - -typedef BTreeTraits<16, 16, 10, false> LSeekTraits; -typedef BTree, LSeekTraits> SetTreeL; - -struct LeafPairLess { - bool operator()(const LeafPair & lhs, const LeafPair & rhs) const { - return UNWRAP(lhs.first) < UNWRAP(rhs.first); - } -}; - -template -void -cleanup(GenerationHandler & g, ManagerType & m) -{ - m.freeze(); - m.transferHoldLists(g.getCurrentGeneration()); - g.incGeneration(); - m.trimHoldLists(g.getFirstUsedGeneration()); -} - -template -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 - 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 MemoryUsage & exp, const MemoryUsage & act); - - void - buildSubTree(const std::vector &sub, - size_t numEntries); - - void requireThatNodeInsertWorks(); - void requireThatNodeSplitInsertWorks(); - void requireThatNodeStealWorks(); - void requireThatNodeRemoveWorks(); - void requireThatNodeLowerBoundWorks(); - void requireThatWeCanInsertAndRemoveFromTree(); - void requireThatSortedTreeInsertWorks(); - void requireThatCornerCaseTreeFindWorks(); - void requireThatBasicTreeIteratorWorks(); - void requireThatTreeIteratorSeekWorks(); - void requireThatTreeIteratorAssignWorks(); - void requireThatMemoryUsageIsCalculated(); - template - void requireThatLowerBoundWorksT(); - void requireThatLowerBoundWorks(); - template - void requireThatUpperBoundWorksT(); - void requireThatUpperBoundWorks(); - void requireThatUpdateOfKeyWorks(); - - void - requireThatSmallNodesWorks(); - - void - requireThatApplyWorks(); - - void - requireThatIteratorDistanceWorks(int numEntries); - - void - requireThatIteratorDistanceWorks(); -public: - int Main() override; -}; - -template -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 MemoryUsage & exp, const 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); -} - -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; -}; - -void -Test::requireThatNodeStealWorks() -{ - typedef BTreeLeafNode MyStealNode; - typedef BTreeNodeAllocator - 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::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 & 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 &sub, - size_t numEntries) -{ - GenerationHandler g; - MyTree tree; - MyTreeBuilder builder(tree.getAllocator()); - - std::vector 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 exp; - std::vector 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 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 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); - } -} - -void -Test::requireThatMemoryUsageIsCalculated() -{ - typedef BTreeNodeAllocator 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; - MemoryUsage mu; - const uint32_t initialInternalNodes = 128u; - const uint32_t initialLeafNodes = 128u; - mu.incAllocatedBytes(sizeof(INode) * initialInternalNodes); - mu.incAllocatedBytes(sizeof(LNode) * initialLeafNodes); - 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 = MemoryUsage(); - mu.incAllocatedBytes(sizeof(INode) * initialInternalNodes); - mu.incAllocatedBytes(sizeof(LNode) * initialLeafNodes); - 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 -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(); - requireThatLowerBoundWorksT(); -} - -template -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(); - requireThatUpperBoundWorksT(); -} - -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 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 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 TreeStore; - typedef TreeStore::KeyType KeyType; - typedef TreeStore::KeyDataType KeyDataType; - GenerationHandler g; - TreeStore s; - std::vector additions; - std::vector 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(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(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(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(); - requireThatNodeSplitInsertWorks(); - requireThatNodeStealWorks(); - 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/searchlib/src/tests/memoryindex/btree/frozenbtree_test.cpp b/searchlib/src/tests/memoryindex/btree/frozenbtree_test.cpp deleted file mode 100644 index 399c20f53cc..00000000000 --- a/searchlib/src/tests/memoryindex/btree/frozenbtree_test.cpp +++ /dev/null @@ -1,469 +0,0 @@ -// 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 -#include -#include -#include -#include -#include -#include - -#include -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 _randomValues; - std::vector _sortedRandomValues; - -public: - typedef int DataType; - typedef BTreeRoot, - 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 &values); - void removeRandomValues(Tree &tree, NodeAllocator &allocator, const std::vector &values); - void lookupRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector &values); - void lookupGoneRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector &values); - void lookupFrozenRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector &values); - void sortRandomValues(); - void traverseTreeIterator(const Tree &tree, NodeAllocator &allocator, - const std::vector &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(_intTree->getUsedMemory()), - static_cast(_intTree->getHeldMemory()), - _intTree->validLeaves()); - _intTree->clear(); - LOG(info, - "freeTree before unhold: %" PRIu64 " (%" PRIu64 " held)", - static_cast(_intTree->getUsedMemory()), - static_cast(_intTree->getHeldMemory())); - _intTree->dropFrozen(); - _intTree->removeOldGenerations(_intTree->getGeneration() + 1); - LOG(info, - "freeTree after unhold: %" PRIu64 " (%" PRIu64 " held)", - static_cast(_intTree->getUsedMemory()), - static_cast(_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 &values) -{ - std::vector::const_iterator i(values.begin()); - std::vector::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 & values) -{ - std::vector::const_iterator i(values.begin()); - std::vector::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 &values) -{ - std::vector::const_iterator i(values.begin()); - std::vector::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 &values) -{ - std::vector::const_iterator i(values.begin()); - std::vector::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 &values) -{ - std::vector::const_iterator i(values.begin()); - std::vector::const_iterator ie(values.end()); - ConstIterator p; - - LOG(info, "lookupFrozenRandomValues start"); - for (; i != ie; ++i) { - p = tree.getFrozenView(allocator).find(*i, std::less()); - ASSERT_TRUE(p.valid() && p.getKey() == *i && p.getData() == *i + 42); - } - LOG(info, "lookupFrozenRandomValues done"); -} - - -void -FrozenBTreeTest::sortRandomValues() -{ - std::vector::iterator i; - std::vector::iterator ie; - uint32_t okcnt; - int prevVal; - std::vector 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 - abort(); - prevVal = *i; - } - EXPECT_TRUE(okcnt == sorted.size()); - LOG(info, "sortRandomValues done"); -} - - -void -FrozenBTreeTest:: -traverseTreeIterator(const Tree &tree, - NodeAllocator &allocator, - const std::vector &sorted, - bool frozen) -{ - LOG(info, - "traverseTreeIterator %s start", - frozenName(frozen)); - - std::vector::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); -- cgit v1.2.3