1// hashtable.h header -*- C++ -*-
2
3// Copyright (C) 2007-2022 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.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{unordered_map, unordered_set}
28 */
29
30#ifndef _HASHTABLE_H
31#define _HASHTABLE_H 1
32
33#pragma GCC system_header
34
35#include <bits/hashtable_policy.h>
36#include <bits/enable_special_members.h>
37#if __cplusplus > 201402L
38# include <bits/node_handle.h>
39#endif
40#include <bits/functional_hash.h>
41#include <bits/stl_function.h> // equal_to, _Identity, _Select1st
42
43namespace std _GLIBCXX_VISIBILITY(default)
44{
45_GLIBCXX_BEGIN_NAMESPACE_VERSION
46/// @cond undocumented
47
48 template<typename _Tp, typename _Hash>
49 using __cache_default
50 = __not_<__and_<// Do not cache for fast hasher.
51 __is_fast_hash<_Hash>,
52 // Mandatory to have erase not throwing.
53 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
54
55 // Helper to conditionally delete the default constructor.
56 // The _Hash_node_base type is used to distinguish this specialization
57 // from any other potentially-overlapping subobjects of the hashtable.
58 template<typename _Equal, typename _Hash, typename _Allocator>
59 using _Hashtable_enable_default_ctor
60 = _Enable_default_constructor<__and_<is_default_constructible<_Equal>,
61 is_default_constructible<_Hash>,
62 is_default_constructible<_Allocator>>{},
63 __detail::_Hash_node_base>;
64
65 /**
66 * Primary class template _Hashtable.
67 *
68 * @ingroup hashtable-detail
69 *
70 * @tparam _Value CopyConstructible type.
71 *
72 * @tparam _Key CopyConstructible type.
73 *
74 * @tparam _Alloc An allocator type
75 * ([lib.allocator.requirements]) whose _Alloc::value_type is
76 * _Value. As a conforming extension, we allow for
77 * _Alloc::value_type != _Value.
78 *
79 * @tparam _ExtractKey Function object that takes an object of type
80 * _Value and returns a value of type _Key.
81 *
82 * @tparam _Equal Function object that takes two objects of type k
83 * and returns a bool-like value that is true if the two objects
84 * are considered equal.
85 *
86 * @tparam _Hash The hash function. A unary function object with
87 * argument type _Key and result type size_t. Return values should
88 * be distributed over the entire range [0, numeric_limits<size_t>:::max()].
89 *
90 * @tparam _RangeHash The range-hashing function (in the terminology of
91 * Tavori and Dreizin). A binary function object whose argument
92 * types and result type are all size_t. Given arguments r and N,
93 * the return value is in the range [0, N).
94 *
95 * @tparam _Unused Not used.
96 *
97 * @tparam _RehashPolicy Policy class with three members, all of
98 * which govern the bucket count. _M_next_bkt(n) returns a bucket
99 * count no smaller than n. _M_bkt_for_elements(n) returns a
100 * bucket count appropriate for an element count of n.
101 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
102 * current bucket count is n_bkt and the current element count is
103 * n_elt, we need to increase the bucket count for n_ins insertions.
104 * If so, returns make_pair(true, n), where n is the new bucket count. If
105 * not, returns make_pair(false, <anything>)
106 *
107 * @tparam _Traits Compile-time class with three boolean
108 * std::integral_constant members: __cache_hash_code, __constant_iterators,
109 * __unique_keys.
110 *
111 * Each _Hashtable data structure has:
112 *
113 * - _Bucket[] _M_buckets
114 * - _Hash_node_base _M_before_begin
115 * - size_type _M_bucket_count
116 * - size_type _M_element_count
117 *
118 * with _Bucket being _Hash_node_base* and _Hash_node containing:
119 *
120 * - _Hash_node* _M_next
121 * - Tp _M_value
122 * - size_t _M_hash_code if cache_hash_code is true
123 *
124 * In terms of Standard containers the hashtable is like the aggregation of:
125 *
126 * - std::forward_list<_Node> containing the elements
127 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
128 *
129 * The non-empty buckets contain the node before the first node in the
130 * bucket. This design makes it possible to implement something like a
131 * std::forward_list::insert_after on container insertion and
132 * std::forward_list::erase_after on container erase
133 * calls. _M_before_begin is equivalent to
134 * std::forward_list::before_begin. Empty buckets contain
135 * nullptr. Note that one of the non-empty buckets contains
136 * &_M_before_begin which is not a dereferenceable node so the
137 * node pointer in a bucket shall never be dereferenced, only its
138 * next node can be.
139 *
140 * Walking through a bucket's nodes requires a check on the hash code to
141 * see if each node is still in the bucket. Such a design assumes a
142 * quite efficient hash functor and is one of the reasons it is
143 * highly advisable to set __cache_hash_code to true.
144 *
145 * The container iterators are simply built from nodes. This way
146 * incrementing the iterator is perfectly efficient independent of
147 * how many empty buckets there are in the container.
148 *
149 * On insert we compute the element's hash code and use it to find the
150 * bucket index. If the element must be inserted in an empty bucket
151 * we add it at the beginning of the singly linked list and make the
152 * bucket point to _M_before_begin. The bucket that used to point to
153 * _M_before_begin, if any, is updated to point to its new before
154 * begin node.
155 *
156 * On erase, the simple iterator design requires using the hash
157 * functor to get the index of the bucket to update. For this
158 * reason, when __cache_hash_code is set to false the hash functor must
159 * not throw and this is enforced by a static assertion.
160 *
161 * Functionality is implemented by decomposition into base classes,
162 * where the derived _Hashtable class is used in _Map_base,
163 * _Insert, _Rehash_base, and _Equality base classes to access the
164 * "this" pointer. _Hashtable_base is used in the base classes as a
165 * non-recursive, fully-completed-type so that detailed nested type
166 * information, such as iterator type and node type, can be
167 * used. This is similar to the "Curiously Recurring Template
168 * Pattern" (CRTP) technique, but uses a reconstructed, not
169 * explicitly passed, template pattern.
170 *
171 * Base class templates are:
172 * - __detail::_Hashtable_base
173 * - __detail::_Map_base
174 * - __detail::_Insert
175 * - __detail::_Rehash_base
176 * - __detail::_Equality
177 */
178 template<typename _Key, typename _Value, typename _Alloc,
179 typename _ExtractKey, typename _Equal,
180 typename _Hash, typename _RangeHash, typename _Unused,
181 typename _RehashPolicy, typename _Traits>
182 class _Hashtable
183 : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
184 _Hash, _RangeHash, _Unused, _Traits>,
185 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
186 _Hash, _RangeHash, _Unused,
187 _RehashPolicy, _Traits>,
188 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
189 _Hash, _RangeHash, _Unused,
190 _RehashPolicy, _Traits>,
191 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
192 _Hash, _RangeHash, _Unused,
193 _RehashPolicy, _Traits>,
194 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
195 _Hash, _RangeHash, _Unused,
196 _RehashPolicy, _Traits>,
197 private __detail::_Hashtable_alloc<
198 __alloc_rebind<_Alloc,
199 __detail::_Hash_node<_Value,
200 _Traits::__hash_cached::value>>>,
201 private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
202 {
203 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
204 "unordered container must have a non-const, non-volatile value_type");
205#if __cplusplus > 201703L || defined __STRICT_ANSI__
206 static_assert(is_same<typename _Alloc::value_type, _Value>{},
207 "unordered container must have the same value_type as its allocator");
208#endif
209
210 using __traits_type = _Traits;
211 using __hash_cached = typename __traits_type::__hash_cached;
212 using __constant_iterators = typename __traits_type::__constant_iterators;
213 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
214 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
215
216 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
217
218 using __node_value_type =
219 __detail::_Hash_node_value<_Value, __hash_cached::value>;
220 using __node_ptr = typename __hashtable_alloc::__node_ptr;
221 using __value_alloc_traits =
222 typename __hashtable_alloc::__value_alloc_traits;
223 using __node_alloc_traits =
224 typename __hashtable_alloc::__node_alloc_traits;
225 using __node_base = typename __hashtable_alloc::__node_base;
226 using __node_base_ptr = typename __hashtable_alloc::__node_base_ptr;
227 using __buckets_ptr = typename __hashtable_alloc::__buckets_ptr;
228
229 using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
230 _Equal, _Hash,
231 _RangeHash, _Unused,
232 _RehashPolicy, _Traits>;
233 using __enable_default_ctor
234 = _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>;
235
236 public:
237 typedef _Key key_type;
238 typedef _Value value_type;
239 typedef _Alloc allocator_type;
240 typedef _Equal key_equal;
241
242 // mapped_type, if present, comes from _Map_base.
243 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
244 typedef typename __value_alloc_traits::pointer pointer;
245 typedef typename __value_alloc_traits::const_pointer const_pointer;
246 typedef value_type& reference;
247 typedef const value_type& const_reference;
248
249 using iterator = typename __insert_base::iterator;
250
251 using const_iterator = typename __insert_base::const_iterator;
252
253 using local_iterator = __detail::_Local_iterator<key_type, _Value,
254 _ExtractKey, _Hash, _RangeHash, _Unused,
255 __constant_iterators::value,
256 __hash_cached::value>;
257
258 using const_local_iterator = __detail::_Local_const_iterator<
259 key_type, _Value,
260 _ExtractKey, _Hash, _RangeHash, _Unused,
261 __constant_iterators::value, __hash_cached::value>;
262
263 private:
264 using __rehash_type = _RehashPolicy;
265 using __rehash_state = typename __rehash_type::_State;
266
267 using __unique_keys = typename __traits_type::__unique_keys;
268
269 using __hashtable_base = __detail::
270 _Hashtable_base<_Key, _Value, _ExtractKey,
271 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
272
273 using __hash_code_base = typename __hashtable_base::__hash_code_base;
274 using __hash_code = typename __hashtable_base::__hash_code;
275 using __ireturn_type = typename __insert_base::__ireturn_type;
276
277 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
278 _Equal, _Hash, _RangeHash, _Unused,
279 _RehashPolicy, _Traits>;
280
281 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
282 _ExtractKey, _Equal,
283 _Hash, _RangeHash, _Unused,
284 _RehashPolicy, _Traits>;
285
286 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
287 _Equal, _Hash, _RangeHash, _Unused,
288 _RehashPolicy, _Traits>;
289
290 using __reuse_or_alloc_node_gen_t =
291 __detail::_ReuseOrAllocNode<__node_alloc_type>;
292 using __alloc_node_gen_t =
293 __detail::_AllocNode<__node_alloc_type>;
294 using __node_builder_t =
295 __detail::_NodeBuilder<_ExtractKey>;
296
297 // Simple RAII type for managing a node containing an element
298 struct _Scoped_node
299 {
300 // Take ownership of a node with a constructed element.
301 _Scoped_node(__node_ptr __n, __hashtable_alloc* __h)
302 : _M_h(__h), _M_node(__n) { }
303
304 // Allocate a node and construct an element within it.
305 template<typename... _Args>
306 _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
307 : _M_h(__h),
308 _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
309 { }
310
311 // Destroy element and deallocate node.
312 ~_Scoped_node() { if (_M_node) _M_h->_M_deallocate_node(_M_node); };
313
314 _Scoped_node(const _Scoped_node&) = delete;
315 _Scoped_node& operator=(const _Scoped_node&) = delete;
316
317 __hashtable_alloc* _M_h;
318 __node_ptr _M_node;
319 };
320
321 template<typename _Ht>
322 static constexpr
323 __conditional_t<std::is_lvalue_reference<_Ht>::value,
324 const value_type&, value_type&&>
325 __fwd_value_for(value_type& __val) noexcept
326 { return std::move(__val); }
327
328 // Compile-time diagnostics.
329
330 // _Hash_code_base has everything protected, so use this derived type to
331 // access it.
332 struct __hash_code_base_access : __hash_code_base
333 { using __hash_code_base::_M_bucket_index; };
334
335 // To get bucket index we need _RangeHash not to throw.
336 static_assert(is_nothrow_default_constructible<_RangeHash>::value,
337 "Functor used to map hash code to bucket index"
338 " must be nothrow default constructible");
339 static_assert(noexcept(
340 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
341 "Functor used to map hash code to bucket index must be"
342 " noexcept");
343
344 // To compute bucket index we also need _ExtratKey not to throw.
345 static_assert(is_nothrow_default_constructible<_ExtractKey>::value,
346 "_ExtractKey must be nothrow default constructible");
347 static_assert(noexcept(
348 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
349 "_ExtractKey functor must be noexcept invocable");
350
351 template<typename _Keya, typename _Valuea, typename _Alloca,
352 typename _ExtractKeya, typename _Equala,
353 typename _Hasha, typename _RangeHasha, typename _Unuseda,
354 typename _RehashPolicya, typename _Traitsa,
355 bool _Unique_keysa>
356 friend struct __detail::_Map_base;
357
358 template<typename _Keya, typename _Valuea, typename _Alloca,
359 typename _ExtractKeya, typename _Equala,
360 typename _Hasha, typename _RangeHasha, typename _Unuseda,
361 typename _RehashPolicya, typename _Traitsa>
362 friend struct __detail::_Insert_base;
363
364 template<typename _Keya, typename _Valuea, typename _Alloca,
365 typename _ExtractKeya, typename _Equala,
366 typename _Hasha, typename _RangeHasha, typename _Unuseda,
367 typename _RehashPolicya, typename _Traitsa,
368 bool _Constant_iteratorsa>
369 friend struct __detail::_Insert;
370
371 template<typename _Keya, typename _Valuea, typename _Alloca,
372 typename _ExtractKeya, typename _Equala,
373 typename _Hasha, typename _RangeHasha, typename _Unuseda,
374 typename _RehashPolicya, typename _Traitsa,
375 bool _Unique_keysa>
376 friend struct __detail::_Equality;
377
378 public:
379 using size_type = typename __hashtable_base::size_type;
380 using difference_type = typename __hashtable_base::difference_type;
381
382#if __cplusplus > 201402L
383 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
384 using insert_return_type = _Node_insert_return<iterator, node_type>;
385#endif
386
387 private:
388 __buckets_ptr _M_buckets = &_M_single_bucket;
389 size_type _M_bucket_count = 1;
390 __node_base _M_before_begin;
391 size_type _M_element_count = 0;
392 _RehashPolicy _M_rehash_policy;
393
394 // A single bucket used when only need for 1 bucket. Especially
395 // interesting in move semantic to leave hashtable with only 1 bucket
396 // which is not allocated so that we can have those operations noexcept
397 // qualified.
398 // Note that we can't leave hashtable with 0 bucket without adding
399 // numerous checks in the code to avoid 0 modulus.
400 __node_base_ptr _M_single_bucket = nullptr;
401
402 void
403 _M_update_bbegin()
404 {
405 if (_M_begin())
406 _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin;
407 }
408
409 void
410 _M_update_bbegin(__node_ptr __n)
411 {
412 _M_before_begin._M_nxt = __n;
413 _M_update_bbegin();
414 }
415
416 bool
417 _M_uses_single_bucket(__buckets_ptr __bkts) const
418 { return __builtin_expect(__bkts == &_M_single_bucket, false); }
419
420 bool
421 _M_uses_single_bucket() const
422 { return _M_uses_single_bucket(_M_buckets); }
423
424 static constexpr size_t
425 __small_size_threshold() noexcept
426 {
427 return
428 __detail::_Hashtable_hash_traits<_Hash>::__small_size_threshold();
429 }
430
431 __hashtable_alloc&
432 _M_base_alloc() { return *this; }
433
434 __buckets_ptr
435 _M_allocate_buckets(size_type __bkt_count)
436 {
437 if (__builtin_expect(__bkt_count == 1, false))
438 {
439 _M_single_bucket = nullptr;
440 return &_M_single_bucket;
441 }
442
443 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
444 }
445
446 void
447 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
448 {
449 if (_M_uses_single_bucket(__bkts))
450 return;
451
452 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
453 }
454
455 void
456 _M_deallocate_buckets()
457 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
458
459 // Gets bucket begin, deals with the fact that non-empty buckets contain
460 // their before begin node.
461 __node_ptr
462 _M_bucket_begin(size_type __bkt) const;
463
464 __node_ptr
465 _M_begin() const
466 { return static_cast<__node_ptr>(_M_before_begin._M_nxt); }
467
468 // Assign *this using another _Hashtable instance. Whether elements
469 // are copied or moved depends on the _Ht reference.
470 template<typename _Ht>
471 void
472 _M_assign_elements(_Ht&&);
473
474 template<typename _Ht, typename _NodeGenerator>
475 void
476 _M_assign(_Ht&&, const _NodeGenerator&);
477
478 void
479 _M_move_assign(_Hashtable&&, true_type);
480
481 void
482 _M_move_assign(_Hashtable&&, false_type);
483
484 void
485 _M_reset() noexcept;
486
487 _Hashtable(const _Hash& __h, const _Equal& __eq,
488 const allocator_type& __a)
489 : __hashtable_base(__h, __eq),
490 __hashtable_alloc(__node_alloc_type(__a)),
491 __enable_default_ctor(_Enable_default_constructor_tag{})
492 { }
493
494 template<bool _No_realloc = true>
495 static constexpr bool
496 _S_nothrow_move()
497 {
498#if __cplusplus <= 201402L
499 return __and_<__bool_constant<_No_realloc>,
500 is_nothrow_copy_constructible<_Hash>,
501 is_nothrow_copy_constructible<_Equal>>::value;
502#else
503 if constexpr (_No_realloc)
504 if constexpr (is_nothrow_copy_constructible<_Hash>())
505 return is_nothrow_copy_constructible<_Equal>();
506 return false;
507#endif
508 }
509
510 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
511 true_type /* alloc always equal */)
512 noexcept(_S_nothrow_move());
513
514 _Hashtable(_Hashtable&&, __node_alloc_type&&,
515 false_type /* alloc always equal */);
516
517 template<typename _InputIterator>
518 _Hashtable(_InputIterator __first, _InputIterator __last,
519 size_type __bkt_count_hint,
520 const _Hash&, const _Equal&, const allocator_type&,
521 true_type __uks);
522
523 template<typename _InputIterator>
524 _Hashtable(_InputIterator __first, _InputIterator __last,
525 size_type __bkt_count_hint,
526 const _Hash&, const _Equal&, const allocator_type&,
527 false_type __uks);
528
529 public:
530 // Constructor, destructor, assignment, swap
531 _Hashtable() = default;
532
533 _Hashtable(const _Hashtable&);
534
535 _Hashtable(const _Hashtable&, const allocator_type&);
536
537 explicit
538 _Hashtable(size_type __bkt_count_hint,
539 const _Hash& __hf = _Hash(),
540 const key_equal& __eql = key_equal(),
541 const allocator_type& __a = allocator_type());
542
543 // Use delegating constructors.
544 _Hashtable(_Hashtable&& __ht)
545 noexcept(_S_nothrow_move())
546 : _Hashtable(std::move(__ht), std::move(__ht._M_node_allocator()),
547 true_type{})
548 { }
549
550 _Hashtable(_Hashtable&& __ht, const allocator_type& __a)
551 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
552 : _Hashtable(std::move(__ht), __node_alloc_type(__a),
553 typename __node_alloc_traits::is_always_equal{})
554 { }
555
556 explicit
557 _Hashtable(const allocator_type& __a)
558 : __hashtable_alloc(__node_alloc_type(__a)),
559 __enable_default_ctor(_Enable_default_constructor_tag{})
560 { }
561
562 template<typename _InputIterator>
563 _Hashtable(_InputIterator __f, _InputIterator __l,
564 size_type __bkt_count_hint = 0,
565 const _Hash& __hf = _Hash(),
566 const key_equal& __eql = key_equal(),
567 const allocator_type& __a = allocator_type())
568 : _Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
569 __unique_keys{})
570 { }
571
572 _Hashtable(initializer_list<value_type> __l,
573 size_type __bkt_count_hint = 0,
574 const _Hash& __hf = _Hash(),
575 const key_equal& __eql = key_equal(),
576 const allocator_type& __a = allocator_type())
577 : _Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
578 __hf, __eql, __a, __unique_keys{})
579 { }
580
581 _Hashtable&
582 operator=(const _Hashtable& __ht);
583
584 _Hashtable&
585 operator=(_Hashtable&& __ht)
586 noexcept(__node_alloc_traits::_S_nothrow_move()
587 && is_nothrow_move_assignable<_Hash>::value
588 && is_nothrow_move_assignable<_Equal>::value)
589 {
590 constexpr bool __move_storage =
591 __node_alloc_traits::_S_propagate_on_move_assign()
592 || __node_alloc_traits::_S_always_equal();
593 _M_move_assign(std::move(__ht), __bool_constant<__move_storage>());
594 return *this;
595 }
596
597 _Hashtable&
598 operator=(initializer_list<value_type> __l)
599 {
600 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
601 _M_before_begin._M_nxt = nullptr;
602 clear();
603
604 // We consider that all elements of __l are going to be inserted.
605 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
606
607 // Do not shrink to keep potential user reservation.
608 if (_M_bucket_count < __l_bkt_count)
609 rehash(__l_bkt_count);
610
611 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
612 return *this;
613 }
614
615 ~_Hashtable() noexcept;
616
617 void
618 swap(_Hashtable&)
619 noexcept(__and_<__is_nothrow_swappable<_Hash>,
620 __is_nothrow_swappable<_Equal>>::value);
621
622 // Basic container operations
623 iterator
624 begin() noexcept
625 { return iterator(_M_begin()); }
626
627 const_iterator
628 begin() const noexcept
629 { return const_iterator(_M_begin()); }
630
631 iterator
632 end() noexcept
633 { return iterator(nullptr); }
634
635 const_iterator
636 end() const noexcept
637 { return const_iterator(nullptr); }
638
639 const_iterator
640 cbegin() const noexcept
641 { return const_iterator(_M_begin()); }
642
643 const_iterator
644 cend() const noexcept
645 { return const_iterator(nullptr); }
646
647 size_type
648 size() const noexcept
649 { return _M_element_count; }
650
651 _GLIBCXX_NODISCARD bool
652 empty() const noexcept
653 { return size() == 0; }
654
655 allocator_type
656 get_allocator() const noexcept
657 { return allocator_type(this->_M_node_allocator()); }
658
659 size_type
660 max_size() const noexcept
661 { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
662
663 // Observers
664 key_equal
665 key_eq() const
666 { return this->_M_eq(); }
667
668 // hash_function, if present, comes from _Hash_code_base.
669
670 // Bucket operations
671 size_type
672 bucket_count() const noexcept
673 { return _M_bucket_count; }
674
675 size_type
676 max_bucket_count() const noexcept
677 { return max_size(); }
678
679 size_type
680 bucket_size(size_type __bkt) const
681 { return std::distance(begin(__bkt), end(__bkt)); }
682
683 size_type
684 bucket(const key_type& __k) const
685 { return _M_bucket_index(this->_M_hash_code(__k)); }
686
687 local_iterator
688 begin(size_type __bkt)
689 {
690 return local_iterator(*this, _M_bucket_begin(__bkt),
691 __bkt, _M_bucket_count);
692 }
693
694 local_iterator
695 end(size_type __bkt)
696 { return local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
697
698 const_local_iterator
699 begin(size_type __bkt) const
700 {
701 return const_local_iterator(*this, _M_bucket_begin(__bkt),
702 __bkt, _M_bucket_count);
703 }
704
705 const_local_iterator
706 end(size_type __bkt) const
707 { return const_local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
708
709 // DR 691.
710 const_local_iterator
711 cbegin(size_type __bkt) const
712 {
713 return const_local_iterator(*this, _M_bucket_begin(__bkt),
714 __bkt, _M_bucket_count);
715 }
716
717 const_local_iterator
718 cend(size_type __bkt) const
719 { return const_local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
720
721 float
722 load_factor() const noexcept
723 {
724 return static_cast<float>(size()) / static_cast<float>(bucket_count());
725 }
726
727 // max_load_factor, if present, comes from _Rehash_base.
728
729 // Generalization of max_load_factor. Extension, not found in
730 // TR1. Only useful if _RehashPolicy is something other than
731 // the default.
732 const _RehashPolicy&
733 __rehash_policy() const
734 { return _M_rehash_policy; }
735
736 void
737 __rehash_policy(const _RehashPolicy& __pol)
738 { _M_rehash_policy = __pol; }
739
740 // Lookup.
741 iterator
742 find(const key_type& __k);
743
744 const_iterator
745 find(const key_type& __k) const;
746
747 size_type
748 count(const key_type& __k) const;
749
750 std::pair<iterator, iterator>
751 equal_range(const key_type& __k);
752
753 std::pair<const_iterator, const_iterator>
754 equal_range(const key_type& __k) const;
755
756#if __cplusplus >= 202002L
757#define __cpp_lib_generic_unordered_lookup 201811L
758
759 template<typename _Kt,
760 typename = __has_is_transparent_t<_Hash, _Kt>,
761 typename = __has_is_transparent_t<_Equal, _Kt>>
762 iterator
763 _M_find_tr(const _Kt& __k);
764
765 template<typename _Kt,
766 typename = __has_is_transparent_t<_Hash, _Kt>,
767 typename = __has_is_transparent_t<_Equal, _Kt>>
768 const_iterator
769 _M_find_tr(const _Kt& __k) const;
770
771 template<typename _Kt,
772 typename = __has_is_transparent_t<_Hash, _Kt>,
773 typename = __has_is_transparent_t<_Equal, _Kt>>
774 size_type
775 _M_count_tr(const _Kt& __k) const;
776
777 template<typename _Kt,
778 typename = __has_is_transparent_t<_Hash, _Kt>,
779 typename = __has_is_transparent_t<_Equal, _Kt>>
780 pair<iterator, iterator>
781 _M_equal_range_tr(const _Kt& __k);
782
783 template<typename _Kt,
784 typename = __has_is_transparent_t<_Hash, _Kt>,
785 typename = __has_is_transparent_t<_Equal, _Kt>>
786 pair<const_iterator, const_iterator>
787 _M_equal_range_tr(const _Kt& __k) const;
788#endif // C++20
789
790 private:
791 // Bucket index computation helpers.
792 size_type
793 _M_bucket_index(const __node_value_type& __n) const noexcept
794 { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
795
796 size_type
797 _M_bucket_index(__hash_code __c) const
798 { return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
799
800 __node_base_ptr
801 _M_find_before_node(const key_type&);
802
803 // Find and insert helper functions and types
804 // Find the node before the one matching the criteria.
805 __node_base_ptr
806 _M_find_before_node(size_type, const key_type&, __hash_code) const;
807
808 template<typename _Kt>
809 __node_base_ptr
810 _M_find_before_node_tr(size_type, const _Kt&, __hash_code) const;
811
812 __node_ptr
813 _M_find_node(size_type __bkt, const key_type& __key,
814 __hash_code __c) const
815 {
816 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
817 if (__before_n)
818 return static_cast<__node_ptr>(__before_n->_M_nxt);
819 return nullptr;
820 }
821
822 template<typename _Kt>
823 __node_ptr
824 _M_find_node_tr(size_type __bkt, const _Kt& __key,
825 __hash_code __c) const
826 {
827 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
828 if (__before_n)
829 return static_cast<__node_ptr>(__before_n->_M_nxt);
830 return nullptr;
831 }
832
833 // Insert a node at the beginning of a bucket.
834 void
835 _M_insert_bucket_begin(size_type, __node_ptr);
836
837 // Remove the bucket first node
838 void
839 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
840 size_type __next_bkt);
841
842 // Get the node before __n in the bucket __bkt
843 __node_base_ptr
844 _M_get_previous_node(size_type __bkt, __node_ptr __n);
845
846 pair<const_iterator, __hash_code>
847 _M_compute_hash_code(const_iterator __hint, const key_type& __k) const;
848
849 // Insert node __n with hash code __code, in bucket __bkt if no
850 // rehash (assumes no element with same key already present).
851 // Takes ownership of __n if insertion succeeds, throws otherwise.
852 iterator
853 _M_insert_unique_node(size_type __bkt, __hash_code,
854 __node_ptr __n, size_type __n_elt = 1);
855
856 // Insert node __n with key __k and hash code __code.
857 // Takes ownership of __n if insertion succeeds, throws otherwise.
858 iterator
859 _M_insert_multi_node(__node_ptr __hint,
860 __hash_code __code, __node_ptr __n);
861
862 template<typename... _Args>
863 std::pair<iterator, bool>
864 _M_emplace(true_type __uks, _Args&&... __args);
865
866 template<typename... _Args>
867 iterator
868 _M_emplace(false_type __uks, _Args&&... __args)
869 { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
870
871 // Emplace with hint, useless when keys are unique.
872 template<typename... _Args>
873 iterator
874 _M_emplace(const_iterator, true_type __uks, _Args&&... __args)
875 { return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
876
877 template<typename... _Args>
878 iterator
879 _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
880
881 template<typename _Kt, typename _Arg, typename _NodeGenerator>
882 std::pair<iterator, bool>
883 _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&);
884
885 template<typename _Kt>
886 static __conditional_t<
887 __and_<__is_nothrow_invocable<_Hash&, const key_type&>,
888 __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
889 key_type, _Kt&&>
890 _S_forward_key(_Kt&& __k)
891 { return std::forward<_Kt>(__k); }
892
893 static const key_type&
894 _S_forward_key(const key_type& __k)
895 { return __k; }
896
897 static key_type&&
898 _S_forward_key(key_type&& __k)
899 { return std::move(__k); }
900
901 template<typename _Arg, typename _NodeGenerator>
902 std::pair<iterator, bool>
903 _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
904 true_type /* __uks */)
905 {
906 return _M_insert_unique(
907 _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
908 std::forward<_Arg>(__arg), __node_gen);
909 }
910
911 template<typename _Arg, typename _NodeGenerator>
912 iterator
913 _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
914 false_type __uks)
915 {
916 return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
917 __uks);
918 }
919
920 // Insert with hint, not used when keys are unique.
921 template<typename _Arg, typename _NodeGenerator>
922 iterator
923 _M_insert(const_iterator, _Arg&& __arg,
924 const _NodeGenerator& __node_gen, true_type __uks)
925 {
926 return
927 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
928 }
929
930 // Insert with hint when keys are not unique.
931 template<typename _Arg, typename _NodeGenerator>
932 iterator
933 _M_insert(const_iterator, _Arg&&,
934 const _NodeGenerator&, false_type __uks);
935
936 size_type
937 _M_erase(true_type __uks, const key_type&);
938
939 size_type
940 _M_erase(false_type __uks, const key_type&);
941
942 iterator
943 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
944
945 public:
946 // Emplace
947 template<typename... _Args>
948 __ireturn_type
949 emplace(_Args&&... __args)
950 { return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
951
952 template<typename... _Args>
953 iterator
954 emplace_hint(const_iterator __hint, _Args&&... __args)
955 {
956 return _M_emplace(__hint, __unique_keys{},
957 std::forward<_Args>(__args)...);
958 }
959
960 // Insert member functions via inheritance.
961
962 // Erase
963 iterator
964 erase(const_iterator);
965
966 // LWG 2059.
967 iterator
968 erase(iterator __it)
969 { return erase(const_iterator(__it)); }
970
971 size_type
972 erase(const key_type& __k)
973 { return _M_erase(__unique_keys{}, __k); }
974
975 iterator
976 erase(const_iterator, const_iterator);
977
978 void
979 clear() noexcept;
980
981 // Set number of buckets keeping it appropriate for container's number
982 // of elements.
983 void rehash(size_type __bkt_count);
984
985 // DR 1189.
986 // reserve, if present, comes from _Rehash_base.
987
988#if __cplusplus > 201402L
989 /// Re-insert an extracted node into a container with unique keys.
990 insert_return_type
991 _M_reinsert_node(node_type&& __nh)
992 {
993 insert_return_type __ret;
994 if (__nh.empty())
995 __ret.position = end();
996 else
997 {
998 __glibcxx_assert(get_allocator() == __nh.get_allocator());
999
1000 const key_type& __k = __nh._M_key();
1001 __hash_code __code = this->_M_hash_code(__k);
1002 size_type __bkt = _M_bucket_index(__code);
1003 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
1004 {
1005 __ret.node = std::move(__nh);
1006 __ret.position = iterator(__n);
1007 __ret.inserted = false;
1008 }
1009 else
1010 {
1011 __ret.position
1012 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
1013 __nh._M_ptr = nullptr;
1014 __ret.inserted = true;
1015 }
1016 }
1017 return __ret;
1018 }
1019
1020 /// Re-insert an extracted node into a container with equivalent keys.
1021 iterator
1022 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
1023 {
1024 if (__nh.empty())
1025 return end();
1026
1027 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1028
1029 const key_type& __k = __nh._M_key();
1030 auto __code = this->_M_hash_code(__k);
1031 auto __ret
1032 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
1033 __nh._M_ptr = nullptr;
1034 return __ret;
1035 }
1036
1037 private:
1038 node_type
1039 _M_extract_node(size_t __bkt, __node_base_ptr __prev_n)
1040 {
1041 __node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
1042 if (__prev_n == _M_buckets[__bkt])
1043 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1044 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1045 else if (__n->_M_nxt)
1046 {
1047 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1048 if (__next_bkt != __bkt)
1049 _M_buckets[__next_bkt] = __prev_n;
1050 }
1051
1052 __prev_n->_M_nxt = __n->_M_nxt;
1053 __n->_M_nxt = nullptr;
1054 --_M_element_count;
1055 return { __n, this->_M_node_allocator() };
1056 }
1057
1058 public:
1059 // Extract a node.
1060 node_type
1061 extract(const_iterator __pos)
1062 {
1063 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1064 return _M_extract_node(__bkt,
1065 _M_get_previous_node(__bkt, __pos._M_cur));
1066 }
1067
1068 /// Extract a node.
1069 node_type
1070 extract(const _Key& __k)
1071 {
1072 node_type __nh;
1073 __hash_code __code = this->_M_hash_code(__k);
1074 std::size_t __bkt = _M_bucket_index(__code);
1075 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1076 __nh = _M_extract_node(__bkt, __prev_node);
1077 return __nh;
1078 }
1079
1080 /// Merge from a compatible container into one with unique keys.
1081 template<typename _Compatible_Hashtable>
1082 void
1083 _M_merge_unique(_Compatible_Hashtable& __src)
1084 {
1085 static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
1086 node_type>, "Node types are compatible");
1087 __glibcxx_assert(get_allocator() == __src.get_allocator());
1088
1089 auto __n_elt = __src.size();
1090 for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1091 {
1092 auto __pos = __i++;
1093 const key_type& __k = _ExtractKey{}(*__pos);
1094 __hash_code __code
1095 = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
1096 size_type __bkt = _M_bucket_index(__code);
1097 if (_M_find_node(__bkt, __k, __code) == nullptr)
1098 {
1099 auto __nh = __src.extract(__pos);
1100 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1101 __nh._M_ptr = nullptr;
1102 __n_elt = 1;
1103 }
1104 else if (__n_elt != 1)
1105 --__n_elt;
1106 }
1107 }
1108
1109 /// Merge from a compatible container into one with equivalent keys.
1110 template<typename _Compatible_Hashtable>
1111 void
1112 _M_merge_multi(_Compatible_Hashtable& __src)
1113 {
1114 static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
1115 node_type>, "Node types are compatible");
1116 __glibcxx_assert(get_allocator() == __src.get_allocator());
1117
1118 __node_ptr __hint = nullptr;
1119 this->reserve(size() + __src.size());
1120 for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1121 {
1122 auto __pos = __i++;
1123 __hash_code __code
1124 = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
1125 auto __nh = __src.extract(__pos);
1126 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1127 __nh._M_ptr = nullptr;
1128 }
1129 }
1130#endif // C++17
1131
1132 private:
1133 // Helper rehash method used when keys are unique.
1134 void _M_rehash_aux(size_type __bkt_count, true_type __uks);
1135
1136 // Helper rehash method used when keys can be non-unique.
1137 void _M_rehash_aux(size_type __bkt_count, false_type __uks);
1138
1139 // Unconditionally change size of bucket array to n, restore
1140 // hash policy state to __state on exception.
1141 void _M_rehash(size_type __bkt_count, const __rehash_state& __state);
1142 };
1143
1144 // Definitions of class template _Hashtable's out-of-line member functions.
1145 template<typename _Key, typename _Value, typename _Alloc,
1146 typename _ExtractKey, typename _Equal,
1147 typename _Hash, typename _RangeHash, typename _Unused,
1148 typename _RehashPolicy, typename _Traits>
1149 auto
1150 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1151 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1152 _M_bucket_begin(size_type __bkt) const
1153 -> __node_ptr
1154 {
1155 __node_base_ptr __n = _M_buckets[__bkt];
1156 return __n ? static_cast<__node_ptr>(__n->_M_nxt) : nullptr;
1157 }
1158
1159 template<typename _Key, typename _Value, typename _Alloc,
1160 typename _ExtractKey, typename _Equal,
1161 typename _Hash, typename _RangeHash, typename _Unused,
1162 typename _RehashPolicy, typename _Traits>
1163 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1164 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1165 _Hashtable(size_type __bkt_count_hint,
1166 const _Hash& __h, const _Equal& __eq, const allocator_type& __a)
1167 : _Hashtable(__h, __eq, __a)
1168 {
1169 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1170 if (__bkt_count > _M_bucket_count)
1171 {
1172 _M_buckets = _M_allocate_buckets(__bkt_count);
1173 _M_bucket_count = __bkt_count;
1174 }
1175 }
1176
1177 template<typename _Key, typename _Value, typename _Alloc,
1178 typename _ExtractKey, typename _Equal,
1179 typename _Hash, typename _RangeHash, typename _Unused,
1180 typename _RehashPolicy, typename _Traits>
1181 template<typename _InputIterator>
1182 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1183 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1184 _Hashtable(_InputIterator __f, _InputIterator __l,
1185 size_type __bkt_count_hint,
1186 const _Hash& __h, const _Equal& __eq,
1187 const allocator_type& __a, true_type /* __uks */)
1188 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1189 {
1190 for (; __f != __l; ++__f)
1191 this->insert(*__f);
1192 }
1193
1194 template<typename _Key, typename _Value, typename _Alloc,
1195 typename _ExtractKey, typename _Equal,
1196 typename _Hash, typename _RangeHash, typename _Unused,
1197 typename _RehashPolicy, typename _Traits>
1198 template<typename _InputIterator>
1199 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1200 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1201 _Hashtable(_InputIterator __f, _InputIterator __l,
1202 size_type __bkt_count_hint,
1203 const _Hash& __h, const _Equal& __eq,
1204 const allocator_type& __a, false_type /* __uks */)
1205 : _Hashtable(__h, __eq, __a)
1206 {
1207 auto __nb_elems = __detail::__distance_fw(__f, __l);
1208 auto __bkt_count =
1209 _M_rehash_policy._M_next_bkt(
1210 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1211 __bkt_count_hint));
1212
1213 if (__bkt_count > _M_bucket_count)
1214 {
1215 _M_buckets = _M_allocate_buckets(__bkt_count);
1216 _M_bucket_count = __bkt_count;
1217 }
1218
1219 for (; __f != __l; ++__f)
1220 this->insert(*__f);
1221 }
1222
1223 template<typename _Key, typename _Value, typename _Alloc,
1224 typename _ExtractKey, typename _Equal,
1225 typename _Hash, typename _RangeHash, typename _Unused,
1226 typename _RehashPolicy, typename _Traits>
1227 auto
1228 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1229 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1230 operator=(const _Hashtable& __ht)
1231 -> _Hashtable&
1232 {
1233 if (&__ht == this)
1234 return *this;
1235
1236 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1237 {
1238 auto& __this_alloc = this->_M_node_allocator();
1239 auto& __that_alloc = __ht._M_node_allocator();
1240 if (!__node_alloc_traits::_S_always_equal()
1241 && __this_alloc != __that_alloc)
1242 {
1243 // Replacement allocator cannot free existing storage.
1244 this->_M_deallocate_nodes(_M_begin());
1245 _M_before_begin._M_nxt = nullptr;
1246 _M_deallocate_buckets();
1247 _M_buckets = nullptr;
1248 std::__alloc_on_copy(__this_alloc, __that_alloc);
1249 __hashtable_base::operator=(__ht);
1250 _M_bucket_count = __ht._M_bucket_count;
1251 _M_element_count = __ht._M_element_count;
1252 _M_rehash_policy = __ht._M_rehash_policy;
1253 __alloc_node_gen_t __alloc_node_gen(*this);
1254 __try
1255 {
1256 _M_assign(__ht, __alloc_node_gen);
1257 }
1258 __catch(...)
1259 {
1260 // _M_assign took care of deallocating all memory. Now we
1261 // must make sure this instance remains in a usable state.
1262 _M_reset();
1263 __throw_exception_again;
1264 }
1265 return *this;
1266 }
1267 std::__alloc_on_copy(__this_alloc, __that_alloc);
1268 }
1269
1270 // Reuse allocated buckets and nodes.
1271 _M_assign_elements(__ht);
1272 return *this;
1273 }
1274
1275 template<typename _Key, typename _Value, typename _Alloc,
1276 typename _ExtractKey, typename _Equal,
1277 typename _Hash, typename _RangeHash, typename _Unused,
1278 typename _RehashPolicy, typename _Traits>
1279 template<typename _Ht>
1280 void
1281 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1282 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1283 _M_assign_elements(_Ht&& __ht)
1284 {
1285 __buckets_ptr __former_buckets = nullptr;
1286 std::size_t __former_bucket_count = _M_bucket_count;
1287 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1288
1289 if (_M_bucket_count != __ht._M_bucket_count)
1290 {
1291 __former_buckets = _M_buckets;
1292 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1293 _M_bucket_count = __ht._M_bucket_count;
1294 }
1295 else
1296 __builtin_memset(_M_buckets, 0,
1297 _M_bucket_count * sizeof(__node_base_ptr));
1298
1299 __try
1300 {
1301 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1302 _M_element_count = __ht._M_element_count;
1303 _M_rehash_policy = __ht._M_rehash_policy;
1304 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
1305 _M_before_begin._M_nxt = nullptr;
1306 _M_assign(std::forward<_Ht>(__ht), __roan);
1307 if (__former_buckets)
1308 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1309 }
1310 __catch(...)
1311 {
1312 if (__former_buckets)
1313 {
1314 // Restore previous buckets.
1315 _M_deallocate_buckets();
1316 _M_rehash_policy._M_reset(__former_state);
1317 _M_buckets = __former_buckets;
1318 _M_bucket_count = __former_bucket_count;
1319 }
1320 __builtin_memset(_M_buckets, 0,
1321 _M_bucket_count * sizeof(__node_base_ptr));
1322 __throw_exception_again;
1323 }
1324 }
1325
1326 template<typename _Key, typename _Value, typename _Alloc,
1327 typename _ExtractKey, typename _Equal,
1328 typename _Hash, typename _RangeHash, typename _Unused,
1329 typename _RehashPolicy, typename _Traits>
1330 template<typename _Ht, typename _NodeGenerator>
1331 void
1332 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1333 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1334 _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen)
1335 {
1336 __buckets_ptr __buckets = nullptr;
1337 if (!_M_buckets)
1338 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1339
1340 __try
1341 {
1342 if (!__ht._M_before_begin._M_nxt)
1343 return;
1344
1345 // First deal with the special first node pointed to by
1346 // _M_before_begin.
1347 __node_ptr __ht_n = __ht._M_begin();
1348 __node_ptr __this_n
1349 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1350 this->_M_copy_code(*__this_n, *__ht_n);
1351 _M_update_bbegin(__this_n);
1352
1353 // Then deal with other nodes.
1354 __node_ptr __prev_n = __this_n;
1355 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1356 {
1357 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1358 __prev_n->_M_nxt = __this_n;
1359 this->_M_copy_code(*__this_n, *__ht_n);
1360 size_type __bkt = _M_bucket_index(*__this_n);
1361 if (!_M_buckets[__bkt])
1362 _M_buckets[__bkt] = __prev_n;
1363 __prev_n = __this_n;
1364 }
1365 }
1366 __catch(...)
1367 {
1368 clear();
1369 if (__buckets)
1370 _M_deallocate_buckets();
1371 __throw_exception_again;
1372 }
1373 }
1374
1375 template<typename _Key, typename _Value, typename _Alloc,
1376 typename _ExtractKey, typename _Equal,
1377 typename _Hash, typename _RangeHash, typename _Unused,
1378 typename _RehashPolicy, typename _Traits>
1379 void
1380 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1381 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1382 _M_reset() noexcept
1383 {
1384 _M_rehash_policy._M_reset();
1385 _M_bucket_count = 1;
1386 _M_single_bucket = nullptr;
1387 _M_buckets = &_M_single_bucket;
1388 _M_before_begin._M_nxt = nullptr;
1389 _M_element_count = 0;
1390 }
1391
1392 template<typename _Key, typename _Value, typename _Alloc,
1393 typename _ExtractKey, typename _Equal,
1394 typename _Hash, typename _RangeHash, typename _Unused,
1395 typename _RehashPolicy, typename _Traits>
1396 void
1397 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1398 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1399 _M_move_assign(_Hashtable&& __ht, true_type)
1400 {
1401 if (__builtin_expect(std::__addressof(__ht) == this, false))
1402 return;
1403
1404 this->_M_deallocate_nodes(_M_begin());
1405 _M_deallocate_buckets();
1406 __hashtable_base::operator=(std::move(__ht));
1407 _M_rehash_policy = __ht._M_rehash_policy;
1408 if (!__ht._M_uses_single_bucket())
1409 _M_buckets = __ht._M_buckets;
1410 else
1411 {
1412 _M_buckets = &_M_single_bucket;
1413 _M_single_bucket = __ht._M_single_bucket;
1414 }
1415
1416 _M_bucket_count = __ht._M_bucket_count;
1417 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1418 _M_element_count = __ht._M_element_count;
1419 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1420
1421 // Fix bucket containing the _M_before_begin pointer that can't be moved.
1422 _M_update_bbegin();
1423 __ht._M_reset();
1424 }
1425
1426 template<typename _Key, typename _Value, typename _Alloc,
1427 typename _ExtractKey, typename _Equal,
1428 typename _Hash, typename _RangeHash, typename _Unused,
1429 typename _RehashPolicy, typename _Traits>
1430 void
1431 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1432 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1433 _M_move_assign(_Hashtable&& __ht, false_type)
1434 {
1435 if (__ht._M_node_allocator() == this->_M_node_allocator())
1436 _M_move_assign(std::move(__ht), true_type{});
1437 else
1438 {
1439 // Can't move memory, move elements then.
1440 _M_assign_elements(std::move(__ht));
1441 __ht.clear();
1442 }
1443 }
1444
1445 template<typename _Key, typename _Value, typename _Alloc,
1446 typename _ExtractKey, typename _Equal,
1447 typename _Hash, typename _RangeHash, typename _Unused,
1448 typename _RehashPolicy, typename _Traits>
1449 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1450 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1451 _Hashtable(const _Hashtable& __ht)
1452 : __hashtable_base(__ht),
1453 __map_base(__ht),
1454 __rehash_base(__ht),
1455 __hashtable_alloc(
1456 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1457 __enable_default_ctor(__ht),
1458 _M_buckets(nullptr),
1459 _M_bucket_count(__ht._M_bucket_count),
1460 _M_element_count(__ht._M_element_count),
1461 _M_rehash_policy(__ht._M_rehash_policy)
1462 {
1463 __alloc_node_gen_t __alloc_node_gen(*this);
1464 _M_assign(__ht, __alloc_node_gen);
1465 }
1466
1467 template<typename _Key, typename _Value, typename _Alloc,
1468 typename _ExtractKey, typename _Equal,
1469 typename _Hash, typename _RangeHash, typename _Unused,
1470 typename _RehashPolicy, typename _Traits>
1471 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1472 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1473 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1474 true_type /* alloc always equal */)
1475 noexcept(_S_nothrow_move())
1476 : __hashtable_base(__ht),
1477 __map_base(__ht),
1478 __rehash_base(__ht),
1479 __hashtable_alloc(std::move(__a)),
1480 __enable_default_ctor(__ht),
1481 _M_buckets(__ht._M_buckets),
1482 _M_bucket_count(__ht._M_bucket_count),
1483 _M_before_begin(__ht._M_before_begin._M_nxt),
1484 _M_element_count(__ht._M_element_count),
1485 _M_rehash_policy(__ht._M_rehash_policy)
1486 {
1487 // Update buckets if __ht is using its single bucket.
1488 if (__ht._M_uses_single_bucket())
1489 {
1490 _M_buckets = &_M_single_bucket;
1491 _M_single_bucket = __ht._M_single_bucket;
1492 }
1493
1494 // Fix bucket containing the _M_before_begin pointer that can't be moved.
1495 _M_update_bbegin();
1496
1497 __ht._M_reset();
1498 }
1499
1500 template<typename _Key, typename _Value, typename _Alloc,
1501 typename _ExtractKey, typename _Equal,
1502 typename _Hash, typename _RangeHash, typename _Unused,
1503 typename _RehashPolicy, typename _Traits>
1504 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1505 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1506 _Hashtable(const _Hashtable& __ht, const allocator_type& __a)
1507 : __hashtable_base(__ht),
1508 __map_base(__ht),
1509 __rehash_base(__ht),
1510 __hashtable_alloc(__node_alloc_type(__a)),
1511 __enable_default_ctor(__ht),
1512 _M_buckets(),
1513 _M_bucket_count(__ht._M_bucket_count),
1514 _M_element_count(__ht._M_element_count),
1515 _M_rehash_policy(__ht._M_rehash_policy)
1516 {
1517 __alloc_node_gen_t __alloc_node_gen(*this);
1518 _M_assign(__ht, __alloc_node_gen);
1519 }
1520
1521 template<typename _Key, typename _Value, typename _Alloc,
1522 typename _ExtractKey, typename _Equal,
1523 typename _Hash, typename _RangeHash, typename _Unused,
1524 typename _RehashPolicy, typename _Traits>
1525 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1526 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1527 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1528 false_type /* alloc always equal */)
1529 : __hashtable_base(__ht),
1530 __map_base(__ht),
1531 __rehash_base(__ht),
1532 __hashtable_alloc(std::move(__a)),
1533 __enable_default_ctor(__ht),
1534 _M_buckets(nullptr),
1535 _M_bucket_count(__ht._M_bucket_count),
1536 _M_element_count(__ht._M_element_count),
1537 _M_rehash_policy(__ht._M_rehash_policy)
1538 {
1539 if (__ht._M_node_allocator() == this->_M_node_allocator())
1540 {
1541 if (__ht._M_uses_single_bucket())
1542 {
1543 _M_buckets = &_M_single_bucket;
1544 _M_single_bucket = __ht._M_single_bucket;
1545 }
1546 else
1547 _M_buckets = __ht._M_buckets;
1548
1549 // Fix bucket containing the _M_before_begin pointer that can't be
1550 // moved.
1551 _M_update_bbegin(__ht._M_begin());
1552
1553 __ht._M_reset();
1554 }
1555 else
1556 {
1557 __alloc_node_gen_t __alloc_gen(*this);
1558
1559 using _Fwd_Ht = __conditional_t<
1560 __move_if_noexcept_cond<value_type>::value,
1561 const _Hashtable&, _Hashtable&&>;
1562 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1563 __ht.clear();
1564 }
1565 }
1566
1567 template<typename _Key, typename _Value, typename _Alloc,
1568 typename _ExtractKey, typename _Equal,
1569 typename _Hash, typename _RangeHash, typename _Unused,
1570 typename _RehashPolicy, typename _Traits>
1571 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1572 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1573 ~_Hashtable() noexcept
1574 {
1575 // Getting a bucket index from a node shall not throw because it is used
1576 // in methods (erase, swap...) that shall not throw. Need a complete
1577 // type to check this, so do it in the destructor not at class scope.
1578 static_assert(noexcept(declval<const __hash_code_base_access&>()
1579 ._M_bucket_index(declval<const __node_value_type&>(),
1580 (std::size_t)0)),
1581 "Cache the hash code or qualify your functors involved"
1582 " in hash code and bucket index computation with noexcept");
1583
1584 clear();
1585 _M_deallocate_buckets();
1586 }
1587
1588 template<typename _Key, typename _Value, typename _Alloc,
1589 typename _ExtractKey, typename _Equal,
1590 typename _Hash, typename _RangeHash, typename _Unused,
1591 typename _RehashPolicy, typename _Traits>
1592 void
1593 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1594 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1595 swap(_Hashtable& __x)
1596 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1597 __is_nothrow_swappable<_Equal>>::value)
1598 {
1599 // The only base class with member variables is hash_code_base.
1600 // We define _Hash_code_base::_M_swap because different
1601 // specializations have different members.
1602 this->_M_swap(__x);
1603
1604 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1605 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1606
1607 // Deal properly with potentially moved instances.
1608 if (this->_M_uses_single_bucket())
1609 {
1610 if (!__x._M_uses_single_bucket())
1611 {
1612 _M_buckets = __x._M_buckets;
1613 __x._M_buckets = &__x._M_single_bucket;
1614 }
1615 }
1616 else if (__x._M_uses_single_bucket())
1617 {
1618 __x._M_buckets = _M_buckets;
1619 _M_buckets = &_M_single_bucket;
1620 }
1621 else
1622 std::swap(_M_buckets, __x._M_buckets);
1623
1624 std::swap(_M_bucket_count, __x._M_bucket_count);
1625 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1626 std::swap(_M_element_count, __x._M_element_count);
1627 std::swap(_M_single_bucket, __x._M_single_bucket);
1628
1629 // Fix buckets containing the _M_before_begin pointers that can't be
1630 // swapped.
1631 _M_update_bbegin();
1632 __x._M_update_bbegin();
1633 }
1634
1635 template<typename _Key, typename _Value, typename _Alloc,
1636 typename _ExtractKey, typename _Equal,
1637 typename _Hash, typename _RangeHash, typename _Unused,
1638 typename _RehashPolicy, typename _Traits>
1639 auto
1640 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1641 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1642 find(const key_type& __k)
1643 -> iterator
1644 {
1645 if (size() <= __small_size_threshold())
1646 {
1647 for (auto __it = begin(); __it != end(); ++__it)
1648 if (this->_M_key_equals(__k, *__it._M_cur))
1649 return __it;
1650 return end();
1651 }
1652
1653 __hash_code __code = this->_M_hash_code(__k);
1654 std::size_t __bkt = _M_bucket_index(__code);
1655 return iterator(_M_find_node(__bkt, __k, __code));
1656 }
1657
1658 template<typename _Key, typename _Value, typename _Alloc,
1659 typename _ExtractKey, typename _Equal,
1660 typename _Hash, typename _RangeHash, typename _Unused,
1661 typename _RehashPolicy, typename _Traits>
1662 auto
1663 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1664 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1665 find(const key_type& __k) const
1666 -> const_iterator
1667 {
1668 if (size() <= __small_size_threshold())
1669 {
1670 for (auto __it = begin(); __it != end(); ++__it)
1671 if (this->_M_key_equals(__k, *__it._M_cur))
1672 return __it;
1673 return end();
1674 }
1675
1676 __hash_code __code = this->_M_hash_code(__k);
1677 std::size_t __bkt = _M_bucket_index(__code);
1678 return const_iterator(_M_find_node(__bkt, __k, __code));
1679 }
1680
1681#if __cplusplus > 201703L
1682 template<typename _Key, typename _Value, typename _Alloc,
1683 typename _ExtractKey, typename _Equal,
1684 typename _Hash, typename _RangeHash, typename _Unused,
1685 typename _RehashPolicy, typename _Traits>
1686 template<typename _Kt, typename, typename>
1687 auto
1688 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1689 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1690 _M_find_tr(const _Kt& __k)
1691 -> iterator
1692 {
1693 __hash_code __code = this->_M_hash_code_tr(__k);
1694 std::size_t __bkt = _M_bucket_index(__code);
1695 return iterator(_M_find_node_tr(__bkt, __k, __code));
1696 }
1697
1698 template<typename _Key, typename _Value, typename _Alloc,
1699 typename _ExtractKey, typename _Equal,
1700 typename _Hash, typename _RangeHash, typename _Unused,
1701 typename _RehashPolicy, typename _Traits>
1702 template<typename _Kt, typename, typename>
1703 auto
1704 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1705 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1706 _M_find_tr(const _Kt& __k) const
1707 -> const_iterator
1708 {
1709 __hash_code __code = this->_M_hash_code_tr(__k);
1710 std::size_t __bkt = _M_bucket_index(__code);
1711 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1712 }
1713#endif
1714
1715 template<typename _Key, typename _Value, typename _Alloc,
1716 typename _ExtractKey, typename _Equal,
1717 typename _Hash, typename _RangeHash, typename _Unused,
1718 typename _RehashPolicy, typename _Traits>
1719 auto
1720 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1721 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1722 count(const key_type& __k) const
1723 -> size_type
1724 {
1725 auto __it = find(__k);
1726 if (!__it._M_cur)
1727 return 0;
1728
1729 if (__unique_keys::value)
1730 return 1;
1731
1732 // All equivalent values are next to each other, if we find a
1733 // non-equivalent value after an equivalent one it means that we won't
1734 // find any new equivalent value.
1735 size_type __result = 1;
1736 for (auto __ref = __it++;
1737 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1738 ++__it)
1739 ++__result;
1740
1741 return __result;
1742 }
1743
1744#if __cplusplus > 201703L
1745 template<typename _Key, typename _Value, typename _Alloc,
1746 typename _ExtractKey, typename _Equal,
1747 typename _Hash, typename _RangeHash, typename _Unused,
1748 typename _RehashPolicy, typename _Traits>
1749 template<typename _Kt, typename, typename>
1750 auto
1751 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1752 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1753 _M_count_tr(const _Kt& __k) const
1754 -> size_type
1755 {
1756 __hash_code __code = this->_M_hash_code_tr(__k);
1757 std::size_t __bkt = _M_bucket_index(__code);
1758 auto __n = _M_find_node_tr(__bkt, __k, __code);
1759 if (!__n)
1760 return 0;
1761
1762 // All equivalent values are next to each other, if we find a
1763 // non-equivalent value after an equivalent one it means that we won't
1764 // find any new equivalent value.
1765 iterator __it(__n);
1766 size_type __result = 1;
1767 for (++__it;
1768 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1769 ++__it)
1770 ++__result;
1771
1772 return __result;
1773 }
1774#endif
1775
1776 template<typename _Key, typename _Value, typename _Alloc,
1777 typename _ExtractKey, typename _Equal,
1778 typename _Hash, typename _RangeHash, typename _Unused,
1779 typename _RehashPolicy, typename _Traits>
1780 auto
1781 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1782 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1783 equal_range(const key_type& __k)
1784 -> pair<iterator, iterator>
1785 {
1786 auto __ite = find(__k);
1787 if (!__ite._M_cur)
1788 return { __ite, __ite };
1789
1790 auto __beg = __ite++;
1791 if (__unique_keys::value)
1792 return { __beg, __ite };
1793
1794 // All equivalent values are next to each other, if we find a
1795 // non-equivalent value after an equivalent one it means that we won't
1796 // find any new equivalent value.
1797 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1798 ++__ite;
1799
1800 return { __beg, __ite };
1801 }
1802
1803 template<typename _Key, typename _Value, typename _Alloc,
1804 typename _ExtractKey, typename _Equal,
1805 typename _Hash, typename _RangeHash, typename _Unused,
1806 typename _RehashPolicy, typename _Traits>
1807 auto
1808 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1809 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1810 equal_range(const key_type& __k) const
1811 -> pair<const_iterator, const_iterator>
1812 {
1813 auto __ite = find(__k);
1814 if (!__ite._M_cur)
1815 return { __ite, __ite };
1816
1817 auto __beg = __ite++;
1818 if (__unique_keys::value)
1819 return { __beg, __ite };
1820
1821 // All equivalent values are next to each other, if we find a
1822 // non-equivalent value after an equivalent one it means that we won't
1823 // find any new equivalent value.
1824 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1825 ++__ite;
1826
1827 return { __beg, __ite };
1828 }
1829
1830#if __cplusplus > 201703L
1831 template<typename _Key, typename _Value, typename _Alloc,
1832 typename _ExtractKey, typename _Equal,
1833 typename _Hash, typename _RangeHash, typename _Unused,
1834 typename _RehashPolicy, typename _Traits>
1835 template<typename _Kt, typename, typename>
1836 auto
1837 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1838 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1839 _M_equal_range_tr(const _Kt& __k)
1840 -> pair<iterator, iterator>
1841 {
1842 __hash_code __code = this->_M_hash_code_tr(__k);
1843 std::size_t __bkt = _M_bucket_index(__code);
1844 auto __n = _M_find_node_tr(__bkt, __k, __code);
1845 iterator __ite(__n);
1846 if (!__n)
1847 return { __ite, __ite };
1848
1849 // All equivalent values are next to each other, if we find a
1850 // non-equivalent value after an equivalent one it means that we won't
1851 // find any new equivalent value.
1852 auto __beg = __ite++;
1853 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1854 ++__ite;
1855
1856 return { __beg, __ite };
1857 }
1858
1859 template<typename _Key, typename _Value, typename _Alloc,
1860 typename _ExtractKey, typename _Equal,
1861 typename _Hash, typename _RangeHash, typename _Unused,
1862 typename _RehashPolicy, typename _Traits>
1863 template<typename _Kt, typename, typename>
1864 auto
1865 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1866 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1867 _M_equal_range_tr(const _Kt& __k) const
1868 -> pair<const_iterator, const_iterator>
1869 {
1870 __hash_code __code = this->_M_hash_code_tr(__k);
1871 std::size_t __bkt = _M_bucket_index(__code);
1872 auto __n = _M_find_node_tr(__bkt, __k, __code);
1873 const_iterator __ite(__n);
1874 if (!__n)
1875 return { __ite, __ite };
1876
1877 // All equivalent values are next to each other, if we find a
1878 // non-equivalent value after an equivalent one it means that we won't
1879 // find any new equivalent value.
1880 auto __beg = __ite++;
1881 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1882 ++__ite;
1883
1884 return { __beg, __ite };
1885 }
1886#endif
1887
1888 // Find the node before the one whose key compares equal to k.
1889 // Return nullptr if no node is found.
1890 template<typename _Key, typename _Value, typename _Alloc,
1891 typename _ExtractKey, typename _Equal,
1892 typename _Hash, typename _RangeHash, typename _Unused,
1893 typename _RehashPolicy, typename _Traits>
1894 auto
1895 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1896 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1897 _M_find_before_node(const key_type& __k)
1898 -> __node_base_ptr
1899 {
1900 __node_base_ptr __prev_p = &_M_before_begin;
1901 if (!__prev_p->_M_nxt)
1902 return nullptr;
1903
1904 for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);
1905 __p != nullptr;
1906 __p = __p->_M_next())
1907 {
1908 if (this->_M_key_equals(__k, *__p))
1909 return __prev_p;
1910
1911 __prev_p = __p;
1912 }
1913
1914 return nullptr;
1915 }
1916
1917 // Find the node before the one whose key compares equal to k in the bucket
1918 // bkt. Return nullptr if no node is found.
1919 template<typename _Key, typename _Value, typename _Alloc,
1920 typename _ExtractKey, typename _Equal,
1921 typename _Hash, typename _RangeHash, typename _Unused,
1922 typename _RehashPolicy, typename _Traits>
1923 auto
1924 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1925 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1926 _M_find_before_node(size_type __bkt, const key_type& __k,
1927 __hash_code __code) const
1928 -> __node_base_ptr
1929 {
1930 __node_base_ptr __prev_p = _M_buckets[__bkt];
1931 if (!__prev_p)
1932 return nullptr;
1933
1934 for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
1935 __p = __p->_M_next())
1936 {
1937 if (this->_M_equals(__k, __code, *__p))
1938 return __prev_p;
1939
1940 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1941 break;
1942 __prev_p = __p;
1943 }
1944
1945 return nullptr;
1946 }
1947
1948 template<typename _Key, typename _Value, typename _Alloc,
1949 typename _ExtractKey, typename _Equal,
1950 typename _Hash, typename _RangeHash, typename _Unused,
1951 typename _RehashPolicy, typename _Traits>
1952 template<typename _Kt>
1953 auto
1954 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1955 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1956 _M_find_before_node_tr(size_type __bkt, const _Kt& __k,
1957 __hash_code __code) const
1958 -> __node_base_ptr
1959 {
1960 __node_base_ptr __prev_p = _M_buckets[__bkt];
1961 if (!__prev_p)
1962 return nullptr;
1963
1964 for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
1965 __p = __p->_M_next())
1966 {
1967 if (this->_M_equals_tr(__k, __code, *__p))
1968 return __prev_p;
1969
1970 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1971 break;
1972 __prev_p = __p;
1973 }
1974
1975 return nullptr;
1976 }
1977
1978 template<typename _Key, typename _Value, typename _Alloc,
1979 typename _ExtractKey, typename _Equal,
1980 typename _Hash, typename _RangeHash, typename _Unused,
1981 typename _RehashPolicy, typename _Traits>
1982 void
1983 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1984 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1985 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
1986 {
1987 if (_M_buckets[__bkt])
1988 {
1989 // Bucket is not empty, we just need to insert the new node
1990 // after the bucket before begin.
1991 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1992 _M_buckets[__bkt]->_M_nxt = __node;
1993 }
1994 else
1995 {
1996 // The bucket is empty, the new node is inserted at the
1997 // beginning of the singly-linked list and the bucket will
1998 // contain _M_before_begin pointer.
1999 __node->_M_nxt = _M_before_begin._M_nxt;
2000 _M_before_begin._M_nxt = __node;
2001
2002 if (__node->_M_nxt)
2003 // We must update former begin bucket that is pointing to
2004 // _M_before_begin.
2005 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
2006
2007 _M_buckets[__bkt] = &_M_before_begin;
2008 }
2009 }
2010
2011 template<typename _Key, typename _Value, typename _Alloc,
2012 typename _ExtractKey, typename _Equal,
2013 typename _Hash, typename _RangeHash, typename _Unused,
2014 typename _RehashPolicy, typename _Traits>
2015 void
2016 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2017 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2018 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
2019 size_type __next_bkt)
2020 {
2021 if (!__next || __next_bkt != __bkt)
2022 {
2023 // Bucket is now empty
2024 // First update next bucket if any
2025 if (__next)
2026 _M_buckets[__next_bkt] = _M_buckets[__bkt];
2027
2028 // Second update before begin node if necessary
2029 if (&_M_before_begin == _M_buckets[__bkt])
2030 _M_before_begin._M_nxt = __next;
2031 _M_buckets[__bkt] = nullptr;
2032 }
2033 }
2034
2035 template<typename _Key, typename _Value, typename _Alloc,
2036 typename _ExtractKey, typename _Equal,
2037 typename _Hash, typename _RangeHash, typename _Unused,
2038 typename _RehashPolicy, typename _Traits>
2039 auto
2040 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2041 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2042 _M_get_previous_node(size_type __bkt, __node_ptr __n)
2043 -> __node_base_ptr
2044 {
2045 __node_base_ptr __prev_n = _M_buckets[__bkt];
2046 while (__prev_n->_M_nxt != __n)
2047 __prev_n = __prev_n->_M_nxt;
2048 return __prev_n;
2049 }
2050
2051 template<typename _Key, typename _Value, typename _Alloc,
2052 typename _ExtractKey, typename _Equal,
2053 typename _Hash, typename _RangeHash, typename _Unused,
2054 typename _RehashPolicy, typename _Traits>
2055 template<typename... _Args>
2056 auto
2057 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2058 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2059 _M_emplace(true_type /* __uks */, _Args&&... __args)
2060 -> pair<iterator, bool>
2061 {
2062 // First build the node to get access to the hash code
2063 _Scoped_node __node { this, std::forward<_Args>(__args)... };
2064 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2065 if (size() <= __small_size_threshold())
2066 {
2067 for (auto __it = begin(); __it != end(); ++__it)
2068 if (this->_M_key_equals(__k, *__it._M_cur))
2069 // There is already an equivalent node, no insertion
2070 return { __it, false };
2071 }
2072
2073 __hash_code __code = this->_M_hash_code(__k);
2074 size_type __bkt = _M_bucket_index(__code);
2075 if (size() > __small_size_threshold())
2076 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
2077 // There is already an equivalent node, no insertion
2078 return { iterator(__p), false };
2079
2080 // Insert the node
2081 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
2082 __node._M_node = nullptr;
2083 return { __pos, true };
2084 }
2085
2086 template<typename _Key, typename _Value, typename _Alloc,
2087 typename _ExtractKey, typename _Equal,
2088 typename _Hash, typename _RangeHash, typename _Unused,
2089 typename _RehashPolicy, typename _Traits>
2090 template<typename... _Args>
2091 auto
2092 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2093 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2094 _M_emplace(const_iterator __hint, false_type /* __uks */,
2095 _Args&&... __args)
2096 -> iterator
2097 {
2098 // First build the node to get its hash code.
2099 _Scoped_node __node { this, std::forward<_Args>(__args)... };
2100 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2101
2102 auto __res = this->_M_compute_hash_code(__hint, __k);
2103 auto __pos
2104 = _M_insert_multi_node(__res.first._M_cur, __res.second,
2105 __node._M_node);
2106 __node._M_node = nullptr;
2107 return __pos;
2108 }
2109
2110 template<typename _Key, typename _Value, typename _Alloc,
2111 typename _ExtractKey, typename _Equal,
2112 typename _Hash, typename _RangeHash, typename _Unused,
2113 typename _RehashPolicy, typename _Traits>
2114 auto
2115 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2116 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2117 _M_compute_hash_code(const_iterator __hint, const key_type& __k) const
2118 -> pair<const_iterator, __hash_code>
2119 {
2120 if (size() <= __small_size_threshold())
2121 {
2122 if (__hint != cend())
2123 {
2124 for (auto __it = __hint; __it != cend(); ++__it)
2125 if (this->_M_key_equals(__k, *__it._M_cur))
2126 return { __it, this->_M_hash_code(*__it._M_cur) };
2127 }
2128
2129 for (auto __it = cbegin(); __it != __hint; ++__it)
2130 if (this->_M_key_equals(__k, *__it._M_cur))
2131 return { __it, this->_M_hash_code(*__it._M_cur) };
2132 }
2133
2134 return { __hint, this->_M_hash_code(__k) };
2135 }
2136
2137 template<typename _Key, typename _Value, typename _Alloc,
2138 typename _ExtractKey, typename _Equal,
2139 typename _Hash, typename _RangeHash, typename _Unused,
2140 typename _RehashPolicy, typename _Traits>
2141 auto
2142 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2143 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2144 _M_insert_unique_node(size_type __bkt, __hash_code __code,
2145 __node_ptr __node, size_type __n_elt)
2146 -> iterator
2147 {
2148 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2149 std::pair<bool, std::size_t> __do_rehash
2150 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2151 __n_elt);
2152
2153 if (__do_rehash.first)
2154 {
2155 _M_rehash(__do_rehash.second, __saved_state);
2156 __bkt = _M_bucket_index(__code);
2157 }
2158
2159 this->_M_store_code(*__node, __code);
2160
2161 // Always insert at the beginning of the bucket.
2162 _M_insert_bucket_begin(__bkt, __node);
2163 ++_M_element_count;
2164 return iterator(__node);
2165 }
2166
2167 template<typename _Key, typename _Value, typename _Alloc,
2168 typename _ExtractKey, typename _Equal,
2169 typename _Hash, typename _RangeHash, typename _Unused,
2170 typename _RehashPolicy, typename _Traits>
2171 auto
2172 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2173 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2174 _M_insert_multi_node(__node_ptr __hint,
2175 __hash_code __code, __node_ptr __node)
2176 -> iterator
2177 {
2178 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2179 std::pair<bool, std::size_t> __do_rehash
2180 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2181
2182 if (__do_rehash.first)
2183 _M_rehash(__do_rehash.second, __saved_state);
2184
2185 this->_M_store_code(*__node, __code);
2186 const key_type& __k = _ExtractKey{}(__node->_M_v());
2187 size_type __bkt = _M_bucket_index(__code);
2188
2189 // Find the node before an equivalent one or use hint if it exists and
2190 // if it is equivalent.
2191 __node_base_ptr __prev
2192 = __builtin_expect(__hint != nullptr, false)
2193 && this->_M_equals(__k, __code, *__hint)
2194 ? __hint
2195 : _M_find_before_node(__bkt, __k, __code);
2196
2197 if (__prev)
2198 {
2199 // Insert after the node before the equivalent one.
2200 __node->_M_nxt = __prev->_M_nxt;
2201 __prev->_M_nxt = __node;
2202 if (__builtin_expect(__prev == __hint, false))
2203 // hint might be the last bucket node, in this case we need to
2204 // update next bucket.
2205 if (__node->_M_nxt
2206 && !this->_M_equals(__k, __code, *__node->_M_next()))
2207 {
2208 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2209 if (__next_bkt != __bkt)
2210 _M_buckets[__next_bkt] = __node;
2211 }
2212 }
2213 else
2214 // The inserted node has no equivalent in the hashtable. We must
2215 // insert the new node at the beginning of the bucket to preserve
2216 // equivalent elements' relative positions.
2217 _M_insert_bucket_begin(__bkt, __node);
2218 ++_M_element_count;
2219 return iterator(__node);
2220 }
2221
2222 // Insert v if no element with its key is already present.
2223 template<typename _Key, typename _Value, typename _Alloc,
2224 typename _ExtractKey, typename _Equal,
2225 typename _Hash, typename _RangeHash, typename _Unused,
2226 typename _RehashPolicy, typename _Traits>
2227 template<typename _Kt, typename _Arg, typename _NodeGenerator>
2228 auto
2229 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2230 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2231 _M_insert_unique(_Kt&& __k, _Arg&& __v,
2232 const _NodeGenerator& __node_gen)
2233 -> pair<iterator, bool>
2234 {
2235 if (size() <= __small_size_threshold())
2236 for (auto __it = begin(); __it != end(); ++__it)
2237 if (this->_M_key_equals_tr(__k, *__it._M_cur))
2238 return { __it, false };
2239
2240 __hash_code __code = this->_M_hash_code_tr(__k);
2241 size_type __bkt = _M_bucket_index(__code);
2242
2243 if (size() > __small_size_threshold())
2244 if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
2245 return { iterator(__node), false };
2246
2247 _Scoped_node __node {
2248 __node_builder_t::_S_build(std::forward<_Kt>(__k),
2249 std::forward<_Arg>(__v),
2250 __node_gen),
2251 this
2252 };
2253 auto __pos
2254 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2255 __node._M_node = nullptr;
2256 return { __pos, true };
2257 }
2258
2259 // Insert v unconditionally.
2260 template<typename _Key, typename _Value, typename _Alloc,
2261 typename _ExtractKey, typename _Equal,
2262 typename _Hash, typename _RangeHash, typename _Unused,
2263 typename _RehashPolicy, typename _Traits>
2264 template<typename _Arg, typename _NodeGenerator>
2265 auto
2266 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2267 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2268 _M_insert(const_iterator __hint, _Arg&& __v,
2269 const _NodeGenerator& __node_gen,
2270 false_type /* __uks */)
2271 -> iterator
2272 {
2273 // First allocate new node so that we don't do anything if it throws.
2274 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
2275
2276 // Second compute the hash code so that we don't rehash if it throws.
2277 auto __res = this->_M_compute_hash_code(
2278 __hint, _ExtractKey{}(__node._M_node->_M_v()));
2279
2280 auto __pos
2281 = _M_insert_multi_node(__res.first._M_cur, __res.second,
2282 __node._M_node);
2283 __node._M_node = nullptr;
2284 return __pos;
2285 }
2286
2287 template<typename _Key, typename _Value, typename _Alloc,
2288 typename _ExtractKey, typename _Equal,
2289 typename _Hash, typename _RangeHash, typename _Unused,
2290 typename _RehashPolicy, typename _Traits>
2291 auto
2292 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2293 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2294 erase(const_iterator __it)
2295 -> iterator
2296 {
2297 __node_ptr __n = __it._M_cur;
2298 std::size_t __bkt = _M_bucket_index(*__n);
2299
2300 // Look for previous node to unlink it from the erased one, this
2301 // is why we need buckets to contain the before begin to make
2302 // this search fast.
2303 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2304 return _M_erase(__bkt, __prev_n, __n);
2305 }
2306
2307 template<typename _Key, typename _Value, typename _Alloc,
2308 typename _ExtractKey, typename _Equal,
2309 typename _Hash, typename _RangeHash, typename _Unused,
2310 typename _RehashPolicy, typename _Traits>
2311 auto
2312 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2313 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2314 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2315 -> iterator
2316 {
2317 if (__prev_n == _M_buckets[__bkt])
2318 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2319 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2320 else if (__n->_M_nxt)
2321 {
2322 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2323 if (__next_bkt != __bkt)
2324 _M_buckets[__next_bkt] = __prev_n;
2325 }
2326
2327 __prev_n->_M_nxt = __n->_M_nxt;
2328 iterator __result(__n->_M_next());
2329 this->_M_deallocate_node(__n);
2330 --_M_element_count;
2331
2332 return __result;
2333 }
2334
2335 template<typename _Key, typename _Value, typename _Alloc,
2336 typename _ExtractKey, typename _Equal,
2337 typename _Hash, typename _RangeHash, typename _Unused,
2338 typename _RehashPolicy, typename _Traits>
2339 auto
2340 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2341 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2342 _M_erase(true_type /* __uks */, const key_type& __k)
2343 -> size_type
2344 {
2345 __node_base_ptr __prev_n;
2346 __node_ptr __n;
2347 std::size_t __bkt;
2348 if (size() <= __small_size_threshold())
2349 {
2350 __prev_n = _M_find_before_node(__k);
2351 if (!__prev_n)
2352 return 0;
2353
2354 // We found a matching node, erase it.
2355 __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
2356 __bkt = _M_bucket_index(*__n);
2357 }
2358 else
2359 {
2360 __hash_code __code = this->_M_hash_code(__k);
2361 __bkt = _M_bucket_index(__code);
2362
2363 // Look for the node before the first matching node.
2364 __prev_n = _M_find_before_node(__bkt, __k, __code);
2365 if (!__prev_n)
2366 return 0;
2367
2368 // We found a matching node, erase it.
2369 __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
2370 }
2371
2372 _M_erase(__bkt, __prev_n, __n);
2373 return 1;
2374 }
2375
2376 template<typename _Key, typename _Value, typename _Alloc,
2377 typename _ExtractKey, typename _Equal,
2378 typename _Hash, typename _RangeHash, typename _Unused,
2379 typename _RehashPolicy, typename _Traits>
2380 auto
2381 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2382 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2383 _M_erase(false_type /* __uks */, const key_type& __k)
2384 -> size_type
2385 {
2386 std::size_t __bkt;
2387 __node_base_ptr __prev_n;
2388 __node_ptr __n;
2389 if (size() <= __small_size_threshold())
2390 {
2391 __prev_n = _M_find_before_node(__k);
2392 if (!__prev_n)
2393 return 0;
2394
2395 // We found a matching node, erase it.
2396 __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
2397 __bkt = _M_bucket_index(*__n);
2398 }
2399 else
2400 {
2401 __hash_code __code = this->_M_hash_code(__k);
2402 __bkt = _M_bucket_index(__code);
2403
2404 // Look for the node before the first matching node.
2405 __prev_n = _M_find_before_node(__bkt, __k, __code);
2406 if (!__prev_n)
2407 return 0;
2408
2409 __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
2410 }
2411
2412 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2413 // 526. Is it undefined if a function in the standard changes
2414 // in parameters?
2415 // We use one loop to find all matching nodes and another to deallocate
2416 // them so that the key stays valid during the first loop. It might be
2417 // invalidated indirectly when destroying nodes.
2418 __node_ptr __n_last = __n->_M_next();
2419 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2420 __n_last = __n_last->_M_next();
2421
2422 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2423
2424 // Deallocate nodes.
2425 size_type __result = 0;
2426 do
2427 {
2428 __node_ptr __p = __n->_M_next();
2429 this->_M_deallocate_node(__n);
2430 __n = __p;
2431 ++__result;
2432 }
2433 while (__n != __n_last);
2434
2435 _M_element_count -= __result;
2436 if (__prev_n == _M_buckets[__bkt])
2437 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2438 else if (__n_last_bkt != __bkt)
2439 _M_buckets[__n_last_bkt] = __prev_n;
2440 __prev_n->_M_nxt = __n_last;
2441 return __result;
2442 }
2443
2444 template<typename _Key, typename _Value, typename _Alloc,
2445 typename _ExtractKey, typename _Equal,
2446 typename _Hash, typename _RangeHash, typename _Unused,
2447 typename _RehashPolicy, typename _Traits>
2448 auto
2449 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2450 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2451 erase(const_iterator __first, const_iterator __last)
2452 -> iterator
2453 {
2454 __node_ptr __n = __first._M_cur;
2455 __node_ptr __last_n = __last._M_cur;
2456 if (__n == __last_n)
2457 return iterator(__n);
2458
2459 std::size_t __bkt = _M_bucket_index(*__n);
2460
2461 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2462 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2463 std::size_t __n_bkt = __bkt;
2464 for (;;)
2465 {
2466 do
2467 {
2468 __node_ptr __tmp = __n;
2469 __n = __n->_M_next();
2470 this->_M_deallocate_node(__tmp);
2471 --_M_element_count;
2472 if (!__n)
2473 break;
2474 __n_bkt = _M_bucket_index(*__n);
2475 }
2476 while (__n != __last_n && __n_bkt == __bkt);
2477 if (__is_bucket_begin)
2478 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2479 if (__n == __last_n)
2480 break;
2481 __is_bucket_begin = true;
2482 __bkt = __n_bkt;
2483 }
2484
2485 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2486 _M_buckets[__n_bkt] = __prev_n;
2487 __prev_n->_M_nxt = __n;
2488 return iterator(__n);
2489 }
2490
2491 template<typename _Key, typename _Value, typename _Alloc,
2492 typename _ExtractKey, typename _Equal,
2493 typename _Hash, typename _RangeHash, typename _Unused,
2494 typename _RehashPolicy, typename _Traits>
2495 void
2496 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2497 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2498 clear() noexcept
2499 {
2500 this->_M_deallocate_nodes(_M_begin());
2501 __builtin_memset(_M_buckets, 0,
2502 _M_bucket_count * sizeof(__node_base_ptr));
2503 _M_element_count = 0;
2504 _M_before_begin._M_nxt = nullptr;
2505 }
2506
2507 template<typename _Key, typename _Value, typename _Alloc,
2508 typename _ExtractKey, typename _Equal,
2509 typename _Hash, typename _RangeHash, typename _Unused,
2510 typename _RehashPolicy, typename _Traits>
2511 void
2512 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2513 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2514 rehash(size_type __bkt_count)
2515 {
2516 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2517 __bkt_count
2518 = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2519 __bkt_count);
2520 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2521
2522 if (__bkt_count != _M_bucket_count)
2523 _M_rehash(__bkt_count, __saved_state);
2524 else
2525 // No rehash, restore previous state to keep it consistent with
2526 // container state.
2527 _M_rehash_policy._M_reset(__saved_state);
2528 }
2529
2530 template<typename _Key, typename _Value, typename _Alloc,
2531 typename _ExtractKey, typename _Equal,
2532 typename _Hash, typename _RangeHash, typename _Unused,
2533 typename _RehashPolicy, typename _Traits>
2534 void
2535 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2536 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2537 _M_rehash(size_type __bkt_count, const __rehash_state& __state)
2538 {
2539 __try
2540 {
2541 _M_rehash_aux(__bkt_count, __unique_keys{});
2542 }
2543 __catch(...)
2544 {
2545 // A failure here means that buckets allocation failed. We only
2546 // have to restore hash policy previous state.
2547 _M_rehash_policy._M_reset(__state);
2548 __throw_exception_again;
2549 }
2550 }
2551
2552 // Rehash when there is no equivalent elements.
2553 template<typename _Key, typename _Value, typename _Alloc,
2554 typename _ExtractKey, typename _Equal,
2555 typename _Hash, typename _RangeHash, typename _Unused,
2556 typename _RehashPolicy, typename _Traits>
2557 void
2558 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2559 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2560 _M_rehash_aux(size_type __bkt_count, true_type /* __uks */)
2561 {
2562 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2563 __node_ptr __p = _M_begin();
2564 _M_before_begin._M_nxt = nullptr;
2565 std::size_t __bbegin_bkt = 0;
2566 while (__p)
2567 {
2568 __node_ptr __next = __p->_M_next();
2569 std::size_t __bkt
2570 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2571 if (!__new_buckets[__bkt])
2572 {
2573 __p->_M_nxt = _M_before_begin._M_nxt;
2574 _M_before_begin._M_nxt = __p;
2575 __new_buckets[__bkt] = &_M_before_begin;
2576 if (__p->_M_nxt)
2577 __new_buckets[__bbegin_bkt] = __p;
2578 __bbegin_bkt = __bkt;
2579 }
2580 else
2581 {
2582 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2583 __new_buckets[__bkt]->_M_nxt = __p;
2584 }
2585
2586 __p = __next;
2587 }
2588
2589 _M_deallocate_buckets();
2590 _M_bucket_count = __bkt_count;
2591 _M_buckets = __new_buckets;
2592 }
2593
2594 // Rehash when there can be equivalent elements, preserve their relative
2595 // order.
2596 template<typename _Key, typename _Value, typename _Alloc,
2597 typename _ExtractKey, typename _Equal,
2598 typename _Hash, typename _RangeHash, typename _Unused,
2599 typename _RehashPolicy, typename _Traits>
2600 void
2601 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2602 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2603 _M_rehash_aux(size_type __bkt_count, false_type /* __uks */)
2604 {
2605 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2606 __node_ptr __p = _M_begin();
2607 _M_before_begin._M_nxt = nullptr;
2608 std::size_t __bbegin_bkt = 0;
2609 std::size_t __prev_bkt = 0;
2610 __node_ptr __prev_p = nullptr;
2611 bool __check_bucket = false;
2612
2613 while (__p)
2614 {
2615 __node_ptr __next = __p->_M_next();
2616 std::size_t __bkt
2617 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2618
2619 if (__prev_p && __prev_bkt == __bkt)
2620 {
2621 // Previous insert was already in this bucket, we insert after
2622 // the previously inserted one to preserve equivalent elements
2623 // relative order.
2624 __p->_M_nxt = __prev_p->_M_nxt;
2625 __prev_p->_M_nxt = __p;
2626
2627 // Inserting after a node in a bucket require to check that we
2628 // haven't change the bucket last node, in this case next
2629 // bucket containing its before begin node must be updated. We
2630 // schedule a check as soon as we move out of the sequence of
2631 // equivalent nodes to limit the number of checks.
2632 __check_bucket = true;
2633 }
2634 else
2635 {
2636 if (__check_bucket)
2637 {
2638 // Check if we shall update the next bucket because of
2639 // insertions into __prev_bkt bucket.
2640 if (__prev_p->_M_nxt)
2641 {
2642 std::size_t __next_bkt
2643 = __hash_code_base::_M_bucket_index(
2644 *__prev_p->_M_next(), __bkt_count);
2645 if (__next_bkt != __prev_bkt)
2646 __new_buckets[__next_bkt] = __prev_p;
2647 }
2648 __check_bucket = false;
2649 }
2650
2651 if (!__new_buckets[__bkt])
2652 {
2653 __p->_M_nxt = _M_before_begin._M_nxt;
2654 _M_before_begin._M_nxt = __p;
2655 __new_buckets[__bkt] = &_M_before_begin;
2656 if (__p->_M_nxt)
2657 __new_buckets[__bbegin_bkt] = __p;
2658 __bbegin_bkt = __bkt;
2659 }
2660 else
2661 {
2662 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2663 __new_buckets[__bkt]->_M_nxt = __p;
2664 }
2665 }
2666 __prev_p = __p;
2667 __prev_bkt = __bkt;
2668 __p = __next;
2669 }
2670
2671 if (__check_bucket && __prev_p->_M_nxt)
2672 {
2673 std::size_t __next_bkt
2674 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2675 __bkt_count);
2676 if (__next_bkt != __prev_bkt)
2677 __new_buckets[__next_bkt] = __prev_p;
2678 }
2679
2680 _M_deallocate_buckets();
2681 _M_bucket_count = __bkt_count;
2682 _M_buckets = __new_buckets;
2683 }
2684
2685#if __cplusplus > 201402L
2686 template<typename, typename, typename> class _Hash_merge_helper { };
2687#endif // C++17
2688
2689#if __cpp_deduction_guides >= 201606
2690 // Used to constrain deduction guides
2691 template<typename _Hash>
2692 using _RequireNotAllocatorOrIntegral
2693 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2694#endif
2695
2696/// @endcond
2697_GLIBCXX_END_NAMESPACE_VERSION
2698} // namespace std
2699
2700#endif // _HASHTABLE_H
2701