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