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

   1 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
   2
   3 // Copyright (C) 2010-2013 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_policy.h
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly.
  28  *  @headername{unordered_map,unordered_set}
  29  */
  30
  31 #ifndef _HASHTABLE_POLICY_H
  32 #define _HASHTABLE_POLICY_H 1
  33
  34 namespace std _GLIBCXX_VISIBILITY(default)
  35 {
  36 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  37
  38   template<typename _Key, typename _Value, typename _Alloc,
  39            typename _ExtractKey, typename _Equal,
  40            typename _H1, typename _H2, typename _Hash,
  41            typename _RehashPolicy, typename _Traits>
  42     class _Hashtable;
  43
  44 _GLIBCXX_END_NAMESPACE_VERSION
  45
  46 namespace __detail
  47 {
  48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  49
  50   /**
  51    *  @defgroup hashtable-detail Base and Implementation Classes
  52    *  @ingroup unordered_associative_containers
  53    *  @{
  54    */
  55   template<typename _Key, typename _Value,
  56            typename _ExtractKey, typename _Equal,
  57            typename _H1, typename _H2, typename _Hash, typename _Traits>
  58     struct _Hashtable_base;
  59
  60   // Helper function: return distance(first, last) for forward
  61   // iterators, or 0 for input iterators.
  62   template<class _Iterator>
  63     inline typename std::iterator_traits<_Iterator>::difference_type
  64     __distance_fw(_Iterator __first, _Iterator __last,
  65                   std::input_iterator_tag)
  66     { return 0; }
  67
  68   template<class _Iterator>
  69     inline typename std::iterator_traits<_Iterator>::difference_type
  70     __distance_fw(_Iterator __first, _Iterator __last,
  71                   std::forward_iterator_tag)
  72     { return std::distance(__first, __last); }
  73
  74   template<class _Iterator>
  75     inline typename std::iterator_traits<_Iterator>::difference_type
  76     __distance_fw(_Iterator __first, _Iterator __last)
  77     {
  78       typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
  79       return __distance_fw(__first, __last, _Tag());
  80     }
  81
  82   // Helper type used to detect whether the hash functor is noexcept.
  83   template <typename _Key, typename _Hash>
  84     struct __is_noexcept_hash : std::integral_constant<bool,
  85         noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
  86     { };
  87
  88   struct _Identity
  89   {
  90     template<typename _Tp>
  91       _Tp&&
  92       operator()(_Tp&& __x) const
  93       { return std::forward<_Tp>(__x); }
  94   };
  95
  96   struct _Select1st
  97   {
  98     template<typename _Tp>
  99       auto
 100       operator()(_Tp&& __x) const
 101       -> decltype(std::get<0>(std::forward<_Tp>(__x)))
 102       { return std::get<0>(std::forward<_Tp>(__x)); }
 103   };
 104
 105   // Auxiliary types used for all instantiations of _Hashtable nodes
 106   // and iterators.
 107
 108   /**
 109    *  struct _Hashtable_traits
 110    *
 111    *  Important traits for hash tables.
 112    *
 113    *  @tparam _Cache_hash_code  Boolean value. True if the value of
 114    *  the hash function is stored along with the value. This is a
 115    *  time-space tradeoff.  Storing it may improve lookup speed by
 116    *  reducing the number of times we need to call the _Equal
 117    *  function.
 118    *
 119    *  @tparam _Constant_iterators  Boolean value. True if iterator and
 120    *  const_iterator are both constant iterator types. This is true
 121    *  for unordered_set and unordered_multiset, false for
 122    *  unordered_map and unordered_multimap.
 123    *
 124    *  @tparam _Unique_keys  Boolean value. True if the return value
 125    *  of _Hashtable::count(k) is always at most one, false if it may
 126    *  be an arbitrary number. This is true for unordered_set and
 127    *  unordered_map, false for unordered_multiset and
 128    *  unordered_multimap.
 129    */
 130   template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
 131     struct _Hashtable_traits
 132     {
 133       template<bool _Cond>
 134         using __bool_constant = integral_constant<bool, _Cond>;
 135
 136       using __hash_cached = __bool_constant<_Cache_hash_code>;
 137       using __constant_iterators = __bool_constant<_Constant_iterators>;
 138       using __unique_keys = __bool_constant<_Unique_keys>;
 139     };
 140
 141   /**
 142    *  struct _Hash_node_base
 143    *
 144    *  Nodes, used to wrap elements stored in the hash table.  A policy
 145    *  template parameter of class template _Hashtable controls whether
 146    *  nodes also store a hash code. In some cases (e.g. strings) this
 147    *  may be a performance win.
 148    */
 149   struct _Hash_node_base
 150   {
 151     _Hash_node_base* _M_nxt;
 152
 153     _Hash_node_base() : _M_nxt() { }
 154
 155     _Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { }
 156   };
 157
 158   /**
 159    *  struct _Hash_node_value_base
 160    *
 161    *  Node type with the value to store.
 162    */
 163   template<typename _Value>
 164     struct _Hash_node_value_base : _Hash_node_base
 165     {
 166       __gnu_cxx::__aligned_buffer<_Value> _M_storage;
 167
 168       _Value*
 169       _M_valptr() noexcept
 170       { return _M_storage._M_ptr(); }
 171
 172       const _Value*
 173       _M_valptr() const noexcept
 174       { return _M_storage._M_ptr(); }
 175
 176       _Value&
 177       _M_v() noexcept
 178       { return *_M_valptr(); }
 179
 180       const _Value&
 181       _M_v() const noexcept
 182       { return *_M_valptr(); }
 183     };
 184
 185   /**
 186    *  Primary template struct _Hash_node.
 187    */
 188   template<typename _Value, bool _Cache_hash_code>
 189     struct _Hash_node;
 190
 191   /**
 192    *  Specialization for nodes with caches, struct _Hash_node.
 193    *
 194    *  Base class is __detail::_Hash_node_value_base.
 195    */
 196   template<typename _Value>
 197     struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
 198     {
 199       std::size_t  _M_hash_code;
 200
 201       _Hash_node*
 202       _M_next() const { return static_cast<_Hash_node*>(this->_M_nxt); }
 203     };
 204
 205   /**
 206    *  Specialization for nodes without caches, struct _Hash_node.
 207    *
 208    *  Base class is __detail::_Hash_node_value_base.
 209    */
 210   template<typename _Value>
 211     struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
 212     {
 213       _Hash_node*
 214       _M_next() const { return static_cast<_Hash_node*>(this->_M_nxt); }
 215     };
 216
 217   /// Base class for node iterators.
 218   template<typename _Value, bool _Cache_hash_code>
 219     struct _Node_iterator_base
 220     {
 221       using __node_type = _Hash_node<_Value, _Cache_hash_code>;
 222
 223       __node_type*  _M_cur;
 224
 225       _Node_iterator_base(__node_type* __p)
 226       : _M_cur(__p) { }
 227
 228       void
 229       _M_incr()
 230       { _M_cur = _M_cur->_M_next(); }
 231     };
 232
 233   template<typename _Value, bool _Cache_hash_code>
 234     inline bool
 235     operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
 236                const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
 237     { return __x._M_cur == __y._M_cur; }
 238
 239   template<typename _Value, bool _Cache_hash_code>
 240     inline bool
 241     operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
 242                const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
 243     { return __x._M_cur != __y._M_cur; }
 244
 245   /// Node iterators, used to iterate through all the hashtable.
 246   template<typename _Value, bool __constant_iterators, bool __cache>
 247     struct _Node_iterator
 248     : public _Node_iterator_base<_Value, __cache>
 249     {
 250     private:
 251       using __base_type = _Node_iterator_base<_Value, __cache>;
 252       using __node_type = typename __base_type::__node_type;
 253
 254     public:
 255       typedef _Value                                   value_type;
 256       typedef std::ptrdiff_t                           difference_type;
 257       typedef std::forward_iterator_tag                iterator_category;
 258
 259       using pointer = typename std::conditional<__constant_iterators,
 260                                                 const _Value*, _Value*>::type;
 261
 262       using reference = typename std::conditional<__constant_iterators,
 263                                                   const _Value&, _Value&>::type;
 264
 265       _Node_iterator()
 266       : __base_type(0) { }
 267
 268       explicit
 269       _Node_iterator(__node_type* __p)
 270       : __base_type(__p) { }
 271
 272       reference
 273       operator*() const
 274       { return this->_M_cur->_M_v(); }
 275
 276       pointer
 277       operator->() const
 278       { return this->_M_cur->_M_valptr(); }
 279
 280       _Node_iterator&
 281       operator++()
 282       {
 283         this->_M_incr();
 284         return *this;
 285       }
 286
 287       _Node_iterator
 288       operator++(int)
 289       {
 290         _Node_iterator __tmp(*this);
 291         this->_M_incr();
 292         return __tmp;
 293       }
 294     };
 295
 296   /// Node const_iterators, used to iterate through all the hashtable.
 297   template<typename _Value, bool __constant_iterators, bool __cache>
 298     struct _Node_const_iterator
 299     : public _Node_iterator_base<_Value, __cache>
 300     {
 301     private:
 302       using __base_type = _Node_iterator_base<_Value, __cache>;
 303       using __node_type = typename __base_type::__node_type;
 304
 305     public:
 306       typedef _Value                                   value_type;
 307       typedef std::ptrdiff_t                           difference_type;
 308       typedef std::forward_iterator_tag                iterator_category;
 309
 310       typedef const _Value*                            pointer;
 311       typedef const _Value&                            reference;
 312
 313       _Node_const_iterator()
 314       : __base_type(0) { }
 315
 316       explicit
 317       _Node_const_iterator(__node_type* __p)
 318       : __base_type(__p) { }
 319
 320       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
 321                            __cache>& __x)
 322       : __base_type(__x._M_cur) { }
 323
 324       reference
 325       operator*() const
 326       { return this->_M_cur->_M_v(); }
 327
 328       pointer
 329       operator->() const
 330       { return this->_M_cur->_M_valptr(); }
 331
 332       _Node_const_iterator&
 333       operator++()
 334       {
 335         this->_M_incr();
 336         return *this;
 337       }
 338
 339       _Node_const_iterator
 340       operator++(int)
 341       {
 342         _Node_const_iterator __tmp(*this);
 343         this->_M_incr();
 344         return __tmp;
 345       }
 346     };
 347
 348   // Many of class template _Hashtable's template parameters are policy
 349   // classes.  These are defaults for the policies.
 350
 351   /// Default range hashing function: use division to fold a large number
 352   /// into the range [0, N).
 353   struct _Mod_range_hashing
 354   {
 355     typedef std::size_t first_argument_type;
 356     typedef std::size_t second_argument_type;
 357     typedef std::size_t result_type;
 358
 359     result_type
 360     operator()(first_argument_type __num,
 361                second_argument_type __den) const noexcept
 362     { return __num % __den; }
 363   };
 364
 365   /// Default ranged hash function H.  In principle it should be a
 366   /// function object composed from objects of type H1 and H2 such that
 367   /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
 368   /// h1 and h2.  So instead we'll just use a tag to tell class template
 369   /// hashtable to do that composition.
 370   struct _Default_ranged_hash { };
 371
 372   /// Default value for rehash policy.  Bucket size is (usually) the
 373   /// smallest prime that keeps the load factor small enough.
 374   struct _Prime_rehash_policy
 375   {
 376     _Prime_rehash_policy(float __z = 1.0)
 377     : _M_max_load_factor(__z), _M_next_resize(0) { }
 378
 379     float
 380     max_load_factor() const noexcept
 381     { return _M_max_load_factor; }
 382
 383     // Return a bucket size no smaller than n.
 384     std::size_t
 385     _M_next_bkt(std::size_t __n) const;
 386
 387     // Return a bucket count appropriate for n elements
 388     std::size_t
 389     _M_bkt_for_elements(std::size_t __n) const
 390     { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
 391
 392     // __n_bkt is current bucket count, __n_elt is current element count,
 393     // and __n_ins is number of elements to be inserted.  Do we need to
 394     // increase bucket count?  If so, return make_pair(true, n), where n
 395     // is the new bucket count.  If not, return make_pair(false, 0).
 396     std::pair<bool, std::size_t>
 397     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
 398                    std::size_t __n_ins) const;
 399
 400     typedef std::size_t _State;
 401
 402     _State
 403     _M_state() const
 404     { return _M_next_resize; }
 405
 406     void
 407     _M_reset() noexcept
 408     { _M_next_resize = 0; }
 409
 410     void
 411     _M_reset(_State __state)
 412     { _M_next_resize = __state; }
 413
 414     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
 415
 416     static const std::size_t _S_growth_factor = 2;
 417
 418     float                _M_max_load_factor;
 419     mutable std::size_t  _M_next_resize;
 420   };
 421
 422   // Base classes for std::_Hashtable.  We define these base classes
 423   // because in some cases we want to do different things depending on
 424   // the value of a policy class.  In some cases the policy class
 425   // affects which member functions and nested typedefs are defined;
 426   // we handle that by specializing base class templates.  Several of
 427   // the base class templates need to access other members of class
 428   // template _Hashtable, so we use a variant of the "Curiously
 429   // Recurring Template Pattern" (CRTP) technique.
 430
 431   /**
 432    *  Primary class template _Map_base.
 433    *
 434    *  If the hashtable has a value type of the form pair<T1, T2> and a
 435    *  key extraction policy (_ExtractKey) that returns the first part
 436    *  of the pair, the hashtable gets a mapped_type typedef.  If it
 437    *  satisfies those criteria and also has unique keys, then it also
 438    *  gets an operator[].
 439    */
 440   template<typename _Key, typename _Value, typename _Alloc,
 441            typename _ExtractKey, typename _Equal,
 442            typename _H1, typename _H2, typename _Hash,
 443            typename _RehashPolicy, typename _Traits,
 444            bool _Unique_keys = _Traits::__unique_keys::value>
 445     struct _Map_base { };
 446
 447   /// Partial specialization, __unique_keys set to false.
 448   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 449            typename _H1, typename _H2, typename _Hash,
 450            typename _RehashPolicy, typename _Traits>
 451     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 452                      _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
 453     {
 454       using mapped_type = typename std::tuple_element<1, _Pair>::type;
 455     };
 456
 457   /// Partial specialization, __unique_keys set to true.
 458   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 459            typename _H1, typename _H2, typename _Hash,
 460            typename _RehashPolicy, typename _Traits>
 461     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 462                      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
 463     {
 464     private:
 465       using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
 466                                                          _Select1st,
 467                                                         _Equal, _H1, _H2, _Hash,
 468                                                           _Traits>;
 469
 470       using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
 471                                      _Select1st, _Equal,
 472                                      _H1, _H2, _Hash, _RehashPolicy, _Traits>;
 473
 474       using __hash_code = typename __hashtable_base::__hash_code;
 475       using __node_type = typename __hashtable_base::__node_type;
 476
 477     public:
 478       using key_type = typename __hashtable_base::key_type;
 479       using iterator = typename __hashtable_base::iterator;
 480       using mapped_type = typename std::tuple_element<1, _Pair>::type;
 481
 482       mapped_type&
 483       operator[](const key_type& __k);
 484
 485       mapped_type&
 486       operator[](key_type&& __k);
 487
 488       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 489       // DR 761. unordered_map needs an at() member function.
 490       mapped_type&
 491       at(const key_type& __k);
 492
 493       const mapped_type&
 494       at(const key_type& __k) const;
 495     };
 496
 497   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 498            typename _H1, typename _H2, typename _Hash,
 499            typename _RehashPolicy, typename _Traits>
 500     typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 501                        _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
 502                        ::mapped_type&
 503     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 504               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
 505     operator[](const key_type& __k)
 506     {
 507       __hashtable* __h = static_cast<__hashtable*>(this);
 508       __hash_code __code = __h->_M_hash_code(__k);
 509       std::size_t __n = __h->_M_bucket_index(__k, __code);
 510       __node_type* __p = __h->_M_find_node(__n, __k, __code);
 511
 512       if (!__p)
 513         {
 514           __p = __h->_M_allocate_node(std::piecewise_construct,
 515                                       std::tuple<const key_type&>(__k),
 516                                       std::tuple<>());
 517           return __h->_M_insert_unique_node(__n, __code, __p)->second;
 518         }
 519
 520       return __p->_M_v().second;
 521     }
 522
 523   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 524            typename _H1, typename _H2, typename _Hash,
 525            typename _RehashPolicy, typename _Traits>
 526     typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 527                        _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
 528                        ::mapped_type&
 529     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 530               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
 531     operator[](key_type&& __k)
 532     {
 533       __hashtable* __h = static_cast<__hashtable*>(this);
 534       __hash_code __code = __h->_M_hash_code(__k);
 535       std::size_t __n = __h->_M_bucket_index(__k, __code);
 536       __node_type* __p = __h->_M_find_node(__n, __k, __code);
 537
 538       if (!__p)
 539         {
 540           __p = __h->_M_allocate_node(std::piecewise_construct,
 541                                       std::forward_as_tuple(std::move(__k)),
 542                                       std::tuple<>());
 543           return __h->_M_insert_unique_node(__n, __code, __p)->second;
 544         }
 545
 546       return __p->_M_v().second;
 547     }
 548
 549   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 550            typename _H1, typename _H2, typename _Hash,
 551            typename _RehashPolicy, typename _Traits>
 552     typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 553                        _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
 554                        ::mapped_type&
 555     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 556               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
 557     at(const key_type& __k)
 558     {
 559       __hashtable* __h = static_cast<__hashtable*>(this);
 560       __hash_code __code = __h->_M_hash_code(__k);
 561       std::size_t __n = __h->_M_bucket_index(__k, __code);
 562       __node_type* __p = __h->_M_find_node(__n, __k, __code);
 563
 564       if (!__p)
 565         __throw_out_of_range(__N("_Map_base::at"));
 566       return __p->_M_v().second;
 567     }
 568
 569   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 570            typename _H1, typename _H2, typename _Hash,
 571            typename _RehashPolicy, typename _Traits>
 572     const typename _Map_base<_Key, _Pair, _Alloc, _Select1st,
 573                              _Equal, _H1, _H2, _Hash, _RehashPolicy,
 574                              _Traits, true>::mapped_type&
 575     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
 576               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
 577     at(const key_type& __k) const
 578     {
 579       const __hashtable* __h = static_cast<const __hashtable*>(this);
 580       __hash_code __code = __h->_M_hash_code(__k);
 581       std::size_t __n = __h->_M_bucket_index(__k, __code);
 582       __node_type* __p = __h->_M_find_node(__n, __k, __code);
 583
 584       if (!__p)
 585         __throw_out_of_range(__N("_Map_base::at"));
 586       return __p->_M_v().second;
 587     }
 588
 589   /**
 590    *  Primary class template _Insert_base.
 591    *
 592    *  insert member functions appropriate to all _Hashtables.
 593    */
 594   template<typename _Key, typename _Value, typename _Alloc,
 595            typename _ExtractKey, typename _Equal,
 596            typename _H1, typename _H2, typename _Hash,
 597            typename _RehashPolicy, typename _Traits>
 598     struct _Insert_base
 599     {
 600       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
 601                                      _Equal, _H1, _H2, _Hash,
 602                                      _RehashPolicy, _Traits>;
 603
 604       using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
 605                                                _Equal, _H1, _H2, _Hash,
 606                                                _Traits>;
 607
 608       using value_type = typename __hashtable_base::value_type;
 609       using iterator = typename __hashtable_base::iterator;
 610       using const_iterator =  typename __hashtable_base::const_iterator;
 611       using size_type = typename __hashtable_base::size_type;
 612
 613       using __unique_keys = typename __hashtable_base::__unique_keys;
 614       using __ireturn_type = typename __hashtable_base::__ireturn_type;
 615       using __iconv_type = typename __hashtable_base::__iconv_type;
 616
 617       __hashtable&
 618       _M_conjure_hashtable()
 619       { return *(static_cast<__hashtable*>(this)); }
 620
 621       __ireturn_type
 622       insert(const value_type& __v)
 623       {
 624         __hashtable& __h = _M_conjure_hashtable();
 625         return __h._M_insert(__v, __unique_keys());
 626       }
 627
 628       iterator
 629       insert(const_iterator, const value_type& __v)
 630       { return __iconv_type()(insert(__v)); }
 631
 632       void
 633       insert(initializer_list<value_type> __l)
 634       { this->insert(__l.begin(), __l.end()); }
 635
 636       template<typename _InputIterator>
 637         void
 638         insert(_InputIterator __first, _InputIterator __last);
 639     };
 640
 641   template<typename _Key, typename _Value, typename _Alloc,
 642            typename _ExtractKey, typename _Equal,
 643            typename _H1, typename _H2, typename _Hash,
 644            typename _RehashPolicy, typename _Traits>
 645     template<typename _InputIterator>
 646       void
 647       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 648                     _RehashPolicy, _Traits>::
 649       insert(_InputIterator __first, _InputIterator __last)
 650       {
 651         using __rehash_type = typename __hashtable::__rehash_type;
 652         using __rehash_state = typename __hashtable::__rehash_state;
 653         using pair_type = std::pair<bool, std::size_t>;
 654
 655         size_type __n_elt = __detail::__distance_fw(__first, __last);
 656
 657         __hashtable& __h = _M_conjure_hashtable();
 658         __rehash_type& __rehash = __h._M_rehash_policy;
 659         const __rehash_state& __saved_state = __rehash._M_state();
 660         pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
 661                                                         __h._M_element_count,
 662                                                         __n_elt);
 663
 664         if (__do_rehash.first)
 665           __h._M_rehash(__do_rehash.second, __saved_state);
 666
 667         for (; __first != __last; ++__first)
 668           __h._M_insert(*__first, __unique_keys());
 669       }
 670
 671   /**
 672    *  Primary class template _Insert.
 673    *
 674    *  Select insert member functions appropriate to _Hashtable policy choices.
 675    */
 676   template<typename _Key, typename _Value, typename _Alloc,
 677            typename _ExtractKey, typename _Equal,
 678            typename _H1, typename _H2, typename _Hash,
 679            typename _RehashPolicy, typename _Traits,
 680            bool _Constant_iterators = _Traits::__constant_iterators::value,
 681            bool _Unique_keys = _Traits::__unique_keys::value>
 682     struct _Insert;
 683
 684   /// Specialization.
 685   template<typename _Key, typename _Value, typename _Alloc,
 686            typename _ExtractKey, typename _Equal,
 687            typename _H1, typename _H2, typename _Hash,
 688            typename _RehashPolicy, typename _Traits>
 689     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 690                    _RehashPolicy, _Traits, true, true>
 691     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 692                            _H1, _H2, _Hash, _RehashPolicy, _Traits>
 693     {
 694       using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
 695                                         _Equal, _H1, _H2, _Hash,
 696                                         _RehashPolicy, _Traits>;
 697       using value_type = typename __base_type::value_type;
 698       using iterator = typename __base_type::iterator;
 699       using const_iterator =  typename __base_type::const_iterator;
 700
 701       using __unique_keys = typename __base_type::__unique_keys;
 702       using __hashtable = typename __base_type::__hashtable;
 703
 704       using __base_type::insert;
 705
 706       std::pair<iterator, bool>
 707       insert(value_type&& __v)
 708       {
 709         __hashtable& __h = this->_M_conjure_hashtable();
 710         return __h._M_insert(std::move(__v), __unique_keys());
 711       }
 712
 713       iterator
 714       insert(const_iterator, value_type&& __v)
 715       { return insert(std::move(__v)).first; }
 716     };
 717
 718   /// Specialization.
 719   template<typename _Key, typename _Value, typename _Alloc,
 720            typename _ExtractKey, typename _Equal,
 721            typename _H1, typename _H2, typename _Hash,
 722            typename _RehashPolicy, typename _Traits>
 723     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 724                    _RehashPolicy, _Traits, true, false>
 725     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 726                            _H1, _H2, _Hash, _RehashPolicy, _Traits>
 727     {
 728       using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
 729                                         _Equal, _H1, _H2, _Hash,
 730                                         _RehashPolicy, _Traits>;
 731       using value_type = typename __base_type::value_type;
 732       using iterator = typename __base_type::iterator;
 733       using const_iterator =  typename __base_type::const_iterator;
 734
 735       using __unique_keys = typename __base_type::__unique_keys;
 736       using __hashtable = typename __base_type::__hashtable;
 737
 738       using __base_type::insert;
 739
 740       iterator
 741       insert(value_type&& __v)
 742       {
 743         __hashtable& __h = this->_M_conjure_hashtable();
 744         return __h._M_insert(std::move(__v), __unique_keys());
 745       }
 746
 747       iterator
 748       insert(const_iterator, value_type&& __v)
 749       { return insert(std::move(__v)); }
 750      };
 751
 752   /// Specialization.
 753   template<typename _Key, typename _Value, typename _Alloc,
 754            typename _ExtractKey, typename _Equal,
 755            typename _H1, typename _H2, typename _Hash,
 756            typename _RehashPolicy, typename _Traits, bool _Unique_keys>
 757     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 758                    _RehashPolicy, _Traits, false, _Unique_keys>
 759     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 760                            _H1, _H2, _Hash, _RehashPolicy, _Traits>
 761     {
 762       using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
 763                                        _Equal, _H1, _H2, _Hash,
 764                                        _RehashPolicy, _Traits>;
 765       using value_type = typename __base_type::value_type;
 766       using iterator = typename __base_type::iterator;
 767       using const_iterator =  typename __base_type::const_iterator;
 768
 769       using __unique_keys = typename __base_type::__unique_keys;
 770       using __hashtable = typename __base_type::__hashtable;
 771       using __ireturn_type = typename __base_type::__ireturn_type;
 772       using __iconv_type = typename __base_type::__iconv_type;
 773
 774       using __base_type::insert;
 775
 776       template<typename _Pair>
 777         using __is_cons = std::is_constructible<value_type, _Pair&&>;
 778
 779       template<typename _Pair>
 780         using _IFcons = std::enable_if<__is_cons<_Pair>::value>;
 781
 782       template<typename _Pair>
 783         using _IFconsp = typename _IFcons<_Pair>::type;
 784
 785       template<typename _Pair, typename = _IFconsp<_Pair>>
 786         __ireturn_type
 787         insert(_Pair&& __v)
 788         {
 789           __hashtable& __h = this->_M_conjure_hashtable();
 790           return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
 791         }
 792
 793       template<typename _Pair, typename = _IFconsp<_Pair>>
 794         iterator
 795         insert(const_iterator, _Pair&& __v)
 796         { return __iconv_type()(insert(std::forward<_Pair>(__v))); }
 797    };
 798
 799   /**
 800    *  Primary class template  _Rehash_base.
 801    *
 802    *  Give hashtable the max_load_factor functions and reserve iff the
 803    *  rehash policy is _Prime_rehash_policy.
 804   */
 805   template<typename _Key, typename _Value, typename _Alloc,
 806            typename _ExtractKey, typename _Equal,
 807            typename _H1, typename _H2, typename _Hash,
 808            typename _RehashPolicy, typename _Traits>
 809     struct _Rehash_base;
 810
 811   /// Specialization.
 812   template<typename _Key, typename _Value, typename _Alloc,
 813            typename _ExtractKey, typename _Equal,
 814            typename _H1, typename _H2, typename _Hash, typename _Traits>
 815     struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 816                         _H1, _H2, _Hash, _Prime_rehash_policy, _Traits>
 817     {
 818       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
 819                                      _Equal, _H1, _H2, _Hash,
 820                                      _Prime_rehash_policy, _Traits>;
 821
 822       float
 823       max_load_factor() const noexcept
 824       {
 825         const __hashtable* __this = static_cast<const __hashtable*>(this);
 826         return __this->__rehash_policy().max_load_factor();
 827       }
 828
 829       void
 830       max_load_factor(float __z)
 831       {
 832         __hashtable* __this = static_cast<__hashtable*>(this);
 833         __this->__rehash_policy(_Prime_rehash_policy(__z));
 834       }
 835
 836       void
 837       reserve(std::size_t __n)
 838       {
 839         __hashtable* __this = static_cast<__hashtable*>(this);
 840         __this->rehash(__builtin_ceil(__n / max_load_factor()));
 841       }
 842     };
 843
 844   /**
 845    *  Primary class template _Hashtable_ebo_helper.
 846    *
 847    *  Helper class using EBO when it is not forbidden (the type is not
 848    *  final) and when it is worth it (the type is empty.)
 849    */
 850   template<int _Nm, typename _Tp,
 851            bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
 852     struct _Hashtable_ebo_helper;
 853
 854   /// Specialization using EBO.
 855   template<int _Nm, typename _Tp>
 856     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
 857     : private _Tp
 858     {
 859       _Hashtable_ebo_helper() = default;
 860
 861       _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)
 862       { }
 863
 864       static const _Tp&
 865       _S_cget(const _Hashtable_ebo_helper& __eboh)
 866       { return static_cast<const _Tp&>(__eboh); }
 867
 868       static _Tp&
 869       _S_get(_Hashtable_ebo_helper& __eboh)
 870       { return static_cast<_Tp&>(__eboh); }
 871     };
 872
 873   /// Specialization not using EBO.
 874   template<int _Nm, typename _Tp>
 875     struct _Hashtable_ebo_helper<_Nm, _Tp, false>
 876     {
 877       _Hashtable_ebo_helper() = default;
 878
 879       _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp)
 880       { }
 881
 882       static const _Tp&
 883       _S_cget(const _Hashtable_ebo_helper& __eboh)
 884       { return __eboh._M_tp; }
 885
 886       static _Tp&
 887       _S_get(_Hashtable_ebo_helper& __eboh)
 888       { return __eboh._M_tp; }
 889
 890     private:
 891       _Tp _M_tp;
 892     };
 893
 894   /**
 895    *  Primary class template _Local_iterator_base.
 896    *
 897    *  Base class for local iterators, used to iterate within a bucket
 898    *  but not between buckets.
 899    */
 900   template<typename _Key, typename _Value, typename _ExtractKey,
 901            typename _H1, typename _H2, typename _Hash,
 902            bool __cache_hash_code>
 903     struct _Local_iterator_base;
 904
 905   /**
 906    *  Primary class template _Hash_code_base.
 907    *
 908    *  Encapsulates two policy issues that aren't quite orthogonal.
 909    *   (1) the difference between using a ranged hash function and using
 910    *       the combination of a hash function and a range-hashing function.
 911    *       In the former case we don't have such things as hash codes, so
 912    *       we have a dummy type as placeholder.
 913    *   (2) Whether or not we cache hash codes.  Caching hash codes is
 914    *       meaningless if we have a ranged hash function.
 915    *
 916    *  We also put the key extraction objects here, for convenience.
 917    *  Each specialization derives from one or more of the template
 918    *  parameters to benefit from Ebo. This is important as this type
 919    *  is inherited in some cases by the _Local_iterator_base type used
 920    *  to implement local_iterator and const_local_iterator. As with
 921    *  any iterator type we prefer to make it as small as possible.
 922    *
 923    *  Primary template is unused except as a hook for specializations.
 924    */
 925   template<typename _Key, typename _Value, typename _ExtractKey,
 926            typename _H1, typename _H2, typename _Hash,
 927            bool __cache_hash_code>
 928     struct _Hash_code_base;
 929
 930   /// Specialization: ranged hash function, no caching hash codes.  H1
 931   /// and H2 are provided but ignored.  We define a dummy hash code type.
 932   template<typename _Key, typename _Value, typename _ExtractKey,
 933            typename _H1, typename _H2, typename _Hash>
 934     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
 935     : private _Hashtable_ebo_helper<0, _ExtractKey>,
 936       private _Hashtable_ebo_helper<1, _Hash>
 937     {
 938     private:
 939       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
 940       using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
 941
 942     protected:
 943       typedef void*                                     __hash_code;
 944       typedef _Hash_node<_Value, false>                 __node_type;
 945
 946       // We need the default constructor for the local iterators.
 947       _Hash_code_base() = default;
 948
 949       _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
 950                       const _Hash& __h)
 951       : __ebo_extract_key(__ex), __ebo_hash(__h) { }
 952
 953       __hash_code
 954       _M_hash_code(const _Key& __key) const
 955       { return 0; }
 956
 957       std::size_t
 958       _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const
 959       { return _M_ranged_hash()(__k, __n); }
 960
 961       std::size_t
 962       _M_bucket_index(const __node_type* __p, std::size_t __n) const
 963         noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(), (std::size_t)0)) )
 964       { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
 965
 966       void
 967       _M_store_code(__node_type*, __hash_code) const
 968       { }
 969
 970       void
 971       _M_copy_code(__node_type*, const __node_type*) const
 972       { }
 973
 974       void
 975       _M_swap(_Hash_code_base& __x)
 976       {
 977         std::swap(_M_extract(), __x._M_extract());
 978         std::swap(_M_ranged_hash(), __x._M_ranged_hash());
 979       }
 980
 981       const _ExtractKey&
 982       _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
 983
 984       _ExtractKey&
 985       _M_extract() { return __ebo_extract_key::_S_get(*this); }
 986
 987       const _Hash&
 988       _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
 989
 990       _Hash&
 991       _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
 992     };
 993
 994   // No specialization for ranged hash function while caching hash codes.
 995   // That combination is meaningless, and trying to do it is an error.
 996
 997   /// Specialization: ranged hash function, cache hash codes.  This
 998   /// combination is meaningless, so we provide only a declaration
 999   /// and no definition.
