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

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