diff mbox series

Hashtable consider all initializer_list on insertion

Message ID 32c49589-8a91-cb3f-296e-6b4ea31a417a@gmail.com
State New
Headers show
Series Hashtable consider all initializer_list on insertion | expand

Commit Message

François Dumont Sept. 1, 2020, 12:18 p.m. UTC
When I commit the small series of patches on _Hashtable I realize that I 
miss a part on the one regarding reservation management on range 
insertion. I've added a comment saying that we consider that all 
initializer_list elements will be inserted.

For the moment it is true only for assignement operator, this patch 
makes it true for constructor and insert methods. In the insert method 
we "reserve" only if container is empty cause otherwise we can't be that 
sure that all elements will be inserted even if the users made its best 
for that.

The consequence is that silly initialization in the tests are not 
working anymore.

     libstdc++: Hashtable: Consider that all initializer_list elements 
are inserted

     libstdc++-v3/ChangeLog:

             * include/bits/hashtable_policy.h 
(_Insert_base<>::_M_initialize): New.
(_Insert_base<>::insert(initializer_list<value_type>)): Adapt, use
             latter.
             * include/bits/hashtable.h
             (_Hashtable(initializer_list<value_type>, size_type, const 
_H1&,
             const key_equal&, const allocator_type&)): Likewise.
(_Hashtable<>::operator=(initializer_list<value_type>)): Likewise.
             * testsuite/23_containers/unordered_set/cons/bucket_hint.cc 
(test02):
             New.
             * testsuite/23_containers/unordered_set/init-list.cc 
(test01): Remove.
             * testsuite/23_containers/unordered_set/modifiers/insert.cc 
(test01):
             Remove.

Tested under Linux x86_64.

Ok to commit ?

François
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 07a4abe5c33..d530005f05f 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -529,9 +529,11 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 const _Hash& __hf = _Hash(),
 		 const key_equal& __eql = key_equal(),
 		 const allocator_type& __a = allocator_type())
-      : _Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
-		   __hf, __eql, __a, __unique_keys{})
-      { }
+      : _Hashtable(__bkt_count_hint, __hf, __eql, __a)
+      {
+	__alloc_node_gen_t __alloc_node_gen(*this);
+	this->_M_initialize(__l, __alloc_node_gen);
+      }
 
       _Hashtable&
       operator=(const _Hashtable& __ht);
@@ -556,14 +558,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_before_begin._M_nxt = nullptr;
 	clear();
 
-	// We consider that all elements of __l are going to be inserted.
-	auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
-
-	// Do not shrink to keep potential user reservation.
-	if (_M_bucket_count < __l_bkt_count)
-	  rehash(__l_bkt_count);
-
-	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
+	this->_M_initialize(__l, __roan);
 	return *this;
       }
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 0109ef86a7b..6ad09db10a0 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -825,6 +825,25 @@  namespace __detail
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
 			const _NodeGetter&, false_type __uks);
 
+      template<typename _NodeGetter>
+	void
+	_M_initialize(initializer_list<value_type> __l,
+		      const _NodeGetter& __node_gen)
+	{
+	  __hashtable& __h = _M_conjure_hashtable();
+
+	  // We consider that all elements of __l are going to be inserted.
+	  auto __l_bkt_count
+	    = __h._M_rehash_policy._M_bkt_for_elements(__l.size());
+
+	  // Do not shrink to keep potential user reservation.
+	  if (__h._M_bucket_count < __l_bkt_count)
+	    __h.rehash(__l_bkt_count);
+
+	  this->_M_insert_range(__l.begin(), __l.end(), __node_gen,
+				__unique_keys{});
+	}
+
     public:
       __ireturn_type
       insert(const value_type& __v)
@@ -866,7 +885,16 @@  namespace __detail
 
       void
       insert(initializer_list<value_type> __l)
-      { this->insert(__l.begin(), __l.end()); }
+      {
+	__hashtable& __h = _M_conjure_hashtable();
+	if (__h.empty())
+	  {
+	    __node_gen_type __node_gen(__h);
+	    _M_initialize(__l, __node_gen);
+	  }
+	else
+	  this->insert(__l.begin(), __l.end());
+      }
 
       template<typename _InputIterator>
 	void
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/bucket_hint.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/bucket_hint.cc
index 100eb5a27df..424e8f68c28 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/bucket_hint.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/bucket_hint.cc
@@ -23,15 +23,6 @@ 
 
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  std::unordered_set<int> a;
-  a.reserve(2);
-
-  std::unordered_set<int> b({ 0, 1, 0, 1, 0, 1, 0, 1 }, a.bucket_count());
-  VERIFY( b.bucket_count() == a.bucket_count() );
-}
-
 void test02()
 {
   std::unordered_set<int> a;
@@ -56,7 +47,6 @@  void test03()
 
 int main()
 {
-  test01();
   test02();
   test03();
   return 0;
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/init-list.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/init-list.cc
index 66efa72f262..e86f90b1361 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/init-list.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/init-list.cc
@@ -48,8 +48,27 @@  void test01()
   VERIFY(m.count(1) == 0);
 }
 
+void test02()
+{
+  unordered_set<int> u({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
+  VERIFY( u.size() == 13 );
+  VERIFY( u.count(0) == 1 );
+  VERIFY( u.count(13) == 0 );
+
+  auto bkt_count = u.bucket_count();
+  u.insert({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
+  VERIFY( u.size() == 13 );
+  VERIFY( u.bucket_count() == bkt_count );
+
+  u.clear();
+  u.insert({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
+  VERIFY( u.size() == 13 );
+  VERIFY( u.bucket_count() == bkt_count );
+}
+
 int main()
 {
   __gnu_test::set_memory_limits();
   test01();
+  test02();
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert.cc
index acf01c73b1b..7e4d3c06cb9 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert.cc
@@ -23,16 +23,6 @@ 
 
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  std::unordered_set<int> a;
-  a.reserve(2);
-
-  auto bkt_count = a.bucket_count();
-  a.insert({ 0, 1, 0, 1, 0, 1, 0, 1 });
-  VERIFY( a.bucket_count() == bkt_count );
-}
-
 void test02()
 {
   std::unordered_set<int> a;
@@ -59,7 +49,6 @@  void test03()
 
 int main()
 {
-  test01();
   test02();
   test03();
   return 0;