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