libstdc++
hashtable_policy.h
Go to the documentation of this file.
1// Internal policy header for unordered_set and unordered_map -*- C++ -*-
2
3// Copyright (C) 2010-2019 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
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}
29 */
30
31#ifndef _HASHTABLE_POLICY_H
32#define _HASHTABLE_POLICY_H 1
33
34#include <tuple> // for std::tuple, std::forward_as_tuple
35#include <limits> // for std::numeric_limits
36#include <bits/stl_algobase.h> // for std::min.
37
38namespace std _GLIBCXX_VISIBILITY(default)
39{
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
41
42 template<typename _Key, typename _Value, typename _Alloc,
43 typename _ExtractKey, typename _Equal,
44 typename _H1, typename _H2, typename _Hash,
45 typename _RehashPolicy, typename _Traits>
46 class _Hashtable;
47
48namespace __detail
49{
50 /**
51 * @defgroup hashtable-detail Base and Implementation Classes
52 * @ingroup unordered_associative_containers
53 * @{
54 */
55 template<typename _Key, typename _Value,
56 typename _ExtractKey, typename _Equal,
57 typename _H1, typename _H2, typename _Hash, typename _Traits>
58 struct _Hashtable_base;
59
60 // Helper function: return distance(first, last) for forward
61 // iterators, or 0/1 for input iterators.
62 template<class _Iterator>
63 inline typename std::iterator_traits<_Iterator>::difference_type
64 __distance_fw(_Iterator __first, _Iterator __last,
66 { return __first != __last ? 1 : 0; }
67
68 template<class _Iterator>
69 inline typename std::iterator_traits<_Iterator>::difference_type
70 __distance_fw(_Iterator __first, _Iterator __last,
72 { return std::distance(__first, __last); }
73
74 template<class _Iterator>
75 inline typename std::iterator_traits<_Iterator>::difference_type
76 __distance_fw(_Iterator __first, _Iterator __last)
77 { return __distance_fw(__first, __last,
78 std::__iterator_category(__first)); }
79
80 struct _Identity
81 {
82 template<typename _Tp>
83 _Tp&&
84 operator()(_Tp&& __x) const
85 { return std::forward<_Tp>(__x); }
86 };
87
88 struct _Select1st
89 {
90 template<typename _Tp>
91 auto
92 operator()(_Tp&& __x) const
93 -> decltype(std::get<0>(std::forward<_Tp>(__x)))
94 { return std::get<0>(std::forward<_Tp>(__x)); }
95 };
96
97 template<typename _NodeAlloc>
98 struct _Hashtable_alloc;
99
100 // Functor recycling a pool of nodes and using allocation once the pool is
101 // empty.
102 template<typename _NodeAlloc>
103 struct _ReuseOrAllocNode
104 {
105 private:
106 using __node_alloc_type = _NodeAlloc;
107 using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
108 using __node_alloc_traits =
109 typename __hashtable_alloc::__node_alloc_traits;
110 using __node_type = typename __hashtable_alloc::__node_type;
111
112 public:
113 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
114 : _M_nodes(__nodes), _M_h(__h) { }
115 _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
116
117 ~_ReuseOrAllocNode()
118 { _M_h._M_deallocate_nodes(_M_nodes); }
119
120 template<typename _Arg>
121 __node_type*
122 operator()(_Arg&& __arg) const
123 {
124 if (_M_nodes)
125 {
126 __node_type* __node = _M_nodes;
127 _M_nodes = _M_nodes->_M_next();
128 __node->_M_nxt = nullptr;
129 auto& __a = _M_h._M_node_allocator();
130 __node_alloc_traits::destroy(__a, __node->_M_valptr());
131 __try
132 {
133 __node_alloc_traits::construct(__a, __node->_M_valptr(),
134 std::forward<_Arg>(__arg));
135 }
136 __catch(...)
137 {
138 _M_h._M_deallocate_node_ptr(__node);
139 __throw_exception_again;
140 }
141 return __node;
142 }
143 return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
144 }
145
146 private:
147 mutable __node_type* _M_nodes;
148 __hashtable_alloc& _M_h;
149 };
150
151 // Functor similar to the previous one but without any pool of nodes to
152 // recycle.
153 template<typename _NodeAlloc>
154 struct _AllocNode
155 {
156 private:
157 using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
158 using __node_type = typename __hashtable_alloc::__node_type;
159
160 public:
161 _AllocNode(__hashtable_alloc& __h)
162 : _M_h(__h) { }
163
164 template<typename _Arg>
165 __node_type*
166 operator()(_Arg&& __arg) const
167 { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
168
169 private:
170 __hashtable_alloc& _M_h;
171 };
172
173 // Auxiliary types used for all instantiations of _Hashtable nodes
174 // and iterators.
175
176 /**
177 * struct _Hashtable_traits
178 *
179 * Important traits for hash tables.
180 *
181 * @tparam _Cache_hash_code Boolean value. True if the value of
182 * the hash function is stored along with the value. This is a
183 * time-space tradeoff. Storing it may improve lookup speed by
184 * reducing the number of times we need to call the _Equal
185 * function.
186 *
187 * @tparam _Constant_iterators Boolean value. True if iterator and
188 * const_iterator are both constant iterator types. This is true
189 * for unordered_set and unordered_multiset, false for
190 * unordered_map and unordered_multimap.
191 *
192 * @tparam _Unique_keys Boolean value. True if the return value
193 * of _Hashtable::count(k) is always at most one, false if it may
194 * be an arbitrary number. This is true for unordered_set and
195 * unordered_map, false for unordered_multiset and
196 * unordered_multimap.
197 */
198 template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
200 {
204 };
205
206 /**
207 * struct _Hash_node_base
208 *
209 * Nodes, used to wrap elements stored in the hash table. A policy
210 * template parameter of class template _Hashtable controls whether
211 * nodes also store a hash code. In some cases (e.g. strings) this
212 * may be a performance win.
213 */
215 {
216 _Hash_node_base* _M_nxt;
217
218 _Hash_node_base() noexcept : _M_nxt() { }
219
220 _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
221 };
222
223 /**
224 * struct _Hash_node_value_base
225 *
226 * Node type with the value to store.
227 */
228 template<typename _Value>
230 {
231 typedef _Value value_type;
232
233 __gnu_cxx::__aligned_buffer<_Value> _M_storage;
234
235 _Value*
236 _M_valptr() noexcept
237 { return _M_storage._M_ptr(); }
238
239 const _Value*
240 _M_valptr() const noexcept
241 { return _M_storage._M_ptr(); }
242
243 _Value&
244 _M_v() noexcept
245 { return *_M_valptr(); }
246
247 const _Value&
248 _M_v() const noexcept
249 { return *_M_valptr(); }
250 };
251
252 /**
253 * Primary template struct _Hash_node.
254 */
255 template<typename _Value, bool _Cache_hash_code>
257
258 /**
259 * Specialization for nodes with caches, struct _Hash_node.
260 *
261 * Base class is __detail::_Hash_node_value_base.
262 */
263 template<typename _Value>
264 struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
265 {
266 std::size_t _M_hash_code;
267
269 _M_next() const noexcept
270 { return static_cast<_Hash_node*>(this->_M_nxt); }
271 };
272
273 /**
274 * Specialization for nodes without caches, struct _Hash_node.
275 *
276 * Base class is __detail::_Hash_node_value_base.
277 */
278 template<typename _Value>
279 struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
280 {
282 _M_next() const noexcept
283 { return static_cast<_Hash_node*>(this->_M_nxt); }
284 };
285
286 /// Base class for node iterators.
287 template<typename _Value, bool _Cache_hash_code>
289 {
291
292 __node_type* _M_cur;
293
294 _Node_iterator_base(__node_type* __p) noexcept
295 : _M_cur(__p) { }
296
297 void
298 _M_incr() noexcept
299 { _M_cur = _M_cur->_M_next(); }
300 };
301
302 template<typename _Value, bool _Cache_hash_code>
303 inline bool
306 noexcept
307 { return __x._M_cur == __y._M_cur; }
308
309 template<typename _Value, bool _Cache_hash_code>
310 inline bool
311 operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
312 const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
313 noexcept
314 { return __x._M_cur != __y._M_cur; }
315
316 /// Node iterators, used to iterate through all the hashtable.
317 template<typename _Value, bool __constant_iterators, bool __cache>
319 : public _Node_iterator_base<_Value, __cache>
320 {
321 private:
323 using __node_type = typename __base_type::__node_type;
324
325 public:
326 typedef _Value value_type;
327 typedef std::ptrdiff_t difference_type;
329
330 using pointer = typename std::conditional<__constant_iterators,
331 const _Value*, _Value*>::type;
332
333 using reference = typename std::conditional<__constant_iterators,
334 const _Value&, _Value&>::type;
335
336 _Node_iterator() noexcept
337 : __base_type(0) { }
338
339 explicit
340 _Node_iterator(__node_type* __p) noexcept
341 : __base_type(__p) { }
342
343 reference
344 operator*() const noexcept
345 { return this->_M_cur->_M_v(); }
346
347 pointer
348 operator->() const noexcept
349 { return this->_M_cur->_M_valptr(); }
350
352 operator++() noexcept
353 {
354 this->_M_incr();
355 return *this;
356 }
357
359 operator++(int) noexcept
360 {
361 _Node_iterator __tmp(*this);
362 this->_M_incr();
363 return __tmp;
364 }
365 };
366
367 /// Node const_iterators, used to iterate through all the hashtable.
368 template<typename _Value, bool __constant_iterators, bool __cache>
370 : public _Node_iterator_base<_Value, __cache>
371 {
372 private:
374 using __node_type = typename __base_type::__node_type;
375
376 public:
377 typedef _Value value_type;
378 typedef std::ptrdiff_t difference_type;
380
381 typedef const _Value* pointer;
382 typedef const _Value& reference;
383
384 _Node_const_iterator() noexcept
385 : __base_type(0) { }
386
387 explicit
388 _Node_const_iterator(__node_type* __p) noexcept
389 : __base_type(__p) { }
390
391 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
392 __cache>& __x) noexcept
393 : __base_type(__x._M_cur) { }
394
395 reference
396 operator*() const noexcept
397 { return this->_M_cur->_M_v(); }
398
399 pointer
400 operator->() const noexcept
401 { return this->_M_cur->_M_valptr(); }
402
404 operator++() noexcept
405 {
406 this->_M_incr();
407 return *this;
408 }
409
411 operator++(int) noexcept
412 {
413 _Node_const_iterator __tmp(*this);
414 this->_M_incr();
415 return __tmp;
416 }
417 };
418
419 // Many of class template _Hashtable's template parameters are policy
420 // classes. These are defaults for the policies.
421
422 /// Default range hashing function: use division to fold a large number
423 /// into the range [0, N).
425 {
426 typedef std::size_t first_argument_type;
427 typedef std::size_t second_argument_type;
428 typedef std::size_t result_type;
429
430 result_type
431 operator()(first_argument_type __num,
432 second_argument_type __den) const noexcept
433 { return __num % __den; }
434 };
435
436 /// Default ranged hash function H. In principle it should be a
437 /// function object composed from objects of type H1 and H2 such that
438 /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
439 /// h1 and h2. So instead we'll just use a tag to tell class template
440 /// hashtable to do that composition.
442
443 /// Default value for rehash policy. Bucket size is (usually) the
444 /// smallest prime that keeps the load factor small enough.
446 {
448
449 _Prime_rehash_policy(float __z = 1.0) noexcept
450 : _M_max_load_factor(__z), _M_next_resize(0) { }
451
452 float
453 max_load_factor() const noexcept
454 { return _M_max_load_factor; }
455
456 // Return a bucket size no smaller than n.
457 std::size_t
458 _M_next_bkt(std::size_t __n) const;
459
460 // Return a bucket count appropriate for n elements
461 std::size_t
462 _M_bkt_for_elements(std::size_t __n) const
463 { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
464
465 // __n_bkt is current bucket count, __n_elt is current element count,
466 // and __n_ins is number of elements to be inserted. Do we need to
467 // increase bucket count? If so, return make_pair(true, n), where n
468 // is the new bucket count. If not, return make_pair(false, 0).
470 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
471 std::size_t __n_ins) const;
472
473 typedef std::size_t _State;
474
475 _State
476 _M_state() const
477 { return _M_next_resize; }
478
479 void
480 _M_reset() noexcept
481 { _M_next_resize = 0; }
482
483 void
484 _M_reset(_State __state)
485 { _M_next_resize = __state; }
486
487 static const std::size_t _S_growth_factor = 2;
488
489 float _M_max_load_factor;
490 mutable std::size_t _M_next_resize;
491 };
492
493 /// Range hashing function assuming that second arg is a power of 2.
495 {
496 typedef std::size_t first_argument_type;
497 typedef std::size_t second_argument_type;
498 typedef std::size_t result_type;
499
500 result_type
501 operator()(first_argument_type __num,
502 second_argument_type __den) const noexcept
503 { return __num & (__den - 1); }
504 };
505
506 /// Compute closest power of 2 not less than __n
507 inline std::size_t
508 __clp2(std::size_t __n) noexcept
509 {
510 // Equivalent to return __n ? std::ceil2(__n) : 0;
511 if (__n < 2)
512 return __n;
513 const unsigned __lz = sizeof(size_t) > sizeof(long)
514 ? __builtin_clzll(__n - 1ull)
515 : __builtin_clzl(__n - 1ul);
516 // Doing two shifts avoids undefined behaviour when __lz == 0.
517 return (size_t(1) << (numeric_limits<size_t>::digits - __lz - 1)) << 1;
518 }
519
520 /// Rehash policy providing power of 2 bucket numbers. Avoids modulo
521 /// operations.
523 {
525
526 _Power2_rehash_policy(float __z = 1.0) noexcept
527 : _M_max_load_factor(__z), _M_next_resize(0) { }
528
529 float
530 max_load_factor() const noexcept
531 { return _M_max_load_factor; }
532
533 // Return a bucket size no smaller than n (as long as n is not above the
534 // highest power of 2).
535 std::size_t
536 _M_next_bkt(std::size_t __n) noexcept
537 {
538 const auto __max_width = std::min<size_t>(sizeof(size_t), 8);
539 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
540 std::size_t __res = __clp2(__n);
541
542 if (__res == __n)
543 __res <<= 1;
544
545 if (__res == 0)
546 __res = __max_bkt;
547
548 if (__res == __max_bkt)
549 // Set next resize to the max value so that we never try to rehash again
550 // as we already reach the biggest possible bucket number.
551 // Note that it might result in max_load_factor not being respected.
552 _M_next_resize = std::size_t(-1);
553 else
554 _M_next_resize
555 = __builtin_ceil(__res * (long double)_M_max_load_factor);
556
557 return __res;
558 }
559
560 // Return a bucket count appropriate for n elements
561 std::size_t
562 _M_bkt_for_elements(std::size_t __n) const noexcept
563 { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
564
565 // __n_bkt is current bucket count, __n_elt is current element count,
566 // and __n_ins is number of elements to be inserted. Do we need to
567 // increase bucket count? If so, return make_pair(true, n), where n
568 // is the new bucket count. If not, return make_pair(false, 0).
570 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
571 std::size_t __n_ins) noexcept
572 {
573 if (__n_elt + __n_ins >= _M_next_resize)
574 {
575 long double __min_bkts = (__n_elt + __n_ins)
576 / (long double)_M_max_load_factor;
577 if (__min_bkts >= __n_bkt)
578 return std::make_pair(true,
579 _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
580 __n_bkt * _S_growth_factor)));
581
582 _M_next_resize
583 = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
584 return std::make_pair(false, 0);
585 }
586 else
587 return std::make_pair(false, 0);
588 }
589
590 typedef std::size_t _State;
591
592 _State
593 _M_state() const noexcept
594 { return _M_next_resize; }
595
596 void
597 _M_reset() noexcept
598 { _M_next_resize = 0; }
599
600 void
601 _M_reset(_State __state) noexcept
602 { _M_next_resize = __state; }
603
604 static const std::size_t _S_growth_factor = 2;
605
606 float _M_max_load_factor;
607 std::size_t _M_next_resize;
608 };
609
610 // Base classes for std::_Hashtable. We define these base classes
611 // because in some cases we want to do different things depending on
612 // the value of a policy class. In some cases the policy class
613 // affects which member functions and nested typedefs are defined;
614 // we handle that by specializing base class templates. Several of
615 // the base class templates need to access other members of class
616 // template _Hashtable, so we use a variant of the "Curiously
617 // Recurring Template Pattern" (CRTP) technique.
618
619 /**
620 * Primary class template _Map_base.
621 *
622 * If the hashtable has a value type of the form pair<T1, T2> and a
623 * key extraction policy (_ExtractKey) that returns the first part
624 * of the pair, the hashtable gets a mapped_type typedef. If it
625 * satisfies those criteria and also has unique keys, then it also
626 * gets an operator[].
627 */
628 template<typename _Key, typename _Value, typename _Alloc,
629 typename _ExtractKey, typename _Equal,
630 typename _H1, typename _H2, typename _Hash,
631 typename _RehashPolicy, typename _Traits,
632 bool _Unique_keys = _Traits::__unique_keys::value>
633 struct _Map_base { };
634
635 /// Partial specialization, __unique_keys set to false.
636 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
637 typename _H1, typename _H2, typename _Hash,
638 typename _RehashPolicy, typename _Traits>
639 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
640 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
641 {
642 using mapped_type = typename std::tuple_element<1, _Pair>::type;
643 };
644
645 /// Partial specialization, __unique_keys set to true.
646 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
647 typename _H1, typename _H2, typename _Hash,
648 typename _RehashPolicy, typename _Traits>
649 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
650 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
651 {
652 private:
654 _Select1st,
655 _Equal, _H1, _H2, _Hash,
656 _Traits>;
657
658 using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
659 _Select1st, _Equal,
660 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
661
662 using __hash_code = typename __hashtable_base::__hash_code;
663 using __node_type = typename __hashtable_base::__node_type;
664
665 public:
666 using key_type = typename __hashtable_base::key_type;
667 using iterator = typename __hashtable_base::iterator;
668 using mapped_type = typename std::tuple_element<1, _Pair>::type;
669
670 mapped_type&
671 operator[](const key_type& __k);
672
673 mapped_type&
674 operator[](key_type&& __k);
675
676 // _GLIBCXX_RESOLVE_LIB_DEFECTS
677 // DR 761. unordered_map needs an at() member function.
678 mapped_type&
679 at(const key_type& __k);
680
681 const mapped_type&
682 at(const key_type& __k) const;
683 };
684
685 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
686 typename _H1, typename _H2, typename _Hash,
687 typename _RehashPolicy, typename _Traits>
688 auto
689 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
690 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
691 operator[](const key_type& __k)
692 -> mapped_type&
693 {
694 __hashtable* __h = static_cast<__hashtable*>(this);
695 __hash_code __code = __h->_M_hash_code(__k);
696 std::size_t __n = __h->_M_bucket_index(__k, __code);
697 __node_type* __p = __h->_M_find_node(__n, __k, __code);
698
699 if (!__p)
700 {
701 __p = __h->_M_allocate_node(std::piecewise_construct,
703 std::tuple<>());
704 return __h->_M_insert_unique_node(__n, __code, __p)->second;
705 }
706
707 return __p->_M_v().second;
708 }
709
710 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
711 typename _H1, typename _H2, typename _Hash,
712 typename _RehashPolicy, typename _Traits>
713 auto
714 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
715 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
716 operator[](key_type&& __k)
717 -> mapped_type&
718 {
719 __hashtable* __h = static_cast<__hashtable*>(this);
720 __hash_code __code = __h->_M_hash_code(__k);
721 std::size_t __n = __h->_M_bucket_index(__k, __code);
722 __node_type* __p = __h->_M_find_node(__n, __k, __code);
723
724 if (!__p)
725 {
726 __p = __h->_M_allocate_node(std::piecewise_construct,
727 std::forward_as_tuple(std::move(__k)),
728 std::tuple<>());
729 return __h->_M_insert_unique_node(__n, __code, __p)->second;
730 }
731
732 return __p->_M_v().second;
733 }
734
735 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
736 typename _H1, typename _H2, typename _Hash,
737 typename _RehashPolicy, typename _Traits>
738 auto
739 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
740 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
741 at(const key_type& __k)
742 -> mapped_type&
743 {
744 __hashtable* __h = static_cast<__hashtable*>(this);
745 __hash_code __code = __h->_M_hash_code(__k);
746 std::size_t __n = __h->_M_bucket_index(__k, __code);
747 __node_type* __p = __h->_M_find_node(__n, __k, __code);
748
749 if (!__p)
750 __throw_out_of_range(__N("_Map_base::at"));
751 return __p->_M_v().second;
752 }
753
754 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
755 typename _H1, typename _H2, typename _Hash,
756 typename _RehashPolicy, typename _Traits>
757 auto
758 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
759 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
760 at(const key_type& __k) const
761 -> const mapped_type&
762 {
763 const __hashtable* __h = static_cast<const __hashtable*>(this);
764 __hash_code __code = __h->_M_hash_code(__k);
765 std::size_t __n = __h->_M_bucket_index(__k, __code);
766 __node_type* __p = __h->_M_find_node(__n, __k, __code);
767
768 if (!__p)
769 __throw_out_of_range(__N("_Map_base::at"));
770 return __p->_M_v().second;
771 }
772
773 /**
774 * Primary class template _Insert_base.
775 *
776 * Defines @c insert member functions appropriate to all _Hashtables.
777 */
778 template<typename _Key, typename _Value, typename _Alloc,
779 typename _ExtractKey, typename _Equal,
780 typename _H1, typename _H2, typename _Hash,
781 typename _RehashPolicy, typename _Traits>
783 {
784 protected:
785 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
786 _Equal, _H1, _H2, _Hash,
787 _RehashPolicy, _Traits>;
788
789 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
790 _Equal, _H1, _H2, _Hash,
791 _Traits>;
792
793 using value_type = typename __hashtable_base::value_type;
794 using iterator = typename __hashtable_base::iterator;
795 using const_iterator = typename __hashtable_base::const_iterator;
796 using size_type = typename __hashtable_base::size_type;
797
798 using __unique_keys = typename __hashtable_base::__unique_keys;
799 using __ireturn_type = typename __hashtable_base::__ireturn_type;
801 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
802 using __node_gen_type = _AllocNode<__node_alloc_type>;
803
805 _M_conjure_hashtable()
806 { return *(static_cast<__hashtable*>(this)); }
807
808 template<typename _InputIterator, typename _NodeGetter>
809 void
810 _M_insert_range(_InputIterator __first, _InputIterator __last,
811 const _NodeGetter&, true_type);
812
813 template<typename _InputIterator, typename _NodeGetter>
814 void
815 _M_insert_range(_InputIterator __first, _InputIterator __last,
816 const _NodeGetter&, false_type);
817
818 public:
819 __ireturn_type
820 insert(const value_type& __v)
821 {
822 __hashtable& __h = _M_conjure_hashtable();
823 __node_gen_type __node_gen(__h);
824 return __h._M_insert(__v, __node_gen, __unique_keys());
825 }
826
827 iterator
828 insert(const_iterator __hint, const value_type& __v)
829 {
830 __hashtable& __h = _M_conjure_hashtable();
831 __node_gen_type __node_gen(__h);
832 return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
833 }
834
835 void
837 { this->insert(__l.begin(), __l.end()); }
838
839 template<typename _InputIterator>
840 void
841 insert(_InputIterator __first, _InputIterator __last)
842 {
843 __hashtable& __h = _M_conjure_hashtable();
844 __node_gen_type __node_gen(__h);
845 return _M_insert_range(__first, __last, __node_gen, __unique_keys());
846 }
847 };
848
849 template<typename _Key, typename _Value, typename _Alloc,
850 typename _ExtractKey, typename _Equal,
851 typename _H1, typename _H2, typename _Hash,
852 typename _RehashPolicy, typename _Traits>
853 template<typename _InputIterator, typename _NodeGetter>
854 void
855 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
856 _RehashPolicy, _Traits>::
857 _M_insert_range(_InputIterator __first, _InputIterator __last,
858 const _NodeGetter& __node_gen, true_type)
859 {
860 size_type __n_elt = __detail::__distance_fw(__first, __last);
861 if (__n_elt == 0)
862 return;
863
864 __hashtable& __h = _M_conjure_hashtable();
865 for (; __first != __last; ++__first)
866 {
867 if (__h._M_insert(*__first, __node_gen, __unique_keys(),
868 __n_elt).second)
869 __n_elt = 1;
870 else if (__n_elt != 1)
871 --__n_elt;
872 }
873 }
874
875 template<typename _Key, typename _Value, typename _Alloc,
876 typename _ExtractKey, typename _Equal,
877 typename _H1, typename _H2, typename _Hash,
878 typename _RehashPolicy, typename _Traits>
879 template<typename _InputIterator, typename _NodeGetter>
880 void
881 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
882 _RehashPolicy, _Traits>::
883 _M_insert_range(_InputIterator __first, _InputIterator __last,
884 const _NodeGetter& __node_gen, false_type)
885 {
886 using __rehash_type = typename __hashtable::__rehash_type;
887 using __rehash_state = typename __hashtable::__rehash_state;
888 using pair_type = std::pair<bool, std::size_t>;
889
890 size_type __n_elt = __detail::__distance_fw(__first, __last);
891 if (__n_elt == 0)
892 return;
893
894 __hashtable& __h = _M_conjure_hashtable();
895 __rehash_type& __rehash = __h._M_rehash_policy;
896 const __rehash_state& __saved_state = __rehash._M_state();
897 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
898 __h._M_element_count,
899 __n_elt);
900
901 if (__do_rehash.first)
902 __h._M_rehash(__do_rehash.second, __saved_state);
903
904 for (; __first != __last; ++__first)
905 __h._M_insert(*__first, __node_gen, __unique_keys());
906 }
907
908 /**
909 * Primary class template _Insert.
910 *
911 * Defines @c insert member functions that depend on _Hashtable policies,
912 * via partial specializations.
913 */
914 template<typename _Key, typename _Value, typename _Alloc,
915 typename _ExtractKey, typename _Equal,
916 typename _H1, typename _H2, typename _Hash,
917 typename _RehashPolicy, typename _Traits,
918 bool _Constant_iterators = _Traits::__constant_iterators::value>
919 struct _Insert;
920
921 /// Specialization.
922 template<typename _Key, typename _Value, typename _Alloc,
923 typename _ExtractKey, typename _Equal,
924 typename _H1, typename _H2, typename _Hash,
925 typename _RehashPolicy, typename _Traits>
926 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
927 _RehashPolicy, _Traits, true>
928 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
929 _H1, _H2, _Hash, _RehashPolicy, _Traits>
930 {
931 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
932 _Equal, _H1, _H2, _Hash,
933 _RehashPolicy, _Traits>;
934
935 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
936 _Equal, _H1, _H2, _Hash,
937 _Traits>;
938
939 using value_type = typename __base_type::value_type;
940 using iterator = typename __base_type::iterator;
941 using const_iterator = typename __base_type::const_iterator;
942
943 using __unique_keys = typename __base_type::__unique_keys;
944 using __ireturn_type = typename __hashtable_base::__ireturn_type;
945 using __hashtable = typename __base_type::__hashtable;
946 using __node_gen_type = typename __base_type::__node_gen_type;
947
948 using __base_type::insert;
949
950 __ireturn_type
951 insert(value_type&& __v)
952 {
953 __hashtable& __h = this->_M_conjure_hashtable();
954 __node_gen_type __node_gen(__h);
955 return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
956 }
957
958 iterator
959 insert(const_iterator __hint, value_type&& __v)
960 {
961 __hashtable& __h = this->_M_conjure_hashtable();
962 __node_gen_type __node_gen(__h);
963 return __h._M_insert(__hint, std::move(__v), __node_gen,
964 __unique_keys());
965 }
966 };
967
968 /// Specialization.
969 template<typename _Key, typename _Value, typename _Alloc,
970 typename _ExtractKey, typename _Equal,
971 typename _H1, typename _H2, typename _Hash,
972 typename _RehashPolicy, typename _Traits>
973 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
974 _RehashPolicy, _Traits, false>
975 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
976 _H1, _H2, _Hash, _RehashPolicy, _Traits>
977 {
978 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
979 _Equal, _H1, _H2, _Hash,
980 _RehashPolicy, _Traits>;
981 using value_type = typename __base_type::value_type;
982 using iterator = typename __base_type::iterator;
983 using const_iterator = typename __base_type::const_iterator;
984
985 using __unique_keys = typename __base_type::__unique_keys;
986 using __hashtable = typename __base_type::__hashtable;
987 using __ireturn_type = typename __base_type::__ireturn_type;
988
989 using __base_type::insert;
990
991 template<typename _Pair>
993
994 template<typename _Pair>
996
997 template<typename _Pair>
998 using _IFconsp = typename _IFcons<_Pair>::type;
999
1000 template<typename _Pair, typename = _IFconsp<_Pair>>
1001 __ireturn_type
1002 insert(_Pair&& __v)
1003 {
1004 __hashtable& __h = this->_M_conjure_hashtable();
1005 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
1006 }
1007
1008 template<typename _Pair, typename = _IFconsp<_Pair>>
1009 iterator
1010 insert(const_iterator __hint, _Pair&& __v)
1011 {
1012 __hashtable& __h = this->_M_conjure_hashtable();
1013 return __h._M_emplace(__hint, __unique_keys(),
1014 std::forward<_Pair>(__v));
1015 }
1016 };
1017
1018 template<typename _Policy>
1019 using __has_load_factor = typename _Policy::__has_load_factor;
1020
1021 /**
1022 * Primary class template _Rehash_base.
1023 *
1024 * Give hashtable the max_load_factor functions and reserve iff the
1025 * rehash policy supports it.
1026 */
1027 template<typename _Key, typename _Value, typename _Alloc,
1028 typename _ExtractKey, typename _Equal,
1029 typename _H1, typename _H2, typename _Hash,
1030 typename _RehashPolicy, typename _Traits,
1031 typename =
1032 __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>>
1034
1035 /// Specialization when rehash policy doesn't provide load factor management.
1036 template<typename _Key, typename _Value, typename _Alloc,
1037 typename _ExtractKey, typename _Equal,
1038 typename _H1, typename _H2, typename _Hash,
1039 typename _RehashPolicy, typename _Traits>
1040 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1041 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1042 std::false_type>
1043 {
1044 };
1045
1046 /// Specialization when rehash policy provide load factor management.
1047 template<typename _Key, typename _Value, typename _Alloc,
1048 typename _ExtractKey, typename _Equal,
1049 typename _H1, typename _H2, typename _Hash,
1050 typename _RehashPolicy, typename _Traits>
1051 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1052 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1053 std::true_type>
1054 {
1055 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1056 _Equal, _H1, _H2, _Hash,
1057 _RehashPolicy, _Traits>;
1058
1059 float
1060 max_load_factor() const noexcept
1061 {
1062 const __hashtable* __this = static_cast<const __hashtable*>(this);
1063 return __this->__rehash_policy().max_load_factor();
1064 }
1065
1066 void
1067 max_load_factor(float __z)
1068 {
1069 __hashtable* __this = static_cast<__hashtable*>(this);
1070 __this->__rehash_policy(_RehashPolicy(__z));
1071 }
1072
1073 void
1074 reserve(std::size_t __n)
1075 {
1076 __hashtable* __this = static_cast<__hashtable*>(this);
1077 __this->rehash(__builtin_ceil(__n / max_load_factor()));
1078 }
1079 };
1080
1081 /**
1082 * Primary class template _Hashtable_ebo_helper.
1083 *
1084 * Helper class using EBO when it is not forbidden (the type is not
1085 * final) and when it is worth it (the type is empty.)
1086 */
1087 template<int _Nm, typename _Tp,
1088 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1090
1091 /// Specialization using EBO.
1092 template<int _Nm, typename _Tp>
1093 struct _Hashtable_ebo_helper<_Nm, _Tp, true>
1094 : private _Tp
1095 {
1096 _Hashtable_ebo_helper() = default;
1097
1098 template<typename _OtherTp>
1099 _Hashtable_ebo_helper(_OtherTp&& __tp)
1100 : _Tp(std::forward<_OtherTp>(__tp))
1101 { }
1102
1103 static const _Tp&
1104 _S_cget(const _Hashtable_ebo_helper& __eboh)
1105 { return static_cast<const _Tp&>(__eboh); }
1106
1107 static _Tp&
1108 _S_get(_Hashtable_ebo_helper& __eboh)
1109 { return static_cast<_Tp&>(__eboh); }
1110 };
1111
1112 /// Specialization not using EBO.
1113 template<int _Nm, typename _Tp>
1114 struct _Hashtable_ebo_helper<_Nm, _Tp, false>
1115 {
1116 _Hashtable_ebo_helper() = default;
1117
1118 template<typename _OtherTp>
1119 _Hashtable_ebo_helper(_OtherTp&& __tp)
1120 : _M_tp(std::forward<_OtherTp>(__tp))
1121 { }
1122
1123 static const _Tp&
1124 _S_cget(const _Hashtable_ebo_helper& __eboh)
1125 { return __eboh._M_tp; }
1126
1127 static _Tp&
1128 _S_get(_Hashtable_ebo_helper& __eboh)
1129 { return __eboh._M_tp; }
1130
1131 private:
1132 _Tp _M_tp;
1133 };
1134
1135 /**
1136 * Primary class template _Local_iterator_base.
1137 *
1138 * Base class for local iterators, used to iterate within a bucket
1139 * but not between buckets.
1140 */
1141 template<typename _Key, typename _Value, typename _ExtractKey,
1142 typename _H1, typename _H2, typename _Hash,
1143 bool __cache_hash_code>
1145
1146 /**
1147 * Primary class template _Hash_code_base.
1148 *
1149 * Encapsulates two policy issues that aren't quite orthogonal.
1150 * (1) the difference between using a ranged hash function and using
1151 * the combination of a hash function and a range-hashing function.
1152 * In the former case we don't have such things as hash codes, so
1153 * we have a dummy type as placeholder.
1154 * (2) Whether or not we cache hash codes. Caching hash codes is
1155 * meaningless if we have a ranged hash function.
1156 *
1157 * We also put the key extraction objects here, for convenience.
1158 * Each specialization derives from one or more of the template
1159 * parameters to benefit from Ebo. This is important as this type
1160 * is inherited in some cases by the _Local_iterator_base type used
1161 * to implement local_iterator and const_local_iterator. As with
1162 * any iterator type we prefer to make it as small as possible.
1163 *
1164 * Primary template is unused except as a hook for specializations.
1165 */
1166 template<typename _Key, typename _Value, typename _ExtractKey,
1167 typename _H1, typename _H2, typename _Hash,
1168 bool __cache_hash_code>
1170
1171 /// Specialization: ranged hash function, no caching hash codes. H1
1172 /// and H2 are provided but ignored. We define a dummy hash code type.
1173 template<typename _Key, typename _Value, typename _ExtractKey,
1174 typename _H1, typename _H2, typename _Hash>
1175 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
1176 : private _Hashtable_ebo_helper<0, _ExtractKey>,
1177 private _Hashtable_ebo_helper<1, _Hash>
1178 {
1179 private:
1182
1183 protected:
1184 typedef void* __hash_code;
1186
1187 // We need the default constructor for the local iterators and _Hashtable
1188 // default constructor.
1189 _Hash_code_base() = default;
1190
1191 _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
1192 const _Hash& __h)
1193 : __ebo_extract_key(__ex), __ebo_hash(__h) { }
1194
1195 __hash_code
1196 _M_hash_code(const _Key& __key) const
1197 { return 0; }
1198
1199 std::size_t
1200 _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const
1201 { return _M_ranged_hash()(__k, __n); }
1202
1203 std::size_t
1204 _M_bucket_index(const __node_type* __p, std::size_t __n) const
1205 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1206 (std::size_t)0)) )
1207 { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
1208
1209 void
1210 _M_store_code(__node_type*, __hash_code) const
1211 { }
1212
1213 void
1214 _M_copy_code(__node_type*, const __node_type*) const
1215 { }
1216
1217 void
1218 _M_swap(_Hash_code_base& __x)
1219 {
1220 std::swap(_M_extract(), __x._M_extract());
1221 std::swap(_M_ranged_hash(), __x._M_ranged_hash());
1222 }
1223
1224 const _ExtractKey&
1225 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1226
1227 _ExtractKey&
1228 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1229
1230 const _Hash&
1231 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
1232
1233 _Hash&
1234 _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
1235 };
1236
1237 // No specialization for ranged hash function while caching hash codes.
1238 // That combination is meaningless, and trying to do it is an error.
1239
1240 /// Specialization: ranged hash function, cache hash codes. This
1241 /// combination is meaningless, so we provide only a declaration
1242 /// and no definition.
1243 template<typename _Key, typename _Value, typename _ExtractKey,
1244 typename _H1, typename _H2, typename _Hash>
1245 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1246
1247 /// Specialization: hash function and range-hashing function, no
1248 /// caching of hash codes.
1249 /// Provides typedef and accessor required by C++ 11.
1250 template<typename _Key, typename _Value, typename _ExtractKey,
1251 typename _H1, typename _H2>
1252 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1253 _Default_ranged_hash, false>
1254 : private _Hashtable_ebo_helper<0, _ExtractKey>,
1255 private _Hashtable_ebo_helper<1, _H1>,
1256 private _Hashtable_ebo_helper<2, _H2>
1257 {
1258 private:
1262
1263 // Gives the local iterator implementation access to _M_bucket_index().
1264 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1265 _Default_ranged_hash, false>;
1266
1267 public:
1268 typedef _H1 hasher;
1269
1270 hasher
1271 hash_function() const
1272 { return _M_h1(); }
1273
1274 protected:
1275 typedef std::size_t __hash_code;
1277
1278 // We need the default constructor for the local iterators and _Hashtable
1279 // default constructor.
1280 _Hash_code_base() = default;
1281
1282 _Hash_code_base(const _ExtractKey& __ex,
1283 const _H1& __h1, const _H2& __h2,
1284 const _Default_ranged_hash&)
1285 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1286
1287 __hash_code
1288 _M_hash_code(const _Key& __k) const
1289 {
1290 static_assert(__is_invocable<const _H1&, const _Key&>{},
1291 "hash function must be invocable with an argument of key type");
1292 return _M_h1()(__k);
1293 }
1294
1295 std::size_t
1296 _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const
1297 { return _M_h2()(__c, __n); }
1298
1299 std::size_t
1300 _M_bucket_index(const __node_type* __p, std::size_t __n) const
1301 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1302 && noexcept(declval<const _H2&>()((__hash_code)0,
1303 (std::size_t)0)) )
1304 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1305
1306 void
1307 _M_store_code(__node_type*, __hash_code) const
1308 { }
1309
1310 void
1311 _M_copy_code(__node_type*, const __node_type*) const
1312 { }
1313
1314 void
1315 _M_swap(_Hash_code_base& __x)
1316 {
1317 std::swap(_M_extract(), __x._M_extract());
1318 std::swap(_M_h1(), __x._M_h1());
1319 std::swap(_M_h2(), __x._M_h2());
1320 }
1321
1322 const _ExtractKey&
1323 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1324
1325 _ExtractKey&
1326 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1327
1328 const _H1&
1329 _M_h1() const { return __ebo_h1::_S_cget(*this); }
1330
1331 _H1&
1332 _M_h1() { return __ebo_h1::_S_get(*this); }
1333
1334 const _H2&
1335 _M_h2() const { return __ebo_h2::_S_cget(*this); }
1336
1337 _H2&
1338 _M_h2() { return __ebo_h2::_S_get(*this); }
1339 };
1340
1341 /// Specialization: hash function and range-hashing function,
1342 /// caching hash codes. H is provided but ignored. Provides
1343 /// typedef and accessor required by C++ 11.
1344 template<typename _Key, typename _Value, typename _ExtractKey,
1345 typename _H1, typename _H2>
1346 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1348 : private _Hashtable_ebo_helper<0, _ExtractKey>,
1349 private _Hashtable_ebo_helper<1, _H1>,
1350 private _Hashtable_ebo_helper<2, _H2>
1351 {
1352 private:
1353 // Gives the local iterator implementation access to _M_h2().
1354 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1355 _Default_ranged_hash, true>;
1356
1360
1361 public:
1362 typedef _H1 hasher;
1363
1364 hasher
1365 hash_function() const
1366 { return _M_h1(); }
1367
1368 protected:
1369 typedef std::size_t __hash_code;
1371
1372 // We need the default constructor for _Hashtable default constructor.
1373 _Hash_code_base() = default;
1374 _Hash_code_base(const _ExtractKey& __ex,
1375 const _H1& __h1, const _H2& __h2,
1376 const _Default_ranged_hash&)
1377 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1378
1379 __hash_code
1380 _M_hash_code(const _Key& __k) const
1381 {
1382 static_assert(__is_invocable<const _H1&, const _Key&>{},
1383 "hash function must be invocable with an argument of key type");
1384 return _M_h1()(__k);
1385 }
1386
1387 std::size_t
1388 _M_bucket_index(const _Key&, __hash_code __c,
1389 std::size_t __n) const
1390 { return _M_h2()(__c, __n); }
1391
1392 std::size_t
1393 _M_bucket_index(const __node_type* __p, std::size_t __n) const
1394 noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1395 (std::size_t)0)) )
1396 { return _M_h2()(__p->_M_hash_code, __n); }
1397
1398 void
1399 _M_store_code(__node_type* __n, __hash_code __c) const
1400 { __n->_M_hash_code = __c; }
1401
1402 void
1403 _M_copy_code(__node_type* __to, const __node_type* __from) const
1404 { __to->_M_hash_code = __from->_M_hash_code; }
1405
1406 void
1407 _M_swap(_Hash_code_base& __x)
1408 {
1409 std::swap(_M_extract(), __x._M_extract());
1410 std::swap(_M_h1(), __x._M_h1());
1411 std::swap(_M_h2(), __x._M_h2());
1412 }
1413
1414 const _ExtractKey&
1415 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1416
1417 _ExtractKey&
1418 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1419
1420 const _H1&
1421 _M_h1() const { return __ebo_h1::_S_cget(*this); }
1422
1423 _H1&
1424 _M_h1() { return __ebo_h1::_S_get(*this); }
1425
1426 const _H2&
1427 _M_h2() const { return __ebo_h2::_S_cget(*this); }
1428
1429 _H2&
1430 _M_h2() { return __ebo_h2::_S_get(*this); }
1431 };
1432
1433 /**
1434 * Primary class template _Equal_helper.
1435 *
1436 */
1437 template <typename _Key, typename _Value, typename _ExtractKey,
1438 typename _Equal, typename _HashCodeType,
1439 bool __cache_hash_code>
1441
1442 /// Specialization.
1443 template<typename _Key, typename _Value, typename _ExtractKey,
1444 typename _Equal, typename _HashCodeType>
1445 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
1446 {
1447 static bool
1448 _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1449 const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
1450 { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1451 };
1452
1453 /// Specialization.
1454 template<typename _Key, typename _Value, typename _ExtractKey,
1455 typename _Equal, typename _HashCodeType>
1456 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
1457 {
1458 static bool
1459 _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1460 const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
1461 { return __eq(__k, __extract(__n->_M_v())); }
1462 };
1463
1464
1465 /// Partial specialization used when nodes contain a cached hash code.
1466 template<typename _Key, typename _Value, typename _ExtractKey,
1467 typename _H1, typename _H2, typename _Hash>
1468 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1469 _H1, _H2, _Hash, true>
1470 : private _Hashtable_ebo_helper<0, _H2>
1471 {
1472 protected:
1474 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1475 _H1, _H2, _Hash, true>;
1476
1477 _Local_iterator_base() = default;
1480 std::size_t __bkt, std::size_t __bkt_count)
1481 : __base_type(__base._M_h2()),
1482 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1483
1484 void
1485 _M_incr()
1486 {
1487 _M_cur = _M_cur->_M_next();
1488 if (_M_cur)
1489 {
1490 std::size_t __bkt
1491 = __base_type::_S_get(*this)(_M_cur->_M_hash_code,
1492 _M_bucket_count);
1493 if (__bkt != _M_bucket)
1494 _M_cur = nullptr;
1495 }
1496 }
1497
1499 std::size_t _M_bucket;
1500 std::size_t _M_bucket_count;
1501
1502 public:
1503 const void*
1504 _M_curr() const { return _M_cur; } // for equality ops
1505
1506 std::size_t
1507 _M_get_bucket() const { return _M_bucket; } // for debug mode
1508 };
1509
1510 // Uninitialized storage for a _Hash_code_base.
1511 // This type is DefaultConstructible and Assignable even if the
1512 // _Hash_code_base type isn't, so that _Local_iterator_base<..., false>
1513 // can be DefaultConstructible and Assignable.
1514 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1515 struct _Hash_code_storage
1516 {
1517 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1518
1519 _Tp*
1520 _M_h() { return _M_storage._M_ptr(); }
1521
1522 const _Tp*
1523 _M_h() const { return _M_storage._M_ptr(); }
1524 };
1525
1526 // Empty partial specialization for empty _Hash_code_base types.
1527 template<typename _Tp>
1528 struct _Hash_code_storage<_Tp, true>
1529 {
1530 static_assert( std::is_empty<_Tp>::value, "Type must be empty" );
1531
1532 // As _Tp is an empty type there will be no bytes written/read through
1533 // the cast pointer, so no strict-aliasing violation.
1534 _Tp*
1535 _M_h() { return reinterpret_cast<_Tp*>(this); }
1536
1537 const _Tp*
1538 _M_h() const { return reinterpret_cast<const _Tp*>(this); }
1539 };
1540
1541 template<typename _Key, typename _Value, typename _ExtractKey,
1542 typename _H1, typename _H2, typename _Hash>
1543 using __hash_code_for_local_iter
1544 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1545 _H1, _H2, _Hash, false>>;
1546
1547 // Partial specialization used when hash codes are not cached
1548 template<typename _Key, typename _Value, typename _ExtractKey,
1549 typename _H1, typename _H2, typename _Hash>
1550 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1551 _H1, _H2, _Hash, false>
1552 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1553 {
1554 protected:
1555 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1556 _H1, _H2, _Hash, false>;
1557
1558 _Local_iterator_base() : _M_bucket_count(-1) { }
1559
1560 _Local_iterator_base(const __hash_code_base& __base,
1561 _Hash_node<_Value, false>* __p,
1562 std::size_t __bkt, std::size_t __bkt_count)
1563 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1564 { _M_init(__base); }
1565
1566 ~_Local_iterator_base()
1567 {
1568 if (_M_bucket_count != -1)
1569 _M_destroy();
1570 }
1571
1572 _Local_iterator_base(const _Local_iterator_base& __iter)
1573 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1574 _M_bucket_count(__iter._M_bucket_count)
1575 {
1576 if (_M_bucket_count != -1)
1577 _M_init(*__iter._M_h());
1578 }
1579
1580 _Local_iterator_base&
1581 operator=(const _Local_iterator_base& __iter)
1582 {
1583 if (_M_bucket_count != -1)
1584 _M_destroy();
1585 _M_cur = __iter._M_cur;
1586 _M_bucket = __iter._M_bucket;
1587 _M_bucket_count = __iter._M_bucket_count;
1588 if (_M_bucket_count != -1)
1589 _M_init(*__iter._M_h());
1590 return *this;
1591 }
1592
1593 void
1594 _M_incr()
1595 {
1596 _M_cur = _M_cur->_M_next();
1597 if (_M_cur)
1598 {
1599 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1600 _M_bucket_count);
1601 if (__bkt != _M_bucket)
1602 _M_cur = nullptr;
1603 }
1604 }
1605
1606 _Hash_node<_Value, false>* _M_cur;
1607 std::size_t _M_bucket;
1608 std::size_t _M_bucket_count;
1609
1610 void
1611 _M_init(const __hash_code_base& __base)
1612 { ::new(this->_M_h()) __hash_code_base(__base); }
1613
1614 void
1615 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1616
1617 public:
1618 const void*
1619 _M_curr() const { return _M_cur; } // for equality ops and debug mode
1620
1621 std::size_t
1622 _M_get_bucket() const { return _M_bucket; } // for debug mode
1623 };
1624
1625 template<typename _Key, typename _Value, typename _ExtractKey,
1626 typename _H1, typename _H2, typename _Hash, bool __cache>
1627 inline bool
1628 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1629 _H1, _H2, _Hash, __cache>& __x,
1630 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1631 _H1, _H2, _Hash, __cache>& __y)
1632 { return __x._M_curr() == __y._M_curr(); }
1633
1634 template<typename _Key, typename _Value, typename _ExtractKey,
1635 typename _H1, typename _H2, typename _Hash, bool __cache>
1636 inline bool
1637 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1638 _H1, _H2, _Hash, __cache>& __x,
1639 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1640 _H1, _H2, _Hash, __cache>& __y)
1641 { return __x._M_curr() != __y._M_curr(); }
1642
1643 /// local iterators
1644 template<typename _Key, typename _Value, typename _ExtractKey,
1645 typename _H1, typename _H2, typename _Hash,
1646 bool __constant_iterators, bool __cache>
1648 : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1649 _H1, _H2, _Hash, __cache>
1650 {
1651 private:
1652 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1653 _H1, _H2, _Hash, __cache>;
1654 using __hash_code_base = typename __base_type::__hash_code_base;
1655 public:
1656 typedef _Value value_type;
1657 typedef typename std::conditional<__constant_iterators,
1658 const _Value*, _Value*>::type
1659 pointer;
1660 typedef typename std::conditional<__constant_iterators,
1661 const _Value&, _Value&>::type
1662 reference;
1663 typedef std::ptrdiff_t difference_type;
1665
1666 _Local_iterator() = default;
1667
1668 _Local_iterator(const __hash_code_base& __base,
1670 std::size_t __bkt, std::size_t __bkt_count)
1671 : __base_type(__base, __p, __bkt, __bkt_count)
1672 { }
1673
1674 reference
1675 operator*() const
1676 { return this->_M_cur->_M_v(); }
1677
1678 pointer
1679 operator->() const
1680 { return this->_M_cur->_M_valptr(); }
1681
1683 operator++()
1684 {
1685 this->_M_incr();
1686 return *this;
1687 }
1688
1690 operator++(int)
1691 {
1692 _Local_iterator __tmp(*this);
1693 this->_M_incr();
1694 return __tmp;
1695 }
1696 };
1697
1698 /// local const_iterators
1699 template<typename _Key, typename _Value, typename _ExtractKey,
1700 typename _H1, typename _H2, typename _Hash,
1701 bool __constant_iterators, bool __cache>
1703 : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1704 _H1, _H2, _Hash, __cache>
1705 {
1706 private:
1707 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1708 _H1, _H2, _Hash, __cache>;
1709 using __hash_code_base = typename __base_type::__hash_code_base;
1710
1711 public:
1712 typedef _Value value_type;
1713 typedef const _Value* pointer;
1714 typedef const _Value& reference;
1715 typedef std::ptrdiff_t difference_type;
1717
1718 _Local_const_iterator() = default;
1719
1720 _Local_const_iterator(const __hash_code_base& __base,
1722 std::size_t __bkt, std::size_t __bkt_count)
1723 : __base_type(__base, __p, __bkt, __bkt_count)
1724 { }
1725
1726 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1727 _H1, _H2, _Hash,
1728 __constant_iterators,
1729 __cache>& __x)
1730 : __base_type(__x)
1731 { }
1732
1733 reference
1734 operator*() const
1735 { return this->_M_cur->_M_v(); }
1736
1737 pointer
1738 operator->() const
1739 { return this->_M_cur->_M_valptr(); }
1740
1742 operator++()
1743 {
1744 this->_M_incr();
1745 return *this;
1746 }
1747
1749 operator++(int)
1750 {
1751 _Local_const_iterator __tmp(*this);
1752 this->_M_incr();
1753 return __tmp;
1754 }
1755 };
1756
1757 /**
1758 * Primary class template _Hashtable_base.
1759 *
1760 * Helper class adding management of _Equal functor to
1761 * _Hash_code_base type.
1762 *
1763 * Base class templates are:
1764 * - __detail::_Hash_code_base
1765 * - __detail::_Hashtable_ebo_helper
1766 */
1767 template<typename _Key, typename _Value,
1768 typename _ExtractKey, typename _Equal,
1769 typename _H1, typename _H2, typename _Hash, typename _Traits>
1771 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1772 _Traits::__hash_cached::value>,
1773 private _Hashtable_ebo_helper<0, _Equal>
1774 {
1775 public:
1776 typedef _Key key_type;
1777 typedef _Value value_type;
1778 typedef _Equal key_equal;
1779 typedef std::size_t size_type;
1780 typedef std::ptrdiff_t difference_type;
1781
1782 using __traits_type = _Traits;
1783 using __hash_cached = typename __traits_type::__hash_cached;
1784 using __constant_iterators = typename __traits_type::__constant_iterators;
1785 using __unique_keys = typename __traits_type::__unique_keys;
1786
1787 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1788 _H1, _H2, _Hash,
1789 __hash_cached::value>;
1790
1791 using __hash_code = typename __hash_code_base::__hash_code;
1792 using __node_type = typename __hash_code_base::__node_type;
1793
1794 using iterator = __detail::_Node_iterator<value_type,
1795 __constant_iterators::value,
1796 __hash_cached::value>;
1797
1799 __constant_iterators::value,
1800 __hash_cached::value>;
1801
1802 using local_iterator = __detail::_Local_iterator<key_type, value_type,
1803 _ExtractKey, _H1, _H2, _Hash,
1804 __constant_iterators::value,
1805 __hash_cached::value>;
1806
1808 value_type,
1809 _ExtractKey, _H1, _H2, _Hash,
1810 __constant_iterators::value,
1811 __hash_cached::value>;
1812
1813 using __ireturn_type = typename std::conditional<__unique_keys::value,
1815 iterator>::type;
1816 private:
1818 using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1819 __hash_code, __hash_cached::value>;
1820
1821 protected:
1822 _Hashtable_base() = default;
1823 _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
1824 const _Hash& __hash, const _Equal& __eq)
1825 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1826 { }
1827
1828 bool
1829 _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
1830 {
1831 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1832 "key equality predicate must be invocable with two arguments of "
1833 "key type");
1834 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1835 __k, __c, __n);
1836 }
1837
1838 void
1839 _M_swap(_Hashtable_base& __x)
1840 {
1841 __hash_code_base::_M_swap(__x);
1842 std::swap(_M_eq(), __x._M_eq());
1843 }
1844
1845 const _Equal&
1846 _M_eq() const { return _EqualEBO::_S_cget(*this); }
1847
1848 _Equal&
1849 _M_eq() { return _EqualEBO::_S_get(*this); }
1850 };
1851
1852 /**
1853 * struct _Equality_base.
1854 *
1855 * Common types and functions for class _Equality.
1856 */
1858 {
1859 protected:
1860 template<typename _Uiterator>
1861 static bool
1862 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1863 };
1864
1865 // See std::is_permutation in N3068.
1866 template<typename _Uiterator>
1867 bool
1868 _Equality_base::
1869 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1870 _Uiterator __first2)
1871 {
1872 for (; __first1 != __last1; ++__first1, ++__first2)
1873 if (!(*__first1 == *__first2))
1874 break;
1875
1876 if (__first1 == __last1)
1877 return true;
1878
1879 _Uiterator __last2 = __first2;
1880 std::advance(__last2, std::distance(__first1, __last1));
1881
1882 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1883 {
1884 _Uiterator __tmp = __first1;
1885 while (__tmp != __it1 && !bool(*__tmp == *__it1))
1886 ++__tmp;
1887
1888 // We've seen this one before.
1889 if (__tmp != __it1)
1890 continue;
1891
1892 std::ptrdiff_t __n2 = 0;
1893 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1894 if (*__tmp == *__it1)
1895 ++__n2;
1896
1897 if (!__n2)
1898 return false;
1899
1900 std::ptrdiff_t __n1 = 0;
1901 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1902 if (*__tmp == *__it1)
1903 ++__n1;
1904
1905 if (__n1 != __n2)
1906 return false;
1907 }
1908 return true;
1909 }
1910
1911 /**
1912 * Primary class template _Equality.
1913 *
1914 * This is for implementing equality comparison for unordered
1915 * containers, per N3068, by John Lakos and Pablo Halpern.
1916 * Algorithmically, we follow closely the reference implementations
1917 * therein.
1918 */
1919 template<typename _Key, typename _Value, typename _Alloc,
1920 typename _ExtractKey, typename _Equal,
1921 typename _H1, typename _H2, typename _Hash,
1922 typename _RehashPolicy, typename _Traits,
1923 bool _Unique_keys = _Traits::__unique_keys::value>
1925
1926 /// Specialization.
1927 template<typename _Key, typename _Value, typename _Alloc,
1928 typename _ExtractKey, typename _Equal,
1929 typename _H1, typename _H2, typename _Hash,
1930 typename _RehashPolicy, typename _Traits>
1931 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1932 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1933 {
1934 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1935 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1936
1937 bool
1938 _M_equal(const __hashtable&) const;
1939 };
1940
1941 template<typename _Key, typename _Value, typename _Alloc,
1942 typename _ExtractKey, typename _Equal,
1943 typename _H1, typename _H2, typename _Hash,
1944 typename _RehashPolicy, typename _Traits>
1945 bool
1946 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1947 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
1948 _M_equal(const __hashtable& __other) const
1949 {
1950 const __hashtable* __this = static_cast<const __hashtable*>(this);
1951
1952 if (__this->size() != __other.size())
1953 return false;
1954
1955 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1956 {
1957 const auto __ity = __other.find(_ExtractKey()(*__itx));
1958 if (__ity == __other.end() || !bool(*__ity == *__itx))
1959 return false;
1960 }
1961 return true;
1962 }
1963
1964 /// Specialization.
1965 template<typename _Key, typename _Value, typename _Alloc,
1966 typename _ExtractKey, typename _Equal,
1967 typename _H1, typename _H2, typename _Hash,
1968 typename _RehashPolicy, typename _Traits>
1969 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1970 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1971 : public _Equality_base
1972 {
1973 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1974 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1975
1976 bool
1977 _M_equal(const __hashtable&) const;
1978 };
1979
1980 template<typename _Key, typename _Value, typename _Alloc,
1981 typename _ExtractKey, typename _Equal,
1982 typename _H1, typename _H2, typename _Hash,
1983 typename _RehashPolicy, typename _Traits>
1984 bool
1985 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1986 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
1987 _M_equal(const __hashtable& __other) const
1988 {
1989 const __hashtable* __this = static_cast<const __hashtable*>(this);
1990
1991 if (__this->size() != __other.size())
1992 return false;
1993
1994 for (auto __itx = __this->begin(); __itx != __this->end();)
1995 {
1996 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1997 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1998
1999 if (std::distance(__xrange.first, __xrange.second)
2000 != std::distance(__yrange.first, __yrange.second))
2001 return false;
2002
2003 if (!_S_is_permutation(__xrange.first, __xrange.second,
2004 __yrange.first))
2005 return false;
2006
2007 __itx = __xrange.second;
2008 }
2009 return true;
2010 }
2011
2012 /**
2013 * This type deals with all allocation and keeps an allocator instance through
2014 * inheritance to benefit from EBO when possible.
2015 */
2016 template<typename _NodeAlloc>
2017 struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc>
2018 {
2019 private:
2021 public:
2022 using __node_type = typename _NodeAlloc::value_type;
2023 using __node_alloc_type = _NodeAlloc;
2024 // Use __gnu_cxx to benefit from _S_always_equal and al.
2026
2027 using __value_alloc_traits = typename __node_alloc_traits::template
2028 rebind_traits<typename __node_type::value_type>;
2029
2031 using __bucket_type = __node_base*;
2032 using __bucket_alloc_type =
2033 __alloc_rebind<__node_alloc_type, __bucket_type>;
2035
2036 _Hashtable_alloc() = default;
2037 _Hashtable_alloc(const _Hashtable_alloc&) = default;
2039
2040 template<typename _Alloc>
2041 _Hashtable_alloc(_Alloc&& __a)
2042 : __ebo_node_alloc(std::forward<_Alloc>(__a))
2043 { }
2044
2045 __node_alloc_type&
2046 _M_node_allocator()
2047 { return __ebo_node_alloc::_S_get(*this); }
2048
2049 const __node_alloc_type&
2050 _M_node_allocator() const
2051 { return __ebo_node_alloc::_S_cget(*this); }
2052
2053 template<typename... _Args>
2054 __node_type*
2055 _M_allocate_node(_Args&&... __args);
2056
2057 void
2058 _M_deallocate_node(__node_type* __n);
2059
2060 void
2061 _M_deallocate_node_ptr(__node_type* __n);
2062
2063 // Deallocate the linked list of nodes pointed to by __n
2064 void
2065 _M_deallocate_nodes(__node_type* __n);
2066
2068 _M_allocate_buckets(std::size_t __n);
2069
2070 void
2071 _M_deallocate_buckets(__bucket_type*, std::size_t __n);
2072 };
2073
2074 // Definitions of class template _Hashtable_alloc's out-of-line member
2075 // functions.
2076 template<typename _NodeAlloc>
2077 template<typename... _Args>
2078 typename _Hashtable_alloc<_NodeAlloc>::__node_type*
2080 {
2081 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2082 __node_type* __n = std::__to_address(__nptr);
2083 __try
2084 {
2085 ::new ((void*)__n) __node_type;
2086 __node_alloc_traits::construct(_M_node_allocator(),
2087 __n->_M_valptr(),
2088 std::forward<_Args>(__args)...);
2089 return __n;
2090 }
2091 __catch(...)
2092 {
2093 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2094 __throw_exception_again;
2095 }
2096 }
2097
2098 template<typename _NodeAlloc>
2099 void
2100 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2101 {
2102 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2103 _M_deallocate_node_ptr(__n);
2104 }
2105
2106 template<typename _NodeAlloc>
2107 void
2108 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n)
2109 {
2110 typedef typename __node_alloc_traits::pointer _Ptr;
2111 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
2112 __n->~__node_type();
2113 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2114 }
2115
2116 template<typename _NodeAlloc>
2117 void
2118 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
2119 {
2120 while (__n)
2121 {
2122 __node_type* __tmp = __n;
2123 __n = __n->_M_next();
2124 _M_deallocate_node(__tmp);
2125 }
2126 }
2127
2128 template<typename _NodeAlloc>
2129 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
2130 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n)
2131 {
2132 __bucket_alloc_type __alloc(_M_node_allocator());
2133
2134 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n);
2135 __bucket_type* __p = std::__to_address(__ptr);
2136 __builtin_memset(__p, 0, __n * sizeof(__bucket_type));
2137 return __p;
2138 }
2139
2140 template<typename _NodeAlloc>
2141 void
2142 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2143 std::size_t __n)
2144 {
2145 typedef typename __bucket_alloc_traits::pointer _Ptr;
2146 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
2147 __bucket_alloc_type __alloc(_M_node_allocator());
2148 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
2149 }
2150
2151 ///@} hashtable-detail
2152} // namespace __detail
2153_GLIBCXX_END_NAMESPACE_VERSION
2154} // namespace std
2155
2156#endif // _HASHTABLE_POLICY_H
_GLIBCXX20_CONSTEXPR complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:391
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:75
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:78
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
Definition: tuple:1482
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Definition: stl_pair.h:79
std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2 not less than __n.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_Iterator __base(_Iterator __it)
initializer_list
tuple_element
Definition: array:359
Properties of fundamental types.
Definition: limits:313
Primary class template, tuple.
Definition: tuple:524
integral_constant
Definition: type_traits:58
Define a member typedef type to one of two argument types.
Definition: type_traits:2054
is_empty
Definition: type_traits:705
is_constructible
Definition: type_traits:885
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:2040
Uniform interface to all allocator types.
Base class for node iterators.
Node iterators, used to iterate through all the hashtable.
Node const_iterators, used to iterate through all the hashtable.
Default range hashing function: use division to fold a large number into the range [0,...
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Range hashing function assuming that second arg is a power of 2.
Rehash policy providing power of 2 bucket numbers. Avoids modulo operations.
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:84
Marking input iterators.
Forward iterators support a superset of input iterator operations.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:210
Uniform interface to C++98 and C++11 allocators.