libstdc++-v3/include/bits/hashtable.h

   1 // hashtable.h header -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /** @file bits/hashtable.h
  27  *  This is an internal header file, included by other library headers.
  28  *  Do not attempt to use it directly. @headername{unordered_map, unordered_set}
  29  */
  30
  31 #ifndef _HASHTABLE_H
  32 #define _HASHTABLE_H 1
  33
  34 #pragma GCC system_header
  35
  36 #include <bits/hashtable_policy.h>
  37
  38 namespace std _GLIBCXX_VISIBILITY(default)
  39 {
  40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  41
  42   // Class template _Hashtable, class definition.
  43
  44   // Meaning of class template _Hashtable's template parameters
  45
  46   // _Key and _Value: arbitrary CopyConstructible types.
  47
  48   // _Allocator: an allocator type ([lib.allocator.requirements]) whose
  49   // value type is Value.  As a conforming extension, we allow for
  50   // value type != Value.
  51
  52   // _ExtractKey: function object that takes an object of type Value
  53   // and returns a value of type _Key.
  54
  55   // _Equal: function object that takes two objects of type k and returns
  56   // a bool-like value that is true if the two objects are considered equal.
  57
  58   // _H1: the hash function.  A unary function object with argument type
  59   // Key and result type size_t.  Return values should be distributed
  60   // over the entire range [0, numeric_limits<size_t>:::max()].
  61
  62   // _H2: the range-hashing function (in the terminology of Tavori and
  63   // Dreizin).  A binary function object whose argument types and result
  64   // type are all size_t.  Given arguments r and N, the return value is
  65   // in the range [0, N).
  66
  67   // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
  68   // whose argument types are _Key and size_t and whose result type is
  69   // size_t.  Given arguments k and N, the return value is in the range
  70   // [0, N).  Default: hash(k, N) = h2(h1(k), N).  If _Hash is anything other
  71   // than the default, _H1 and _H2 are ignored.
  72
  73   // _RehashPolicy: Policy class with three members, all of which govern
  74   // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
  75   // than n.  _M_bkt_for_elements(n) returns a bucket count appropriate
  76   // for an element count of n.  _M_need_rehash(n_bkt, n_elt, n_ins)
  77   // determines whether, if the current bucket count is n_bkt and the
  78   // current element count is n_elt, we need to increase the bucket
  79   // count.  If so, returns make_pair(true, n), where n is the new
  80   // bucket count.  If not, returns make_pair(false, <anything>).
  81
  82   // __cache_hash_code: bool.  true if we store the value of the hash
  83   // function along with the value.  This is a time-space tradeoff.
  84   // Storing it may improve lookup speed by reducing the number of times
  85   // we need to call the Equal function.
  86
  87   // __constant_iterators: bool.  true if iterator and const_iterator are
  88   // both constant iterator types.  This is true for unordered_set and
  89   // unordered_multiset, false for unordered_map and unordered_multimap.
  90
  91   // __unique_keys: bool.  true if the return value of _Hashtable::count(k)
  92   // is always at most one, false if it may be an arbitrary number.  This
  93   // true for unordered_set and unordered_map, false for unordered_multiset
  94   // and unordered_multimap.
  95   /**
  96    * Here's _Hashtable data structure, each _Hashtable has:
  97    * - _Bucket[]       _M_buckets
  98    * - _Hash_node_base _M_before_begin
  99    * - size_type       _M_bucket_count
 100    * - size_type       _M_element_count
 101    *
 102    * with _Bucket being _Hash_node* and _Hash_node containing:
 103    * - _Hash_node*   _M_next
 104    * - Tp            _M_value
 105    * - size_t        _M_hash_code if cache_hash_code is true
 106    *
 107    * In terms of Standard containers the hashtable is like the aggregation of:
 108    * - std::forward_list<_Node> containing the elements
 109    * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
 110    *
 111    * The non-empty buckets contain the node before the first node in the
 112    * bucket. This design makes it possible to implement something like a
 113    * std::forward_list::insert_after on container insertion and
 114    * std::forward_list::erase_after on container erase calls.
 115    * _M_before_begin is equivalent to std::foward_list::before_begin.
 116    * Empty buckets contain nullptr.
 117    * Note that one of the non-empty buckets contains &_M_before_begin which is
 118    * not a dereferenceable node so the node pointer in a bucket shall never be
 119    * dereferenced, only its next node can be.
 120    *
 121    * Walking through a bucket's nodes requires a check on the hash code to see
 122    * if each node is still in the bucket. Such a design assumes a quite
 123    * efficient hash functor and is one of the reasons it is
 124    * highly advisable to set __cache_hash_code to true.
 125    *
 126    * The container iterators are simply built from nodes. This way incrementing
 127    * the iterator is perfectly efficient independent of how many empty buckets
 128    * there are in the container.
 129    *
 130    * On insert we compute the element's hash code and use it to it find the
 131    * bucket index. If the element must be inserted in an empty bucket we add
 132    * it at the beginning of the singly linked list and make the bucket point to
 133    * _M_before_begin. The bucket that used to point to _M_before_begin, if any,
 134    * is updated to point to its new before begin node.
 135    *
 136    * On erase, the simple iterator design requires using the hash functor to
 137    * get the index of the bucket to update. For this reason, when
 138    * __cache_hash_code is set to false, the hash functor must not throw
 139    * and this is enforced by a statied assertion.
 140    */
 141
 142   template<typename _Key, typename _Value, typename _Allocator,
 143            typename _ExtractKey, typename _Equal,
 144            typename _H1, typename _H2, typename _Hash,
 145            typename _RehashPolicy,
 146            bool __cache_hash_code,
 147            bool __constant_iterators,
 148            bool __unique_keys>
 149     class _Hashtable
 150     : public __detail::_Rehash_base<_RehashPolicy,
 151                                     _Hashtable<_Key, _Value, _Allocator,
 152                                                _ExtractKey,
 153                                                _Equal, _H1, _H2, _Hash,
 154                                                _RehashPolicy,
 155                                                __cache_hash_code,
 156                                                __constant_iterators,
 157                                                __unique_keys> >,
 158       public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 159                                        _H1, _H2, _Hash, __cache_hash_code>,
 160       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
 161                                  _Hashtable<_Key, _Value, _Allocator,
 162                                             _ExtractKey,
 163                                             _Equal, _H1, _H2, _Hash,
 164                                             _RehashPolicy,
 165                                             __cache_hash_code,
 166                                             __constant_iterators,
 167                                             __unique_keys> >,
 168       public __detail::_Equality_base<_ExtractKey, __unique_keys,
 169                                       _Hashtable<_Key, _Value, _Allocator,
 170                                                  _ExtractKey,
 171                                                  _Equal, _H1, _H2, _Hash,
 172                                                  _RehashPolicy,
 173                                                  __cache_hash_code,
 174                                                  __constant_iterators,
 175                                                  __unique_keys> >
 176     {
 177       template<typename _Cond>
 178         using __if_hash_code_cached
 179           = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
 180
 181       template<typename _Cond>
 182         using __if_hash_code_not_cached
 183           = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
 184
 185       // When hash codes are not cached the hash functor shall not throw
 186       // because it is used in methods (erase, swap...) that shall not throw.
 187       static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
 188                                                                 _H1>>::value,
 189             "Cache the hash code or qualify your hash functor with noexcept");
 190
 191       // Following two static assertions are necessary to guarantee that
 192       // swapping two hashtable instances won't invalidate associated local
 193       // iterators.
 194
 195       // When hash codes are cached local iterator only uses H2 which must then
 196       // be empty.
 197       static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
 198             "Functor used to map hash code to bucket index must be empty");
 199
 200       typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
 201                                         _H1, _H2, _Hash,
 202                                         __cache_hash_code> _HCBase;
 203
 204       // When hash codes are not cached local iterator is going to use _HCBase
 205       // above to compute node bucket index so it has to be empty.
 206       static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
 207             "Cache the hash code or make functors involved in hash code"
 208             " and bucket index computation empty");
 209
 210     public:
 211       typedef _Allocator                                  allocator_type;
 212       typedef _Value                                      value_type;
 213       typedef _Key                                        key_type;
 214       typedef _Equal                                      key_equal;
 215       // mapped_type, if present, comes from _Map_base.
 216       // hasher, if present, comes from _Hash_code_base.
 217       typedef typename _Allocator::pointer                pointer;
 218       typedef typename _Allocator::const_pointer          const_pointer;
 219       typedef typename _Allocator::reference              reference;
 220       typedef typename _Allocator::const_reference        const_reference;
 221
 222       typedef std::size_t                                 size_type;
 223       typedef std::ptrdiff_t                              difference_type;
 224       typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
 225                                         _H1, _H2, _Hash,
 226                                         __constant_iterators,
 227                                         __cache_hash_code>
 228                                                           local_iterator;
 229       typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
 230                                               _H1, _H2, _Hash,
 231                                               __constant_iterators,
 232                                               __cache_hash_code>
 233                                                           const_local_iterator;
 234       typedef __detail::_Node_iterator<value_type, __constant_iterators,
 235                                        __cache_hash_code>
 236                                                           iterator;
 237       typedef __detail::_Node_const_iterator<value_type,
 238                                              __constant_iterators,
 239                                              __cache_hash_code>
 240                                                           const_iterator;
 241
 242       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
 243                typename _Hashtable2>
 244         friend struct __detail::_Map_base;
 245
 246     private:
 247       typedef typename _RehashPolicy::_State _RehashPolicyState;
 248       typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
 249       typedef typename _Allocator::template rebind<_Node>::other
 250                                                         _Node_allocator_type;
 251       typedef __detail::_Hash_node_base _BaseNode;
 252       typedef _BaseNode* _Bucket;
 253       typedef typename _Allocator::template rebind<_Bucket>::other
 254                                                         _Bucket_allocator_type;
 255
 256       typedef typename _Allocator::template rebind<_Value>::other
 257                                                         _Value_allocator_type;
 258
 259       _Node_allocator_type      _M_node_allocator;
 260       _Bucket*                  _M_buckets;
 261       size_type                 _M_bucket_count;
 262       _BaseNode                 _M_before_begin;
 263       size_type                 _M_element_count;
 264       _RehashPolicy             _M_rehash_policy;
 265
 266       template<typename... _Args>
 267         _Node*
 268         _M_allocate_node(_Args&&... __args);
 269
 270       void
 271       _M_deallocate_node(_Node* __n);
 272
 273       // Deallocate the linked list of nodes pointed to by __n
 274       void
 275       _M_deallocate_nodes(_Node* __n);
 276
 277       _Bucket*
 278       _M_allocate_buckets(size_type __n);
 279
 280       void
 281       _M_deallocate_buckets(_Bucket*, size_type __n);
 282
 283       // Gets bucket begin, deals with the fact that non-empty buckets contain
 284       // their before begin node.
 285       _Node*
 286       _M_bucket_begin(size_type __bkt) const;
 287
 288       _Node*
 289       _M_begin() const
 290       { return static_cast<_Node*>(_M_before_begin._M_nxt); }
 291
 292     public:
 293       // Constructor, destructor, assignment, swap
 294       _Hashtable(size_type __bucket_hint,
 295                  const _H1&, const _H2&, const _Hash&,
 296                  const _Equal&, const _ExtractKey&,
 297                  const allocator_type&);
 298
 299       template<typename _InputIterator>
 300         _Hashtable(_InputIterator __first, _InputIterator __last,
 301                    size_type __bucket_hint,
 302                    const _H1&, const _H2&, const _Hash&,
 303                    const _Equal&, const _ExtractKey&,
 304                    const allocator_type&);
 305
 306       _Hashtable(const _Hashtable&);
 307
 308       _Hashtable(_Hashtable&&);
 309
 310       _Hashtable&
 311       operator=(const _Hashtable& __ht)
 312       {
 313         _Hashtable __tmp(__ht);
 314         this->swap(__tmp);
 315         return *this;
 316       }
 317
 318       _Hashtable&
 319       operator=(_Hashtable&& __ht)
 320       {
 321         // NB: DR 1204.
 322         // NB: DR 675.
 323         this->clear();
 324         this->swap(__ht);
 325         return *this;
 326       }
 327
 328       ~_Hashtable() noexcept;
 329
 330       void swap(_Hashtable&);
 331
 332       // Basic container operations
 333       iterator
 334       begin() noexcept
 335       { return iterator(_M_begin()); }
 336
 337       const_iterator
 338       begin() const noexcept
 339       { return const_iterator(_M_begin()); }
 340
 341       iterator
 342       end() noexcept
 343       { return iterator(nullptr); }
 344
 345       const_iterator
 346       end() const noexcept
 347       { return const_iterator(nullptr); }
 348
 349       const_iterator
 350       cbegin() const noexcept
 351       { return const_iterator(_M_begin()); }
 352
 353       const_iterator
 354       cend() const noexcept
 355       { return const_iterator(nullptr); }
 356
 357       size_type
 358       size() const noexcept
 359       { return _M_element_count; }
 360
 361       bool
 362       empty() const noexcept
 363       { return size() == 0; }
 364
 365       allocator_type
 366       get_allocator() const noexcept
 367       { return allocator_type(_M_node_allocator); }
 368
 369       size_type
 370       max_size() const noexcept
 371       { return _M_node_allocator.max_size(); }
 372
 373       // Observers
 374       key_equal
 375       key_eq() const
 376       { return this->_M_eq(); }
 377
 378       // hash_function, if present, comes from _Hash_code_base.
 379
 380       // Bucket operations
 381       size_type
 382       bucket_count() const noexcept
 383       { return _M_bucket_count; }
 384
 385       size_type
 386       max_bucket_count() const noexcept
 387       { return max_size(); }
 388
 389       size_type
 390       bucket_size(size_type __n) const
 391       { return std::distance(begin(__n), end(__n)); }
 392
 393       size_type
 394       bucket(const key_type& __k) const
 395       { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
 396
 397       local_iterator
 398       begin(size_type __n)
 399       { return local_iterator(_M_bucket_begin(__n), __n,
 400                               _M_bucket_count); }
 401
 402       local_iterator
 403       end(size_type __n)
 404       { return local_iterator(nullptr, __n, _M_bucket_count); }
 405
 406       const_local_iterator
 407       begin(size_type __n) const
 408       { return const_local_iterator(_M_bucket_begin(__n), __n,
 409                                     _M_bucket_count); }
 410
 411       const_local_iterator
 412       end(size_type __n) const
 413       { return const_local_iterator(nullptr, __n, _M_bucket_count); }
 414
 415       // DR 691.
 416       const_local_iterator
 417       cbegin(size_type __n) const
 418       { return const_local_iterator(_M_bucket_begin(__n), __n,
 419                                     _M_bucket_count); }
 420
 421       const_local_iterator
 422       cend(size_type __n) const
 423       { return const_local_iterator(nullptr, __n, _M_bucket_count); }
 424
 425       float
 426       load_factor() const noexcept
 427       {
 428         return static_cast<float>(size()) / static_cast<float>(bucket_count());
 429       }
 430
 431       // max_load_factor, if present, comes from _Rehash_base.
 432
 433       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
 434       // useful if _RehashPolicy is something other than the default.
 435       const _RehashPolicy&
 436       __rehash_policy() const
 437       { return _M_rehash_policy; }
 438
 439       void
 440       __rehash_policy(const _RehashPolicy&);
 441
 442       // Lookup.
 443       iterator
 444       find(const key_type& __k);
 445
 446       const_iterator
 447       find(const key_type& __k) const;
 448
 449       size_type
 450       count(const key_type& __k) const;
 451
 452       std::pair<iterator, iterator>
 453       equal_range(const key_type& __k);
 454
 455       std::pair<const_iterator, const_iterator>
 456       equal_range(const key_type& __k) const;
 457
 458     private:
 459       // Bucket index computation helpers.
 460       size_type
 461       _M_bucket_index(_Node* __n) const
 462       { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
 463
 464       size_type
 465       _M_bucket_index(const key_type& __k,
 466                       typename _Hashtable::_Hash_code_type __c) const
 467       { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
 468
 469       // Find and insert helper functions and types
 470       // Find the node before the one matching the criteria.
 471       _BaseNode*
 472       _M_find_before_node(size_type, const key_type&,
 473                           typename _Hashtable::_Hash_code_type) const;
 474
 475       _Node*
 476       _M_find_node(size_type __bkt, const key_type& __key,
 477                    typename _Hashtable::_Hash_code_type __c) const
 478       {
 479         _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
 480         if (__before_n)
 481           return static_cast<_Node*>(__before_n->_M_nxt);
 482         return nullptr;
 483       }
 484
 485       // Insert a node at the beginning of a bucket.
 486       void
 487       _M_insert_bucket_begin(size_type, _Node*);
 488
 489       // Remove the bucket first node
 490       void
 491       _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
 492                              size_type __next_bkt);
 493
 494       // Get the node before __n in the bucket __bkt
 495       _BaseNode*
 496       _M_get_previous_node(size_type __bkt, _BaseNode* __n);
 497
 498       template<typename _Arg>
 499         iterator
 500         _M_insert_bucket(_Arg&&, size_type,
 501                          typename _Hashtable::_Hash_code_type);
 502
 503       typedef typename std::conditional<__unique_keys,
 504                                         std::pair<iterator, bool>,
 505                                         iterator>::type
 506         _Insert_Return_Type;
 507
 508       typedef typename std::conditional<__unique_keys,
 509                                         std::_Select1st<_Insert_Return_Type>,
 510                                         std::_Identity<_Insert_Return_Type>
 511                                    >::type
 512         _Insert_Conv_Type;
 513
 514     protected:
 515       template<typename... _Args>
 516         std::pair<iterator, bool>
 517         _M_emplace(std::true_type, _Args&&... __args);
 518
 519       template<typename... _Args>
 520         iterator
 521         _M_emplace(std::false_type, _Args&&... __args);
 522
 523       template<typename _Arg>
 524         std::pair<iterator, bool>
 525         _M_insert(_Arg&&, std::true_type);
 526
 527       template<typename _Arg>
 528         iterator
 529         _M_insert(_Arg&&, std::false_type);
 530
 531     public:
 532       // Emplace, insert and erase
 533       template<typename... _Args>
 534         _Insert_Return_Type
 535         emplace(_Args&&... __args)
 536         { return _M_emplace(integral_constant<bool, __unique_keys>(),
 537                             std::forward<_Args>(__args)...); }
 538
 539       template<typename... _Args>
 540         iterator
 541         emplace_hint(const_iterator, _Args&&... __args)
 542         { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
 543
 544       _Insert_Return_Type
 545       insert(const value_type& __v)
 546       { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
 547
 548       iterator
 549       insert(const_iterator, const value_type& __v)
 550       { return _Insert_Conv_Type()(insert(__v)); }
 551
 552       template<typename _Pair, typename = typename
 553         std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
 554                               std::is_constructible<value_type,
 555                                                     _Pair&&>>::value>::type>
 556         _Insert_Return_Type
 557         insert(_Pair&& __v)
 558         { return _M_insert(std::forward<_Pair>(__v),
 559                            integral_constant<bool, __unique_keys>()); }
 560
 561       template<typename _Pair, typename = typename
 562         std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
 563                               std::is_constructible<value_type,
 564                                                     _Pair&&>>::value>::type>
 565         iterator
 566         insert(const_iterator, _Pair&& __v)
 567         { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
 568
 569       template<typename _InputIterator>
 570         void
 571         insert(_InputIterator __first, _InputIterator __last);
 572
 573       void
 574       insert(initializer_list<value_type> __l)
 575       { this->insert(__l.begin(), __l.end()); }
 576
 577       iterator
 578       erase(const_iterator);
 579
 580       // LWG 2059.
 581       iterator
 582       erase(iterator __it)
 583       { return erase(const_iterator(__it)); }
 584
 585       size_type
 586       erase(const key_type&);
 587
 588       iterator
 589       erase(const_iterator, const_iterator);
 590
 591       void
 592       clear() noexcept;
 593
 594       // Set number of buckets to be appropriate for container of n element.
 595       void rehash(size_type __n);
 596
 597       // DR 1189.
 598       // reserve, if present, comes from _Rehash_base.
 599
 600     private:
 601       // Helper rehash method used when keys are unique.
 602       void _M_rehash_aux(size_type __n, std::true_type);
 603
 604       // Helper rehash method used when keys can be non-unique.
 605       void _M_rehash_aux(size_type __n, std::false_type);
 606
 607       // Unconditionally change size of bucket array to n, restore hash policy
 608       // state to __state on exception.
 609       void _M_rehash(size_type __n, const _RehashPolicyState& __state);
 610     };
 611
 612
 613   // Definitions of class template _Hashtable's out-of-line member functions.
 614   template<typename _Key, typename _Value,
 615            typename _Allocator, typename _ExtractKey, typename _Equal,
 616            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 617            bool __chc, bool __cit, bool __uk>
 618     template<typename... _Args>
 619       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 620                           _H1, _H2, _Hash, _RehashPolicy,
 621                           __chc, __cit, __uk>::_Node*
 622       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 623                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 624       _M_allocate_node(_Args&&... __args)
 625       {
 626         _Node* __n = _M_node_allocator.allocate(1);
 627         __try
 628           {
 629             _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
 630             return __n;
 631           }
 632         __catch(...)
 633           {
 634             _M_node_allocator.deallocate(__n, 1);
 635             __throw_exception_again;
 636           }
 637       }
 638
 639   template<typename _Key, typename _Value,
 640            typename _Allocator, typename _ExtractKey, typename _Equal,
 641            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 642            bool __chc, bool __cit, bool __uk>
 643     void
 644     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 645                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 646     _M_deallocate_node(_Node* __n)
 647     {
 648       _M_node_allocator.destroy(__n);
 649       _M_node_allocator.deallocate(__n, 1);
 650     }
 651
 652   template<typename _Key, typename _Value,
 653            typename _Allocator, typename _ExtractKey, typename _Equal,
 654            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 655            bool __chc, bool __cit, bool __uk>
 656     void
 657     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 658                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 659     _M_deallocate_nodes(_Node* __n)
 660     {
 661       while (__n)
 662         {
 663           _Node* __tmp = __n;
 664           __n = __n->_M_next();
 665           _M_deallocate_node(__tmp);
 666         }
 667     }
 668
 669   template<typename _Key, typename _Value,
 670            typename _Allocator, typename _ExtractKey, typename _Equal,
 671            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 672            bool __chc, bool __cit, bool __uk>
 673     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 674                         _H1, _H2, _Hash, _RehashPolicy,
 675                         __chc, __cit, __uk>::_Bucket*
 676     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 677                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 678     _M_allocate_buckets(size_type __n)
 679     {
 680       _Bucket_allocator_type __alloc(_M_node_allocator);
 681
 682       _Bucket* __p = __alloc.allocate(__n);
 683       __builtin_memset(__p, 0, __n * sizeof(_Bucket));
 684       return __p;
 685     }
 686
 687   template<typename _Key, typename _Value,
 688            typename _Allocator, typename _ExtractKey, typename _Equal,
 689            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 690            bool __chc, bool __cit, bool __uk>
 691     void
 692     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 693                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 694     _M_deallocate_buckets(_Bucket* __p, size_type __n)
 695     {
 696       _Bucket_allocator_type __alloc(_M_node_allocator);
 697       __alloc.deallocate(__p, __n);
 698     }
 699
 700   template<typename _Key, typename _Value,
 701            typename _Allocator, typename _ExtractKey, typename _Equal,
 702            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 703            bool __chc, bool __cit, bool __uk>
 704     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
 705                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
 706                         __chc, __cit, __uk>::_Node*
 707     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 708                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 709     _M_bucket_begin(size_type __bkt) const
 710     {
 711       _BaseNode* __n = _M_buckets[__bkt];
 712       return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;
 713     }
 714
 715   template<typename _Key, typename _Value,
 716            typename _Allocator, typename _ExtractKey, typename _Equal,
 717            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 718            bool __chc, bool __cit, bool __uk>
 719     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 720                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 721     _Hashtable(size_type __bucket_hint,
 722                const _H1& __h1, const _H2& __h2, const _Hash& __h,
 723                const _Equal& __eq, const _ExtractKey& __exk,
 724                const allocator_type& __a)
 725     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
 726       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 727                                 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
 728                                                         __eq),
 729       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 730       _M_node_allocator(__a),
 731       _M_bucket_count(0),
 732       _M_element_count(0),
 733       _M_rehash_policy()
 734     {
 735       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
 736       // We don't want the rehash policy to ask for the hashtable to shrink
 737       // on the first insertion so we need to reset its previous resize level.
 738       _M_rehash_policy._M_prev_resize = 0;
 739       _M_buckets = _M_allocate_buckets(_M_bucket_count);
 740     }
 741
 742   template<typename _Key, typename _Value,
 743            typename _Allocator, typename _ExtractKey, typename _Equal,
 744            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 745            bool __chc, bool __cit, bool __uk>
 746     template<typename _InputIterator>
 747       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 748                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 749       _Hashtable(_InputIterator __f, _InputIterator __l,
 750                  size_type __bucket_hint,
 751                  const _H1& __h1, const _H2& __h2, const _Hash& __h,
 752                  const _Equal& __eq, const _ExtractKey& __exk,
 753                  const allocator_type& __a)
 754       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
 755         __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 756                                   _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
 757                                                           __eq),
 758         __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 759         _M_node_allocator(__a),
 760         _M_bucket_count(0),
 761         _M_element_count(0),
 762         _M_rehash_policy()
 763       {
 764         _M_bucket_count =
 765           _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
 766                                                                        __l));
 767         if (_M_bucket_count <= __bucket_hint)
 768           _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
 769
 770         // We don't want the rehash policy to ask for the hashtable to shrink
 771         // on the first insertion so we need to reset its previous resize
 772         // level.
 773         _M_rehash_policy._M_prev_resize = 0;
 774         _M_buckets = _M_allocate_buckets(_M_bucket_count);
 775         __try
 776           {
 777             for (; __f != __l; ++__f)
 778               this->insert(*__f);
 779           }
 780         __catch(...)
 781           {
 782             clear();
 783             _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 784             __throw_exception_again;
 785           }
 786       }
 787
 788   template<typename _Key, typename _Value,
 789            typename _Allocator, typename _ExtractKey, typename _Equal,
 790            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 791            bool __chc, bool __cit, bool __uk>
 792     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 793                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 794     _Hashtable(const _Hashtable& __ht)
 795     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
 796       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 797                                 _H1, _H2, _Hash, __chc>(__ht),
 798       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
 799       _M_node_allocator(__ht._M_node_allocator),
 800       _M_bucket_count(__ht._M_bucket_count),
 801       _M_element_count(__ht._M_element_count),
 802       _M_rehash_policy(__ht._M_rehash_policy)
 803     {
 804       _M_buckets = _M_allocate_buckets(_M_bucket_count);
 805       __try
 806         {
 807           if (!__ht._M_before_begin._M_nxt)
 808             return;
 809
 810           // First deal with the special first node pointed to by
 811           // _M_before_begin.
 812           const _Node* __ht_n = __ht._M_begin();
 813           _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
 814           this->_M_copy_code(__this_n, __ht_n);
 815           _M_before_begin._M_nxt = __this_n;
 816           _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
 817
 818           // Then deal with other nodes.
 819           _BaseNode* __prev_n = __this_n;
 820           for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
 821             {
 822               __this_n = _M_allocate_node(__ht_n->_M_v);
 823               __prev_n->_M_nxt = __this_n;
 824               this->_M_copy_code(__this_n, __ht_n);
 825               size_type __bkt = _M_bucket_index(__this_n);
 826               if (!_M_buckets[__bkt])
 827                 _M_buckets[__bkt] = __prev_n;
 828               __prev_n = __this_n;
 829             }
 830         }
 831       __catch(...)
 832         {
 833           clear();
 834           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 835           __throw_exception_again;
 836         }
 837     }
 838
 839   template<typename _Key, typename _Value,
 840            typename _Allocator, typename _ExtractKey, typename _Equal,
 841            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 842            bool __chc, bool __cit, bool __uk>
 843     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 844                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 845     _Hashtable(_Hashtable&& __ht)
 846     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
 847       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 848                                 _H1, _H2, _Hash, __chc>(__ht),
 849       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
 850       _M_node_allocator(std::move(__ht._M_node_allocator)),
 851       _M_buckets(__ht._M_buckets),
 852       _M_bucket_count(__ht._M_bucket_count),
 853       _M_before_begin(__ht._M_before_begin._M_nxt),
 854       _M_element_count(__ht._M_element_count),
 855       _M_rehash_policy(__ht._M_rehash_policy)
 856     {
 857       // Update, if necessary, bucket pointing to before begin that hasn't move.
 858       if (_M_begin())
 859         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
 860       __ht._M_rehash_policy = _RehashPolicy();
 861       __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
 862       __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
 863       __ht._M_before_begin._M_nxt = nullptr;
 864       __ht._M_element_count = 0;
 865     }
 866
 867   template<typename _Key, typename _Value,
 868            typename _Allocator, typename _ExtractKey, typename _Equal,
 869            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 870            bool __chc, bool __cit, bool __uk>
 871     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 872                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 873     ~_Hashtable() noexcept
 874     {
 875       clear();
 876       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 877     }
 878
 879   template<typename _Key, typename _Value,
 880            typename _Allocator, typename _ExtractKey, typename _Equal,
 881            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 882            bool __chc, bool __cit, bool __uk>
 883     void
 884     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 885                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 886     swap(_Hashtable& __x)
 887     {
 888       // The only base class with member variables is hash_code_base.  We
 889       // define _Hash_code_base::_M_swap because different specializations
 890       // have different members.
 891       this->_M_swap(__x);
 892
 893       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 894       // 431. Swapping containers with unequal allocators.
 895       std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
 896                                                         __x._M_node_allocator);
 897
 898       std::swap(_M_rehash_policy, __x._M_rehash_policy);
 899       std::swap(_M_buckets, __x._M_buckets);
 900       std::swap(_M_bucket_count, __x._M_bucket_count);
 901       std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
 902       std::swap(_M_element_count, __x._M_element_count);
 903       // Fix buckets containing the _M_before_begin pointers that can't be
 904       // swapped.
 905       if (_M_begin())
 906         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
 907       if (__x._M_begin())
 908         __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
 909           = &(__x._M_before_begin);
 910     }
 911
 912   template<typename _Key, typename _Value,
 913            typename _Allocator, typename _ExtractKey, typename _Equal,
 914            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 915            bool __chc, bool __cit, bool __uk>
 916     void
 917     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 918                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 919     __rehash_policy(const _RehashPolicy& __pol)
 920     {
 921       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
 922       if (__n_bkt != _M_bucket_count)
 923         _M_rehash(__n_bkt, _M_rehash_policy._M_state());
 924       _M_rehash_policy = __pol;
 925     }
 926
 927   template<typename _Key, typename _Value,
 928            typename _Allocator, typename _ExtractKey, typename _Equal,
 929            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 930            bool __chc, bool __cit, bool __uk>
 931     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 932                         _H1, _H2, _Hash, _RehashPolicy,
 933                         __chc, __cit, __uk>::iterator
 934     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 935                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 936     find(const key_type& __k)
 937     {
 938       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 939       std::size_t __n = _M_bucket_index(__k, __code);
 940       _Node* __p = _M_find_node(__n, __k, __code);
 941       return __p ? iterator(__p) : this->end();
 942     }
 943
 944   template<typename _Key, typename _Value,
 945            typename _Allocator, typename _ExtractKey, typename _Equal,
 946            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 947            bool __chc, bool __cit, bool __uk>
 948     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 949                         _H1, _H2, _Hash, _RehashPolicy,
 950                         __chc, __cit, __uk>::const_iterator
 951     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 952                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 953     find(const key_type& __k) const
 954     {
 955       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 956       std::size_t __n = _M_bucket_index(__k, __code);
 957       _Node* __p = _M_find_node(__n, __k, __code);
 958       return __p ? const_iterator(__p) : this->end();
 959     }
 960
 961   template<typename _Key, typename _Value,
 962            typename _Allocator, typename _ExtractKey, typename _Equal,
 963            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 964            bool __chc, bool __cit, bool __uk>
 965     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 966                         _H1, _H2, _Hash, _RehashPolicy,
 967                         __chc, __cit, __uk>::size_type
 968     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 969                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 970     count(const key_type& __k) const
 971     {
 972       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 973       std::size_t __n = _M_bucket_index(__k, __code);
 974       _Node* __p = _M_bucket_begin(__n);
 975       if (!__p)
 976         return 0;
 977
 978       std::size_t __result = 0;
 979       for (;; __p = __p->_M_next())
 980         {
 981           if (this->_M_equals(__k, __code, __p))
 982             ++__result;
 983           else if (__result)
 984             // All equivalent values are next to each other, if we found a not
 985             // equivalent value after an equivalent one it means that we won't
 986             // find any more equivalent values.
 987             break;
 988           if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
 989             break;
 990         }
 991       return __result;
 992     }
 993
 994   template<typename _Key, typename _Value,
 995            typename _Allocator, typename _ExtractKey, typename _Equal,
 996            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 997            bool __chc, bool __cit, bool __uk>
 998     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
 999                                   _ExtractKey, _Equal, _H1,
