public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [patch] libstdc++/61143 make unordered containers usable after move
@ 2014-05-15 20:20 François Dumont
  2014-05-15 20:31 ` Paolo Carlini
  2014-05-15 20:52 ` Jonathan Wakely
  0 siblings, 2 replies; 6+ messages in thread
From: François Dumont @ 2014-05-15 20:20 UTC (permalink / raw)
  To: libstdc++, gcc-patches

[-- Attachment #1: Type: text/plain, Size: 788 bytes --]

Hi

     Here is a proposal to fix PR 61143. As explained in the PR I 
finally prefer to leave the container in a valid state that is to say 
with a non zero number of bucket, that is to say 1, after a move. This 
bucket is stored directly in the container so not allocated to leave the 
move operations noexcept qualified. With this evolution we could even 
make the default constructor noexcept but I don't think it has any interest.

2014-05-15  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.

     I run unordered containers test for the moment with no error. I 
will run the others before to commit.

François

[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 16444 bytes --]

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 210479)
+++ include/bits/hashtable.h	(working copy)
@@ -316,14 +316,37 @@
       size_type			_M_element_count;
       _RehashPolicy		_M_rehash_policy;
 
+      // A single bucket used when only need 1 bucket. After move the hashtable
+      // is left with only 1 bucket which is not allocated so that we can have a
+      // noexcept move constructor.
+      // 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;
+
       __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))
+	  return &_M_single_bucket;
 
+	return __hashtable_alloc::_M_allocate_buckets(__n);
+      }
+
       void
