1 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
3 // Copyright (C) 2010-2013 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/hashtable_policy.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly.
28 * @headername{unordered_map,unordered_set}
31 #ifndef _HASHTABLE_POLICY_H
32 #define _HASHTABLE_POLICY_H 1
34 namespace std
_GLIBCXX_VISIBILITY(default)
36 _GLIBCXX_BEGIN_NAMESPACE_VERSION
38 template<typename _Key
, typename _Value
, typename _Alloc
,
39 typename _ExtractKey
, typename _Equal
,
40 typename _H1
, typename _H2
, typename _Hash
,
41 typename _RehashPolicy
, typename _Traits
>
44 _GLIBCXX_END_NAMESPACE_VERSION
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
51 * @defgroup hashtable-detail Base and Implementation Classes
52 * @ingroup unordered_associative_containers
55 template<typename _Key
, typename _Value
,
56 typename _ExtractKey
, typename _Equal
,
57 typename _H1
, typename _H2
, typename _Hash
, typename _Traits
>
58 struct _Hashtable_base
;
60 // Helper function: return distance(first, last) for forward
61 // iterators, or 0 for input iterators.
62 template<class _Iterator
>
63 inline typename
std::iterator_traits
<_Iterator
>::difference_type
64 __distance_fw(_Iterator __first
, _Iterator __last
,
65 std::input_iterator_tag
)
68 template<class _Iterator
>
69 inline typename
std::iterator_traits
<_Iterator
>::difference_type
70 __distance_fw(_Iterator __first
, _Iterator __last
,
71 std::forward_iterator_tag
)
72 { return std::distance(__first
, __last
); }
74 template<class _Iterator
>
75 inline typename
std::iterator_traits
<_Iterator
>::difference_type
76 __distance_fw(_Iterator __first
, _Iterator __last
)
78 typedef typename
std::iterator_traits
<_Iterator
>::iterator_category _Tag
;
79 return __distance_fw(__first
, __last
, _Tag());
82 // Helper type used to detect whether the hash functor is noexcept.
83 template <typename _Key
, typename _Hash
>
84 struct __is_noexcept_hash
: std::integral_constant
<bool,
85 noexcept(declval
<const _Hash
&>()(declval
<const _Key
&>()))>
90 template<typename _Tp
>
92 operator()(_Tp
&& __x
) const
93 { return std::forward
<_Tp
>(__x
); }
98 template<typename _Tp
>
100 operator()(_Tp
&& __x
) const
101 -> decltype(std::get
<0>(std::forward
<_Tp
>(__x
)))
102 { return std::get
<0>(std::forward
<_Tp
>(__x
)); }
105 template<typename _NodeAlloc
>
106 struct _Hashtable_alloc
;
108 // Functor recycling a pool of nodes and using allocation once the pool is
110 template<typename _NodeAlloc
>
111 struct _ReuseOrAllocNode
114 using __node_alloc_type
= _NodeAlloc
;
115 using __hashtable_alloc
= _Hashtable_alloc
<__node_alloc_type
>;
116 using __value_alloc_type
= typename
__hashtable_alloc::__value_alloc_type
;
117 using __value_alloc_traits
=
118 typename
__hashtable_alloc::__value_alloc_traits
;
119 using __node_alloc_traits
=
120 typename
__hashtable_alloc::__node_alloc_traits
;
121 using __node_type
= typename
__hashtable_alloc::__node_type
;
124 _ReuseOrAllocNode(__node_type
* __nodes
, __hashtable_alloc
& __h
)
125 : _M_nodes(__nodes
), _M_h(__h
) { }
126 _ReuseOrAllocNode(const _ReuseOrAllocNode
&) = delete;
129 { _M_h
._M_deallocate_nodes(_M_nodes
); }
131 template<typename _Arg
>
133 operator()(_Arg
&& __arg
) const
137 __node_type
* __node
= _M_nodes
;
138 _M_nodes
= _M_nodes
->_M_next();
139 __node
->_M_nxt
= nullptr;
140 __value_alloc_type
__a(_M_h
._M_node_allocator());
141 __value_alloc_traits::destroy(__a
, __node
->_M_valptr());
144 __value_alloc_traits::construct(__a
, __node
->_M_valptr(),
145 std::forward
<_Arg
>(__arg
));
149 __node
->~__node_type();
150 __node_alloc_traits::deallocate(_M_h
._M_node_allocator(),
152 __throw_exception_again
;
156 return _M_h
._M_allocate_node(std::forward
<_Arg
>(__arg
));
160 mutable __node_type
* _M_nodes
;
161 __hashtable_alloc
& _M_h
;
164 // Functor similar to the previous one but without any pool of node to recycle.
165 template<typename _NodeAlloc
>
169 using __hashtable_alloc
= _Hashtable_alloc
<_NodeAlloc
>;
170 using __node_type
= typename
__hashtable_alloc::__node_type
;
173 _AllocNode(__hashtable_alloc
& __h
)
176 template<typename _Arg
>
178 operator()(_Arg
&& __arg
) const
179 { return _M_h
._M_allocate_node(std::forward
<_Arg
>(__arg
)); }
182 __hashtable_alloc
& _M_h
;
185 // Auxiliary types used for all instantiations of _Hashtable nodes
189 * struct _Hashtable_traits
191 * Important traits for hash tables.
193 * @tparam _Cache_hash_code Boolean value. True if the value of
194 * the hash function is stored along with the value. This is a
195 * time-space tradeoff. Storing it may improve lookup speed by
196 * reducing the number of times we need to call the _Equal
199 * @tparam _Constant_iterators Boolean value. True if iterator and
200 * const_iterator are both constant iterator types. This is true
201 * for unordered_set and unordered_multiset, false for
202 * unordered_map and unordered_multimap.
204 * @tparam _Unique_keys Boolean value. True if the return value
205 * of _Hashtable::count(k) is always at most one, false if it may
206 * be an arbitrary number. This is true for unordered_set and
207 * unordered_map, false for unordered_multiset and
208 * unordered_multimap.
210 template<bool _Cache_hash_code
, bool _Constant_iterators
, bool _Unique_keys
>
211 struct _Hashtable_traits
214 using __bool_constant
= integral_constant
<bool, _Cond
>;
216 using __hash_cached
= __bool_constant
<_Cache_hash_code
>;
217 using __constant_iterators
= __bool_constant
<_Constant_iterators
>;
218 using __unique_keys
= __bool_constant
<_Unique_keys
>;
222 * struct _Hash_node_base
224 * Nodes, used to wrap elements stored in the hash table. A policy
225 * template parameter of class template _Hashtable controls whether
226 * nodes also store a hash code. In some cases (e.g. strings) this
227 * may be a performance win.
229 struct _Hash_node_base
231 _Hash_node_base
* _M_nxt
;
233 _Hash_node_base() noexcept
: _M_nxt() { }
235 _Hash_node_base(_Hash_node_base
* __next
) noexcept
: _M_nxt(__next
) { }
239 * struct _Hash_node_value_base
241 * Node type with the value to store.
243 template<typename _Value
>
244 struct _Hash_node_value_base
: _Hash_node_base
246 typedef _Value value_type
;
248 __gnu_cxx::__aligned_buffer
<_Value
> _M_storage
;
252 { return _M_storage
._M_ptr(); }
255 _M_valptr() const noexcept
256 { return _M_storage
._M_ptr(); }
260 { return *_M_valptr(); }
263 _M_v() const noexcept
264 { return *_M_valptr(); }
268 * Primary template struct _Hash_node.
270 template<typename _Value
, bool _Cache_hash_code
>
274 * Specialization for nodes with caches, struct _Hash_node.
276 * Base class is __detail::_Hash_node_value_base.
278 template<typename _Value
>
279 struct _Hash_node
<_Value
, true> : _Hash_node_value_base
<_Value
>
281 std::size_t _M_hash_code
;
284 _M_next() const noexcept
285 { return static_cast<_Hash_node
*>(this->_M_nxt
); }
289 * Specialization for nodes without caches, struct _Hash_node.
291 * Base class is __detail::_Hash_node_value_base.
293 template<typename _Value
>
294 struct _Hash_node
<_Value
, false> : _Hash_node_value_base
<_Value
>
297 _M_next() const noexcept
298 { return static_cast<_Hash_node
*>(this->_M_nxt
); }
301 /// Base class for node iterators.
302 template<typename _Value
, bool _Cache_hash_code
>
303 struct _Node_iterator_base
305 using __node_type
= _Hash_node
<_Value
, _Cache_hash_code
>;
309 _Node_iterator_base(__node_type
* __p
) noexcept
314 { _M_cur
= _M_cur
->_M_next(); }
317 template<typename _Value
, bool _Cache_hash_code
>
319 operator==(const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __x
,
320 const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __y
)
322 { return __x
._M_cur
== __y
._M_cur
; }
324 template<typename _Value
, bool _Cache_hash_code
>
326 operator!=(const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __x
,
327 const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __y
)
329 { return __x
._M_cur
!= __y
._M_cur
; }
331 /// Node iterators, used to iterate through all the hashtable.
332 template<typename _Value
, bool __constant_iterators
, bool __cache
>
333 struct _Node_iterator
334 : public _Node_iterator_base
<_Value
, __cache
>
337 using __base_type
= _Node_iterator_base
<_Value
, __cache
>;
338 using __node_type
= typename
__base_type::__node_type
;
341 typedef _Value value_type
;
342 typedef std::ptrdiff_t difference_type
;
343 typedef std::forward_iterator_tag iterator_category
;
345 using pointer
= typename
std::conditional
<__constant_iterators
,
346 const _Value
*, _Value
*>::type
;
348 using reference
= typename
std::conditional
<__constant_iterators
,
349 const _Value
&, _Value
&>::type
;
351 _Node_iterator() noexcept
355 _Node_iterator(__node_type
* __p
) noexcept
356 : __base_type(__p
) { }
359 operator*() const noexcept
360 { return this->_M_cur
->_M_v(); }
363 operator->() const noexcept
364 { return this->_M_cur
->_M_valptr(); }
367 operator++() noexcept
374 operator++(int) noexcept
376 _Node_iterator
__tmp(*this);
382 /// Node const_iterators, used to iterate through all the hashtable.
383 template<typename _Value
, bool __constant_iterators
, bool __cache
>
384 struct _Node_const_iterator
385 : public _Node_iterator_base
<_Value
, __cache
>
388 using __base_type
= _Node_iterator_base
<_Value
, __cache
>;
389 using __node_type
= typename
__base_type::__node_type
;
392 typedef _Value value_type
;
393 typedef std::ptrdiff_t difference_type
;
394 typedef std::forward_iterator_tag iterator_category
;
396 typedef const _Value
* pointer
;
397 typedef const _Value
& reference
;
399 _Node_const_iterator() noexcept
403 _Node_const_iterator(__node_type
* __p
) noexcept
404 : __base_type(__p
) { }
406 _Node_const_iterator(const _Node_iterator
<_Value
, __constant_iterators
,
407 __cache
>& __x
) noexcept
408 : __base_type(__x
._M_cur
) { }
411 operator*() const noexcept
412 { return this->_M_cur
->_M_v(); }
415 operator->() const noexcept
416 { return this->_M_cur
->_M_valptr(); }
418 _Node_const_iterator
&
419 operator++() noexcept
426 operator++(int) noexcept
428 _Node_const_iterator
__tmp(*this);
434 // Many of class template _Hashtable's template parameters are policy
435 // classes. These are defaults for the policies.
437 /// Default range hashing function: use division to fold a large number
438 /// into the range [0, N).
439 struct _Mod_range_hashing
441 typedef std::size_t first_argument_type
;
442 typedef std::size_t second_argument_type
;
443 typedef std::size_t result_type
;
446 operator()(first_argument_type __num
,
447 second_argument_type __den
) const noexcept
448 { return __num
% __den
; }
451 /// Default ranged hash function H. In principle it should be a
452 /// function object composed from objects of type H1 and H2 such that
453 /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
454 /// h1 and h2. So instead we'll just use a tag to tell class template
455 /// hashtable to do that composition.
456 struct _Default_ranged_hash
{ };
458 /// Default value for rehash policy. Bucket size is (usually) the
459 /// smallest prime that keeps the load factor small enough.
460 struct _Prime_rehash_policy
462 _Prime_rehash_policy(float __z
= 1.0)
463 : _M_max_load_factor(__z
), _M_next_resize(0) { }
466 max_load_factor() const noexcept
467 { return _M_max_load_factor
; }
469 // Return a bucket size no smaller than n.
471 _M_next_bkt(std::size_t __n
) const;
473 // Return a bucket count appropriate for n elements
475 _M_bkt_for_elements(std::size_t __n
) const
476 { return __builtin_ceil(__n
/ (long double)_M_max_load_factor
); }
478 // __n_bkt is current bucket count, __n_elt is current element count,
479 // and __n_ins is number of elements to be inserted. Do we need to
480 // increase bucket count? If so, return make_pair(true, n), where n
481 // is the new bucket count. If not, return make_pair(false, 0).
482 std::pair
<bool, std::size_t>
483 _M_need_rehash(std::size_t __n_bkt
, std::size_t __n_elt
,
484 std::size_t __n_ins
) const;
486 typedef std::size_t _State
;
490 { return _M_next_resize
; }
494 { _M_next_resize
= 0; }
497 _M_reset(_State __state
)
498 { _M_next_resize
= __state
; }
500 enum { _S_n_primes
= sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
502 static const std::size_t _S_growth_factor
= 2;
504 float _M_max_load_factor
;
505 mutable std::size_t _M_next_resize
;
508 // Base classes for std::_Hashtable. We define these base classes
509 // because in some cases we want to do different things depending on
510 // the value of a policy class. In some cases the policy class
511 // affects which member functions and nested typedefs are defined;
512 // we handle that by specializing base class templates. Several of
513 // the base class templates need to access other members of class
514 // template _Hashtable, so we use a variant of the "Curiously
515 // Recurring Template Pattern" (CRTP) technique.
518 * Primary class template _Map_base.
520 * If the hashtable has a value type of the form pair<T1, T2> and a
521 * key extraction policy (_ExtractKey) that returns the first part
522 * of the pair, the hashtable gets a mapped_type typedef. If it
523 * satisfies those criteria and also has unique keys, then it also
524 * gets an operator[].
526 template<typename _Key
, typename _Value
, typename _Alloc
,
527 typename _ExtractKey
, typename _Equal
,
528 typename _H1
, typename _H2
, typename _Hash
,
529 typename _RehashPolicy
, typename _Traits
,
530 bool _Unique_keys
= _Traits::__unique_keys::value
>
531 struct _Map_base
{ };
533 /// Partial specialization, __unique_keys set to false.
534 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
535 typename _H1
, typename _H2
, typename _Hash
,
536 typename _RehashPolicy
, typename _Traits
>
537 struct _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
538 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, false>
540 using mapped_type
= typename
std::tuple_element
<1, _Pair
>::type
;
543 /// Partial specialization, __unique_keys set to true.
544 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
545 typename _H1
, typename _H2
, typename _Hash
,
546 typename _RehashPolicy
, typename _Traits
>
547 struct _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
548 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
551 using __hashtable_base
= __detail::_Hashtable_base
<_Key
, _Pair
,
553 _Equal
, _H1
, _H2
, _Hash
,
556 using __hashtable
= _Hashtable
<_Key
, _Pair
, _Alloc
,
558 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>;
560 using __hash_code
= typename
__hashtable_base::__hash_code
;
561 using __node_type
= typename
__hashtable_base::__node_type
;
564 using key_type
= typename
__hashtable_base::key_type
;
565 using iterator
= typename
__hashtable_base::iterator
;
566 using mapped_type
= typename
std::tuple_element
<1, _Pair
>::type
;
569 operator[](const key_type
& __k
);
572 operator[](key_type
&& __k
);
574 // _GLIBCXX_RESOLVE_LIB_DEFECTS
575 // DR 761. unordered_map needs an at() member function.
577 at(const key_type
& __k
);
580 at(const key_type
& __k
) const;
583 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
584 typename _H1
, typename _H2
, typename _Hash
,
585 typename _RehashPolicy
, typename _Traits
>
586 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
587 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
589 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
590 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
591 operator[](const key_type
& __k
)
593 __hashtable
* __h
= static_cast<__hashtable
*>(this);
594 __hash_code __code
= __h
->_M_hash_code(__k
);
595 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
596 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
600 __p
= __h
->_M_allocate_node(std::piecewise_construct
,
601 std::tuple
<const key_type
&>(__k
),
603 return __h
->_M_insert_unique_node(__n
, __code
, __p
)->second
;
606 return __p
->_M_v().second
;
609 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
610 typename _H1
, typename _H2
, typename _Hash
,
611 typename _RehashPolicy
, typename _Traits
>
612 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
613 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
615 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
616 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
617 operator[](key_type
&& __k
)
619 __hashtable
* __h
= static_cast<__hashtable
*>(this);
620 __hash_code __code
= __h
->_M_hash_code(__k
);
621 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
622 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
626 __p
= __h
->_M_allocate_node(std::piecewise_construct
,
627 std::forward_as_tuple(std::move(__k
)),
629 return __h
->_M_insert_unique_node(__n
, __code
, __p
)->second
;
632 return __p
->_M_v().second
;
635 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
636 typename _H1
, typename _H2
, typename _Hash
,
637 typename _RehashPolicy
, typename _Traits
>
638 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
639 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
641 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
642 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
643 at(const key_type
& __k
)
645 __hashtable
* __h
= static_cast<__hashtable
*>(this);
646 __hash_code __code
= __h
->_M_hash_code(__k
);
647 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
648 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
651 __throw_out_of_range(__N("_Map_base::at"));
652 return __p
->_M_v().second
;
655 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
656 typename _H1
, typename _H2
, typename _Hash
,
657 typename _RehashPolicy
, typename _Traits
>
658 const typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
,
659 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
660 _Traits
, true>::mapped_type
&
661 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
662 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
663 at(const key_type
& __k
) const
665 const __hashtable
* __h
= static_cast<const __hashtable
*>(this);
666 __hash_code __code
= __h
->_M_hash_code(__k
);
667 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
668 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
671 __throw_out_of_range(__N("_Map_base::at"));
672 return __p
->_M_v().second
;
676 * Primary class template _Insert_base.
678 * insert member functions appropriate to all _Hashtables.
680 template<typename _Key
, typename _Value
, typename _Alloc
,
681 typename _ExtractKey
, typename _Equal
,
682 typename _H1
, typename _H2
, typename _Hash
,
683 typename _RehashPolicy
, typename _Traits
>
687 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
688 _Equal
, _H1
, _H2
, _Hash
,
689 _RehashPolicy
, _Traits
>;
691 using __hashtable_base
= _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
692 _Equal
, _H1
, _H2
, _Hash
,
695 using value_type
= typename
__hashtable_base::value_type
;
696 using iterator
= typename
__hashtable_base::iterator
;
697 using const_iterator
= typename
__hashtable_base::const_iterator
;
698 using size_type
= typename
__hashtable_base::size_type
;
700 using __unique_keys
= typename
__hashtable_base::__unique_keys
;
701 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
702 using __node_type
= _Hash_node
<_Value
, _Traits::__hash_cached::value
>;
703 using __node_alloc_type
=
704 typename __alloctr_rebind
<_Alloc
, __node_type
>::__type
;
705 using __node_gen_type
= _AllocNode
<__node_alloc_type
>;
708 _M_conjure_hashtable()
709 { return *(static_cast<__hashtable
*>(this)); }
711 template<typename _InputIterator
, typename _NodeGetter
>
713 _M_insert_range(_InputIterator __first
, _InputIterator __last
,
718 insert(const value_type
& __v
)
720 __hashtable
& __h
= _M_conjure_hashtable();
721 __node_gen_type
__node_gen(__h
);
722 return __h
._M_insert(__v
, __node_gen
, __unique_keys());
726 insert(const_iterator __hint
, const value_type
& __v
)
728 __hashtable
& __h
= _M_conjure_hashtable();
729 __node_gen_type
__node_gen(__h
);
730 return __h
._M_insert(__hint
, __v
, __node_gen
, __unique_keys());
734 insert(initializer_list
<value_type
> __l
)
735 { this->insert(__l
.begin(), __l
.end()); }
737 template<typename _InputIterator
>
739 insert(_InputIterator __first
, _InputIterator __last
)
741 __hashtable
& __h
= _M_conjure_hashtable();
742 __node_gen_type
__node_gen(__h
);
743 return _M_insert_range(__first
, __last
, __node_gen
);
747 template<typename _Key
, typename _Value
, typename _Alloc
,
748 typename _ExtractKey
, typename _Equal
,
749 typename _H1
, typename _H2
, typename _Hash
,
750 typename _RehashPolicy
, typename _Traits
>
751 template<typename _InputIterator
, typename _NodeGetter
>
753 _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
754 _RehashPolicy
, _Traits
>::
755 _M_insert_range(_InputIterator __first
, _InputIterator __last
,
756 const _NodeGetter
& __node_gen
)
758 using __rehash_type
= typename
__hashtable::__rehash_type
;
759 using __rehash_state
= typename
__hashtable::__rehash_state
;
760 using pair_type
= std::pair
<bool, std::size_t>;
762 size_type __n_elt
= __detail::__distance_fw(__first
, __last
);
764 __hashtable
& __h
= _M_conjure_hashtable();
765 __rehash_type
& __rehash
= __h
._M_rehash_policy
;
766 const __rehash_state
& __saved_state
= __rehash
._M_state();
767 pair_type __do_rehash
= __rehash
._M_need_rehash(__h
._M_bucket_count
,
768 __h
._M_element_count
,
771 if (__do_rehash
.first
)
772 __h
._M_rehash(__do_rehash
.second
, __saved_state
);
774 for (; __first
!= __last
; ++__first
)
775 __h
._M_insert(*__first
, __node_gen
, __unique_keys());
779 * Primary class template _Insert.
781 * Select insert member functions appropriate to _Hashtable policy choices.
783 template<typename _Key
, typename _Value
, typename _Alloc
,
784 typename _ExtractKey
, typename _Equal
,
785 typename _H1
, typename _H2
, typename _Hash
,
786 typename _RehashPolicy
, typename _Traits
,
787 bool _Constant_iterators
= _Traits::__constant_iterators::value
,
788 bool _Unique_keys
= _Traits::__unique_keys::value
>
792 template<typename _Key
, typename _Value
, typename _Alloc
,
793 typename _ExtractKey
, typename _Equal
,
794 typename _H1
, typename _H2
, typename _Hash
,
795 typename _RehashPolicy
, typename _Traits
>
796 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
797 _RehashPolicy
, _Traits
, true, true>
798 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
799 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
801 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
802 _Equal
, _H1
, _H2
, _Hash
,
803 _RehashPolicy
, _Traits
>;
804 using value_type
= typename
__base_type::value_type
;
805 using iterator
= typename
__base_type::iterator
;
806 using const_iterator
= typename
__base_type::const_iterator
;
808 using __unique_keys
= typename
__base_type::__unique_keys
;
809 using __hashtable
= typename
__base_type::__hashtable
;
810 using __node_gen_type
= typename
__base_type::__node_gen_type
;
812 using __base_type::insert
;
814 std::pair
<iterator
, bool>
815 insert(value_type
&& __v
)
817 __hashtable
& __h
= this->_M_conjure_hashtable();
818 __node_gen_type
__node_gen(__h
);
819 return __h
._M_insert(std::move(__v
), __node_gen
, __unique_keys());
823 insert(const_iterator __hint
, value_type
&& __v
)
825 __hashtable
& __h
= this->_M_conjure_hashtable();
826 __node_gen_type
__node_gen(__h
);
827 return __h
._M_insert(__hint
, std::move(__v
), __node_gen
,
833 template<typename _Key
, typename _Value
, typename _Alloc
,
834 typename _ExtractKey
, typename _Equal
,
835 typename _H1
, typename _H2
, typename _Hash
,
836 typename _RehashPolicy
, typename _Traits
>
837 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
838 _RehashPolicy
, _Traits
, true, false>
839 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
840 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
842 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
843 _Equal
, _H1
, _H2
, _Hash
,
844 _RehashPolicy
, _Traits
>;
845 using value_type
= typename
__base_type::value_type
;
846 using iterator
= typename
__base_type::iterator
;
847 using const_iterator
= typename
__base_type::const_iterator
;
849 using __unique_keys
= typename
__base_type::__unique_keys
;
850 using __hashtable
= typename
__base_type::__hashtable
;
851 using __node_gen_type
= typename
__base_type::__node_gen_type
;
853 using __base_type::insert
;
856 insert(value_type
&& __v
)
858 __hashtable
& __h
= this->_M_conjure_hashtable();
859 __node_gen_type
__node_gen(__h
);
860 return __h
._M_insert(std::move(__v
), __node_gen
, __unique_keys());
864 insert(const_iterator __hint
, value_type
&& __v
)
866 __hashtable
& __h
= this->_M_conjure_hashtable();
867 __node_gen_type
__node_gen(__h
);
868 return __h
._M_insert(__hint
, std::move(__v
), __node_gen
,
874 template<typename _Key
, typename _Value
, typename _Alloc
,
875 typename _ExtractKey
, typename _Equal
,
876 typename _H1
, typename _H2
, typename _Hash
,
877 typename _RehashPolicy
, typename _Traits
, bool _Unique_keys
>
878 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
879 _RehashPolicy
, _Traits
, false, _Unique_keys
>
880 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
881 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
883 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
884 _Equal
, _H1
, _H2
, _Hash
,
885 _RehashPolicy
, _Traits
>;
886 using value_type
= typename
__base_type::value_type
;
887 using iterator
= typename
__base_type::iterator
;
888 using const_iterator
= typename
__base_type::const_iterator
;
890 using __unique_keys
= typename
__base_type::__unique_keys
;
891 using __hashtable
= typename
__base_type::__hashtable
;
892 using __ireturn_type
= typename
__base_type::__ireturn_type
;
894 using __base_type::insert
;
896 template<typename _Pair
>
897 using __is_cons
= std::is_constructible
<value_type
, _Pair
&&>;
899 template<typename _Pair
>
900 using _IFcons
= std::enable_if
<__is_cons
<_Pair
>::value
>;
902 template<typename _Pair
>
903 using _IFconsp
= typename _IFcons
<_Pair
>::type
;
905 template<typename _Pair
, typename
= _IFconsp
<_Pair
>>
909 __hashtable
& __h
= this->_M_conjure_hashtable();
910 return __h
._M_emplace(__unique_keys(), std::forward
<_Pair
>(__v
));
913 template<typename _Pair
, typename
= _IFconsp
<_Pair
>>
915 insert(const_iterator __hint
, _Pair
&& __v
)
917 __hashtable
& __h
= this->_M_conjure_hashtable();
918 return __h
._M_emplace(__hint
, __unique_keys(),
919 std::forward
<_Pair
>(__v
));
924 * Primary class template _Rehash_base.
926 * Give hashtable the max_load_factor functions and reserve iff the
927 * rehash policy is _Prime_rehash_policy.
929 template<typename _Key
, typename _Value
, typename _Alloc
,
930 typename _ExtractKey
, typename _Equal
,
931 typename _H1
, typename _H2
, typename _Hash
,
932 typename _RehashPolicy
, typename _Traits
>
936 template<typename _Key
, typename _Value
, typename _Alloc
,
937 typename _ExtractKey
, typename _Equal
,
938 typename _H1
, typename _H2
, typename _Hash
, typename _Traits
>
939 struct _Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
940 _H1
, _H2
, _Hash
, _Prime_rehash_policy
, _Traits
>
942 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
943 _Equal
, _H1
, _H2
, _Hash
,
944 _Prime_rehash_policy
, _Traits
>;
947 max_load_factor() const noexcept
949 const __hashtable
* __this
= static_cast<const __hashtable
*>(this);
950 return __this
->__rehash_policy().max_load_factor();
954 max_load_factor(float __z
)
956 __hashtable
* __this
= static_cast<__hashtable
*>(this);
957 __this
->__rehash_policy(_Prime_rehash_policy(__z
));
961 reserve(std::size_t __n
)
963 __hashtable
* __this
= static_cast<__hashtable
*>(this);
964 __this
->rehash(__builtin_ceil(__n
/ max_load_factor()));
969 * Primary class template _Hashtable_ebo_helper.
971 * Helper class using EBO when it is not forbidden (the type is not
972 * final) and when it is worth it (the type is empty.)
974 template<int _Nm
, typename _Tp
,
975 bool __use_ebo
= !__is_final(_Tp
) && __is_empty(_Tp
)>
976 struct _Hashtable_ebo_helper
;
978 /// Specialization using EBO.
979 template<int _Nm
, typename _Tp
>
980 struct _Hashtable_ebo_helper
<_Nm
, _Tp
, true>
983 _Hashtable_ebo_helper() = default;
985 template<typename _OtherTp
>
986 _Hashtable_ebo_helper(_OtherTp
&& __tp
)
987 : _Tp(std::forward
<_OtherTp
>(__tp
))
991 _S_cget(const _Hashtable_ebo_helper
& __eboh
)
992 { return static_cast<const _Tp
&>(__eboh
); }
995 _S_get(_Hashtable_ebo_helper
& __eboh
)
996 { return static_cast<_Tp
&>(__eboh
); }
999 /// Specialization not using EBO.
1000 template<int _Nm
, typename _Tp
>
1001 struct _Hashtable_ebo_helper
<_Nm
, _Tp
, false>
1003 _Hashtable_ebo_helper() = default;
1005 template<typename _OtherTp
>
1006 _Hashtable_ebo_helper(_OtherTp
&& __tp
)
1007 : _M_tp(std::forward
<_OtherTp
>(__tp
))
1011 _S_cget(const _Hashtable_ebo_helper
& __eboh
)
1012 { return __eboh
._M_tp
; }
1015 _S_get(_Hashtable_ebo_helper
& __eboh
)
1016 { return __eboh
._M_tp
; }
1023 * Primary class template _Local_iterator_base.
1025 * Base class for local iterators, used to iterate within a bucket
1026 * but not between buckets.
1028 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1029 typename _H1
, typename _H2
, typename _Hash
,
1030 bool __cache_hash_code
>
1031 struct _Local_iterator_base
;
1034 * Primary class template _Hash_code_base.
1036 * Encapsulates two policy issues that aren't quite orthogonal.
1037 * (1) the difference between using a ranged hash function and using
1038 * the combination of a hash function and a range-hashing function.
1039 * In the former case we don't have such things as hash codes, so
1040 * we have a dummy type as placeholder.
1041 * (2) Whether or not we cache hash codes. Caching hash codes is
1042 * meaningless if we have a ranged hash function.
1044 * We also put the key extraction objects here, for convenience.
1045 * Each specialization derives from one or more of the template
1046 * parameters to benefit from Ebo. This is important as this type
1047 * is inherited in some cases by the _Local_iterator_base type used
1048 * to implement local_iterator and const_local_iterator. As with
1049 * any iterator type we prefer to make it as small as possible.
1051 * Primary template is unused except as a hook for specializations.
1053 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1054 typename _H1
, typename _H2
, typename _Hash
,
1055 bool __cache_hash_code
>
1056 struct _Hash_code_base
;
1058 /// Specialization: ranged hash function, no caching hash codes. H1
1059 /// and H2 are provided but ignored. We define a dummy hash code type.
1060 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1061 typename _H1
, typename _H2
, typename _Hash
>
1062 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
, false>
1063 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1064 private _Hashtable_ebo_helper
<1, _Hash
>
1067 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1068 using __ebo_hash
= _Hashtable_ebo_helper
<1, _Hash
>;
1071 typedef void* __hash_code
;
1072 typedef _Hash_node
<_Value
, false> __node_type
;
1074 // We need the default constructor for the local iterators.
1075 _Hash_code_base() = default;
1077 _Hash_code_base(const _ExtractKey
& __ex
, const _H1
&, const _H2
&,
1079 : __ebo_extract_key(__ex
), __ebo_hash(__h
) { }
1082 _M_hash_code(const _Key
& __key
) const
1086 _M_bucket_index(const _Key
& __k
, __hash_code
, std::size_t __n
) const
1087 { return _M_ranged_hash()(__k
, __n
); }
1090 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1091 noexcept( noexcept(declval
<const _Hash
&>()(declval
<const _Key
&>(), (std::size_t)0)) )
1092 { return _M_ranged_hash()(_M_extract()(__p
->_M_v()), __n
); }
1095 _M_store_code(__node_type
*, __hash_code
) const
1099 _M_copy_code(__node_type
*, const __node_type
*) const
1103 _M_swap(_Hash_code_base
& __x
)
1105 std::swap(_M_extract(), __x
._M_extract());
1106 std::swap(_M_ranged_hash(), __x
._M_ranged_hash());
1110 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1113 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1116 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
1119 _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
1122 // No specialization for ranged hash function while caching hash codes.
1123 // That combination is meaningless, and trying to do it is an error.
1125 /// Specialization: ranged hash function, cache hash codes. This
1126 /// combination is meaningless, so we provide only a declaration
1127 /// and no definition.
1128 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1129 typename _H1
, typename _H2
, typename _Hash
>
1130 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
, true>;
1132 /// Specialization: hash function and range-hashing function, no
1133 /// caching of hash codes.
1134 /// Provides typedef and accessor required by C++ 11.
1135 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1136 typename _H1
, typename _H2
>
1137 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1138 _Default_ranged_hash
, false>
1139 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1140 private _Hashtable_ebo_helper
<1, _H1
>,
1141 private _Hashtable_ebo_helper
<2, _H2
>
1144 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1145 using __ebo_h1
= _Hashtable_ebo_helper
<1, _H1
>;
1146 using __ebo_h2
= _Hashtable_ebo_helper
<2, _H2
>;
1152 hash_function() const
1156 typedef std::size_t __hash_code
;
1157 typedef _Hash_node
<_Value
, false> __node_type
;
1159 // We need the default constructor for the local iterators.
1160 _Hash_code_base() = default;
1162 _Hash_code_base(const _ExtractKey
& __ex
,
1163 const _H1
& __h1
, const _H2
& __h2
,
1164 const _Default_ranged_hash
&)
1165 : __ebo_extract_key(__ex
), __ebo_h1(__h1
), __ebo_h2(__h2
) { }
1168 _M_hash_code(const _Key
& __k
) const
1169 { return _M_h1()(__k
); }
1172 _M_bucket_index(const _Key
&, __hash_code __c
, std::size_t __n
) const
1173 { return _M_h2()(__c
, __n
); }
1176 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1177 noexcept( noexcept(declval
<const _H1
&>()(declval
<const _Key
&>()))
1178 && noexcept(declval
<const _H2
&>()((__hash_code
)0, (std::size_t)0)) )
1179 { return _M_h2()(_M_h1()(_M_extract()(__p
->_M_v())), __n
); }
1182 _M_store_code(__node_type
*, __hash_code
) const
1186 _M_copy_code(__node_type
*, const __node_type
*) const
1190 _M_swap(_Hash_code_base
& __x
)
1192 std::swap(_M_extract(), __x
._M_extract());
1193 std::swap(_M_h1(), __x
._M_h1());
1194 std::swap(_M_h2(), __x
._M_h2());
1198 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1201 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1204 _M_h1() const { return __ebo_h1::_S_cget(*this); }
1207 _M_h1() { return __ebo_h1::_S_get(*this); }
1210 _M_h2() const { return __ebo_h2::_S_cget(*this); }
1213 _M_h2() { return __ebo_h2::_S_get(*this); }
1216 /// Specialization: hash function and range-hashing function,
1217 /// caching hash codes. H is provided but ignored. Provides
1218 /// typedef and accessor required by C++ 11.
1219 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1220 typename _H1
, typename _H2
>
1221 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1222 _Default_ranged_hash
, true>
1223 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1224 private _Hashtable_ebo_helper
<1, _H1
>,
1225 private _Hashtable_ebo_helper
<2, _H2
>
1228 // Gives access to _M_h2() to the local iterator implementation.
1229 friend struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1230 _Default_ranged_hash
, true>;
1232 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1233 using __ebo_h1
= _Hashtable_ebo_helper
<1, _H1
>;
1234 using __ebo_h2
= _Hashtable_ebo_helper
<2, _H2
>;
1240 hash_function() const
1244 typedef std::size_t __hash_code
;
1245 typedef _Hash_node
<_Value
, true> __node_type
;
1247 _Hash_code_base(const _ExtractKey
& __ex
,
1248 const _H1
& __h1
, const _H2
& __h2
,
1249 const _Default_ranged_hash
&)
1250 : __ebo_extract_key(__ex
), __ebo_h1(__h1
), __ebo_h2(__h2
) { }
1253 _M_hash_code(const _Key
& __k
) const
1254 { return _M_h1()(__k
); }
1257 _M_bucket_index(const _Key
&, __hash_code __c
,
1258 std::size_t __n
) const
1259 { return _M_h2()(__c
, __n
); }
1262 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1263 noexcept( noexcept(declval
<const _H2
&>()((__hash_code
)0,
1265 { return _M_h2()(__p
->_M_hash_code
, __n
); }
1268 _M_store_code(__node_type
* __n
, __hash_code __c
) const
1269 { __n
->_M_hash_code
= __c
; }
1272 _M_copy_code(__node_type
* __to
, const __node_type
* __from
) const
1273 { __to
->_M_hash_code
= __from
->_M_hash_code
; }
1276 _M_swap(_Hash_code_base
& __x
)
1278 std::swap(_M_extract(), __x
._M_extract());
1279 std::swap(_M_h1(), __x
._M_h1());
1280 std::swap(_M_h2(), __x
._M_h2());
1284 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1287 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1290 _M_h1() const { return __ebo_h1::_S_cget(*this); }
1293 _M_h1() { return __ebo_h1::_S_get(*this); }
1296 _M_h2() const { return __ebo_h2::_S_cget(*this); }
1299 _M_h2() { return __ebo_h2::_S_get(*this); }
1303 * Primary class template _Equal_helper.
1306 template <typename _Key
, typename _Value
, typename _ExtractKey
,
1307 typename _Equal
, typename _HashCodeType
,
1308 bool __cache_hash_code
>
1309 struct _Equal_helper
;
1312 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1313 typename _Equal
, typename _HashCodeType
>
1314 struct _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
, _HashCodeType
, true>
1317 _S_equals(const _Equal
& __eq
, const _ExtractKey
& __extract
,
1318 const _Key
& __k
, _HashCodeType __c
, _Hash_node
<_Value
, true>* __n
)
1319 { return __c
== __n
->_M_hash_code
&& __eq(__k
, __extract(__n
->_M_v())); }
1323 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1324 typename _Equal
, typename _HashCodeType
>
1325 struct _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
, _HashCodeType
, false>
1328 _S_equals(const _Equal
& __eq
, const _ExtractKey
& __extract
,
1329 const _Key
& __k
, _HashCodeType
, _Hash_node
<_Value
, false>* __n
)
1330 { return __eq(__k
, __extract(__n
->_M_v())); }
1335 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1336 typename _H1
, typename _H2
, typename _Hash
>
1337 struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1338 _H1
, _H2
, _Hash
, true>
1339 : private _Hashtable_ebo_helper
<0, _H2
>
1342 using __base_type
= _Hashtable_ebo_helper
<0, _H2
>;
1343 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1344 _H1
, _H2
, _Hash
, true>;
1347 _Local_iterator_base() = default;
1348 _Local_iterator_base(const __hash_code_base
& __base
,
1349 _Hash_node
<_Value
, true>* __p
,
1350 std::size_t __bkt
, std::size_t __bkt_count
)
1351 : __base_type(__base
._M_h2()),
1352 _M_cur(__p
), _M_bucket(__bkt
), _M_bucket_count(__bkt_count
) { }
1357 _M_cur
= _M_cur
->_M_next();
1361 = __base_type::_S_get(*this)(_M_cur
->_M_hash_code
,
1363 if (__bkt
!= _M_bucket
)
1368 _Hash_node
<_Value
, true>* _M_cur
;
1369 std::size_t _M_bucket
;
1370 std::size_t _M_bucket_count
;
1374 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1375 typename _H1
, typename _H2
, typename _Hash
>
1376 struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1377 _H1
, _H2
, _Hash
, false>
1378 : private _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1379 _H1
, _H2
, _Hash
, false>
1382 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1383 _H1
, _H2
, _Hash
, false>;
1386 _Local_iterator_base() = default;
1387 _Local_iterator_base(const __hash_code_base
& __base
,
1388 _Hash_node
<_Value
, false>* __p
,
1389 std::size_t __bkt
, std::size_t __bkt_count
)
1390 : __hash_code_base(__base
),
1391 _M_cur(__p
), _M_bucket(__bkt
), _M_bucket_count(__bkt_count
) { }
1396 _M_cur
= _M_cur
->_M_next();
1399 std::size_t __bkt
= this->_M_bucket_index(_M_cur
, _M_bucket_count
);
1400 if (__bkt
!= _M_bucket
)
1405 _Hash_node
<_Value
, false>* _M_cur
;
1406 std::size_t _M_bucket
;
1407 std::size_t _M_bucket_count
;
1410 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1411 typename _H1
, typename _H2
, typename _Hash
, bool __cache
>
1413 operator==(const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1414 _H1
, _H2
, _Hash
, __cache
>& __x
,
1415 const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1416 _H1
, _H2
, _Hash
, __cache
>& __y
)
1417 { return __x
._M_cur
== __y
._M_cur
; }
1419 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1420 typename _H1
, typename _H2
, typename _Hash
, bool __cache
>
1422 operator!=(const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1423 _H1
, _H2
, _Hash
, __cache
>& __x
,
1424 const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1425 _H1
, _H2
, _Hash
, __cache
>& __y
)
1426 { return __x
._M_cur
!= __y
._M_cur
; }
1429 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1430 typename _H1
, typename _H2
, typename _Hash
,
1431 bool __constant_iterators
, bool __cache
>
1432 struct _Local_iterator
1433 : public _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1434 _H1
, _H2
, _Hash
, __cache
>
1437 using __base_type
= _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1438 _H1
, _H2
, _Hash
, __cache
>;
1439 using __hash_code_base
= typename
__base_type::__hash_code_base
;
1441 typedef _Value value_type
;
1442 typedef typename
std::conditional
<__constant_iterators
,
1443 const _Value
*, _Value
*>::type
1445 typedef typename
std::conditional
<__constant_iterators
,
1446 const _Value
&, _Value
&>::type
1448 typedef std::ptrdiff_t difference_type
;
1449 typedef std::forward_iterator_tag iterator_category
;
1451 _Local_iterator() = default;
1453 _Local_iterator(const __hash_code_base
& __base
,
1454 _Hash_node
<_Value
, __cache
>* __p
,
1455 std::size_t __bkt
, std::size_t __bkt_count
)
1456 : __base_type(__base
, __p
, __bkt
, __bkt_count
)
1461 { return this->_M_cur
->_M_v(); }
1465 { return this->_M_cur
->_M_valptr(); }
1477 _Local_iterator
__tmp(*this);
1483 /// local const_iterators
1484 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1485 typename _H1
, typename _H2
, typename _Hash
,
1486 bool __constant_iterators
, bool __cache
>
1487 struct _Local_const_iterator
1488 : public _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1489 _H1
, _H2
, _Hash
, __cache
>
1492 using __base_type
= _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1493 _H1
, _H2
, _Hash
, __cache
>;
1494 using __hash_code_base
= typename
__base_type::__hash_code_base
;
1497 typedef _Value value_type
;
1498 typedef const _Value
* pointer
;
1499 typedef const _Value
& reference
;
1500 typedef std::ptrdiff_t difference_type
;
1501 typedef std::forward_iterator_tag iterator_category
;
1503 _Local_const_iterator() = default;
1505 _Local_const_iterator(const __hash_code_base
& __base
,
1506 _Hash_node
<_Value
, __cache
>* __p
,
1507 std::size_t __bkt
, std::size_t __bkt_count
)
1508 : __base_type(__base
, __p
, __bkt
, __bkt_count
)
1511 _Local_const_iterator(const _Local_iterator
<_Key
, _Value
, _ExtractKey
,
1513 __constant_iterators
,
1520 { return this->_M_cur
->_M_v(); }
1524 { return this->_M_cur
->_M_valptr(); }
1526 _Local_const_iterator
&
1533 _Local_const_iterator
1536 _Local_const_iterator
__tmp(*this);
1543 * Primary class template _Hashtable_base.
1545 * Helper class adding management of _Equal functor to
1546 * _Hash_code_base type.
1548 * Base class templates are:
1549 * - __detail::_Hash_code_base
1550 * - __detail::_Hashtable_ebo_helper
1552 template<typename _Key
, typename _Value
,
1553 typename _ExtractKey
, typename _Equal
,
1554 typename _H1
, typename _H2
, typename _Hash
, typename _Traits
>
1555 struct _Hashtable_base
1556 : public _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
,
1557 _Traits::__hash_cached::value
>,
1558 private _Hashtable_ebo_helper
<0, _Equal
>
1561 typedef _Key key_type
;
1562 typedef _Value value_type
;
1563 typedef _Equal key_equal
;
1564 typedef std::size_t size_type
;
1565 typedef std::ptrdiff_t difference_type
;
1567 using __traits_type
= _Traits
;
1568 using __hash_cached
= typename
__traits_type::__hash_cached
;
1569 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
1570 using __unique_keys
= typename
__traits_type::__unique_keys
;
1572 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1574 __hash_cached::value
>;
1576 using __hash_code
= typename
__hash_code_base::__hash_code
;
1577 using __node_type
= typename
__hash_code_base::__node_type
;
1579 using iterator
= __detail::_Node_iterator
<value_type
,
1580 __constant_iterators::value
,
1581 __hash_cached::value
>;
1583 using const_iterator
= __detail::_Node_const_iterator
<value_type
,
1584 __constant_iterators::value
,
1585 __hash_cached::value
>;
1587 using local_iterator
= __detail::_Local_iterator
<key_type
, value_type
,
1588 _ExtractKey
, _H1
, _H2
, _Hash
,
1589 __constant_iterators::value
,
1590 __hash_cached::value
>;
1592 using const_local_iterator
= __detail::_Local_const_iterator
<key_type
,
1594 _ExtractKey
, _H1
, _H2
, _Hash
,
1595 __constant_iterators::value
,
1596 __hash_cached::value
>;
1598 using __ireturn_type
= typename
std::conditional
<__unique_keys::value
,
1599 std::pair
<iterator
, bool>,
1602 using _EqualEBO
= _Hashtable_ebo_helper
<0, _Equal
>;
1603 using _EqualHelper
= _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
,
1604 __hash_code
, __hash_cached::value
>;
1607 _Hashtable_base(const _ExtractKey
& __ex
, const _H1
& __h1
, const _H2
& __h2
,
1608 const _Hash
& __hash
, const _Equal
& __eq
)
1609 : __hash_code_base(__ex
, __h1
, __h2
, __hash
), _EqualEBO(__eq
)
1613 _M_equals(const _Key
& __k
, __hash_code __c
, __node_type
* __n
) const
1615 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1620 _M_swap(_Hashtable_base
& __x
)
1622 __hash_code_base::_M_swap(__x
);
1623 std::swap(_M_eq(), __x
._M_eq());
1627 _M_eq() const { return _EqualEBO::_S_cget(*this); }
1630 _M_eq() { return _EqualEBO::_S_get(*this); }
1634 * struct _Equality_base.
1636 * Common types and functions for class _Equality.
1638 struct _Equality_base
1641 template<typename _Uiterator
>
1643 _S_is_permutation(_Uiterator
, _Uiterator
, _Uiterator
);
1646 // See std::is_permutation in N3068.
1647 template<typename _Uiterator
>
1650 _S_is_permutation(_Uiterator __first1
, _Uiterator __last1
,
1651 _Uiterator __first2
)
1653 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
1654 if (!(*__first1
== *__first2
))
1657 if (__first1
== __last1
)
1660 _Uiterator __last2
= __first2
;
1661 std::advance(__last2
, std::distance(__first1
, __last1
));
1663 for (_Uiterator __it1
= __first1
; __it1
!= __last1
; ++__it1
)
1665 _Uiterator __tmp
= __first1
;
1666 while (__tmp
!= __it1
&& !bool(*__tmp
== *__it1
))
1669 // We've seen this one before.
1673 std::ptrdiff_t __n2
= 0;
1674 for (__tmp
= __first2
; __tmp
!= __last2
; ++__tmp
)
1675 if (*__tmp
== *__it1
)
1681 std::ptrdiff_t __n1
= 0;
1682 for (__tmp
= __it1
; __tmp
!= __last1
; ++__tmp
)
1683 if (*__tmp
== *__it1
)
1693 * Primary class template _Equality.
1695 * This is for implementing equality comparison for unordered
1696 * containers, per N3068, by John Lakos and Pablo Halpern.
1697 * Algorithmically, we follow closely the reference implementations
1700 template<typename _Key
, typename _Value
, typename _Alloc
,
1701 typename _ExtractKey
, typename _Equal
,
1702 typename _H1
, typename _H2
, typename _Hash
,
1703 typename _RehashPolicy
, typename _Traits
,
1704 bool _Unique_keys
= _Traits::__unique_keys::value
>
1708 template<typename _Key
, typename _Value
, typename _Alloc
,
1709 typename _ExtractKey
, typename _Equal
,
1710 typename _H1
, typename _H2
, typename _Hash
,
1711 typename _RehashPolicy
, typename _Traits
>
1712 struct _Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1713 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
1715 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1716 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>;
1719 _M_equal(const __hashtable
&) const;
1722 template<typename _Key
, typename _Value
, typename _Alloc
,
1723 typename _ExtractKey
, typename _Equal
,
1724 typename _H1
, typename _H2
, typename _Hash
,
1725 typename _RehashPolicy
, typename _Traits
>
1727 _Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1728 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
1729 _M_equal(const __hashtable
& __other
) const
1731 const __hashtable
* __this
= static_cast<const __hashtable
*>(this);
1733 if (__this
->size() != __other
.size())
1736 for (auto __itx
= __this
->begin(); __itx
!= __this
->end(); ++__itx
)
1738 const auto __ity
= __other
.find(_ExtractKey()(*__itx
));
1739 if (__ity
== __other
.end() || !bool(*__ity
== *__itx
))
1746 template<typename _Key
, typename _Value
, typename _Alloc
,
1747 typename _ExtractKey
, typename _Equal
,
1748 typename _H1
, typename _H2
, typename _Hash
,
1749 typename _RehashPolicy
, typename _Traits
>
1750 struct _Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1751 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, false>
1752 : public _Equality_base
1754 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1755 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>;
1758 _M_equal(const __hashtable
&) const;
1761 template<typename _Key
, typename _Value
, typename _Alloc
,
1762 typename _ExtractKey
, typename _Equal
,
1763 typename _H1
, typename _H2
, typename _Hash
,
1764 typename _RehashPolicy
, typename _Traits
>
1766 _Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1767 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, false>::
1768 _M_equal(const __hashtable
& __other
) const
1770 const __hashtable
* __this
= static_cast<const __hashtable
*>(this);
1772 if (__this
->size() != __other
.size())
1775 for (auto __itx
= __this
->begin(); __itx
!= __this
->end();)
1777 const auto __xrange
= __this
->equal_range(_ExtractKey()(*__itx
));
1778 const auto __yrange
= __other
.equal_range(_ExtractKey()(*__itx
));
1780 if (std::distance(__xrange
.first
, __xrange
.second
)
1781 != std::distance(__yrange
.first
, __yrange
.second
))
1784 if (!_S_is_permutation(__xrange
.first
, __xrange
.second
,
1788 __itx
= __xrange
.second
;
1794 * This type deals with all allocation and keeps an allocator instance through
1795 * inheritance to benefit from EBO when possible.
1797 template<typename _NodeAlloc
>
1798 struct _Hashtable_alloc
: private _Hashtable_ebo_helper
<0, _NodeAlloc
>
1801 using __ebo_node_alloc
= _Hashtable_ebo_helper
<0, _NodeAlloc
>;
1803 using __node_type
= typename
_NodeAlloc::value_type
;
1804 using __node_alloc_type
= _NodeAlloc
;
1805 // Use __gnu_cxx to benefit from _S_always_equal and al.
1806 using __node_alloc_traits
= __gnu_cxx::__alloc_traits
<__node_alloc_type
>;
1808 using __value_type
= typename
__node_type::value_type
;
1809 using __value_alloc_type
=
1810 typename __alloctr_rebind
<__node_alloc_type
, __value_type
>::__type
;
1811 using __value_alloc_traits
= std::allocator_traits
<__value_alloc_type
>;
1813 using __node_base
= __detail::_Hash_node_base
;
1814 using __bucket_type
= __node_base
*;
1815 using __bucket_alloc_type
=
1816 typename __alloctr_rebind
<__node_alloc_type
, __bucket_type
>::__type
;
1817 using __bucket_alloc_traits
= std::allocator_traits
<__bucket_alloc_type
>;
1819 _Hashtable_alloc(const _Hashtable_alloc
&) = default;
1820 _Hashtable_alloc(_Hashtable_alloc
&&) = default;
1822 template<typename _Alloc
>
1823 _Hashtable_alloc(_Alloc
&& __a
)
1824 : __ebo_node_alloc(std::forward
<_Alloc
>(__a
))
1829 { return __ebo_node_alloc::_S_get(*this); }
1831 const __node_alloc_type
&
1832 _M_node_allocator() const
1833 { return __ebo_node_alloc::_S_cget(*this); }
1835 template<typename
... _Args
>
1837 _M_allocate_node(_Args
&&... __args
);
1840 _M_deallocate_node(__node_type
* __n
);
1842 // Deallocate the linked list of nodes pointed to by __n
1844 _M_deallocate_nodes(__node_type
* __n
);
1847 _M_allocate_buckets(std::size_t __n
);
1850 _M_deallocate_buckets(__bucket_type
*, std::size_t __n
);
1853 // Definitions of class template _Hashtable_alloc's out-of-line member
1855 template<typename _NodeAlloc
>
1856 template<typename
... _Args
>
1857 typename _Hashtable_alloc
<_NodeAlloc
>::__node_type
*
1858 _Hashtable_alloc
<_NodeAlloc
>::_M_allocate_node(_Args
&&... __args
)
1860 auto __nptr
= __node_alloc_traits::allocate(_M_node_allocator(), 1);
1861 __node_type
* __n
= std::__addressof(*__nptr
);
1864 __value_alloc_type
__a(_M_node_allocator());
1865 ::new ((void*)__n
) __node_type();
1866 __value_alloc_traits::construct(__a
, __n
->_M_valptr(),
1867 std::forward
<_Args
>(__args
)...);
1872 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr
, 1);
1873 __throw_exception_again
;
1877 template<typename _NodeAlloc
>
1879 _Hashtable_alloc
<_NodeAlloc
>::_M_deallocate_node(__node_type
* __n
)
1881 typedef typename
__node_alloc_traits::pointer _Ptr
;
1882 auto __ptr
= std::pointer_traits
<_Ptr
>::pointer_to(*__n
);
1883 __value_alloc_type
__a(_M_node_allocator());
1884 __value_alloc_traits::destroy(__a
, __n
->_M_valptr());
1885 __n
->~__node_type();
1886 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr
, 1);
1889 template<typename _NodeAlloc
>
1891 _Hashtable_alloc
<_NodeAlloc
>::_M_deallocate_nodes(__node_type
* __n
)
1895 __node_type
* __tmp
= __n
;
1896 __n
= __n
->_M_next();
1897 _M_deallocate_node(__tmp
);
1901 template<typename _NodeAlloc
>
1902 typename _Hashtable_alloc
<_NodeAlloc
>::__bucket_type
*
1903 _Hashtable_alloc
<_NodeAlloc
>::_M_allocate_buckets(std::size_t __n
)
1905 __bucket_alloc_type
__alloc(_M_node_allocator());
1907 auto __ptr
= __bucket_alloc_traits::allocate(__alloc
, __n
);
1908 __bucket_type
* __p
= std::__addressof(*__ptr
);
1909 __builtin_memset(__p
, 0, __n
* sizeof(__bucket_type
));
1913 template<typename _NodeAlloc
>
1915 _Hashtable_alloc
<_NodeAlloc
>::_M_deallocate_buckets(__bucket_type
* __bkts
,
1918 typedef typename
__bucket_alloc_traits::pointer _Ptr
;
1919 auto __ptr
= std::pointer_traits
<_Ptr
>::pointer_to(*__bkts
);
1920 __bucket_alloc_type
__alloc(_M_node_allocator());
1921 __bucket_alloc_traits::deallocate(__alloc
, __ptr
, __n
);
1924 //@} hashtable-detail
1925 _GLIBCXX_END_NAMESPACE_VERSION
1926 } // namespace __detail
1929 #endif // _HASHTABLE_POLICY_H