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