Refactor deque to centralize handling of spare blocks.

I have upcoming changes that modify how deque handles spare blocks.
This cleanup is intended to make those changes easier to review
and understand. This patch should have NFC.

llvm-svn: 367631

2 files changed, 334 insertions, 48 deletions

diff --git a/libcxx/include/deque b/libcxx/include/deque
index d3ccf2ef6f7..fe988d093ef 100644
--- a/libcxx/include/deque
+++ b/libcxx/include/deque
@@ -934,7 +934,7 @@ public:
     typedef _Allocator                               allocator_type;
     typedef allocator_traits<allocator_type>         __alloc_traits;
     typedef typename __alloc_traits::size_type       size_type;
-protected:
+
     typedef _Tp                                      value_type;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
@@ -1399,7 +1399,7 @@ public:
 
     _LIBCPP_INLINE_VISIBILITY
     bool __invariants() const {return __base::__invariants();}
-private:
+
     typedef typename __base::__map_const_pointer __map_const_pointer;
 
     _LIBCPP_INLINE_VISIBILITY
@@ -1413,15 +1413,53 @@ private:
         return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
     }
     _LIBCPP_INLINE_VISIBILITY
+    size_type __block_count() const
+    {
+        return __base::__map_.size();
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
     size_type __front_spare() const
     {
         return __base::__start_;
     }
     _LIBCPP_INLINE_VISIBILITY
+    size_type __front_spare_blocks() const {
+      return __front_spare() / __base::__block_size;
+    }
+    _LIBCPP_INLINE_VISIBILITY
     size_type __back_spare() const
     {
         return __capacity() - (__base::__start_ + __base::size());
     }
+    _LIBCPP_INLINE_VISIBILITY
+    size_type __back_spare_blocks() const {
+      return __back_spare() / __base::__block_size;
+    }
+
+ private:
+    _LIBCPP_INLINE_VISIBILITY
+    bool __maybe_remove_front_spare(bool __keep_one = true) {
+      if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) {
+        __alloc_traits::deallocate(__base::__alloc(), __base::__map_.front(),
+                                   __base::__block_size);
+        __base::__map_.pop_front();
+        __base::__start_ -= __base::__block_size;
+        return true;
+      }
+      return false;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool __maybe_remove_back_spare(bool __keep_one = true) {
+      if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) {
+        __alloc_traits::deallocate(__base::__alloc(), __base::__map_.back(),
+                                   __base::__block_size);
+        __base::__map_.pop_back();
+        return true;
+      }
+      return false;
+    }
 
     template <class _InpIter>
         void __append(_InpIter __f, _InpIter __l,
@@ -1727,17 +1765,8 @@ deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
     }
     else
     {
-        if (__front_spare() >= __base::__block_size)
-        {
-            __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
-            __base::__map_.pop_front();
-            __base::__start_ -= __base::__block_size;
-        }
-        if (__back_spare() >= __base::__block_size)
-        {
-            __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
-            __base::__map_.pop_back();
-        }
+      __maybe_remove_front_spare(/*__keep_one=*/false);
+      __maybe_remove_back_spare(/*__keep_one=*/false);
     }
     __base::__map_.shrink_to_fit();
 }
@@ -2596,12 +2625,8 @@ deque<_Tp, _Allocator>::pop_front()
                                                     __base::__start_ / __base::__block_size) +
                                                     __base::__start_ % __base::__block_size));
     --__base::size();
-    if (++__base::__start_ >= 2 * __base::__block_size)
-    {
-        __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
-        __base::__map_.pop_front();
-        __base::__start_ -= __base::__block_size;
-    }
+    ++__base::__start_;
+    __maybe_remove_front_spare();
 }
 
 template <class _Tp, class _Allocator>
@@ -2615,11 +2640,7 @@ deque<_Tp, _Allocator>::pop_back()
                                                     __p / __base::__block_size) +
                                                     __p % __base::__block_size));
     --__base::size();
-    if (__back_spare() >= 2 * __base::__block_size)
-    {
-        __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
-        __base::__map_.pop_back();
-    }
+    __maybe_remove_back_spare();
 }
 
 // move assign [__f, __l) to [__r, __r + (__l-__f)).
