From 4dad8b49ee0f90c4960e86dedc9337c6d1be01db Mon Sep 17 00:00:00 2001 From: Benjamin Kosnik Date: Fri, 13 Apr 2012 00:33:10 +0000 Subject: [PATCH] unordered_map.h (__unordered_map): Remove. 2012-04-12 Benjamin Kosnik * include/bits/unordered_map.h (__unordered_map): Remove. (__unordered_multimap): Remove. Add aliases for __umap_traits, __umap_hashtable, __ummap_traits, __ummap_hashtable. (unordered_map): Derive from __umap_hashtable. (unordered_multimap): Derive from __ummap_hashtable. * include/bits/unordered_set.h (__unordered_set): Remove. (__unordered_multiset): Remove. Add aliases for __uset_traits, __uset_hashtable, __umset_traits, __umset_hashtable. (unordered_set): Derive from __uset_hashtable. (unordered_multiset): Derive from __umset_hashtable. * include/bits/hashtable.h (__cache_default): New, consolidated cache defaults for _Hashtable. Adjust comments for doxygen. (_Hashtable): Consolidate bool template parameters into new, _Traits class. Inherited base classes synthesize _Hashtable in CRTP via original 10 parameters. Prefer using declarations to typedefs, add __node_type, __bucket_type, etc. Push many nested types down hierarchy to _Hashtable_base. Add constructors necessary for top-level unordered_containers. Consolidate insert member functions and logic in new base class, __detail::_Insert and __detail::_Insert_base. (_Hashtable::operator=(initializer_list)): Add. * include/bits/hashtable_policy.h: Convert to doxygen markup. (_Hashtable_traits) New. Consolidate bool template parameters here. (_Insert, _Insert_base): New, consolidated insert member functions. (_Map_base, _Equality, _Rehash_base): Adjust template parameters, use base types. (_Hashtable_base): Move type declarations useful to other base classes into this class. * python/libstdcxx/v6/printers.py (Tr1HashtableIterator): Update. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust traits, line numbers. From-SVN: r186403 --- libstdc++-v3/ChangeLog | 36 + libstdc++-v3/include/bits/hashtable.h | 1315 +++++++++-------- libstdc++-v3/include/bits/hashtable_policy.h | 1097 ++++++++++---- libstdc++-v3/include/bits/unordered_map.h | 315 +--- libstdc++-v3/include/bits/unordered_set.h | 325 +--- libstdc++-v3/python/libstdcxx/v6/printers.py | 2 +- .../unordered_set/instantiation_neg.cc | 13 +- 7 files changed, 1629 insertions(+), 1474 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 11f4b7c5c1d9..eb9936f423ba 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,39 @@ +2012-04-12 Benjamin Kosnik + + * include/bits/unordered_map.h (__unordered_map): Remove. + (__unordered_multimap): Remove. + Add aliases for __umap_traits, __umap_hashtable, __ummap_traits, + __ummap_hashtable. + (unordered_map): Derive from __umap_hashtable. + (unordered_multimap): Derive from __ummap_hashtable. + * include/bits/unordered_set.h (__unordered_set): Remove. + (__unordered_multiset): Remove. + Add aliases for __uset_traits, __uset_hashtable, __umset_traits, + __umset_hashtable. + (unordered_set): Derive from __uset_hashtable. + (unordered_multiset): Derive from __umset_hashtable. + * include/bits/hashtable.h (__cache_default): New, consolidated + cache defaults for _Hashtable. Adjust comments for doxygen. + (_Hashtable): Consolidate bool template parameters into new, + _Traits class. Inherited base classes synthesize _Hashtable in + CRTP via original 10 parameters. Prefer using declarations to + typedefs, add __node_type, __bucket_type, etc. Push many nested + types down hierarchy to _Hashtable_base. Add constructors + necessary for top-level unordered_containers. Consolidate insert + member functions and logic in new base class, __detail::_Insert + and __detail::_Insert_base. + (_Hashtable::operator=(initializer_list)): Add. + * include/bits/hashtable_policy.h: Convert to doxygen markup. + (_Hashtable_traits) New. Consolidate bool template parameters here. + (_Insert, _Insert_base): New, consolidated insert member functions. + (_Map_base, _Equality, _Rehash_base): Adjust template parameters, + use base types. + (_Hashtable_base): Move type declarations useful to other base + classes into this class. + * python/libstdcxx/v6/printers.py (Tr1HashtableIterator): Update. + * testsuite/23_containers/unordered_set/instantiation_neg.cc: + Adjust traits, line numbers. + 2012-04-12 Jeffrey Yasskin PR libstdc++/52822 diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 41418a8a5094..8c17035b5c8b 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1,6 +1,7 @@ // hashtable.h header -*- C++ -*- -// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 +// 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 @@ -38,254 +39,305 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION - // Class template _Hashtable, class definition. + template + using __cache_default = __not_<__and_, + is_empty<_Hash>, + integral_constant, + __detail::__is_noexcept_hash<_Tp, _Hash> >>; - // Meaning of class template _Hashtable's template parameters - - // _Key and _Value: arbitrary CopyConstructible types. - - // _Allocator: an allocator type ([lib.allocator.requirements]) whose - // value type is Value. As a conforming extension, we allow for - // value type != Value. - - // _ExtractKey: function object that takes an object of type Value - // and returns a value of type _Key. - - // _Equal: function object that takes two objects of type k and returns - // a bool-like value that is true if the two objects are considered equal. - - // _H1: the hash function. A unary function object with argument type - // Key and result type size_t. Return values should be distributed - // over the entire range [0, numeric_limits:::max()]. - - // _H2: the range-hashing function (in the terminology of Tavori and - // Dreizin). A binary function object whose argument types and result - // type are all size_t. Given arguments r and N, the return value is - // in the range [0, N). - - // _Hash: the ranged hash function (Tavori and Dreizin). A binary function - // whose argument types are _Key and size_t and whose result type is - // size_t. Given arguments k and N, the return value is in the range - // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other - // than the default, _H1 and _H2 are ignored. - - // _RehashPolicy: Policy class with three members, all of which govern - // the bucket count. _M_next_bkt(n) returns a bucket count no smaller - // than n. _M_bkt_for_elements(n) returns a bucket count appropriate - // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) - // determines whether, if the current bucket count is n_bkt and the - // current element count is n_elt, we need to increase the bucket - // count. If so, returns make_pair(true, n), where n is the new - // bucket count. If not, returns make_pair(false, ). - - // __cache_hash_code: bool. true if we store the value of the hash - // function along with the value. This is a time-space tradeoff. - // Storing it may improve lookup speed by reducing the number of times - // we need to call the Equal function. - - // __constant_iterators: bool. true if iterator and const_iterator are - // both constant iterator types. This is true for unordered_set and - // unordered_multiset, false for unordered_map and unordered_multimap. - - // __unique_keys: bool. true if the return value of _Hashtable::count(k) - // is always at most one, false if it may be an arbitrary number. This - // true for unordered_set and unordered_map, false for unordered_multiset - // and unordered_multimap. /** - * Here's _Hashtable data structure, each _Hashtable has: - * - _Bucket[] _M_buckets - * - _Hash_node_base _M_before_begin - * - size_type _M_bucket_count - * - size_type _M_element_count + * Primary class template _Hashtable. + * + * @ingroup hashtable-detail + * + * @tparam _Value CopyConstructible type. + * + * @tparam _Key CopyConstructible type. + * + * @tparam _Alloc An allocator type + * ([lib.allocator.requirements]) whose _Alloc::value_type is + * _Value. As a conforming extension, we allow for + * _Alloc::value_type != _Value. + * + * @tparam _ExtractKey Function object that takes an object of type + * _Value and returns a value of type _Key. + * + * @tparam _Equal Function object that takes two objects of type k + * and returns a bool-like value that is true if the two objects + * are considered equal. + * + * @tparam _H1 The hash function. A unary function object with + * argument type _Key and result type size_t. Return values should + * be distributed over the entire range [0, numeric_limits:::max()]. + * + * @tparam _H2 The range-hashing function (in the terminology of + * Tavori and Dreizin). A binary function object whose argument + * types and result type are all size_t. Given arguments r and N, + * the return value is in the range [0, N). + * + * @tparam _Hash The ranged hash function (Tavori and Dreizin). A + * binary function whose argument types are _Key and size_t and + * whose result type is size_t. Given arguments k and N, the + * return value is in the range [0, N). Default: hash(k, N) = + * h2(h1(k), N). If _Hash is anything other than the default, _H1 + * and _H2 are ignored. + * + * @tparam _RehashPolicy Policy class with three members, all of + * which govern the bucket count. _M_next_bkt(n) returns a bucket + * count no smaller than n. _M_bkt_for_elements(n) returns a + * bucket count appropriate for an element count of n. + * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the + * current bucket count is n_bkt and the current element count is + * n_elt, we need to increase the bucket count. If so, returns + * make_pair(true, n), where n is the new bucket count. If not, + * returns make_pair(false, ) + * + * @tparam _Traits Compile-time class with three boolean + * std::integral_constant members: __cache_hash_code, __constant_iterators, + * __unique_keys. * - * with _Bucket being _Hash_node* and _Hash_node constaining: - * - _Hash_node* _M_next - * - Tp _M_value - * - size_t _M_code if cache_hash_code is true + * Each _Hashtable data structure has: * - * In terms of Standard containers the hastable is like the aggregation of: - * - std::forward_list<_Node> containing the elements - * - std::vector::iterator> representing the buckets + * - _Bucket[] _M_buckets + * - _Hash_node_base _M_before_begin + * - size_type _M_bucket_count + * - size_type _M_element_count * - * The non-empty buckets contain the node before the first bucket node. This - * design allow to implement something like a std::forward_list::insert_after - * on container insertion and std::forward_list::erase_after on container - * erase calls. _M_before_begin is equivalent to - * std::foward_list::before_begin. Empty buckets are containing nullptr. - * Note that one of the non-empty bucket contains &_M_before_begin which is - * not a derefenrenceable node so the node pointers in buckets shall never be - * derefenrenced, only its next node can be. - * - * Walk through a bucket nodes require a check on the hash code to see if the - * node is still in the bucket. Such a design impose a quite efficient hash - * functor and is one of the reasons it is highly advise to set - * __cache_hash_code to true. + * with _Bucket being _Hash_node* and _Hash_node constaining: * - * The container iterators are simply built from nodes. This way incrementing - * the iterator is perfectly efficient independent of how many empty buckets - * there are in the container. + * - _Hash_node* _M_next + * - Tp _M_value + * - size_t _M_code if cache_hash_code is true * - * On insert we compute element hash code and thanks to it find the bucket - * index. If the element must be inserted on an empty bucket we add it at the - * beginning of the singly linked list and make the bucket point to - * _M_before_begin. The bucket that used to point to _M_before_begin, if any, - * is updated to point to its new before begin node. + * In terms of Standard containers the hastable is like the aggregation of: * - * On erase, the simple iterator design impose to use the hash functor to get - * the index of the bucket to update. For this reason, when __cache_hash_code - * is set to false, there is a static assertion that the hash functor cannot - * throw. + * - std::forward_list<_Node> containing the elements + * - std::vector::iterator> representing the buckets + * + * The non-empty buckets contain the node before the first bucket + * node. This design allow to implement something like a + * std::forward_list::insert_after on container insertion and + * std::forward_list::erase_after on container erase + * calls. _M_before_begin is equivalent to + * std::foward_list::before_begin. Empty buckets are containing + * nullptr. Note that one of the non-empty bucket contains + * &_M_before_begin which is not a derefenrenceable node so the + * node pointers in buckets shall never be derefenrenced, only its + * next node can be. + * + * Walk through a bucket nodes require a check on the hash code to + * see if the node is still in the bucket. Such a design impose a + * quite efficient hash functor and is one of the reasons it is + * highly advise to set __cache_hash_code to true. + * + * The container iterators are simply built from nodes. This way + * incrementing the iterator is perfectly efficient independent of + * how many empty buckets there are in the container. + * + * On insert we compute element hash code and thanks to it find the + * bucket index. If the element must be inserted on an empty bucket + * we add it at the beginning of the singly linked list and make the + * bucket point to _M_before_begin. The bucket that used to point to + * _M_before_begin, if any, is updated to point to its new before + * begin node. + * + * On erase, the simple iterator design impose to use the hash + * functor to get the index of the bucket to update. For this + * reason, when __cache_hash_code is set to false, there is a static + * assertion that the hash functor cannot throw. + * + * Functionality is implemented by decomposition into base classes, + * where the derived _Hashtable class is used in _Map_base, + * _Insert, _Rehash_base, and _Equality base classes to access the + * "this" pointer. _Hashtable_base is used in the base classes as a + * non-recursive, fully-completed-type so that detailed nested type + * information, such as iterator type and node type, can be + * used. This is similar to the "Curiously Recurring Template + * Pattern" (CRTP) technique, but uses a reconstructed, not + * explicitly passed, template pattern. + * + * Base class templates are: + * __detail::_Hashtable_base + * __detail::_Map_base + * __detail::_Insert + * __detail::_Rehash_base + * __detail::_Equality */ - - template + typename _RehashPolicy, typename _Traits> class _Hashtable - : public __detail::_Rehash_base<_RehashPolicy, - _Hashtable<_Key, _Value, _Allocator, - _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, - __cache_hash_code, - __constant_iterators, - __unique_keys> >, - public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __cache_hash_code>, - public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, - _Hashtable<_Key, _Value, _Allocator, - _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, - __cache_hash_code, - __constant_iterators, - __unique_keys> >, - public __detail::_Equality_base<_ExtractKey, __unique_keys, - _Hashtable<_Key, _Value, _Allocator, - _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, - __cache_hash_code, - __constant_iterators, - __unique_keys> > + : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, _Traits>, + public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>, + public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>, + public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>, + public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits> { + public: + typedef _Key key_type; + typedef _Value value_type; + typedef _Alloc allocator_type; + typedef _Equal key_equal; + + // mapped_type, if present, comes from _Map_base. + // hasher, if present, comes from _Hash_code_base/_Hashtable_base. + typedef typename _Alloc::pointer pointer; + typedef typename _Alloc::const_pointer const_pointer; + typedef typename _Alloc::reference reference; + typedef typename _Alloc::const_reference const_reference; + + private: + using __rehash_type = _RehashPolicy; + using __rehash_state = typename __rehash_type::_State; + + using __traits_type = _Traits; + using __hash_cached = typename __traits_type::__hash_cached; + using __constant_iterators = typename __traits_type::__constant_iterators; + using __unique_keys = typename __traits_type::__unique_keys; + + using __key_extract = typename std::conditional< + __constant_iterators::value, + std::_Identity, + std::_Select1st>::type; + + using __hashtable_base = __detail:: + _Hashtable_base<_Key, _Value, _ExtractKey, + _Equal, _H1, _H2, _Hash, _Traits>; + + using __hash_code_base = typename __hashtable_base::__hash_code_base; + using __hash_code = typename __hashtable_base::__hash_code; + using __node_type = typename __hashtable_base::__node_type; + using __node_base = typename __hashtable_base::__node_base; + using __bucket_type = typename __hashtable_base::__bucket_type; + using __ireturn_type = typename __hashtable_base::__ireturn_type; + using __iconv_type = typename __hashtable_base::__iconv_type; + + using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + + using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc, + _ExtractKey, _Equal, + _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + + using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + + // Metaprogramming for picking apart hash caching. + using __hash_noexcept = __detail::__is_noexcept_hash<_Key, _H1>; + template - using __if_hash_code_cached - = __or_<__not_>, _Cond>; + using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>; template - using __if_hash_code_not_cached - = __or_, _Cond>; - - // When hash codes are not cached the hash functor shall not throw - // because it is used in methods (erase, swap...) that shall not throw. - static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key, - _H1>>::value, - "Cache the hash code or qualify your hash functor with noexcept"); - - // Following two static assertions are necessary to guarantee that - // swapping two hashtable instances won't invalidate associated local - // iterators. - - // When hash codes are cached local iterator only uses H2 which must then - // be empty. - static_assert(__if_hash_code_cached>::value, - "Functor used to map hash code to bucket index must be empty"); - - typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, - __cache_hash_code> _HCBase; - - // When hash codes are not cached local iterator is going to use _HCBase - // above to compute node bucket index so it has to be empty. - static_assert(__if_hash_code_not_cached>::value, - "Cache the hash code or make functors involved in hash code" - " and bucket index computation empty"); + using __if_hash_not_cached = __or_<__hash_cached, _Cond>; + + // Compile-time diagnostics. + + // When hash codes are not cached the hash functor shall not + // throw because it is used in methods (erase, swap...) that + // shall not throw. + static_assert(__if_hash_not_cached<__hash_noexcept>::value, + "Cache the hash code" + " or qualify your hash functor with noexcept"); + + // Following two static assertions are necessary to guarantee + // that swapping two hashtable instances won't invalidate + // associated local iterators. + + // When hash codes are cached local iterator only uses H2 which + // must then be empty. + static_assert(__if_hash_cached>::value, + "Functor used to map hash code to bucket index" + " must be empty"); + + // When hash codes are not cached local iterator is going to use + // __hash_code_base above to compute node bucket index so it has + // to be empty. + static_assert(__if_hash_not_cached>::value, + "Cache the hash code or make functors involved in hash code" + " and bucket index computation empty"); public: - typedef _Allocator allocator_type; - typedef _Value value_type; - typedef _Key key_type; - typedef _Equal key_equal; - // mapped_type, if present, comes from _Map_base. - // hasher, if present, comes from _Hash_code_base. - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; - - typedef std::size_t size_type; - typedef std::ptrdiff_t difference_type; - typedef __detail::_Local_iterator - local_iterator; - typedef __detail::_Local_const_iterator - const_local_iterator; - typedef __detail::_Node_iterator - iterator; - typedef __detail::_Node_const_iterator - const_iterator; - - template + template friend struct __detail::_Map_base; + template + friend struct __detail::_Insert_base; + + template + friend struct __detail::_Insert; + + using size_type = typename __hashtable_base::size_type; + using difference_type = typename __hashtable_base::difference_type; + + using iterator = typename __hashtable_base::iterator; + using const_iterator = typename __hashtable_base::const_iterator; + + using local_iterator = typename __hashtable_base::local_iterator; + using const_local_iterator = typename __hashtable_base:: + const_local_iterator; + private: - typedef typename _RehashPolicy::_State _RehashPolicyState; - typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; - typedef typename _Allocator::template rebind<_Node>::other + typedef typename _Alloc::template rebind<__node_type>::other _Node_allocator_type; - typedef __detail::_Hash_node_base _BaseNode; - typedef _BaseNode* _Bucket; - typedef typename _Allocator::template rebind<_Bucket>::other + typedef typename _Alloc::template rebind<__bucket_type>::other _Bucket_allocator_type; - - typedef typename _Allocator::template rebind<_Value>::other + typedef typename _Alloc::template rebind::other _Value_allocator_type; + _Node_allocator_type _M_node_allocator; - _Bucket* _M_buckets; + __bucket_type* _M_buckets; size_type _M_bucket_count; - _BaseNode _M_before_begin; + __node_base _M_before_begin; size_type _M_element_count; _RehashPolicy _M_rehash_policy; template - _Node* + __node_type* _M_allocate_node(_Args&&... __args); void - _M_deallocate_node(_Node* __n); + _M_deallocate_node(__node_type* __n); // Deallocate the linked list of nodes pointed to by __n void - _M_deallocate_nodes(_Node* __n); + _M_deallocate_nodes(__node_type* __n); - _Bucket* + __bucket_type* _M_allocate_buckets(size_type __n); void - _M_deallocate_buckets(_Bucket*, size_type __n); + _M_deallocate_buckets(__bucket_type*, size_type __n); // Gets bucket begin, deals with the fact that non-empty buckets contain // their before begin node. - _Node* + __node_type* _M_bucket_begin(size_type __bkt) const; - _Node* + __node_type* _M_begin() const - { return static_cast<_Node*>(_M_before_begin._M_nxt); } + { return static_cast<__node_type*>(_M_before_begin._M_nxt); } public: // Constructor, destructor, assignment, swap @@ -305,6 +357,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable(_Hashtable&&); + // Use delegating construtors. + explicit + _Hashtable(size_type __n = 10, + const _H1& __hf = _H1(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Hashtable(__n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + __key_extract(), __a) + { } + + template + _Hashtable(_InputIterator __f, _InputIterator __l, + size_type __n = 0, + const _H1& __hf = _H1(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Hashtable(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + __key_extract(), __a) + { } + + _Hashtable(initializer_list __l, + size_type __n = 0, + const _H1& __hf = _H1(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Hashtable(__l.begin(), __l.end(), __n, __hf, + __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + __key_extract(), __a) + { } + _Hashtable& operator=(const _Hashtable& __ht) { @@ -323,6 +408,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return *this; } + _Hashtable& + operator=(initializer_list __l) + { + this->clear(); + this->insert(__l.begin(), __l.end()); + return *this; + } + ~_Hashtable() noexcept; void swap(_Hashtable&); @@ -394,8 +487,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION local_iterator begin(size_type __n) - { return local_iterator(_M_bucket_begin(__n), __n, - _M_bucket_count); } + { return local_iterator(_M_bucket_begin(__n), __n, _M_bucket_count); } local_iterator end(size_type __n) @@ -428,8 +520,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // max_load_factor, if present, comes from _Rehash_base. - // Generalization of max_load_factor. Extension, not found in TR1. Only - // useful if _RehashPolicy is something other than the default. + // Generalization of max_load_factor. Extension, not found in + // TR1. Only useful if _RehashPolicy is something other than + // the default. const _RehashPolicy& __rehash_policy() const { return _M_rehash_policy; } @@ -453,63 +546,49 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::pair equal_range(const key_type& __k) const; - private: + protected: // Bucket index computation helpers. size_type - _M_bucket_index(_Node* __n) const - { return _HCBase::_M_bucket_index(__n, _M_bucket_count); } + _M_bucket_index(__node_type* __n) const + { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } size_type - _M_bucket_index(const key_type& __k, - typename _Hashtable::_Hash_code_type __c) const - { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); } + _M_bucket_index(const key_type& __k, __hash_code __c) const + { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); } // Find and insert helper functions and types // Find the node before the one matching the criteria. - _BaseNode* - _M_find_before_node(size_type, const key_type&, - typename _Hashtable::_Hash_code_type) const; + __node_base* + _M_find_before_node(size_type, const key_type&, __hash_code) const; - _Node* + __node_type* _M_find_node(size_type __bkt, const key_type& __key, - typename _Hashtable::_Hash_code_type __c) const + __hash_code __c) const { - _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c); + __node_base* __before_n = _M_find_before_node(__bkt, __key, __c); if (__before_n) - return static_cast<_Node*>(__before_n->_M_nxt); + return static_cast<__node_type*>(__before_n->_M_nxt); return nullptr; } // Insert a node at the beginning of a bucket. void - _M_insert_bucket_begin(size_type, _Node*); + _M_insert_bucket_begin(size_type, __node_type*); // Remove the bucket first node void - _M_remove_bucket_begin(size_type __bkt, _Node* __next_n, + _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n, size_type __next_bkt); // Get the node before __n in the bucket __bkt - _BaseNode* - _M_get_previous_node(size_type __bkt, _BaseNode* __n); + __node_base* + _M_get_previous_node(size_type __bkt, __node_base* __n); template iterator - _M_insert_bucket(_Arg&&, size_type, - typename _Hashtable::_Hash_code_type); + _M_insert_bucket(_Arg&&, size_type, __hash_code); - typedef typename std::conditional<__unique_keys, - std::pair, - iterator>::type - _Insert_Return_Type; - typedef typename std::conditional<__unique_keys, - std::_Select1st<_Insert_Return_Type>, - std::_Identity<_Insert_Return_Type> - >::type - _Insert_Conv_Type; - - protected: template std::pair _M_emplace(std::true_type, _Args&&... __args); @@ -527,51 +606,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&&, std::false_type); public: - // Emplace, insert and erase + // Emplace template - _Insert_Return_Type + __ireturn_type emplace(_Args&&... __args) - { return _M_emplace(integral_constant(), - std::forward<_Args>(__args)...); } + { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); } template iterator emplace_hint(const_iterator, _Args&&... __args) - { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); } + { return __iconv_type()(emplace(std::forward<_Args>(__args)...)); } - _Insert_Return_Type - insert(const value_type& __v) - { return _M_insert(__v, integral_constant()); } - - iterator - insert(const_iterator, const value_type& __v) - { return _Insert_Conv_Type()(insert(__v)); } - - template, - std::is_convertible<_Pair, - value_type>>::value>::type> - _Insert_Return_Type - insert(_Pair&& __v) - { return _M_insert(std::forward<_Pair>(__v), - integral_constant()); } - - template, - std::is_convertible<_Pair, - value_type>>::value>::type> - iterator - insert(const_iterator, _Pair&& __v) - { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); } - - template - void - insert(_InputIterator __first, _InputIterator __last); - - void - insert(initializer_list __l) - { this->insert(__l.begin(), __l.end()); } + // Insert member functions via inheritance. + // Erase iterator erase(const_iterator); @@ -602,26 +650,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Helper rehash method used when keys can be non-unique. void _M_rehash_aux(size_type __n, std::false_type); - // Unconditionally change size of bucket array to n, restore hash policy - // state to __state on exception. - void _M_rehash(size_type __n, const _RehashPolicyState& __state); + // Unconditionally change size of bucket array to n, restore + // hash policy state to __state on exception. + void _M_rehash(size_type __n, const __rehash_state& __state); }; // Definitions of class template _Hashtable's out-of-line member functions. template + typename _Traits> template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_Node* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>::__node_type* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_allocate_node(_Args&&... __args) { - _Node* __n = _M_node_allocator.allocate(1); + __node_type* __n = _M_node_allocator.allocate(1); __try { _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); @@ -635,125 +682,122 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_deallocate_node(_Node* __n) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_deallocate_node(__node_type* __n) { _M_node_allocator.destroy(__n); _M_node_allocator.deallocate(__n, 1); } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_deallocate_nodes(_Node* __n) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_deallocate_nodes(__node_type* __n) { while (__n) { - _Node* __tmp = __n; + __node_type* __tmp = __n; __n = __n->_M_next(); _M_deallocate_node(__tmp); } } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_Bucket* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>::__bucket_type* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_allocate_buckets(size_type __n) { _Bucket_allocator_type __alloc(_M_node_allocator); - _Bucket* __p = __alloc.allocate(__n); - __builtin_memset(__p, 0, __n * sizeof(_Bucket)); + __bucket_type* __p = __alloc.allocate(__n); + __builtin_memset(__p, 0, __n * sizeof(__bucket_type)); return __p; } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_deallocate_buckets(_Bucket* __p, size_type __n) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_deallocate_buckets(__bucket_type* __p, size_type __n) { _Bucket_allocator_type __alloc(_M_node_allocator); __alloc.deallocate(__p, __n); } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_Node* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::__node_type* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_bucket_begin(size_type __bkt) const { - _BaseNode* __n = _M_buckets[__bkt]; - return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr; + __node_base* __n = _M_buckets[__bkt]; + return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr; } template - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _Hashtable(size_type __bucket_hint, const _H1& __h1, const _H2& __h2, const _Hash& __h, const _Equal& __eq, const _ExtractKey& __exk, const allocator_type& __a) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), - __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, - __eq), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + : __hashtable_base(__exk, __h1, __h2, __h, __eq), + __map_base(), + __rehash_base(), _M_node_allocator(__a), _M_bucket_count(0), _M_element_count(0), _M_rehash_policy() { _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); - // We don't want the rehash policy to ask for the hashtable to shrink - // on the first insertion so we need to reset its previous resize level. + + // We don't want the rehash policy to ask for the hashtable to + // shrink on the first insertion so we need to reset its + // previous resize level. _M_rehash_policy._M_prev_resize = 0; _M_buckets = _M_allocate_buckets(_M_bucket_count); } template + typename _Traits> template - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _Hashtable(_InputIterator __f, _InputIterator __l, size_type __bucket_hint, const _H1& __h1, const _H2& __h2, const _Hash& __h, const _Equal& __eq, const _ExtractKey& __exk, const allocator_type& __a) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), - __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, - __eq), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + : __hashtable_base(__exk, __h1, __h2, __h, __eq), + __map_base(), + __rehash_base(), _M_node_allocator(__a), _M_bucket_count(0), _M_element_count(0), @@ -764,9 +808,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bkt_for_elements(__detail:: __distance_fw(__f, __l))); - // We don't want the rehash policy to ask for the hashtable to shrink - // on the first insertion so we need to reset its previous resize - // level. + + // We don't want the rehash policy to ask for the hashtable to + // shrink on the first insertion so we need to reset its + // previous resize level. _M_rehash_policy._M_prev_resize = 0; _M_buckets = _M_allocate_buckets(_M_bucket_count); __try @@ -783,16 +828,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _Hashtable(const _Hashtable& __ht) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), - __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__ht), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + : __hashtable_base(__ht), + __map_base(__ht), + __rehash_base(__ht), _M_node_allocator(__ht._M_node_allocator), _M_bucket_count(__ht._M_bucket_count), _M_element_count(__ht._M_element_count), @@ -806,14 +850,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First deal with the special first node pointed to by // _M_before_begin. - const _Node* __ht_n = __ht._M_begin(); - _Node* __this_n = _M_allocate_node(__ht_n->_M_v); + const __node_type* __ht_n = __ht._M_begin(); + __node_type* __this_n = _M_allocate_node(__ht_n->_M_v); this->_M_copy_code(__this_n, __ht_n); _M_before_begin._M_nxt = __this_n; _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; // Then deal with other nodes. - _BaseNode* __prev_n = __this_n; + __node_base* __prev_n = __this_n; for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) { __this_n = _M_allocate_node(__ht_n->_M_v); @@ -834,16 +878,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _Hashtable(_Hashtable&& __ht) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), - __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__ht), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + : __hashtable_base(__ht), + __map_base(__ht), + __rehash_base(__ht), _M_node_allocator(std::move(__ht._M_node_allocator)), _M_buckets(__ht._M_buckets), _M_bucket_count(__ht._M_bucket_count), @@ -862,11 +905,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: ~_Hashtable() noexcept { clear(); @@ -874,17 +917,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: swap(_Hashtable& __x) { - // The only base class with member variables is hash_code_base. We - // define _Hash_code_base::_M_swap because different specializations - // have different members. + // The only base class with member variables is hash_code_base. + // We define _Hash_code_base::_M_swap because different + // specializations have different members. this->_M_swap(__x); // _GLIBCXX_RESOLVE_LIB_DEFECTS @@ -897,8 +940,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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); - // Fix buckets containing the _M_before_begin pointers that can't be - // swapped. + + // 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()) @@ -907,12 +951,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: __rehash_policy(const _RehashPolicy& __pol) { size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); @@ -922,53 +966,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: find(const key_type& __k) { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_find_node(__n, __k, __code); + __node_type* __p = _M_find_node(__n, __k, __code); return __p ? iterator(__p) : this->end(); } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::const_iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::const_iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: find(const key_type& __k) const { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_find_node(__n, __k, __code); + __node_type* __p = _M_find_node(__n, __k, __code); return __p ? const_iterator(__p) : this->end(); } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::size_type - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::size_type + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: count(const key_type& __k) const { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_bucket_begin(__n); + __node_type* __p = _M_bucket_begin(__n); if (!__p) return 0; @@ -978,9 +1022,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (this->_M_equals(__k, __code, __p)) ++__result; else if (__result) - // All equivalent values are next to each other, if we found a not - // equivalent value after an equivalent one it means that we won't - // find anymore an equivalent value. + // All equivalent values are next to each other, if we + // found a not equivalent value after an equivalent one it + // means that we won't find anymore an equivalent value. break; if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) break; @@ -989,28 +1033,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - std::pair + std::pair::iterator, - typename _Hashtable<_Key, _Value, _Allocator, + _Traits>::iterator, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_find_node(__n, __k, __code); + __node_type* __p = _M_find_node(__n, __k, __code); if (__p) { - _Node* __p1 = __p->_M_next(); + __node_type* __p1 = __p->_M_next(); while (__p1 && _M_bucket_index(__p1) == __n && this->_M_equals(__k, __code, __p1)) __p1 = __p1->_M_next(); @@ -1022,28 +1066,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - std::pair + std::pair::const_iterator, - typename _Hashtable<_Key, _Value, _Allocator, + _Traits>::const_iterator, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::const_iterator> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::const_iterator> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) const { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_find_node(__n, __k, __code); + __node_type* __p = _M_find_node(__n, __k, __code); if (__p) { - _Node* __p1 = __p->_M_next(); + __node_type* __p1 = __p->_M_next(); while (__p1 && _M_bucket_index(__p1) == __n && this->_M_equals(__k, __code, __p1)) __p1 = __p1->_M_next(); @@ -1054,24 +1098,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::make_pair(this->end(), this->end()); } - // Find the node whose key compares equal to k in the bucket n. Return nullptr - // if no node is found. + // Find the node whose key compares equal to k in the bucket n. + // Return nullptr if no node is found. template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_BaseNode* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::__node_base* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_find_before_node(size_type __n, const key_type& __k, - typename _Hashtable::_Hash_code_type __code) const + __hash_code __code) const { - _BaseNode* __prev_p = _M_buckets[__n]; + __node_base* __prev_p = _M_buckets[__n]; if (!__prev_p) return nullptr; - _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); + __node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt); for (;; __p = __p->_M_next()) { if (this->_M_equals(__k, __code, __p)) @@ -1084,44 +1128,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_insert_bucket_begin(size_type __bkt, _Node* __new_node) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_insert_bucket_begin(size_type __bkt, __node_type* __node) { if (_M_buckets[__bkt]) { - // Bucket is not empty, we just need to insert the new node after the - // bucket before begin. - __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt; - _M_buckets[__bkt]->_M_nxt = __new_node; + // Bucket is not empty, we just need to insert the new node + // after the bucket before begin. + __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; + _M_buckets[__bkt]->_M_nxt = __node; } else { - // The bucket is empty, the new node is inserted at the beginning of - // the singly linked list and the bucket will contain _M_before_begin - // pointer. - __new_node->_M_nxt = _M_before_begin._M_nxt; - _M_before_begin._M_nxt = __new_node; - if (__new_node->_M_nxt) + // The bucket is empty, the new node is inserted at the + // beginning of the singly linked list and the bucket will + // contain _M_before_begin pointer. + __node->_M_nxt = _M_before_begin._M_nxt; + _M_before_begin._M_nxt = __node; + if (__node->_M_nxt) // We must update former begin bucket that is pointing to // _M_before_begin. - _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node; + _M_buckets[_M_bucket_index(__node->_M_next())] = __node; _M_buckets[__bkt] = &_M_before_begin; } } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_remove_bucket_begin(size_type __bkt, __node_type* __next, + size_type __next_bkt) { if (!__next || __next_bkt != __bkt) { @@ -1129,6 +1174,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First update next bucket if any if (__next) _M_buckets[__next_bkt] = _M_buckets[__bkt]; + // Second update before begin node if necessary if (&_M_before_begin == _M_buckets[__bkt]) _M_before_begin._M_nxt = __next; @@ -1137,54 +1183,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_BaseNode* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_get_previous_node(size_type __bkt, _BaseNode* __n) + _Traits>::__node_base* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_get_previous_node(size_type __bkt, __node_base* __n) { - _BaseNode* __prev_n = _M_buckets[__bkt]; + __node_base* __prev_n = _M_buckets[__bkt]; while (__prev_n->_M_nxt != __n) __prev_n = __prev_n->_M_nxt; return __prev_n; } template + typename _Traits> template - std::pair::iterator, bool> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator, bool> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_emplace(std::true_type, _Args&&... __args) { // First build the node to get access to the hash code - _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); + __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...); __try { - const key_type& __k = this->_M_extract()(__new_node->_M_v); - typename _Hashtable::_Hash_code_type __code - = this->_M_hash_code(__k); + const key_type& __k = this->_M_extract()(__node->_M_v); + __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__k, __code); - if (_Node* __p = _M_find_node(__bkt, __k, __code)) + if (__node_type* __p = _M_find_node(__bkt, __k, __code)) { // There is already an equivalent node, no insertion - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); return std::make_pair(iterator(__p), false); } // We are going to insert this node - this->_M_store_code(__new_node, __code); - const _RehashPolicyState& __saved_state + this->_M_store_code(__node, __code); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, @@ -1196,42 +1241,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __bkt = _M_bucket_index(__k, __code); } - _M_insert_bucket_begin(__bkt, __new_node); + _M_insert_bucket_begin(__bkt, __node); ++_M_element_count; - return std::make_pair(iterator(__new_node), true); + return std::make_pair(iterator(__node), true); } __catch(...) { - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); __throw_exception_again; } } template + typename _Traits> template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_emplace(std::false_type, _Args&&... __args) { - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); // First build the node to get its hash code. - _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); + __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...); __try { - const key_type& __k = this->_M_extract()(__new_node->_M_v); - typename _Hashtable::_Hash_code_type __code - = this->_M_hash_code(__k); - this->_M_store_code(__new_node, __code); + const key_type& __k = this->_M_extract()(__node->_M_v); + __hash_code __code = this->_M_hash_code(__k); + this->_M_store_code(__node, __code); // Second, do rehash if necessary. if (__do_rehash.first) @@ -1239,44 +1283,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Third, find the node before an equivalent one. size_type __bkt = _M_bucket_index(__k, __code); - _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code); - + __node_base* __prev = _M_find_before_node(__bkt, __k, __code); + if (__prev) { // Insert after the node before the equivalent one. - __new_node->_M_nxt = __prev->_M_nxt; - __prev->_M_nxt = __new_node; + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; } else - // The inserted node has no equivalent in the hashtable. We must - // insert the new node at the beginning of the bucket to preserve - // equivalent elements relative positions. - _M_insert_bucket_begin(__bkt, __new_node); + // The inserted node has no equivalent in the + // hashtable. We must insert the new node at the + // beginning of the bucket to preserve equivalent + // elements relative positions. + _M_insert_bucket_begin(__bkt, __node); ++_M_element_count; - return iterator(__new_node); + return iterator(__node); } __catch(...) { - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); __throw_exception_again; } } // Insert v in bucket n (assumes no element with its key already present). template + typename _Traits> template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_insert_bucket(_Arg&& __v, size_type __n, - typename _Hashtable::_Hash_code_type __code) + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_insert_bucket(_Arg&& __v, size_type __n, __hash_code __code) { - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); @@ -1284,52 +1328,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__do_rehash.first) { const key_type& __k = this->_M_extract()(__v); - __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second); + __n = __hash_code_base::_M_bucket_index(__k, __code, + __do_rehash.second); } - _Node* __new_node = nullptr; + __node_type* __node = nullptr; __try { // Allocate the new node before doing the rehash so that we // don't do a rehash if the allocation throws. - __new_node = _M_allocate_node(std::forward<_Arg>(__v)); - this->_M_store_code(__new_node, __code); + __node = _M_allocate_node(std::forward<_Arg>(__v)); + this->_M_store_code(__node, __code); if (__do_rehash.first) _M_rehash(__do_rehash.second, __saved_state); - _M_insert_bucket_begin(__n, __new_node); + _M_insert_bucket_begin(__n, __node); ++_M_element_count; - return iterator(__new_node); + return iterator(__node); } __catch(...) { - if (!__new_node) + if (!__node) _M_rehash_policy._M_reset(__saved_state); else - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); __throw_exception_again; } } // Insert v if no element with its key is already present. template + typename _Traits> template - std::pair::iterator, bool> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator, bool> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_insert(_Arg&& __v, std::true_type) { const key_type& __k = this->_M_extract()(__v); - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); size_type __n = _M_bucket_index(__k, __code); - if (_Node* __p = _M_find_node(__n, __k, __code)) + if (__node_type* __p = _M_find_node(__n, __k, __code)) return std::make_pair(iterator(__p), false); return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v), __n, __code), true); @@ -1337,103 +1382,84 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert v unconditionally. template + typename _Traits> template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_insert(_Arg&& __v, std::false_type) { - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); - // First compute the hash code so that we don't do anything if it throws. - typename _Hashtable::_Hash_code_type __code - = this->_M_hash_code(this->_M_extract()(__v)); + // First compute the hash code so that we don't do anything if + // it throws. + __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); - _Node* __new_node = nullptr; + __node_type* __node = nullptr; __try { // Second allocate new node so that we don't rehash if it throws. - __new_node = _M_allocate_node(std::forward<_Arg>(__v)); - this->_M_store_code(__new_node, __code); + __node = _M_allocate_node(std::forward<_Arg>(__v)); + this->_M_store_code(__node, __code); if (__do_rehash.first) _M_rehash(__do_rehash.second, __saved_state); // Third, find the node before an equivalent one. - size_type __bkt = _M_bucket_index(__new_node); - _BaseNode* __prev - = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v), + size_type __bkt = _M_bucket_index(__node); + __node_base* __prev + = _M_find_before_node(__bkt, this->_M_extract()(__node->_M_v), __code); if (__prev) { // Insert after the node before the equivalent one. - __new_node->_M_nxt = __prev->_M_nxt; - __prev->_M_nxt = __new_node; + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; } else - // The inserted node has no equivalent in the hashtable. We must - // insert the new node at the beginning of the bucket to preserve - // equivalent elements relative positions. - _M_insert_bucket_begin(__bkt, __new_node); + // The inserted node has no equivalent in the + // hashtable. We must insert the new node at the + // beginning of the bucket to preserve equivalent + // elements relative positions. + _M_insert_bucket_begin(__bkt, __node); ++_M_element_count; - return iterator(__new_node); + return iterator(__node); } __catch(...) { - if (!__new_node) + if (!__node) _M_rehash_policy._M_reset(__saved_state); else - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); __throw_exception_again; } } - template - template - void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - insert(_InputIterator __first, _InputIterator __last) - { - size_type __n_elt = __detail::__distance_fw(__first, __last); - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); - std::pair __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, - _M_element_count, __n_elt); - if (__do_rehash.first) - _M_rehash(__do_rehash.second, __saved_state); - - for (; __first != __last; ++__first) - this->insert(*__first); - } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: erase(const_iterator __it) { - _Node* __n = __it._M_cur; + __node_type* __n = __it._M_cur; std::size_t __bkt = _M_bucket_index(__n); - // Look for previous node to unlink it from the erased one, this is why - // we need buckets to contain the before begin to make this research fast. - _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); + // Look for previous node to unlink it from the erased one, this + // is why we need buckets to contain the before begin to make + // this research fast. + __node_base* __prev_n = _M_get_previous_node(__bkt, __n); if (__n == _M_bucket_begin(__bkt)) _M_remove_bucket_begin(__bkt, __n->_M_next(), __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); @@ -1453,34 +1479,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::size_type - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::size_type + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: erase(const key_type& __k) { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__k, __code); + // Look for the node before the first matching node. - _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code); + __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); if (!__prev_n) return 0; - _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt); + __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n; // We found a matching node, start deallocation loop from it std::size_t __next_bkt = __bkt; - _Node* __next_n = __n; + __node_type* __next_n = __n; size_type __result = 0; - _Node* __saved_n = nullptr; + __node_type* __saved_n = nullptr; do { - _Node* __p = __next_n; + __node_type* __p = __next_n; __next_n = __p->_M_next(); + // _GLIBCXX_RESOLVE_LIB_DEFECTS // 526. Is it undefined if a function in the standard changes // in parameters? @@ -1509,31 +1537,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: erase(const_iterator __first, const_iterator __last) { - _Node* __n = __first._M_cur; - _Node* __last_n = __last._M_cur; + __node_type* __n = __first._M_cur; + __node_type* __last_n = __last._M_cur; if (__n == __last_n) return iterator(__n); std::size_t __bkt = _M_bucket_index(__n); - _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); + __node_base* __prev_n = _M_get_previous_node(__bkt, __n); bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); std::size_t __n_bkt = __bkt; for (;;) { do { - _Node* __tmp = __n; + __node_type* __tmp = __n; __n = __n->_M_next(); _M_deallocate_node(__tmp); --_M_element_count; @@ -1557,30 +1585,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: clear() noexcept { _M_deallocate_nodes(_M_begin()); - __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket)); + __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); _M_element_count = 0; _M_before_begin._M_nxt = nullptr; } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: rehash(size_type __n) { - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1)), @@ -1588,17 +1616,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_rehash(size_type __n, const _RehashPolicyState& __state) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_rehash(size_type __n, const __rehash_state& __state) { __try { - _M_rehash_aux(__n, integral_constant()); + _M_rehash_aux(__n, __unique_keys()); } __catch(...) { @@ -1611,22 +1639,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Rehash when there is no equivalent elements. template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __n, std::true_type) { - _Bucket* __new_buckets = _M_allocate_buckets(__n); - _Node* __p = _M_begin(); + __bucket_type* __new_buckets = _M_allocate_buckets(__n); + __node_type* __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt; while (__p) { - _Node* __next = __p->_M_next(); - std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); + __node_type* __next = __p->_M_next(); + std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); if (!__new_buckets[__bkt]) { __p->_M_nxt = _M_before_begin._M_nxt; @@ -1651,28 +1679,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Rehash when there can be equivalent elements, preserve their relative // order. template + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __n, std::false_type) { - _Bucket* __new_buckets = _M_allocate_buckets(__n); + __bucket_type* __new_buckets = _M_allocate_buckets(__n); - _Node* __p = _M_begin(); + __node_type* __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt; std::size_t __prev_bkt; - _Node* __prev_p = nullptr; + __node_type* __prev_p = nullptr; bool __check_bucket = false; while (__p) { bool __check_now = true; - _Node* __next = __p->_M_next(); - std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); + __node_type* __next = __p->_M_next(); + std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); if (!__new_buckets[__bkt]) { @@ -1707,7 +1735,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_buckets[__bkt]->_M_nxt = __p; } } - + if (__check_now && __check_bucket) { // Check if we shall update the next bucket because of insertions @@ -1715,7 +1743,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__prev_p->_M_nxt) { std::size_t __next_bkt - = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); + = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), + __n); if (__next_bkt != __prev_bkt) __new_buckets[__next_bkt] = __prev_p; } @@ -1729,7 +1758,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__check_bucket && __prev_p->_M_nxt) { std::size_t __next_bkt - = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); + = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n); if (__next_bkt != __prev_bkt) __new_buckets[__next_bkt] = __prev_p; } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index b585d23a970f..2c66645e2c49 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -33,10 +33,26 @@ namespace std _GLIBCXX_VISIBILITY(default) { + template + class _Hashtable; + namespace __detail { _GLIBCXX_BEGIN_NAMESPACE_VERSION + /** + * @defgroup hashtable-detail Base and Implementation Classes + * @ingroup unordered_associative_containers + * @{ + */ + template + struct _Hashtable_base; + // Helper function: return distance(first, last) for forward // iterators, or 0 for input iterators. template @@ -64,28 +80,68 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template struct __is_noexcept_hash : std::integral_constant()(declval()))> - {}; + { }; - // Auxiliary types used for all instantiations of _Hashtable: nodes + // Auxiliary types used for all instantiations of _Hashtable nodes // and iterators. - // Nodes, used to wrap elements stored in the hash table. A policy - // template parameter of class template _Hashtable controls whether - // nodes also store a hash code. In some cases (e.g. strings) this - // may be a performance win. + /** + * struct _Hashtable_traits + * + * Important traits for hash tables. + * + * @tparam __cache_hash_code Boolean value. True if the value of + * the hash function is stored along with the value. This is a + * time-space tradeoff. Storing it may improve lookup speed by + * reducing the number of times we need to call the _Equal + * function. + * + * @tparam __constant_iterators Boolean value. True if iterator and + * const_iterator are both constant iterator types. This is true + * for unordered_set and unordered_multiset, false for + * unordered_map and unordered_multimap. + * + * @tparam __unique_keys Boolean value. True if the return value + * of _Hashtable::count(k) is always at most one, false if it may + * be an arbitrary number. This true for unordered_set and + * unordered_map, false for unordered_multiset and + * unordered_multimap. + */ + template + struct _Hashtable_traits + { + template + using __bool_constant = integral_constant; + + using __hash_cached = __bool_constant<_Cache_hash_code>; + using __constant_iterators = __bool_constant<_Constant_iterators>; + using __unique_keys = __bool_constant<_Unique_keys>; + }; + + /** + * struct _Hash_node_base + * + * Nodes, used to wrap elements stored in the hash table. A policy + * template parameter of class template _Hashtable controls whether + * nodes also store a hash code. In some cases (e.g. strings) this + * may be a performance win. + */ struct _Hash_node_base { _Hash_node_base* _M_nxt; - _Hash_node_base() - : _M_nxt() { } - _Hash_node_base(_Hash_node_base* __next) - : _M_nxt(__next) { } + _Hash_node_base() : _M_nxt() { } + + _Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { } }; - template + /** + * Primary template struct _Hash_node. + */ + template struct _Hash_node; + /// Specialization. template struct _Hash_node<_Value, true> : _Hash_node_base { @@ -96,10 +152,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash_node(_Args&&... __args) : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { } - _Hash_node* _M_next() const - { return static_cast<_Hash_node*>(_M_nxt); } + _Hash_node* + _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } }; + /// Specialization. template struct _Hash_node<_Value, false> : _Hash_node_base { @@ -109,56 +166,64 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash_node(_Args&&... __args) : _M_v(std::forward<_Args>(__args)...) { } - _Hash_node* _M_next() const - { return static_cast<_Hash_node*>(_M_nxt); } + _Hash_node* + _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } }; - // Node iterators, used to iterate through all the hashtable. - template + /// Base class for node iterators. + template struct _Node_iterator_base { - _Node_iterator_base(_Hash_node<_Value, __cache>* __p) + typedef _Hash_node<_Value, _Cache_hash_code> __node_type; + + __node_type* _M_cur; + + _Node_iterator_base(__node_type* __p) : _M_cur(__p) { } void _M_incr() { _M_cur = _M_cur->_M_next(); } - - _Hash_node<_Value, __cache>* _M_cur; }; - template + template inline bool - operator==(const _Node_iterator_base<_Value, __cache>& __x, - const _Node_iterator_base<_Value, __cache>& __y) + operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, + const _Node_iterator_base<_Value, _Cache_hash_code >& __y) { return __x._M_cur == __y._M_cur; } - template + template inline bool - operator!=(const _Node_iterator_base<_Value, __cache>& __x, - const _Node_iterator_base<_Value, __cache>& __y) + operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, + const _Node_iterator_base<_Value, _Cache_hash_code>& __y) { return __x._M_cur != __y._M_cur; } + /// Node iterators, used to iterate through all the hashtable. template struct _Node_iterator : public _Node_iterator_base<_Value, __cache> { + private: + using __base_type = _Node_iterator_base<_Value, __cache>; + using __node_type = typename __base_type::__node_type; + + public: typedef _Value value_type; - typedef typename std::conditional<__constant_iterators, - const _Value*, _Value*>::type - pointer; - typedef typename std::conditional<__constant_iterators, - const _Value&, _Value&>::type - reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; + using pointer = typename std::conditional<__constant_iterators, + const _Value*, _Value*>::type; + + using reference = typename std::conditional<__constant_iterators, + const _Value&, _Value&>::type; + _Node_iterator() - : _Node_iterator_base<_Value, __cache>(0) { } + : __base_type(0) { } explicit - _Node_iterator(_Hash_node<_Value, __cache>* __p) - : _Node_iterator_base<_Value, __cache>(__p) { } + _Node_iterator(__node_type* __p) + : __base_type(__p) { } reference operator*() const @@ -184,26 +249,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + /// Node const_iterators, used to iterate through all the hashtable. template struct _Node_const_iterator : public _Node_iterator_base<_Value, __cache> { + private: + using __base_type = _Node_iterator_base<_Value, __cache>; + using __node_type = typename __base_type::__node_type; + + public: typedef _Value value_type; - typedef const _Value* pointer; - typedef const _Value& reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; + typedef const _Value* pointer; + typedef const _Value& reference; + _Node_const_iterator() - : _Node_iterator_base<_Value, __cache>(0) { } + : __base_type(0) { } explicit - _Node_const_iterator(_Hash_node<_Value, __cache>* __p) - : _Node_iterator_base<_Value, __cache>(__p) { } + _Node_const_iterator(__node_type* __p) + : __base_type(__p) { } _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, __cache>& __x) - : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } + : __base_type(__x._M_cur) { } reference operator*() const @@ -232,8 +304,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Many of class template _Hashtable's template parameters are policy // classes. These are defaults for the policies. - // Default range hashing function: use division to fold a large number - // into the range [0, N). + /// Default range hashing function: use division to fold a large number + /// into the range [0, N). struct _Mod_range_hashing { typedef std::size_t first_argument_type; @@ -245,15 +317,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return __num % __den; } }; - // Default ranged hash function H. In principle it should be a - // function object composed from objects of type H1 and H2 such that - // h(k, N) = h2(h1(k), N), but that would mean making extra copies of - // h1 and h2. So instead we'll just use a tag to tell class template - // hashtable to do that composition. + /// Default ranged hash function H. In principle it should be a + /// function object composed from objects of type H1 and H2 such that + /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of + /// h1 and h2. So instead we'll just use a tag to tell class template + /// hashtable to do that composition. struct _Default_ranged_hash { }; - // Default value for rehash policy. Bucket size is (usually) the - // smallest prime that keeps the load factor small enough. + /// Default value for rehash policy. Bucket size is (usually) the + /// smallest prime that keeps the load factor small enough. struct _Prime_rehash_policy { _Prime_rehash_policy(float __z = 1.0) @@ -385,77 +457,116 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Base classes for std::_Hashtable. We define these base classes - // because in some cases we want to do different things depending - // on the value of a policy class. In some cases the policy class + // because in some cases we want to do different things depending on + // the value of a policy class. In some cases the policy class // affects which member functions and nested typedefs are defined; // we handle that by specializing base class templates. Several of // the base class templates need to access other members of class - // template _Hashtable, so we use the "curiously recurring template - // pattern" for them. - - // class template _Map_base. If the hashtable has a value type of - // the form pair and a key extraction policy that returns the - // first part of the pair, the hashtable gets a mapped_type typedef. - // If it satisfies those criteria and also has unique keys, then it - // also gets an operator[]. - template + // template _Hashtable, so we use a variant of the "Curiously + // Recurring Template Pattern" (CRTP) technique. + + /** + * Primary class template _Map_base. + * + * If the hashtable has a value type of the form pair and a + * key extraction policy (_ExtractKey) that returns the first part + * of the pair, the hashtable gets a mapped_type typedef. If it + * satisfies those criteria and also has unique keys, then it also + * gets an operator[]. + */ + template struct _Map_base { }; - template - struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> + /// Partial specialization, __unique_keys set to false. + template + struct _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false> { - typedef typename _Pair::second_type mapped_type; + using mapped_type = typename _Pair::second_type; }; - template - struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> + /// Partial specialization, __unique_keys set to true. + template + struct _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> { - typedef typename _Pair::second_type mapped_type; + private: + using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, + std::_Select1st<_Pair>, + _Equal, _H1, _H2, _Hash, + _Traits>; + + using __hashtable = _Hashtable<_Key, _Pair, _Alloc, + std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; + + using __hash_code = typename __hashtable_base::__hash_code; + using __node_type = typename __hashtable_base::__node_type; + + public: + using key_type = typename __hashtable_base::key_type; + using iterator = typename __hashtable_base::iterator; + using mapped_type = typename _Pair::second_type; mapped_type& - operator[](const _Key& __k); + operator[](const key_type& __k); mapped_type& - operator[](_Key&& __k); + operator[](key_type&& __k); // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 761. unordered_map needs an at() member function. mapped_type& - at(const _Key& __k); + at(const key_type& __k); const mapped_type& - at(const _Key& __k) const; + at(const key_type& __k) const; }; - template - typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - operator[](const _Key& __k) + template + typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + ::mapped_type& + _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + operator[](const key_type& __k) { - _Hashtable* __h = static_cast<_Hashtable*>(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + __hashtable* __h = static_cast<__hashtable*>(this); + __hash_code __code = __h->_M_hash_code(__k); std::size_t __n = __h->_M_bucket_index(__k, __code); + __node_type* __p = __h->_M_find_node(__n, __k, __code); - typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); if (!__p) return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), __n, __code)->second; return (__p->_M_v).second; } - template - typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - operator[](_Key&& __k) + template + typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + ::mapped_type& + _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + operator[](key_type&& __k) { - _Hashtable* __h = static_cast<_Hashtable*>(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + __hashtable* __h = static_cast<__hashtable*>(this); + __hash_code __code = __h->_M_hash_code(__k); std::size_t __n = __h->_M_bucket_index(__k, __code); + __node_type* __p = __h->_M_find_node(__n, __k, __code); - typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); if (!__p) return __h->_M_insert_bucket(std::make_pair(std::move(__k), mapped_type()), @@ -463,79 +574,318 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return (__p->_M_v).second; } - template - typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - at(const _Key& __k) + template + typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + ::mapped_type& + _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + at(const key_type& __k) { - _Hashtable* __h = static_cast<_Hashtable*>(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + __hashtable* __h = static_cast<__hashtable*>(this); + __hash_code __code = __h->_M_hash_code(__k); std::size_t __n = __h->_M_bucket_index(__k, __code); + __node_type* __p = __h->_M_find_node(__n, __k, __code); - typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); if (!__p) __throw_out_of_range(__N("_Map_base::at")); return (__p->_M_v).second; } - template - const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - at(const _Key& __k) const + template + const typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, + _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + ::mapped_type& + _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + at(const key_type& __k) const { - const _Hashtable* __h = static_cast(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + const __hashtable* __h = static_cast(this); + __hash_code __code = __h->_M_hash_code(__k); std::size_t __n = __h->_M_bucket_index(__k, __code); + __node_type* __p = __h->_M_find_node(__n, __k, __code); - typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); if (!__p) __throw_out_of_range(__N("_Map_base::at")); return (__p->_M_v).second; } - // class template _Rehash_base. Give hashtable the max_load_factor - // functions and reserve iff the rehash policy is _Prime_rehash_policy. - template - struct _Rehash_base { }; + /** + * Primary class template _Insert_base. + * + * insert member functions appropriate to all _Hashtables. + */ + template + struct _Insert_base + { + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + + using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _Traits>; + + using value_type = typename __hashtable_base::value_type; + using iterator = typename __hashtable_base::iterator; + using const_iterator = typename __hashtable_base::const_iterator; + using size_type = typename __hashtable_base::size_type; + + using __unique_keys = typename __hashtable_base::__unique_keys; + using __ireturn_type = typename __hashtable_base::__ireturn_type; + using __iconv_type = typename __hashtable_base::__iconv_type; + + __hashtable& + _M_conjure_hashtable() + { return *(static_cast<__hashtable*>(this)); } + + __ireturn_type + insert(const value_type& __v) + { + __hashtable& __h = _M_conjure_hashtable(); + return __h._M_insert(__v, __unique_keys()); + } + + iterator + insert(const_iterator, const value_type& __v) + { return __iconv_type()(insert(__v)); } - template - struct _Rehash_base<_Prime_rehash_policy, _Hashtable> + void + insert(initializer_list __l) + { this->insert(__l.begin(), __l.end()); } + + template + void + insert(_InputIterator __first, _InputIterator __last); + }; + + template + template + void + _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>:: + insert(_InputIterator __first, _InputIterator __last) + { + using __rehash_type = typename __hashtable::__rehash_type; + using __rehash_state = typename __hashtable::__rehash_state; + using pair_type = std::pair; + + size_type __n_elt = __detail::__distance_fw(__first, __last); + + __hashtable& __h = _M_conjure_hashtable(); + __rehash_type& __rehash = __h._M_rehash_policy; + const __rehash_state& __saved_state = __rehash._M_state(); + pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count, + __h._M_element_count, + __n_elt); + + if (__do_rehash.first) + __h._M_rehash(__do_rehash.second, __saved_state); + + for (; __first != __last; ++__first) + this->insert(*__first); + } + + /** + * Primary class template _Insert. + * + * Select insert member functions appropriate to _Hashtable policy choices. + */ + template + struct _Insert; + + /// Specialization. + template + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits, true, true> + : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits> + { + using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + using value_type = typename __base_type::value_type; + using iterator = typename __base_type::iterator; + using const_iterator = typename __base_type::const_iterator; + + using __unique_keys = typename __base_type::__unique_keys; + using __hashtable = typename __base_type::__hashtable; + + using __base_type::insert; + + std::pair + insert(value_type&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(std::move(__v), __unique_keys()); + } + + iterator + insert(const_iterator, value_type&& __v) + { return insert(std::move(__v)).first; } + }; + + /// Specialization. + template + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits, true, false> + : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits> + { + using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + using value_type = typename __base_type::value_type; + using iterator = typename __base_type::iterator; + using const_iterator = typename __base_type::const_iterator; + + using __unique_keys = typename __base_type::__unique_keys; + using __hashtable = typename __base_type::__hashtable; + + using __base_type::insert; + + iterator + insert(value_type&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(std::move(__v), __unique_keys()); + } + + iterator + insert(const_iterator, value_type&& __v) + { return insert(std::move(__v)); } + }; + + /// Specialization. + template + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits, false, _Unique_keys> + : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits> { + using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + using value_type = typename __base_type::value_type; + using iterator = typename __base_type::iterator; + using const_iterator = typename __base_type::const_iterator; + + using __unique_keys = typename __base_type::__unique_keys; + using __hashtable = typename __base_type::__hashtable; + using __ireturn_type = typename __base_type::__ireturn_type; + using __iconv_type = typename __base_type::__iconv_type; + + using __base_type::insert; + + template + using __is_convertible = std::is_convertible<_Pair, value_type>; + + template + using _IFconv = std::enable_if<__is_convertible<_Pair>::value>; + + template + using _IFconvp = typename _IFconv<_Pair>::type; + + template> + __ireturn_type + insert(_Pair&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(std::forward<_Pair>(__v), __unique_keys()); + } + + template> + iterator + insert(const_iterator, _Pair&& __v) + { return __iconv_type()(insert(std::forward<_Pair>(__v))); } + }; + + /** + * Primary class template _Rehash_base. + * + * Give hashtable the max_load_factor functions and reserve iff the + * rehash policy is _Prime_rehash_policy. + */ + template + struct _Rehash_base; + + /// Specialization. + template + struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _Prime_rehash_policy, _Traits> + { + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _Prime_rehash_policy, _Traits>; + float max_load_factor() const noexcept { - const _Hashtable* __this = static_cast(this); + const __hashtable* __this = static_cast(this); return __this->__rehash_policy().max_load_factor(); } void max_load_factor(float __z) { - _Hashtable* __this = static_cast<_Hashtable*>(this); + __hashtable* __this = static_cast<__hashtable*>(this); __this->__rehash_policy(_Prime_rehash_policy(__z)); } void reserve(std::size_t __n) { - _Hashtable* __this = static_cast<_Hashtable*>(this); + __hashtable* __this = static_cast<__hashtable*>(this); __this->rehash(__builtin_ceil(__n / max_load_factor())); } }; - // Helper class using EBO when it is not forbidden, type is not final, - // and when it worth it, type is empty. + /** + * Primary class template _Hashtable_ebo_helper. + * + * Helper class using EBO when it is not forbidden, type is not + * final, and when it worth it, type is empty. + */ template struct _Hashtable_ebo_helper; - // Specialization using EBO. + /// Specialization using EBO. template struct _Hashtable_ebo_helper<_Nm, _Tp, true> : private _Tp { _Hashtable_ebo_helper() = default; + _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) { } @@ -548,11 +898,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return static_cast<_Tp&>(__eboh); } }; - // Specialization not using EBO. + /// Specialization not using EBO. template struct _Hashtable_ebo_helper<_Nm, _Tp, false> { _Hashtable_ebo_helper() = default; + _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) { } @@ -568,70 +919,72 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Tp _M_tp; }; - // Class template _Hash_code_base. Encapsulates two policy issues that - // aren't quite orthogonal. - // (1) the difference between using a ranged hash function and using - // the combination of a hash function and a range-hashing function. - // In the former case we don't have such things as hash codes, so - // we have a dummy type as placeholder. - // (2) Whether or not we cache hash codes. Caching hash codes is - // meaningless if we have a ranged hash function. - // We also put the key extraction objects here, for convenience. - // - // Each specialization derives from one or more of the template parameters to - // benefit from Ebo. This is important as this type is inherited in some cases - // by the _Local_iterator_base type used to implement local_iterator and - // const_local_iterator. As with any iterator type we prefer to make it as - // small as possible. - - // Primary template: unused except as a hook for specializations. + /** + * Primary class template _Hash_code_base. + * + * Encapsulates two policy issues that aren't quite orthogonal. + * (1) the difference between using a ranged hash function and using + * the combination of a hash function and a range-hashing function. + * In the former case we don't have such things as hash codes, so + * we have a dummy type as placeholder. + * (2) Whether or not we cache hash codes. Caching hash codes is + * meaningless if we have a ranged hash function. + * + * We also put the key extraction objects here, for convenience. + * Each specialization derives from one or more of the template + * parameters to benefit from Ebo. This is important as this type + * is inherited in some cases by the _Local_iterator_base type used + * to implement local_iterator and const_local_iterator. As with + * any iterator type we prefer to make it as small as possible. + * + * Primary template is unused except as a hook for specializations. + */ template struct _Hash_code_base; - // Specialization: ranged hash function, no caching hash codes. H1 - // and H2 are provided but ignored. We define a dummy hash code type. - template struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> : private _Hashtable_ebo_helper<0, _ExtractKey>, private _Hashtable_ebo_helper<1, _Hash> { private: - typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; - typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; + typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; + typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; protected: + typedef void* __hash_code; + typedef _Hash_node<_Value, false> __node_type; + // We need the default constructor for the local iterators. _Hash_code_base() = default; - _Hash_code_base(const _ExtractKey& __ex, - const _H1&, const _H2&, const _Hash& __h) - : _EboExtractKey(__ex), _EboHash(__h) { } - typedef void* _Hash_code_type; + _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&, + const _Hash& __h) + : _EboExtractKey(__ex), _EboHash(__h) { } - _Hash_code_type + __hash_code _M_hash_code(const _Key& __key) const { return 0; } std::size_t - _M_bucket_index(const _Key& __k, _Hash_code_type, - std::size_t __n) const + _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const { return _M_ranged_hash()(__k, __n); } std::size_t - _M_bucket_index(const _Hash_node<_Value, false>* __p, - std::size_t __n) const + _M_bucket_index(const __node_type* __p, std::size_t __n) const { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } void - _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const + _M_store_code(__node_type*, __hash_code) const { } void - _M_copy_code(_Hash_node<_Value, false>*, - const _Hash_node<_Value, false>*) const + _M_copy_code(__node_type*, const __node_type*) const { } void @@ -644,10 +997,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION protected: const _ExtractKey& _M_extract() const { return _EboExtractKey::_S_cget(*this); } + _ExtractKey& _M_extract() { return _EboExtractKey::_S_get(*this); } + const _Hash& _M_ranged_hash() const { return _EboHash::_S_cget(*this); } + _Hash& _M_ranged_hash() { return _EboHash::_S_get(*this); } }; @@ -655,16 +1011,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // No specialization for ranged hash function while caching hash codes. // That combination is meaningless, and trying to do it is an error. - // Specialization: ranged hash function, cache hash codes. This - // combination is meaningless, so we provide only a declaration - // and no definition. + /// Specialization: ranged hash function, cache hash codes. This + /// combination is meaningless, so we provide only a declaration + /// and no definition. template struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; - // Specialization: hash function and range-hashing function, no - // caching of hash codes. - // Provides typedef and accessor required by TR1. + /// Specialization: hash function and range-hashing function, no + /// caching of hash codes. + /// Provides typedef and accessor required by TR1. template struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, @@ -674,48 +1030,48 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private _Hashtable_ebo_helper<2, _H2> { private: - typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; - typedef _Hashtable_ebo_helper<1, _H1> _EboH1; - typedef _Hashtable_ebo_helper<2, _H2> _EboH2; + typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; + typedef _Hashtable_ebo_helper<1, _H1> _EboH1; + typedef _Hashtable_ebo_helper<2, _H2> _EboH2; public: - typedef _H1 hasher; + typedef _H1 hasher; hasher hash_function() const { return _M_h1(); } + typedef std::size_t __hash_code; + typedef _Hash_node<_Value, false> __node_type; + protected: // We need the default constructor for the local iterators. _Hash_code_base() = default; + _Hash_code_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, const _Default_ranged_hash&) : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } - typedef std::size_t _Hash_code_type; - - _Hash_code_type + __hash_code _M_hash_code(const _Key& __k) const { return _M_h1()(__k); } std::size_t - _M_bucket_index(const _Key&, _Hash_code_type __c, - std::size_t __n) const + _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const { return _M_h2()(__c, __n); } std::size_t - _M_bucket_index(const _Hash_node<_Value, false>* __p, + _M_bucket_index(const __node_type* __p, std::size_t __n) const { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } void - _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const + _M_store_code(__node_type*, __hash_code) const { } void - _M_copy_code(_Hash_node<_Value, false>*, - const _Hash_node<_Value, false>*) const + _M_copy_code(__node_type*, const __node_type*) const { } void @@ -726,24 +1082,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::swap(_M_h2(), __x._M_h2()); } - protected: const _ExtractKey& _M_extract() const { return _EboExtractKey::_S_cget(*this); } + _ExtractKey& _M_extract() { return _EboExtractKey::_S_get(*this); } + const _H1& _M_h1() const { return _EboH1::_S_cget(*this); } + _H1& _M_h1() { return _EboH1::_S_get(*this); } + const _H2& _M_h2() const { return _EboH2::_S_cget(*this); } + _H2& _M_h2() { return _EboH2::_S_get(*this); } }; - // Specialization: hash function and range-hashing function, - // caching hash codes. H is provided but ignored. Provides - // typedef and accessor required by TR1. + /// Specialization: hash function and range-hashing function, + /// caching hash codes. H is provided but ignored. Provides + /// typedef and accessor required by TR1. template struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, @@ -753,46 +1113,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private _Hashtable_ebo_helper<2, _H2> { private: - typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; - typedef _Hashtable_ebo_helper<1, _H1> _EboH1; - typedef _Hashtable_ebo_helper<2, _H2> _EboH2; + typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; + typedef _Hashtable_ebo_helper<1, _H1> _EboH1; + typedef _Hashtable_ebo_helper<2, _H2> _EboH2; public: - typedef _H1 hasher; + typedef _H1 hasher; hasher hash_function() const { return _M_h1(); } + typedef std::size_t __hash_code; + typedef _Hash_node<_Value, true> __node_type; + protected: _Hash_code_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, const _Default_ranged_hash&) : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } - typedef std::size_t _Hash_code_type; - - _Hash_code_type + __hash_code _M_hash_code(const _Key& __k) const { return _M_h1()(__k); } std::size_t - _M_bucket_index(const _Key&, _Hash_code_type __c, + _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const { return _M_h2()(__c, __n); } std::size_t - _M_bucket_index(const _Hash_node<_Value, true>* __p, - std::size_t __n) const + _M_bucket_index(const __node_type* __p, std::size_t __n) const { return _M_h2()(__p->_M_hash_code, __n); } void - _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const + _M_store_code(__node_type* __n, __hash_code __c) const { __n->_M_hash_code = __c; } void - _M_copy_code(_Hash_node<_Value, true>* __to, - const _Hash_node<_Value, true>* __from) const + _M_copy_code(__node_type* __to, const __node_type* __from) const { __to->_M_hash_code = __from->_M_hash_code; } void @@ -803,105 +1162,69 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::swap(_M_h2(), __x._M_h2()); } - protected: const _ExtractKey& _M_extract() const { return _EboExtractKey::_S_cget(*this); } + _ExtractKey& _M_extract() { return _EboExtractKey::_S_get(*this); } + const _H1& _M_h1() const { return _EboH1::_S_cget(*this); } + _H1& _M_h1() { return _EboH1::_S_get(*this); } + const _H2& _M_h2() const { return _EboH2::_S_cget(*this); } + _H2& _M_h2() { return _EboH2::_S_get(*this); } }; + /** + * Primary class template _Equal_helper. + * + */ template struct _Equal_helper; + /// Specialization. template struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> { static bool _S_equals(const _Equal& __eq, const _ExtractKey& __extract, - const _Key& __k, _HashCodeType __c, - _Hash_node<_Value, true>* __n) - { return __c == __n->_M_hash_code - && __eq(__k, __extract(__n->_M_v)); } + const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n) + { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); } }; + /// Specialization. template struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> { static bool _S_equals(const _Equal& __eq, const _ExtractKey& __extract, - const _Key& __k, _HashCodeType, - _Hash_node<_Value, false>* __n) + const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n) { return __eq(__k, __extract(__n->_M_v)); } }; - // Helper class adding management of _Equal functor to _Hash_code_base - // type. - template - struct _Hashtable_base - : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, - __cache_hash_code>, - private _Hashtable_ebo_helper<0, _Equal> - { - private: - typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual; - - protected: - typedef _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, __cache_hash_code> _HCBase; - typedef typename _HCBase::_Hash_code_type _Hash_code_type; - - _Hashtable_base(const _ExtractKey& __ex, - const _H1& __h1, const _H2& __h2, - const _Hash& __hash, const _Equal& __eq) - : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { } - - bool - _M_equals(const _Key& __k, _Hash_code_type __c, - _Hash_node<_Value, __cache_hash_code>* __n) const - { - typedef _Equal_helper<_Key, _Value, _ExtractKey, - _Equal, _Hash_code_type, - __cache_hash_code> _EqualHelper; - return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), - __k, __c, __n); - } - void - _M_swap(_Hashtable_base& __x) - { - _HCBase::_M_swap(__x); - std::swap(_M_eq(), __x._M_eq()); - } - - protected: - const _Equal& - _M_eq() const { return _EboEqual::_S_cget(*this); } - _Equal& - _M_eq() { return _EboEqual::_S_get(*this); } - }; - - // Local iterators, used to iterate within a bucket but not between - // buckets. + /** + * Primary class template _Local_iterator_base. + * + * Base class for local iterators, used to iterate within a bucket + * but not between buckets. + */ template struct _Local_iterator_base; + /// Specialization. template struct _Local_iterator_base<_Key, _Value, _ExtractKey, @@ -933,6 +1256,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::size_t _M_bucket_count; }; + /// Specialization. template struct _Local_iterator_base<_Key, _Value, _ExtractKey, @@ -980,6 +1304,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, __cache>& __y) { return __x._M_cur != __y._M_cur; } + /// local iterators template @@ -1030,6 +1355,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + /// local const_iterators template @@ -1085,27 +1411,200 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + /** + * Primary class template _Hashtable_base. + * + * Base class for _Hashtable. Helper class adding management of + * _Equal functor to _Hash_code_base type. + */ + template + struct _Hashtable_base + : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, + _Traits::__hash_cached::value>, + private _Hashtable_ebo_helper<0, _Equal> + { + public: + typedef _Key key_type; + typedef _Value value_type; + typedef _Equal key_equal; + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + + using __traits_type = _Traits; + using __hash_cached = typename __traits_type::__hash_cached; + using __constant_iterators = typename __traits_type::__constant_iterators; + using __unique_keys = typename __traits_type::__unique_keys; + + using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, + _H1, _H2, _Hash, + __hash_cached::value>; + + using __hash_code = typename __hash_code_base::__hash_code; + using __node_type = typename __hash_code_base::__node_type; + + using iterator = __detail::_Node_iterator; + + using const_iterator = __detail::_Node_const_iterator; + + using local_iterator = __detail::_Local_iterator; + + using const_local_iterator = __detail::_Local_const_iterator; + + using __ireturn_type = typename std::conditional<__unique_keys::value, + std::pair, + iterator>::type; + + using __iconv_type = typename std::conditional<__unique_keys::value, + std::_Select1st<__ireturn_type>, + std::_Identity<__ireturn_type> + >::type; + private: + using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; + using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, + __hash_code, __hash_cached::value>; + + protected: + using __node_base = __detail::_Hash_node_base; + using __bucket_type = __node_base*; + + _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, + const _Hash& __hash, const _Equal& __eq) + : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) + { } + + bool + _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const + { + return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), + __k, __c, __n); + } + + void + _M_swap(_Hashtable_base& __x) + { + __hash_code_base::_M_swap(__x); + std::swap(_M_eq(), __x._M_eq()); + } + + const _Equal& + _M_eq() const { return _EqualEBO::_S_cget(*this); } + + _Equal& + _M_eq() { return _EqualEBO::_S_get(*this); } + }; - // Class template _Equality_base. This is for implementing equality - // comparison for unordered containers, per N3068, by John Lakos and - // Pablo Halpern. Algorithmically, we follow closely the reference - // implementations therein. - template - struct _Equality_base; + /** + * struct _Equality_base. + * + * Common types and functions for class _Equality. + */ + struct _Equality_base + { + protected: + template + static bool + _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); + }; - template - struct _Equality_base<_ExtractKey, true, _Hashtable> + // See std::is_permutation in N3068. + template + bool + _Equality_base:: + _S_is_permutation(_Uiterator __first1, _Uiterator __last1, + _Uiterator __first2) { - bool _M_equal(const _Hashtable&) const; + for (; __first1 != __last1; ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + break; + + if (__first1 == __last1) + return true; + + _Uiterator __last2 = __first2; + std::advance(__last2, std::distance(__first1, __last1)); + + for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) + { + _Uiterator __tmp = __first1; + while (__tmp != __it1 && !bool(*__tmp == *__it1)) + ++__tmp; + + // We've seen this one before. + if (__tmp != __it1) + continue; + + std::ptrdiff_t __n2 = 0; + for (__tmp = __first2; __tmp != __last2; ++__tmp) + if (*__tmp == *__it1) + ++__n2; + + if (!__n2) + return false; + + std::ptrdiff_t __n1 = 0; + for (__tmp = __it1; __tmp != __last1; ++__tmp) + if (*__tmp == *__it1) + ++__n1; + + if (__n1 != __n2) + return false; + } + return true; + } + + /** + * Primary class template _Equality. + * + * This is for implementing equality comparison for unordered + * containers, per N3068, by John Lakos and Pablo Halpern. + * Algorithmically, we follow closely the reference implementations + * therein. + */ + template + struct _Equality; + + /// Specialization. + template + struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + { + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; + + bool + _M_equal(const __hashtable&) const; }; - template + template bool - _Equality_base<_ExtractKey, true, _Hashtable>:: - _M_equal(const _Hashtable& __other) const + _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + _M_equal(const __hashtable& __other) const { - const _Hashtable* __this = static_cast(this); + const __hashtable* __this = static_cast(this); if (__this->size() != __other.size()) return false; @@ -1119,70 +1618,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return true; } - template - struct _Equality_base<_ExtractKey, false, _Hashtable> + /// Specialization. + template + struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false> + : public _Equality_base { - bool _M_equal(const _Hashtable&) const; - - private: - template - static bool - _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); - }; + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; - // See std::is_permutation in N3068. - template - template bool - _Equality_base<_ExtractKey, false, _Hashtable>:: - _S_is_permutation(_Uiterator __first1, _Uiterator __last1, - _Uiterator __first2) - { - for (; __first1 != __last1; ++__first1, ++__first2) - if (!(*__first1 == *__first2)) - break; - - if (__first1 == __last1) - return true; - - _Uiterator __last2 = __first2; - std::advance(__last2, std::distance(__first1, __last1)); - - for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) - { - _Uiterator __tmp = __first1; - while (__tmp != __it1 && !bool(*__tmp == *__it1)) - ++__tmp; - - // We've seen this one before. - if (__tmp != __it1) - continue; - - std::ptrdiff_t __n2 = 0; - for (__tmp = __first2; __tmp != __last2; ++__tmp) - if (*__tmp == *__it1) - ++__n2; - - if (!__n2) - return false; - - std::ptrdiff_t __n1 = 0; - for (__tmp = __it1; __tmp != __last1; ++__tmp) - if (*__tmp == *__it1) - ++__n1; - - if (__n1 != __n2) - return false; - } - return true; - } + _M_equal(const __hashtable&) const; + }; - template + template bool - _Equality_base<_ExtractKey, false, _Hashtable>:: - _M_equal(const _Hashtable& __other) const + _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: + _M_equal(const __hashtable& __other) const { - const _Hashtable* __this = static_cast(this); + const __hashtable* __this = static_cast(this); if (__this->size() != __other.size()) return false; @@ -1196,8 +1657,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION != std::distance(__yrange.first, __yrange.second)) return false; - if (!_S_is_permutation(__xrange.first, - __xrange.second, + if (!_S_is_permutation(__xrange.first, __xrange.second, __yrange.first)) return false; @@ -1206,6 +1666,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return true; } + //@} hashtable-detail _GLIBCXX_END_NAMESPACE_VERSION } // namespace __detail } // namespace std diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 95f5657762a1..dd08b2645c18 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -1,6 +1,6 @@ // unordered_map implementation -*- C++ -*- -// Copyright (C) 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2010, 2011, 2012 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 @@ -34,208 +34,41 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER - // NB: When we get typedef templates these class definitions - // will be unnecessary. - template, - class _Pred = std::equal_to<_Key>, - class _Alloc = std::allocator >, - bool __cache_hash_code = - __not_<__and_, is_empty<_Hash>, - integral_constant, - __detail::__is_noexcept_hash<_Key, _Hash>>>::value> - class __unordered_map - : public _Hashtable<_Key, std::pair, _Alloc, - std::_Select1st >, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, false, true> - { - typedef _Hashtable<_Key, std::pair, _Alloc, - std::_Select1st >, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, false, true> - _Base; - - public: - typedef typename _Base::value_type value_type; - typedef typename _Base::size_type size_type; - typedef typename _Base::hasher hasher; - typedef typename _Base::key_equal key_equal; - typedef typename _Base::allocator_type allocator_type; - - explicit - __unordered_map(size_type __n = 10, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st >(), __a) - { } - - template - __unordered_map(_InputIterator __f, _InputIterator __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st >(), __a) - { } - - __unordered_map(initializer_list __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__l.begin(), __l.end(), __n, __hf, - __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st >(), __a) - { } - - __unordered_map& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } - }; - - template, - class _Pred = std::equal_to<_Key>, - class _Alloc = std::allocator >, - bool __cache_hash_code = - __not_<__and_, is_empty<_Hash>, - integral_constant, - __detail::__is_noexcept_hash<_Key, _Hash>>>::value> - class __unordered_multimap - : public _Hashtable<_Key, std::pair, - _Alloc, - std::_Select1st >, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, false, false> - { - typedef _Hashtable<_Key, std::pair, - _Alloc, - std::_Select1st >, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, false, false> - _Base; - - public: - typedef typename _Base::value_type value_type; - typedef typename _Base::size_type size_type; - typedef typename _Base::hasher hasher; - typedef typename _Base::key_equal key_equal; - typedef typename _Base::allocator_type allocator_type; - - explicit - __unordered_multimap(size_type __n = 10, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st >(), __a) - { } - - - template - __unordered_multimap(_InputIterator __f, _InputIterator __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st >(), __a) - { } - - __unordered_multimap(initializer_list __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__l.begin(), __l.end(), __n, __hf, - __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st >(), __a) - { } - - __unordered_multimap& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } - }; - - template - inline void - swap(__unordered_map<_Key, _Tp, _Hash, _Pred, - _Alloc, __cache_hash_code>& __x, - __unordered_map<_Key, _Tp, _Hash, _Pred, - _Alloc, __cache_hash_code>& __y) - { __x.swap(__y); } - - template - inline void - swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred, - _Alloc, __cache_hash_code>& __x, - __unordered_multimap<_Key, _Tp, _Hash, _Pred, - _Alloc, __cache_hash_code>& __y) - { __x.swap(__y); } - - template - inline bool - operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return __x._M_equal(__y); } - - template - inline bool - operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return !(__x == __y); } - - template - inline bool - operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return __x._M_equal(__y); } - - template - inline bool - operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return !(__x == __y); } + /// Base types for unordered_map. + template + using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>; + + template, + typename _Pred = std::equal_to<_Key>, + typename _Alloc = std::allocator >, + typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>> + using __umap_hashtable = _Hashtable<_Key, std::pair, + _Alloc, + std::_Select1st>, + _Pred, _Hash, + __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, _Tr>; + + /// Base types for unordered_multimap. + template + using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>; + + template, + typename _Pred = std::equal_to<_Key>, + typename _Alloc = std::allocator >, + typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>> + using __ummap_hashtable = _Hashtable<_Key, std::pair, + _Alloc, + std::_Select1st>, + _Pred, _Hash, + __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, _Tr>; /** * @brief A standard container composed of unique keys (containing @@ -247,22 +80,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Meets the requirements of a container, and * unordered associative container * - * @param Key Type of key objects. - * @param Tp Type of mapped objects. - * @param Hash Hashing function object type, defaults to hash. - * @param Pred Predicate function object type, defaults to equal_to. - * @param Alloc Allocator type, defaults to allocator. + * @tparam _Key Type of key objects. + * @tparam _Tp Type of mapped objects. + * @tparam _Hash Hashing function object type, defaults to hash<_Value>. + * @tparam _Pred Predicate function object type, defaults + * to equal_to<_Value>. + * @tparam _Alloc Allocator type, defaults to allocator<_Key>. * - * The resulting value type of the container is std::pair. + * The resulting value type of the container is std::pair. + * + * Base is _Hashtable, dispatched at compile time via template + * alias __umap_hashtable. */ template, class _Pred = std::equal_to<_Key>, class _Alloc = std::allocator > > class unordered_map - : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> + : public __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> { - typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; + typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; public: typedef typename _Base::value_type value_type; @@ -280,13 +117,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { } template - unordered_map(_InputIterator __f, _InputIterator __l, + unordered_map(_InputIterator __f, _InputIterator __l, size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) - { } + { } unordered_map(initializer_list __l, size_type __n = 0, @@ -295,16 +132,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const allocator_type& __a = allocator_type()) : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) { } - - unordered_map& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } }; - + /** * @brief A standard container composed of equivalent keys * (possibly containing multiple of each key value) that associates @@ -315,22 +144,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Meets the requirements of a container, and * unordered associative container * - * @param Key Type of key objects. - * @param Tp Type of mapped objects. - * @param Hash Hashing function object type, defaults to hash. - * @param Pred Predicate function object type, defaults to equal_to. - * @param Alloc Allocator type, defaults to allocator. + * @tparam _Key Type of key objects. + * @tparam _Tp Type of mapped objects. + * @tparam _Hash Hashing function object type, defaults to hash<_Value>. + * @tparam _Pred Predicate function object type, defaults + * to equal_to<_Value>. + * @tparam _Alloc Allocator type, defaults to allocator<_Key>. + * + * The resulting value type of the container is std::pair. * - * The resulting value type of the container is std::pair. + * Base is _Hashtable, dispatched at compile time via template + * alias __ummap_hashtable. */ template, class _Pred = std::equal_to<_Key>, class _Alloc = std::allocator > > class unordered_multimap - : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> + : public __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> { - typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; + typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; public: typedef typename _Base::value_type value_type; @@ -338,7 +171,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Base::hasher hasher; typedef typename _Base::key_equal key_equal; typedef typename _Base::allocator_type allocator_type; - + explicit unordered_multimap(size_type __n = 10, const hasher& __hf = hasher(), @@ -348,13 +181,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { } template - unordered_multimap(_InputIterator __f, _InputIterator __l, + unordered_multimap(_InputIterator __f, _InputIterator __l, size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) - { } + { } unordered_multimap(initializer_list __l, size_type __n = 0, @@ -363,14 +196,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const allocator_type& __a = allocator_type()) : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) { } - - unordered_multimap& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } }; template diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 3d5361d42668..bd0deb0717c2 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -1,6 +1,6 @@ // unordered_set implementation -*- C++ -*- -// Copyright (C) 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2010, 2011, 2012 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 @@ -34,228 +34,36 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER - // NB: When we get typedef templates these class definitions - // will be unnecessary. - template, - class _Pred = std::equal_to<_Value>, - class _Alloc = std::allocator<_Value>, - bool __cache_hash_code = - __not_<__and_, is_empty<_Hash>, - integral_constant, - __detail::__is_noexcept_hash<_Value, _Hash>>>::value> - class __unordered_set - : public _Hashtable<_Value, _Value, _Alloc, - std::_Identity<_Value>, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, true, true> - { - typedef _Hashtable<_Value, _Value, _Alloc, - std::_Identity<_Value>, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, true, true> - _Base; - - public: - typedef typename _Base::value_type value_type; - typedef typename _Base::size_type size_type; - typedef typename _Base::hasher hasher; - typedef typename _Base::key_equal key_equal; - typedef typename _Base::allocator_type allocator_type; - typedef typename _Base::iterator iterator; - typedef typename _Base::const_iterator const_iterator; - - explicit - __unordered_set(size_type __n = 10, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity(), __a) - { } - - template - __unordered_set(_InputIterator __f, _InputIterator __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity(), __a) - { } - - __unordered_set(initializer_list __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__l.begin(), __l.end(), __n, __hf, - __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity(), __a) - { } - - __unordered_set& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } - - using _Base::insert; - - std::pair - insert(value_type&& __v) - { return this->_M_insert(std::move(__v), std::true_type()); } - - iterator - insert(const_iterator, value_type&& __v) - { return insert(std::move(__v)).first; } - }; - - template, - class _Pred = std::equal_to<_Value>, - class _Alloc = std::allocator<_Value>, - bool __cache_hash_code = - __not_<__and_, is_empty<_Hash>, - integral_constant, - __detail::__is_noexcept_hash<_Value, _Hash>>>::value> - class __unordered_multiset - : public _Hashtable<_Value, _Value, _Alloc, - std::_Identity<_Value>, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, true, false> - { - typedef _Hashtable<_Value, _Value, _Alloc, - std::_Identity<_Value>, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, true, false> - _Base; - - public: - typedef typename _Base::value_type value_type; - typedef typename _Base::size_type size_type; - typedef typename _Base::hasher hasher; - typedef typename _Base::key_equal key_equal; - typedef typename _Base::allocator_type allocator_type; - typedef typename _Base::iterator iterator; - typedef typename _Base::const_iterator const_iterator; - - explicit - __unordered_multiset(size_type __n = 10, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity(), __a) - { } - - - template - __unordered_multiset(_InputIterator __f, _InputIterator __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity(), __a) - { } - - __unordered_multiset(initializer_list __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__l.begin(), __l.end(), __n, __hf, - __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity(), __a) - { } - - __unordered_multiset& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } - - using _Base::insert; - - iterator - insert(value_type&& __v) - { return this->_M_insert(std::move(__v), std::false_type()); } - - iterator - insert(const_iterator, value_type&& __v) - { return insert(std::move(__v)); } - }; - - template - inline void - swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x, - __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y) - { __x.swap(__y); } - - template - inline void - swap(__unordered_multiset<_Value, _Hash, _Pred, - _Alloc, __cache_hash_code>& __x, - __unordered_multiset<_Value, _Hash, _Pred, - _Alloc, __cache_hash_code>& __y) - { __x.swap(__y); } - - template - inline bool - operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_set<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return __x._M_equal(__y); } - - template - inline bool - operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_set<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return !(__x == __y); } - - template - inline bool - operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return __x._M_equal(__y); } - - template - inline bool - operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return !(__x == __y); } + /// Base types for unordered_set. + template + using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>; + + template, + typename _Pred = std::equal_to<_Value>, + typename _Alloc = std::allocator<_Value>, + typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> + using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, _Hash, + __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, _Tr>; + + /// Base types for unordered_multiset. + template + using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>; + + template, + typename _Pred = std::equal_to<_Value>, + typename _Alloc = std::allocator<_Value>, + typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>> + using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, + _Pred, _Hash, + __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, _Tr>; /** * @brief A standard container composed of unique keys (containing @@ -267,19 +75,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Meets the requirements of a container, and * unordered associative container * - * @param Value Type of key objects. - * @param Hash Hashing function object type, defaults to hash. - * @param Pred Predicate function object type, defaults to equal_to. - * @param Alloc Allocator type, defaults to allocator. + * @tparam _Value Type of key objects. + * @tparam _Hash Hashing function object type, defaults to hash<_Value>. + + * @tparam _Pred Predicate function object type, defaults to + * equal_to<_Value>. + * + * @tparam _Alloc Allocator type, defaults to allocator<_Key>. + * + * Base is _Hashtable, dispatched at compile time via template + * alias __uset_hashtable. */ template, class _Pred = std::equal_to<_Value>, class _Alloc = std::allocator<_Value> > class unordered_set - : public __unordered_set<_Value, _Hash, _Pred, _Alloc> + : public __uset_hashtable<_Value, _Hash, _Pred, _Alloc> { - typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base; + typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Base; public: typedef typename _Base::value_type value_type; @@ -287,7 +101,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Base::hasher hasher; typedef typename _Base::key_equal key_equal; typedef typename _Base::allocator_type allocator_type; - + explicit unordered_set(size_type __n = 10, const hasher& __hf = hasher(), @@ -297,13 +111,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { } template - unordered_set(_InputIterator __f, _InputIterator __l, + unordered_set(_InputIterator __f, _InputIterator __l, size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) - { } + { } unordered_set(initializer_list __l, size_type __n = 0, @@ -312,14 +126,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const allocator_type& __a = allocator_type()) : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) { } - - unordered_set& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } }; /** @@ -332,19 +138,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Meets the requirements of a container, and * unordered associative container * - * @param Value Type of key objects. - * @param Hash Hashing function object type, defaults to hash. - * @param Pred Predicate function object type, defaults to equal_to. - * @param Alloc Allocator type, defaults to allocator. + * @tparam _Value Type of key objects. + * @tparam _Hash Hashing function object type, defaults to hash<_Value>. + * @tparam _Pred Predicate function object type, defaults + * to equal_to<_Value>. + * @tparam _Alloc Allocator type, defaults to allocator<_Key>. + * + * Base is _Hashtable, dispatched at compile time via template + * alias __umset_hashtable. */ template, class _Pred = std::equal_to<_Value>, class _Alloc = std::allocator<_Value> > class unordered_multiset - : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc> + : public __umset_hashtable<_Value, _Hash, _Pred, _Alloc> { - typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base; + typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Base; public: typedef typename _Base::value_type value_type; @@ -352,7 +162,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Base::hasher hasher; typedef typename _Base::key_equal key_equal; typedef typename _Base::allocator_type allocator_type; - + explicit unordered_multiset(size_type __n = 10, const hasher& __hf = hasher(), @@ -363,13 +173,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template - unordered_multiset(_InputIterator __f, _InputIterator __l, + unordered_multiset(_InputIterator __f, _InputIterator __l, size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) - { } + { } unordered_multiset(initializer_list __l, size_type __n = 0, @@ -378,14 +188,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const allocator_type& __a = allocator_type()) : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) { } - - unordered_multiset& - operator=(initializer_list __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } }; template @@ -428,4 +230,3 @@ _GLIBCXX_END_NAMESPACE_CONTAINER } // namespace std #endif /* _UNORDERED_SET_H */ - diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py index 76c54b1598e6..4520f32ac135 100644 --- a/libstdc++-v3/python/libstdcxx/v6/printers.py +++ b/libstdc++-v3/python/libstdcxx/v6/printers.py @@ -611,7 +611,7 @@ class StdStringPrinter: class Tr1HashtableIterator: def __init__ (self, hash): self.node = hash['_M_before_begin']['_M_nxt'] - self.node_type = find_type(hash.type, '_Node').pointer() + self.node_type = find_type(hash.type, '__node_type').pointer() def __iter__ (self): return self diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc index eb16e81a4d34..ac304776cadc 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc @@ -2,7 +2,7 @@ // { dg-options "-std=gnu++0x" } // { dg-require-normal-mode "" } -// Copyright (C) 2011 Free Software Foundation, Inc. +// Copyright (C) 2011, 2012 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 @@ -19,7 +19,7 @@ // with this library; see the file COPYING3. If not see // . -// { dg-error "static assertion failed" "" { target *-*-* } 185 } +// { dg-error "with noexcept" "" { target *-*-* } 248 } #include @@ -35,7 +35,10 @@ namespace void test01() { - std::__unordered_set, std::allocator, - false> us; + using traits = std::__detail::_Hashtable_traits; + using hashtable = std::__uset_hashtable, + std::allocator, traits>; + + hashtable ht; } -- 2.39.2