diff options
Diffstat (limited to 'vespalib/src/tests/btree/btreeaggregation_test.cpp')
-rw-r--r-- | vespalib/src/tests/btree/btreeaggregation_test.cpp | 1157 |
1 files changed, 1157 insertions, 0 deletions
diff --git a/vespalib/src/tests/btree/btreeaggregation_test.cpp b/vespalib/src/tests/btree/btreeaggregation_test.cpp new file mode 100644 index 00000000000..0ce3d2c7d04 --- /dev/null +++ b/vespalib/src/tests/btree/btreeaggregation_test.cpp @@ -0,0 +1,1157 @@ +// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#include <vespa/log/log.h> +LOG_SETUP("btreeaggregation_test"); +#include <vespa/vespalib/testkit/testapp.h> +#include <vespa/vespalib/btree/btreeroot.h> +#include <vespa/vespalib/btree/btreebuilder.h> +#include <vespa/vespalib/btree/btreenodeallocator.h> +#include <vespa/vespalib/btree/btree.h> +#include <vespa/vespalib/btree/btreestore.h> +#include <vespa/vespalib/btree/btreenodeallocator.hpp> +#include <vespa/vespalib/btree/btreenode.hpp> +#include <vespa/vespalib/btree/btreenodestore.hpp> +#include <vespa/vespalib/btree/btreeiterator.hpp> +#include <vespa/vespalib/btree/btreeroot.hpp> +#include <vespa/vespalib/btree/btreebuilder.hpp> +#include <vespa/vespalib/btree/btree.hpp> +#include <vespa/vespalib/btree/btreestore.hpp> +#include <vespa/vespalib/btree/btreeaggregator.hpp> +#include <vespa/vespalib/test/btree/btree_printer.h> +#include <vespa/vespalib/util/rand48.h> + +#include <iostream> +#include <map> +#include <set> +#include <string> + +using vespalib::GenerationHandler; +using search::datastore::EntryRef; + +namespace search { +namespace btree { + +namespace { + +int32_t +toVal(uint32_t key) +{ + return key + 1000; +} + +int32_t +toHighVal(uint32_t key) +{ + return toVal(key) + 1000; +} + +int32_t +toLowVal(uint32_t key) +{ + return toVal(key) - 1000000; +} + +int32_t +toNotVal(uint32_t key) +{ + return key + 2000; +} + +} + +typedef BTreeTraits<4, 4, 31, false> MyTraits; + +#define KEYWRAP + +#ifdef KEYWRAP + +// Force use of functor to compare keys. +class WrapInt +{ +public: + int _val; + WrapInt(int val) : _val(val) {} + WrapInt() : _val(0) {} + bool operator==(const WrapInt & rhs) const { return _val == rhs._val; } +}; + +std::ostream & +operator<<(std::ostream &s, const WrapInt &i) +{ + s << i._val; + return s; +} + +typedef WrapInt MyKey; +class MyComp +{ +public: + bool + operator()(const WrapInt &a, const WrapInt &b) const + { + return a._val < b._val; + } +}; + +#define UNWRAP(key) (key._val) +#else +typedef int MyKey; +typedef std::less<int> MyComp; +#define UNWRAP(key) (key) +#endif + +typedef BTree<MyKey, int32_t, + btree::MinMaxAggregated, + MyComp, MyTraits, + MinMaxAggrCalc> MyTree; +typedef BTreeStore<MyKey, int32_t, + btree::MinMaxAggregated, + MyComp, + BTreeDefaultTraits, + MinMaxAggrCalc> MyTreeStore; +typedef MyTree::Builder MyTreeBuilder; +typedef MyTree::LeafNodeType MyLeafNode; +typedef MyTree::InternalNodeType MyInternalNode; +typedef MyTree::NodeAllocatorType MyNodeAllocator; +typedef MyTree::Builder::Aggregator MyAggregator; +typedef MyTree::AggrCalcType MyAggrCalc; +typedef std::pair<MyKey, int32_t> LeafPair; +typedef MyTreeStore::KeyDataType MyKeyData; +typedef MyTreeStore::KeyDataTypeRefPair MyKeyDataRefPair; + +typedef BTree<int, BTreeNoLeafData, btree::NoAggregated> SetTreeB; + +typedef BTreeTraits<16, 16, 10, false> LSeekTraits; +typedef BTree<int, BTreeNoLeafData, btree::NoAggregated, + std::less<int>, LSeekTraits> SetTreeL; + +struct LeafPairLess { + bool operator()(const LeafPair & lhs, const LeafPair & rhs) const { + return UNWRAP(lhs.first) < UNWRAP(rhs.first); + } +}; + + +class MockTree +{ +public: + typedef std::map<uint32_t, int32_t> MTree; + typedef std::map<int32_t, std::set<uint32_t> > MRTree; + MTree _tree; + MRTree _rtree; + + MockTree(); + ~MockTree(); + + + void + erase(uint32_t key) + { + MTree::iterator it(_tree.find(key)); + if (it == _tree.end()) + return; + int32_t oval = it->second; + MRTree::iterator rit(_rtree.find(oval)); + assert(rit != _rtree.end()); + size_t ecount = rit->second.erase(key); + assert(ecount == 1); + (void) ecount; + if (rit->second.empty()) { + _rtree.erase(oval); + } + _tree.erase(key); + } + + void + insert(uint32_t key, int32_t val) + { + erase(key); + _tree[key] = val; + _rtree[val].insert(key); + } +}; + + +MockTree::MockTree() + : _tree(), + _rtree() +{} +MockTree::~MockTree() {} + +class MyTreeForceApplyStore : public MyTreeStore +{ +public: + typedef MyComp CompareT; + + bool + insert(EntryRef &ref, const KeyType &key, const DataType &data, + CompareT comp = CompareT()); + + bool + remove(EntryRef &ref, const KeyType &key, CompareT comp = CompareT()); +}; + + +bool +MyTreeForceApplyStore::insert(EntryRef &ref, + const KeyType &key, const DataType &data, + CompareT comp) +{ + bool retVal = true; + if (ref.valid()) { + RefType iRef(ref); + uint32_t clusterSize = getClusterSize(iRef); + if (clusterSize == 0) { + const BTreeType *tree = getTreeEntry(iRef); + const NodeAllocatorType &allocator = getAllocator(); + Iterator itr = tree->find(key, allocator, comp); + if (itr.valid()) + retVal = false; + } else { + const KeyDataType *old = getKeyDataEntry(iRef, clusterSize); + const KeyDataType *olde = old + clusterSize; + const KeyDataType *oldi = lower_bound(old, olde, key, comp); + if (oldi < olde && !comp(key, oldi->_key)) + retVal = false; // key already present + } + } + KeyDataType addition(key, data); + if (retVal) { + apply(ref, &addition, &addition+1, NULL, NULL, comp); + } + return retVal; +} + + +bool +MyTreeForceApplyStore::remove(EntryRef &ref, const KeyType &key, + CompareT comp) +{ + bool retVal = true; + if (!ref.valid()) + retVal = false; // not found + else { + RefType iRef(ref); + uint32_t clusterSize = getClusterSize(iRef); + if (clusterSize == 0) { + const BTreeType *tree = getTreeEntry(iRef); + const NodeAllocatorType &allocator = getAllocator(); + Iterator itr = tree->find(key, allocator, comp); + if (!itr.valid()) + retVal = false; + } else { + const KeyDataType *old = getKeyDataEntry(iRef, clusterSize); + const KeyDataType *olde = old + clusterSize; + const KeyDataType *oldi = lower_bound(old, olde, key, comp); + if (oldi == olde || comp(key, oldi->_key)) + retVal = false; // not found + } + } + std::vector<KeyDataType> additions; + std::vector<KeyType> removals; + removals.push_back(key); + apply(ref, + &additions[0], &additions[additions.size()], + &removals[0], &removals[removals.size()], + comp); + return retVal; +} + + +template <typename ManagerType> +void +freezeTree(GenerationHandler &g, ManagerType &m) +{ + m.freeze(); + m.transferHoldLists(g.getCurrentGeneration()); + g.incGeneration(); + m.trimHoldLists(g.getFirstUsedGeneration()); +} + +template <typename ManagerType> +void +cleanup(GenerationHandler &g, ManagerType &m) +{ + freezeTree(g, m); +} + +template <typename ManagerType, typename NodeType> +void +cleanup(GenerationHandler & g, + ManagerType & m, + BTreeNode::Ref n1Ref, NodeType * n1, + BTreeNode::Ref n2Ref = BTreeNode::Ref(), NodeType * n2 = NULL) +{ + assert(ManagerType::isValidRef(n1Ref)); + m.holdNode(n1Ref, n1); + if (n2 != NULL) { + assert(ManagerType::isValidRef(n2Ref)); + m.holdNode(n2Ref, n2); + } else { + assert(!ManagerType::isValidRef(n2Ref)); + } + cleanup(g, m); +} + +class Test : public vespalib::TestApp { +private: + template <typename Tree> + bool + assertTree(const std::string & exp, const Tree &t); + + template <typename Tree> + bool + assertAggregated(const MockTree &m, const Tree &t); + + template <typename TreeStore> + bool + assertAggregated(const MockTree &m, const TreeStore &s, EntryRef ref); + + void + buildSubTree(const std::vector<LeafPair> &sub, + size_t numEntries); + + void requireThatNodeInsertWorks(); + void requireThatNodeSplitInsertWorks(); + void requireThatTreeInsertWorks(); + void requireThatNodeStealWorks(); + void requireThatNodeRemoveWorks(); + void requireThatWeCanInsertAndRemoveFromTree(); + void requireThatSortedTreeInsertWorks(); + void requireThatCornerCaseTreeFindWorks(); + void requireThatBasicTreeIteratorWorks(); + void requireThatTreeIteratorAssignWorks(); + void requireThatUpdateOfKeyWorks(); + void requireThatUpdateOfDataWorks(); + + template <typename TreeStore> + void + requireThatSmallNodesWorks(); +public: + int Main() override; +}; + + +template<typename Tree> +bool +Test::assertTree(const std::string &exp, const Tree &t) +{ + std::stringstream ss; + test::BTreePrinter<std::stringstream, typename Tree::NodeAllocatorType> printer(ss, t.getAllocator()); + printer.print(t.getRoot()); + if (!EXPECT_EQUAL(exp, ss.str())) return false; + return true; +} + + +template <typename Tree> +bool +Test::assertAggregated(const MockTree &m, const Tree &t) +{ + const MinMaxAggregated &ta(t.getAggregated()); + if (t.getRoot().valid()) { + return + EXPECT_FALSE(m._rtree.empty()) && + EXPECT_EQUAL(m._rtree.rbegin()->first, + ta.getMax()) && + EXPECT_EQUAL(m._rtree.begin()->first, + ta.getMin()); + } else { + return EXPECT_TRUE(m._rtree.empty()) && + EXPECT_EQUAL(std::numeric_limits<int32_t>::min(), + ta.getMax()) && + EXPECT_EQUAL(std::numeric_limits<int32_t>::max(), + ta.getMin()); + } +} + +template <typename TreeStore> +bool +Test::assertAggregated(const MockTree &m, const TreeStore &s, EntryRef ref) +{ + typename TreeStore::Iterator i(s.begin(ref)); + MinMaxAggregated sa(s.getAggregated(ref)); + const MinMaxAggregated &ia(i.getAggregated()); + if (ref.valid()) { + return + EXPECT_FALSE(m._rtree.empty()) && + EXPECT_EQUAL(m._rtree.rbegin()->first, + ia.getMax()) && + EXPECT_EQUAL(m._rtree.begin()->first, + ia.getMin()) && + EXPECT_EQUAL(m._rtree.rbegin()->first, + sa.getMax()) && + EXPECT_EQUAL(m._rtree.begin()->first, + sa.getMin()); + } else { + return EXPECT_TRUE(m._rtree.empty()) && + EXPECT_EQUAL(std::numeric_limits<int32_t>::min(), + ia.getMax()) && + EXPECT_EQUAL(std::numeric_limits<int32_t>::max(), + ia.getMin()) && + EXPECT_EQUAL(std::numeric_limits<int32_t>::min(), + sa.getMax()) && + EXPECT_EQUAL(std::numeric_limits<int32_t>::max(), + sa.getMin()); + } +} + + +void +Test::requireThatNodeInsertWorks() +{ + MyTree t; + t.insert(20, 102); + EXPECT_TRUE(assertTree("{{20:102[min=102,max=102]}}", t)); + t.insert(10, 101); + EXPECT_TRUE(assertTree("{{10:101,20:102[min=101,max=102]}}", t)); + t.insert(30, 103); + t.insert(40, 104); + EXPECT_TRUE(assertTree("{{10:101,20:102,30:103,40:104[min=101,max=104]}}", t)); +} + +template <typename Tree> +void +populateTree(Tree &t, uint32_t count, uint32_t delta) +{ + uint32_t key = 1; + int32_t value = 101; + for (uint32_t i = 0; i < count; ++i) { + t.insert(key, value); + key += delta; + value += delta; + } +} + +void +populateLeafNode(MyTree &t) +{ + populateTree(t, 4, 2); +} + +void +Test::requireThatNodeSplitInsertWorks() +{ + { // new entry in current node + MyTree t; + populateLeafNode(t); + t.insert(4, 104); + EXPECT_TRUE(assertTree("{{4,7[min=101,max=107]}} -> " + "{{1:101,3:103,4:104[min=101,max=104]}," + "{5:105,7:107[min=105,max=107]}}", t)); + } + { // new entry in split node + MyTree t; + populateLeafNode(t); + t.insert(6, 106); + EXPECT_TRUE(assertTree("{{5,7[min=101,max=107]}} -> " + "{{1:101,3:103,5:105[min=101,max=105]}," + "{6:106,7:107[min=106,max=107]}}", t)); + } + { // new entry at end + MyTree t; + populateLeafNode(t); + t.insert(8, 108); + EXPECT_TRUE(assertTree("{{5,8[min=101,max=108]}} -> " + "{{1:101,3:103,5:105[min=101,max=105]}," + "{7:107,8:108[min=107,max=108]}}", t)); + } +} + +void +Test::requireThatTreeInsertWorks() +{ + { // multi level node split + MyTree t; + populateTree(t, 16, 2); + EXPECT_TRUE(assertTree("{{7,15,23,31[min=101,max=131]}} -> " + "{{1:101,3:103,5:105,7:107[min=101,max=107]}," + "{9:109,11:111,13:113,15:115[min=109,max=115]}," + "{17:117,19:119,21:121,23:123[min=117,max=123]}," + "{25:125,27:127,29:129,31:131[min=125,max=131]}}", t)); + t.insert(33, 133); + EXPECT_TRUE(assertTree("{{23,33[min=101,max=133]}} -> " + "{{7,15,23[min=101,max=123]},{29,33[min=125,max=133]}} -> " + "{{1:101,3:103,5:105,7:107[min=101,max=107]}," + "{9:109,11:111,13:113,15:115[min=109,max=115]}," + "{17:117,19:119,21:121,23:123[min=117,max=123]}," + "{25:125,27:127,29:129[min=125,max=129]}," + "{31:131,33:133[min=131,max=133]}}", t)); + } + { // give to left node to avoid split + MyTree t; + populateTree(t, 8, 2); + t.remove(5); + EXPECT_TRUE(assertTree("{{7,15[min=101,max=115]}} -> " + "{{1:101,3:103,7:107[min=101,max=107]}," + "{9:109,11:111,13:113,15:115[min=109,max=115]}}", t)); + t.insert(10, 110); + EXPECT_TRUE(assertTree("{{9,15[min=101,max=115]}} -> " + "{{1:101,3:103,7:107,9:109[min=101,max=109]}," + "{10:110,11:111,13:113,15:115[min=110,max=115]}}", t)); + } + { // give to left node to avoid split, and move to left node + MyTree t; + populateTree(t, 8, 2); + t.remove(3); + t.remove(5); + EXPECT_TRUE(assertTree("{{7,15[min=101,max=115]}} -> " + "{{1:101,7:107[min=101,max=107]}," + "{9:109,11:111,13:113,15:115[min=109,max=115]}}", t)); + t.insert(8, 108); + EXPECT_TRUE(assertTree("{{9,15[min=101,max=115]}} -> " + "{{1:101,7:107,8:108,9:109[min=101,max=109]}," + "{11:111,13:113,15:115[min=111,max=115]}}", t)); + } + { // not give to left node to avoid split, but insert at end at left node + MyTree t; + populateTree(t, 8, 2); + t.remove(5); + EXPECT_TRUE(assertTree("{{7,15[min=101,max=115]}} -> " + "{{1:101,3:103,7:107[min=101,max=107]}," + "{9:109,11:111,13:113,15:115[min=109,max=115]}}", t)); + t.insert(8, 108); + EXPECT_TRUE(assertTree("{{8,15[min=101,max=115]}} -> " + "{{1:101,3:103,7:107,8:108[min=101,max=108]}," + "{9:109,11:111,13:113,15:115[min=109,max=115]}}", t)); + } + { // give to right node to avoid split + MyTree t; + populateTree(t, 8, 2); + t.remove(13); + EXPECT_TRUE(assertTree("{{7,15[min=101,max=115]}} -> " + "{{1:101,3:103,5:105,7:107[min=101,max=107]}," + "{9:109,11:111,15:115[min=109,max=115]}}", t)); + t.insert(4, 104); + EXPECT_TRUE(assertTree("{{5,15[min=101,max=115]}} -> " + "{{1:101,3:103,4:104,5:105[min=101,max=105]}," + "{7:107,9:109,11:111,15:115[min=107,max=115]}}", t)); + } + { // give to right node to avoid split and move to right node + using MyTraits6 = BTreeTraits<6, 6, 31, false>; + using Tree6 = BTree<MyKey, int32_t, btree::MinMaxAggregated, MyComp, MyTraits6, MinMaxAggrCalc>; + + Tree6 t; + populateTree(t, 12, 2); + t.remove(19); + t.remove(21); + t.remove(23); + EXPECT_TRUE(assertTree("{{11,17[min=101,max=117]}} -> " + "{{1:101,3:103,5:105,7:107,9:109,11:111[min=101,max=111]}," + "{13:113,15:115,17:117[min=113,max=117]}}", t)); + t.insert(10, 110); + EXPECT_TRUE(assertTree("{{7,17[min=101,max=117]}} -> " + "{{1:101,3:103,5:105,7:107[min=101,max=107]}," + "{9:109,10:110,11:111,13:113,15:115,17:117[min=109,max=117]}}", t)); + } +} + +struct BTreeStealTraits +{ + static const size_t LEAF_SLOTS = 6; + static const size_t INTERNAL_SLOTS = 6; + static const size_t PATH_SIZE = 20; + static const bool BINARY_SEEK = true; +}; + +void +Test::requireThatNodeStealWorks() +{ + typedef BTree<MyKey, int32_t, + btree::MinMaxAggregated, + MyComp, BTreeStealTraits, + MinMaxAggrCalc> MyStealTree; + { // steal all from left + MyStealTree t; + t.insert(10, 110); + t.insert(20, 120); + t.insert(30, 130); + t.insert(40, 140); + t.insert(50, 150); + t.insert(60, 160); + t.insert(35, 135); + t.remove(35); + EXPECT_TRUE(assertTree("{{30,60[min=110,max=160]}} -> " + "{{10:110,20:120,30:130[min=110,max=130]}," + "{40:140,50:150,60:160[min=140,max=160]}}", t)); + t.remove(50); + EXPECT_TRUE(assertTree("{{10:110,20:120,30:130,40:140,60:160[min=110,max=160]}}", t)); + } + { // steal all from right + MyStealTree t; + t.insert(10, 110); + t.insert(20, 120); + t.insert(30, 130); + t.insert(40, 140); + t.insert(50, 150); + t.insert(60, 160); + t.insert(35, 135); + t.remove(35); + EXPECT_TRUE(assertTree("{{30,60[min=110,max=160]}} -> " + "{{10:110,20:120,30:130[min=110,max=130]}," + "{40:140,50:150,60:160[min=140,max=160]}}", t)); + t.remove(20); + EXPECT_TRUE(assertTree("{{10:110,30:130,40:140,50:150,60:160[min=110,max=160]}}", t)); + } + { // steal some from left + MyStealTree t; + t.insert(10, 110); + t.insert(20, 120); + t.insert(30, 130); + t.insert(60, 160); + t.insert(70, 170); + t.insert(80, 180); + t.insert(50, 150); + t.insert(40, 140); + EXPECT_TRUE(assertTree("{{50,80[min=110,max=180]}} -> " + "{{10:110,20:120,30:130,40:140,50:150[min=110,max=150]}," + "{60:160,70:170,80:180[min=160,max=180]}}", t)); + t.remove(60); + EXPECT_TRUE(assertTree("{{30,80[min=110,max=180]}} -> " + "{{10:110,20:120,30:130[min=110,max=130]}," + "{40:140,50:150,70:170,80:180[min=140,max=180]}}", t)); + } + { // steal some from right + MyStealTree t; + t.insert(10, 110); + t.insert(20, 120); + t.insert(30, 130); + t.insert(40, 140); + t.insert(50, 150); + t.insert(60, 160); + t.insert(70, 170); + t.insert(80, 180); + t.insert(90, 190); + t.remove(40); + EXPECT_TRUE(assertTree("{{30,90[min=110,max=190]}} -> " + "{{10:110,20:120,30:130[min=110,max=130]}," + "{50:150,60:160,70:170,80:180,90:190[min=150,max=190]}}", t)); + t.remove(20); + EXPECT_TRUE(assertTree("{{60,90[min=110,max=190]}} -> " + "{{10:110,30:130,50:150,60:160[min=110,max=160]}," + "{70:170,80:180,90:190[min=170,max=190]}}", t)); + } +} + +void +Test::requireThatNodeRemoveWorks() +{ + MyTree t; + populateLeafNode(t); + t.remove(3); + EXPECT_TRUE(assertTree("{{1:101,5:105,7:107[min=101,max=107]}}", t)); + t.remove(1); + EXPECT_TRUE(assertTree("{{5:105,7:107[min=105,max=107]}}", t)); + t.remove(7); + EXPECT_TRUE(assertTree("{{5:105[min=105,max=105]}}", t)); +} + +void +generateData(std::vector<LeafPair> & data, size_t numEntries) +{ + data.reserve(numEntries); + Rand48 rnd; + rnd.srand48(10); + for (size_t i = 0; i < numEntries; ++i) { + int num = rnd.lrand48() % 10000000; + uint32_t val = toVal(num); + data.push_back(std::make_pair(num, val)); + } +} + +void +Test::buildSubTree(const std::vector<LeafPair> &sub, + size_t numEntries) +{ + GenerationHandler g; + MyTree tree; + MyTreeBuilder builder(tree.getAllocator()); + MockTree mock; + + std::vector<LeafPair> sorted(sub.begin(), sub.begin() + numEntries); + std::sort(sorted.begin(), sorted.end(), LeafPairLess()); + for (size_t i = 0; i < numEntries; ++i) { + int num = UNWRAP(sorted[i].first); + const uint32_t & val = sorted[i].second; + builder.insert(num, val); + mock.insert(num, val); + } + tree.assign(builder); + assert(numEntries == tree.size()); + assert(tree.isValid()); + + TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree))); + EXPECT_EQUAL(numEntries, tree.size()); + EXPECT_TRUE(tree.isValid()); + MyTree::Iterator itr = tree.begin(); + MyTree::Iterator ritr = itr; + if (numEntries > 0) { + EXPECT_TRUE(ritr.valid()); + EXPECT_EQUAL(0u, ritr.position()); + --ritr; + EXPECT_TRUE(!ritr.valid()); + EXPECT_EQUAL(numEntries, ritr.position()); + --ritr; + EXPECT_TRUE(ritr.valid()); + EXPECT_EQUAL(numEntries - 1, ritr.position()); + } else { + EXPECT_TRUE(!ritr.valid()); + EXPECT_EQUAL(0u, ritr.position()); + --ritr; + EXPECT_TRUE(!ritr.valid()); + EXPECT_EQUAL(0u, ritr.position()); + } + for (size_t i = 0; i < numEntries; ++i) { + EXPECT_TRUE(itr.valid()); + EXPECT_EQUAL(sorted[i].first, itr.getKey()); + EXPECT_EQUAL(sorted[i].second, itr.getData()); + ++itr; + } + EXPECT_TRUE(!itr.valid()); + ritr = itr; + EXPECT_TRUE(!ritr.valid()); + --ritr; + for (size_t i = 0; i < numEntries; ++i) { + EXPECT_TRUE(ritr.valid()); + EXPECT_EQUAL(sorted[numEntries - 1 - i].first, ritr.getKey()); + EXPECT_EQUAL(sorted[numEntries - 1 - i].second, ritr.getData()); + --ritr; + } + EXPECT_TRUE(!ritr.valid()); +} + +void +Test::requireThatWeCanInsertAndRemoveFromTree() +{ + GenerationHandler g; + MyTree tree; + MockTree mock; + std::vector<LeafPair> exp; + std::vector<LeafPair> sorted; + TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree))); + size_t numEntries = 1000; + generateData(exp, numEntries); + sorted = exp; + std::sort(sorted.begin(), sorted.end(), LeafPairLess()); + // insert entries + for (size_t i = 0; i < numEntries; ++i) { + int num = UNWRAP(exp[i].first); + const uint32_t & val = exp[i].second; + EXPECT_TRUE(!tree.find(num).valid()); + //LOG(info, "insert[%zu](%d, %s)", i, num, str.c_str()); + EXPECT_TRUE(tree.insert(num, val)); + EXPECT_TRUE(!tree.insert(num, val)); + mock.insert(num, val); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree))); + for (size_t j = 0; j <= i; ++j) { + //LOG(info, "find[%zu](%d)", j, exp[j].first._val); + MyTree::Iterator itr = tree.find(exp[j].first); + EXPECT_TRUE(itr.valid()); + EXPECT_EQUAL(exp[j].first, itr.getKey()); + EXPECT_EQUAL(exp[j].second, itr.getData()); + } + EXPECT_EQUAL(i + 1u, tree.size()); + EXPECT_TRUE(tree.isValid()); + buildSubTree(exp, i + 1); + } + //std::cout << "tree: " << tree.toString() << std::endl; + + { + MyTree::Iterator itr = tree.begin(); + MyTree::Iterator itre = itr; + MyTree::Iterator itre2; + MyTree::Iterator ritr = itr; + while (itre.valid()) + ++itre; + if (numEntries > 0) { + EXPECT_TRUE(ritr.valid()); + EXPECT_EQUAL(0u, ritr.position()); + --ritr; + EXPECT_TRUE(!ritr.valid()); + EXPECT_EQUAL(numEntries, ritr.position()); + --ritr; + EXPECT_TRUE(ritr.valid()); + EXPECT_EQUAL(numEntries - 1, ritr.position()); + } else { + EXPECT_TRUE(!ritr.valid()); + EXPECT_EQUAL(0u, ritr.position()); + --ritr; + EXPECT_TRUE(!ritr.valid()); + EXPECT_EQUAL(0u, ritr.position()); + } + MyTree::Iterator pitr = itr; + for (size_t i = 0; i < numEntries; ++i) { + ssize_t si = i; + ssize_t sileft = numEntries - i; + EXPECT_TRUE(itr.valid()); + EXPECT_EQUAL(i, itr.position()); + EXPECT_EQUAL(sileft, itre - itr); + EXPECT_EQUAL(-sileft, itr - itre); + EXPECT_EQUAL(sileft, itre2 - itr); + EXPECT_EQUAL(-sileft, itr - itre2); + EXPECT_EQUAL(si, itr - tree.begin()); + EXPECT_EQUAL(-si, tree.begin() - itr); + EXPECT_EQUAL(i != 0, itr - pitr); + EXPECT_EQUAL(-(i != 0), pitr - itr); + EXPECT_EQUAL(sorted[i].first, itr.getKey()); + EXPECT_EQUAL(sorted[i].second, itr.getData()); + pitr = itr; + ++itr; + ritr = itr; + --ritr; + EXPECT_TRUE(ritr.valid()); + EXPECT_TRUE(ritr == pitr); + } + EXPECT_TRUE(!itr.valid()); + EXPECT_EQUAL(numEntries, itr.position()); + ssize_t sNumEntries = numEntries; + EXPECT_EQUAL(sNumEntries, itr - tree.begin()); + EXPECT_EQUAL(-sNumEntries, tree.begin() - itr); + EXPECT_EQUAL(1, itr - pitr); + EXPECT_EQUAL(-1, pitr - itr); + } + // compact full tree by calling incremental compaction methods in a loop + { + MyTree::NodeAllocatorType &manager = tree.getAllocator(); + std::vector<uint32_t> toHold = manager.startCompact(); + MyTree::Iterator itr = tree.begin(); + tree.setRoot(itr.moveFirstLeafNode(tree.getRoot())); + while (itr.valid()) { + // LOG(info, "Leaf moved to %d", UNWRAP(itr.getKey())); + itr.moveNextLeafNode(); + } + manager.finishCompact(toHold); + manager.freeze(); + manager.transferHoldLists(g.getCurrentGeneration()); + g.incGeneration(); + manager.trimHoldLists(g.getFirstUsedGeneration()); + } + // remove entries + for (size_t i = 0; i < numEntries; ++i) { + int num = UNWRAP(exp[i].first); + //LOG(info, "remove[%zu](%d)", i, num); + //std::cout << "tree: " << tree.toString() << std::endl; + EXPECT_TRUE(tree.remove(num)); + EXPECT_TRUE(!tree.find(num).valid()); + EXPECT_TRUE(!tree.remove(num)); + EXPECT_TRUE(tree.isValid()); + mock.erase(num); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree))); + for (size_t j = i + 1; j < numEntries; ++j) { + MyTree::Iterator itr = tree.find(exp[j].first); + EXPECT_TRUE(itr.valid()); + EXPECT_EQUAL(exp[j].first, itr.getKey()); + EXPECT_EQUAL(exp[j].second, itr.getData()); + } + EXPECT_EQUAL(numEntries - 1 - i, tree.size()); + } +} + +void +Test::requireThatSortedTreeInsertWorks() +{ + { + MyTree tree; + MockTree mock; + TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree))); + for (int i = 0; i < 1000; ++i) { + EXPECT_TRUE(tree.insert(i, toVal(i))); + mock.insert(i, toVal(i)); + MyTree::Iterator itr = tree.find(i); + EXPECT_TRUE(itr.valid()); + EXPECT_EQUAL(toVal(i), itr.getData()); + EXPECT_TRUE(tree.isValid()); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree))); + } + } + { + MyTree tree; + MockTree mock; + TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree))); + for (int i = 1000; i > 0; --i) { + EXPECT_TRUE(tree.insert(i, toVal(i))); + mock.insert(i, toVal(i)); + MyTree::Iterator itr = tree.find(i); + EXPECT_TRUE(itr.valid()); + EXPECT_EQUAL(toVal(i), itr.getData()); + EXPECT_TRUE(tree.isValid()); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, tree))); + } + } +} + +void +Test::requireThatCornerCaseTreeFindWorks() +{ + GenerationHandler g; + MyTree tree; + for (int i = 1; i < 100; ++i) { + tree.insert(i, toVal(i)); + } + EXPECT_TRUE(!tree.find(0).valid()); // lower than lowest + EXPECT_TRUE(!tree.find(1000).valid()); // higher than highest +} + +void +Test::requireThatBasicTreeIteratorWorks() +{ + GenerationHandler g; + MyTree tree; + EXPECT_TRUE(!tree.begin().valid()); + std::vector<LeafPair> exp; + size_t numEntries = 1000; + generateData(exp, numEntries); + for (size_t i = 0; i < numEntries; ++i) { + tree.insert(exp[i].first, exp[i].second); + } + std::sort(exp.begin(), exp.end(), LeafPairLess()); + size_t ei = 0; + MyTree::Iterator itr = tree.begin(); + MyTree::Iterator ritr; + EXPECT_EQUAL(1000u, itr.size()); + for (; itr.valid(); ++itr) { + //LOG(info, "itr(%d, %s)", itr.getKey(), itr.getData().c_str()); + EXPECT_EQUAL(UNWRAP(exp[ei].first), UNWRAP(itr.getKey())); + EXPECT_EQUAL(exp[ei].second, itr.getData()); + ei++; + ritr = itr; + } + EXPECT_EQUAL(numEntries, ei); + for (; ritr.valid(); --ritr) { + --ei; + //LOG(info, "itr(%d, %s)", itr.getKey(), itr.getData().c_str()); + EXPECT_EQUAL(UNWRAP(exp[ei].first), UNWRAP(ritr.getKey())); + EXPECT_EQUAL(exp[ei].second, ritr.getData()); + } +} + + + +void +Test::requireThatTreeIteratorAssignWorks() +{ + GenerationHandler g; + MyTree tree; + for (int i = 0; i < 1000; ++i) { + tree.insert(i, toVal(i)); + } + for (int i = 0; i < 1000; ++i) { + MyTree::Iterator itr = tree.find(i); + MyTree::Iterator itr2 = itr; + EXPECT_TRUE(itr == itr2); + int expNum = i; + for (; itr2.valid(); ++itr2) { + EXPECT_EQUAL(expNum++, UNWRAP(itr2.getKey())); + } + EXPECT_EQUAL(1000, expNum); + } +} + +struct UpdKeyComp { + int _remainder; + mutable size_t _numErrors; + UpdKeyComp(int remainder) : _remainder(remainder), _numErrors(0) {} + bool operator() (const int & lhs, const int & rhs) const { + if (lhs % 2 != _remainder) ++_numErrors; + if (rhs % 2 != _remainder) ++_numErrors; + return lhs < rhs; + } +}; + +void +Test::requireThatUpdateOfKeyWorks() +{ + typedef BTree<int, BTreeNoLeafData, + btree::NoAggregated, + UpdKeyComp &> UpdKeyTree; + typedef UpdKeyTree::Iterator UpdKeyTreeIterator; + GenerationHandler g; + UpdKeyTree t; + UpdKeyComp cmp1(0); + for (int i = 0; i < 1000; i+=2) { + EXPECT_TRUE(t.insert(i, BTreeNoLeafData(), cmp1)); + } + EXPECT_EQUAL(0u, cmp1._numErrors); + for (int i = 0; i < 1000; i+=2) { + UpdKeyTreeIterator itr = t.find(i, cmp1); + itr.writeKey(i + 1); + } + UpdKeyComp cmp2(1); + for (int i = 1; i < 1000; i+=2) { + UpdKeyTreeIterator itr = t.find(i, cmp2); + EXPECT_TRUE(itr.valid()); + } + EXPECT_EQUAL(0u, cmp2._numErrors); +} + + +void +Test::requireThatUpdateOfDataWorks() +{ + // typedef MyTree::Iterator Iterator; + GenerationHandler g; + MyTree t; + MockTree mock; + MyAggrCalc ac; + MyTree::NodeAllocatorType &manager = t.getAllocator(); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, t))); + for (int i = 0; i < 1000; i+=2) { + EXPECT_TRUE(t.insert(i, toVal(i))); + mock.insert(i, toVal(i)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, t))); + } + freezeTree(g, manager); + for (int i = 0; i < 1000; i+=2) { + MyTree::Iterator itr = t.find(i); + MyTree::Iterator itr2 = itr; + t.thaw(itr); + itr.updateData(toHighVal(i), ac); + EXPECT_EQUAL(toHighVal(i), itr.getData()); + EXPECT_EQUAL(toVal(i), itr2.getData()); + mock.erase(i); + mock.insert(i, toHighVal(i)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, t))); + freezeTree(g, manager); + itr = t.find(i); + itr2 = itr; + t.thaw(itr); + itr.updateData(toLowVal(i), ac); + EXPECT_EQUAL(toLowVal(i), itr.getData()); + EXPECT_EQUAL(toHighVal(i), itr2.getData()); + mock.erase(i); + mock.insert(i, toLowVal(i)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, t))); + freezeTree(g, manager); + itr = t.find(i); + itr2 = itr; + t.thaw(itr); + itr.updateData(toVal(i), ac); + EXPECT_EQUAL(toVal(i), itr.getData()); + EXPECT_EQUAL(toLowVal(i), itr2.getData()); + mock.erase(i); + mock.insert(i, toVal(i)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, t))); + freezeTree(g, manager); + } +} + + +template <typename TreeStore> +void +Test::requireThatSmallNodesWorks() +{ + GenerationHandler g; + TreeStore s; + MockTree mock; + + EntryRef root; + EXPECT_EQUAL(0u, s.size(root)); + EXPECT_TRUE(s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + EXPECT_TRUE(s.insert(root, 40, toVal(40))); + mock.insert(40, toVal(40)); + EXPECT_TRUE(!s.insert(root, 40, toNotVal(40))); + EXPECT_EQUAL(1u, s.size(root)); + EXPECT_TRUE(s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + EXPECT_TRUE(s.insert(root, 20, toVal(20))); + mock.insert(20, toVal(20)); + EXPECT_TRUE(!s.insert(root, 20, toNotVal(20))); + EXPECT_TRUE(!s.insert(root, 40, toNotVal(40))); + EXPECT_EQUAL(2u, s.size(root)); + EXPECT_TRUE(s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + EXPECT_TRUE(s.insert(root, 60, toVal(60))); + mock.insert(60, toVal(60)); + EXPECT_TRUE(!s.insert(root, 60, toNotVal(60))); + EXPECT_TRUE(!s.insert(root, 20, toNotVal(20))); + EXPECT_TRUE(!s.insert(root, 40, toNotVal(40))); + EXPECT_EQUAL(3u, s.size(root)); + EXPECT_TRUE(s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + EXPECT_TRUE(s.insert(root, 50, toVal(50))); + mock.insert(50, toVal(50)); + EXPECT_TRUE(!s.insert(root, 50, toNotVal(50))); + EXPECT_TRUE(!s.insert(root, 60, toNotVal(60))); + EXPECT_TRUE(!s.insert(root, 20, toNotVal(20))); + EXPECT_TRUE(!s.insert(root, 40, toNotVal(40))); + EXPECT_EQUAL(4u, s.size(root)); + EXPECT_TRUE(s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + + for (uint32_t i = 0; i < 100; ++i) { + EXPECT_TRUE(s.insert(root, 1000 + i, 42)); + mock.insert(1000 + i, 42); + if (i > 0) { + EXPECT_TRUE(!s.insert(root, 1000 + i - 1, 42)); + } + EXPECT_EQUAL(5u + i, s.size(root)); + EXPECT_EQUAL(5u + i <= 8u, s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + } + EXPECT_TRUE(s.remove(root, 40)); + mock.erase(40); + EXPECT_TRUE(!s.remove(root, 40)); + EXPECT_EQUAL(103u, s.size(root)); + EXPECT_TRUE(!s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + EXPECT_TRUE(s.remove(root, 20)); + mock.erase(20); + EXPECT_TRUE(!s.remove(root, 20)); + EXPECT_EQUAL(102u, s.size(root)); + EXPECT_TRUE(!s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + EXPECT_TRUE(s.remove(root, 50)); + mock.erase(50); + EXPECT_TRUE(!s.remove(root, 50)); + EXPECT_EQUAL(101u, s.size(root)); + EXPECT_TRUE(!s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + for (uint32_t i = 0; i < 100; ++i) { + EXPECT_TRUE(s.remove(root, 1000 + i)); + mock.erase(1000 + i); + if (i > 0) { + EXPECT_TRUE(!s.remove(root, 1000 + i - 1)); + } + EXPECT_EQUAL(100 - i, s.size(root)); + EXPECT_EQUAL(100 - i <= 8u, s.isSmallArray(root)); + TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); + } + EXPECT_EQUAL(1u, s.size(root)); + EXPECT_TRUE(s.isSmallArray(root)); + + s.clear(root); + s.clearBuilder(); + s.freeze(); + s.transferHoldLists(g.getCurrentGeneration()); + g.incGeneration(); + s.trimHoldLists(g.getFirstUsedGeneration()); +} + + +int +Test::Main() +{ + TEST_INIT("btreeaggregation_test"); + + requireThatNodeInsertWorks(); + requireThatNodeSplitInsertWorks(); + requireThatTreeInsertWorks(); + requireThatNodeStealWorks(); + requireThatNodeRemoveWorks(); + requireThatWeCanInsertAndRemoveFromTree(); + requireThatSortedTreeInsertWorks(); + requireThatCornerCaseTreeFindWorks(); + requireThatBasicTreeIteratorWorks(); + requireThatTreeIteratorAssignWorks(); + requireThatUpdateOfKeyWorks(); + requireThatUpdateOfDataWorks(); + TEST_DO(requireThatSmallNodesWorks<MyTreeStore>()); + TEST_DO(requireThatSmallNodesWorks<MyTreeForceApplyStore>()); + + TEST_DONE(); +} + +} +} + +TEST_APPHOOK(search::btree::Test); |