@@ -2768,23 +2789,14 @@ deque<_Tp, _Allocator>::erase(const_iterator __f)
         __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
         --__base::size();
         ++__base::__start_;
-        if (__front_spare() >= 2 * __base::__block_size)
-        {
-            __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
-            __base::__map_.pop_front();
-            __base::__start_ -= __base::__block_size;
-        }
+        __maybe_remove_front_spare();
     }
     else
     {   // erase from back
         iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
         __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
         --__base::size();
-        if (__back_spare() >= 2 * __base::__block_size)
-        {
-            __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
-            __base::__map_.pop_back();
-        }
+        __maybe_remove_back_spare();
     }
     return __base::begin() + __pos;
 }
@@ -2807,11 +2819,7 @@ deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
                 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
             __base::size() -= __n;
             __base::__start_ += __n;
-            while (__front_spare() >= 2 * __base::__block_size)
-            {
-                __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
-                __base::__map_.pop_front();
-                __base::__start_ -= __base::__block_size;
+            while (__maybe_remove_front_spare()) {
             }
         }
         else
@@ -2820,10 +2828,7 @@ deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
             for (iterator __e = __base::end(); __i != __e; ++__i)
                 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
             __base::size() -= __n;
-            while (__back_spare() >= 2 * __base::__block_size)
-            {
-                __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
-                __base::__map_.pop_back();
+            while (__maybe_remove_back_spare()) {
             }
         }
     }
@@ -2844,10 +2849,7 @@ deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
         for (iterator __p = __b + __pos; __p != __e; ++__p)
             __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
         __base::size() -= __n;
-        while (__back_spare() >= 2 * __base::__block_size)
-        {
-            __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
-            __base::__map_.pop_back();
+        while (__maybe_remove_back_spare()) {
         }
     }
 }
