From 03565f4e4ec13b2d9485ce77dc2d7b01338bfab1 Mon Sep 17 00:00:00 2001 From: Tor Egge Date: Thu, 22 Feb 2024 01:19:19 +0100 Subject: Remove BTreeStore insert and remove member functions, use apply instead. --- vespalib/src/tests/btree/btree_test.cpp | 62 ++++--- vespalib/src/tests/btree/btreeaggregation_test.cpp | 149 +++------------- vespalib/src/vespa/vespalib/btree/btreestore.h | 4 - vespalib/src/vespa/vespalib/btree/btreestore.hpp | 196 --------------------- 4 files changed, 58 insertions(+), 353 deletions(-) (limited to 'vespalib') diff --git a/vespalib/src/tests/btree/btree_test.cpp b/vespalib/src/tests/btree/btree_test.cpp index 30e3df7dd14..a43fbf01ad1 100644 --- a/vespalib/src/tests/btree/btree_test.cpp +++ b/vespalib/src/tests/btree/btree_test.cpp @@ -1227,6 +1227,23 @@ TEST_F(BTreeTest, require_that_update_of_key_works) EXPECT_EQ(0u, cmp2._numErrors); } +namespace { + +template +void +insert(TreeStore& s, EntryRef& root, typename TreeStore::KeyDataType addition) +{ + s.apply(root, &addition, &addition + 1, nullptr, nullptr); +} + +template +void +remove(TreeStore& s, EntryRef& root, typename TreeStore::KeyType removal) +{ + s.apply(root, nullptr, nullptr, &removal, &removal + 1); +} + +} TEST_F(BTreeTest, require_that_small_nodes_works) { @@ -1238,56 +1255,37 @@ TEST_F(BTreeTest, require_that_small_nodes_works) EntryRef root; EXPECT_EQ(0u, s.size(root)); EXPECT_TRUE(s.isSmallArray(root)); - EXPECT_TRUE(s.insert(root, 40, "fourty")); - EXPECT_TRUE(!s.insert(root, 40, "fourty.not")); + insert(s, root, {40, "fourty"}); EXPECT_EQ(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")); + insert(s, root, {20, "twenty"}); EXPECT_EQ(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")); + insert(s, root, {60, "sixty"}); EXPECT_EQ(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")); + insert(s, root, {50, "fifty"}); EXPECT_EQ(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")); - } + insert(s, root, {int(1000 + i), "big"}); EXPECT_EQ(5u + i, s.size(root)); - EXPECT_EQ(5u + i <= 8u, s.isSmallArray(root)); + EXPECT_EQ(5u + i <= TreeStore::clusterLimit, s.isSmallArray(root)); } - EXPECT_TRUE(s.remove(root, 40)); - EXPECT_TRUE(!s.remove(root, 40)); + remove(s, root, 40); EXPECT_EQ(103u, s.size(root)); EXPECT_TRUE(!s.isSmallArray(root)); - EXPECT_TRUE(s.remove(root, 20)); - EXPECT_TRUE(!s.remove(root, 20)); + remove(s, root, 20); EXPECT_EQ(102u, s.size(root)); EXPECT_TRUE(!s.isSmallArray(root)); - EXPECT_TRUE(s.remove(root, 50)); - EXPECT_TRUE(!s.remove(root, 50)); + remove(s, root, 50); EXPECT_EQ(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)); - } + remove(s, root, 1000 + i); EXPECT_EQ(100 - i, s.size(root)); - EXPECT_EQ(100 - i <= 8u, s.isSmallArray(root)); + EXPECT_EQ(100 - i <= TreeStore::clusterLimit, s.isSmallArray(root)); } EXPECT_EQ(1u, s.size(root)); EXPECT_TRUE(s.isSmallArray(root)); @@ -1367,7 +1365,7 @@ TEST_F(BTreeTest, require_that_apply_works) additions.push_back(KeyDataType(1000 + i, "big")); apply_tree_mutations(s, root, additions, removals); EXPECT_EQ(5u + i, s.size(root)); - EXPECT_EQ(5u + i <= 8u, s.isSmallArray(root)); + EXPECT_EQ(5u + i <= TreeStore::clusterLimit, s.isSmallArray(root)); } additions.clear(); @@ -1396,7 +1394,7 @@ TEST_F(BTreeTest, require_that_apply_works) removals.push_back(1000 +i); apply_tree_mutations(s, root, additions, removals); EXPECT_EQ(100 - i, s.size(root)); - EXPECT_EQ(100 - i <= 8u, s.isSmallArray(root)); + EXPECT_EQ(100 - i <= TreeStore::clusterLimit, s.isSmallArray(root)); } EXPECT_EQ(1u, s.size(root)); EXPECT_TRUE(s.isSmallArray(root)); diff --git a/vespalib/src/tests/btree/btreeaggregation_test.cpp b/vespalib/src/tests/btree/btreeaggregation_test.cpp index 15fb9b51d21..b33242b918e 100644 --- a/vespalib/src/tests/btree/btreeaggregation_test.cpp +++ b/vespalib/src/tests/btree/btreeaggregation_test.cpp @@ -54,12 +54,6 @@ toLowVal(uint32_t key) return toVal(key) - 1000000; } -int32_t -toNotVal(uint32_t key) -{ - return key + 2000; -} - } using MyTraits = BTreeTraits<4, 4, 31, false>; @@ -187,86 +181,6 @@ MockTree::MockTree() {} MockTree::~MockTree() {} -class MyTreeForceApplyStore : public MyTreeStore -{ -public: - using CompareT = MyComp; - - 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 additions; - std::vector removals; - removals.push_back(key); - apply(ref, - additions.data(), additions.data() + additions.size(), - removals.data(), removals.data() + removals.size(), - comp); - return retVal; -} - - template void freezeTree(GenerationHandler &g, ManagerType &m) @@ -337,7 +251,6 @@ private: void requireThatUpdateOfDataWorks(); void requireThatFrozenViewProvidesAggregatedValues(); - template void requireThatSmallNodesWorks(); public: @@ -1101,86 +1014,81 @@ Test::requireThatUpdateOfDataWorks() } } +namespace { + +void +insert(MyTreeStore& s, EntryRef& root, MyTreeStore::KeyDataType addition) +{ + s.apply(root, &addition, &addition + 1, nullptr, nullptr); +} + +void +remove(MyTreeStore& s, EntryRef& root, MyTreeStore::KeyType removal) +{ + s.apply(root, nullptr, nullptr, &removal, &removal + 1); +} + +} -template void Test::requireThatSmallNodesWorks() { GenerationHandler g; - TreeStore s; + MyTreeStore 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))); + insert(s, 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))); + insert(s, 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))); + insert(s, 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))); + insert(s, 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)); + insert(s, root, {int(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)); + EXPECT_EQUAL(5u + i <= MyTreeStore::clusterLimit, s.isSmallArray(root)); TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); } - EXPECT_TRUE(s.remove(root, 40)); + remove(s, 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)); + remove(s, 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)); + remove(s, 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)); + remove(s, 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)); + EXPECT_EQUAL(100 - i <= MyTreeStore::clusterLimit, s.isSmallArray(root)); TEST_DO(EXPECT_TRUE(assertAggregated(mock, s, root))); } EXPECT_EQUAL(1u, s.size(root)); @@ -1233,8 +1141,7 @@ Test::Main() requireThatTreeIteratorAssignWorks(); requireThatUpdateOfKeyWorks(); requireThatUpdateOfDataWorks(); - TEST_DO(requireThatSmallNodesWorks()); - TEST_DO(requireThatSmallNodesWorks()); + TEST_DO(requireThatSmallNodesWorks()); TEST_DO(requireThatFrozenViewProvidesAggregatedValues()); TEST_DONE(); diff --git a/vespalib/src/vespa/vespalib/btree/btreestore.h b/vespalib/src/vespa/vespalib/btree/btreestore.h index 5ab3a317be8..4b20c16c91b 100644 --- a/vespalib/src/vespa/vespalib/btree/btreestore.h +++ b/vespalib/src/vespa/vespalib/btree/btreestore.h @@ -136,10 +136,6 @@ public: void makeTree(EntryRef &ref, const KeyDataType *array, uint32_t clusterSize); void makeArray(EntryRef &ref, EntryRef leafRef, LeafNodeType *leafNode); - bool insert(EntryRef &ref, const KeyType &key, const DataType &data, CompareT comp = CompareT()); - - bool remove(EntryRef &ref, const KeyType &key,CompareT comp = CompareT()); - uint32_t getNewClusterSize(const KeyDataType *o, const KeyDataType *oe, AddIter a, AddIter ae, RemoveIter r, RemoveIter re, CompareT comp); diff --git a/vespalib/src/vespa/vespalib/btree/btreestore.hpp b/vespalib/src/vespa/vespalib/btree/btreestore.hpp index 17ab627d50c..012b9852d13 100644 --- a/vespalib/src/vespa/vespalib/btree/btreestore.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreestore.hpp @@ -184,202 +184,6 @@ makeArray(EntryRef &ref, EntryRef root, LeafNodeType *leafNode) ref = kPair.ref; } - -template -bool -BTreeStore:: -insert(EntryRef &ref, - const KeyType &key, const DataType &data, - CompareT comp) -{ -#ifdef FORCE_APPLY - bool retVal = true; - if (ref.valid()) { - RefType iRef(ref); - uint32_t clusterSize = getClusterSize(iRef); - if (clusterSize == 0) { - const BTreeType *tree = getTreeEntry(iRef); - 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, nullptr, nullptr, comp); - } - return retVal; -#else - if (!ref.valid()) { - KeyDataTypeRefPair kPair(allocKeyData(1)); - KeyDataType *kd = kPair.data; - kd->_key = key; - kd->setData(data); - ref = kPair.ref; - return true; - } - RefType iRef(ref); - uint32_t clusterSize = getClusterSize(iRef); - if (clusterSize == 0) { - BTreeType *tree = getWTreeEntry(iRef); - return tree->insert(key, data, _allocator, comp, _aggrCalc); - } - 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)) - return false; // key already present - if (clusterSize < clusterLimit) { - // Grow array - KeyDataTypeRefPair kPair(allocKeyData(clusterSize + 1)); - KeyDataType *kd = kPair.data; - // Copy data before key - for (const KeyDataType *i = old; i != oldi; ++i, ++kd) { - kd->_key = i->_key; - kd->setData(i->getData()); - } - // Copy key - kd->_key = key; - kd->setData(data); - ++kd; - // Copy data after key - for (const KeyDataType *i = oldi; i != olde; ++i, ++kd) { - kd->_key = i->_key; - kd->setData(i->getData()); - } - assert(kd == kPair.data + clusterSize + 1); - _store.hold_entry(ref); - ref = kPair.ref; - return true; - } - // Convert from short array to tree - LeafNodeTypeRefPair lPair(_allocator.allocLeafNode()); - LeafNodeType *lNode = lPair.data; - uint32_t idx = 0; - lNode->setValidSlots(clusterSize + 1); - // Copy data before key - for (const KeyDataType *i = old; i != oldi; ++i, ++idx) { - lNode->update(idx, i->_key, i->getData()); - } - // Copy key - lNode->update(idx, key, data); - ++idx; - // Copy data after key - for (const KeyDataType *i = oldi; i != olde; ++i, ++idx) { - lNode->update(idx, i->_key, i->getData()); - } - assert(idx == clusterSize + 1); - using Aggregator = BTreeAggregator; - if constexpr (AggrCalcT::hasAggregated()) { - Aggregator::recalc(*lNode, _aggrCalc); - } - lNode->freeze(); - BTreeTypeRefPair tPair(allocBTree()); - tPair.data->setRoots(lPair.ref); // allow immediate access to readers - _store.hold_entry(ref); - ref = tPair.ref; - return true; -#endif -} - - -template -bool -BTreeStore:: -remove(EntryRef &ref, - const KeyType &key, - CompareT comp) -{ -#ifdef FORCE_APPLY - 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); - 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 additions; - std::vector removals; - removals.push_back(key); - apply(ref, - &additions[0], &additions[additions.size()], - &removals[0], &removals[removals.size()], - comp); - return retVal; -#else - if (!ref.valid()) - return false; // not found - RefType iRef(ref); - uint32_t clusterSize = getClusterSize(iRef); - if (clusterSize != 0) { - 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)) - return false; // not found - if (clusterSize == 1) { - _store.hold_entry(ref); - ref = EntryRef(); - return true; - } - // Copy to smaller array - KeyDataTypeRefPair kPair(allocKeyData(clusterSize - 1)); - KeyDataType *kd = kPair.data; - // Copy data before key - for (const KeyDataType *i = old; i != oldi; ++i, ++kd) { - kd->_key = i->_key; - kd->setData(i->getData()); - } - // Copy data after key - for (const KeyDataType *i = oldi + 1; i != olde; ++i, ++kd) { - kd->_key = i->_key; - kd->setData(i->getData()); - } - assert(kd == kPair.data + clusterSize - 1); - _store.hold_entry(ref); - ref = kPair.ref; - return true; - } - BTreeType *tree = getWTreeEntry(iRef); - if (!tree->remove(key, _allocator, comp, _aggrCalc)) - return false; // not found - EntryRef root = tree->getRoot(); - assert(NodeAllocatorType::isValidRef(root)); - if (!_allocator.isLeafRef(root)) - return true; - LeafNodeType *lNode = _allocator.mapLeafRef(root); - clusterSize = lNode->validSlots(); - assert(clusterSize > 0); - if (clusterSize > clusterLimit) - return true; - // Convert from tree to short array - makeArray(ref, root, lNode); - return true; -#endif -} - - template uint32_t -- cgit v1.2.3