1000                                   _H2, _Hash, _RehashPolicy,
1001                                   __chc, __cit, __uk>::iterator,
1002               typename _Hashtable<_Key, _Value, _Allocator,
1003                                   _ExtractKey, _Equal, _H1,
1004                                   _H2, _Hash, _RehashPolicy,
1005                                   __chc, __cit, __uk>::iterator>
1006     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1007                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1008     equal_range(const key_type& __k)
1009     {
1010       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1011       std::size_t __n = _M_bucket_index(__k, __code);
1012       _Node* __p = _M_find_node(__n, __k, __code);
1013
1014       if (__p)
1015         {
1016           _Node* __p1 = __p->_M_next();
1017           while (__p1 && _M_bucket_index(__p1) == __n
1018                  && this->_M_equals(__k, __code, __p1))
1019             __p1 = __p1->_M_next();
1020
1021           return std::make_pair(iterator(__p), iterator(__p1));
1022         }
1023       else
1024         return std::make_pair(this->end(), this->end());
1025     }
1026
1027   template<typename _Key, typename _Value,
1028            typename _Allocator, typename _ExtractKey, typename _Equal,
1029            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1030            bool __chc, bool __cit, bool __uk>
1031     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1032                                   _ExtractKey, _Equal, _H1,
1033                                   _H2, _Hash, _RehashPolicy,
1034                                   __chc, __cit, __uk>::const_iterator,
1035               typename _Hashtable<_Key, _Value, _Allocator,
1036                                   _ExtractKey, _Equal, _H1,
1037                                   _H2, _Hash, _RehashPolicy,
1038                                   __chc, __cit, __uk>::const_iterator>
1039     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1040                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1041     equal_range(const key_type& __k) const
1042     {
1043       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1044       std::size_t __n = _M_bucket_index(__k, __code);
1045       _Node* __p = _M_find_node(__n, __k, __code);
1046
1047       if (__p)
1048         {
1049           _Node* __p1 = __p->_M_next();
1050           while (__p1 && _M_bucket_index(__p1) == __n
1051                  && this->_M_equals(__k, __code, __p1))
1052             __p1 = __p1->_M_next();
1053
1054           return std::make_pair(const_iterator(__p), const_iterator(__p1));
1055         }
1056       else
1057         return std::make_pair(this->end(), this->end());
1058     }
1059
1060   // Find the node whose key compares equal to k in the bucket n. Return nullptr
1061   // if no node is found.
1062   template<typename _Key, typename _Value,
1063            typename _Allocator, typename _ExtractKey, typename _Equal,
1064            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1065            bool __chc, bool __cit, bool __uk>
1066     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1067                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
1068                         __chc, __cit, __uk>::_BaseNode*
1069     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1070                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1071     _M_find_before_node(size_type __n, const key_type& __k,
1072                         typename _Hashtable::_Hash_code_type __code) const
1073     {
1074       _BaseNode* __prev_p = _M_buckets[__n];
1075       if (!__prev_p)
1076         return nullptr;
1077       _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);
1078       for (;; __p = __p->_M_next())
1079         {
1080           if (this->_M_equals(__k, __code, __p))
1081             return __prev_p;
1082           if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
1083             break;
1084           __prev_p = __p;
1085         }
1086       return nullptr;
1087     }
1088
1089   template<typename _Key, typename _Value,
1090            typename _Allocator, typename _ExtractKey, typename _Equal,
1091            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1092            bool __chc, bool __cit, bool __uk>
1093     void
1094     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1095                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1096     _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
1097     {
1098       if (_M_buckets[__bkt])
1099         {
1100           // Bucket is not empty, we just need to insert the new node after the
1101           // bucket before begin.
1102           __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1103           _M_buckets[__bkt]->_M_nxt = __new_node;
1104         }
1105       else
1106         {
1107           // The bucket is empty, the new node is inserted at the beginning of
1108           // the singly-linked list and the bucket will contain _M_before_begin
1109           // pointer.
1110           __new_node->_M_nxt = _M_before_begin._M_nxt;
1111           _M_before_begin._M_nxt = __new_node;
1112           if (__new_node->_M_nxt)
1113             // We must update former begin bucket that is pointing to
1114             // _M_before_begin.
1115             _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
1116           _M_buckets[__bkt] = &_M_before_begin;
1117         }
1118     }
1119
1120   template<typename _Key, typename _Value,
1121            typename _Allocator, typename _ExtractKey, typename _Equal,
1122            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1123            bool __chc, bool __cit, bool __uk>
1124     void
1125     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1126                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1127     _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt)
1128     {
1129       if (!__next || __next_bkt != __bkt)
1130         {
1131           // Bucket is now empty
1132           // First update next bucket if any
1133           if (__next)
1134             _M_buckets[__next_bkt] = _M_buckets[__bkt];
1135           // Second update before begin node if necessary
1136           if (&_M_before_begin == _M_buckets[__bkt])
1137             _M_before_begin._M_nxt = __next;
1138           _M_buckets[__bkt] = nullptr;
1139         }
1140     }
1141
1142   template<typename _Key, typename _Value,
1143            typename _Allocator, typename _ExtractKey, typename _Equal,
1144            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1145            bool __chc, bool __cit, bool __uk>
1146     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1147                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
1148                         __chc, __cit, __uk>::_BaseNode*
1149     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1150                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1151     _M_get_previous_node(size_type __bkt, _BaseNode* __n)
1152     {
1153       _BaseNode* __prev_n = _M_buckets[__bkt];
1154       while (__prev_n->_M_nxt != __n)
1155         __prev_n = __prev_n->_M_nxt;
1156       return __prev_n;
1157     }
1158
1159   template<typename _Key, typename _Value,
1160            typename _Allocator, typename _ExtractKey, typename _Equal,
1161            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1162            bool __chc, bool __cit, bool __uk>
1163     template<typename... _Args>
1164       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1165                                     _ExtractKey, _Equal, _H1,
1166                                     _H2, _Hash, _RehashPolicy,
1167                                     __chc, __cit, __uk>::iterator, bool>
1168       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1169                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1170       _M_emplace(std::true_type, _Args&&... __args)
1171       {
1172         // First build the node to get access to the hash code
1173         _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1174         __try
1175           {
1176             const key_type& __k = this->_M_extract()(__new_node->_M_v);
1177             typename _Hashtable::_Hash_code_type __code
1178               = this->_M_hash_code(__k);
1179             size_type __bkt = _M_bucket_index(__k, __code);
1180
1181             if (_Node* __p = _M_find_node(__bkt, __k, __code))
1182               {
1183                 // There is already an equivalent node, no insertion
1184                 _M_deallocate_node(__new_node);
1185                 return std::make_pair(iterator(__p), false);
1186               }
1187
1188             // We are going to insert this node
1189             this->_M_store_code(__new_node, __code);
1190             const _RehashPolicyState& __saved_state
1191               = _M_rehash_policy._M_state();
1192             std::pair<bool, std::size_t> __do_rehash
1193               = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1194                                                 _M_element_count, 1);
1195
1196             if (__do_rehash.first)
1197               {
1198                 _M_rehash(__do_rehash.second, __saved_state);
1199                 __bkt = _M_bucket_index(__k, __code);
1200               }
1201
1202             _M_insert_bucket_begin(__bkt, __new_node);
1203             ++_M_element_count;
1204             return std::make_pair(iterator(__new_node), true);
1205           }
1206         __catch(...)
1207           {
1208             _M_deallocate_node(__new_node);
1209             __throw_exception_again;
1210           }
1211       }
1212
1213   template<typename _Key, typename _Value,
1214            typename _Allocator, typename _ExtractKey, typename _Equal,
1215            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1216            bool __chc, bool __cit, bool __uk>
1217     template<typename... _Args>
1218       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1219                           _H1, _H2, _Hash, _RehashPolicy,
1220                           __chc, __cit, __uk>::iterator
1221       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1222                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1223       _M_emplace(std::false_type, _Args&&... __args)
1224       {
1225         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1226         std::pair<bool, std::size_t> __do_rehash
1227           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1228                                             _M_element_count, 1);
1229
1230         // First build the node to get its hash code.
1231         _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1232         __try
1233           {
1234             const key_type& __k = this->_M_extract()(__new_node->_M_v);
1235             typename _Hashtable::_Hash_code_type __code
1236               = this->_M_hash_code(__k);
1237             this->_M_store_code(__new_node, __code);
1238
1239             // Second, do rehash if necessary.
1240             if (__do_rehash.first)
1241                 _M_rehash(__do_rehash.second, __saved_state);
1242
1243             // Third, find the node before an equivalent one.
1244             size_type __bkt = _M_bucket_index(__k, __code);
1245             _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code);
1246
1247             if (__prev)
1248               {
1249                 // Insert after the node before the equivalent one.
1250                 __new_node->_M_nxt = __prev->_M_nxt;
1251                 __prev->_M_nxt = __new_node;
1252               }
1253             else
1254               // The inserted node has no equivalent in the hashtable. We must
1255               // insert the new node at the beginning of the bucket to preserve
1256               // equivalent elements' relative positions.
1257               _M_insert_bucket_begin(__bkt, __new_node);
1258             ++_M_element_count;
1259             return iterator(__new_node);
1260           }
1261         __catch(...)
1262           {
1263             _M_deallocate_node(__new_node);
1264             __throw_exception_again;
1265           }
1266       }
1267
1268   // Insert v in bucket n (assumes no element with its key already present).
1269   template<typename _Key, typename _Value,
1270            typename _Allocator, typename _ExtractKey, typename _Equal,
1271            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1272            bool __chc, bool __cit, bool __uk>
1273     template<typename _Arg>
1274       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1275                           _H1, _H2, _Hash, _RehashPolicy,
1276                           __chc, __cit, __uk>::iterator
1277       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1278                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1279       _M_insert_bucket(_Arg&& __v, size_type __n,
1280                        typename _Hashtable::_Hash_code_type __code)
1281       {
1282         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1283         std::pair<bool, std::size_t> __do_rehash
1284           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1285                                             _M_element_count, 1);
1286
1287         if (__do_rehash.first)
1288           {
1289             const key_type& __k = this->_M_extract()(__v);
1290             __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
1291           }
1292
1293         _Node* __new_node = nullptr;
1294         __try
1295           {
1296             // Allocate the new node before doing the rehash so that we
1297             // don't do a rehash if the allocation throws.
1298             __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1299             this->_M_store_code(__new_node, __code);
1300             if (__do_rehash.first)
1301               _M_rehash(__do_rehash.second, __saved_state);
1302
1303             _M_insert_bucket_begin(__n, __new_node);
1304             ++_M_element_count;
1305             return iterator(__new_node);
1306           }
1307         __catch(...)
1308           {
1309             if (!__new_node)
1310               _M_rehash_policy._M_reset(__saved_state);
1311             else
1312               _M_deallocate_node(__new_node);
1313             __throw_exception_again;
1314           }
1315       }
1316
1317   // Insert v if no element with its key is already present.
1318   template<typename _Key, typename _Value,
1319            typename _Allocator, typename _ExtractKey, typename _Equal,
1320            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1321            bool __chc, bool __cit, bool __uk>
1322     template<typename _Arg>
1323       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1324                                     _ExtractKey, _Equal, _H1,
1325                                     _H2, _Hash, _RehashPolicy,
1326                                     __chc, __cit, __uk>::iterator, bool>
1327       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1328                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1329       _M_insert(_Arg&& __v, std::true_type)
1330       {
1331         const key_type& __k = this->_M_extract()(__v);
1332         typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1333         size_type __n = _M_bucket_index(__k, __code);
1334
1335         if (_Node* __p = _M_find_node(__n, __k, __code))
1336           return std::make_pair(iterator(__p), false);
1337         return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
1338                               __n, __code), true);
1339       }
1340
1341   // Insert v unconditionally.
1342   template<typename _Key, typename _Value,
1343            typename _Allocator, typename _ExtractKey, typename _Equal,
1344            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1345            bool __chc, bool __cit, bool __uk>
1346     template<typename _Arg>
1347       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1348                           _H1, _H2, _Hash, _RehashPolicy,
1349                           __chc, __cit, __uk>::iterator
1350       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1351                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1352       _M_insert(_Arg&& __v, std::false_type)
1353       {
1354         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1355         std::pair<bool, std::size_t> __do_rehash
1356           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1357                                             _M_element_count, 1);
1358
1359         // First compute the hash code so that we don't do anything if it throws.
1360         typename _Hashtable::_Hash_code_type __code
1361           = this->_M_hash_code(this->_M_extract()(__v));
1362
1363         _Node* __new_node = nullptr;
1364         __try
1365           {
1366             // Second allocate new node so that we don't rehash if it throws.
1367             __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1368             this->_M_store_code(__new_node, __code);
1369             if (__do_rehash.first)
1370                 _M_rehash(__do_rehash.second, __saved_state);
1371
1372             // Third, find the node before an equivalent one.
1373             size_type __bkt = _M_bucket_index(__new_node);
1374             _BaseNode* __prev
1375               = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v),
1376                                     __code);
1377             if (__prev)
1378               {
1379                 // Insert after the node before the equivalent one.
1380                 __new_node->_M_nxt = __prev->_M_nxt;
1381                 __prev->_M_nxt = __new_node;
1382               }
1383             else
1384               // The inserted node has no equivalent in the hashtable. We must
1385               // insert the new node at the beginning of the bucket to preserve
1386               // equivalent elements relative positions.
1387               _M_insert_bucket_begin(__bkt, __new_node);
1388             ++_M_element_count;
1389             return iterator(__new_node);
1390           }
1391         __catch(...)
1392           {
1393             if (!__new_node)
1394               _M_rehash_policy._M_reset(__saved_state);
1395             else
1396               _M_deallocate_node(__new_node);
1397             __throw_exception_again;
1398           }
1399       }
1400
1401   template<typename _Key, typename _Value,
1402            typename _Allocator, typename _ExtractKey, typename _Equal,
1403            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1404            bool __chc, bool __cit, bool __uk>
1405     template<typename _InputIterator>
1406       void
1407       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1408                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1409       insert(_InputIterator __first, _InputIterator __last)
1410       {
1411         size_type __n_elt = __detail::__distance_fw(__first, __last);
1412         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1413         std::pair<bool, std::size_t> __do_rehash
1414           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1415                                             _M_element_count, __n_elt);
1416         if (__do_rehash.first)
1417           _M_rehash(__do_rehash.second, __saved_state);
1418
1419         for (; __first != __last; ++__first)
1420           this->insert(*__first);
1421       }
1422
1423   template<typename _Key, typename _Value,
1424            typename _Allocator, typename _ExtractKey, typename _Equal,
1425            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1426            bool __chc, bool __cit, bool __uk>
1427     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1428                         _H1, _H2, _Hash, _RehashPolicy,
1429                         __chc, __cit, __uk>::iterator
1430     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1431                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1432     erase(const_iterator __it)
1433     {
1434       _Node* __n = __it._M_cur;
1435       std::size_t __bkt = _M_bucket_index(__n);
1436
1437       // Look for previous node to unlink it from the erased one, this is why
1438       // we need buckets to contain the before begin to make this search fast.
1439       _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1440       if (__n == _M_bucket_begin(__bkt))
1441         _M_remove_bucket_begin(__bkt, __n->_M_next(),
1442            __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1443       else if (__n->_M_nxt)
1444         {
1445           size_type __next_bkt = _M_bucket_index(__n->_M_next());
1446           if (__next_bkt != __bkt)
1447             _M_buckets[__next_bkt] = __prev_n;
1448         }
1449
1450       __prev_n->_M_nxt = __n->_M_nxt;
1451       iterator __result(__n->_M_next());
1452       _M_deallocate_node(__n);
1453       --_M_element_count;
1454
1455       return __result;
1456     }
1457
1458   template<typename _Key, typename _Value,
1459            typename _Allocator, typename _ExtractKey, typename _Equal,
1460            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1461            bool __chc, bool __cit, bool __uk>
1462     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1463                         _H1, _H2, _Hash, _RehashPolicy,
1464                         __chc, __cit, __uk>::size_type
1465     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1466                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1467     erase(const key_type& __k)
1468     {
1469       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1470       std::size_t __bkt = _M_bucket_index(__k, __code);
1471       // Look for the node before the first matching node.
1472       _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code);
1473       if (!__prev_n)
1474         return 0;
1475       _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt);
1476       bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
1477
1478       // We found a matching node, start deallocation loop from it
1479       std::size_t __next_bkt = __bkt;
1480       _Node* __next_n = __n;
1481       size_type __result = 0;
1482       _Node* __saved_n = nullptr;
1483       do
1484         {
1485           _Node* __p = __next_n;
1486           __next_n = __p->_M_next();
1487           // _GLIBCXX_RESOLVE_LIB_DEFECTS
1488           // 526. Is it undefined if a function in the standard changes
1489           // in parameters?
1490           if (std::__addressof(this->_M_extract()(__p->_M_v))
1491               != std::__addressof(__k))
1492             _M_deallocate_node(__p);
1493           else
1494             __saved_n = __p;
1495           --_M_element_count;
1496           ++__result;
1497           if (!__next_n)
1498             break;
1499           __next_bkt = _M_bucket_index(__next_n);
1500         }
1501       while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
1502
1503       if (__saved_n)
1504         _M_deallocate_node(__saved_n);
1505       if (__is_bucket_begin)
1506         _M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
1507       else if (__next_n && __next_bkt != __bkt)
1508         _M_buckets[__next_bkt] = __prev_n;
1509       if (__prev_n)
1510         __prev_n->_M_nxt = __next_n;
1511       return __result;
1512     }
1513
1514   template<typename _Key, typename _Value,
1515            typename _Allocator, typename _ExtractKey, typename _Equal,
1516            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1517            bool __chc, bool __cit, bool __uk>
1518     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1519                         _H1, _H2, _Hash, _RehashPolicy,
1520                         __chc, __cit, __uk>::iterator
1521     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1522                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1523     erase(const_iterator __first, const_iterator __last)
1524     {
1525       _Node* __n = __first._M_cur;
1526       _Node* __last_n = __last._M_cur;
1527       if (__n == __last_n)
1528         return iterator(__n);
1529
1530       std::size_t __bkt = _M_bucket_index(__n);
1531
1532       _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1533       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1534       std::size_t __n_bkt = __bkt;
1535       for (;;)
1536         {
1537           do
1538             {
1539               _Node* __tmp = __n;
1540               __n = __n->_M_next();
1541               _M_deallocate_node(__tmp);
1542               --_M_element_count;
1543               if (!__n)
1544                 break;
1545               __n_bkt = _M_bucket_index(__n);
1546             }
1547           while (__n != __last_n && __n_bkt == __bkt);
1548           if (__is_bucket_begin)
1549             _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1550           if (__n == __last_n)
1551             break;
1552           __is_bucket_begin = true;
1553           __bkt = __n_bkt;
1554         }
1555
1556       if (__n && (__n_bkt != __bkt || __is_bucket_begin))
1557         _M_buckets[__n_bkt] = __prev_n;
1558       __prev_n->_M_nxt = __n;
1559       return iterator(__n);
1560     }
1561
1562   template<typename _Key, typename _Value,
1563            typename _Allocator, typename _ExtractKey, typename _Equal,
1564            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1565            bool __chc, bool __cit, bool __uk>
1566     void
1567     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1568                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1569     clear() noexcept
1570     {
1571       _M_deallocate_nodes(_M_begin());
1572       __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
1573       _M_element_count = 0;
1574       _M_before_begin._M_nxt = nullptr;
1575     }
1576
1577   template<typename _Key, typename _Value,
1578            typename _Allocator, typename _ExtractKey, typename _Equal,
1579            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1580            bool __chc, bool __cit, bool __uk>
1581     void
1582     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1583                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1584     rehash(size_type __n)
1585     {
1586       const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1587       std::size_t __buckets
1588         = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1);
1589       if (__buckets <= __n)
1590         __buckets = _M_rehash_policy._M_next_bkt(__n);
1591
1592       if (__buckets != _M_bucket_count)
1593         {
1594           _M_rehash(__buckets, __saved_state);
1595
1596           // We don't want the rehash policy to ask for the hashtable to shrink
1597           // on the next insertion so we need to reset its previous resize
1598           // level.
1599           _M_rehash_policy._M_prev_resize = 0;
1600         }
1601       else
1602         // No rehash, restore previous state to keep a consistent state.
1603         _M_rehash_policy._M_reset(__saved_state);
1604     }
1605
1606   template<typename _Key, typename _Value,
1607            typename _Allocator, typename _ExtractKey, typename _Equal,
1608            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1609            bool __chc, bool __cit, bool __uk>
1610     void
1611     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1612                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1613     _M_rehash(size_type __n, const _RehashPolicyState& __state)
1614     {
1615       __try
1616         {
1617           _M_rehash_aux(__n, integral_constant<bool, __uk>());
1618         }
1619       __catch(...)
1620         {
1621           // A failure here means that buckets allocation failed.  We only
1622           // have to restore hash policy previous state.
1623           _M_rehash_policy._M_reset(__state);
1624           __throw_exception_again;
1625         }
1626     }
1627
1628   // Rehash when there is no equivalent elements.
1629   template<typename _Key, typename _Value,
1630            typename _Allocator, typename _ExtractKey, typename _Equal,
1631            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1632            bool __chc, bool __cit, bool __uk>
1633     void
1634     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1635                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1636     _M_rehash_aux(size_type __n, std::true_type)
1637     {
1638       _Bucket* __new_buckets = _M_allocate_buckets(__n);
1639       _Node* __p = _M_begin();
1640       _M_before_begin._M_nxt = nullptr;
1641       std::size_t __bbegin_bkt = 0;
1642       while (__p)
1643         {
1644           _Node* __next = __p->_M_next();
1645           std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1646           if (!__new_buckets[__bkt])
1647             {
1648               __p->_M_nxt = _M_before_begin._M_nxt;
1649               _M_before_begin._M_nxt = __p;
1650               __new_buckets[__bkt] = &_M_before_begin;
1651               if (__p->_M_nxt)
1652                 __new_buckets[__bbegin_bkt] = __p;
1653               __bbegin_bkt = __bkt;
1654             }
1655           else
1656             {
1657               __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1658               __new_buckets[__bkt]->_M_nxt = __p;
1659             }
1660           __p = __next;
1661         }
1662       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1663       _M_bucket_count = __n;
1664       _M_buckets = __new_buckets;
1665     }
1666
1667   // Rehash when there can be equivalent elements, preserve their relative
1668   // order.
1669   template<typename _Key, typename _Value,
1670            typename _Allocator, typename _ExtractKey, typename _Equal,
1671            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1672            bool __chc, bool __cit, bool __uk>
1673     void
1674     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1675                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1676     _M_rehash_aux(size_type __n, std::false_type)
1677     {
1678       _Bucket* __new_buckets = _M_allocate_buckets(__n);
1679
1680       _Node* __p = _M_begin();
1681       _M_before_begin._M_nxt = nullptr;
1682       std::size_t __bbegin_bkt = 0;
1683       std::size_t __prev_bkt = 0;
1684       _Node* __prev_p = nullptr;
1685       bool __check_bucket = false;
1686
1687       while (__p)
1688         {
1689           _Node* __next = __p->_M_next();
1690           std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1691
1692           if (__prev_p && __prev_bkt == __bkt)
1693             {
1694               // Previous insert was already in this bucket, we insert after
1695               // the previously inserted one to preserve equivalent elements
1696               // relative order.
1697               __p->_M_nxt = __prev_p->_M_nxt;
1698               __prev_p->_M_nxt = __p;
1699
1700               // Inserting after a node in a bucket require to check that we
1701               // haven't change the bucket last node, in this case next
1702               // bucket containing its before begin node must be updated. We
1703               // schedule a check as soon as we move out of the sequence of
1704               // equivalent nodes to limit the number of checks.
1705               __check_bucket = true;
1706             }
1707           else
1708             {
1709               if (__check_bucket)
1710                 {
1711                   // Check if we shall update the next bucket because of
1712                   // insertions into __prev_bkt bucket.
1713                   if (__prev_p->_M_nxt)
1714                     {
1715                       std::size_t __next_bkt
1716                         = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1717                       if (__next_bkt != __prev_bkt)
1718                         __new_buckets[__next_bkt] = __prev_p;
1719                     }
1720                   __check_bucket = false;
1721                 }
1722               if (!__new_buckets[__bkt])
1723                 {
1724                   __p->_M_nxt = _M_before_begin._M_nxt;
1725                   _M_before_begin._M_nxt = __p;
1726                   __new_buckets[__bkt] = &_M_before_begin;
1727                   if (__p->_M_nxt)
1728                     __new_buckets[__bbegin_bkt] = __p;
1729                   __bbegin_bkt = __bkt;
1730                 }
1731               else
1732                 {
1733                   __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1734                   __new_buckets[__bkt]->_M_nxt = __p;
1735                 }
1736             }
1737
1738           __prev_p = __p;
1739           __prev_bkt = __bkt;
1740           __p = __next;
1741         }
1742
1743       if (__check_bucket && __prev_p->_M_nxt)
1744         {
1745           std::size_t __next_bkt
1746             = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1747           if (__next_bkt != __prev_bkt)
1748             __new_buckets[__next_bkt] = __prev_p;
1749         }
1750
1751       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1752       _M_bucket_count = __n;
1753       _M_buckets = __new_buckets;
1754     }
1755
1756 _GLIBCXX_END_NAMESPACE_VERSION
1757 } // namespace std
1758
1759 #endif // _HASHTABLE_H