diff --git a/libcxx/test/libcxx/containers/sequences/deque/spare_block_handling.pass.cpp b/libcxx/test/libcxx/containers/sequences/deque/spare_block_handling.pass.cpp
new file mode 100644
index 00000000000..fb6c7673921
--- /dev/null
+++ b/libcxx/test/libcxx/containers/sequences/deque/spare_block_handling.pass.cpp
@@ -0,0 +1,284 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03
+
+// <deque>
+
+// Test how deque manages the spare blocks it keeps. The exact values it tests
+// for are not always important, but are sometimes needed to ensure the container
+// resizes or shrinks at the correct time.
+
+#include <deque>
+#include <iostream>
+#include <memory>
+#include <stack>
+#include <queue>
+
+#include "min_allocator.h"
+#include "rapid-cxx-test.hpp"
+
+template <class Adaptor>
+struct ContainerAdaptor : public Adaptor {
+  using Adaptor::Adaptor;
+  typename Adaptor::container_type& GetContainer() { return Adaptor::c; }
+};
+
+template <class Deque>
+static void print(const Deque& d) {
+  std::cout << d.size()
+            << " : __front_spare() == " << d.__front_spare()
+            << " : __back_spare() == " << d.__back_spare()
+            << " : __capacity() == " << d.__capacity()
+            << " : bytes allocated == "
+            << malloc_allocator_base::outstanding_bytes << '\n';
+}
+
+template <class T>
+using Deque = std::deque<T, malloc_allocator<T> >;
+
+template <class T>
+using BlockSize = std::__deque_block_size<T, std::ptrdiff_t>;
+
+struct LargeT {
+  LargeT() = default;
+  char buff[256] = {};
+};
+static_assert(BlockSize<LargeT>::value == 16, "");
+
+const auto& AllocBytes = malloc_allocator_base::outstanding_bytes;
+
+template <class DT>
+struct PrintOnFailure {
+   explicit PrintOnFailure(DT const& d) : d(&d) {}
+
+  ~PrintOnFailure() {
+    if (::rapid_cxx_test::get_reporter().current_failure().type
+        != ::rapid_cxx_test::failure_type::none) {
+      print(*d);
+    }
+  }
+private:
+  const DT* d;
+
+  PrintOnFailure(PrintOnFailure const&) = delete;
+};
+
+TEST_SUITE(deque_spare_tests)
+
+TEST_CASE(push_back) {
+  const auto BS = BlockSize<LargeT>::value;
+  std::unique_ptr<Deque<LargeT>> dp(new Deque<LargeT>);
+  auto& d = *dp;
+  PrintOnFailure<Deque<LargeT>> on_fail(d);
+
+  // Test nothing is allocated after default construction.
+  {
+    TEST_REQUIRE(d.size() == 0);
+    TEST_REQUIRE(d.__capacity() == 0);
+    TEST_REQUIRE(d.__block_count() == 0);
+  }
+  // First push back allocates one block.
+  d.push_back({});
+  {
+    TEST_REQUIRE(d.size() == 1);
+    TEST_REQUIRE(d.__front_spare() == 0);
+    TEST_REQUIRE(d.__back_spare() == 14);
+    TEST_REQUIRE(d.__back_spare_blocks() == 0);
+    TEST_REQUIRE(d.__capacity() == BS - 1);
+    TEST_REQUIRE(d.__block_count() == 1);
+  }
+
+  d.push_back({});
+  {
+    TEST_REQUIRE(d.size() == 2);
+    TEST_REQUIRE(d.__front_spare() == 0);
+    TEST_REQUIRE(d.__back_spare() == 13);
+    TEST_REQUIRE(d.__back_spare_blocks() == 0);
+  }
+  // Push back until we need a new block.
+  for (int RemainingCap = d.__capacity() - d.size(); RemainingCap >= 0; --RemainingCap)
+    d.push_back({});
+  {
+    TEST_REQUIRE(d.__block_count() == 2);
+    TEST_REQUIRE(d.__front_spare_blocks() == 0);
+    TEST_REQUIRE(d.__back_spare_blocks() == 0);
+    TEST_REQUIRE(d.__back_spare() == 15);
+  }
+
+  // Remove the only element in the new block. Test that we keep the empty
+  // block as a spare.
+  d.pop_back();
+  {
+    TEST_REQUIRE(d.__block_count() == 2);
+    TEST_REQUIRE(d.__front_spare_blocks() == 0);
+    TEST_REQUIRE(d.__back_spare_blocks() == 1);
+    TEST_REQUIRE(d.__back_spare() == 16);
+  }
+
+  // Pop back again, keep the spare.
+  d.pop_back();
+  {
+    TEST_REQUIRE(d.__block_count() == 2);
+    TEST_REQUIRE(d.__front_spare() == 0);
+    TEST_REQUIRE(d.__back_spare() == 17);
+    TEST_REQUIRE(d.__back_spare_blocks() == 1);
+  }
+
+  dp.reset();
+  TEST_REQUIRE(AllocBytes == 0);
+}
+
+TEST_CASE(push_front) {
+  std::unique_ptr<Deque<LargeT>> dp(new Deque<LargeT>);
+  auto& d = *dp;
+  PrintOnFailure<Deque<LargeT>> on_fail(d);
+
+  // Test nothing is allocated after default construction.
+  {
+    TEST_REQUIRE(d.size() == 0);
+    TEST_REQUIRE(d.__capacity() == 0);
+    TEST_REQUIRE(d.__block_count() == 0);
+  }
+  // First push front allocates one block, and we start the sequence in the
+  // middle.
+  d.push_front({});
+  {
+    TEST_REQUIRE(d.size() == 1);
+    TEST_REQUIRE(d.__front_spare() == 7);
+    TEST_REQUIRE(d.__back_spare() == 7);
+    TEST_REQUIRE(d.__front_spare_blocks() == 0);
+    TEST_REQUIRE(d.__back_spare_blocks() == 0);
+    TEST_REQUIRE(d.__block_count() == 1);
+  }
+
+  d.push_front({});
+  {
+    TEST_REQUIRE(d.size() == 2);
+    TEST_REQUIRE(d.__front_spare() == 6);
+    TEST_REQUIRE(d.__back_spare() == 7);
+    TEST_REQUIRE(d.__front_spare_blocks() == 0);
+    TEST_REQUIRE(d.__back_spare_blocks() == 0);
+  }
+  // Push front until we need a new block.
+  for (int RemainingCap = d.__front_spare(); RemainingCap >= 0; --RemainingCap)
+    d.push_front({});
+  {
+    TEST_REQUIRE(d.__block_count() == 2);
+    TEST_REQUIRE(d.__front_spare() == 15);
+    TEST_REQUIRE(d.__back_spare() == 7);
+    TEST_REQUIRE(d.__front_spare_blocks() == 0);
+    TEST_REQUIRE(d.__back_spare_blocks() == 0);
+  }
+
+  // Remove the only element in the new block. Test that we keep the empty
+  // block as a spare.
+  d.pop_front();
+  {
+    TEST_REQUIRE(d.__block_count() == 2);
+    TEST_REQUIRE(d.__front_spare_blocks() == 1);
+    TEST_REQUIRE(d.__back_spare_blocks() == 0);
+    TEST_REQUIRE(d.__back_spare() == 7);
+  }
+
+  // Pop back again, keep the spare.
+  d.pop_front();
+  {
+    TEST_REQUIRE(d.__block_count() == 2);
+    TEST_REQUIRE(d.__front_spare_blocks() == 1);
+    TEST_REQUIRE(d.__back_spare() == 7);
+  }
+
+  dp.reset();
+  TEST_REQUIRE(AllocBytes == 0);
+}
+
+TEST_CASE(std_queue) {
+  using D = Deque<LargeT>;
+  using Queue = std::queue<LargeT, D>;
+  ContainerAdaptor<Queue> CA;
+  const D& d = CA.GetContainer();
+  Queue &q = CA;
+  PrintOnFailure<Deque<LargeT>> on_fail(d);
+
+  while (d.__block_count() < 4)
+    q.push({});
+  {
+    TEST_REQUIRE(d.__block_count() == 4);
+    TEST_REQUIRE(d.__front_spare() == 0);
+    TEST_REQUIRE(d.__back_spare() == 15);
+    TEST_REQUIRE(d.__back_spare_blocks() == 0);
+  }
+  while (d.__back_spare()) {
+    q.push({});
+  }
+  {
+    TEST_REQUIRE(d.__block_count() == 4);
+    TEST_REQUIRE(d.__front_spare() == 0);
+    TEST_REQUIRE(d.__back_spare() == 0);
+  }
+  q.pop();
+  {
+    TEST_REQUIRE(d.__block_count() == 4);
+    TEST_REQUIRE(d.__front_spare() == 1);
+    TEST_REQUIRE(d.__back_spare() == 0);
+  }
+
+  // Pop until we create a spare block at the front.
+  while (d.__front_spare() <= 15)
+    q.pop();
+
+  {
+    TEST_REQUIRE(d.__block_count() == 4);
+    TEST_REQUIRE(d.__front_spare_blocks() == 1);
+    TEST_REQUIRE(d.__front_spare() == 16);
+    TEST_REQUIRE(d.__back_spare() == 0);
+  }
+
+  // Push at the end -- should re-use new spare block at front
+  q.push({});
+
+  {
+    TEST_REQUIRE(d.__block_count() == 4);
+    TEST_REQUIRE(d.__front_spare_blocks() == 0);
+    TEST_REQUIRE(d.__front_spare() == 0);
+    TEST_REQUIRE(d.__back_spare() == 15);
+  }
+  while (!q.empty()) {
+    q.pop();
+    TEST_REQUIRE(d.__front_spare_blocks() + d.__back_spare_blocks() <= 2);
+  }
+
+  // The empty state has two blocks
+  {
+    TEST_REQUIRE(d.__front_spare() == 16);
+    TEST_REQUIRE(d.__back_spare() == 15);
+    TEST_REQUIRE(d.__capacity() == 31);
+  }
+}
+
+TEST_CASE(pop_front_push_back) {
+  Deque<char> d(32 * 1024, 'a');
+  bool take_from_front = true;
+  while (d.size() > 0) {
+    if (take_from_front) {
+      d.pop_front();
+      take_from_front = false;
+    } else {
+      d.pop_back();
+      take_from_front = true;
+    }
+    if (d.size() % 1000 == 0 || d.size() < 50) {
+      print(d);
+    }
+  }
+}
+
+TEST_SUITE_END()
+
+