From 409eeae532d0a5b9b877797c4055b7ea6d8acfaa Mon Sep 17 00:00:00 2001 From: Tor Egge Date: Sun, 4 Apr 2021 17:11:21 +0200 Subject: Compaction of B-tree can cause identity of nodes to change. Change operator== for B-tree iterator accordingly. --- vespalib/src/tests/btree/btree_test.cpp | 20 ++++++++++++++++++++ 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 +void +make_iterators(Tree& t, std::vector& list, std::vector& 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 before_list; + std::vector before_iterators; std::vector after_list; + std::vector 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; } -- cgit v1.2.3 From a13ab9632e3ca8ef1736301ae7ad87a65e12c5a7 Mon Sep 17 00:00:00 2001 From: Tor Egge Date: Sun, 4 Apr 2021 18:58:47 +0200 Subject: Test that foreach_key_range and operator- member functions on B-tree iterator don't depend on node identity. --- vespalib/src/tests/btree/btree_test.cpp | 45 ++++++++++++++++++++-- vespalib/src/vespa/vespalib/btree/btreeiterator.h | 2 - .../src/vespa/vespalib/btree/btreeiterator.hpp | 3 -- 3 files changed, 42 insertions(+), 8 deletions(-) diff --git a/vespalib/src/tests/btree/btree_test.cpp b/vespalib/src/tests/btree/btree_test.cpp index 55947736621..82fa4b6b50a 100644 --- a/vespalib/src/tests/btree/btree_test.cpp +++ b/vespalib/src/tests/btree/btree_test.cpp @@ -1559,6 +1559,28 @@ make_iterators(Tree& t, std::vector& list, std::vector &_list; + size_t _start_pos; + size_t _end_pos; + size_t _curr_pos; +public: + KeyRangeValidator(std::vector &list, size_t start_pos, size_t end_pos) + : _list(list), + _start_pos(start_pos), + _end_pos(end_pos), + _curr_pos(start_pos) + { + } + void operator()(int key) { + assert(_curr_pos < _list.size()); + EXPECT_EQ(key, _list[_curr_pos]); + ++_curr_pos; + } + size_t curr_pos() const noexcept { return _curr_pos; } +}; + } TEST_F(BTreeTest, require_that_compaction_works) @@ -1577,10 +1599,13 @@ TEST_F(BTreeTest, require_that_compaction_works) t.remove(i); } inc_generation(g, t); + auto guard = g.takeGuard(); 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(); + for (int i = 0; i < 15; ++i) { + 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); }); @@ -1588,9 +1613,23 @@ TEST_F(BTreeTest, require_that_compaction_works) 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) { + for (size_t i = 0; i < before_iterators.size(); ++i) { + for (size_t j = 0; j < after_iterators.size(); ++j) { EXPECT_EQ(before_iterators[i] == after_iterators[j], i == j); + EXPECT_EQ(before_iterators[i] - after_iterators[j], static_cast(i - j)); + EXPECT_EQ(after_iterators[j] - before_iterators[i], static_cast(j - i)); + if (i <= j) { + KeyRangeValidator validate_keys(before_list, i, j); + EXPECT_EQ(i, validate_keys.curr_pos()); + before_iterators[i].foreach_key_range(after_iterators[j], [&validate_keys](int key) { validate_keys(key); }); + EXPECT_EQ(j, validate_keys.curr_pos()); + } + if (j <= i) { + KeyRangeValidator validate_keys(before_list, j, i); + EXPECT_EQ(j, validate_keys.curr_pos()); + after_iterators[j].foreach_key_range(before_iterators[i], [&validate_keys](int key) { validate_keys(key); }); + EXPECT_EQ(i, validate_keys.curr_pos()); + } } } } diff --git a/vespalib/src/vespa/vespalib/btree/btreeiterator.h b/vespalib/src/vespa/vespalib/btree/btreeiterator.h index 6639351e856..21d232db31a 100644 --- a/vespalib/src/vespa/vespalib/btree/btreeiterator.h +++ b/vespalib/src/vespa/vespalib/btree/btreeiterator.h @@ -531,7 +531,6 @@ public: uint32_t eidx; do { --level; - assert(_path[level].getNode() == end_itr._path[level].getNode()); idx = _path[level].getIdx(); eidx = end_itr._path[level].getIdx(); if (idx > eidx) { @@ -555,7 +554,6 @@ public: return; } else { // Lowest shared node is a leaf node. - assert(_leaf.getNode() == end_itr._leaf.getNode()); } } uint32_t idx = _leaf.getIdx(); diff --git a/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp b/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp index 82864bff057..2102abbf10c 100644 --- a/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp @@ -515,15 +515,12 @@ operator-(const BTreeIteratorBase &rhs) const if (_pathSize != 0) { uint32_t pidx = _pathSize; while (pidx > 0) { - assert(_path[pidx - 1].getNode() == rhs._path[pidx - 1].getNode()); if (_path[pidx - 1].getIdx() != rhs._path[pidx - 1].getIdx()) break; --pidx; } return position(pidx) - rhs.position(pidx); } else { - assert(_leaf.getNode() == nullptr || rhs._leaf.getNode() == nullptr || - _leaf.getNode() == rhs._leaf.getNode()); return position(0) - rhs.position(0); } } -- cgit v1.2.3