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