2014-05-23 François Dumont <fdumont@gcc.gnu.org>

	PR libstdc++/61143
	* include/bits/hashtable.h: Fix move semantic to leave hashtable in a
	usable state.
	* testsuite/23_containers/unordered_set/61143.cc: New.
	* testsuite/23_containers/unordered_set/modifiers/swap.cc: New.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/gcc-4_9-branch@210876 138bc75d-0d04-0410-961f-82ee72b054a4

4 files changed, 210 insertions, 47 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index b0f3f7a0af8..dbb82fda492 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,11 @@
+2014-05-23  François Dumont  <fdumont@gcc.gnu.org>
+
+	PR libstdc++/61143
+	* include/bits/hashtable.h: Fix move semantic to leave hashtable in a
+	usable state.
+	* testsuite/23_containers/unordered_set/61143.cc: New.
+	* testsuite/23_containers/unordered_set/modifiers/swap.cc: New.
+
 2014-05-17  Jonathan Wakely  <jwakely@redhat.com>
 
 	PR libstdc++/60966
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 22e17d29d7b..9b6394c4e49 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -316,14 +316,49 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       size_type			_M_element_count;
       _RehashPolicy		_M_rehash_policy;
 
+      // A single bucket used when only need for 1 bucket. Especially
+      // interesting in move semantic to leave hashtable with only 1 buckets
+      // which is not allocated so that we can have those operations noexcept
+      // qualified.
+      // Note that we can't leave hashtable with 0 bucket without adding
+      // numerous checks in the code to avoid 0 modulus.
+      __bucket_type		_M_single_bucket;
+
+      bool
+      _M_uses_single_bucket(__bucket_type* __bkts) const
+      { return __builtin_expect(_M_buckets == &_M_single_bucket, false); }
+
+      bool
+      _M_uses_single_bucket() const
+      { return _M_uses_single_bucket(_M_buckets); }
+
       __hashtable_alloc&
       _M_base_alloc() { return *this; }
 
-      using __hashtable_alloc::_M_deallocate_buckets;
+      __bucket_type*
+      _M_allocate_buckets(size_type __n)
+      {
+	if (__builtin_expect(__n == 1, false))
+	  {
+	    _M_single_bucket = nullptr;
+	    return &_M_single_bucket;
+	  }
+
+	return __hashtable_alloc::_M_allocate_buckets(__n);
+      }
+
+      void
+      _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
+      {
+	if (_M_uses_single_bucket(__bkts))
+	  return;
+
+	__hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
+      }
 
       void
       _M_deallocate_buckets()
-      { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+      { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
 
       // Gets bucket begin, deals with the fact that non-empty buckets contain
       // their before begin node.
@@ -703,11 +738,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       size_type
       erase(const key_type& __k)
-      {
-	if (__builtin_expect(_M_bucket_count == 0, false))
-	  return 0;
-	return _M_erase(__unique_keys(), __k);
-      }
+      { return _M_erase(__unique_keys(), __k); }
 
       iterator
       erase(const_iterator, const_iterator);
@@ -768,7 +799,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_rehash_policy()
     {
       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
-      _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+      _M_buckets = _M_allocate_buckets(_M_bucket_count);
     }
 
   template<typename _Key, typename _Value,
@@ -796,7 +827,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
 		     __bucket_hint));
 
