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.
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@367631 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/deque b/include/deque
index d3ccf2e..fe988d0 100644
--- a/include/deque
+++ b/include/deque
@@ -934,7 +934,7 @@
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 @@
_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 @@
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 @@
}
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 @@
__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 @@
__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 @@
__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 @@
__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 @@
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 @@
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/test/libcxx/containers/sequences/deque/spare_block_handling.pass.cpp b/test/libcxx/containers/sequences/deque/spare_block_handling.pass.cpp
new file mode 100644
index 0000000..fb6c767
--- /dev/null
+++ b/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()
+
+
