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