allocator.h (__shrink_to_fit): Rename to __shrink_to_fit_aux, fix.

2011-06-12  François Dumont  <francois.cppdevs@free.fr>
	    Paolo Carlini  <paolo.carlini@oracle.com>

	* include/bits/allocator.h (__shrink_to_fit): Rename to
	__shrink_to_fit_aux, fix.
	* include/bits/stl_vector.h (_M_shrink_to_fit): Declare.
	(shrink_to_fit): Use the latter.
	* include/debug/vector (shrink_to_fit): Likewise.
	* include/bits/vector.tcc (_M_shrink_to_fit): Define.
	* include/bits/stl_deque.h (_M_shrink_to_fit): Declare.
	(shrink_to_fit): Use the latter.
	* include/debug/deque (shrink_to_fit): Likewise.
	* include/bits/deque.tcc (_M_shrink_to_fit): Define.
	* include/bits/vector.tcc (vector<bool>::_M_reallocate): Add.
	* include/bits/stl_bvector.h (_M_shrink_to_fit): Declare.
	(shrink_to_fit): Use the latter.
	(reserve): Use _M_reallocate, move inline.
	(_Bvector_base<>::_S_nword): Add, use it throughout.
	* include/debug/string (shrink_to_fit): Redo.
	* include/ext/vstring.h (shrink_to_fit): Optimize.
	* include/bits/basic_string.h (shrink_to_fit): Likewise.
	* testsuite/21_strings/debug/shrink_to_fit.cc: New.
	* testsuite/23_containers/vector/debug/shrink_to_fit.cc: Likewise.
	* testsuite/23_containers/vector/debug/bool/shrink_to_fit.cc:
	Likewise.
	* testsuite/23_containers/vector/bool/capacity/shrink_to_fit.cc:
	Likewise.
	* testsuite/23_containers/deque/debug/shrink_to_fit.cc: Likewise.



Co-Authored-By: Paolo Carlini <paolo.carlini@oracle.com>

From-SVN: r174967

11 files changed, 150 insertions, 54 deletions

diff --git a/libstdc++-v3/include/bits/allocator.h b/libstdc++-v3/include/bits/allocator.h
index 7067fa0..6801950 100644
--- a/libstdc++-v3/include/bits/allocator.h
+++ b/libstdc++-v3/include/bits/allocator.h
@@ -184,18 +184,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
+  template<typename _Tp, bool
+    = __or_<is_copy_constructible<typename _Tp::value_type>,
+            is_nothrow_move_constructible<typename _Tp::value_type>>::value>
+    struct __shrink_to_fit_aux
+    { static bool _S_do_it(_Tp&) { return false; } };
+
   template<typename _Tp>
-    bool
-    __shrink_to_fit(_Tp& __v)
+    struct __shrink_to_fit_aux<_Tp, true>
     {
-      __try
-	{
-	  _Tp(__v).swap(__v);
-	  return true;
-	}
-      __catch(...)
-	{ return false; }
-    }
+      static bool
+      _S_do_it(_Tp& __c)
+      {
+	__try
+	  {
+	    _Tp(__make_move_if_noexcept_iterator(__c.begin()),
+		__make_move_if_noexcept_iterator(__c.end())).swap(__c);
+	    return true;
+	  }
+	__catch(...)
+	  { return false; }
+      }
+    };
 
   template<typename _Alloc, typename _Tp>
     class __alloctr_rebind_helper
diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index 9279a38..1022ce0 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -753,10 +753,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       shrink_to_fit()
       {
-	__try
-	  { reserve(0); }
-	__catch(...)
-	  { }
+	if (capacity() > size())
+	  {
+	    __try
+	      { reserve(0); }
+	    __catch(...)
+	      { }
+	  }
       }
 #endif
 
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 389fc80..fab7915 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -325,6 +325,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    }
 	}
     }
