Move btree unit tests to proper location.

6 files changed, 0 insertions, 1770 deletions

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 <vespa/log/log.h>
-LOG_SETUP("btree_test");
-#include <vespa/vespalib/testkit/testapp.h>
-#include <string>
-#include <vespa/searchlib/btree/btreeroot.h>
-#include <vespa/searchlib/btree/btreebuilder.h>
-#include <vespa/searchlib/btree/btreenodeallocator.h>
-#include <vespa/searchlib/btree/btree.h>
-#include <vespa/searchlib/btree/btreestore.h>
-#include <vespa/searchlib/util/rand48.h>
-
-#include <vespa/searchlib/btree/btreenodeallocator.hpp>
-#include <vespa/searchlib/btree/btreenode.hpp>
-#include <vespa/searchlib/btree/btreenodestore.hpp>
-#include <vespa/searchlib/btree/btreeiterator.hpp>
-#include <vespa/searchlib/btree/btreeroot.hpp>
-#include <vespa/searchlib/btree/btreebuilder.hpp>
-#include <vespa/searchlib/btree/btree.hpp>
-#include <vespa/searchlib/btree/btreestore.hpp>
-
-using vespalib::GenerationHandler;
-using search::datastore::EntryRef;
-
-namespace search {
-namespace btree {
-
-namespace {
-
-template <typename T>
-std::string
-toStr(const T & v)
-{
-    std::stringstream ss;
-    ss << v;
-    return ss.str();
-}
-
-}
-
-typedef BTreeTraits<4, 4, 31, false> MyTraits;
-
-#define KEYWRAP
-
-#ifdef KEYWRAP
-
-// Force use of functor to compare keys.
-class WrapInt
-{
-public:
-    int _val;
-    WrapInt(int val) : _val(val) {}
-    WrapInt() : _val(0) {}
-    bool operator==(const WrapInt & rhs) const { return _val == rhs._val; }
-};
-
-std::ostream &
-operator<<(std::ostream &s, const WrapInt &i)
-{
-    s << i._val;
-    return s;
-}
-
-typedef WrapInt MyKey;
-class MyComp
-{
-public:
-    bool
-    operator()(const WrapInt &a, const WrapInt &b) const
-    {
-        return a._val < b._val;
-    }
-};
-
-#define UNWRAP(key) (key._val)
-#else
-typedef int MyKey;
-typedef std::less<int> MyComp;
-#define UNWRAP(key) (key)
-#endif
-
-typedef BTree<MyKey, std::string,
-              btree::NoAggregated,
-              MyComp, MyTraits> MyTree;
-typedef BTreeStore<MyKey, std::string,
-                   btree::NoAggregated,
-                   MyComp, MyTraits> MyTreeStore;
-typedef MyTree::Builder               MyTreeBuilder;
-typedef MyTree::LeafNodeType          MyLeafNode;
-typedef MyTree::InternalNodeType      MyInternalNode;
-typedef MyTree::NodeAllocatorType     MyNodeAllocator;
-typedef std::pair<MyKey, std::string> LeafPair;
-typedef MyTreeStore::KeyDataType	MyKeyData;
-typedef MyTreeStore::KeyDataTypeRefPair	MyKeyDataRefPair;
-
-typedef BTree<int, BTreeNoLeafData, btree::NoAggregated> SetTreeB;
-
-typedef BTreeTraits<16, 16, 10, false> LSeekTraits;
-typedef BTree<int, BTreeNoLeafData, btree::NoAggregated,
-              std::less<int>, LSeekTraits> SetTreeL;
-
-struct LeafPairLess {
-    bool operator()(const LeafPair & lhs, const LeafPair & rhs) const {
-        return UNWRAP(lhs.first) < UNWRAP(rhs.first);
-    }
-};
-
-template <typename ManagerType>
-void
-cleanup(GenerationHandler & g, ManagerType & m)
-{
-    m.freeze();
-    m.transferHoldLists(g.getCurrentGeneration());
-    g.incGeneration();
-    m.trimHoldLists(g.getFirstUsedGeneration());
-}
-
-template <typename ManagerType, typename NodeType>
-void
-cleanup(GenerationHandler & g,
-        ManagerType & m,
-        BTreeNode::Ref n1Ref, NodeType * n1,
-        BTreeNode::Ref n2Ref = BTreeNode::Ref(), NodeType * n2 = NULL)
-{
-    assert(ManagerType::isValidRef(n1Ref));
-    m.holdNode(n1Ref, n1);
-    if (n2 != NULL) {
-        assert(ManagerType::isValidRef(n2Ref));
-        m.holdNode(n2Ref, n2);
-    } else {
-        assert(!ManagerType::isValidRef(n2Ref));
-    }
-    cleanup(g, m);
-}
-
-class Test : public vespalib::TestApp {
-private:
-    template <typename LeafNodeType>
-    bool assertLeafNode(const std::string & exp, const LeafNodeType & n);
-    bool assertSeek(int skey, int ekey, const MyTree & tree);
-    bool assertSeek(int skey, int ekey, MyTree::Iterator & itr);
-    bool assertMemoryUsage(const MemoryUsage & exp, const MemoryUsage & act);
-
-    void
-    buildSubTree(const std::vector<LeafPair> &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 <typename TreeType>
-    void requireThatLowerBoundWorksT();
-    void requireThatLowerBoundWorks();
-    template <typename TreeType>
-    void requireThatUpperBoundWorksT();
-    void requireThatUpperBoundWorks();
-    void requireThatUpdateOfKeyWorks();
-
-    void
-    requireThatSmallNodesWorks();
-
-    void
-    requireThatApplyWorks();
-
-    void
-    requireThatIteratorDistanceWorks(int numEntries);
-
-    void
-    requireThatIteratorDistanceWorks();
-public:
-    int Main() override;
-};
-
-template <typename LeafNodeType>
-bool
-Test::assertLeafNode(const std::string & exp, const LeafNodeType & n)
-{
-    std::stringstream ss;
-    ss << "[";
-    for (uint32_t i = 0; i < n.validSlots(); ++i) {
-        if (i > 0) ss << ",";
-        ss << n.getKey(i) << ":" << n.getData(i);
-    }
-    ss << "]";
-    if (!EXPECT_EQUAL(exp, ss.str())) return false;
-    return true;
-}
-
-bool
-Test::assertSeek(int skey, int ekey, const MyTree & tree)
-{
-    MyTree::Iterator itr = tree.begin();
-    return assertSeek(skey, ekey, itr);
-}
-
-bool
-Test::assertSeek(int skey, int ekey, MyTree::Iterator & itr)
-{
-    MyTree::Iterator bseekItr = itr;
-    MyTree::Iterator lseekItr = itr;
-    bseekItr.binarySeek(skey);
-    lseekItr.linearSeek(skey);
-    if (!EXPECT_EQUAL(ekey, UNWRAP(bseekItr.getKey()))) return false;
-    if (!EXPECT_EQUAL(ekey, UNWRAP(lseekItr.getKey()))) return false;
-    itr = bseekItr;
-    return true;
-}
-
-bool
-Test::assertMemoryUsage(const 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<int, std::string,
-        btree::NoAggregated, 6> MyStealNode;
-    typedef BTreeNodeAllocator<int, std::string,
-        btree::NoAggregated,
-        BTreeStealTraits::INTERNAL_SLOTS, BTreeStealTraits::LEAF_SLOTS>
-        MyStealManager;
-    { // steal all from left
-        GenerationHandler g;
-        MyStealManager m;
-        MyStealNode::RefPair nPair = m.allocLeafNode();
-        MyStealNode *n = nPair.data;
-        n->insert(0, 4, "d");
-        n->insert(1, 5, "e");
-        EXPECT_TRUE(!n->isAtLeastHalfFull());
-        MyStealNode::RefPair vPair = m.allocLeafNode();
-        MyStealNode *v = vPair.data;
-        v->insert(0, 1, "a");
-        v->insert(1, 2, "b");
-        v->insert(2, 3, "c");
-        n->stealAllFromLeftNode(v);
-        EXPECT_TRUE(n->isAtLeastHalfFull());
-        EXPECT_TRUE(assertLeafNode("[1:a,2:b,3:c,4:d,5:e]", *n));
-        cleanup(g, m, nPair.ref, n, vPair.ref, v);
-    }
-    { // steal all from right
-        GenerationHandler g;
-        MyStealManager m;
-        MyStealNode::RefPair nPair = m.allocLeafNode();
-        MyStealNode *n = nPair.data;
-        n->insert(0, 1, "a");
-        n->insert(1, 2, "b");
-        EXPECT_TRUE(!n->isAtLeastHalfFull());
-        MyStealNode::RefPair vPair = m.allocLeafNode();
-        MyStealNode *v = vPair.data;
-        v->insert(0, 3, "c");
-        v->insert(1, 4, "d");
-        v->insert(2, 5, "e");
-        n->stealAllFromRightNode(v);
-        EXPECT_TRUE(n->isAtLeastHalfFull());
-        EXPECT_TRUE(assertLeafNode("[1:a,2:b,3:c,4:d,5:e]", *n));
-        cleanup(g, m, nPair.ref, n, vPair.ref, v);
-    }
-    { // steal some from left
-        GenerationHandler g;
-        MyStealManager m;
-        MyStealNode::RefPair nPair = m.allocLeafNode();
-        MyStealNode *n = nPair.data;
-        n->insert(0, 5, "e");
-        n->insert(1, 6, "f");
-        EXPECT_TRUE(!n->isAtLeastHalfFull());
-        MyStealNode::RefPair vPair = m.allocLeafNode();
-        MyStealNode *v = vPair.data;
-        v->insert(0, 1, "a");
-        v->insert(1, 2, "b");
-        v->insert(2, 3, "c");
-        v->insert(3, 4, "d");
-        n->stealSomeFromLeftNode(v);
-        EXPECT_TRUE(n->isAtLeastHalfFull());
-        EXPECT_TRUE(v->isAtLeastHalfFull());
-        EXPECT_TRUE(assertLeafNode("[4:d,5:e,6:f]", *n));
-        EXPECT_TRUE(assertLeafNode("[1:a,2:b,3:c]", *v));
-        cleanup(g, m, nPair.ref, n, vPair.ref, v);
-    }
-    { // steal some from right
-        GenerationHandler g;
-        MyStealManager m;
-        MyStealNode::RefPair nPair = m.allocLeafNode();
-        MyStealNode *n = nPair.data;
-        n->insert(0, 1, "a");
-        n->insert(1, 2, "b");
-        EXPECT_TRUE(!n->isAtLeastHalfFull());
-        MyStealNode::RefPair vPair = m.allocLeafNode();
-        MyStealNode *v = vPair.data;
-        v->insert(0, 3, "c");
-        v->insert(1, 4, "d");
-        v->insert(2, 5, "e");
-        v->insert(3, 6, "f");
-        n->stealSomeFromRightNode(v);
-        EXPECT_TRUE(n->isAtLeastHalfFull());
-        EXPECT_TRUE(v->isAtLeastHalfFull());
-        EXPECT_TRUE(assertLeafNode("[1:a,2:b,3:c]", *n));
-        EXPECT_TRUE(assertLeafNode("[4:d,5:e,6:f]", *v));
-        cleanup(g, m, nPair.ref, n, vPair.ref, v);
-    }
-}
-
-void
-Test::requireThatNodeRemoveWorks()
-{
-    GenerationHandler g;
-    MyNodeAllocator m;
-    MyLeafNode::RefPair nPair = getLeafNode(m);
-    MyLeafNode *n = nPair.data;
-    n->remove(1);
-    EXPECT_TRUE(assertLeafNode("[1:a,5:e,7:g]", *n));
-    cleanup(g, m, nPair.ref, n);
-}
-
-void
-Test::requireThatNodeLowerBoundWorks()
-{
-    GenerationHandler g;
-    MyNodeAllocator m;
-    MyLeafNode::RefPair nPair = getLeafNode(m);
-    MyLeafNode *n = nPair.data;
-    EXPECT_EQUAL(1u, n->lower_bound(3, MyComp()));
-    EXPECT_FALSE(MyComp()(3, n->getKey(1u)));
-    EXPECT_EQUAL(0u, n->lower_bound(0, MyComp()));
-    EXPECT_TRUE(MyComp()(0, n->getKey(0u)));
-    EXPECT_EQUAL(1u, n->lower_bound(2, MyComp()));
-    EXPECT_TRUE(MyComp()(2, n->getKey(1u)));
-    EXPECT_EQUAL(3u, n->lower_bound(6, MyComp()));
-    EXPECT_TRUE(MyComp()(6, n->getKey(3u)));
-    EXPECT_EQUAL(4u, n->lower_bound(8, MyComp()));
-    cleanup(g, m, nPair.ref, n);
-}
-
-void
-generateData(std::vector<LeafPair> & data, size_t numEntries)
-{
-    data.reserve(numEntries);
-    Rand48 rnd;
-    rnd.srand48(10);
-    for (size_t i = 0; i < numEntries; ++i) {
-        int num = rnd.lrand48() % 10000000;
-        std::string str = toStr(num);
-        data.push_back(std::make_pair(num, str));
-    }
-}
-
-
-void
-Test::buildSubTree(const std::vector<LeafPair> &sub,
-                   size_t numEntries)
-{
-    GenerationHandler g;
-    MyTree tree;
-    MyTreeBuilder builder(tree.getAllocator());
-
-    std::vector<LeafPair> sorted(sub.begin(), sub.begin() + numEntries);
-    std::sort(sorted.begin(), sorted.end(), LeafPairLess());
-    for (size_t i = 0; i < numEntries; ++i) {
-        int num = UNWRAP(sorted[i].first);
-        const std::string & str = sorted[i].second;
-        builder.insert(num, str);
-    }
-    tree.assign(builder);
-    assert(numEntries == tree.size());
-    assert(tree.isValid());
-    EXPECT_EQUAL(numEntries, tree.size());
-    EXPECT_TRUE(tree.isValid());
-    MyTree::Iterator itr = tree.begin();
-    MyTree::Iterator ritr = itr;
-    if (numEntries > 0) {
-        EXPECT_TRUE(ritr.valid());
-        EXPECT_EQUAL(0u, ritr.position());
-        --ritr;
-        EXPECT_TRUE(!ritr.valid());
-        EXPECT_EQUAL(numEntries, ritr.position());
-        --ritr;
-        EXPECT_TRUE(ritr.valid());
-        EXPECT_EQUAL(numEntries - 1, ritr.position());
-    } else {
-        EXPECT_TRUE(!ritr.valid());
-        EXPECT_EQUAL(0u, ritr.position());
-        --ritr;
-        EXPECT_TRUE(!ritr.valid());
-        EXPECT_EQUAL(0u, ritr.position());
-    }
-    for (size_t i = 0; i < numEntries; ++i) {
-        EXPECT_TRUE(itr.valid());
-        EXPECT_EQUAL(sorted[i].first, itr.getKey());
-        EXPECT_EQUAL(sorted[i].second, itr.getData());
-        ++itr;
-    }
-    EXPECT_TRUE(!itr.valid());
-    ritr = itr;
-    EXPECT_TRUE(!ritr.valid());
-    --ritr;
-    for (size_t i = 0; i < numEntries; ++i) {
-        EXPECT_TRUE(ritr.valid());
-        EXPECT_EQUAL(sorted[numEntries - 1 - i].first, ritr.getKey());
-        EXPECT_EQUAL(sorted[numEntries - 1 - i].second, ritr.getData());
-        --ritr;
-    }
-    EXPECT_TRUE(!ritr.valid());
-}
-
-void
-Test::requireThatWeCanInsertAndRemoveFromTree()
-{
-    GenerationHandler g;
-    MyTree tree;
-    std::vector<LeafPair> exp;
-    std::vector<LeafPair> sorted;
-    size_t numEntries = 1000;
-    generateData(exp, numEntries);
-    sorted = exp;
-    std::sort(sorted.begin(), sorted.end(), LeafPairLess());
-    // insert entries
-    for (size_t i = 0; i < numEntries; ++i) {
-        int num = UNWRAP(exp[i].first);
-        const std::string & str = exp[i].second;
-        EXPECT_TRUE(!tree.find(num).valid());
-        //LOG(info, "insert[%zu](%d, %s)", i, num, str.c_str());
-        EXPECT_TRUE(tree.insert(num, str));
-        EXPECT_TRUE(!tree.insert(num, str));
-        for (size_t j = 0; j <= i; ++j) {
-            //LOG(info, "find[%zu](%d)", j, exp[j].first._val);
-            MyTree::Iterator itr = tree.find(exp[j].first);
-            EXPECT_TRUE(itr.valid());
-            EXPECT_EQUAL(exp[j].first, itr.getKey());
-            EXPECT_EQUAL(exp[j].second, itr.getData());
-        }
-        EXPECT_EQUAL(i + 1u, tree.size());
-        EXPECT_TRUE(tree.isValid());
-        buildSubTree(exp, i + 1);
-    }
-    //std::cout << "tree: " << tree.toString() << std::endl;
-
-    {
-        MyTree::Iterator itr = tree.begin();
-        MyTree::Iterator itre = itr;
-        MyTree::Iterator itre2;
-        MyTree::Iterator ritr = itr;
-        while (itre.valid())
-            ++itre;
-        if (numEntries > 0) {
-            EXPECT_TRUE(ritr.valid());
-            EXPECT_EQUAL(0u, ritr.position());
-            --ritr;
-            EXPECT_TRUE(!ritr.valid());
-            EXPECT_EQUAL(numEntries, ritr.position());
-            --ritr;
-            EXPECT_TRUE(ritr.valid());
-            EXPECT_EQUAL(numEntries - 1, ritr.position());
-        } else {
-            EXPECT_TRUE(!ritr.valid());
-            EXPECT_EQUAL(0u, ritr.position());
-            --ritr;
-            EXPECT_TRUE(!ritr.valid());
-            EXPECT_EQUAL(0u, ritr.position());
-        }
-        MyTree::Iterator pitr = itr;
-        for (size_t i = 0; i < numEntries; ++i) {
-            ssize_t si = i;
-            ssize_t sileft = numEntries - i;
-            EXPECT_TRUE(itr.valid());
-            EXPECT_EQUAL(i, itr.position());
-            EXPECT_EQUAL(sileft, itre - itr);
-            EXPECT_EQUAL(-sileft, itr - itre);
-            EXPECT_EQUAL(sileft, itre2 - itr);
-            EXPECT_EQUAL(-sileft, itr - itre2);
-            EXPECT_EQUAL(si, itr - tree.begin());
-            EXPECT_EQUAL(-si, tree.begin() - itr);
-            EXPECT_EQUAL(i != 0, itr - pitr);
-            EXPECT_EQUAL(-(i != 0), pitr - itr);
-            EXPECT_EQUAL(sorted[i].first, itr.getKey());
-            EXPECT_EQUAL(sorted[i].second, itr.getData());
-            pitr = itr;
-            ++itr;
-            ritr = itr;
-            --ritr;
-            EXPECT_TRUE(ritr.valid());
-            EXPECT_TRUE(ritr == pitr);
-        }
-        EXPECT_TRUE(!itr.valid());
-        EXPECT_EQUAL(numEntries, itr.position());
-        ssize_t sNumEntries = numEntries;
-        EXPECT_EQUAL(sNumEntries, itr - tree.begin());
-        EXPECT_EQUAL(-sNumEntries, tree.begin() - itr);
-        EXPECT_EQUAL(1, itr - pitr);
-        EXPECT_EQUAL(-1, pitr - itr);
-    }
-    // compact full tree by calling incremental compaction methods in a loop
-    {
-        MyTree::NodeAllocatorType &manager = tree.getAllocator();
-        std::vector<uint32_t> toHold = manager.startCompact();
-        MyTree::Iterator itr = tree.begin();
-        tree.setRoot(itr.moveFirstLeafNode(tree.getRoot()));
-        while (itr.valid()) {
-            // LOG(info, "Leaf moved to %d", UNWRAP(itr.getKey()));
-            itr.moveNextLeafNode();
-        }
-        manager.finishCompact(toHold);
-        manager.freeze();
-        manager.transferHoldLists(g.getCurrentGeneration());
-        g.incGeneration();
-        manager.trimHoldLists(g.getFirstUsedGeneration());
-    }
-    // remove entries
-    for (size_t i = 0; i < numEntries; ++i) {
-        int num = UNWRAP(exp[i].first);
-        //LOG(info, "remove[%zu](%d)", i, num);
-        //std::cout << "tree: " << tree.toString() << std::endl;
-        EXPECT_TRUE(tree.remove(num));
-        EXPECT_TRUE(!tree.find(num).valid());
-        EXPECT_TRUE(!tree.remove(num));
-        EXPECT_TRUE(tree.isValid());
-        for (size_t j = i + 1; j < numEntries; ++j) {
-            MyTree::Iterator itr = tree.find(exp[j].first);
-            EXPECT_TRUE(itr.valid());
-            EXPECT_EQUAL(exp[j].first, itr.getKey());
-            EXPECT_EQUAL(exp[j].second, itr.getData());
-        }
-        EXPECT_EQUAL(numEntries - 1 - i, tree.size());
-    }
-}
-
-void
-Test::requireThatSortedTreeInsertWorks()
-{
-    {
-        GenerationHandler g;
-        MyTree tree;
-        for (int i = 0; i < 1000; ++i) {
-            EXPECT_TRUE(tree.insert(i, toStr(i)));
-            MyTree::Iterator itr = tree.find(i);
-            EXPECT_TRUE(itr.valid());
-            EXPECT_EQUAL(toStr(i), itr.getData());
-            EXPECT_TRUE(tree.isValid());
-        }
-    }
-    {
-        GenerationHandler g;
-        MyTree tree;
-        for (int i = 1000; i > 0; --i) {
-            EXPECT_TRUE(tree.insert(i, toStr(i)));
-            MyTree::Iterator itr = tree.find(i);
-            EXPECT_TRUE(itr.valid());
-            EXPECT_EQUAL(toStr(i), itr.getData());
-            EXPECT_TRUE(tree.isValid());
-        }
-    }
-}
-
-void
-Test::requireThatCornerCaseTreeFindWorks()
-{
-    GenerationHandler g;
-    MyTree tree;
-    for (int i = 1; i < 100; ++i) {
-        tree.insert(i, toStr(i));
-    }
-    EXPECT_TRUE(!tree.find(0).valid()); // lower than lowest
-    EXPECT_TRUE(!tree.find(1000).valid()); // higher than highest
-}
-
-void
-Test::requireThatBasicTreeIteratorWorks()
-{
-    GenerationHandler g;
-    MyTree tree;
-    EXPECT_TRUE(!tree.begin().valid());
-    std::vector<LeafPair> exp;
-    size_t numEntries = 1000;
-    generateData(exp, numEntries);
-    for (size_t i = 0; i < numEntries; ++i) {
-        tree.insert(exp[i].first, exp[i].second);
-    }
-    std::sort(exp.begin(), exp.end(), LeafPairLess());
-    size_t ei = 0;
-    MyTree::Iterator itr = tree.begin();
-    MyTree::Iterator ritr;
-    EXPECT_EQUAL(1000u, itr.size());
-    for (; itr.valid(); ++itr) {
-        //LOG(info, "itr(%d, %s)", itr.getKey(), itr.getData().c_str());
-        EXPECT_EQUAL(UNWRAP(exp[ei].first), UNWRAP(itr.getKey()));
-        EXPECT_EQUAL(exp[ei].second, itr.getData());
-        ei++;
-        ritr = itr;
-    }
-    EXPECT_EQUAL(numEntries, ei);
-    for (; ritr.valid(); --ritr) {
-        --ei;
-        //LOG(info, "itr(%d, %s)", itr.getKey(), itr.getData().c_str());
-        EXPECT_EQUAL(UNWRAP(exp[ei].first), UNWRAP(ritr.getKey()));
-        EXPECT_EQUAL(exp[ei].second, ritr.getData());
-    }
-}
-
-void
-Test::requireThatTreeIteratorSeekWorks()
-{
-    GenerationHandler g;
-    MyTree tree;
-    for (int i = 0; i < 40; i += 2) {
-        tree.insert(i, toStr(i));
-    }
-    //std::cout << tree.toString() << std::endl;
-    EXPECT_TRUE(assertSeek(2, 2, tree)); // next key
-    EXPECT_TRUE(assertSeek(10, 10, tree)); // skip to existing
-    EXPECT_TRUE(assertSeek(26, 26, tree)); // skip to existing
-    EXPECT_TRUE(assertSeek(11, 12, tree)); // skip to non-existing
-    EXPECT_TRUE(assertSeek(23, 24, tree)); // skip to non-existing
-    {
-        MyTree::Iterator itr = tree.begin();
-        EXPECT_TRUE(assertSeek(4, 4, itr));
-        EXPECT_TRUE(assertSeek(14, 14, itr));
-        EXPECT_TRUE(assertSeek(18, 18, itr));
-        EXPECT_TRUE(assertSeek(36, 36, itr));
-    }
-    {
-        MyTree::Iterator itr = tree.begin();
-        EXPECT_TRUE(assertSeek(3, 4, itr));
-        EXPECT_TRUE(assertSeek(13, 14, itr));
-        EXPECT_TRUE(assertSeek(17, 18, itr));
-        EXPECT_TRUE(assertSeek(35, 36, itr));
-    }
-    {
-        MyTree::Iterator itr = tree.begin();
-        MyTree::Iterator itr2 = tree.begin();
-        itr.binarySeek(40); // outside
-        itr2.linearSeek(40); // outside
-        EXPECT_TRUE(!itr.valid());
-        EXPECT_TRUE(!itr2.valid());
-    }
-    {
-        MyTree::Iterator itr = tree.begin();
-        EXPECT_TRUE(assertSeek(8, 8, itr));
-        for (int i = 10; i < 40; i += 2) {
-            ++itr;
-            EXPECT_EQUAL(i, UNWRAP(itr.getKey()));
-        }
-    }
-    {
-        MyTree::Iterator itr = tree.begin();
-        EXPECT_TRUE(assertSeek(26, 26, itr));
-        for (int i = 28; i < 40; i += 2) {
-            ++itr;
-            EXPECT_EQUAL(i, UNWRAP(itr.getKey()));
-        }
-    }
-    GenerationHandler g2;
-    MyTree tree2; // only leaf node
-    tree2.insert(0, "0");
-    tree2.insert(2, "2");
-    tree2.insert(4, "4");
-    EXPECT_TRUE(assertSeek(1, 2, tree2));
-    EXPECT_TRUE(assertSeek(2, 2, tree2));
-    {
-        MyTree::Iterator itr = tree2.begin();
-        MyTree::Iterator itr2 = tree2.begin();
-        itr.binarySeek(5); // outside
-        itr2.linearSeek(5); // outside
-        EXPECT_TRUE(!itr.valid());
-        EXPECT_TRUE(!itr2.valid());
-    }
-}
-
-void
-Test::requireThatTreeIteratorAssignWorks()
-{
-    GenerationHandler g;
-    MyTree tree;
-    for (int i = 0; i < 1000; ++i) {
-        tree.insert(i, toStr(i));
-    }
-    for (int i = 0; i < 1000; ++i) {
-        MyTree::Iterator itr = tree.find(i);
-        MyTree::Iterator itr2 = itr;
-        EXPECT_TRUE(itr == itr2);
-        int expNum = i;
-        for (; itr2.valid(); ++itr2) {
-            EXPECT_EQUAL(expNum++, UNWRAP(itr2.getKey()));
-        }
-        EXPECT_EQUAL(1000, expNum);
-    }
-}
-
-void
-Test::requireThatMemoryUsageIsCalculated()
-{
-    typedef BTreeNodeAllocator<int32_t, int8_t,
-        btree::NoAggregated,
-        MyTraits::INTERNAL_SLOTS, MyTraits::LEAF_SLOTS> NodeAllocator;
-    typedef NodeAllocator::InternalNodeType        INode;
-    typedef NodeAllocator::LeafNodeType            LNode;
-    typedef NodeAllocator::InternalNodeTypeRefPair IRef;
-    typedef NodeAllocator::LeafNodeTypeRefPair     LRef;
-    LOG(info, "sizeof(BTreeNode)=%zu, sizeof(INode)=%zu, sizeof(LNode)=%zu",
-        sizeof(BTreeNode), sizeof(INode), sizeof(LNode));
-    EXPECT_GREATER(sizeof(INode), sizeof(LNode));
-    GenerationHandler gh;
-    gh.incGeneration();
-    NodeAllocator tm;
-    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 <typename TreeType>
-void
-Test::requireThatLowerBoundWorksT()
-{
-    GenerationHandler g;
-    TreeType t;
-    EXPECT_TRUE(t.insert(10, BTreeNoLeafData()));
-    EXPECT_TRUE(t.insert(20, BTreeNoLeafData()));
-    EXPECT_TRUE(t.insert(30, BTreeNoLeafData()));
-    EXPECT_EQUAL(10, t.lowerBound(9).getKey());
-    EXPECT_EQUAL(20, t.lowerBound(20).getKey());
-    EXPECT_EQUAL(30, t.lowerBound(21).getKey());
-    EXPECT_EQUAL(30, t.lowerBound(30).getKey());
-    EXPECT_TRUE(!t.lowerBound(31).valid());
-    for (int i = 40; i < 1000; i+=10) {
-        EXPECT_TRUE(t.insert(i, BTreeNoLeafData()));
-    }
-    for (int i = 9; i < 990; i+=10) {
-        EXPECT_EQUAL(i + 1, t.lowerBound(i).getKey());
-        EXPECT_EQUAL(i + 1, t.lowerBound(i + 1).getKey());
-    }
-    EXPECT_TRUE(!t.lowerBound(991).valid());
-}
-
-void
-Test::requireThatLowerBoundWorks()
-{
-    requireThatLowerBoundWorksT<SetTreeB>();
-    requireThatLowerBoundWorksT<SetTreeL>();
-}
-
-template <typename TreeType>
-void
-Test::requireThatUpperBoundWorksT()
-{
-    GenerationHandler g;
-    TreeType t;
-    EXPECT_TRUE(t.insert(10, BTreeNoLeafData()));
-    EXPECT_TRUE(t.insert(20, BTreeNoLeafData()));
-    EXPECT_TRUE(t.insert(30, BTreeNoLeafData()));
-    EXPECT_EQUAL(10, t.upperBound(9).getKey());
-    EXPECT_EQUAL(30, t.upperBound(20).getKey());
-    EXPECT_EQUAL(30, t.upperBound(21).getKey());
-    EXPECT_TRUE(!t.upperBound(30).valid());
-    for (int i = 40; i < 1000; i+=10) {
-        EXPECT_TRUE(t.insert(i, BTreeNoLeafData()));
-    }
-    for (int i = 9; i < 980; i+=10) {
-        EXPECT_EQUAL(i + 1, t.upperBound(i).getKey());
-        EXPECT_EQUAL(i + 11, t.upperBound(i + 1).getKey());
-    }
-    EXPECT_TRUE(!t.upperBound(990).valid());
-}
-
-void
-Test::requireThatUpperBoundWorks()
-{
-    requireThatUpperBoundWorksT<SetTreeB>();
-    requireThatUpperBoundWorksT<SetTreeL>();
-}
-
-struct UpdKeyComp {
-    int _remainder;
-    mutable size_t _numErrors;
-    UpdKeyComp(int remainder) : _remainder(remainder), _numErrors(0) {}
-    bool operator() (const int & lhs, const int & rhs) const {
-        if (lhs % 2 != _remainder) ++_numErrors;
-        if (rhs % 2 != _remainder) ++_numErrors;
-        return lhs < rhs;
-    }
-};
-
-void
-Test::requireThatUpdateOfKeyWorks()
-{
-    typedef BTree<int, BTreeNoLeafData,
-        btree::NoAggregated,
-        UpdKeyComp &> UpdKeyTree;
-    typedef UpdKeyTree::Iterator                       UpdKeyTreeIterator;
-    GenerationHandler g;
-    UpdKeyTree t;
-    UpdKeyComp cmp1(0);
-    for (int i = 0; i < 1000; i+=2) {
-        EXPECT_TRUE(t.insert(i, BTreeNoLeafData(), cmp1));
-    }
-    EXPECT_EQUAL(0u, cmp1._numErrors);
-    for (int i = 0; i < 1000; i+=2) {
-        UpdKeyTreeIterator itr = t.find(i, cmp1);
-        itr.writeKey(i + 1);
-    }
-    UpdKeyComp cmp2(1);
-    for (int i = 1; i < 1000; i+=2) {
-        UpdKeyTreeIterator itr = t.find(i, cmp2);
-        EXPECT_TRUE(itr.valid());
-    }
-    EXPECT_EQUAL(0u, cmp2._numErrors);
-}
-
-
-void
-Test::requireThatSmallNodesWorks()
-{
-    typedef BTreeStore<MyKey, std::string, btree::NoAggregated, MyComp,
-        BTreeDefaultTraits> TreeStore;
-    GenerationHandler g;
-    TreeStore s;
-
-    EntryRef root;
-    EXPECT_EQUAL(0u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-    EXPECT_TRUE(s.insert(root, 40, "fourty"));
-    EXPECT_TRUE(!s.insert(root, 40, "fourty.not"));
-    EXPECT_EQUAL(1u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-    EXPECT_TRUE(s.insert(root, 20, "twenty"));
-    EXPECT_TRUE(!s.insert(root, 20, "twenty.not"));
-    EXPECT_TRUE(!s.insert(root, 40, "fourty.not"));
-    EXPECT_EQUAL(2u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-    EXPECT_TRUE(s.insert(root, 60, "sixty"));
-    EXPECT_TRUE(!s.insert(root, 60, "sixty.not"));
-    EXPECT_TRUE(!s.insert(root, 20, "twenty.not"));
-    EXPECT_TRUE(!s.insert(root, 40, "fourty.not"));
-    EXPECT_EQUAL(3u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-    EXPECT_TRUE(s.insert(root, 50, "fifty"));
-    EXPECT_TRUE(!s.insert(root, 50, "fifty.not"));
-    EXPECT_TRUE(!s.insert(root, 60, "sixty.not"));
-    EXPECT_TRUE(!s.insert(root, 20, "twenty.not"));
-    EXPECT_TRUE(!s.insert(root, 40, "fourty.not"));
-    EXPECT_EQUAL(4u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-
-    for (uint32_t i = 0; i < 100; ++i) {
-        EXPECT_TRUE(s.insert(root, 1000 + i, "big"));
-        if (i > 0) {
-            EXPECT_TRUE(!s.insert(root, 1000 + i - 1, "big"));
-        }
-        EXPECT_EQUAL(5u + i, s.size(root));
-        EXPECT_EQUAL(5u + i <= 8u,  s.isSmallArray(root));
-    }
-    EXPECT_TRUE(s.remove(root, 40));
-    EXPECT_TRUE(!s.remove(root, 40));
-    EXPECT_EQUAL(103u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-    EXPECT_TRUE(s.remove(root, 20));
-    EXPECT_TRUE(!s.remove(root, 20));
-    EXPECT_EQUAL(102u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-    EXPECT_TRUE(s.remove(root, 50));
-    EXPECT_TRUE(!s.remove(root, 50));
-    EXPECT_EQUAL(101u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-    for (uint32_t i = 0; i < 100; ++i) {
-        EXPECT_TRUE(s.remove(root, 1000 + i));
-        if (i > 0) {
-            EXPECT_TRUE(!s.remove(root, 1000 + i - 1));
-        }
-        EXPECT_EQUAL(100 - i, s.size(root));
-        EXPECT_EQUAL(100 - i <= 8u,  s.isSmallArray(root));
-    }
-    EXPECT_EQUAL(1u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-
-    s.clear(root);
-    s.clearBuilder();
-    s.freeze();
-    s.transferHoldLists(g.getCurrentGeneration());
-    g.incGeneration();
-    s.trimHoldLists(g.getFirstUsedGeneration());
-}
-
-
-void
-Test::requireThatApplyWorks()
-{
-    typedef BTreeStore<MyKey, std::string, btree::NoAggregated, MyComp,
-        BTreeDefaultTraits> TreeStore;
-    typedef TreeStore::KeyType KeyType;
-    typedef TreeStore::KeyDataType KeyDataType;
-    GenerationHandler g;
-    TreeStore s;
-    std::vector<KeyDataType> additions;
-    std::vector<KeyType> removals;
-
-    EntryRef root;
-    EXPECT_EQUAL(0u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-
-    additions.clear();
-    removals.clear();
-    additions.push_back(KeyDataType(40, "fourty"));
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(1u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-
-    additions.clear();
-    removals.clear();
-    additions.push_back(KeyDataType(20, "twenty"));
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(2u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-
-    additions.clear();
-    removals.clear();
-    additions.push_back(KeyDataType(60, "sixty"));
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(3u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-
-    additions.clear();
-    removals.clear();
-    additions.push_back(KeyDataType(50, "fifty"));
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(4u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-
-    for (uint32_t i = 0; i < 100; ++i) {
-        additions.clear();
-        removals.clear();
-        additions.push_back(KeyDataType(1000 + i, "big"));
-        s.apply(root, &additions[0], &additions[0] + additions.size(),
-                      &removals[0], &removals[0] + removals.size());
-        EXPECT_EQUAL(5u + i, s.size(root));
-        EXPECT_EQUAL(5u + i <= 8u,  s.isSmallArray(root));
-    }
-
-    additions.clear();
-    removals.clear();
-    removals.push_back(40);
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(103u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-
-    additions.clear();
-    removals.clear();
-    removals.push_back(20);
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(102u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-
-    additions.clear();
-    removals.clear();
-    removals.push_back(50);
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(101u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-    for (uint32_t i = 0; i < 100; ++i) {
-        additions.clear();
-        removals.clear();
-        removals.push_back(1000 +i);
-        s.apply(root, &additions[0], &additions[0] + additions.size(),
-                      &removals[0], &removals[0] + removals.size());
-        EXPECT_EQUAL(100 - i, s.size(root));
-        EXPECT_EQUAL(100 - i <= 8u,  s.isSmallArray(root));
-    }
-    EXPECT_EQUAL(1u, s.size(root));
-    EXPECT_TRUE(s.isSmallArray(root));
-
-    additions.clear();
-    removals.clear();
-    for (uint32_t i = 0; i < 20; ++i)
-        additions.push_back(KeyDataType(1000 + i, "big"));
-    removals.push_back(60);
-    removals.push_back(1002);
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(20u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-
-    additions.clear();
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(19u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-
-    additions.clear();
-    removals.clear();
-    for (uint32_t i = 0; i < 20; ++i)
-        additions.push_back(KeyDataType(1100 + i, "big"));
-    for (uint32_t i = 0; i < 10; ++i)
-        removals.push_back(1000 + i);
-    s.apply(root, &additions[0], &additions[0] + additions.size(),
-                  &removals[0], &removals[0] + removals.size());
-    EXPECT_EQUAL(30u, s.size(root));
-    EXPECT_TRUE(!s.isSmallArray(root));
-
-    s.clear(root);
-    s.clearBuilder();
-    s.freeze();
-    s.transferHoldLists(g.getCurrentGeneration());
-    g.incGeneration();
-    s.trimHoldLists(g.getFirstUsedGeneration());
-}
-
-class MyTreeTestIterator : public MyTree::Iterator
-{
-public:
-    MyTreeTestIterator(const MyTree::Iterator &rhs)
-        : MyTree::Iterator(rhs)
-    {
-    }
-
-    int getPathSize() const { return _pathSize; }
-};
-
-
-void
-Test::requireThatIteratorDistanceWorks(int numEntries)
-{
-    GenerationHandler g;
-    MyTree tree;
-    typedef MyTree::Iterator Iterator;
-    for (int i = 0; i < numEntries; ++i) {
-        tree.insert(i, toStr(i));
-    }
-    MyTreeTestIterator tit = tree.begin();
-    LOG(info,
-        "numEntries=%d, iterator pathSize=%d",
-        numEntries, tit.getPathSize());
-    Iterator it = tree.begin();
-    for (int i = 0; i <= numEntries; ++i) {
-        Iterator iit = tree.lowerBound(i);
-        Iterator iitn = tree.lowerBound(i + 1);
-        Iterator iitu = tree.upperBound(i);
-        Iterator iitls = tree.begin();
-        Iterator iitbs = tree.begin();
-        Iterator iitlsp = tree.begin();
-        Iterator iitbsp = tree.begin();
-        Iterator iitlb(tree.getRoot(), tree.getAllocator());
-        iitlb.lower_bound(i);
-        Iterator iitlb2(BTreeNode::Ref(), tree.getAllocator());
-        iitlb2.lower_bound(tree.getRoot(), i);
-        if (i > 0) {
-            iitls.linearSeek(i);
-            iitbs.binarySeek(i);
-            ++it;
-        }
-        iitlsp.linearSeekPast(i);
-        iitbsp.binarySeekPast(i);
-        Iterator iitlsp2 = iitls;
-        Iterator iitbsp2 = iitbs;
-        Iterator iitnr = i < numEntries ? iitn : tree.begin();
-        --iitnr;
-        if (i < numEntries) {
-            iitlsp2.linearSeekPast(i);
-            iitbsp2.binarySeekPast(i);
-        }
-        EXPECT_EQUAL(i, static_cast<int>(iit.position()));
-        EXPECT_EQUAL(i < numEntries, iit.valid()); 
-        EXPECT_TRUE(iit.identical(it));
-        EXPECT_TRUE(iit.identical(iitls));
-        EXPECT_TRUE(iit.identical(iitbs));
-        EXPECT_TRUE(iit.identical(iitnr));
-        EXPECT_TRUE(iit.identical(iitlb));
-        EXPECT_TRUE(iit.identical(iitlb2));
-        EXPECT_TRUE(iitn.identical(iitu));
-        EXPECT_TRUE(iitn.identical(iitlsp));
-        EXPECT_TRUE(iitn.identical(iitbsp));
-        EXPECT_TRUE(iitn.identical(iitlsp2));
-        EXPECT_TRUE(iitn.identical(iitbsp2));
-        if (i < numEntries) {
-            EXPECT_EQUAL(i + 1, static_cast<int>(iitn.position()));
-            EXPECT_EQUAL(i + 1 < numEntries, iitn.valid());
-        }
-        for (int j = 0; j <= numEntries; ++j) {
-            Iterator jit = tree.lowerBound(j);
-            EXPECT_EQUAL(j, static_cast<int>(jit.position()));
-            EXPECT_EQUAL(j < numEntries, jit.valid()); 
-            EXPECT_EQUAL(i - j, iit - jit);
-            EXPECT_EQUAL(j - i, jit - iit);
-
-            Iterator jit2 = jit;
-            jit2.setupEnd();
-            EXPECT_EQUAL(numEntries - j, jit2 - jit);
-            EXPECT_EQUAL(numEntries - i, jit2 - iit);
-            EXPECT_EQUAL(j - numEntries, jit - jit2);
-            EXPECT_EQUAL(i - numEntries, iit - jit2);
-        }
-    }
-}
-
-
-void
-Test::requireThatIteratorDistanceWorks()
-{
-    requireThatIteratorDistanceWorks(1);
-    requireThatIteratorDistanceWorks(3);
-    requireThatIteratorDistanceWorks(8);
-    requireThatIteratorDistanceWorks(20);
-    requireThatIteratorDistanceWorks(100);
-    requireThatIteratorDistanceWorks(400);
-}
-
-
-int
-Test::Main()
-{
-    TEST_INIT("btree_test");
-
-    requireThatNodeInsertWorks();
-    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 <vespa/vespalib/testkit/testapp.h>
-#include <vespa/searchlib/util/rand48.h>
-#include <vespa/searchlib/btree/btreeroot.h>
-#include <vespa/searchlib/btree/btreeiterator.hpp>
-#include <vespa/searchlib/btree/btreeroot.hpp>
-#include <vespa/searchlib/btree/btreenodeallocator.hpp>
-#include <map>
-
-#include <vespa/log/log.h>
-LOG_SETUP("frozenbtree_test");
-
-using search::btree::BTreeRoot;
-using search::btree::BTreeNode;
-using search::btree::BTreeInternalNode;
-using search::btree::BTreeLeafNode;
-using search::btree::BTreeDefaultTraits;
-using vespalib::GenerationHandler;
-
-namespace search {
-
-
-class FrozenBTreeTest : public vespalib::TestApp
-{
-public:
-    typedef int KeyType;
-private:
-    std::vector<KeyType> _randomValues;
-    std::vector<KeyType> _sortedRandomValues;
-
-public:
-    typedef int DataType;
-    typedef BTreeRoot<KeyType, DataType,
-                      btree::NoAggregated,
-                      std::less<KeyType>,
-                      BTreeDefaultTraits> Tree;
-    typedef Tree::NodeAllocatorType NodeAllocator;
-    typedef Tree::InternalNodeType InternalNodeType;
-    typedef Tree::LeafNodeType LeafNodeType;
-    typedef Tree::Iterator Iterator;
-    typedef Tree::ConstIterator ConstIterator;
-private:
-    GenerationHandler *_generationHandler;
-    NodeAllocator *_allocator;
-    Tree *_tree;
-
-    Rand48 _randomGenerator;
-
-    void allocTree();
-    void freeTree(bool verbose);
-    void fillRandomValues(unsigned int count);
-    void insertRandomValues(Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
-    void removeRandomValues(Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
-    void lookupRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
-    void lookupGoneRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
-    void lookupFrozenRandomValues(const Tree &tree, NodeAllocator &allocator, const std::vector<KeyType> &values);
-    void sortRandomValues();
-    void traverseTreeIterator(const Tree &tree, NodeAllocator &allocator,
-                              const std::vector<KeyType> &sorted, bool frozen);
-
-    void printSubEnumTree(BTreeNode::Ref node, NodeAllocator &allocator, int indent) const;
-    void printEnumTree(const Tree *tree, NodeAllocator &allocator);
-
-    static const char *frozenName(bool frozen) {
-        return frozen ? "frozen" : "thawed";
-    }
-public:
-    FrozenBTreeTest();
-    ~FrozenBTreeTest();
-
-    int Main() override;
-};
-
-FrozenBTreeTest::FrozenBTreeTest()
-    : vespalib::TestApp(),
-      _randomValues(),
-      _sortedRandomValues(),
-      _generationHandler(NULL),
-      _allocator(NULL),
-      _tree(NULL),
-      _randomGenerator()
-{}
-FrozenBTreeTest::~FrozenBTreeTest() {}
-
-void
-FrozenBTreeTest::allocTree()
-{
-    assert(_generationHandler == NULL);
-    assert(_allocator == NULL);
-    assert(_tree == NULL);
-    _generationHandler = new GenerationHandler;
-    _allocator = new NodeAllocator();
-    _tree = new Tree;
-}
-
-
-void
-FrozenBTreeTest::freeTree(bool verbose)
-{
-#if 0
-    LOG(info,
-        "freeTree before clear: %" PRIu64 " (%" PRIu64 " held)"
-        ", %" PRIu32 " leaves",
-        static_cast<uint64_t>(_intTree->getUsedMemory()),
-        static_cast<uint64_t>(_intTree->getHeldMemory()),
-        _intTree->validLeaves());
-    _intTree->clear();
-    LOG(info,
-        "freeTree before unhold: %" PRIu64 " (%" PRIu64 " held)",
-        static_cast<uint64_t>(_intTree->getUsedMemory()),
-        static_cast<uint64_t>(_intTree->getHeldMemory()));
-    _intTree->dropFrozen();
-    _intTree->removeOldGenerations(_intTree->getGeneration() + 1);
-    LOG(info,
-        "freeTree after unhold: %" PRIu64 " (%" PRIu64 " held)",
-        static_cast<uint64_t>(_intTree->getUsedMemory()),
-        static_cast<uint64_t>(_intTree->getHeldMemory()));
-    if (verbose)
-        LOG(info,
-            "%d+%d leftover tree nodes",
-            _intTree->getNumInternalNodes(),
-            _intTree->getNumLeafNodes());
-    EXPECT_TRUE(_intTree->getNumInternalNodes() == 0 &&
-               _intTree->getNumLeafNodes() == 0);
-    delete _intTree;
-    _intTree = NULL;
-    delete _intKeyStore;
-    _intKeyStore = NULL;
-#endif
-    (void) verbose;
-    _tree->clear(*_allocator);
-    _allocator->freeze();
-    _allocator->transferHoldLists(_generationHandler->getCurrentGeneration());
-    _generationHandler->incGeneration();
-    _allocator->trimHoldLists(_generationHandler->getFirstUsedGeneration());
-    delete _tree;
-    _tree = NULL;
-    delete _allocator;
-    _allocator = NULL;
-    delete _generationHandler;
-    _generationHandler = NULL;
-}
-
-
-void
-FrozenBTreeTest::fillRandomValues(unsigned int count)
-{
-    unsigned int i;
-
-    LOG(info, "Filling %u random values", count);
-    _randomValues.clear();
-    _randomValues.reserve(count);
-    _randomGenerator.srand48(42);
-    for (i = 0; i <count; i++)
-        _randomValues.push_back(_randomGenerator.lrand48());
-
-    EXPECT_TRUE(_randomValues.size() == count);
-}
-
-
-void
-FrozenBTreeTest::
-insertRandomValues(Tree &tree,
-                   NodeAllocator &allocator,
-                   const std::vector<KeyType> &values)
-{
-    std::vector<KeyType>::const_iterator i(values.begin());
-    std::vector<KeyType>::const_iterator ie(values.end());
-    Iterator p;
-
-    LOG(info, "insertRandomValues start");
-    for (; i != ie; ++i) {
-#ifdef LOG_FROZENBTREE
-        LOG(info, "Try lookup %d before insert", *i);
-#endif
-        p = tree.find(*i, allocator);
-        if (!p.valid()) {
-            DataType val = *i + 42;
-            if (tree.insert(*i, val, allocator))
-                p = tree.find(*i, allocator);
-        }
-        ASSERT_TRUE(p.valid() && p.getKey() == *i && p.getData() == *i + 42);
-#ifdef DEBUG_FROZENBTREEX
-        printEnumTree(&tree);
-#endif
-    }
-    ASSERT_TRUE(tree.isValid(allocator));
-    ASSERT_TRUE(tree.isValidFrozen(allocator));
-    LOG(info, "insertRandomValues done");
-}
-
-
-void
-FrozenBTreeTest::
-removeRandomValues(Tree &tree,
-                   NodeAllocator &allocator,
-                   const std::vector<KeyType> & values)
-{
-    std::vector<KeyType>::const_iterator i(values.begin());
-    std::vector<KeyType>::const_iterator ie(values.end());
-    Iterator p;
-
-    LOG(info, "removeRandomValues start");
-    for (; i != ie; ++i) {
-#ifdef LOG_FROZENBTREE
-        LOG(info, "Try lookup %d before remove", *i);
-#endif
-        p = tree.find(*i, allocator);
-        if (p.valid()) {
-            if (tree.remove(*i, allocator))
-                p = tree.find(*i, allocator);
-        }
-        ASSERT_TRUE(!p.valid());
-#ifdef DEBUG_FROZENBTREEX
-        tree.printTree();
-#endif
-    }
-    ASSERT_TRUE(tree.isValid(allocator));
-    ASSERT_TRUE(tree.isValidFrozen(allocator));
-    LOG(info, "removeRandomValues done");
-}
-
-
-void
-FrozenBTreeTest::
-lookupRandomValues(const Tree &tree,
-                   NodeAllocator &allocator,
-                   const std::vector<KeyType> &values)
-{
-    std::vector<KeyType>::const_iterator i(values.begin());
-    std::vector<KeyType>::const_iterator ie(values.end());
-    Iterator p;
-
-    LOG(info, "lookupRandomValues start");
-    for (; i != ie; ++i) {
-        p = tree.find(*i, allocator);
-        ASSERT_TRUE(p.valid() && p.getKey() == *i);
-    }
-    LOG(info, "lookupRandomValues done");
-}
-
-
-void
-FrozenBTreeTest::
-lookupGoneRandomValues(const Tree &tree,
-                       NodeAllocator &allocator,
-                       const std::vector<KeyType> &values)
-{
-    std::vector<KeyType>::const_iterator i(values.begin());
-    std::vector<KeyType>::const_iterator ie(values.end());
-    Iterator p;
-
-    LOG(info, "lookupGoneRandomValues start");
-    for (; i != ie; ++i) {
-        p = tree.find(*i, allocator);
-        ASSERT_TRUE(!p.valid());
-    }
-    LOG(info, "lookupGoneRandomValues done");
-}
-
-
-void
-FrozenBTreeTest::
-lookupFrozenRandomValues(const Tree &tree,
-                         NodeAllocator &allocator,
-                         const std::vector<KeyType> &values)
-{
-    std::vector<KeyType>::const_iterator i(values.begin());
-    std::vector<KeyType>::const_iterator ie(values.end());
-    ConstIterator p;
-
-    LOG(info, "lookupFrozenRandomValues start");
-    for (; i != ie; ++i) {
-        p = tree.getFrozenView(allocator).find(*i, std::less<int>());
-        ASSERT_TRUE(p.valid() && p.getKey() == *i && p.getData() == *i + 42);
-    }
-    LOG(info, "lookupFrozenRandomValues done");
-}
-
-
-void
-FrozenBTreeTest::sortRandomValues()
-{
-    std::vector<KeyType>::iterator i;
-    std::vector<KeyType>::iterator ie;
-    uint32_t okcnt;
-    int prevVal;
-    std::vector<KeyType> sorted;
-
-    LOG(info, "sortRandomValues start");
-    sorted = _randomValues;
-    std::sort(sorted.begin(), sorted.end());
-    _sortedRandomValues.clear();
-    _sortedRandomValues.reserve(sorted.size());
-
-    okcnt = 0;
-    prevVal = 0;
-    ie = sorted.end();
-    for (i = sorted.begin(); i != ie; ++i) {
-        if (i == _sortedRandomValues.begin() || *i > prevVal) {
-            okcnt++;
-            _sortedRandomValues.push_back(*i);
-        } else if (*i == prevVal)
-            okcnt++;
-        else
-            abort();
-        prevVal = *i;
-    }
-    EXPECT_TRUE(okcnt == sorted.size());
-    LOG(info, "sortRandomValues done");
-}
-
-
-void
-FrozenBTreeTest::
-traverseTreeIterator(const Tree &tree,
-                     NodeAllocator &allocator,
-                     const std::vector<KeyType> &sorted,
-                     bool frozen)
-{
-   LOG(info,
-       "traverseTreeIterator %s start",
-       frozenName(frozen));
-
-   std::vector<KeyType>::const_iterator i;
-
-   i = sorted.begin();
-   if (frozen) {
-       ConstIterator ai;
-       ai = tree.getFrozenView(allocator).begin();
-       for (;ai.valid(); ++ai, ++i)
-       {
-           ASSERT_TRUE(ai.getKey() == *i);
-       }
-   } else {
-       Iterator ai;
-       ai = tree.begin(allocator);
-       for (;ai.valid(); ++ai, ++i)
-       {
-           ASSERT_TRUE(ai.getKey() == *i);
-       }
-   }
-
-
-   ASSERT_TRUE(i == sorted.end());
-
-   LOG(info,
-       "traverseTreeIterator %s done",
-       frozenName(frozen));
-}
-
-
-void
-FrozenBTreeTest::
-printSubEnumTree(BTreeNode::Ref node,
-                 NodeAllocator &allocator,
-                 int indent) const
-{
-    // typedef BTreeNode Node;
-    typedef LeafNodeType LeafNode;
-    typedef InternalNodeType InternalNode;
-    BTreeNode::Ref subNode;
-    unsigned int i;
-
-    if (allocator.isLeafRef(node)) {
-        const LeafNode *lnode = allocator.mapLeafRef(node);
-        printf("%*s LeafNode %s valid=%d\n",
-               indent, "",
-               lnode->getFrozen() ? "frozen" : "thawed",
-               lnode->validSlots());
-        for (i = 0; i < lnode->validSlots(); i++) {
-
-            KeyType k = lnode->getKey(i);
-            DataType d = lnode->getData(i);
-            printf("leaf value %3d %d %d\n",
-                   (int) i,
-                   (int) k,
-                   (int) d);
-        }
-        return;
-    }
-    const InternalNode *inode = allocator.mapInternalRef(node);
-    printf("%*s IntermediteNode %s valid=%d\n",
-           indent, "",
-           inode->getFrozen() ? "frozen" : "thawed",
-           inode->validSlots());
-    for (i = 0; i < inode->validSlots(); i++) {
-        subNode = inode->getChild(i);
-        assert(subNode != BTreeNode::Ref());
-        printSubEnumTree(subNode, allocator, indent + 4);
-    }
-}
-
-
-void
-FrozenBTreeTest::printEnumTree(const Tree *tree,
-                               NodeAllocator &allocator)
-{
-    printf("Tree Dump start\n");
-    if (!NodeAllocator::isValidRef(tree->getRoot())) {
-        printf("EMPTY\n");
-    } else {
-        printSubEnumTree(tree->getRoot(), allocator, 0);
-    }
-    printf("Tree Dump done\n");
-}
-
-
-
-int
-FrozenBTreeTest::Main()
-{
-    TEST_INIT("frozenbtree_test");
-
-    fillRandomValues(1000);
-    sortRandomValues();
-
-    allocTree();
-    insertRandomValues(*_tree, *_allocator, _randomValues);
-    lookupRandomValues(*_tree, *_allocator, _randomValues);
-    _allocator->freeze();
-    _allocator->transferHoldLists(_generationHandler->getCurrentGeneration());
-    lookupFrozenRandomValues(*_tree, *_allocator, _randomValues);
-    traverseTreeIterator(*_tree,
-                         *_allocator,
-                         _sortedRandomValues,
-                         false);
-    traverseTreeIterator(*_tree,
-                         *_allocator,
-                         _sortedRandomValues,
-                         true);
-    traverseTreeIterator(*_tree,
-                         *_allocator,
-                         _sortedRandomValues,
-                         false);
-    traverseTreeIterator(*_tree,
-                         *_allocator,
-                         _sortedRandomValues,
-                         true);
-    removeRandomValues(*_tree, *_allocator, _randomValues);
-    lookupGoneRandomValues(*_tree, *_allocator, _randomValues);
-    lookupFrozenRandomValues(*_tree, *_allocator,_randomValues);
-    traverseTreeIterator(*_tree,
-                         *_allocator,
-                         _sortedRandomValues,
-                         true);
-    insertRandomValues(*_tree, *_allocator, _randomValues);
-    freeTree(true);
-
-    fillRandomValues(1000000);
-    sortRandomValues();
-
-    allocTree();
-    insertRandomValues(*_tree, *_allocator, _randomValues);
-    traverseTreeIterator(*_tree,
-                         *_allocator,
-                         _sortedRandomValues,
-                         false);
-    freeTree(false);
-
-    TEST_DONE();
-}
-
-}
-
-TEST_APPHOOK(search::FrozenBTreeTest);