* [PATCH] Hashtable consider all initializer_list on insertion
@ 2020-09-01 12:18 François Dumont
0 siblings, 0 replies; only message in thread
From: François Dumont @ 2020-09-01 12:18 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1641 bytes --]
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
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 5173 bytes --]
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;
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2020-09-01 12:18 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-09-01 12:18 [PATCH] Hashtable consider all initializer_list on insertion 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).