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-2020 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, std::is_permutation.
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>
64 __distance_fw(_Iterator __first, _Iterator __last,
66 { return __first != __last ? 1 : 0; }
67
68 template<class _Iterator>
70 __distance_fw(_Iterator __first, _Iterator __last,
72 { return std::distance(__first, __last); }
73
74 template<class _Iterator>
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 _Hash or _Equal
185 * functors.
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_ceill(__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::bit_ceil(__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 if (__n == 0)
539 // Special case on container 1st initialization with 0 bucket count
540 // hint. We keep _M_next_resize to 0 to make sure that next time we
541 // want to add an element allocation will take place.
542 return 1;
543
544 const auto __max_width = std::min<size_t>(sizeof(size_t), 8);
545 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
546 std::size_t __res = __clp2(__n);
547
548 if (__res == 0)
549 __res = __max_bkt;
550 else if (__res == 1)
551 // If __res is 1 we force it to 2 to make sure there will be an
552 // allocation so that nothing need to be stored in the initial
553 // single bucket
554 __res = 2;
555
556 if (__res == __max_bkt)
557 // Set next resize to the max value so that we never try to rehash again
558 // as we already reach the biggest possible bucket number.
559 // Note that it might result in max_load_factor not being respected.
560 _M_next_resize = numeric_limits<size_t>::max();
561 else
562 _M_next_resize
563 = __builtin_floorl(__res * (long double)_M_max_load_factor);
564
565 return __res;
566 }
567
568 // Return a bucket count appropriate for n elements
569 std::size_t
570 _M_bkt_for_elements(std::size_t __n) const noexcept
571 { return __builtin_ceill(__n / (long double)_M_max_load_factor); }
572
573 // __n_bkt is current bucket count, __n_elt is current element count,
574 // and __n_ins is number of elements to be inserted. Do we need to
575 // increase bucket count? If so, return make_pair(true, n), where n
576 // is the new bucket count. If not, return make_pair(false, 0).
578 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
579 std::size_t __n_ins) noexcept
580 {
581 if (__n_elt + __n_ins > _M_next_resize)
582 {
583 // If _M_next_resize is 0 it means that we have nothing allocated so
584 // far and that we start inserting elements. In this case we start
585 // with an initial bucket size of 11.
586 long double __min_bkts
587 = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
588 / (long double)_M_max_load_factor;
589 if (__min_bkts >= __n_bkt)
590 return { true,
591 _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__min_bkts) + 1,
592 __n_bkt * _S_growth_factor)) };
593
594 _M_next_resize
595 = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor);
596 return { false, 0 };
597 }
598 else
599 return { false, 0 };
600 }
601
602 typedef std::size_t _State;
603
604 _State
605 _M_state() const noexcept
606 { return _M_next_resize; }
607
608 void
609 _M_reset() noexcept
610 { _M_next_resize = 0; }
611
612 void
613 _M_reset(_State __state) noexcept
614 { _M_next_resize = __state; }
615
616 static const std::size_t _S_growth_factor = 2;
617
618 float _M_max_load_factor;
619 std::size_t _M_next_resize;
620 };
621
622 // Base classes for std::_Hashtable. We define these base classes
623 // because in some cases we want to do different things depending on
624 // the value of a policy class. In some cases the policy class
625 // affects which member functions and nested typedefs are defined;
626 // we handle that by specializing base class templates. Several of
627 // the base class templates need to access other members of class
628 // template _Hashtable, so we use a variant of the "Curiously
629 // Recurring Template Pattern" (CRTP) technique.
630
631 /**
632 * Primary class template _Map_base.
633 *
634 * If the hashtable has a value type of the form pair<T1, T2> and a
635 * key extraction policy (_ExtractKey) that returns the first part
636 * of the pair, the hashtable gets a mapped_type typedef. If it
637 * satisfies those criteria and also has unique keys, then it also
638 * gets an operator[].
639 */
640 template<typename _Key, typename _Value, typename _Alloc,
641 typename _ExtractKey, typename _Equal,
642 typename _H1, typename _H2, typename _Hash,
643 typename _RehashPolicy, typename _Traits,
644 bool _Unique_keys = _Traits::__unique_keys::value>
645 struct _Map_base { };
646
647 /// Partial specialization, __unique_keys set to false.
648 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
649 typename _H1, typename _H2, typename _Hash,
650 typename _RehashPolicy, typename _Traits>
651 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
652 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
653 {
654 using mapped_type = typename std::tuple_element<1, _Pair>::type;
655 };
656
657 /// Partial specialization, __unique_keys set to true.
658 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
659 typename _H1, typename _H2, typename _Hash,
660 typename _RehashPolicy, typename _Traits>
661 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
662 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
663 {
664 private:
666 _Select1st,
667 _Equal, _H1, _H2, _Hash,
668 _Traits>;
669
670 using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
671 _Select1st, _Equal,
672 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
673
674 using __hash_code = typename __hashtable_base::__hash_code;
675 using __node_type = typename __hashtable_base::__node_type;
676
677 public:
678 using key_type = typename __hashtable_base::key_type;
679 using iterator = typename __hashtable_base::iterator;
680 using mapped_type = typename std::tuple_element<1, _Pair>::type;
681
682 mapped_type&
683 operator[](const key_type& __k);
684
685 mapped_type&
686 operator[](key_type&& __k);
687
688 // _GLIBCXX_RESOLVE_LIB_DEFECTS
689 // DR 761. unordered_map needs an at() member function.
690 mapped_type&
691 at(const key_type& __k);
692
693 const mapped_type&
694 at(const key_type& __k) const;
695 };
696
697 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
698 typename _H1, typename _H2, typename _Hash,
699 typename _RehashPolicy, typename _Traits>
700 auto
701 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
702 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
703 operator[](const key_type& __k)
704 -> mapped_type&
705 {
706 __hashtable* __h = static_cast<__hashtable*>(this);
707 __hash_code __code = __h->_M_hash_code(__k);
708 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
709 if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
710 return __node->_M_v().second;
711
712 typename __hashtable::_Scoped_node __node {
713 __h,
717 };
718 auto __pos
719 = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
720 __node._M_node = nullptr;
721 return __pos->second;
722 }
723
724 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
725 typename _H1, typename _H2, typename _Hash,
726 typename _RehashPolicy, typename _Traits>
727 auto
728 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
729 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
730 operator[](key_type&& __k)
731 -> mapped_type&
732 {
733 __hashtable* __h = static_cast<__hashtable*>(this);
734 __hash_code __code = __h->_M_hash_code(__k);
735 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
736 if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
737 return __node->_M_v().second;
738
739 typename __hashtable::_Scoped_node __node {
740 __h,
744 };
745 auto __pos
746 = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
747 __node._M_node = nullptr;
748 return __pos->second;
749 }
750
751 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
752 typename _H1, typename _H2, typename _Hash,
753 typename _RehashPolicy, typename _Traits>
754 auto
755 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
756 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
757 at(const key_type& __k)
758 -> mapped_type&
759 {
760 __hashtable* __h = static_cast<__hashtable*>(this);
761 __hash_code __code = __h->_M_hash_code(__k);
762 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
763 __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
764
765 if (!__p)
766 __throw_out_of_range(__N("_Map_base::at"));
767 return __p->_M_v().second;
768 }
769
770 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
771 typename _H1, typename _H2, typename _Hash,
772 typename _RehashPolicy, typename _Traits>
773 auto
774 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
775 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
776 at(const key_type& __k) const
777 -> const mapped_type&
778 {
779 const __hashtable* __h = static_cast<const __hashtable*>(this);
780 __hash_code __code = __h->_M_hash_code(__k);
781 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
782 __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
783
784 if (!__p)
785 __throw_out_of_range(__N("_Map_base::at"));
786 return __p->_M_v().second;
787 }
788
789 /**
790 * Primary class template _Insert_base.
791 *
792 * Defines @c insert member functions appropriate to all _Hashtables.
793 */
794 template<typename _Key, typename _Value, typename _Alloc,
795 typename _ExtractKey, typename _Equal,
796 typename _H1, typename _H2, typename _Hash,
797 typename _RehashPolicy, typename _Traits>
799 {
800 protected:
801 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
802 _Equal, _H1, _H2, _Hash,
803 _RehashPolicy, _Traits>;
804
805 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
806 _Equal, _H1, _H2, _Hash,
807 _Traits>;
808
809 using value_type = typename __hashtable_base::value_type;
810 using iterator = typename __hashtable_base::iterator;
811 using const_iterator = typename __hashtable_base::const_iterator;
812 using size_type = typename __hashtable_base::size_type;
813
814 using __unique_keys = typename __hashtable_base::__unique_keys;
815 using __ireturn_type = typename __hashtable_base::__ireturn_type;
817 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
818 using __node_gen_type = _AllocNode<__node_alloc_type>;
819
821 _M_conjure_hashtable()
822 { return *(static_cast<__hashtable*>(this)); }
823
824 template<typename _InputIterator, typename _NodeGetter>
825 void
826 _M_insert_range(_InputIterator __first, _InputIterator __last,
827 const _NodeGetter&, true_type);
828
829 template<typename _InputIterator, typename _NodeGetter>
830 void
831 _M_insert_range(_InputIterator __first, _InputIterator __last,
832 const _NodeGetter&, false_type);
833
834 public:
835 __ireturn_type
836 insert(const value_type& __v)
837 {
838 __hashtable& __h = _M_conjure_hashtable();
839 __node_gen_type __node_gen(__h);
840 return __h._M_insert(__v, __node_gen, __unique_keys());
841 }
842
843 iterator
844 insert(const_iterator __hint, const value_type& __v)
845 {
846 __hashtable& __h = _M_conjure_hashtable();
847 __node_gen_type __node_gen(__h);
848 return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
849 }
850
851 void
853 { this->insert(__l.begin(), __l.end()); }
854
855 template<typename _InputIterator>
856 void
857 insert(_InputIterator __first, _InputIterator __last)
858 {
859 __hashtable& __h = _M_conjure_hashtable();
860 __node_gen_type __node_gen(__h);
861 return _M_insert_range(__first, __last, __node_gen, __unique_keys());
862 }
863 };
864
865 template<typename _Key, typename _Value, typename _Alloc,
866 typename _ExtractKey, typename _Equal,
867 typename _H1, typename _H2, typename _Hash,
868 typename _RehashPolicy, typename _Traits>
869 template<typename _InputIterator, typename _NodeGetter>
870 void
871 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
872 _RehashPolicy, _Traits>::
873 _M_insert_range(_InputIterator __first, _InputIterator __last,
874 const _NodeGetter& __node_gen, true_type)
875 {
876 size_type __n_elt = __detail::__distance_fw(__first, __last);
877 if (__n_elt == 0)
878 return;
879
880 __hashtable& __h = _M_conjure_hashtable();
881 for (; __first != __last; ++__first)
882 {
883 if (__h._M_insert(*__first, __node_gen, __unique_keys(),
884 __n_elt).second)
885 __n_elt = 1;
886 else if (__n_elt != 1)
887 --__n_elt;
888 }
889 }
890
891 template<typename _Key, typename _Value, typename _Alloc,
892 typename _ExtractKey, typename _Equal,
893 typename _H1, typename _H2, typename _Hash,
894 typename _RehashPolicy, typename _Traits>
895 template<typename _InputIterator, typename _NodeGetter>
896 void
897 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
898 _RehashPolicy, _Traits>::
899 _M_insert_range(_InputIterator __first, _InputIterator __last,
900 const _NodeGetter& __node_gen, false_type)
901 {
902 using __rehash_type = typename __hashtable::__rehash_type;
903 using __rehash_state = typename __hashtable::__rehash_state;
904 using pair_type = std::pair<bool, std::size_t>;
905
906 size_type __n_elt = __detail::__distance_fw(__first, __last);
907 if (__n_elt == 0)
908 return;
909
910 __hashtable& __h = _M_conjure_hashtable();
911 __rehash_type& __rehash = __h._M_rehash_policy;
912 const __rehash_state& __saved_state = __rehash._M_state();
913 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
914 __h._M_element_count,
915 __n_elt);
916
917 if (__do_rehash.first)
918 __h._M_rehash(__do_rehash.second, __saved_state);
919
920 for (; __first != __last; ++__first)
921 __h._M_insert(*__first, __node_gen, __unique_keys());
922 }
923
924 /**
925 * Primary class template _Insert.
926 *
927 * Defines @c insert member functions that depend on _Hashtable policies,
928 * via partial specializations.
929 */
930 template<typename _Key, typename _Value, typename _Alloc,
931 typename _ExtractKey, typename _Equal,
932 typename _H1, typename _H2, typename _Hash,
933 typename _RehashPolicy, typename _Traits,
934 bool _Constant_iterators = _Traits::__constant_iterators::value>
935 struct _Insert;
936
937 /// Specialization.
938 template<typename _Key, typename _Value, typename _Alloc,
939 typename _ExtractKey, typename _Equal,
940 typename _H1, typename _H2, typename _Hash,
941 typename _RehashPolicy, typename _Traits>
942 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
943 _RehashPolicy, _Traits, true>
944 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
945 _H1, _H2, _Hash, _RehashPolicy, _Traits>
946 {
947 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
948 _Equal, _H1, _H2, _Hash,
949 _RehashPolicy, _Traits>;
950
951 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
952 _Equal, _H1, _H2, _Hash,
953 _Traits>;
954
955 using value_type = typename __base_type::value_type;
956 using iterator = typename __base_type::iterator;
957 using const_iterator = typename __base_type::const_iterator;
958
959 using __unique_keys = typename __base_type::__unique_keys;
960 using __ireturn_type = typename __hashtable_base::__ireturn_type;
961 using __hashtable = typename __base_type::__hashtable;
962 using __node_gen_type = typename __base_type::__node_gen_type;
963
964 using __base_type::insert;
965
966 __ireturn_type
967 insert(value_type&& __v)
968 {
969 __hashtable& __h = this->_M_conjure_hashtable();
970 __node_gen_type __node_gen(__h);
971 return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
972 }
973
974 iterator
975 insert(const_iterator __hint, value_type&& __v)
976 {
977 __hashtable& __h = this->_M_conjure_hashtable();
978 __node_gen_type __node_gen(__h);
979 return __h._M_insert(__hint, std::move(__v), __node_gen,
980 __unique_keys());
981 }
982 };
983
984 /// Specialization.
985 template<typename _Key, typename _Value, typename _Alloc,
986 typename _ExtractKey, typename _Equal,
987 typename _H1, typename _H2, typename _Hash,
988 typename _RehashPolicy, typename _Traits>
989 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
990 _RehashPolicy, _Traits, false>
991 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
992 _H1, _H2, _Hash, _RehashPolicy, _Traits>
993 {
994 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
995 _Equal, _H1, _H2, _Hash,
996 _RehashPolicy, _Traits>;
997 using value_type = typename __base_type::value_type;
998 using iterator = typename __base_type::iterator;
999 using const_iterator = typename __base_type::const_iterator;
1000
1001 using __unique_keys = typename __base_type::__unique_keys;
1002 using __hashtable = typename __base_type::__hashtable;
1003 using __ireturn_type = typename __base_type::__ireturn_type;
1004
1005 using __base_type::insert;
1006
1007 template<typename _Pair>
1009
1010 template<typename _Pair>
1012
1013 template<typename _Pair>
1014 using _IFconsp = typename _IFcons<_Pair>::type;
1015
1016 template<typename _Pair, typename = _IFconsp<_Pair>>
1017 __ireturn_type
1018 insert(_Pair&& __v)
1019 {
1020 __hashtable& __h = this->_M_conjure_hashtable();
1021 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
1022 }
1023
1024 template<typename _Pair, typename = _IFconsp<_Pair>>
1025 iterator
1026 insert(const_iterator __hint, _Pair&& __v)
1027 {
1028 __hashtable& __h = this->_M_conjure_hashtable();
1029 return __h._M_emplace(__hint, __unique_keys(),
1030 std::forward<_Pair>(__v));
1031 }
1032 };
1033
1034 template<typename _Policy>
1035 using __has_load_factor = typename _Policy::__has_load_factor;
1036
1037 /**
1038 * Primary class template _Rehash_base.
1039 *
1040 * Give hashtable the max_load_factor functions and reserve iff the
1041 * rehash policy supports it.
1042 */
1043 template<typename _Key, typename _Value, typename _Alloc,
1044 typename _ExtractKey, typename _Equal,
1045 typename _H1, typename _H2, typename _Hash,
1046 typename _RehashPolicy, typename _Traits,
1047 typename =
1048 __detected_or_t<false_type, __has_load_factor, _RehashPolicy>>
1050
1051 /// Specialization when rehash policy doesn't provide load factor management.
1052 template<typename _Key, typename _Value, typename _Alloc,
1053 typename _ExtractKey, typename _Equal,
1054 typename _H1, typename _H2, typename _Hash,
1055 typename _RehashPolicy, typename _Traits>
1056 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1057 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1058 false_type>
1059 {
1060 };
1061
1062 /// Specialization when rehash policy provide load factor management.
1063 template<typename _Key, typename _Value, typename _Alloc,
1064 typename _ExtractKey, typename _Equal,
1065 typename _H1, typename _H2, typename _Hash,
1066 typename _RehashPolicy, typename _Traits>
1067 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1068 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1069 true_type>
1070 {
1071 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1072 _Equal, _H1, _H2, _Hash,
1073 _RehashPolicy, _Traits>;
1074
1075 float
1076 max_load_factor() const noexcept
1077 {
1078 const __hashtable* __this = static_cast<const __hashtable*>(this);
1079 return __this->__rehash_policy().max_load_factor();
1080 }
1081
1082 void
1083 max_load_factor(float __z)
1084 {
1085 __hashtable* __this = static_cast<__hashtable*>(this);
1086 __this->__rehash_policy(_RehashPolicy(__z));
1087 }
1088
1089 void
1090 reserve(std::size_t __n)
1091 {
1092 __hashtable* __this = static_cast<__hashtable*>(this);
1093 __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
1094 }
1095 };
1096
1097 /**
1098 * Primary class template _Hashtable_ebo_helper.
1099 *
1100 * Helper class using EBO when it is not forbidden (the type is not
1101 * final) and when it is worth it (the type is empty.)
1102 */
1103 template<int _Nm, typename _Tp,
1104 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1106
1107 /// Specialization using EBO.
1108 template<int _Nm, typename _Tp>
1109 struct _Hashtable_ebo_helper<_Nm, _Tp, true>
1110 : private _Tp
1111 {
1112 _Hashtable_ebo_helper() = default;
1113
1114 template<typename _OtherTp>
1115 _Hashtable_ebo_helper(_OtherTp&& __tp)
1116 : _Tp(std::forward<_OtherTp>(__tp))
1117 { }
1118
1119 const _Tp& _M_cget() const { return static_cast<const _Tp&>(*this); }
1120 _Tp& _M_get() { return static_cast<_Tp&>(*this); }
1121 };
1122
1123 /// Specialization not using EBO.
1124 template<int _Nm, typename _Tp>
1125 struct _Hashtable_ebo_helper<_Nm, _Tp, false>
1126 {
1127 _Hashtable_ebo_helper() = default;
1128
1129 template<typename _OtherTp>
1130 _Hashtable_ebo_helper(_OtherTp&& __tp)
1131 : _M_tp(std::forward<_OtherTp>(__tp))
1132 { }
1133
1134 const _Tp& _M_cget() const { return _M_tp; }
1135 _Tp& _M_get() { return _M_tp; }
1136
1137 private:
1138 _Tp _M_tp;
1139 };
1140
1141 /**
1142 * Primary class template _Local_iterator_base.
1143 *
1144 * Base class for local iterators, used to iterate within a bucket
1145 * but not between buckets.
1146 */
1147 template<typename _Key, typename _Value, typename _ExtractKey,
1148 typename _H1, typename _H2, typename _Hash,
1149 bool __cache_hash_code>
1151
1152 /**
1153 * Primary class template _Hash_code_base.
1154 *
1155 * Encapsulates two policy issues that aren't quite orthogonal.
1156 * (1) the difference between using a ranged hash function and using
1157 * the combination of a hash function and a range-hashing function.
1158 * In the former case we don't have such things as hash codes, so
1159 * we have a dummy type as placeholder.
1160 * (2) Whether or not we cache hash codes. Caching hash codes is
1161 * meaningless if we have a ranged hash function.
1162 *
1163 * We also put the key extraction objects here, for convenience.
1164 * Each specialization derives from one or more of the template
1165 * parameters to benefit from Ebo. This is important as this type
1166 * is inherited in some cases by the _Local_iterator_base type used
1167 * to implement local_iterator and const_local_iterator. As with
1168 * any iterator type we prefer to make it as small as possible.
1169 *
1170 * Primary template is unused except as a hook for specializations.
1171 */
1172 template<typename _Key, typename _Value, typename _ExtractKey,
1173 typename _H1, typename _H2, typename _Hash,
1174 bool __cache_hash_code>
1176
1177 /// Specialization: ranged hash function, no caching hash codes. H1
1178 /// and H2 are provided but ignored. We define a dummy hash code type.
1179 template<typename _Key, typename _Value, typename _ExtractKey,
1180 typename _H1, typename _H2, typename _Hash>
1181 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
1182 : private _Hashtable_ebo_helper<0, _ExtractKey>,
1183 private _Hashtable_ebo_helper<1, _Hash>
1184 {
1185 private:
1188
1189 protected:
1190 typedef void* __hash_code;
1192
1193 // We need the default constructor for the local iterators and _Hashtable
1194 // default constructor.
1195 _Hash_code_base() = default;
1196
1197 _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
1198 const _Hash& __h)
1199 : __ebo_extract_key(__ex), __ebo_hash(__h) { }
1200
1201 __hash_code
1202 _M_hash_code(const _Key& __key) const
1203 { return 0; }
1204
1205 std::size_t
1206 _M_bucket_index(const _Key& __k, __hash_code,
1207 std::size_t __bkt_count) const
1208 { return _M_ranged_hash()(__k, __bkt_count); }
1209
1210 std::size_t
1211 _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
1212 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1213 (std::size_t)0)) )
1214 { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __bkt_count); }
1215
1216 void
1217 _M_store_code(__node_type*, __hash_code) const
1218 { }
1219
1220 void
1221 _M_copy_code(__node_type*, const __node_type*) const
1222 { }
1223
1224 void
1225 _M_swap(_Hash_code_base& __x)
1226 {
1227 std::swap(__ebo_extract_key::_M_get(),
1228 __x.__ebo_extract_key::_M_get());
1229 std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get());
1230 }
1231
1232 const _ExtractKey&
1233 _M_extract() const { return __ebo_extract_key::_M_cget(); }
1234
1235 const _Hash&
1236 _M_ranged_hash() const { return __ebo_hash::_M_cget(); }
1237 };
1238
1239 // No specialization for ranged hash function while caching hash codes.
1240 // That combination is meaningless, and trying to do it is an error.
1241
1242 /// Specialization: ranged hash function, cache hash codes. This
1243 /// combination is meaningless, so we provide only a declaration
1244 /// and no definition.
1245 template<typename _Key, typename _Value, typename _ExtractKey,
1246 typename _H1, typename _H2, typename _Hash>
1247 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1248
1249 /// Specialization: hash function and range-hashing function, no
1250 /// caching of hash codes.
1251 /// Provides typedef and accessor required by C++ 11.
1252 template<typename _Key, typename _Value, typename _ExtractKey,
1253 typename _H1, typename _H2>
1254 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1255 _Default_ranged_hash, false>
1256 : private _Hashtable_ebo_helper<0, _ExtractKey>,
1257 private _Hashtable_ebo_helper<1, _H1>,
1258 private _Hashtable_ebo_helper<2, _H2>
1259 {
1260 private:
1264
1265 // Gives the local iterator implementation access to _M_bucket_index().
1266 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1267 _Default_ranged_hash, false>;
1268
1269 public:
1270 typedef _H1 hasher;
1271
1272 hasher
1273 hash_function() const
1274 { return _M_h1(); }
1275
1276 protected:
1277 typedef std::size_t __hash_code;
1279
1280 // We need the default constructor for the local iterators and _Hashtable
1281 // default constructor.
1282 _Hash_code_base() = default;
1283
1284 _Hash_code_base(const _ExtractKey& __ex,
1285 const _H1& __h1, const _H2& __h2,
1286 const _Default_ranged_hash&)
1287 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1288
1289 __hash_code
1290 _M_hash_code(const _Key& __k) const
1291 {
1292 static_assert(__is_invocable<const _H1&, const _Key&>{},
1293 "hash function must be invocable with an argument of key type");
1294 return _M_h1()(__k);
1295 }
1296
1297 std::size_t
1298 _M_bucket_index(const _Key&, __hash_code __c,
1299 std::size_t __bkt_count) const
1300 { return _M_h2()(__c, __bkt_count); }
1301
1302 std::size_t
1303 _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
1304 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1305 && noexcept(declval<const _H2&>()((__hash_code)0,
1306 (std::size_t)0)) )
1307 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __bkt_count); }
1308
1309 void
1310 _M_store_code(__node_type*, __hash_code) const
1311 { }
1312
1313 void
1314 _M_copy_code(__node_type*, const __node_type*) const
1315 { }
1316
1317 void
1318 _M_swap(_Hash_code_base& __x)
1319 {
1320 std::swap(__ebo_extract_key::_M_get(),
1321 __x.__ebo_extract_key::_M_get());
1322 std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
1323 std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
1324 }
1325
1326 const _ExtractKey&
1327 _M_extract() const { return __ebo_extract_key::_M_cget(); }
1328
1329 const _H1&
1330 _M_h1() const { return __ebo_h1::_M_cget(); }
1331
1332 const _H2&
1333 _M_h2() const { return __ebo_h2::_M_cget(); }
1334 };
1335
1336 /// Specialization: hash function and range-hashing function,
1337 /// caching hash codes. H is provided but ignored. Provides
1338 /// typedef and accessor required by C++ 11.
1339 template<typename _Key, typename _Value, typename _ExtractKey,
1340 typename _H1, typename _H2>
1341 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1343 : private _Hashtable_ebo_helper<0, _ExtractKey>,
1344 private _Hashtable_ebo_helper<1, _H1>,
1345 private _Hashtable_ebo_helper<2, _H2>
1346 {
1347 private:
1348 // Gives the local iterator implementation access to _M_h2().
1349 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1350 _Default_ranged_hash, true>;
1351
1355
1356 public:
1357 typedef _H1 hasher;
1358
1359 hasher
1360 hash_function() const
1361 { return _M_h1(); }
1362
1363 protected:
1364 typedef std::size_t __hash_code;
1366
1367 // We need the default constructor for _Hashtable default constructor.
1368 _Hash_code_base() = default;
1369 _Hash_code_base(const _ExtractKey& __ex,
1370 const _H1& __h1, const _H2& __h2,
1371 const _Default_ranged_hash&)
1372 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1373
1374 __hash_code
1375 _M_hash_code(const _Key& __k) const
1376 {
1377 static_assert(__is_invocable<const _H1&, const _Key&>{},
1378 "hash function must be invocable with an argument of key type");
1379 return _M_h1()(__k);
1380 }
1381
1382 std::size_t
1383 _M_bucket_index(const _Key&, __hash_code __c,
1384 std::size_t __bkt_count) const
1385 { return _M_h2()(__c, __bkt_count); }
1386
1387 std::size_t
1388 _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
1389 noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1390 (std::size_t)0)) )
1391 { return _M_h2()(__p->_M_hash_code, __bkt_count); }
1392
1393 void
1394 _M_store_code(__node_type* __n, __hash_code __c) const
1395 { __n->_M_hash_code = __c; }
1396
1397 void
1398 _M_copy_code(__node_type* __to, const __node_type* __from) const
1399 { __to->_M_hash_code = __from->_M_hash_code; }
1400
1401 void
1402 _M_swap(_Hash_code_base& __x)
1403 {
1404 std::swap(__ebo_extract_key::_M_get(),
1405 __x.__ebo_extract_key::_M_get());
1406 std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
1407 std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
1408 }
1409
1410 const _ExtractKey&
1411 _M_extract() const { return __ebo_extract_key::_M_cget(); }
1412
1413 const _H1&
1414 _M_h1() const { return __ebo_h1::_M_cget(); }
1415
1416 const _H2&
1417 _M_h2() const { return __ebo_h2::_M_cget(); }
1418 };
1419
1420 /// Partial specialization used when nodes contain a cached hash code.
1421 template<typename _Key, typename _Value, typename _ExtractKey,
1422 typename _H1, typename _H2, typename _Hash>
1423 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1424 _H1, _H2, _Hash, true>
1425 : private _Hashtable_ebo_helper<0, _H2>
1426 {
1427 protected:
1429 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1430 _H1, _H2, _Hash, true>;
1431
1432 _Local_iterator_base() = default;
1435 std::size_t __bkt, std::size_t __bkt_count)
1436 : __base_type(__base._M_h2()),
1437 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1438
1439 void
1440 _M_incr()
1441 {
1442 _M_cur = _M_cur->_M_next();
1443 if (_M_cur)
1444 {
1445 std::size_t __bkt
1446 = __base_type::_M_get()(_M_cur->_M_hash_code,
1447 _M_bucket_count);
1448 if (__bkt != _M_bucket)
1449 _M_cur = nullptr;
1450 }
1451 }
1452
1454 std::size_t _M_bucket;
1455 std::size_t _M_bucket_count;
1456
1457 public:
1458 const void*
1459 _M_curr() const { return _M_cur; } // for equality ops
1460
1461 std::size_t
1462 _M_get_bucket() const { return _M_bucket; } // for debug mode
1463 };
1464
1465 // Uninitialized storage for a _Hash_code_base.
1466 // This type is DefaultConstructible and Assignable even if the
1467 // _Hash_code_base type isn't, so that _Local_iterator_base<..., false>
1468 // can be DefaultConstructible and Assignable.
1469 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1470 struct _Hash_code_storage
1471 {
1472 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1473
1474 _Tp*
1475 _M_h() { return _M_storage._M_ptr(); }
1476
1477 const _Tp*
1478 _M_h() const { return _M_storage._M_ptr(); }
1479 };
1480
1481 // Empty partial specialization for empty _Hash_code_base types.
1482 template<typename _Tp>
1483 struct _Hash_code_storage<_Tp, true>
1484 {
1485 static_assert( std::is_empty<_Tp>::value, "Type must be empty" );
1486
1487 // As _Tp is an empty type there will be no bytes written/read through
1488 // the cast pointer, so no strict-aliasing violation.
1489 _Tp*
1490 _M_h() { return reinterpret_cast<_Tp*>(this); }
1491
1492 const _Tp*
1493 _M_h() const { return reinterpret_cast<const _Tp*>(this); }
1494 };
1495
1496 template<typename _Key, typename _Value, typename _ExtractKey,
1497 typename _H1, typename _H2, typename _Hash>
1498 using __hash_code_for_local_iter
1499 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1500 _H1, _H2, _Hash, false>>;
1501
1502 // Partial specialization used when hash codes are not cached
1503 template<typename _Key, typename _Value, typename _ExtractKey,
1504 typename _H1, typename _H2, typename _Hash>
1505 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1506 _H1, _H2, _Hash, false>
1507 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1508 {
1509 protected:
1510 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1511 _H1, _H2, _Hash, false>;
1512
1513 _Local_iterator_base() : _M_bucket_count(-1) { }
1514
1515 _Local_iterator_base(const __hash_code_base& __base,
1516 _Hash_node<_Value, false>* __p,
1517 std::size_t __bkt, std::size_t __bkt_count)
1518 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1519 { _M_init(__base); }
1520
1521 ~_Local_iterator_base()
1522 {
1523 if (_M_bucket_count != -1)
1524 _M_destroy();
1525 }
1526
1527 _Local_iterator_base(const _Local_iterator_base& __iter)
1528 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1529 _M_bucket_count(__iter._M_bucket_count)
1530 {
1531 if (_M_bucket_count != -1)
1532 _M_init(*__iter._M_h());
1533 }
1534
1535 _Local_iterator_base&
1536 operator=(const _Local_iterator_base& __iter)
1537 {
1538 if (_M_bucket_count != -1)
1539 _M_destroy();
1540 _M_cur = __iter._M_cur;
1541 _M_bucket = __iter._M_bucket;
1542 _M_bucket_count = __iter._M_bucket_count;
1543 if (_M_bucket_count != -1)
1544 _M_init(*__iter._M_h());
1545 return *this;
1546 }
1547
1548 void
1549 _M_incr()
1550 {
1551 _M_cur = _M_cur->_M_next();
1552 if (_M_cur)
1553 {
1554 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1555 _M_bucket_count);
1556 if (__bkt != _M_bucket)
1557 _M_cur = nullptr;
1558 }
1559 }
1560
1561 _Hash_node<_Value, false>* _M_cur;
1562 std::size_t _M_bucket;
1563 std::size_t _M_bucket_count;
1564
1565 void
1566 _M_init(const __hash_code_base& __base)
1567 { ::new(this->_M_h()) __hash_code_base(__base); }
1568
1569 void
1570 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1571
1572 public:
1573 const void*
1574 _M_curr() const { return _M_cur; } // for equality ops and debug mode
1575
1576 std::size_t
1577 _M_get_bucket() const { return _M_bucket; } // for debug mode
1578 };
1579
1580 template<typename _Key, typename _Value, typename _ExtractKey,
1581 typename _H1, typename _H2, typename _Hash, bool __cache>
1582 inline bool
1583 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1584 _H1, _H2, _Hash, __cache>& __x,
1585 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1586 _H1, _H2, _Hash, __cache>& __y)
1587 { return __x._M_curr() == __y._M_curr(); }
1588
1589 template<typename _Key, typename _Value, typename _ExtractKey,
1590 typename _H1, typename _H2, typename _Hash, bool __cache>
1591 inline bool
1592 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1593 _H1, _H2, _Hash, __cache>& __x,
1594 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1595 _H1, _H2, _Hash, __cache>& __y)
1596 { return __x._M_curr() != __y._M_curr(); }
1597
1598 /// local iterators
1599 template<typename _Key, typename _Value, typename _ExtractKey,
1600 typename _H1, typename _H2, typename _Hash,
1601 bool __constant_iterators, bool __cache>
1603 : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1604 _H1, _H2, _Hash, __cache>
1605 {
1606 private:
1607 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1608 _H1, _H2, _Hash, __cache>;
1609 using __hash_code_base = typename __base_type::__hash_code_base;
1610 public:
1611 typedef _Value value_type;
1612 typedef typename std::conditional<__constant_iterators,
1613 const _Value*, _Value*>::type
1614 pointer;
1615 typedef typename std::conditional<__constant_iterators,
1616 const _Value&, _Value&>::type
1617 reference;
1618 typedef std::ptrdiff_t difference_type;
1620
1621 _Local_iterator() = default;
1622
1623 _Local_iterator(const __hash_code_base& __base,
1625 std::size_t __bkt, std::size_t __bkt_count)
1626 : __base_type(__base, __n, __bkt, __bkt_count)
1627 { }
1628
1629 reference
1630 operator*() const
1631 { return this->_M_cur->_M_v(); }
1632
1633 pointer
1634 operator->() const
1635 { return this->_M_cur->_M_valptr(); }
1636
1638 operator++()
1639 {
1640 this->_M_incr();
1641 return *this;
1642 }
1643
1645 operator++(int)
1646 {
1647 _Local_iterator __tmp(*this);
1648 this->_M_incr();
1649 return __tmp;
1650 }
1651 };
1652
1653 /// local const_iterators
1654 template<typename _Key, typename _Value, typename _ExtractKey,
1655 typename _H1, typename _H2, typename _Hash,
1656 bool __constant_iterators, bool __cache>
1658 : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1659 _H1, _H2, _Hash, __cache>
1660 {
1661 private:
1662 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1663 _H1, _H2, _Hash, __cache>;
1664 using __hash_code_base = typename __base_type::__hash_code_base;
1665
1666 public:
1667 typedef _Value value_type;
1668 typedef const _Value* pointer;
1669 typedef const _Value& reference;
1670 typedef std::ptrdiff_t difference_type;
1672
1673 _Local_const_iterator() = default;
1674
1675 _Local_const_iterator(const __hash_code_base& __base,
1677 std::size_t __bkt, std::size_t __bkt_count)
1678 : __base_type(__base, __n, __bkt, __bkt_count)
1679 { }
1680
1681 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1682 _H1, _H2, _Hash,
1683 __constant_iterators,
1684 __cache>& __x)
1685 : __base_type(__x)
1686 { }
1687
1688 reference
1689 operator*() const
1690 { return this->_M_cur->_M_v(); }
1691
1692 pointer
1693 operator->() const
1694 { return this->_M_cur->_M_valptr(); }
1695
1697 operator++()
1698 {
1699 this->_M_incr();
1700 return *this;
1701 }
1702
1704 operator++(int)
1705 {
1706 _Local_const_iterator __tmp(*this);
1707 this->_M_incr();
1708 return __tmp;
1709 }
1710 };
1711
1712 /**
1713 * Primary class template _Hashtable_base.
1714 *
1715 * Helper class adding management of _Equal functor to
1716 * _Hash_code_base type.
1717 *
1718 * Base class templates are:
1719 * - __detail::_Hash_code_base
1720 * - __detail::_Hashtable_ebo_helper
1721 */
1722 template<typename _Key, typename _Value,
1723 typename _ExtractKey, typename _Equal,
1724 typename _H1, typename _H2, typename _Hash, typename _Traits>
1726 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1727 _Traits::__hash_cached::value>,
1728 private _Hashtable_ebo_helper<0, _Equal>
1729 {
1730 public:
1731 typedef _Key key_type;
1732 typedef _Value value_type;
1733 typedef _Equal key_equal;
1734 typedef std::size_t size_type;
1735 typedef std::ptrdiff_t difference_type;
1736
1737 using __traits_type = _Traits;
1738 using __hash_cached = typename __traits_type::__hash_cached;
1739 using __constant_iterators = typename __traits_type::__constant_iterators;
1740 using __unique_keys = typename __traits_type::__unique_keys;
1741
1742 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1743 _H1, _H2, _Hash,
1744 __hash_cached::value>;
1745
1746 using __hash_code = typename __hash_code_base::__hash_code;
1747 using __node_type = typename __hash_code_base::__node_type;
1748
1749 using iterator = __detail::_Node_iterator<value_type,
1750 __constant_iterators::value,
1751 __hash_cached::value>;
1752
1754 __constant_iterators::value,
1755 __hash_cached::value>;
1756
1757 using local_iterator = __detail::_Local_iterator<key_type, value_type,
1758 _ExtractKey, _H1, _H2, _Hash,
1759 __constant_iterators::value,
1760 __hash_cached::value>;
1761
1763 value_type,
1764 _ExtractKey, _H1, _H2, _Hash,
1765 __constant_iterators::value,
1766 __hash_cached::value>;
1767
1768 using __ireturn_type = typename std::conditional<__unique_keys::value,
1770 iterator>::type;
1771 private:
1773
1774 template<typename _NodeT>
1775 struct _Equal_hash_code
1776 {
1777 static bool
1778 _S_equals(__hash_code, const _NodeT&)
1779 { return true; }
1780 };
1781
1782 template<typename _Ptr2>
1783 struct _Equal_hash_code<_Hash_node<_Ptr2, true>>
1784 {
1785 static bool
1786 _S_equals(__hash_code __c, const _Hash_node<_Ptr2, true>& __n)
1787 { return __c == __n._M_hash_code; }
1788 };
1789
1790 protected:
1791 _Hashtable_base() = default;
1792 _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
1793 const _Hash& __hash, const _Equal& __eq)
1794 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1795 { }
1796
1797 bool
1798 _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
1799 {
1800 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1801 "key equality predicate must be invocable with two arguments of "
1802 "key type");
1803 return _Equal_hash_code<__node_type>::_S_equals(__c, *__n)
1804 && _M_eq()(__k, this->_M_extract()(__n->_M_v()));
1805 }
1806
1807 void
1808 _M_swap(_Hashtable_base& __x)
1809 {
1810 __hash_code_base::_M_swap(__x);
1811 std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get());
1812 }
1813
1814 const _Equal&
1815 _M_eq() const { return _EqualEBO::_M_cget(); }
1816 };
1817
1818 /**
1819 * Primary class template _Equality.
1820 *
1821 * This is for implementing equality comparison for unordered
1822 * containers, per N3068, by John Lakos and Pablo Halpern.
1823 * Algorithmically, we follow closely the reference implementations
1824 * therein.
1825 */
1826 template<typename _Key, typename _Value, typename _Alloc,
1827 typename _ExtractKey, typename _Equal,
1828 typename _H1, typename _H2, typename _Hash,
1829 typename _RehashPolicy, typename _Traits,
1830 bool _Unique_keys = _Traits::__unique_keys::value>
1832
1833 /// unordered_map and unordered_set specializations.
1834 template<typename _Key, typename _Value, typename _Alloc,
1835 typename _ExtractKey, typename _Equal,
1836 typename _H1, typename _H2, typename _Hash,
1837 typename _RehashPolicy, typename _Traits>
1838 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1839 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1840 {
1841 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1842 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1843
1844 bool
1845 _M_equal(const __hashtable&) const;
1846 };
1847
1848 template<typename _Key, typename _Value, typename _Alloc,
1849 typename _ExtractKey, typename _Equal,
1850 typename _H1, typename _H2, typename _Hash,
1851 typename _RehashPolicy, typename _Traits>
1852 bool
1853 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1854 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
1855 _M_equal(const __hashtable& __other) const
1856 {
1857 using __node_base = typename __hashtable::__node_base;
1858 using __node_type = typename __hashtable::__node_type;
1859 const __hashtable* __this = static_cast<const __hashtable*>(this);
1860 if (__this->size() != __other.size())
1861 return false;
1862
1863 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1864 {
1865 std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
1866 __node_base* __prev_n = __other._M_buckets[__ybkt];
1867 if (!__prev_n)
1868 return false;
1869
1870 for (__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);;
1871 __n = __n->_M_next())
1872 {
1873 if (__n->_M_v() == *__itx)
1874 break;
1875
1876 if (!__n->_M_nxt
1877 || __other._M_bucket_index(__n->_M_next()) != __ybkt)
1878 return false;
1879 }
1880 }
1881
1882 return true;
1883 }
1884
1885 /// unordered_multiset and unordered_multimap specializations.
1886 template<typename _Key, typename _Value, typename _Alloc,
1887 typename _ExtractKey, typename _Equal,
1888 typename _H1, typename _H2, typename _Hash,
1889 typename _RehashPolicy, typename _Traits>
1890 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1891 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1892 {
1893 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1894 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1895
1896 bool
1897 _M_equal(const __hashtable&) const;
1898 };
1899
1900 template<typename _Key, typename _Value, typename _Alloc,
1901 typename _ExtractKey, typename _Equal,
1902 typename _H1, typename _H2, typename _Hash,
1903 typename _RehashPolicy, typename _Traits>
1904 bool
1905 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1906 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
1907 _M_equal(const __hashtable& __other) const
1908 {
1909 using __node_base = typename __hashtable::__node_base;
1910 using __node_type = typename __hashtable::__node_type;
1911 const __hashtable* __this = static_cast<const __hashtable*>(this);
1912 if (__this->size() != __other.size())
1913 return false;
1914
1915 for (auto __itx = __this->begin(); __itx != __this->end();)
1916 {
1917 std::size_t __x_count = 1;
1918 auto __itx_end = __itx;
1919 for (++__itx_end; __itx_end != __this->end()
1920 && __this->key_eq()(_ExtractKey()(*__itx),
1921 _ExtractKey()(*__itx_end));
1922 ++__itx_end)
1923 ++__x_count;
1924
1925 std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
1926 __node_base* __y_prev_n = __other._M_buckets[__ybkt];
1927 if (!__y_prev_n)
1928 return false;
1929
1930 __node_type* __y_n = static_cast<__node_type*>(__y_prev_n->_M_nxt);
1931 for (;; __y_n = __y_n->_M_next())
1932 {
1933 if (__this->key_eq()(_ExtractKey()(__y_n->_M_v()),
1934 _ExtractKey()(*__itx)))
1935 break;
1936
1937 if (!__y_n->_M_nxt
1938 || __other._M_bucket_index(__y_n->_M_next()) != __ybkt)
1939 return false;
1940 }
1941
1942 typename __hashtable::const_iterator __ity(__y_n);
1943 for (auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
1944 if (--__x_count == 0)
1945 break;
1946
1947 if (__x_count != 0)
1948 return false;
1949
1950 if (!std::is_permutation(__itx, __itx_end, __ity))
1951 return false;
1952
1953 __itx = __itx_end;
1954 }
1955 return true;
1956 }
1957
1958 /**
1959 * This type deals with all allocation and keeps an allocator instance
1960 * through inheritance to benefit from EBO when possible.
1961 */
1962 template<typename _NodeAlloc>
1963 struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc>
1964 {
1965 private:
1967 public:
1968 using __node_type = typename _NodeAlloc::value_type;
1969 using __node_alloc_type = _NodeAlloc;
1970 // Use __gnu_cxx to benefit from _S_always_equal and al.
1972
1973 using __value_alloc_traits = typename __node_alloc_traits::template
1974 rebind_traits<typename __node_type::value_type>;
1975
1977 using __bucket_type = __node_base*;
1978 using __bucket_alloc_type =
1979 __alloc_rebind<__node_alloc_type, __bucket_type>;
1981
1982 _Hashtable_alloc() = default;
1983 _Hashtable_alloc(const _Hashtable_alloc&) = default;
1985
1986 template<typename _Alloc>
1987 _Hashtable_alloc(_Alloc&& __a)
1988 : __ebo_node_alloc(std::forward<_Alloc>(__a))
1989 { }
1990
1991 __node_alloc_type&
1992 _M_node_allocator()
1993 { return __ebo_node_alloc::_M_get(); }
1994
1995 const __node_alloc_type&
1996 _M_node_allocator() const
1997 { return __ebo_node_alloc::_M_cget(); }
1998
1999 // Allocate a node and construct an element within it.
2000 template<typename... _Args>
2001 __node_type*
2002 _M_allocate_node(_Args&&... __args);
2003
2004 // Destroy the element within a node and deallocate the node.
2005 void
2006 _M_deallocate_node(__node_type* __n);
2007
2008 // Deallocate a node.
2009 void
2010 _M_deallocate_node_ptr(__node_type* __n);
2011
2012 // Deallocate the linked list of nodes pointed to by __n.
2013 // The elements within the nodes are destroyed.
2014 void
2015 _M_deallocate_nodes(__node_type* __n);
2016
2018 _M_allocate_buckets(std::size_t __bkt_count);
2019
2020 void
2021 _M_deallocate_buckets(__bucket_type*, std::size_t __bkt_count);
2022 };
2023
2024 // Definitions of class template _Hashtable_alloc's out-of-line member
2025 // functions.
2026 template<typename _NodeAlloc>
2027 template<typename... _Args>
2028 auto
2030 -> __node_type*
2031 {
2032 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2033 __node_type* __n = std::__to_address(__nptr);
2034 __try
2035 {
2036 ::new ((void*)__n) __node_type;
2037 __node_alloc_traits::construct(_M_node_allocator(),
2038 __n->_M_valptr(),
2039 std::forward<_Args>(__args)...);
2040 return __n;
2041 }
2042 __catch(...)
2043 {
2044 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2045 __throw_exception_again;
2046 }
2047 }
2048
2049 template<typename _NodeAlloc>
2050 void
2051 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2052 {
2053 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2054 _M_deallocate_node_ptr(__n);
2055 }
2056
2057 template<typename _NodeAlloc>
2058 void
2059 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n)
2060 {
2061 typedef typename __node_alloc_traits::pointer _Ptr;
2062 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
2063 __n->~__node_type();
2064 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2065 }
2066
2067 template<typename _NodeAlloc>
2068 void
2069 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
2070 {
2071 while (__n)
2072 {
2073 __node_type* __tmp = __n;
2074 __n = __n->_M_next();
2075 _M_deallocate_node(__tmp);
2076 }
2077 }
2078
2079 template<typename _NodeAlloc>
2080 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
2081 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
2082 {
2083 __bucket_alloc_type __alloc(_M_node_allocator());
2084
2085 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __bkt_count);
2086 __bucket_type* __p = std::__to_address(__ptr);
2087 __builtin_memset(__p, 0, __bkt_count * sizeof(__bucket_type));
2088 return __p;
2089 }
2090
2091 template<typename _NodeAlloc>
2092 void
2093 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2094 std::size_t __bkt_count)
2095 {
2096 typedef typename __bucket_alloc_traits::pointer _Ptr;
2097 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
2098 __bucket_alloc_type __alloc(_M_node_allocator());
2099 __bucket_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
2100 }
2101
2102 //@} hashtable-detail
2103} // namespace __detail
2104_GLIBCXX_END_NAMESPACE_VERSION
2105} // namespace std
2106
2107#endif // _HASHTABLE_POLICY_H
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 tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
Definition: tuple:1485
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
Definition: stl_pair.h:82
std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2 not less than __n.
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr _Iterator __base(_Iterator __it)
initializer_list
tuple_element
Definition: array:424
Properties of fundamental types.
Definition: limits:313
static constexpr _Tp max() noexcept
Definition: limits:321
Primary class template, tuple.
Definition: tuple:516
integral_constant
Definition: type_traits:58
Define a member typedef type to one of two argument types.
Definition: type_traits:2188
is_empty
Definition: type_traits:717
is_constructible
Definition: type_traits:908
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:2170
Uniform interface to all allocator types.
Traits class for iterators.
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:83
Marking input iterators.
Forward iterators support a superset of input iterator operations.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:212
Uniform interface to C++98 and C++11 allocators.