<deque>: Make deque::shrink_to_fit never relocate elements (#4091)

frederick-vs-ja · achabense · StephanTLavavej · web-flow · commit 46402aa2d7f7 · 2024-01-30T12:10:15.000-08:00
Co-authored-by: achabense &lt;60953653+achabense@users.noreply.github.com&gt;
Co-authored-by: Stephan T. Lavavej &lt;stl@nuwen.net&gt;
diff --git a/stl/inc/deque b/stl/inc/deque
@@ -989,19 +989,74 @@ public:
     }
 
     void shrink_to_fit() {
-        size_type _Oldcapacity = _Block_size * _Mapsize();
-        size_type _Newcapacity = _Oldcapacity / 2;
+        if (empty()) {
+            if (_Map() != nullptr) {
+                _Reset_map();
+            }
+            return;
+        }
+
+        const auto _Mask = static_cast<size_type>(_Mapsize() - 1);
+
+        const auto _First_used_block_idx = static_cast<size_type>(_Myoff() / _Block_size);
+
+        // (_Myoff() + _Mysize() - 1) is for the last element, i.e. the back() of the deque.
+        // Divide by _Block_size to get the unmasked index of the last used block.
+        // Add 1 to get the unmasked index of the first unused block.
+        const auto _Unmasked_first_unused_block_idx =
+            static_cast<size_type>(((_Myoff() + _Mysize() - 1) / _Block_size) + 1);
+
+        const auto _First_unused_block_idx = static_cast<size_type>(_Unmasked_first_unused_block_idx & _Mask);
+
+        // deallocate unused blocks, traversing over the circular buffer until the first used block index
+        for (auto _Block_idx = _First_unused_block_idx; _Block_idx != _First_used_block_idx;
+             _Block_idx      = static_cast<size_type>((_Block_idx + 1) & _Mask)) {
+            auto& _Block_ptr = _Map()[static_cast<_Map_difference_type>(_Block_idx)];
+            if (_Block_ptr != nullptr) {
+                _Getal().deallocate(_Block_ptr, _Block_size);
+                _Block_ptr = nullptr;
+            }
+        }
+
+        const auto _Used_block_count = static_cast<size_type>(_Unmasked_first_unused_block_idx - _First_used_block_idx);
+
+        size_type _New_block_count = _Minimum_map_size; // should be power of 2
+
+        while (_New_block_count < _Used_block_count) {
+            _New_block_count *= 2;
+        }
+
+        if (_New_block_count >= _Mapsize()) {
+            return;
+        }
+
+        // worth shrinking the internal map, do it
+
+        _Alpty _Almap(_Getal());
+        const auto _New_map = _Almap.allocate(_New_block_count);
 
-        if (_Newcapacity < _Block_size * _Minimum_map_size) {
-            _Newcapacity = _Block_size * _Minimum_map_size;
+        _Orphan_all(); // the map can be shrunk, invalidate all iterators
+
+        // transfer the ownership of blocks to pointers in the new map
+        for (size_type _Block = 0; _Block != _Used_block_count; ++_Block) {
+            const auto _New_block_idx = static_cast<_Map_difference_type>(_Block);
+            const auto _Old_block_idx = static_cast<_Map_difference_type>((_First_used_block_idx + _Block) & _Mask);
+            _STD _Construct_in_place(_New_map[_New_block_idx], _Map()[_Old_block_idx]);
         }
 
-        if ((empty() && _Mapsize() > 0)
-            || (!empty() && size() <= _Newcapacity && _Newcapacity < _Oldcapacity)) { // worth shrinking, do it
-            deque _Tmp(
-                _STD make_move_iterator(_Unchecked_begin()), _STD make_move_iterator(_Unchecked_end()), _Getal());
-            swap(_Tmp);
+        // null out the rest of the new map
+        _STD _Uninitialized_value_construct_n_unchecked1(
+            _New_map + static_cast<_Map_difference_type>(_Used_block_count), _New_block_count - _Used_block_count);
+
+        for (auto _Block = _Map_distance(); _Block > 0;) {
+            --_Block;
+            _STD _Destroy_in_place(_Map()[_Block]); // destroy pointer to block
         }
+        _Almap.deallocate(_Map(), _Mapsize()); // free storage for map
+
+        _Map()     = _New_map;
+        _Mapsize() = _New_block_count;
+        _Myoff() %= _Block_size; // the first element is within block index 0 of the new map
     }
 
     _NODISCARD const_reference operator[](size_type _Pos) const noexcept /* strengthened */ {
@@ -1591,27 +1646,37 @@ private:
         _Mapsize() += _Count;
     }
 
+    void _Reset_map() noexcept {
+        // pre: each block pointer is either null or pointing to a block without constructed elements
+
+        for (auto _Block = _Map_distance(); _Block > 0;) { // free storage for a block and destroy pointer
+            --_Block;
+            auto& _Block_ptr = _Map()[_Block];
+            if (_Block_ptr) { // free block
+                _Getal().deallocate(_Block_ptr, _Block_size);
+            }
+            _STD _Destroy_in_place(_Block_ptr); // destroy pointer to block
+        }
+
+        _Alpty _Almap(_Getal());
+        _Almap.deallocate(_Map(), _Mapsize()); // free storage for map
+
+        _Map()     = nullptr;
+        _Mapsize() = 0;
+    }
+
     void _Tidy() noexcept { // free all storage
         _Orphan_all();
 
-        _Alpty _Almap(_Getal());
         while (!empty()) {
             pop_back();
         }
 
         if (_Map() != nullptr) {
-            for (auto _Block = _Map_distance(); _Block > 0;) { // free storage for a block and destroy pointer
-                if (_Map()[--_Block]) { // free block
-                    _Getal().deallocate(_Map()[_Block], _Block_size);
-                }
-                _Destroy_in_place(_Map()[_Block]); // destroy pointer to block
-            }
-
-            _Almap.deallocate(_Map(), _Mapsize()); // free storage for map
+            _Reset_map();
         }
 
-        _Mapsize() = 0;
-        _Map()     = nullptr;
+        _STL_INTERNAL_CHECK(_Mapsize() == 0); // null map should always be paired with zero mapsize
     }
 
 #if _ITERATOR_DEBUG_LEVEL == 2
diff --git a/tests/std/tests/Dev10_860421_deque_push_back_pop_front/test.cpp b/tests/std/tests/Dev10_860421_deque_push_back_pop_front/test.cpp
@@ -259,11 +259,56 @@ void test_exception_safety_for_throwing_movable() {
     assert(d == d_orig);
 }
 
+// Also test GH-4072: <deque>: shrink_to_fit() should follow the Standard
+void test_gh_4072() {
+    {
+        constexpr int removed_count = 768;
+
+        deque<ThrowingMovable> d;
+        for (int i = 0; i < 1729; ++i) {
+            d.emplace_back(i);
+        }
+
+        for (int i = 0; i < removed_count; ++i) {
+            d.pop_front();
+            d.pop_back();
+        }
+
+        deque<ThrowingMovable> d2;
+        for (int i = removed_count; i < 1729 - removed_count; ++i) {
+            d2.emplace_back(i);
+        }
+
+        d.shrink_to_fit(); // ensures that no constructor or assignment operator of the element type is called
+        assert(d == d2);
+    }
+
+    // ensure that the circular buffer is correctly handled
+    {
+        deque<ThrowingMovable> deq(128);
+        deq.pop_back();
+        deq.emplace_front(0);
+        deq.shrink_to_fit();
+    }
+    {
+        deque<ThrowingMovable> deq(128);
+        for (int i = 0; i < 120; ++i) {
+            deq.pop_back();
+        }
+        for (int i = 0; i < 5; ++i) {
+            deq.emplace_front(0);
+        }
+        deq.shrink_to_fit();
+    }
+}
+
 int main() {
     test_push_back_pop_front();
 
     test_Dev10_391805();
 
     test_exception_safety_for_nonswappable_movable();
     test_exception_safety_for_throwing_movable();
+
+    test_gh_4072();
 }
diff --git a/tests/std/tests/VSO_0000000_allocator_propagation/test.cpp b/tests/std/tests/VSO_0000000_allocator_propagation/test.cpp
@@ -501,7 +501,7 @@ void test_deque_shrink_to_fit_per_alloc() {
     }
 }
 
-void test_deque_shrink_to_fit() { // MSVC STL's deque::shrink_to_fit relies on swap
+void test_deque_shrink_to_fit() { // regression test: MSVC STL's deque::shrink_to_fit used to rely on swap
     test_deque_shrink_to_fit_per_alloc<StationaryAlloc<int>>();
     test_deque_shrink_to_fit_per_alloc<CopyAlloc<int>>();
     test_deque_shrink_to_fit_per_alloc<CopyEqualAlloc<int>>();

Original file line number	Diff line number	Diff line change
`@@ -501,7 +501,7 @@ void test_deque_shrink_to_fit_per_alloc() {`
`501`	`501`	`}`
`502`	`502`	`}`
`503`	`503`
`504`		`-void test_deque_shrink_to_fit() { // MSVC STL's deque::shrink_to_fit relies on swap`
	`504`	`+void test_deque_shrink_to_fit() { // regression test: MSVC STL's deque::shrink_to_fit used to rely on swap`
`505`	`505`	`test_deque_shrink_to_fit_per_alloc<StationaryAlloc<int>>();`
`506`	`506`	`test_deque_shrink_to_fit_per_alloc<CopyAlloc<int>>();`
`507`	`507`	`test_deque_shrink_to_fit_per_alloc<CopyEqualAlloc<int>>();`