This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[patch] No allocation for empty unordered containers
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 03 Jun 2014 22:44:10 +0200
- Subject: [patch] No allocation for empty unordered containers
- Authentication-results: sourceware.org; auth=none
Hi
Thanks to the single bucket introduced to make move semantic
noexcept we can also avoid some over allocations. Here is a patch to
avoid any allocation on default instantiation, on range constructor when
range is empty and on construction from an initialization list when this
list is empty too. I had to make all default hint value to 0 so that if
this value is used the rehash policy next bucket returns 1 bucket.
I don't know if you had in mind to noexcept qualify the default
constructor but it would mean to have a real default constructor and
another to deal with the hint which wouldn't match the Standard so no
noexcept qualification at the moment.
Tested under Linux x86_64.normal debug and profile modes.
2014-06-03 François Dumont <fdumont@gcc.gnu.org>
* include/bits/hashtable.h: Make use of the internal single bucket to
limit allocation as long as container remains empty.
* include/bits/unordered_map.h: Set default bucket hint to 0 in
constructors to avoid allocation.
* include/bits/unordered_set.h: Likewise.
* include/debug/unordered_map: Likewise.
* include/debug/unordered_set: Likewise.
* include/profile/unordered_map: Likewise.
* include/profile/unordered_set: Likewise.
* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
Returns 1 for hint 0.
* testsuite/23_containers/unordered_map/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_multimap/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_set/allocator/
empty_instantiation.cc: New.
* testsuite/23_containers/unordered_multiset/allocator/
empty_instantiation.cc: New.
Ok to commit ?
François
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 211144)
+++ include/bits/hashtable.h (working copy)
@@ -407,12 +407,12 @@
// Use delegating constructors.
explicit
_Hashtable(const allocator_type& __a)
- : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
+ : _Hashtable(0, _H1(), _H2(), _Hash(), key_equal(),
__key_extract(), __a)
{ }
explicit
- _Hashtable(size_type __n = 10,
+ _Hashtable(size_type __n = 0,
const _H1& __hf = _H1(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -792,14 +792,18 @@
const _Equal& __eq, const _ExtractKey& __exk,
const allocator_type& __a)
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
__hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
- _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ auto __bkt_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
}
template<typename _Key, typename _Value,
@@ -815,19 +819,24 @@
const _Equal& __eq, const _ExtractKey& __exk,
const allocator_type& __a)
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
- __map_base(),
- __rehash_base(),
__hashtable_alloc(__node_alloc_type(__a)),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(0),
- _M_rehash_policy()
+ _M_single_bucket(nullptr)
{
auto __nb_elems = __detail::__distance_fw(__f, __l);
- _M_bucket_count =
+ auto __bkt_count =
_M_rehash_policy._M_next_bkt(
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
+
+ if (_M_bucket_count != __bkt_count)
+ {
+ _M_bucket_count = __bkt_count;
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ }
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -864,14 +873,15 @@
{
// Replacement allocator cannot free existing storage.
this->_M_deallocate_nodes(_M_begin());
- _M_before_begin._M_nxt = nullptr;
_M_deallocate_buckets();
- _M_buckets = nullptr;
+ __hashtable_base::operator=(__ht);
std::__alloc_on_copy(__this_alloc, __that_alloc);
- __hashtable_base::operator=(__ht);
- _M_bucket_count = __ht._M_bucket_count;
+ _M_buckets = &_M_single_bucket;
+ _M_bucket_count = 1;
+ _M_before_begin._M_nxt = nullptr;
_M_element_count = __ht._M_element_count;
_M_rehash_policy = __ht._M_rehash_policy;
+ _M_single_bucket = nullptr;
__try
{
_M_assign(__ht,
@@ -946,8 +956,14 @@
_M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
{
__bucket_type* __buckets = nullptr;
- if (!_M_buckets)
- _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+ if (_M_bucket_count != __ht._M_bucket_count)
+ {
+ // Bucket deallocation useless because per design _M_buckets
+ // can only be pointing to _M_single_bucket.
+ //_M_deallocate_buckets();
+ _M_bucket_count = __ht._M_bucket_count;
+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+ }
__try
{
@@ -1101,10 +1117,11 @@
__rehash_base(__ht),
__hashtable_alloc(
__node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
_M_assign(__ht,
[this](const __node_type* __n)
@@ -1126,14 +1143,12 @@
_M_bucket_count(__ht._M_bucket_count),
_M_before_begin(__ht._M_before_begin._M_nxt),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(__ht._M_single_bucket)
{
// 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;
- }
+ _M_buckets = &_M_single_bucket;
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
@@ -1154,10 +1169,11 @@
__map_base(__ht),
__rehash_base(__ht),
__hashtable_alloc(__node_alloc_type(__a)),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
_M_assign(__ht,
[this](const __node_type* __n)
@@ -1175,18 +1191,17 @@
__map_base(__ht),
__rehash_base(__ht),
__hashtable_alloc(__node_alloc_type(__a)),
- _M_buckets(),
- _M_bucket_count(__ht._M_bucket_count),
+ _M_buckets(&_M_single_bucket),
+ _M_bucket_count(1),
_M_element_count(__ht._M_element_count),
- _M_rehash_policy(__ht._M_rehash_policy)
+ _M_rehash_policy(__ht._M_rehash_policy),
+ _M_single_bucket(nullptr)
{
if (__ht._M_node_allocator() == this->_M_node_allocator())
{
+ _M_bucket_count = __ht._M_bucket_count;
if (__ht._M_uses_single_bucket())
- {
- _M_buckets = &_M_single_bucket;
- _M_single_bucket = __ht._M_single_bucket;
- }
+ _M_single_bucket = __ht._M_single_bucket;
else
_M_buckets = __ht._M_buckets;
@@ -1195,6 +1210,7 @@
// moved.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
__ht._M_reset();
}
else
@@ -1218,8 +1234,7 @@
~_Hashtable() noexcept
{
clear();
- if (_M_buckets)
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
}
template<typename _Key, typename _Value,
Index: include/bits/unordered_map.h
===================================================================
--- include/bits/unordered_map.h (revision 211144)
+++ include/bits/unordered_map.h (working copy)
@@ -136,7 +136,7 @@
* @param __a An allocator object.
*/
explicit
- unordered_map(size_type __n = 10,
+ unordered_map(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -848,7 +848,7 @@
* @param __a An allocator object.
*/
explicit
- unordered_multimap(size_type __n = 10,
+ unordered_multimap(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: include/bits/unordered_set.h
===================================================================
--- include/bits/unordered_set.h (revision 211144)
+++ include/bits/unordered_set.h (working copy)
@@ -129,7 +129,7 @@
* @param __a An allocator object.
*/
explicit
- unordered_set(size_type __n = 10,
+ unordered_set(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -764,7 +764,7 @@
* @param __a An allocator object.
*/
explicit
- unordered_multiset(size_type __n = 10,
+ unordered_multiset(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map (revision 211144)
+++ include/debug/unordered_map (working copy)
@@ -83,7 +83,7 @@
_Base_const_local_iterator, unordered_map> const_local_iterator;
explicit
- unordered_map(size_type __n = 10,
+ unordered_map(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -496,7 +496,7 @@
_Base_const_local_iterator, unordered_multimap> const_local_iterator;
explicit
- unordered_multimap(size_type __n = 10,
+ unordered_multimap(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set (revision 211144)
+++ include/debug/unordered_set (working copy)
@@ -83,7 +83,7 @@
_Base_const_local_iterator, unordered_set> const_local_iterator;
explicit
- unordered_set(size_type __n = 10,
+ unordered_set(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -492,7 +492,7 @@
_Base_const_local_iterator, unordered_multiset> const_local_iterator;
explicit
- unordered_multiset(size_type __n = 10,
+ unordered_multiset(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: include/profile/unordered_map
===================================================================
--- include/profile/unordered_map (revision 211144)
+++ include/profile/unordered_map (working copy)
@@ -77,7 +77,7 @@
typedef typename _Base::const_iterator const_iterator;
explicit
- unordered_map(size_type __n = 10,
+ unordered_map(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -322,7 +322,7 @@
typedef typename _Base::const_iterator const_iterator;
explicit
- unordered_multimap(size_type __n = 10,
+ unordered_multimap(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: include/profile/unordered_set
===================================================================
--- include/profile/unordered_set (revision 211144)
+++ include/profile/unordered_set (working copy)
@@ -76,7 +76,7 @@
typedef typename _Base::const_iterator const_iterator;
explicit
- unordered_set(size_type __n = 10,
+ unordered_set(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
@@ -300,7 +300,7 @@
typedef typename _Base::const_iterator const_iterator;
explicit
- unordered_multiset(size_type __n = 10,
+ unordered_multiset(size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
Index: src/c++11/hashtable_c++0x.cc
===================================================================
--- src/c++11/hashtable_c++0x.cc (revision 211144)
+++ src/c++11/hashtable_c++0x.cc (working copy)
@@ -47,7 +47,7 @@
// Optimize lookups involving the first elements of __prime_list.
// (useful to speed-up, eg, constructors)
static const unsigned char __fast_bkt[12]
- = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+ = { 1, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
if (__n <= 11)
{
Index: testsuite/23_containers/unordered_map/allocator/empty_instantiation.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/empty_instantiation.cc (revision 0)
+++ testsuite/23_containers/unordered_map/allocator/empty_instantiation.cc (working copy)
@@ -0,0 +1,98 @@
+// Copyright (C) 2013-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_map>
+#include <testsuite_allocator.h>
+#include <testsuite_hooks.h>
+
+using namespace __gnu_test;
+typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+typedef std::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
+ alloc_type> test_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Default constructor, in fact constructor with hint using default value.
+ test_type u;
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u(1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ std::pair<int, int> ints[] {};
+ // Range constructor.
+ test_type u(ints + 0, ints + 0);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ std::pair<int, int> ints[] { { 1, 1 } };
+ // Range constructor.
+ test_type u(ints + 0, ints + 1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Initializer list constructor.
+ test_type u({});
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u({ { 1, 1 } });
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
Index: testsuite/23_containers/unordered_multimap/allocator/empty_instantiation.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/empty_instantiation.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/empty_instantiation.cc (working copy)
@@ -0,0 +1,98 @@
+// Copyright (C) 2013-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_map>
+#include <testsuite_allocator.h>
+#include <testsuite_hooks.h>
+
+using namespace __gnu_test;
+typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+typedef std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>,
+ alloc_type> test_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Default constructor, in fact constructor with hint using default value.
+ test_type u;
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u(1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ std::pair<int, int> ints[] {};
+ // Range constructor.
+ test_type u(ints + 0, ints + 0);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ std::pair<int, int> ints[] { { 1, 1 } };
+ // Range constructor.
+ test_type u(ints + 0, ints + 1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Initializer list constructor.
+ test_type u({});
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u({ { 1, 1 } });
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
Index: testsuite/23_containers/unordered_multiset/allocator/empty_instantiation.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/empty_instantiation.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/empty_instantiation.cc (working copy)
@@ -0,0 +1,99 @@
+// Copyright (C) 2013-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_allocator.h>
+#include <testsuite_hooks.h>
+
+using namespace __gnu_test;
+typedef tracker_allocator<int> alloc_type;
+typedef std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+ alloc_type> test_type;
+
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Default constructor, in fact constructor with hint using default value.
+ test_type u;
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u(1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ int ints[] {};
+ // Range constructor.
+ test_type u(ints + 0, ints + 0);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ int ints[] { 1 };
+ // Range constructor.
+ test_type u(ints + 0, ints + 1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Initializer list constructor.
+ test_type u({});
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u({ 1 });
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
Index: testsuite/23_containers/unordered_set/allocator/empty_instantiation.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/empty_instantiation.cc (revision 0)
+++ testsuite/23_containers/unordered_set/allocator/empty_instantiation.cc (working copy)
@@ -0,0 +1,98 @@
+// Copyright (C) 2013-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_allocator.h>
+#include <testsuite_hooks.h>
+
+using namespace __gnu_test;
+typedef tracker_allocator<int> alloc_type;
+typedef std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+ alloc_type> test_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Default constructor, in fact constructor with hint using default value.
+ test_type u;
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u(1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ int ints[] {};
+ // Range constructor.
+ test_type u(ints + 0, ints + 0);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ int ints[] { 1 };
+ // Range constructor.
+ test_type u(ints + 0, ints + 1);
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ tracker_allocator_counter::reset();
+
+ {
+ // Initializer list constructor.
+ test_type u({});
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+
+ {
+ test_type u({ 1 });
+ }
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() != 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}