Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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