+      _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
+      {
+	if (__builtin_expect(__bkts == &_M_single_bucket, false))
+	  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 +726,7 @@
 
       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 +787,7 @@
       _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 +815,7 @@
 	    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 +852,9 @@
 	      {
 		// 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 +886,7 @@
 	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 +904,7 @@
 		      [&__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 +935,7 @@
       {
 	__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 +982,9 @@
     _M_reset() noexcept
     {
       _M_rehash_policy._M_reset();
-      _M_bucket_count = 0;
-      _M_buckets = nullptr;
+      _M_bucket_count = 1;
+      _M_buckets = &_M_single_bucket;
+      _M_single_bucket = nullptr;
       _M_before_begin._M_nxt = nullptr;
       _M_element_count = 0;
     }
@@ -980,12 +999,16 @@
     _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 (__builtin_expect(__ht._M_buckets != &__ht._M_single_bucket, true))
+	_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 +1042,7 @@
 	  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 +1116,18 @@
       _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 (__builtin_expect(__ht._M_buckets == &__ht._M_single_bucket, false))
+	{
+	  _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 +1170,14 @@
     {
       if (__ht._M_node_allocator() == this->_M_node_allocator())
 	{
-	  _M_buckets = __ht._M_buckets;
+	  if (__builtin_expect(__ht._M_buckets == &__ht._M_single_bucket, false))
+	    {
+	      _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.
@@ -1193,11 +1231,21 @@
       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 if any is pointing to its single bucket that can't be
+      // swapped.
+      if (_M_buckets == &__x._M_single_bucket)
+	_M_buckets = &_M_single_bucket;
+
+      if (__x._M_buckets == &_M_single_bucket)
+	__x._M_buckets = &__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 +1278,6 @@
 	       _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 +1295,6 @@
 	       _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 +1312,6 @@
 	       _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);
@@ -1311,9 +1350,6 @@
 	       _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 +1383,6 @@
 	       _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 +1977,7 @@
 	       _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 +2002,7 @@
 	  __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 +2018,7 @@
 	       _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 +2092,7 @@
 	    __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;
     }
Index: testsuite/23_containers/unordered_map/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/copy_assign.cc	(revision 210479)
+++ testsuite/23_containers/unordered_map/allocator/copy_assign.cc	(working copy)
@@ -17,6 +17,7 @@
 
 // { dg-options "-std=c++11" }
 
+#include <iostream>
 #include <unordered_map>
 #include <testsuite_hooks.h>
 #include <testsuite_allocator.h>
@@ -56,22 +57,37 @@
 void test02()
 {
   bool test __attribute__((unused)) = true;
-  typedef propagating_allocator<T, true> alloc_type;
-  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
-  test_type v1(alloc_type(1));
-  v1.emplace(std::piecewise_construct,
-	     std::make_tuple(T()), std::make_tuple(T()));
-  test_type v2(alloc_type(2));
-  v2.emplace(std::piecewise_construct,
-	     std::make_tuple(T()), std::make_tuple(T()));
-  v2 = v1;
-  VERIFY(1 == v1.get_allocator().get_personality());
-  VERIFY(1 == v2.get_allocator().get_personality());
+  {
+    typedef propagating_allocator<T, true> alloc_type;
+    typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+    std::cout << "Instantiate v1" << std::endl;
+    test_type v1(alloc_type(1));
+    std::cout << "Emplace in v1" << std::endl;
+    v1.emplace(std::piecewise_construct,
+	       std::make_tuple(T()), std::make_tuple(T()));
+    {
+      std::cout << "Instantiate v2" << std::endl;
+      test_type v2(alloc_type(2));
+      std::cout << "Emplace in v2" << std::endl;
+      v2.emplace(std::piecewise_construct,
+		 std::make_tuple(T()), std::make_tuple(T()));
+      std::cout << "v2 = v1" << std::endl;  
+      v2 = v1;
+      std::cout << "Done" << std::endl;
+      VERIFY(1 == v1.get_allocator().get_personality());
+      VERIFY(1 == v2.get_allocator().get_personality());
+    }
+    std::cout << "v2 destroyed" << std::endl;
+  }
+  std::cout << "v1 destroyed" << std::endl;
 }
 
 int main()
 {
+  std::cout << "Running test01" << std::endl;
   test01();
+  std::cout << "Running test02" << std::endl;
   test02();
+  std::cout << "Done" << std::endl;
   return 0;
 }
Index: testsuite/23_containers/unordered_set/61143.cc
===================================================================
--- testsuite/23_containers/unordered_set/61143.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/61143.cc	(working copy)
@@ -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;
+}
Index: testsuite/Makefile.in
===================================================================
--- testsuite/Makefile.in	(revision 210479)
+++ testsuite/Makefile.in	(working copy)
@@ -1,9 +1,9 @@
-# Makefile.in generated by automake 1.11.1 from Makefile.am.
+# Makefile.in generated by automake 1.11.6 from Makefile.am.
 # @configure_input@
 
 # Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002,
-# 2003, 2004, 2005, 2006, 2007, 2008, 2009  Free Software Foundation,
-# Inc.
+# 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software
+# Foundation, Inc.
 # This Makefile.in is free software; the Free Software Foundation
 # gives unlimited permission to copy and/or distribute it,
 # with or without modifications, as long as this notice is preserved.
@@ -15,6 +15,23 @@
 
 @SET_MAKE@
 VPATH = @srcdir@
+am__make_dryrun = \
+  { \
+    am__dry=no; \
+    case $$MAKEFLAGS in \
+      *\\[\ \	]*) \
+        echo 'am--echo: ; @echo "AM"  OK' | $(MAKE) -f - 2>/dev/null \
+          | grep '^AM OK$$' >/dev/null || am__dry=yes;; \
+      *) \
+        for am__flg in $$MAKEFLAGS; do \
+          case $$am__flg in \
+            *=*|--*) ;; \
+            *n*) am__dry=yes; break;; \
+          esac; \
+        done;; \
+    esac; \
+    test $$am__dry = yes; \
+  }
 pkgdatadir = $(datadir)/@PACKAGE@
 pkgincludedir = $(includedir)/@PACKAGE@
 pkglibdir = $(libdir)/@PACKAGE@
@@ -67,6 +84,11 @@
 depcomp =
 am__depfiles_maybe =
 SOURCES =
+am__can_run_installinfo = \
+  case $$AM_UPDATE_INFO_DIR in \
+    n|no|NO) false;; \
+    *) (install-info --version) >/dev/null 2>&1;; \
+  esac
 ABI_TWEAKS_SRCDIR = @ABI_TWEAKS_SRCDIR@
 ACLOCAL = @ACLOCAL@
 ALLOCATOR_H = @ALLOCATOR_H@
@@ -360,6 +382,7 @@
 	    echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \
 	    cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \
 	esac;
+$(top_srcdir)/fragment.am:
 
 $(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES)
 	cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh
@@ -395,10 +418,15 @@
 
 installcheck: installcheck-am
 install-strip:
-	$(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
-	  install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
-	  `test -z '$(STRIP)' || \
-	    echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install
+	if test -z '$(STRIP)'; then \
+	  $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+	    install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
+	      install; \
+	else \
+	  $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+	    install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
+	    "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \
+	fi
 mostlyclean-generic:
 
 clean-generic:

^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2014-05-20 20:37 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-05-15 20:20 [patch] libstdc++/61143 make unordered containers usable after move François Dumont
2014-05-15 20:31 ` Paolo Carlini
2014-05-15 20:52 ` Jonathan Wakely
2014-05-19 20:27   ` François Dumont
2014-05-20 19:36     ` Jonathan Wakely
2014-05-20 20:37       ` François Dumont

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).