1000   template<typename _Key, typename _Value, typename _ExtractKey,
1001            typename _H1, typename _H2, typename _Hash>
1002     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1003
1004   /// Specialization: hash function and range-hashing function, no
1005   /// caching of hash codes.
1006   /// Provides typedef and accessor required by C++ 11.
1007   template<typename _Key, typename _Value, typename _ExtractKey,
1008            typename _H1, typename _H2>
1009     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1010                            _Default_ranged_hash, false>
1011     : private _Hashtable_ebo_helper<0, _ExtractKey>,
1012       private _Hashtable_ebo_helper<1, _H1>,
1013       private _Hashtable_ebo_helper<2, _H2>
1014     {
1015     private:
1016       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
1017       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
1018       using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
1019
1020     public:
1021       typedef _H1                                       hasher;
1022
1023       hasher
1024       hash_function() const
1025       { return _M_h1(); }
1026
1027     protected:
1028       typedef std::size_t                               __hash_code;
1029       typedef _Hash_node<_Value, false>                 __node_type;
1030
1031       // We need the default constructor for the local iterators.
1032       _Hash_code_base() = default;
1033
1034       _Hash_code_base(const _ExtractKey& __ex,
1035                       const _H1& __h1, const _H2& __h2,
1036                       const _Default_ranged_hash&)
1037       : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1038
1039       __hash_code
1040       _M_hash_code(const _Key& __k) const
1041       { return _M_h1()(__k); }
1042
1043       std::size_t
1044       _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const
1045       { return _M_h2()(__c, __n); }
1046
1047       std::size_t
1048       _M_bucket_index(const __node_type* __p, std::size_t __n) const
1049         noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1050                   && noexcept(declval<const _H2&>()((__hash_code)0, (std::size_t)0)) )
1051       { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1052
1053       void
1054       _M_store_code(__node_type*, __hash_code) const
1055       { }
1056
1057       void
1058       _M_copy_code(__node_type*, const __node_type*) const
1059       { }
1060
1061       void
1062       _M_swap(_Hash_code_base& __x)
1063       {
1064         std::swap(_M_extract(), __x._M_extract());
1065         std::swap(_M_h1(), __x._M_h1());
1066         std::swap(_M_h2(), __x._M_h2());
1067       }
1068
1069       const _ExtractKey&
1070       _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1071
1072       _ExtractKey&
1073       _M_extract() { return __ebo_extract_key::_S_get(*this); }
1074
1075       const _H1&
1076       _M_h1() const { return __ebo_h1::_S_cget(*this); }
1077
1078       _H1&
1079       _M_h1() { return __ebo_h1::_S_get(*this); }
1080
1081       const _H2&
1082       _M_h2() const { return __ebo_h2::_S_cget(*this); }
1083
1084       _H2&
1085       _M_h2() { return __ebo_h2::_S_get(*this); }
1086     };
1087
1088   /// Specialization: hash function and range-hashing function,
1089   /// caching hash codes.  H is provided but ignored.  Provides
1090   /// typedef and accessor required by C++ 11.
1091   template<typename _Key, typename _Value, typename _ExtractKey,
1092            typename _H1, typename _H2>
1093     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1094                            _Default_ranged_hash, true>
1095     : private _Hashtable_ebo_helper<0, _ExtractKey>,
1096       private _Hashtable_ebo_helper<1, _H1>,
1097       private _Hashtable_ebo_helper<2, _H2>
1098     {
1099     private:
1100       // Gives access to _M_h2() to the local iterator implementation.
1101       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1102                                          _Default_ranged_hash, true>;
1103
1104       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
1105       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
1106       using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
1107
1108     public:
1109       typedef _H1                                       hasher;
1110
1111       hasher
1112       hash_function() const
1113       { return _M_h1(); }
1114
1115     protected:
1116       typedef std::size_t                               __hash_code;
1117       typedef _Hash_node<_Value, true>                  __node_type;
1118
1119       _Hash_code_base(const _ExtractKey& __ex,
1120                       const _H1& __h1, const _H2& __h2,
1121                       const _Default_ranged_hash&)
1122       : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1123
1124       __hash_code
1125       _M_hash_code(const _Key& __k) const
1126       { return _M_h1()(__k); }
1127
1128       std::size_t
1129       _M_bucket_index(const _Key&, __hash_code __c,
1130                       std::size_t __n) const
1131       { return _M_h2()(__c, __n); }
1132
1133       std::size_t
1134       _M_bucket_index(const __node_type* __p, std::size_t __n) const
1135         noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1136                                                  (std::size_t)0)) )
1137       { return _M_h2()(__p->_M_hash_code, __n); }
1138
1139       void
1140       _M_store_code(__node_type* __n, __hash_code __c) const
1141       { __n->_M_hash_code = __c; }
1142
1143       void
1144       _M_copy_code(__node_type* __to, const __node_type* __from) const
1145       { __to->_M_hash_code = __from->_M_hash_code; }
1146
1147       void
1148       _M_swap(_Hash_code_base& __x)
1149       {
1150         std::swap(_M_extract(), __x._M_extract());
1151         std::swap(_M_h1(), __x._M_h1());
1152         std::swap(_M_h2(), __x._M_h2());
1153       }
1154
1155       const _ExtractKey&
1156       _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1157
1158       _ExtractKey&
1159       _M_extract() { return __ebo_extract_key::_S_get(*this); }
1160
1161       const _H1&
1162       _M_h1() const { return __ebo_h1::_S_cget(*this); }
1163
1164       _H1&
1165       _M_h1() { return __ebo_h1::_S_get(*this); }
1166
1167       const _H2&
1168       _M_h2() const { return __ebo_h2::_S_cget(*this); }
1169
1170       _H2&
1171       _M_h2() { return __ebo_h2::_S_get(*this); }
1172     };
1173
1174   /**
1175    *  Primary class template _Equal_helper.
1176    *
1177    */
1178   template <typename _Key, typename _Value, typename _ExtractKey,
1179             typename _Equal, typename _HashCodeType,
1180             bool __cache_hash_code>
1181   struct _Equal_helper;
1182
1183   /// Specialization.
1184   template<typename _Key, typename _Value, typename _ExtractKey,
1185            typename _Equal, typename _HashCodeType>
1186   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
1187   {
1188     static bool
1189     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1190               const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
1191     { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1192   };
1193
1194   /// Specialization.
1195   template<typename _Key, typename _Value, typename _ExtractKey,
1196            typename _Equal, typename _HashCodeType>
1197   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
1198   {
1199     static bool
1200     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1201               const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
1202     { return __eq(__k, __extract(__n->_M_v())); }
1203   };
1204
1205
1206   /// Specialization.
1207   template<typename _Key, typename _Value, typename _ExtractKey,
1208            typename _H1, typename _H2, typename _Hash>
1209     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1210                                 _H1, _H2, _Hash, true>
1211     : private _Hashtable_ebo_helper<0, _H2>
1212     {
1213     protected:
1214       using __base_type = _Hashtable_ebo_helper<0, _H2>;
1215       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1216                                                _H1, _H2, _Hash, true>;
1217
1218     public:
1219       _Local_iterator_base() = default;
1220       _Local_iterator_base(const __hash_code_base& __base,
1221                            _Hash_node<_Value, true>* __p,
1222                            std::size_t __bkt, std::size_t __bkt_count)
1223       : __base_type(__base._M_h2()),
1224         _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1225
1226       void
1227       _M_incr()
1228       {
1229         _M_cur = _M_cur->_M_next();
1230         if (_M_cur)
1231           {
1232             std::size_t __bkt
1233               = __base_type::_S_get(*this)(_M_cur->_M_hash_code,
1234                                            _M_bucket_count);
1235             if (__bkt != _M_bucket)
1236               _M_cur = nullptr;
1237           }
1238       }
1239
1240       _Hash_node<_Value, true>*  _M_cur;
1241       std::size_t _M_bucket;
1242       std::size_t _M_bucket_count;
1243     };
1244
1245   /// Specialization.
1246   template<typename _Key, typename _Value, typename _ExtractKey,
1247            typename _H1, typename _H2, typename _Hash>
1248     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1249                                 _H1, _H2, _Hash, false>
1250     : private _Hash_code_base<_Key, _Value, _ExtractKey,
1251                               _H1, _H2, _Hash, false>
1252     {
1253     protected:
1254       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1255                                                _H1, _H2, _Hash, false>;
1256
1257     public:
1258       _Local_iterator_base() = default;
1259       _Local_iterator_base(const __hash_code_base& __base,
1260                            _Hash_node<_Value, false>* __p,
1261                            std::size_t __bkt, std::size_t __bkt_count)
1262         : __hash_code_base(__base),
1263           _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1264
1265       void
1266       _M_incr()
1267       {
1268         _M_cur = _M_cur->_M_next();
1269         if (_M_cur)
1270           {
1271             std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
1272             if (__bkt != _M_bucket)
1273               _M_cur = nullptr;
1274           }
1275       }
1276
1277       _Hash_node<_Value, false>*  _M_cur;
1278       std::size_t _M_bucket;
1279       std::size_t _M_bucket_count;
1280     };
1281
1282   template<typename _Key, typename _Value, typename _ExtractKey,
1283            typename _H1, typename _H2, typename _Hash, bool __cache>
1284     inline bool
1285     operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1286                                           _H1, _H2, _Hash, __cache>& __x,
1287                const _Local_iterator_base<_Key, _Value, _ExtractKey,
1288                                           _H1, _H2, _Hash, __cache>& __y)
1289     { return __x._M_cur == __y._M_cur; }
1290
1291   template<typename _Key, typename _Value, typename _ExtractKey,
1292            typename _H1, typename _H2, typename _Hash, bool __cache>
1293     inline bool
1294     operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1295                                           _H1, _H2, _Hash, __cache>& __x,
1296                const _Local_iterator_base<_Key, _Value, _ExtractKey,
1297                                           _H1, _H2, _Hash, __cache>& __y)
1298     { return __x._M_cur != __y._M_cur; }
1299
1300   /// local iterators
1301   template<typename _Key, typename _Value, typename _ExtractKey,
1302            typename _H1, typename _H2, typename _Hash,
1303            bool __constant_iterators, bool __cache>
1304     struct _Local_iterator
1305     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1306                                   _H1, _H2, _Hash, __cache>
1307     {
1308     private:
1309       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1310                                                _H1, _H2, _Hash, __cache>;
1311       using __hash_code_base = typename __base_type::__hash_code_base;
1312     public:
1313       typedef _Value                                   value_type;
1314       typedef typename std::conditional<__constant_iterators,
1315                                         const _Value*, _Value*>::type
1316                                                        pointer;
1317       typedef typename std::conditional<__constant_iterators,
1318                                         const _Value&, _Value&>::type
1319                                                        reference;
1320       typedef std::ptrdiff_t                           difference_type;
1321       typedef std::forward_iterator_tag                iterator_category;
1322
1323       _Local_iterator() = default;
1324
1325       _Local_iterator(const __hash_code_base& __base,
1326                       _Hash_node<_Value, __cache>* __p,
1327                       std::size_t __bkt, std::size_t __bkt_count)
1328         : __base_type(__base, __p, __bkt, __bkt_count)
1329       { }
1330
1331       reference
1332       operator*() const
1333       { return this->_M_cur->_M_v(); }
1334
1335       pointer
1336       operator->() const
1337       { return this->_M_cur->_M_valptr(); }
1338
1339       _Local_iterator&
1340       operator++()
1341       {
1342         this->_M_incr();
1343         return *this;
1344       }
1345
1346       _Local_iterator
1347       operator++(int)
1348       {
1349         _Local_iterator __tmp(*this);
1350         this->_M_incr();
1351         return __tmp;
1352       }
1353     };
1354
1355   /// local const_iterators
1356   template<typename _Key, typename _Value, typename _ExtractKey,
1357            typename _H1, typename _H2, typename _Hash,
1358            bool __constant_iterators, bool __cache>
1359     struct _Local_const_iterator
1360     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1361                                   _H1, _H2, _Hash, __cache>
1362     {
1363     private:
1364       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1365                                                _H1, _H2, _Hash, __cache>;
1366       using __hash_code_base = typename __base_type::__hash_code_base;
1367
1368     public:
1369       typedef _Value                                   value_type;
1370       typedef const _Value*                            pointer;
1371       typedef const _Value&                            reference;
1372       typedef std::ptrdiff_t                           difference_type;
1373       typedef std::forward_iterator_tag                iterator_category;
1374
1375       _Local_const_iterator() = default;
1376
1377       _Local_const_iterator(const __hash_code_base& __base,
1378                             _Hash_node<_Value, __cache>* __p,
1379                             std::size_t __bkt, std::size_t __bkt_count)
1380         : __base_type(__base, __p, __bkt, __bkt_count)
1381       { }
1382
1383       _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1384                                                   _H1, _H2, _Hash,
1385                                                   __constant_iterators,
1386                                                   __cache>& __x)
1387         : __base_type(__x)
1388       { }
1389
1390       reference
1391       operator*() const
1392       { return this->_M_cur->_M_v(); }
1393
1394       pointer
1395       operator->() const
1396       { return this->_M_cur->_M_valptr(); }
1397
1398       _Local_const_iterator&
1399       operator++()
1400       {
1401         this->_M_incr();
1402         return *this;
1403       }
1404
1405       _Local_const_iterator
1406       operator++(int)
1407       {
1408         _Local_const_iterator __tmp(*this);
1409         this->_M_incr();
1410         return __tmp;
1411       }
1412     };
1413
1414   /**
1415    *  Primary class template _Hashtable_base.
1416    *
1417    *  Helper class adding management of _Equal functor to
1418    *  _Hash_code_base type.
1419    *
1420    *  Base class templates are:
1421    *    - __detail::_Hash_code_base
1422    *    - __detail::_Hashtable_ebo_helper
1423    */
1424   template<typename _Key, typename _Value,
1425            typename _ExtractKey, typename _Equal,
1426            typename _H1, typename _H2, typename _Hash, typename _Traits>
1427   struct _Hashtable_base
1428   : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1429                            _Traits::__hash_cached::value>,
1430     private _Hashtable_ebo_helper<0, _Equal>
1431   {
1432   public:
1433     typedef _Key                                    key_type;
1434     typedef _Value                                  value_type;
1435     typedef _Equal                                  key_equal;
1436     typedef std::size_t                             size_type;
1437     typedef std::ptrdiff_t                          difference_type;
1438
1439     using __traits_type = _Traits;
1440     using __hash_cached = typename __traits_type::__hash_cached;
1441     using __constant_iterators = typename __traits_type::__constant_iterators;
1442     using __unique_keys = typename __traits_type::__unique_keys;
1443
1444     using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1445                                              _H1, _H2, _Hash,
1446                                              __hash_cached::value>;
1447
1448     using __hash_code = typename __hash_code_base::__hash_code;
1449     using __node_type = typename __hash_code_base::__node_type;
1450
1451     using iterator = __detail::_Node_iterator<value_type,
1452                                               __constant_iterators::value,
1453                                               __hash_cached::value>;
1454
1455     using const_iterator = __detail::_Node_const_iterator<value_type,
1456                                                    __constant_iterators::value,
1457                                                    __hash_cached::value>;
1458
1459     using local_iterator = __detail::_Local_iterator<key_type, value_type,
1460                                                   _ExtractKey, _H1, _H2, _Hash,
1461                                                   __constant_iterators::value,
1462                                                      __hash_cached::value>;
1463
1464     using const_local_iterator = __detail::_Local_const_iterator<key_type,
1465                                                                  value_type,
1466                                         _ExtractKey, _H1, _H2, _Hash,
1467                                         __constant_iterators::value,
1468                                         __hash_cached::value>;
1469
1470     using __ireturn_type = typename std::conditional<__unique_keys::value,
1471                                                      std::pair<iterator, bool>,
1472                                                      iterator>::type;
1473
1474     using __iconv_type = typename  std::conditional<__unique_keys::value,
1475                                                     _Select1st, _Identity
1476                                                     >::type;
1477   private:
1478     using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>;
1479     using _EqualHelper =  _Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1480                                         __hash_code, __hash_cached::value>;
1481
1482   protected:
1483     using __node_base = __detail::_Hash_node_base;
1484     using __bucket_type = __node_base*;
1485
1486     _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
1487                     const _Hash& __hash, const _Equal& __eq)
1488     : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1489     { }
1490
1491     bool
1492     _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
1493     {
1494       return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1495                                      __k, __c, __n);
1496     }
1497
1498     void
1499     _M_swap(_Hashtable_base& __x)
1500     {
1501       __hash_code_base::_M_swap(__x);
1502       std::swap(_M_eq(), __x._M_eq());
1503     }
1504
1505     const _Equal&
1506     _M_eq() const { return _EqualEBO::_S_cget(*this); }
1507
1508     _Equal&
1509     _M_eq() { return _EqualEBO::_S_get(*this); }
1510   };
1511
1512   /**
1513    *  struct _Equality_base.
1514    *
1515    *  Common types and functions for class _Equality.
1516    */
1517   struct _Equality_base
1518   {
1519   protected:
1520     template<typename _Uiterator>
1521       static bool
1522       _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1523   };
1524
1525   // See std::is_permutation in N3068.
1526   template<typename _Uiterator>
1527     bool
1528     _Equality_base::
1529     _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1530                       _Uiterator __first2)
1531     {
1532       for (; __first1 != __last1; ++__first1, ++__first2)
1533         if (!(*__first1 == *__first2))
1534           break;
1535
1536       if (__first1 == __last1)
1537         return true;
1538
1539       _Uiterator __last2 = __first2;
1540       std::advance(__last2, std::distance(__first1, __last1));
1541
1542       for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1543         {
1544           _Uiterator __tmp =  __first1;
1545           while (__tmp != __it1 && !bool(*__tmp == *__it1))
1546             ++__tmp;
1547
1548           // We've seen this one before.
1549           if (__tmp != __it1)
1550             continue;
1551
1552           std::ptrdiff_t __n2 = 0;
1553           for (__tmp = __first2; __tmp != __last2; ++__tmp)
1554             if (*__tmp == *__it1)
1555               ++__n2;
1556
1557           if (!__n2)
1558             return false;
1559
1560           std::ptrdiff_t __n1 = 0;
1561           for (__tmp = __it1; __tmp != __last1; ++__tmp)
1562             if (*__tmp == *__it1)
1563               ++__n1;
1564
1565           if (__n1 != __n2)
1566             return false;
1567         }
1568       return true;
1569     }
1570
1571   /**
1572    *  Primary class template  _Equality.
1573    *
1574    *  This is for implementing equality comparison for unordered
1575    *  containers, per N3068, by John Lakos and Pablo Halpern.
1576    *  Algorithmically, we follow closely the reference implementations
1577    *  therein.
1578    */
1579   template<typename _Key, typename _Value, typename _Alloc,
1580            typename _ExtractKey, typename _Equal,
1581            typename _H1, typename _H2, typename _Hash,
1582            typename _RehashPolicy, typename _Traits,
1583            bool _Unique_keys = _Traits::__unique_keys::value>
1584     struct _Equality;
1585
1586   /// Specialization.
1587   template<typename _Key, typename _Value, typename _Alloc,
1588            typename _ExtractKey, typename _Equal,
1589            typename _H1, typename _H2, typename _Hash,
1590            typename _RehashPolicy, typename _Traits>
1591     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1592                      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1593     {
1594       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1595                                      _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1596
1597       bool
1598       _M_equal(const __hashtable&) const;
1599     };
1600
1601   template<typename _Key, typename _Value, typename _Alloc,
1602            typename _ExtractKey, typename _Equal,
1603            typename _H1, typename _H2, typename _Hash,
1604            typename _RehashPolicy, typename _Traits>
1605     bool
1606     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1607               _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
1608     _M_equal(const __hashtable& __other) const
1609     {
1610       const __hashtable* __this = static_cast<const __hashtable*>(this);
1611
1612       if (__this->size() != __other.size())
1613         return false;
1614
1615       for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1616         {
1617           const auto __ity = __other.find(_ExtractKey()(*__itx));
1618           if (__ity == __other.end() || !bool(*__ity == *__itx))
1619             return false;
1620         }
1621       return true;
1622     }
1623
1624   /// Specialization.
1625   template<typename _Key, typename _Value, typename _Alloc,
1626            typename _ExtractKey, typename _Equal,
1627            typename _H1, typename _H2, typename _Hash,
1628            typename _RehashPolicy, typename _Traits>
1629     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1630                      _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1631     : public _Equality_base
1632     {
1633       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1634                                      _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1635
1636       bool
1637       _M_equal(const __hashtable&) const;
1638     };
1639
1640   template<typename _Key, typename _Value, typename _Alloc,
1641            typename _ExtractKey, typename _Equal,
1642            typename _H1, typename _H2, typename _Hash,
1643            typename _RehashPolicy, typename _Traits>
1644     bool
1645     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1646               _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
1647     _M_equal(const __hashtable& __other) const
1648     {
1649       const __hashtable* __this = static_cast<const __hashtable*>(this);
1650
1651       if (__this->size() != __other.size())
1652         return false;
1653
1654       for (auto __itx = __this->begin(); __itx != __this->end();)
1655         {
1656           const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1657           const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1658
1659           if (std::distance(__xrange.first, __xrange.second)
1660               != std::distance(__yrange.first, __yrange.second))
1661             return false;
1662
1663           if (!_S_is_permutation(__xrange.first, __xrange.second,
1664                                  __yrange.first))
1665             return false;
1666
1667           __itx = __xrange.second;
1668         }
1669       return true;
1670     }
1671
1672   /**
1673    * This type is to combine a _Hash_node_base instance with an allocator
1674    * instance through inheritance to benefit from EBO when possible.
1675    */
1676   template<typename _NodeAlloc>
1677     struct _Before_begin : public _NodeAlloc
1678     {
1679       _Hash_node_base _M_node;
1680
1681       _Before_begin(const _Before_begin&) = default;
1682       _Before_begin(_Before_begin&&) = default;
1683
1684       template<typename _Alloc>
1685         _Before_begin(_Alloc&& __a)
1686           : _NodeAlloc(std::forward<_Alloc>(__a))
1687         { }
1688     };
1689
1690   /*
1691    * Following are functors recyclicing a pool of nodes and using allocation
1692    * once the pool is empty.
1693    */
1694   /// Version using copy semantic through the copy constructor.
1695   template<typename _Key, typename _Value, typename _Alloc,
1696            typename _ExtractKey, typename _Equal,
1697            typename _H1, typename _H2, typename _Hash,
1698            typename _RehashPolicy, typename _Traits>
1699     struct _ReuseOrAllocNode
1700     {
1701     private:
1702       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1703                                      _Equal, _H1, _H2, _Hash,
1704                                      _RehashPolicy, _Traits>;
1705       using __val_alloc_type = typename __hashtable::_Value_alloc_type;
1706       using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
1707       using __node_alloc_traits = typename __hashtable::_Node_alloc_traits;
1708       using __node_type = typename __hashtable::__node_type;
1709
1710     public:
1711       _ReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
1712         : _M_nodes(__nodes), _M_h(__h) { }
1713       _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
1714
1715       ~_ReuseOrAllocNode()
1716       { _M_h._M_deallocate_nodes(_M_nodes); }
1717
1718       __node_type*
1719       operator()(const __node_type* __n) const
1720       {
1721         if (_M_nodes)
1722           {
1723             __node_type* __node = _M_nodes;
1724             _M_nodes = _M_nodes->_M_next();
1725             __node->_M_nxt = nullptr;
1726             __val_alloc_type __a(_M_h._M_node_allocator());
1727             __val_alloc_traits::destroy(__a, __node->_M_valptr());
1728             __try
1729               {
1730                 __val_alloc_traits::construct(__a, __node->_M_valptr(),
1731                                               __n->_M_v());
1732               }
1733             __catch(...)
1734               {
1735                 __node->~__node_type();
1736                 __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
1737                                                 __node, 1);
1738                 __throw_exception_again;
1739               }
1740             return __node;
1741           }
1742         return _M_h._M_allocate_node(__n->_M_v());
1743       }
1744
1745       mutable __node_type* _M_nodes;
1746       __hashtable& _M_h;
1747     };
1748
1749   /// Version using move semantic through the move constructor.
1750   template<typename _Key, typename _Value, typename _Alloc,
1751            typename _ExtractKey, typename _Equal,
1752            typename _H1, typename _H2, typename _Hash,
1753            typename _RehashPolicy, typename _Traits>
1754     struct _MoveReuseOrAllocNode
1755     {
1756     private:
1757       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1758                                      _Equal, _H1, _H2, _Hash,
1759                                      _RehashPolicy, _Traits>;
1760       using __val_alloc_type = typename __hashtable::_Value_alloc_type;
1761       using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
1762       using __node_alloc_traits = typename __hashtable::_Node_alloc_traits;
1763       using __node_type = typename __hashtable::__node_type;
1764
1765     public:
1766       _MoveReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
1767         : _M_nodes(__nodes), _M_h(__h) { }
1768       _MoveReuseOrAllocNode(const _MoveReuseOrAllocNode&) = delete;
1769
1770       ~_MoveReuseOrAllocNode()
1771       { _M_h._M_deallocate_nodes(_M_nodes); }
1772
1773       __node_type*
1774       operator()(__node_type* __n) const
1775       {
1776         if (_M_nodes)
1777           {
1778             __node_type* __node = _M_nodes;
1779             _M_nodes = _M_nodes->_M_next();
1780             __node->_M_nxt = nullptr;
1781             __val_alloc_type  __a(_M_h._M_node_allocator());
1782             __val_alloc_traits::destroy(__a, __node->_M_valptr());
1783             __try
1784               {
1785                 __val_alloc_traits::construct(__a, __node->_M_valptr(),
1786                                         std::move_if_noexcept(__n->_M_v()));
1787               }
1788             __catch(...)
1789               {
1790                 __node->~__node_type();
1791                 __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
1792                                                 __node, 1);
1793                 __throw_exception_again;
1794               }
1795             return __node;
1796           }
1797         return _M_h._M_allocate_node(std::move_if_noexcept(__n->_M_v()));
1798       }
1799
1800       mutable __node_type* _M_nodes;
1801       __hashtable& _M_h;
1802     };
1803
1804  //@} hashtable-detail
1805 _GLIBCXX_END_NAMESPACE_VERSION
1806 } // namespace __detail
1807 } // namespace std
1808
1809 #endif // _HASHTABLE_POLICY_H