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    * - size_type     _M_bucket_count
  98    * - size_type     _M_begin_bucket_index
  99    * - size_type     _M_element_count
 100    *
 101    * with _Bucket being _Node* and _Node:
 102    * - _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 first non-empty bucket with index _M_begin_bucket_index contains the
 111    * first container node which is also the first bucket node whereas other
 112    * non-empty buckets contain the node before the first bucket node. This is so
 113    * to implement something like a std::forward_list::erase_after on container
 114    * erase calls.
 115    *
 116    * Access to the bucket last element require a check on the hash code to see
 117    * if the node is still in the bucket. Such a design impose a quite efficient
 118    * hash functor and is one of the reasons it is highly advise to set
 119    * __cache_hash_code to true.
 120    *
 121    * The container iterators are simply built from nodes. This way incrementing
 122    * the iterator is perfectly efficient no matter how many empty buckets there
 123    * are in the container.
 124    *
 125    * On insert we compute element hash code and thanks to it find the bucket
 126    * index. If the element is the first one in the bucket we must find the
 127    * previous non-empty bucket where the previous node rely. To keep this loop
 128    * minimal it is important that the number of bucket is not too high compared
 129    * to the number of elements. So the hash policy must be carefully design so
 130    * that it computes a bucket count large enough to respect the user defined
 131    * load factor but also not too large to limit impact on the insert operation.
 132    *
 133    * On erase, the simple iterator design impose to use the hash functor to get
 134    * the index of the bucket to update. For this reason, when __cache_hash_code
 135    * is set to false, there is a static assertion that the hash functor cannot
 136    * throw.
 137    *
 138    * _M_begin_bucket_index is used to offer contant time access to the container
 139    * begin iterator.
 140    */
 141
 142   template<typename _Key, typename _Value, typename _Allocator,
 143            typename _ExtractKey, typename _Equal,
 144            typename _H1, typename _H2, typename _Hash,
 145            typename _RehashPolicy,
 146            bool __cache_hash_code,
 147            bool __constant_iterators,
 148            bool __unique_keys>
 149     class _Hashtable
 150     : public __detail::_Rehash_base<_RehashPolicy,
 151                                     _Hashtable<_Key, _Value, _Allocator,
 152                                                _ExtractKey,
 153                                                _Equal, _H1, _H2, _Hash,
 154                                                _RehashPolicy,
 155                                                __cache_hash_code,
 156                                                __constant_iterators,
 157                                                __unique_keys> >,
 158       public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 159                                        _H1, _H2, _Hash, __cache_hash_code>,
 160       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
 161                                  _Hashtable<_Key, _Value, _Allocator,
 162                                             _ExtractKey,
 163                                             _Equal, _H1, _H2, _Hash,
 164                                             _RehashPolicy,
 165                                             __cache_hash_code,
 166                                             __constant_iterators,
 167                                             __unique_keys> >,
 168       public __detail::_Equality_base<_ExtractKey, __unique_keys,
 169                                       _Hashtable<_Key, _Value, _Allocator,
 170                                                  _ExtractKey,
 171                                                  _Equal, _H1, _H2, _Hash,
 172                                                  _RehashPolicy,
 173                                                  __cache_hash_code,
 174                                                  __constant_iterators,
 175                                                  __unique_keys> >
 176     {
 177       template<typename _Cond>
 178         using __if_hash_code_cached
 179           = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
 180
 181       template<typename _Cond>
 182         using __if_hash_code_not_cached
 183           = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
 184
 185       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 _Node* _Bucket;
 250       typedef typename _Allocator::template rebind<_Bucket>::other
 251                                                         _Bucket_allocator_type;
 252
 253       typedef typename _Allocator::template rebind<_Value>::other
 254                                                         _Value_allocator_type;
 255
 256       _Node_allocator_type   _M_node_allocator;
 257       _Bucket*               _M_buckets;
 258       size_type              _M_bucket_count;
 259       size_type              _M_begin_bucket_index; // First non-empty bucket.
 260       size_type              _M_element_count;
 261       _RehashPolicy          _M_rehash_policy;
 262
 263       template<typename... _Args>
 264         _Node*
 265         _M_allocate_node(_Args&&... __args);
 266
 267       void
 268       _M_deallocate_node(_Node* __n);
 269
 270       // Deallocate the linked list of nodes pointed to by __n
 271       void
 272       _M_deallocate_nodes(_Node* __n);
 273
 274       _Bucket*
 275       _M_allocate_buckets(size_type __n);
 276
 277       void
 278       _M_deallocate_buckets(_Bucket*, size_type __n);
 279
 280       // Gets bucket begin dealing with the difference between first non-empty
 281       // bucket containing the first container node and the other non-empty
 282       // buckets containing the node before the one belonging to the bucket.
 283       _Node*
 284       _M_bucket_begin(size_type __bkt) const;
 285
 286       // Gets the bucket last node if any
 287       _Node*
 288       _M_bucket_end(size_type __bkt) const;
 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_buckets[_M_begin_bucket_index]); }
 334
 335       const_iterator
 336       begin() const noexcept
 337       { return const_iterator(_M_buckets[_M_begin_bucket_index]); }
 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_buckets[_M_begin_bucket_index]); }
 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       size_type
 458       _M_bucket_index(_Node* __n) const
 459       { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
 460
 461       size_type
 462       _M_bucket_index(const key_type& __k,
 463                       typename _Hashtable::_Hash_code_type __c) const
 464       { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
 465
 466       // Find and insert helper functions and types
 467       _Node*
 468       _M_find_node(size_type, const key_type&,
 469                    typename _Hashtable::_Hash_code_type) const;
 470
 471       // Insert a node in an empty bucket
 472       void
 473       _M_insert_bucket_begin(size_type, _Node*);
 474
 475       // Insert a node after an other one in a non-empty bucket
 476       void
 477       _M_insert_after(size_type, _Node*, _Node*);
 478
 479       // Remove the bucket first node
 480       void
 481       _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
 482                              size_type __next_bkt);
 483
 484       // Get the node before __n in the bucket __bkt
 485       _Node*
 486       _M_get_previous_node(size_type __bkt, _Node* __n);
 487
 488       template<typename _Arg>
 489         iterator
 490         _M_insert_bucket(_Arg&&, size_type,
 491                          typename _Hashtable::_Hash_code_type);
 492
 493       typedef typename std::conditional<__unique_keys,
 494                                         std::pair<iterator, bool>,
 495                                         iterator>::type
 496         _Insert_Return_Type;
 497
 498       typedef typename std::conditional<__unique_keys,
 499                                         std::_Select1st<_Insert_Return_Type>,
 500                                         std::_Identity<_Insert_Return_Type>
 501                                    >::type
 502         _Insert_Conv_Type;
 503
 504     protected:
 505       template<typename... _Args>
 506         std::pair<iterator, bool>
 507         _M_emplace(std::true_type, _Args&&... __args);
 508
 509       template<typename... _Args>
 510         iterator
 511         _M_emplace(std::false_type, _Args&&... __args);
 512
 513       template<typename _Arg>
 514         std::pair<iterator, bool>
 515         _M_insert(_Arg&&, std::true_type);
 516
 517       template<typename _Arg>
 518         iterator
 519         _M_insert(_Arg&&, std::false_type);
 520
 521     public:
 522       // Emplace, insert and erase
 523       template<typename... _Args>
 524         _Insert_Return_Type
 525         emplace(_Args&&... __args)
 526         { return _M_emplace(integral_constant<bool, __unique_keys>(),
 527                             std::forward<_Args>(__args)...); }
 528
 529       template<typename... _Args>
 530         iterator
 531         emplace_hint(const_iterator, _Args&&... __args)
 532         { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
 533
 534       _Insert_Return_Type
 535       insert(const value_type& __v)
 536       { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
 537
 538       iterator
 539       insert(const_iterator, const value_type& __v)
 540       { return _Insert_Conv_Type()(insert(__v)); }
 541
 542       template<typename _Pair, typename = typename
 543         std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
 544                               std::is_convertible<_Pair,
 545                                                   value_type>>::value>::type>
 546         _Insert_Return_Type
 547         insert(_Pair&& __v)
 548         { return _M_insert(std::forward<_Pair>(__v),
 549                            integral_constant<bool, __unique_keys>()); }
 550
 551       template<typename _Pair, typename = typename
 552         std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
 553                               std::is_convertible<_Pair,
 554                                                   value_type>>::value>::type>
 555         iterator
 556         insert(const_iterator, _Pair&& __v)
 557         { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
 558
 559       template<typename _InputIterator>
 560         void
 561         insert(_InputIterator __first, _InputIterator __last);
 562
 563       void
 564       insert(initializer_list<value_type> __l)
 565       { this->insert(__l.begin(), __l.end()); }
 566
 567       iterator
 568       erase(const_iterator);
 569
 570       // LWG 2059.
 571       iterator
 572       erase(iterator __it)
 573       { return erase(const_iterator(__it)); }
 574
 575       size_type
 576       erase(const key_type&);
 577
 578       iterator
 579       erase(const_iterator, const_iterator);
 580
 581       void
 582       clear() noexcept;
 583
 584       // Set number of buckets to be appropriate for container of n element.
 585       void rehash(size_type __n);
 586
 587       // DR 1189.
 588       // reserve, if present, comes from _Rehash_base.
 589
 590     private:
 591       // Unconditionally change size of bucket array to n, restore hash policy
 592       // state to __state on exception.
 593       void _M_rehash(size_type __n, const _RehashPolicyState& __state);
 594     };
 595
 596
 597   // Definitions of class template _Hashtable's out-of-line member functions.
 598   template<typename _Key, typename _Value,
 599            typename _Allocator, typename _ExtractKey, typename _Equal,
 600            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 601            bool __chc, bool __cit, bool __uk>
 602     template<typename... _Args>
 603       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 604                           _H1, _H2, _Hash, _RehashPolicy,
 605                           __chc, __cit, __uk>::_Node*
 606       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 607                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 608       _M_allocate_node(_Args&&... __args)
 609       {
 610         _Node* __n = _M_node_allocator.allocate(1);
 611         __try
 612           {
 613             _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
 614             return __n;
 615           }
 616         __catch(...)
 617           {
 618             _M_node_allocator.deallocate(__n, 1);
 619             __throw_exception_again;
 620           }
 621       }
 622
 623   template<typename _Key, typename _Value,
 624            typename _Allocator, typename _ExtractKey, typename _Equal,
 625            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 626            bool __chc, bool __cit, bool __uk>
 627     void
 628     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 629                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 630     _M_deallocate_node(_Node* __n)
 631     {
 632       _M_node_allocator.destroy(__n);
 633       _M_node_allocator.deallocate(__n, 1);
 634     }
 635
 636   template<typename _Key, typename _Value,
 637            typename _Allocator, typename _ExtractKey, typename _Equal,
 638            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 639            bool __chc, bool __cit, bool __uk>
 640     void
 641     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 642                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 643     _M_deallocate_nodes(_Node* __n)
 644     {
 645       while (__n)
 646         {
 647           _Node* __tmp = __n;
 648           __n = __n->_M_next;
 649           _M_deallocate_node(__tmp);
 650         }
 651     }
 652
 653   template<typename _Key, typename _Value,
 654            typename _Allocator, typename _ExtractKey, typename _Equal,
 655            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 656            bool __chc, bool __cit, bool __uk>
 657     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 658                         _H1, _H2, _Hash, _RehashPolicy,
 659                         __chc, __cit, __uk>::_Bucket*
 660     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 661                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 662     _M_allocate_buckets(size_type __n)
 663     {
 664       _Bucket_allocator_type __alloc(_M_node_allocator);
 665
 666       // We allocate one extra bucket to have _M_begin_bucket_index
 667       // point to it as long as container is empty
 668       _Bucket* __p = __alloc.allocate(__n + 1);
 669       __builtin_memset(__p, 0, (__n + 1) * sizeof(_Bucket));
 670       return __p;
 671     }
 672
 673   template<typename _Key, typename _Value,
 674            typename _Allocator, typename _ExtractKey, typename _Equal,
 675            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 676            bool __chc, bool __cit, bool __uk>
 677     void
 678     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 679                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 680     _M_deallocate_buckets(_Bucket* __p, size_type __n)
 681     {
 682       _Bucket_allocator_type __alloc(_M_node_allocator);
 683       __alloc.deallocate(__p, __n + 1);
 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     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
 691                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
 692                         __chc, __cit, __uk>::_Node*
 693     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 694                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 695     _M_bucket_begin(size_type __bkt) const
 696     {
 697       if (__bkt == _M_begin_bucket_index)
 698         return _M_buckets[__bkt];
 699       _Node* __n = _M_buckets[__bkt];
 700       return __n ? __n->_M_next : nullptr;
 701     }
 702
 703   template<typename _Key, typename _Value,
 704            typename _Allocator, typename _ExtractKey, typename _Equal,
 705            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 706            bool __chc, bool __cit, bool __uk>
 707     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
 708                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
 709                         __chc, __cit, __uk>::_Node*
 710     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 711                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 712     _M_bucket_end(size_type __bkt) const
 713     {
 714       _Node* __n = _M_bucket_begin(__bkt);
 715       if (__n)
 716         for (;; __n = __n->_M_next)
 717           if (!__n->_M_next || _M_bucket_index(__n->_M_next) != __bkt)
 718             break;
 719       return __n;
 720     }
 721
 722   template<typename _Key, typename _Value,
 723            typename _Allocator, typename _ExtractKey, typename _Equal,
 724            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 725            bool __chc, bool __cit, bool __uk>
 726     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 727                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 728     _Hashtable(size_type __bucket_hint,
 729                const _H1& __h1, const _H2& __h2, const _Hash& __h,
 730                const _Equal& __eq, const _ExtractKey& __exk,
 731                const allocator_type& __a)
 732     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
 733       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 734                                 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
 735                                                         __eq),
 736       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 737       _M_node_allocator(__a),
 738       _M_bucket_count(0),
 739       _M_element_count(0),
 740       _M_rehash_policy()
 741     {
 742       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
 743       // We don't want the rehash policy to ask for the hashtable to shrink
 744       // on the first insertion so we need to reset its previous resize level.
 745       _M_rehash_policy._M_prev_resize = 0;
 746       _M_buckets = _M_allocate_buckets(_M_bucket_count);
 747       _M_begin_bucket_index = _M_bucket_count;
 748     }
 749
 750   template<typename _Key, typename _Value,
 751            typename _Allocator, typename _ExtractKey, typename _Equal,
 752            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 753            bool __chc, bool __cit, bool __uk>
 754     template<typename _InputIterator>
 755       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 756                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 757       _Hashtable(_InputIterator __f, _InputIterator __l,
 758                  size_type __bucket_hint,
 759                  const _H1& __h1, const _H2& __h2, const _Hash& __h,
 760                  const _Equal& __eq, const _ExtractKey& __exk,
 761                  const allocator_type& __a)
 762       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
 763         __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 764                                   _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
 765                                                           __eq),
 766         __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 767         _M_node_allocator(__a),
 768         _M_bucket_count(0),
 769         _M_element_count(0),
 770         _M_rehash_policy()
 771       {
 772         _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
 773                                    _M_rehash_policy.
 774                                    _M_bkt_for_elements(__detail::
 775                                                        __distance_fw(__f,
 776                                                                      __l)));
 777         // We don't want the rehash policy to ask for the hashtable to shrink
 778         // on the first insertion so we need to reset its previous resize
 779         // level.
 780         _M_rehash_policy._M_prev_resize = 0;
 781         _M_buckets = _M_allocate_buckets(_M_bucket_count);
 782         _M_begin_bucket_index = _M_bucket_count;
 783         __try
 784           {
 785             for (; __f != __l; ++__f)
 786               this->insert(*__f);
 787           }
 788         __catch(...)
 789           {
 790             clear();
 791             _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 792             __throw_exception_again;
 793           }
 794       }
 795
 796   template<typename _Key, typename _Value,
 797            typename _Allocator, typename _ExtractKey, typename _Equal,
 798            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 799            bool __chc, bool __cit, bool __uk>
 800     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 801                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 802     _Hashtable(const _Hashtable& __ht)
 803     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
 804       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 805                                 _H1, _H2, _Hash, __chc>(__ht),
 806       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
 807       _M_node_allocator(__ht._M_node_allocator),
 808       _M_bucket_count(__ht._M_bucket_count),
 809       _M_begin_bucket_index(__ht._M_begin_bucket_index),
 810       _M_element_count(__ht._M_element_count),
 811       _M_rehash_policy(__ht._M_rehash_policy)
 812     {
 813       _M_buckets = _M_allocate_buckets(_M_bucket_count);
 814       __try
 815         {
 816           const _Node* __ht_n = __ht._M_buckets[__ht._M_begin_bucket_index];
 817           if (!__ht_n)
 818             return;
 819
 820           // Note that the copy constructor do not rely on hash code usage.
 821           // First deal with the special first node that is directly store in
 822           // the first non-empty bucket
 823           _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
 824           this->_M_copy_code(__this_n, __ht_n);
 825           _M_buckets[_M_begin_bucket_index] = __this_n;
 826           __ht_n = __ht_n->_M_next;
 827           // Second deal with following non-empty buckets containing previous
 828           // nodes node.
 829           for (size_type __i = __ht._M_begin_bucket_index + 1;
 830                __i != __ht._M_bucket_count; ++__i)
 831             {
 832               if (!__ht._M_buckets[__i])
 833                 continue;
 834
 835               for (; __ht_n != __ht._M_buckets[__i]->_M_next;
 836                    __ht_n = __ht_n->_M_next)
 837                 {
 838                   __this_n->_M_next = _M_allocate_node(__ht_n->_M_v);
 839                   this->_M_copy_code(__this_n->_M_next, __ht_n);
 840                   __this_n = __this_n->_M_next;
 841                 }
 842
 843               _M_buckets[__i] = __this_n;
 844             }
 845           // Last finalize copy of the nodes of the last non-empty bucket
 846           for (; __ht_n; __ht_n = __ht_n->_M_next)
 847             {
 848               __this_n->_M_next = _M_allocate_node(__ht_n->_M_v);
 849               this->_M_copy_code(__this_n->_M_next, __ht_n);
 850               __this_n = __this_n->_M_next;
 851             }
 852         }
 853       __catch(...)
 854         {
 855           clear();
 856           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 857           __throw_exception_again;
 858         }
 859     }
 860
 861   template<typename _Key, typename _Value,
 862            typename _Allocator, typename _ExtractKey, typename _Equal,
 863            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 864            bool __chc, bool __cit, bool __uk>
 865     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 866                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 867     _Hashtable(_Hashtable&& __ht)
 868     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
 869       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 870                                 _H1, _H2, _Hash, __chc>(__ht),
 871       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
 872       _M_node_allocator(std::move(__ht._M_node_allocator)),
 873       _M_buckets(__ht._M_buckets),
 874       _M_bucket_count(__ht._M_bucket_count),
 875       _M_begin_bucket_index(__ht._M_begin_bucket_index),
 876       _M_element_count(__ht._M_element_count),
 877       _M_rehash_policy(__ht._M_rehash_policy)
 878     {
 879       __ht._M_rehash_policy = _RehashPolicy();
 880       __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
 881       __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
 882       __ht._M_begin_bucket_index = __ht._M_bucket_count;
 883       __ht._M_element_count = 0;
 884     }
 885
 886   template<typename _Key, typename _Value,
 887            typename _Allocator, typename _ExtractKey, typename _Equal,
 888            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 889            bool __chc, bool __cit, bool __uk>
 890     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 891                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 892     ~_Hashtable() noexcept
 893     {
 894       clear();
 895       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 896     }
 897
 898   template<typename _Key, typename _Value,
 899            typename _Allocator, typename _ExtractKey, typename _Equal,
 900            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 901            bool __chc, bool __cit, bool __uk>
 902     void
 903     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 904                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 905     swap(_Hashtable& __x)
 906     {
 907       // The only base class with member variables is hash_code_base.  We
 908       // define _Hash_code_base::_M_swap because different specializations
 909       // have different members.
 910       this->_M_swap(__x);
 911
 912       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 913       // 431. Swapping containers with unequal allocators.
 914       std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
 915                                                         __x._M_node_allocator);
 916
 917       std::swap(_M_rehash_policy, __x._M_rehash_policy);
 918       std::swap(_M_buckets, __x._M_buckets);
 919       std::swap(_M_bucket_count, __x._M_bucket_count);
 920       std::swap(_M_begin_bucket_index, __x._M_begin_bucket_index);
 921       std::swap(_M_element_count, __x._M_element_count);
 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     void
 929     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 930                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 931     __rehash_policy(const _RehashPolicy& __pol)
 932     {
 933       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
 934       if (__n_bkt != _M_bucket_count)
 935         _M_rehash(__n_bkt, _M_rehash_policy._M_state());
 936       _M_rehash_policy = __pol;
 937     }
 938
 939   template<typename _Key, typename _Value,
 940            typename _Allocator, typename _ExtractKey, typename _Equal,
 941            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 942            bool __chc, bool __cit, bool __uk>
 943     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 944                         _H1, _H2, _Hash, _RehashPolicy,
 945                         __chc, __cit, __uk>::iterator
 946     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 947                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 948     find(const key_type& __k)
 949     {
 950       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 951       std::size_t __n = _M_bucket_index(__k, __code);
 952       _Node* __p = _M_find_node(__n, __k, __code);
 953       return __p ? iterator(__p) : this->end();
 954     }
 955
 956   template<typename _Key, typename _Value,
 957            typename _Allocator, typename _ExtractKey, typename _Equal,
 958            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 959            bool __chc, bool __cit, bool __uk>
 960     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 961                         _H1, _H2, _Hash, _RehashPolicy,
 962                         __chc, __cit, __uk>::const_iterator
 963     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 964                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 965     find(const key_type& __k) const
 966     {
 967       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 968       std::size_t __n = _M_bucket_index(__k, __code);
 969       _Node* __p = _M_find_node(__n, __k, __code);
 970       return __p ? const_iterator(__p) : this->end();
 971     }
 972
 973   template<typename _Key, typename _Value,
 974            typename _Allocator, typename _ExtractKey, typename _Equal,
 975            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 976            bool __chc, bool __cit, bool __uk>
 977     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 978                         _H1, _H2, _Hash, _RehashPolicy,
 979                         __chc, __cit, __uk>::size_type
 980     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 981                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 982     count(const key_type& __k) const
 983     {
 984       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 985       std::size_t __n = _M_bucket_index(__k, __code);
 986       _Node* __p = _M_bucket_begin(__n);
 987       if (!__p)
 988         return 0;
 989
 990       std::size_t __result = 0;
 991       for (;; __p = __p->_M_next)
 992         {
 993           if (this->_M_equals(__k, __code, __p))
 994             ++__result;
 995           else if (__result)
 996             // All equivalent values are next to each other, if we found a not
 997             // equivalent value after an equivalent one it means that we won't
 998             // find anymore an equivalent value.
 999             break;
1000           if (!__p->_M_next || _M_bucket_index(__p->_M_next) != __n)
1001             break;
1002         }
1003       return __result;
1004     }
1005
1006   template<typename _Key, typename _Value,
1007            typename _Allocator, typename _ExtractKey, typename _Equal,
1008            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1009            bool __chc, bool __cit, bool __uk>
1010     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1011                                   _ExtractKey, _Equal, _H1,
1012                                   _H2, _Hash, _RehashPolicy,
1013                                   __chc, __cit, __uk>::iterator,
1014               typename _Hashtable<_Key, _Value, _Allocator,
1015                                   _ExtractKey, _Equal, _H1,
1016                                   _H2, _Hash, _RehashPolicy,
1017                                   __chc, __cit, __uk>::iterator>
1018     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1019                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1020     equal_range(const key_type& __k)
1021     {
1022       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1023       std::size_t __n = _M_bucket_index(__k, __code);
1024       _Node* __p = _M_find_node(__n, __k, __code);
1025
1026       if (__p)
1027         {
1028           _Node* __p1 = __p->_M_next;
1029           while (__p1 && _M_bucket_index(__p1) == __n
1030                  && this->_M_equals(__k, __code, __p1))
1031             __p1 = __p1->_M_next;
1032
1033           return std::make_pair(iterator(__p), iterator(__p1));
1034         }
1035       else
1036         return std::make_pair(this->end(), this->end());
1037     }
1038
1039   template<typename _Key, typename _Value,
1040            typename _Allocator, typename _ExtractKey, typename _Equal,
1041            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1042            bool __chc, bool __cit, bool __uk>
1043     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1044                                   _ExtractKey, _Equal, _H1,
1045                                   _H2, _Hash, _RehashPolicy,
1046                                   __chc, __cit, __uk>::const_iterator,
1047               typename _Hashtable<_Key, _Value, _Allocator,
1048                                   _ExtractKey, _Equal, _H1,
1049                                   _H2, _Hash, _RehashPolicy,
1050                                   __chc, __cit, __uk>::const_iterator>
1051     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1052                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1053     equal_range(const key_type& __k) const
1054     {
1055       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1056       std::size_t __n = _M_bucket_index(__k, __code);
1057       _Node* __p = _M_find_node(__n, __k, __code);
1058
1059       if (__p)
1060         {
1061           _Node* __p1 = __p->_M_next;
1062           while (__p1 && _M_bucket_index(__p1) == __n
1063                  && this->_M_equals(__k, __code, __p1))
1064             __p1 = __p1->_M_next;
1065
1066           return std::make_pair(const_iterator(__p), const_iterator(__p1));
1067         }
1068       else
1069         return std::make_pair(this->end(), this->end());
1070     }
1071
1072   // Find the node whose key compares equal to k in the bucket n. Return nullptr
1073   // if no node is found.
1074   template<typename _Key, typename _Value,
1075            typename _Allocator, typename _ExtractKey, typename _Equal,
1076            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1077            bool __chc, bool __cit, bool __uk>
1078     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1079                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
1080                         __chc, __cit, __uk>::_Node*
1081     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1082                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1083     _M_find_node(size_type __n, const key_type& __k,
1084                 typename _Hashtable::_Hash_code_type __code) const
1085     {
1086       _Node* __p = _M_bucket_begin(__n);
1087       if (!__p)
1088         return nullptr;
1089       for (;; __p = __p->_M_next)
1090         {
1091           if (this->_M_equals(__k, __code, __p))
1092             return __p;
1093           if (!(__p->_M_next) || _M_bucket_index(__p->_M_next) != __n)
1094             break;
1095         }
1096       return nullptr;
1097     }
1098
1099   template<typename _Key, typename _Value,
1100            typename _Allocator, typename _ExtractKey, typename _Equal,
1101            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1102            bool __chc, bool __cit, bool __uk>
1103     void
1104     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1105                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1106     _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
1107     {
1108       _Node* __prev_n;
1109       if (__bkt < _M_begin_bucket_index)
1110         {
1111           if (_M_begin_bucket_index != _M_bucket_count)
1112             {
1113               __new_node->_M_next = _M_buckets[_M_begin_bucket_index];
1114               _M_buckets[_M_begin_bucket_index] = __new_node;
1115             }
1116           __prev_n = __new_node;
1117           _M_begin_bucket_index = __bkt;
1118         }
1119       else
1120         {
1121           // We need to find previous non-empty bucket to link the new node.
1122           // There are several ways to find this previous bucket:
1123           // 1. Move backward until we find it (the current method)
1124           // 2. Start from the begin bucket index and move forward until we
1125           // cross __n position.
1126           // 3. Move forward until we find a non-empty bucket that will
1127           // contain the previous node.
1128           size_type __prev_bkt;
1129           for (__prev_bkt = __bkt; __prev_bkt-- != 0;)
1130             if (_M_buckets[__prev_bkt])
1131               break;
1132           __prev_n = _M_bucket_end(__prev_bkt);
1133           _M_insert_after(__prev_bkt, __prev_n, __new_node);
1134         }
1135       _M_buckets[__bkt] = __prev_n;
1136     }
1137
1138   template<typename _Key, typename _Value,
1139            typename _Allocator, typename _ExtractKey, typename _Equal,
1140            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1141            bool __chc, bool __cit, bool __uk>
1142     void
1143     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1144                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1145     _M_insert_after(size_type __bkt, _Node* __prev_n, _Node* __new_n)
1146     {
1147       if (__prev_n->_M_next)
1148         {
1149           size_type __next_bkt = _M_bucket_index(__prev_n->_M_next);
1150           if (__next_bkt != __bkt)
1151             _M_buckets[__next_bkt] = __new_n;
1152         }
1153       __new_n->_M_next = __prev_n->_M_next;
1154       __prev_n->_M_next = __new_n;
1155     }
1156
1157   template<typename _Key, typename _Value,
1158            typename _Allocator, typename _ExtractKey, typename _Equal,
1159            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1160            bool __chc, bool __cit, bool __uk>
1161     void
1162     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1163                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1164     _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt)
1165     {
1166       if (!__next || __next_bkt != __bkt)
1167         {
1168           // Bucket is now empty
1169           if (__next && __next_bkt != __bkt)
1170             // Update next non-empty bucket before begin node
1171             _M_buckets[__next_bkt] = _M_buckets[__bkt];
1172           _M_buckets[__bkt] = nullptr;
1173           if (__bkt == _M_begin_bucket_index)
1174             // We need to update begin bucket index
1175             if (__next)
1176               {
1177                 _M_begin_bucket_index = __next_bkt;
1178                 _M_buckets[_M_begin_bucket_index] = __next;
1179               }
1180             else
1181               _M_begin_bucket_index = _M_bucket_count;
1182         }
1183       else if (__bkt == _M_begin_bucket_index)
1184         _M_buckets[__bkt] = __next;
1185     }
1186
1187   template<typename _Key, typename _Value,
1188            typename _Allocator, typename _ExtractKey, typename _Equal,
1189            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1190            bool __chc, bool __cit, bool __uk>
1191     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1192                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
1193                         __chc, __cit, __uk>::_Node*
1194     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1195                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1196     _M_get_previous_node(size_type __bkt, _Node* __n)
1197     {
1198       _Node* __prev_n = nullptr;
1199       if (__bkt != _M_begin_bucket_index || __n != _M_buckets[__bkt])
1200         {
1201           __prev_n = _M_buckets[__bkt];
1202           while (__prev_n->_M_next != __n)
1203             __prev_n = __prev_n->_M_next;
1204         }
1205       return __prev_n;
1206     }
1207
1208   template<typename _Key, typename _Value,
1209            typename _Allocator, typename _ExtractKey, typename _Equal,
1210            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1211            bool __chc, bool __cit, bool __uk>
1212     template<typename... _Args>
1213       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1214                                     _ExtractKey, _Equal, _H1,
1215                                     _H2, _Hash, _RehashPolicy,
1216                                     __chc, __cit, __uk>::iterator, bool>
1217       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1218                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1219       _M_emplace(std::true_type, _Args&&... __args)
1220       {
1221         // First build the node to get access to the hash code
1222         _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1223         __try
1224           {
1225             const key_type& __k = this->_M_extract()(__new_node->_M_v);
1226             typename _Hashtable::_Hash_code_type __code
1227               = this->_M_hash_code(__k);
1228             size_type __bkt = _M_bucket_index(__k, __code);
1229
1230             if (_Node* __p = _M_find_node(__bkt, __k, __code))
1231               {
1232                 // There is already an equivalent node, no insertion
1233                 _M_deallocate_node(__new_node);
1234                 return std::make_pair(iterator(__p), false);
1235               }
1236
1237             // We are going to insert this node
1238             this->_M_store_code(__new_node, __code);
1239             const _RehashPolicyState& __saved_state
1240               = _M_rehash_policy._M_state();
1241             std::pair<bool, std::size_t> __do_rehash
1242               = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1243                                                 _M_element_count, 1);
1244
1245             if (__do_rehash.first)
1246               {
1247                 _M_rehash(__do_rehash.second, __saved_state);
1248                 __bkt = _M_bucket_index(__k, __code);
1249               }
1250
1251             if (_M_buckets[__bkt])
1252               _M_insert_after(__bkt, _M_buckets[__bkt], __new_node);
1253             else
1254               _M_insert_bucket_begin(__bkt, __new_node);
1255             ++_M_element_count;
1256             return std::make_pair(iterator(__new_node), true);
1257           }
1258         __catch(...)
1259           {
1260             _M_deallocate_node(__new_node);
1261             __throw_exception_again;
1262           }
1263       }
1264
1265   template<typename _Key, typename _Value,
1266            typename _Allocator, typename _ExtractKey, typename _Equal,
1267            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1268            bool __chc, bool __cit, bool __uk>
1269     template<typename... _Args>
1270       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1271                           _H1, _H2, _Hash, _RehashPolicy,
1272                           __chc, __cit, __uk>::iterator
1273       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1274                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1275       _M_emplace(std::false_type, _Args&&... __args)
1276       {
1277         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1278         std::pair<bool, std::size_t> __do_rehash
1279           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1280                                             _M_element_count, 1);
1281
1282         // First build the node to get its hash code
1283         _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1284         __try
1285           {
1286             const key_type& __k = this->_M_extract()(__new_node->_M_v);
1287             typename _Hashtable::_Hash_code_type __code
1288               = this->_M_hash_code(__k);
1289             this->_M_store_code(__new_node, __code);
1290             size_type __bkt = _M_bucket_index(__k, __code);
1291
1292             // Second find the node, avoid rehash if compare throws.
1293             _Node* __prev = _M_find_node(__bkt, __k, __code);
1294
1295             if (__do_rehash.first)
1296               {
1297                 _M_rehash(__do_rehash.second, __saved_state);
1298                 __bkt = _M_bucket_index(__k, __code);
1299                 // __prev is still valid because rehash do not invalidate nodes
1300               }
1301
1302             if (__prev)
1303               // Insert after the previous equivalent node
1304               _M_insert_after(__bkt, __prev, __new_node);
1305             else if (_M_buckets[__bkt])
1306               // Bucket is not empty and the inserted node has no equivalent in
1307               // the hashtable. We must insert the new node at the beginning or
1308               // end of the bucket to preserve equivalent elements relative
1309               // positions.
1310               if (__bkt != _M_begin_bucket_index)
1311                 // We insert the new node at the beginning
1312                 _M_insert_after(__bkt, _M_buckets[__bkt], __new_node);
1313               else
1314                 // We insert the new node at the end
1315                 _M_insert_after(__bkt, _M_bucket_end(__bkt), __new_node);
1316             else
1317               _M_insert_bucket_begin(__bkt, __new_node);
1318             ++_M_element_count;
1319             return iterator(__new_node);
1320           }
1321         __catch(...)
1322           {
1323             _M_deallocate_node(__new_node);
1324             __throw_exception_again;
1325           }
1326       }
1327
1328   // Insert v in bucket n (assumes no element with its key already present).
1329   template<typename _Key, typename _Value,
1330            typename _Allocator, typename _ExtractKey, typename _Equal,
1331            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1332            bool __chc, bool __cit, bool __uk>
1333     template<typename _Arg>
1334       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1335                           _H1, _H2, _Hash, _RehashPolicy,
1336                           __chc, __cit, __uk>::iterator
1337       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1338                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1339       _M_insert_bucket(_Arg&& __v, size_type __n,
1340                        typename _Hashtable::_Hash_code_type __code)
1341       {
1342         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1343         std::pair<bool, std::size_t> __do_rehash
1344           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1345                                             _M_element_count, 1);
1346
1347         if (__do_rehash.first)
1348           {
1349             const key_type& __k = this->_M_extract()(__v);
1350             __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
1351           }
1352
1353         _Node* __new_node = nullptr;
1354         __try
1355           {
1356             // Allocate the new node before doing the rehash so that we
1357             // don't do a rehash if the allocation throws.
1358             __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1359             this->_M_store_code(__new_node, __code);
1360             if (__do_rehash.first)
1361               _M_rehash(__do_rehash.second, __saved_state);
1362
1363             if (_M_buckets[__n])
1364               _M_insert_after(__n, _M_buckets[__n], __new_node);
1365             else
1366               _M_insert_bucket_begin(__n, __new_node);
1367             ++_M_element_count;
1368             return iterator(__new_node);
1369           }
1370         __catch(...)
1371           {
1372             if (!__new_node)
1373               _M_rehash_policy._M_reset(__saved_state);
1374             else
1375               _M_deallocate_node(__new_node);
1376             __throw_exception_again;
1377           }
1378       }
1379
1380   // Insert v if no element with its key is already present.
1381   template<typename _Key, typename _Value,
1382            typename _Allocator, typename _ExtractKey, typename _Equal,
1383            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1384            bool __chc, bool __cit, bool __uk>
1385     template<typename _Arg>
1386       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1387                                     _ExtractKey, _Equal, _H1,
1388                                     _H2, _Hash, _RehashPolicy,
1389                                     __chc, __cit, __uk>::iterator, bool>
1390       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1391                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1392       _M_insert(_Arg&& __v, std::true_type)
1393       {
1394         const key_type& __k = this->_M_extract()(__v);
1395         typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1396         size_type __n = _M_bucket_index(__k, __code);
1397
1398         if (_Node* __p = _M_find_node(__n, __k, __code))
1399           return std::make_pair(iterator(__p), false);
1400         return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
1401                               __n, __code), true);
1402       }
1403
1404   // Insert v unconditionally.
1405   template<typename _Key, typename _Value,
1406            typename _Allocator, typename _ExtractKey, typename _Equal,
1407            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1408            bool __chc, bool __cit, bool __uk>
1409     template<typename _Arg>
1410       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1411                           _H1, _H2, _Hash, _RehashPolicy,
1412                           __chc, __cit, __uk>::iterator
1413       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1414                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1415       _M_insert(_Arg&& __v, std::false_type)
1416       {
1417         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1418         std::pair<bool, std::size_t> __do_rehash
1419           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1420                                             _M_element_count, 1);
1421
1422         const key_type& __k = this->_M_extract()(__v);
1423         typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1424         size_type __n = _M_bucket_index(__k, __code);
1425
1426         // First find the node, avoid leaking new_node if compare throws.
1427         _Node* __prev = _M_find_node(__n, __k, __code);
1428         _Node* __new_node = nullptr;
1429         __try
1430           {
1431             // Second allocate new node so that we don't rehash if it throws
1432             __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1433             this->_M_store_code(__new_node, __code);
1434             if (__do_rehash.first)
1435               {
1436                 _M_rehash(__do_rehash.second, __saved_state);
1437                 __n = _M_bucket_index(__k, __code);
1438                 // __prev is still valid because rehash do not invalidate nodes
1439               }
1440
1441             if (__prev)
1442               // Insert after the previous equivalent node
1443               _M_insert_after(__n, __prev, __new_node);
1444             else if (_M_buckets[__n])
1445               // Bucket is not empty and the inserted node has no equivalent in
1446               // the hashtable. We must insert the new node at the beginning or
1447               // end of the bucket to preserve equivalent elements relative
1448               // positions.
1449               if (__n != _M_begin_bucket_index)
1450                 // We insert the new node at the beginning
1451                 _M_insert_after(__n, _M_buckets[__n], __new_node);
1452               else
1453                 // We insert the new node at the end
1454                 _M_insert_after(__n, _M_bucket_end(__n), __new_node);
1455             else
1456               _M_insert_bucket_begin(__n, __new_node);
1457             ++_M_element_count;
1458             return iterator(__new_node);
1459           }
1460         __catch(...)
1461           {
1462             if (!__new_node)
1463               _M_rehash_policy._M_reset(__saved_state);
1464             else
1465               _M_deallocate_node(__new_node);
1466             __throw_exception_again;
1467           }
1468       }
1469
1470   template<typename _Key, typename _Value,
1471            typename _Allocator, typename _ExtractKey, typename _Equal,
1472            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1473            bool __chc, bool __cit, bool __uk>
1474     template<typename _InputIterator>
1475       void
1476       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1477                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1478       insert(_InputIterator __first, _InputIterator __last)
1479       {
1480         size_type __n_elt = __detail::__distance_fw(__first, __last);
1481         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1482         std::pair<bool, std::size_t> __do_rehash
1483           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1484                                             _M_element_count, __n_elt);
1485         if (__do_rehash.first)
1486           _M_rehash(__do_rehash.second, __saved_state);
1487
1488         for (; __first != __last; ++__first)
1489           this->insert(*__first);
1490       }
1491
1492   template<typename _Key, typename _Value,
1493            typename _Allocator, typename _ExtractKey, typename _Equal,
1494            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1495            bool __chc, bool __cit, bool __uk>
1496     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1497                         _H1, _H2, _Hash, _RehashPolicy,
1498                         __chc, __cit, __uk>::iterator
1499     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1500                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1501     erase(const_iterator __it)
1502     {
1503       _Node* __n = __it._M_cur;
1504       std::size_t __bkt = _M_bucket_index(__n);
1505
1506       // Look for previous node to unlink it from the erased one, this is why
1507       // we need buckets to contain the before begin node of the bucket to make
1508       // this research fast.
1509       _Node* __prev_n = _M_get_previous_node(__bkt, __n);
1510       if (__n == _M_bucket_begin(__bkt))
1511         _M_remove_bucket_begin(__bkt, __n->_M_next,
1512            __n->_M_next ? _M_bucket_index(__n->_M_next) : 0);
1513       else if (__n->_M_next)
1514         {
1515           size_type __next_bkt = _M_bucket_index(__n->_M_next);
1516           if (__next_bkt != __bkt)
1517             _M_buckets[__next_bkt] = __prev_n;
1518         }
1519
1520       if (__prev_n)
1521         __prev_n->_M_next = __n->_M_next;
1522       iterator __result(__n->_M_next);
1523       _M_deallocate_node(__n);
1524       --_M_element_count;
1525
1526       return __result;
1527     }
1528
1529   template<typename _Key, typename _Value,
1530            typename _Allocator, typename _ExtractKey, typename _Equal,
1531            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1532            bool __chc, bool __cit, bool __uk>
1533     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1534                         _H1, _H2, _Hash, _RehashPolicy,
1535                         __chc, __cit, __uk>::size_type
1536     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1537                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1538     erase(const key_type& __k)
1539     {
1540       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1541       std::size_t __bkt = _M_bucket_index(__k, __code);
1542       // Look for the first matching node with its previous node at the same
1543       // time
1544       _Node* __n = _M_buckets[__bkt];
1545       if (!__n)
1546         return 0;
1547       _Node* __prev_n = nullptr;
1548       if (__bkt != _M_begin_bucket_index)
1549         {
1550           __prev_n = __n;
1551           __n = __n->_M_next;
1552         }
1553       bool __is_bucket_begin = true;
1554       for (;; __prev_n = __n, __n = __n->_M_next)
1555         {
1556           if (this->_M_equals(__k, __code, __n))
1557             break;
1558           if (!(__n->_M_next) || _M_bucket_index(__n->_M_next) != __bkt)
1559             return 0;
1560           __is_bucket_begin = false;
1561         }
1562
1563       // We found a matching node, start deallocation loop from it
1564       std::size_t __next_bkt = __bkt;
1565       _Node* __next_n = __n;
1566       size_type __result = 0;
1567       _Node* __saved_n = nullptr;
1568       do
1569         {
1570           _Node* __p = __next_n;
1571           __next_n = __p->_M_next;
1572           // _GLIBCXX_RESOLVE_LIB_DEFECTS
1573           // 526. Is it undefined if a function in the standard changes
1574           // in parameters?
1575           if (std::__addressof(this->_M_extract()(__p->_M_v))
1576               != std::__addressof(__k))
1577             _M_deallocate_node(__p);
1578           else
1579             __saved_n = __p;
1580           --_M_element_count;
1581           ++__result;
1582           if (!__next_n)
1583             break;
1584           __next_bkt = _M_bucket_index(__next_n);
1585         }
1586       while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
1587
1588       if (__saved_n)
1589         _M_deallocate_node(__saved_n);
1590       if (__is_bucket_begin)
1591         _M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
1592       else if (__next_n && __next_bkt != __bkt)
1593         _M_buckets[__next_bkt] = __prev_n;
1594       if (__prev_n)
1595         __prev_n->_M_next = __next_n;
1596       return __result;
1597     }
1598
1599   template<typename _Key, typename _Value,
1600            typename _Allocator, typename _ExtractKey, typename _Equal,
1601            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1602            bool __chc, bool __cit, bool __uk>
1603     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1604                         _H1, _H2, _Hash, _RehashPolicy,
1605                         __chc, __cit, __uk>::iterator
1606     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1607                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1608     erase(const_iterator __first, const_iterator __last)
1609     {
1610       _Node* __n = __first._M_cur;
1611       _Node* __last_n = __last._M_cur;
1612       if (__n == __last_n)
1613         return iterator(__n);
1614
1615       std::size_t __bkt = _M_bucket_index(__n);
1616
1617       _Node* __prev_n = _M_get_previous_node(__bkt, __n);
1618       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1619       std::size_t __n_bkt = __bkt;
1620       for (;;)
1621         {
1622           do
1623             {
1624               _Node* __tmp = __n;
1625               __n = __n->_M_next;
1626               _M_deallocate_node(__tmp);
1627               --_M_element_count;
1628               if (!__n)
1629                 break;
1630               __n_bkt = _M_bucket_index(__n);
1631             }
1632           while (__n != __last_n && __n_bkt == __bkt);
1633           if (__is_bucket_begin)
1634             _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1635           if (__n == __last_n)
1636             break;
1637           __is_bucket_begin = true;
1638           __bkt = __n_bkt;
1639         }
1640
1641       if (__n && __n_bkt != __bkt)
1642         _M_buckets[__n_bkt] = __prev_n;
1643       if (__prev_n)
1644         __prev_n->_M_next = __n;
1645       return iterator(__n);
1646     }
1647
1648   template<typename _Key, typename _Value,
1649            typename _Allocator, typename _ExtractKey, typename _Equal,
1650            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1651            bool __chc, bool __cit, bool __uk>
1652     void
1653     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1654                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1655     clear() noexcept
1656     {
1657       _M_deallocate_nodes(_M_buckets[_M_begin_bucket_index]);
1658       __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
1659       _M_element_count = 0;
1660       _M_begin_bucket_index = _M_bucket_count;
1661     }
1662
1663   template<typename _Key, typename _Value,
1664            typename _Allocator, typename _ExtractKey, typename _Equal,
1665            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1666            bool __chc, bool __cit, bool __uk>
1667     void
1668     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1669                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1670     rehash(size_type __n)
1671     {
1672       const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1673       _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1674                          _M_rehash_policy._M_bkt_for_elements(_M_element_count
1675                                                               + 1)),
1676                 __saved_state);
1677     }
1678
1679   template<typename _Key, typename _Value,
1680            typename _Allocator, typename _ExtractKey, typename _Equal,
1681            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1682            bool __chc, bool __cit, bool __uk>
1683     void
1684     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1685                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1686     _M_rehash(size_type __n, const _RehashPolicyState& __state)
1687     {
1688       __try
1689         {
1690           _Bucket* __new_buckets = _M_allocate_buckets(__n);
1691           _Node* __p = _M_buckets[_M_begin_bucket_index];
1692           // First loop to store each node in its new bucket
1693           while (__p)
1694             {
1695               _Node* __next = __p->_M_next;
1696               std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
1697               if (!__new_buckets[__new_index])
1698                 // Store temporarily bucket end node in _M_buckets if possible.
1699                 // This will boost second loop where we need to access bucket
1700                 // end node quickly.
1701                 if (__new_index < _M_bucket_count)
1702                   _M_buckets[__new_index] = __p;
1703               __p->_M_next = __new_buckets[__new_index];
1704               __new_buckets[__new_index] = __p;
1705               __p = __next;
1706             }
1707           _M_begin_bucket_index = __n;
1708           _Node* __prev_node = nullptr;
1709           // Second loop to link all nodes together and to fix bucket values so
1710           // that they contain the before begin node of the bucket.
1711           for (size_type __i = 0; __i != __n; ++__i)
1712             if (__new_buckets[__i])
1713               {
1714                 if (__prev_node)
1715                   {
1716                     __prev_node->_M_next = __new_buckets[__i];
1717                     __new_buckets[__i] = __prev_node;
1718                   }
1719                 else
1720                   _M_begin_bucket_index = __i;
1721                 if (__i < _M_bucket_count)
1722                   __prev_node = _M_buckets[__i];
1723                 else
1724                   {
1725                     __prev_node = __new_buckets[__i];
1726                     while (__prev_node->_M_next)
1727                       __prev_node = __prev_node->_M_next;
1728                   }
1729               }
1730           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1731           _M_bucket_count = __n;
1732           _M_buckets = __new_buckets;
1733         }
1734       __catch(...)
1735         {
1736           // A failure here means that buckets allocation failed.  We only
1737           // have to restore hash policy previous state.
1738           _M_rehash_policy._M_reset(__state);
1739           __throw_exception_again;
1740         }
1741     }
1742
1743 _GLIBCXX_END_NAMESPACE_VERSION
1744 } // namespace std
1745
1746 #endif // _HASHTABLE_H