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

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