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