+
+  template <typename _Tp, typename _Alloc>
+    bool
+    deque<_Tp, _Alloc>::
+    _M_shrink_to_fit()
+    {
+      const difference_type __front_capacity
+	= (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
+      if (__front_capacity == 0)
+	return false;
+
+      const difference_type __back_capacity
+	= (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
+      if (__front_capacity + __back_capacity < _S_buffer_size())
+	return false;
+
+      return std::__shrink_to_fit_aux<deque>::_S_do_it(*this);
+    }
 #endif
 
   template <typename _Tp, typename _Alloc>
diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h
index 30e7b2d..22443f4 100644
--- a/libstdc++-v3/include/bits/stl_bvector.h
+++ b/libstdc++-v3/include/bits/stl_bvector.h
@@ -443,8 +443,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       _Bit_type*
       _M_allocate(size_t __n)
-      { return _M_impl.allocate((__n + int(_S_word_bit) - 1)
-				/ int(_S_word_bit)); }
+      { return _M_impl.allocate(_S_nword(__n)); }
 
       void
       _M_deallocate()
@@ -453,6 +452,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_impl.deallocate(_M_impl._M_start._M_p,
 			     _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
       }
+
+      static size_t
+      _S_nword(size_t __n)
+      { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
     };
 
 _GLIBCXX_END_NAMESPACE_CONTAINER
@@ -511,6 +514,7 @@ template<typename _Alloc>
   protected:
     using _Base::_M_allocate;
     using _Base::_M_deallocate;
+    using _Base::_S_nword;
     using _Base::_M_get_Bit_allocator;
 
   public:
@@ -724,7 +728,13 @@ template<typename _Alloc>
     { _M_range_check(__n); return (*this)[__n]; }
 
     void
-    reserve(size_type __n);
+    reserve(size_type __n)
+    {
+      if (__n > max_size())
+	__throw_length_error(__N("vector::reserve"));
+      if (capacity() < __n)
+	_M_reallocate(__n);
+    }
 
     reference
     front()
@@ -844,7 +854,7 @@ template<typename _Alloc>
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
     void
     shrink_to_fit()
-    { std::__shrink_to_fit(*this); }
+    { _M_shrink_to_fit(); }
 #endif
 
     void
@@ -875,13 +885,19 @@ template<typename _Alloc>
     _M_initialize(size_type __n)
     {
       _Bit_type* __q = this->_M_allocate(__n);
-      this->_M_impl._M_end_of_storage = (__q
-					 + ((__n + int(_S_word_bit) - 1)
-					    / int(_S_word_bit)));
+      this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
       this->_M_impl._M_start = iterator(__q, 0);
       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
     }
 
+    void
+    _M_reallocate(size_type __n);
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+    bool
+    _M_shrink_to_fit();
+#endif
+
     // Check whether it's an integral type.  If so, it's not an iterator.
 
     // _GLIBCXX_RESOLVE_LIB_DEFECTS
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index fab63f1..6d7a18c 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -1196,7 +1196,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**  A non-binding request to reduce memory use.  */
       void
       shrink_to_fit()
-      { std::__shrink_to_fit(*this); }
+      { _M_shrink_to_fit(); }
 #endif
 
       /**
@@ -1847,6 +1847,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Called by resize(sz).
       void
       _M_default_append(size_type __n);
+
+      bool
+      _M_shrink_to_fit();
 #endif
 
       //@{
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 4f61786..929bcbe 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -646,7 +646,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**  A non-binding request to reduce capacity() to size().  */
       void
       shrink_to_fit()
-      { std::__shrink_to_fit(*this); }
+      { _M_shrink_to_fit(); }
 #endif
 
       /**
@@ -1229,6 +1229,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Called by resize(n).
       void
       _M_default_append(size_type __n);
+
+      bool
+      _M_shrink_to_fit();
 #endif
 
       // Called by insert(p,x)
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 5b6a8d7..fd576db 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -509,6 +509,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    }
 	}
     }
+
+  template<typename _Tp, typename _Alloc>
+    bool
+    vector<_Tp, _Alloc>::
+    _M_shrink_to_fit()
+    {
+      if (capacity() == size())
+	return false;
+      return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
+    }
 #endif
 
   template<typename _Tp, typename _Alloc>
@@ -609,24 +619,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
 
   // vector<bool>
-
   template<typename _Alloc>
     void
     vector<bool, _Alloc>::
-    reserve(size_type __n)
+    _M_reallocate(size_type __n)
     {
-      if (__n > this->max_size())
-	__throw_length_error(__N("vector::reserve"));
-      if (this->capacity() < __n)
-	{
-	  _Bit_type* __q = this->_M_allocate(__n);
-	  this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
-						    iterator(__q, 0));
-	  this->_M_deallocate();
-	  this->_M_impl._M_start = iterator(__q, 0);
-	  this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1)
-					     / int(_S_word_bit));
-	}
+      _Bit_type* __q = this->_M_allocate(__n);
+      this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
+						iterator(__q, 0));
+      this->_M_deallocate();
+      this->_M_impl._M_start = iterator(__q, 0);
+      this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
     }
 
   template<typename _Alloc>
@@ -654,9 +657,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  this->_M_impl._M_finish = std::copy(__position, end(),
 					      __i + difference_type(__n));
 	  this->_M_deallocate();
-	  this->_M_impl._M_end_of_storage = (__q + ((__len
-						     + int(_S_word_bit) - 1)
-						    / int(_S_word_bit)));
+	  this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 	  this->_M_impl._M_start = iterator(__q, 0);
 	}
     }
@@ -689,10 +690,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 		__i = std::copy(__first, __last, __i);
 		this->_M_impl._M_finish = std::copy(__position, end(), __i);
 		this->_M_deallocate();
-		this->_M_impl._M_end_of_storage = (__q
-						   + ((__len
-						       + int(_S_word_bit) - 1)
-						      / int(_S_word_bit)));
+		this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 		this->_M_impl._M_start = iterator(__q, 0);
 	      }
 	  }
@@ -720,13 +718,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  *__i++ = __x;
 	  this->_M_impl._M_finish = std::copy(__position, end(), __i);
 	  this->_M_deallocate();
-	  this->_M_impl._M_end_of_storage = (__q + ((__len
-						     + int(_S_word_bit) - 1)
-						    / int(_S_word_bit)));
+	  this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 	  this->_M_impl._M_start = iterator(__q, 0);
 	}
     }
 
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  template<typename _Alloc>
+    bool
+    vector<bool, _Alloc>::
+    _M_shrink_to_fit()
+    {
+      if (capacity() - size() < int(_S_word_bit))
+	return false;
+      __try
+	{
+	  _M_reallocate(size());
+	  return true;
+	}
+      __catch(...)
+	{ return false; }
+    }
+#endif
+
 _GLIBCXX_END_NAMESPACE_CONTAINER
 } // namespace std
 
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index 749fc2e..5b6bdeb 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -277,7 +277,12 @@ namespace __debug
 #endif
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
-      using _Base::shrink_to_fit;
+      void
+      shrink_to_fit()
+      {
+	if (_Base::_M_shrink_to_fit())
+	  this->_M_invalidate_all();
+      }
 #endif
 
       using _Base::empty;
diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string
index b6d2b4b..9e0ad61 100644
--- a/libstdc++-v3/include/debug/string
+++ b/libstdc++-v3/include/debug/string
@@ -237,7 +237,20 @@ namespace __gnu_debug
     { this->resize(__n, _CharT()); }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
-    using _Base::shrink_to_fit;
+    void
+    shrink_to_fit()
+    {
+      if (capacity() > size())
+	{
+	  __try
+	    {
+	      reserve(0);
+	      this->_M_invalidate_all();
+	    }
+	  __catch(...)
+	    { }
+	}
+    }
 #endif
 
     using _Base::capacity;
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 6072515..1b80974 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -280,7 +280,15 @@ namespace __debug
 #endif
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
-      using _Base::shrink_to_fit;
+      void
+      shrink_to_fit()
+      {
+	if (_Base::_M_shrink_to_fit())
+	  {
+	    _M_guaranteed_capacity = _Base::capacity();
+	    this->_M_invalidate_all();
+	  }
+      }
 #endif
 
       size_type
diff --git a/libstdc++-v3/include/ext/vstring.h b/libstdc++-v3/include/ext/vstring.h
index a843368..b0b3e2e 100644
--- a/libstdc++-v3/include/ext/vstring.h
+++ b/libstdc++-v3/include/ext/vstring.h
@@ -465,10 +465,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       shrink_to_fit()
       {
-	__try
-	  { this->reserve(0); }
-	__catch(...)
-	  { }
+	if (capacity() > size())
+	  {
+	    __try
+	      { this->reserve(0); }
+	    __catch(...)
+	      { }
+	  }
       }
 #endif