-	_M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+	_M_buckets = _M_allocate_buckets(_M_bucket_count);
 	__try
 	  {
 	    for (; __f != __l; ++__f)
@@ -833,9 +864,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      {
 		// Replacement allocator cannot free existing storage.
 		this->_M_deallocate_nodes(_M_begin());
-		if (__builtin_expect(_M_bucket_count != 0, true))
-		  _M_deallocate_buckets();
-		_M_reset();
+		_M_before_begin._M_nxt = nullptr;
+		_M_deallocate_buckets();
+		_M_buckets = nullptr;
 		std::__alloc_on_copy(__this_alloc, __that_alloc);
 		__hashtable_base::operator=(__ht);
 		_M_bucket_count = __ht._M_bucket_count;
@@ -867,7 +898,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	if (_M_bucket_count != __ht._M_bucket_count)
 	  {
 	    __former_buckets = _M_buckets;
-	    _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+	    _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
 	    _M_bucket_count = __ht._M_bucket_count;
 	  }
 	else
@@ -885,8 +916,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		      [&__roan](const __node_type* __n)
 		      { return __roan(__n->_M_v()); });
 	    if (__former_buckets)
-	      this->_M_deallocate_buckets(__former_buckets,
-					  __former_bucket_count);
+	      _M_deallocate_buckets(__former_buckets, __former_bucket_count);
 	  }
 	__catch(...)
 	  {
@@ -917,7 +947,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       {
 	__bucket_type* __buckets = nullptr;
 	if (!_M_buckets)
-	  _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count);
+	  _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
 
 	__try
 	  {
@@ -964,8 +994,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_reset() noexcept
     {
       _M_rehash_policy._M_reset();
-      _M_bucket_count = 0;
-      _M_buckets = nullptr;
+      _M_bucket_count = 1;
+      _M_single_bucket = nullptr;
+      _M_buckets = &_M_single_bucket;
       _M_before_begin._M_nxt = nullptr;
       _M_element_count = 0;
     }
@@ -980,12 +1011,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_move_assign(_Hashtable&& __ht, std::true_type)
     {
       this->_M_deallocate_nodes(_M_begin());
-      if (__builtin_expect(_M_bucket_count != 0, true))
-	_M_deallocate_buckets();
-
+      _M_deallocate_buckets();
       __hashtable_base::operator=(std::move(__ht));
       _M_rehash_policy = __ht._M_rehash_policy;
-      _M_buckets = __ht._M_buckets;
+      if (!__ht._M_uses_single_bucket())
+	_M_buckets = __ht._M_buckets;
+      else
+	{
+	  _M_buckets = &_M_single_bucket;
+	  _M_single_bucket = __ht._M_single_bucket;
+	}
       _M_bucket_count = __ht._M_bucket_count;
       _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
       _M_element_count = __ht._M_element_count;
@@ -1019,7 +1054,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  if (_M_bucket_count != __ht._M_bucket_count)
 	    {
 	      __former_buckets = _M_buckets;
-	      _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+	      _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
 	      _M_bucket_count = __ht._M_bucket_count;
 	    }
 	  else
@@ -1093,10 +1128,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
     {
+      // Update, if necessary, buckets if __ht is using its single bucket.
+      if (__ht._M_uses_single_bucket())
+	{
+	  _M_buckets = &_M_single_bucket;
+	  _M_single_bucket = __ht._M_single_bucket;
+	}
+
       // Update, if necessary, bucket pointing to before begin that hasn't
       // moved.
       if (_M_begin())
 	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
       __ht._M_reset();
     }
 
@@ -1139,7 +1182,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       if (__ht._M_node_allocator() == this->_M_node_allocator())
 	{
-	  _M_buckets = __ht._M_buckets;
+	  if (__ht._M_uses_single_bucket())
+	    {
+	      _M_buckets = &_M_single_bucket;
+	      _M_single_bucket = __ht._M_single_bucket;
+	    }
+	  else
+	    _M_buckets = __ht._M_buckets;
+
 	  _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
 	  // Update, if necessary, bucket pointing to before begin that hasn't
 	  // moved.
@@ -1189,15 +1239,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
       std::swap(_M_rehash_policy, __x._M_rehash_policy);
-      std::swap(_M_buckets, __x._M_buckets);
+
+      // Deal properly with potentially moved instances.
+      if (this->_M_uses_single_bucket())
+	{
+	  if (!__x._M_uses_single_bucket())
+	    {
+	      _M_buckets = __x._M_buckets;
+	      __x._M_buckets = &__x._M_single_bucket;
+	    }
+	}
+      else if (__x._M_uses_single_bucket())
+	{
+	  __x._M_buckets = _M_buckets;
+	  _M_buckets = &_M_single_bucket;
+	}	
+      else
+	std::swap(_M_buckets, __x._M_buckets);
+
       std::swap(_M_bucket_count, __x._M_bucket_count);
       std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
       std::swap(_M_element_count, __x._M_element_count);
+      std::swap(_M_single_bucket, __x._M_single_bucket);
 
       // Fix buckets containing the _M_before_begin pointers that can't be
       // swapped.
       if (_M_begin())
 	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
       if (__x._M_begin())
 	__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
 	  = &__x._M_before_begin;
@@ -1230,9 +1299,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     find(const key_type& __k)
     {
-      if (__builtin_expect(_M_bucket_count == 0, false))
-	return end();
-
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_find_node(__n, __k, __code);
@@ -1250,9 +1316,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     find(const key_type& __k) const
     {
-      if (__builtin_expect(_M_bucket_count == 0, false))
-	return end();
-      
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_find_node(__n, __k, __code);
@@ -1270,9 +1333,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     count(const key_type& __k) const
     {
-      if (__builtin_expect(_M_bucket_count == 0, false))
-	return 0;
-
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_bucket_begin(__n);
@@ -1287,7 +1347,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  else if (__result)
 	    // All equivalent values are next to each other, if we
 	    // found a non-equivalent value after an equivalent one it
-	    // means that we won't find any more equivalent values.
+	    // means that we won't find any new equivalent value.
 	    break;
 	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
 	    break;
@@ -1311,9 +1371,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     equal_range(const key_type& __k)
     {
-      if (__builtin_expect(_M_bucket_count == 0, false))
-	return std::make_pair(end(), end());
-
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_find_node(__n, __k, __code);
@@ -1347,9 +1404,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     equal_range(const key_type& __k) const
     {
-      if (__builtin_expect(_M_bucket_count == 0, false))
-	return std::make_pair(end(), end());
-	
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_find_node(__n, __k, __code);
@@ -1944,7 +1998,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_rehash_aux(size_type __n, std::true_type)
     {
-      __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+      __bucket_type* __new_buckets = _M_allocate_buckets(__n);
       __node_type* __p = _M_begin();
       _M_before_begin._M_nxt = nullptr;
       std::size_t __bbegin_bkt = 0;
@@ -1969,8 +2023,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  __p = __next;
 	}
 
-      if (__builtin_expect(_M_bucket_count != 0, true))
-	_M_deallocate_buckets();
+      _M_deallocate_buckets();
       _M_bucket_count = __n;
       _M_buckets = __new_buckets;
     }
@@ -1986,7 +2039,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_rehash_aux(size_type __n, std::false_type)
     {
-      __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+      __bucket_type* __new_buckets = _M_allocate_buckets(__n);
 
       __node_type* __p = _M_begin();
       _M_before_begin._M_nxt = nullptr;
@@ -2060,8 +2113,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    __new_buckets[__next_bkt] = __prev_p;
 	}
 
-      if (__builtin_expect(_M_bucket_count != 0, true))
-	_M_deallocate_buckets();
+      _M_deallocate_buckets();
       _M_bucket_count = __n;
       _M_buckets = __new_buckets;
     }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/61143.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/61143.cc
new file mode 100644
index 00000000000..b9464254f12
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/61143.cc
@@ -0,0 +1,38 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/61143
+
+#include <unordered_set>
+
+void test01()
+{
+  std::unordered_set<int> us1, us2;
+  us1.insert(1);
+
+  us2 = std::move(us1);
+
+  us1.insert(1);
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/swap.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/swap.cc
new file mode 100644
index 00000000000..d03fd1dc3b1
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/swap.cc
@@ -0,0 +1,65 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  std::unordered_set<int> us1 { 0, 1 };
+  {
+    std::unordered_set<int> us2(std::move(us1));
+
+    us1.swap(us2);
+
+    VERIFY( us1.find(0) != us1.end() );
+
+    us1.insert(2);
+
+    VERIFY( us1.size() == 3 );
+
+    us2.swap(us1);
+
+    VERIFY( us2.size() == 3 );
+    VERIFY( us2.find(2) != us2.end() );
+
+    us1 = { 3, 4, 5 };
+
+    VERIFY( us1.size() == 3 );
+    VERIFY( us1.bucket_count() >= 3 );
+
+    std::unordered_set<int> us3(std::move(us1));
+    us3 = std::move(us2);
+
+    us1.swap(us2);
+
+    VERIFY( us1.empty() );
+    VERIFY( us2.empty() );
+  }
+
+  us1 = { 0, 1 };
+  VERIFY( us1.size() == 2 );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}