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