diff options
author | Tor Egge <Tor.Egge@broadpark.no> | 2021-04-04 17:11:21 +0200 |
---|---|---|
committer | Tor Egge <Tor.Egge@broadpark.no> | 2021-04-04 17:11:21 +0200 |
commit | 409eeae532d0a5b9b877797c4055b7ea6d8acfaa (patch) | |
tree | d027751bbd8eb47971c6f8bf153d6e2fdc6cfad4 /vespalib | |
parent | 55766b25eadd4c9527040fd1a8b3458fc526e713 (diff) |
Compaction of B-tree can cause identity of nodes to change.
Change operator== for B-tree iterator accordingly.
Diffstat (limited to 'vespalib')
-rw-r--r-- | vespalib/src/tests/btree/btree_test.cpp | 20 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/btree/btreeiterator.h | 14 |
2 files changed, 32 insertions, 2 deletions
diff --git a/vespalib/src/tests/btree/btree_test.cpp b/vespalib/src/tests/btree/btree_test.cpp index e1a9fa98a21..55947736621 100644 --- a/vespalib/src/tests/btree/btree_test.cpp +++ b/vespalib/src/tests/btree/btree_test.cpp @@ -1549,6 +1549,16 @@ inc_generation(GenerationHandler &g, Tree &t) s.trimHoldLists(g.getFirstUsedGeneration()); } +template <typename Tree> +void +make_iterators(Tree& t, std::vector<int>& list, std::vector<typename Tree::ConstIterator>& iterators) +{ + for (auto key : list) { + iterators.emplace_back(t.lowerBound(key)); + } + iterators.emplace_back(t.lowerBound(300)); +} + } TEST_F(BTreeTest, require_that_compaction_works) @@ -1557,7 +1567,9 @@ TEST_F(BTreeTest, require_that_compaction_works) GenerationHandler g; Tree t; std::vector<int> before_list; + std::vector<typename Tree::ConstIterator> before_iterators; std::vector<int> after_list; + std::vector<typename Tree::ConstIterator> after_iterators; for (uint32_t i = 1; i < 256; ++i) { t.insert(i, 101); } @@ -1567,12 +1579,20 @@ TEST_F(BTreeTest, require_that_compaction_works) inc_generation(g, t); auto memory_usage_before = t.getAllocator().getMemoryUsage(); t.foreach_key([&before_list](int key) { before_list.emplace_back(key); }); + make_iterators(t, before_list, before_iterators); t.compact_worst(); inc_generation(g, t); auto memory_usage_after = t.getAllocator().getMemoryUsage(); t.foreach_key([&after_list](int key) { after_list.emplace_back(key); }); + make_iterators(t, after_list, after_iterators); EXPECT_LT(memory_usage_after.deadBytes(), memory_usage_before.deadBytes()); EXPECT_EQ(before_list, after_list); + EXPECT_EQ(before_iterators.size(), after_iterators.size()); + for (size_t i = 1; i < before_iterators.size(); ++i) { + for (size_t j = 1; j < after_iterators.size(); ++j) { + EXPECT_EQ(before_iterators[i] == after_iterators[j], i == j); + } + } } } diff --git a/vespalib/src/vespa/vespalib/btree/btreeiterator.h b/vespalib/src/vespa/vespalib/btree/btreeiterator.h index bbee8746d6f..6639351e856 100644 --- a/vespalib/src/vespa/vespalib/btree/btreeiterator.h +++ b/vespalib/src/vespa/vespalib/btree/btreeiterator.h @@ -348,10 +348,20 @@ public: bool operator==(const BTreeIteratorBase & rhs) const { - if (_leaf.getNode() != rhs._leaf.getNode() || - _leaf.getIdx() != rhs._leaf.getIdx()) { + if (_leaf.getIdx() != rhs._leaf.getIdx()) { return false; } + if (_leaf.getNode() == rhs._leaf.getNode()) { + return true; + } + if ((_leaf.getNode() == nullptr) || (rhs._leaf.getNode() == nullptr) || (_pathSize != rhs._pathSize)) { + return false; + } + for (uint32_t level = 0; level < _pathSize; ++level) { + if (_path[level].getIdx() != rhs._path[level].getIdx()) { + return false; + } + } return true; } |