1*e4b17023SJohn Marino // Internal policy header for unordered_set and unordered_map -*- C++ -*- 2*e4b17023SJohn Marino 3*e4b17023SJohn Marino // Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc. 4*e4b17023SJohn Marino // 5*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library. This library is free 6*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the 7*e4b17023SJohn Marino // terms of the GNU General Public License as published by the 8*e4b17023SJohn Marino // Free Software Foundation; either version 3, or (at your option) 9*e4b17023SJohn Marino // any later version. 10*e4b17023SJohn Marino 11*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful, 12*e4b17023SJohn Marino // but WITHOUT ANY WARRANTY; without even the implied warranty of 13*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14*e4b17023SJohn Marino // GNU General Public License for more details. 15*e4b17023SJohn Marino 16*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional 17*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version 18*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation. 19*e4b17023SJohn Marino 20*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License and 21*e4b17023SJohn Marino // a copy of the GCC Runtime Library Exception along with this program; 22*e4b17023SJohn Marino // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>. 24*e4b17023SJohn Marino 25*e4b17023SJohn Marino /** @file bits/hashtable_policy.h 26*e4b17023SJohn Marino * This is an internal header file, included by other library headers. 27*e4b17023SJohn Marino * Do not attempt to use it directly. 28*e4b17023SJohn Marino * @headername{unordered_map,unordered_set} 29*e4b17023SJohn Marino */ 30*e4b17023SJohn Marino 31*e4b17023SJohn Marino #ifndef _HASHTABLE_POLICY_H 32*e4b17023SJohn Marino #define _HASHTABLE_POLICY_H 1 33*e4b17023SJohn Marino 34*e4b17023SJohn Marino namespace std _GLIBCXX_VISIBILITY(default) 35*e4b17023SJohn Marino { 36*e4b17023SJohn Marino namespace __detail 37*e4b17023SJohn Marino { 38*e4b17023SJohn Marino _GLIBCXX_BEGIN_NAMESPACE_VERSION 39*e4b17023SJohn Marino 40*e4b17023SJohn Marino // Helper function: return distance(first, last) for forward 41*e4b17023SJohn Marino // iterators, or 0 for input iterators. 42*e4b17023SJohn Marino template<class _Iterator> 43*e4b17023SJohn Marino inline typename std::iterator_traits<_Iterator>::difference_type 44*e4b17023SJohn Marino __distance_fw(_Iterator __first, _Iterator __last, 45*e4b17023SJohn Marino std::input_iterator_tag) 46*e4b17023SJohn Marino { return 0; } 47*e4b17023SJohn Marino 48*e4b17023SJohn Marino template<class _Iterator> 49*e4b17023SJohn Marino inline typename std::iterator_traits<_Iterator>::difference_type 50*e4b17023SJohn Marino __distance_fw(_Iterator __first, _Iterator __last, 51*e4b17023SJohn Marino std::forward_iterator_tag) 52*e4b17023SJohn Marino { return std::distance(__first, __last); } 53*e4b17023SJohn Marino 54*e4b17023SJohn Marino template<class _Iterator> 55*e4b17023SJohn Marino inline typename std::iterator_traits<_Iterator>::difference_type 56*e4b17023SJohn Marino __distance_fw(_Iterator __first, _Iterator __last) 57*e4b17023SJohn Marino { 58*e4b17023SJohn Marino typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; 59*e4b17023SJohn Marino return __distance_fw(__first, __last, _Tag()); 60*e4b17023SJohn Marino } 61*e4b17023SJohn Marino 62*e4b17023SJohn Marino // Helper type used to detect when the hash functor is noexcept qualified or 63*e4b17023SJohn Marino // not 64*e4b17023SJohn Marino template <typename _Key, typename _Hash> 65*e4b17023SJohn Marino struct __is_noexcept_hash : std::integral_constant<bool, 66*e4b17023SJohn Marino noexcept(declval<const _Hash&>()(declval<const _Key&>()))> 67*e4b17023SJohn Marino {}; 68*e4b17023SJohn Marino 69*e4b17023SJohn Marino // Auxiliary types used for all instantiations of _Hashtable: nodes 70*e4b17023SJohn Marino // and iterators. 71*e4b17023SJohn Marino 72*e4b17023SJohn Marino // Nodes, used to wrap elements stored in the hash table. A policy 73*e4b17023SJohn Marino // template parameter of class template _Hashtable controls whether 74*e4b17023SJohn Marino // nodes also store a hash code. In some cases (e.g. strings) this 75*e4b17023SJohn Marino // may be a performance win. 76*e4b17023SJohn Marino struct _Hash_node_base 77*e4b17023SJohn Marino { 78*e4b17023SJohn Marino _Hash_node_base* _M_nxt; 79*e4b17023SJohn Marino 80*e4b17023SJohn Marino _Hash_node_base() 81*e4b17023SJohn Marino : _M_nxt() { } 82*e4b17023SJohn Marino _Hash_node_base(_Hash_node_base* __next) 83*e4b17023SJohn Marino : _M_nxt(__next) { } 84*e4b17023SJohn Marino }; 85*e4b17023SJohn Marino 86*e4b17023SJohn Marino template<typename _Value, bool __cache_hash_code> 87*e4b17023SJohn Marino struct _Hash_node; 88*e4b17023SJohn Marino 89*e4b17023SJohn Marino template<typename _Value> 90*e4b17023SJohn Marino struct _Hash_node<_Value, true> : _Hash_node_base 91*e4b17023SJohn Marino { 92*e4b17023SJohn Marino _Value _M_v; 93*e4b17023SJohn Marino std::size_t _M_hash_code; 94*e4b17023SJohn Marino 95*e4b17023SJohn Marino template<typename... _Args> 96*e4b17023SJohn Marino _Hash_node(_Args&&... __args) 97*e4b17023SJohn Marino : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { } 98*e4b17023SJohn Marino 99*e4b17023SJohn Marino _Hash_node* _M_next() const 100*e4b17023SJohn Marino { return static_cast<_Hash_node*>(_M_nxt); } 101*e4b17023SJohn Marino }; 102*e4b17023SJohn Marino 103*e4b17023SJohn Marino template<typename _Value> 104*e4b17023SJohn Marino struct _Hash_node<_Value, false> : _Hash_node_base 105*e4b17023SJohn Marino { 106*e4b17023SJohn Marino _Value _M_v; 107*e4b17023SJohn Marino 108*e4b17023SJohn Marino template<typename... _Args> 109*e4b17023SJohn Marino _Hash_node(_Args&&... __args) 110*e4b17023SJohn Marino : _M_v(std::forward<_Args>(__args)...) { } 111*e4b17023SJohn Marino 112*e4b17023SJohn Marino _Hash_node* _M_next() const 113*e4b17023SJohn Marino { return static_cast<_Hash_node*>(_M_nxt); } 114*e4b17023SJohn Marino }; 115*e4b17023SJohn Marino 116*e4b17023SJohn Marino // Node iterators, used to iterate through all the hashtable. 117*e4b17023SJohn Marino template<typename _Value, bool __cache> 118*e4b17023SJohn Marino struct _Node_iterator_base 119*e4b17023SJohn Marino { 120*e4b17023SJohn Marino _Node_iterator_base(_Hash_node<_Value, __cache>* __p) 121*e4b17023SJohn Marino : _M_cur(__p) { } 122*e4b17023SJohn Marino 123*e4b17023SJohn Marino void 124*e4b17023SJohn Marino _M_incr() 125*e4b17023SJohn Marino { _M_cur = _M_cur->_M_next(); } 126*e4b17023SJohn Marino 127*e4b17023SJohn Marino _Hash_node<_Value, __cache>* _M_cur; 128*e4b17023SJohn Marino }; 129*e4b17023SJohn Marino 130*e4b17023SJohn Marino template<typename _Value, bool __cache> 131*e4b17023SJohn Marino inline bool 132*e4b17023SJohn Marino operator==(const _Node_iterator_base<_Value, __cache>& __x, 133*e4b17023SJohn Marino const _Node_iterator_base<_Value, __cache>& __y) 134*e4b17023SJohn Marino { return __x._M_cur == __y._M_cur; } 135*e4b17023SJohn Marino 136*e4b17023SJohn Marino template<typename _Value, bool __cache> 137*e4b17023SJohn Marino inline bool 138*e4b17023SJohn Marino operator!=(const _Node_iterator_base<_Value, __cache>& __x, 139*e4b17023SJohn Marino const _Node_iterator_base<_Value, __cache>& __y) 140*e4b17023SJohn Marino { return __x._M_cur != __y._M_cur; } 141*e4b17023SJohn Marino 142*e4b17023SJohn Marino template<typename _Value, bool __constant_iterators, bool __cache> 143*e4b17023SJohn Marino struct _Node_iterator 144*e4b17023SJohn Marino : public _Node_iterator_base<_Value, __cache> 145*e4b17023SJohn Marino { 146*e4b17023SJohn Marino typedef _Value value_type; 147*e4b17023SJohn Marino typedef typename std::conditional<__constant_iterators, 148*e4b17023SJohn Marino const _Value*, _Value*>::type 149*e4b17023SJohn Marino pointer; 150*e4b17023SJohn Marino typedef typename std::conditional<__constant_iterators, 151*e4b17023SJohn Marino const _Value&, _Value&>::type 152*e4b17023SJohn Marino reference; 153*e4b17023SJohn Marino typedef std::ptrdiff_t difference_type; 154*e4b17023SJohn Marino typedef std::forward_iterator_tag iterator_category; 155*e4b17023SJohn Marino 156*e4b17023SJohn Marino _Node_iterator() 157*e4b17023SJohn Marino : _Node_iterator_base<_Value, __cache>(0) { } 158*e4b17023SJohn Marino 159*e4b17023SJohn Marino explicit 160*e4b17023SJohn Marino _Node_iterator(_Hash_node<_Value, __cache>* __p) 161*e4b17023SJohn Marino : _Node_iterator_base<_Value, __cache>(__p) { } 162*e4b17023SJohn Marino 163*e4b17023SJohn Marino reference 164*e4b17023SJohn Marino operator*() const 165*e4b17023SJohn Marino { return this->_M_cur->_M_v; } 166*e4b17023SJohn Marino 167*e4b17023SJohn Marino pointer 168*e4b17023SJohn Marino operator->() const 169*e4b17023SJohn Marino { return std::__addressof(this->_M_cur->_M_v); } 170*e4b17023SJohn Marino 171*e4b17023SJohn Marino _Node_iterator& 172*e4b17023SJohn Marino operator++() 173*e4b17023SJohn Marino { 174*e4b17023SJohn Marino this->_M_incr(); 175*e4b17023SJohn Marino return *this; 176*e4b17023SJohn Marino } 177*e4b17023SJohn Marino 178*e4b17023SJohn Marino _Node_iterator 179*e4b17023SJohn Marino operator++(int) 180*e4b17023SJohn Marino { 181*e4b17023SJohn Marino _Node_iterator __tmp(*this); 182*e4b17023SJohn Marino this->_M_incr(); 183*e4b17023SJohn Marino return __tmp; 184*e4b17023SJohn Marino } 185*e4b17023SJohn Marino }; 186*e4b17023SJohn Marino 187*e4b17023SJohn Marino template<typename _Value, bool __constant_iterators, bool __cache> 188*e4b17023SJohn Marino struct _Node_const_iterator 189*e4b17023SJohn Marino : public _Node_iterator_base<_Value, __cache> 190*e4b17023SJohn Marino { 191*e4b17023SJohn Marino typedef _Value value_type; 192*e4b17023SJohn Marino typedef const _Value* pointer; 193*e4b17023SJohn Marino typedef const _Value& reference; 194*e4b17023SJohn Marino typedef std::ptrdiff_t difference_type; 195*e4b17023SJohn Marino typedef std::forward_iterator_tag iterator_category; 196*e4b17023SJohn Marino 197*e4b17023SJohn Marino _Node_const_iterator() 198*e4b17023SJohn Marino : _Node_iterator_base<_Value, __cache>(0) { } 199*e4b17023SJohn Marino 200*e4b17023SJohn Marino explicit 201*e4b17023SJohn Marino _Node_const_iterator(_Hash_node<_Value, __cache>* __p) 202*e4b17023SJohn Marino : _Node_iterator_base<_Value, __cache>(__p) { } 203*e4b17023SJohn Marino 204*e4b17023SJohn Marino _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 205*e4b17023SJohn Marino __cache>& __x) 206*e4b17023SJohn Marino : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } 207*e4b17023SJohn Marino 208*e4b17023SJohn Marino reference 209*e4b17023SJohn Marino operator*() const 210*e4b17023SJohn Marino { return this->_M_cur->_M_v; } 211*e4b17023SJohn Marino 212*e4b17023SJohn Marino pointer 213*e4b17023SJohn Marino operator->() const 214*e4b17023SJohn Marino { return std::__addressof(this->_M_cur->_M_v); } 215*e4b17023SJohn Marino 216*e4b17023SJohn Marino _Node_const_iterator& 217*e4b17023SJohn Marino operator++() 218*e4b17023SJohn Marino { 219*e4b17023SJohn Marino this->_M_incr(); 220*e4b17023SJohn Marino return *this; 221*e4b17023SJohn Marino } 222*e4b17023SJohn Marino 223*e4b17023SJohn Marino _Node_const_iterator 224*e4b17023SJohn Marino operator++(int) 225*e4b17023SJohn Marino { 226*e4b17023SJohn Marino _Node_const_iterator __tmp(*this); 227*e4b17023SJohn Marino this->_M_incr(); 228*e4b17023SJohn Marino return __tmp; 229*e4b17023SJohn Marino } 230*e4b17023SJohn Marino }; 231*e4b17023SJohn Marino 232*e4b17023SJohn Marino // Many of class template _Hashtable's template parameters are policy 233*e4b17023SJohn Marino // classes. These are defaults for the policies. 234*e4b17023SJohn Marino 235*e4b17023SJohn Marino // Default range hashing function: use division to fold a large number 236*e4b17023SJohn Marino // into the range [0, N). 237*e4b17023SJohn Marino struct _Mod_range_hashing 238*e4b17023SJohn Marino { 239*e4b17023SJohn Marino typedef std::size_t first_argument_type; 240*e4b17023SJohn Marino typedef std::size_t second_argument_type; 241*e4b17023SJohn Marino typedef std::size_t result_type; 242*e4b17023SJohn Marino 243*e4b17023SJohn Marino result_type 244*e4b17023SJohn Marino operator()(first_argument_type __num, second_argument_type __den) const 245*e4b17023SJohn Marino { return __num % __den; } 246*e4b17023SJohn Marino }; 247*e4b17023SJohn Marino 248*e4b17023SJohn Marino // Default ranged hash function H. In principle it should be a 249*e4b17023SJohn Marino // function object composed from objects of type H1 and H2 such that 250*e4b17023SJohn Marino // h(k, N) = h2(h1(k), N), but that would mean making extra copies of 251*e4b17023SJohn Marino // h1 and h2. So instead we'll just use a tag to tell class template 252*e4b17023SJohn Marino // hashtable to do that composition. 253*e4b17023SJohn Marino struct _Default_ranged_hash { }; 254*e4b17023SJohn Marino 255*e4b17023SJohn Marino // Default value for rehash policy. Bucket size is (usually) the 256*e4b17023SJohn Marino // smallest prime that keeps the load factor small enough. 257*e4b17023SJohn Marino struct _Prime_rehash_policy 258*e4b17023SJohn Marino { 259*e4b17023SJohn Marino _Prime_rehash_policy(float __z = 1.0) 260*e4b17023SJohn Marino : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { } 261*e4b17023SJohn Marino 262*e4b17023SJohn Marino float 263*e4b17023SJohn Marino max_load_factor() const noexcept 264*e4b17023SJohn Marino { return _M_max_load_factor; } 265*e4b17023SJohn Marino 266*e4b17023SJohn Marino // Return a bucket size no smaller than n. 267*e4b17023SJohn Marino std::size_t 268*e4b17023SJohn Marino _M_next_bkt(std::size_t __n) const; 269*e4b17023SJohn Marino 270*e4b17023SJohn Marino // Return a bucket count appropriate for n elements 271*e4b17023SJohn Marino std::size_t 272*e4b17023SJohn Marino _M_bkt_for_elements(std::size_t __n) const; 273*e4b17023SJohn Marino 274*e4b17023SJohn Marino // __n_bkt is current bucket count, __n_elt is current element count, 275*e4b17023SJohn Marino // and __n_ins is number of elements to be inserted. Do we need to 276*e4b17023SJohn Marino // increase bucket count? If so, return make_pair(true, n), where n 277*e4b17023SJohn Marino // is the new bucket count. If not, return make_pair(false, 0). 278*e4b17023SJohn Marino std::pair<bool, std::size_t> 279*e4b17023SJohn Marino _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 280*e4b17023SJohn Marino std::size_t __n_ins) const; 281*e4b17023SJohn Marino 282*e4b17023SJohn Marino typedef std::pair<std::size_t, std::size_t> _State; 283*e4b17023SJohn Marino 284*e4b17023SJohn Marino _State 285*e4b17023SJohn Marino _M_state() const 286*e4b17023SJohn Marino { return std::make_pair(_M_prev_resize, _M_next_resize); } 287*e4b17023SJohn Marino 288*e4b17023SJohn Marino void 289*e4b17023SJohn Marino _M_reset(const _State& __state) 290*e4b17023SJohn Marino { 291*e4b17023SJohn Marino _M_prev_resize = __state.first; 292*e4b17023SJohn Marino _M_next_resize = __state.second; 293*e4b17023SJohn Marino } 294*e4b17023SJohn Marino 295*e4b17023SJohn Marino enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; 296*e4b17023SJohn Marino 297*e4b17023SJohn Marino static const std::size_t _S_growth_factor = 2; 298*e4b17023SJohn Marino 299*e4b17023SJohn Marino float _M_max_load_factor; 300*e4b17023SJohn Marino mutable std::size_t _M_prev_resize; 301*e4b17023SJohn Marino mutable std::size_t _M_next_resize; 302*e4b17023SJohn Marino }; 303*e4b17023SJohn Marino 304*e4b17023SJohn Marino extern const unsigned long __prime_list[]; 305*e4b17023SJohn Marino 306*e4b17023SJohn Marino // XXX This is a hack. There's no good reason for any of 307*e4b17023SJohn Marino // _Prime_rehash_policy's member functions to be inline. 308*e4b17023SJohn Marino 309*e4b17023SJohn Marino // Return a prime no smaller than n. 310*e4b17023SJohn Marino inline std::size_t 311*e4b17023SJohn Marino _Prime_rehash_policy:: 312*e4b17023SJohn Marino _M_next_bkt(std::size_t __n) const 313*e4b17023SJohn Marino { 314*e4b17023SJohn Marino // Optimize lookups involving the first elements of __prime_list. 315*e4b17023SJohn Marino // (useful to speed-up, eg, constructors) 316*e4b17023SJohn Marino static const unsigned char __fast_bkt[12] 317*e4b17023SJohn Marino = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; 318*e4b17023SJohn Marino 319*e4b17023SJohn Marino const std::size_t __grown_n = __n * _S_growth_factor; 320*e4b17023SJohn Marino if (__grown_n <= 11) 321*e4b17023SJohn Marino { 322*e4b17023SJohn Marino _M_prev_resize = 0; 323*e4b17023SJohn Marino _M_next_resize 324*e4b17023SJohn Marino = __builtin_ceil(__fast_bkt[__grown_n] 325*e4b17023SJohn Marino * (long double)_M_max_load_factor); 326*e4b17023SJohn Marino return __fast_bkt[__grown_n]; 327*e4b17023SJohn Marino } 328*e4b17023SJohn Marino 329*e4b17023SJohn Marino const unsigned long* __next_bkt 330*e4b17023SJohn Marino = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, 331*e4b17023SJohn Marino __grown_n); 332*e4b17023SJohn Marino const unsigned long* __prev_bkt 333*e4b17023SJohn Marino = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor); 334*e4b17023SJohn Marino 335*e4b17023SJohn Marino _M_prev_resize 336*e4b17023SJohn Marino = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor); 337*e4b17023SJohn Marino _M_next_resize 338*e4b17023SJohn Marino = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); 339*e4b17023SJohn Marino return *__next_bkt; 340*e4b17023SJohn Marino } 341*e4b17023SJohn Marino 342*e4b17023SJohn Marino // Return the smallest prime p such that alpha p >= n, where alpha 343*e4b17023SJohn Marino // is the load factor. 344*e4b17023SJohn Marino inline std::size_t 345*e4b17023SJohn Marino _Prime_rehash_policy:: 346*e4b17023SJohn Marino _M_bkt_for_elements(std::size_t __n) const 347*e4b17023SJohn Marino { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); } 348*e4b17023SJohn Marino 349*e4b17023SJohn Marino // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 350*e4b17023SJohn Marino // If p > __n_bkt, return make_pair(true, p); otherwise return 351*e4b17023SJohn Marino // make_pair(false, 0). In principle this isn't very different from 352*e4b17023SJohn Marino // _M_bkt_for_elements. 353*e4b17023SJohn Marino 354*e4b17023SJohn Marino // The only tricky part is that we're caching the element count at 355*e4b17023SJohn Marino // which we need to rehash, so we don't have to do a floating-point 356*e4b17023SJohn Marino // multiply for every insertion. 357*e4b17023SJohn Marino 358*e4b17023SJohn Marino inline std::pair<bool, std::size_t> 359*e4b17023SJohn Marino _Prime_rehash_policy:: 360*e4b17023SJohn Marino _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 361*e4b17023SJohn Marino std::size_t __n_ins) const 362*e4b17023SJohn Marino { 363*e4b17023SJohn Marino if (__n_elt + __n_ins >= _M_next_resize) 364*e4b17023SJohn Marino { 365*e4b17023SJohn Marino long double __min_bkts = (__n_elt + __n_ins) 366*e4b17023SJohn Marino / (long double)_M_max_load_factor; 367*e4b17023SJohn Marino if (__min_bkts >= __n_bkt) 368*e4b17023SJohn Marino return std::make_pair(true, 369*e4b17023SJohn Marino _M_next_bkt(__builtin_floor(__min_bkts) + 1)); 370*e4b17023SJohn Marino else 371*e4b17023SJohn Marino { 372*e4b17023SJohn Marino _M_next_resize 373*e4b17023SJohn Marino = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); 374*e4b17023SJohn Marino return std::make_pair(false, 0); 375*e4b17023SJohn Marino } 376*e4b17023SJohn Marino } 377*e4b17023SJohn Marino else if (__n_elt + __n_ins < _M_prev_resize) 378*e4b17023SJohn Marino { 379*e4b17023SJohn Marino long double __min_bkts = (__n_elt + __n_ins) 380*e4b17023SJohn Marino / (long double)_M_max_load_factor; 381*e4b17023SJohn Marino return std::make_pair(true, 382*e4b17023SJohn Marino _M_next_bkt(__builtin_floor(__min_bkts) + 1)); 383*e4b17023SJohn Marino } 384*e4b17023SJohn Marino else 385*e4b17023SJohn Marino return std::make_pair(false, 0); 386*e4b17023SJohn Marino } 387*e4b17023SJohn Marino 388*e4b17023SJohn Marino // Base classes for std::_Hashtable. We define these base classes 389*e4b17023SJohn Marino // because in some cases we want to do different things depending 390*e4b17023SJohn Marino // on the value of a policy class. In some cases the policy class 391*e4b17023SJohn Marino // affects which member functions and nested typedefs are defined; 392*e4b17023SJohn Marino // we handle that by specializing base class templates. Several of 393*e4b17023SJohn Marino // the base class templates need to access other members of class 394*e4b17023SJohn Marino // template _Hashtable, so we use the "curiously recurring template 395*e4b17023SJohn Marino // pattern" for them. 396*e4b17023SJohn Marino 397*e4b17023SJohn Marino // class template _Map_base. If the hashtable has a value type of 398*e4b17023SJohn Marino // the form pair<T1, T2> and a key extraction policy that returns the 399*e4b17023SJohn Marino // first part of the pair, the hashtable gets a mapped_type typedef. 400*e4b17023SJohn Marino // If it satisfies those criteria and also has unique keys, then it 401*e4b17023SJohn Marino // also gets an operator[]. 402*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _Ex, bool __unique, 403*e4b17023SJohn Marino typename _Hashtable> 404*e4b17023SJohn Marino struct _Map_base { }; 405*e4b17023SJohn Marino 406*e4b17023SJohn Marino template<typename _Key, typename _Pair, typename _Hashtable> 407*e4b17023SJohn Marino struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> 408*e4b17023SJohn Marino { 409*e4b17023SJohn Marino typedef typename _Pair::second_type mapped_type; 410*e4b17023SJohn Marino }; 411*e4b17023SJohn Marino 412*e4b17023SJohn Marino template<typename _Key, typename _Pair, typename _Hashtable> 413*e4b17023SJohn Marino struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> 414*e4b17023SJohn Marino { 415*e4b17023SJohn Marino typedef typename _Pair::second_type mapped_type; 416*e4b17023SJohn Marino 417*e4b17023SJohn Marino mapped_type& 418*e4b17023SJohn Marino operator[](const _Key& __k); 419*e4b17023SJohn Marino 420*e4b17023SJohn Marino mapped_type& 421*e4b17023SJohn Marino operator[](_Key&& __k); 422*e4b17023SJohn Marino 423*e4b17023SJohn Marino // _GLIBCXX_RESOLVE_LIB_DEFECTS 424*e4b17023SJohn Marino // DR 761. unordered_map needs an at() member function. 425*e4b17023SJohn Marino mapped_type& 426*e4b17023SJohn Marino at(const _Key& __k); 427*e4b17023SJohn Marino 428*e4b17023SJohn Marino const mapped_type& 429*e4b17023SJohn Marino at(const _Key& __k) const; 430*e4b17023SJohn Marino }; 431*e4b17023SJohn Marino 432*e4b17023SJohn Marino template<typename _Key, typename _Pair, typename _Hashtable> 433*e4b17023SJohn Marino typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 434*e4b17023SJohn Marino true, _Hashtable>::mapped_type& 435*e4b17023SJohn Marino _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 436*e4b17023SJohn Marino operator[](const _Key& __k) 437*e4b17023SJohn Marino { 438*e4b17023SJohn Marino _Hashtable* __h = static_cast<_Hashtable*>(this); 439*e4b17023SJohn Marino typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 440*e4b17023SJohn Marino std::size_t __n = __h->_M_bucket_index(__k, __code); 441*e4b17023SJohn Marino 442*e4b17023SJohn Marino typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 443*e4b17023SJohn Marino if (!__p) 444*e4b17023SJohn Marino return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), 445*e4b17023SJohn Marino __n, __code)->second; 446*e4b17023SJohn Marino return (__p->_M_v).second; 447*e4b17023SJohn Marino } 448*e4b17023SJohn Marino 449*e4b17023SJohn Marino template<typename _Key, typename _Pair, typename _Hashtable> 450*e4b17023SJohn Marino typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 451*e4b17023SJohn Marino true, _Hashtable>::mapped_type& 452*e4b17023SJohn Marino _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 453*e4b17023SJohn Marino operator[](_Key&& __k) 454*e4b17023SJohn Marino { 455*e4b17023SJohn Marino _Hashtable* __h = static_cast<_Hashtable*>(this); 456*e4b17023SJohn Marino typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 457*e4b17023SJohn Marino std::size_t __n = __h->_M_bucket_index(__k, __code); 458*e4b17023SJohn Marino 459*e4b17023SJohn Marino typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 460*e4b17023SJohn Marino if (!__p) 461*e4b17023SJohn Marino return __h->_M_insert_bucket(std::make_pair(std::move(__k), 462*e4b17023SJohn Marino mapped_type()), 463*e4b17023SJohn Marino __n, __code)->second; 464*e4b17023SJohn Marino return (__p->_M_v).second; 465*e4b17023SJohn Marino } 466*e4b17023SJohn Marino 467*e4b17023SJohn Marino template<typename _Key, typename _Pair, typename _Hashtable> 468*e4b17023SJohn Marino typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 469*e4b17023SJohn Marino true, _Hashtable>::mapped_type& 470*e4b17023SJohn Marino _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 471*e4b17023SJohn Marino at(const _Key& __k) 472*e4b17023SJohn Marino { 473*e4b17023SJohn Marino _Hashtable* __h = static_cast<_Hashtable*>(this); 474*e4b17023SJohn Marino typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 475*e4b17023SJohn Marino std::size_t __n = __h->_M_bucket_index(__k, __code); 476*e4b17023SJohn Marino 477*e4b17023SJohn Marino typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 478*e4b17023SJohn Marino if (!__p) 479*e4b17023SJohn Marino __throw_out_of_range(__N("_Map_base::at")); 480*e4b17023SJohn Marino return (__p->_M_v).second; 481*e4b17023SJohn Marino } 482*e4b17023SJohn Marino 483*e4b17023SJohn Marino template<typename _Key, typename _Pair, typename _Hashtable> 484*e4b17023SJohn Marino const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 485*e4b17023SJohn Marino true, _Hashtable>::mapped_type& 486*e4b17023SJohn Marino _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 487*e4b17023SJohn Marino at(const _Key& __k) const 488*e4b17023SJohn Marino { 489*e4b17023SJohn Marino const _Hashtable* __h = static_cast<const _Hashtable*>(this); 490*e4b17023SJohn Marino typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 491*e4b17023SJohn Marino std::size_t __n = __h->_M_bucket_index(__k, __code); 492*e4b17023SJohn Marino 493*e4b17023SJohn Marino typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 494*e4b17023SJohn Marino if (!__p) 495*e4b17023SJohn Marino __throw_out_of_range(__N("_Map_base::at")); 496*e4b17023SJohn Marino return (__p->_M_v).second; 497*e4b17023SJohn Marino } 498*e4b17023SJohn Marino 499*e4b17023SJohn Marino // class template _Rehash_base. Give hashtable the max_load_factor 500*e4b17023SJohn Marino // functions and reserve iff the rehash policy is _Prime_rehash_policy. 501*e4b17023SJohn Marino template<typename _RehashPolicy, typename _Hashtable> 502*e4b17023SJohn Marino struct _Rehash_base { }; 503*e4b17023SJohn Marino 504*e4b17023SJohn Marino template<typename _Hashtable> 505*e4b17023SJohn Marino struct _Rehash_base<_Prime_rehash_policy, _Hashtable> 506*e4b17023SJohn Marino { 507*e4b17023SJohn Marino float 508*e4b17023SJohn Marino max_load_factor() const noexcept 509*e4b17023SJohn Marino { 510*e4b17023SJohn Marino const _Hashtable* __this = static_cast<const _Hashtable*>(this); 511*e4b17023SJohn Marino return __this->__rehash_policy().max_load_factor(); 512*e4b17023SJohn Marino } 513*e4b17023SJohn Marino 514*e4b17023SJohn Marino void 515*e4b17023SJohn Marino max_load_factor(float __z) 516*e4b17023SJohn Marino { 517*e4b17023SJohn Marino _Hashtable* __this = static_cast<_Hashtable*>(this); 518*e4b17023SJohn Marino __this->__rehash_policy(_Prime_rehash_policy(__z)); 519*e4b17023SJohn Marino } 520*e4b17023SJohn Marino 521*e4b17023SJohn Marino void 522*e4b17023SJohn Marino reserve(std::size_t __n) 523*e4b17023SJohn Marino { 524*e4b17023SJohn Marino _Hashtable* __this = static_cast<_Hashtable*>(this); 525*e4b17023SJohn Marino __this->rehash(__builtin_ceil(__n / max_load_factor())); 526*e4b17023SJohn Marino } 527*e4b17023SJohn Marino }; 528*e4b17023SJohn Marino 529*e4b17023SJohn Marino // Helper class using EBO when it is not forbidden, type is not final, 530*e4b17023SJohn Marino // and when it worth it, type is empty. 531*e4b17023SJohn Marino template<int _Nm, typename _Tp, 532*e4b17023SJohn Marino bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> 533*e4b17023SJohn Marino struct _Hashtable_ebo_helper; 534*e4b17023SJohn Marino 535*e4b17023SJohn Marino // Specialization using EBO. 536*e4b17023SJohn Marino template<int _Nm, typename _Tp> 537*e4b17023SJohn Marino struct _Hashtable_ebo_helper<_Nm, _Tp, true> 538*e4b17023SJohn Marino // See PR53067. 539*e4b17023SJohn Marino : public _Tp 540*e4b17023SJohn Marino { 541*e4b17023SJohn Marino _Hashtable_ebo_helper() = default; 542*e4b17023SJohn Marino _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) 543*e4b17023SJohn Marino { } 544*e4b17023SJohn Marino 545*e4b17023SJohn Marino static const _Tp& 546*e4b17023SJohn Marino _S_cget(const _Hashtable_ebo_helper& __eboh) 547*e4b17023SJohn Marino { return static_cast<const _Tp&>(__eboh); } 548*e4b17023SJohn Marino 549*e4b17023SJohn Marino static _Tp& 550*e4b17023SJohn Marino _S_get(_Hashtable_ebo_helper& __eboh) 551*e4b17023SJohn Marino { return static_cast<_Tp&>(__eboh); } 552*e4b17023SJohn Marino }; 553*e4b17023SJohn Marino 554*e4b17023SJohn Marino // Specialization not using EBO. 555*e4b17023SJohn Marino template<int _Nm, typename _Tp> 556*e4b17023SJohn Marino struct _Hashtable_ebo_helper<_Nm, _Tp, false> 557*e4b17023SJohn Marino { 558*e4b17023SJohn Marino _Hashtable_ebo_helper() = default; 559*e4b17023SJohn Marino _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) 560*e4b17023SJohn Marino { } 561*e4b17023SJohn Marino 562*e4b17023SJohn Marino static const _Tp& 563*e4b17023SJohn Marino _S_cget(const _Hashtable_ebo_helper& __eboh) 564*e4b17023SJohn Marino { return __eboh._M_tp; } 565*e4b17023SJohn Marino 566*e4b17023SJohn Marino static _Tp& 567*e4b17023SJohn Marino _S_get(_Hashtable_ebo_helper& __eboh) 568*e4b17023SJohn Marino { return __eboh._M_tp; } 569*e4b17023SJohn Marino 570*e4b17023SJohn Marino private: 571*e4b17023SJohn Marino _Tp _M_tp; 572*e4b17023SJohn Marino }; 573*e4b17023SJohn Marino 574*e4b17023SJohn Marino // Class template _Hash_code_base. Encapsulates two policy issues that 575*e4b17023SJohn Marino // aren't quite orthogonal. 576*e4b17023SJohn Marino // (1) the difference between using a ranged hash function and using 577*e4b17023SJohn Marino // the combination of a hash function and a range-hashing function. 578*e4b17023SJohn Marino // In the former case we don't have such things as hash codes, so 579*e4b17023SJohn Marino // we have a dummy type as placeholder. 580*e4b17023SJohn Marino // (2) Whether or not we cache hash codes. Caching hash codes is 581*e4b17023SJohn Marino // meaningless if we have a ranged hash function. 582*e4b17023SJohn Marino // We also put the key extraction objects here, for convenience. 583*e4b17023SJohn Marino // 584*e4b17023SJohn Marino // Each specialization derives from one or more of the template parameters to 585*e4b17023SJohn Marino // benefit from Ebo. This is important as this type is inherited in some cases 586*e4b17023SJohn Marino // by the _Local_iterator_base type used to implement local_iterator and 587*e4b17023SJohn Marino // const_local_iterator. As with any iterator type we prefer to make it as 588*e4b17023SJohn Marino // small as possible. 589*e4b17023SJohn Marino 590*e4b17023SJohn Marino // Primary template: unused except as a hook for specializations. 591*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 592*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash, 593*e4b17023SJohn Marino bool __cache_hash_code> 594*e4b17023SJohn Marino struct _Hash_code_base; 595*e4b17023SJohn Marino 596*e4b17023SJohn Marino // Specialization: ranged hash function, no caching hash codes. H1 597*e4b17023SJohn Marino // and H2 are provided but ignored. We define a dummy hash code type. 598*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 599*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash> 600*e4b17023SJohn Marino struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> 601*e4b17023SJohn Marino // See PR53067. 602*e4b17023SJohn Marino : public _Hashtable_ebo_helper<0, _ExtractKey>, 603*e4b17023SJohn Marino public _Hashtable_ebo_helper<1, _Hash> 604*e4b17023SJohn Marino { 605*e4b17023SJohn Marino private: 606*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 607*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; 608*e4b17023SJohn Marino 609*e4b17023SJohn Marino protected: 610*e4b17023SJohn Marino // We need the default constructor for the local iterators. 611*e4b17023SJohn Marino _Hash_code_base() = default; 612*e4b17023SJohn Marino _Hash_code_base(const _ExtractKey& __ex, 613*e4b17023SJohn Marino const _H1&, const _H2&, const _Hash& __h) 614*e4b17023SJohn Marino : _EboExtractKey(__ex), _EboHash(__h) { } 615*e4b17023SJohn Marino 616*e4b17023SJohn Marino typedef void* _Hash_code_type; 617*e4b17023SJohn Marino 618*e4b17023SJohn Marino _Hash_code_type 619*e4b17023SJohn Marino _M_hash_code(const _Key& __key) const 620*e4b17023SJohn Marino { return 0; } 621*e4b17023SJohn Marino 622*e4b17023SJohn Marino std::size_t 623*e4b17023SJohn Marino _M_bucket_index(const _Key& __k, _Hash_code_type, 624*e4b17023SJohn Marino std::size_t __n) const 625*e4b17023SJohn Marino { return _M_ranged_hash()(__k, __n); } 626*e4b17023SJohn Marino 627*e4b17023SJohn Marino std::size_t 628*e4b17023SJohn Marino _M_bucket_index(const _Hash_node<_Value, false>* __p, 629*e4b17023SJohn Marino std::size_t __n) const 630*e4b17023SJohn Marino { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } 631*e4b17023SJohn Marino 632*e4b17023SJohn Marino void 633*e4b17023SJohn Marino _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 634*e4b17023SJohn Marino { } 635*e4b17023SJohn Marino 636*e4b17023SJohn Marino void 637*e4b17023SJohn Marino _M_copy_code(_Hash_node<_Value, false>*, 638*e4b17023SJohn Marino const _Hash_node<_Value, false>*) const 639*e4b17023SJohn Marino { } 640*e4b17023SJohn Marino 641*e4b17023SJohn Marino void 642*e4b17023SJohn Marino _M_swap(_Hash_code_base& __x) 643*e4b17023SJohn Marino { 644*e4b17023SJohn Marino std::swap(_M_extract(), __x._M_extract()); 645*e4b17023SJohn Marino std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 646*e4b17023SJohn Marino } 647*e4b17023SJohn Marino 648*e4b17023SJohn Marino protected: 649*e4b17023SJohn Marino const _ExtractKey& 650*e4b17023SJohn Marino _M_extract() const { return _EboExtractKey::_S_cget(*this); } 651*e4b17023SJohn Marino _ExtractKey& 652*e4b17023SJohn Marino _M_extract() { return _EboExtractKey::_S_get(*this); } 653*e4b17023SJohn Marino const _Hash& 654*e4b17023SJohn Marino _M_ranged_hash() const { return _EboHash::_S_cget(*this); } 655*e4b17023SJohn Marino _Hash& 656*e4b17023SJohn Marino _M_ranged_hash() { return _EboHash::_S_get(*this); } 657*e4b17023SJohn Marino }; 658*e4b17023SJohn Marino 659*e4b17023SJohn Marino // No specialization for ranged hash function while caching hash codes. 660*e4b17023SJohn Marino // That combination is meaningless, and trying to do it is an error. 661*e4b17023SJohn Marino 662*e4b17023SJohn Marino // Specialization: ranged hash function, cache hash codes. This 663*e4b17023SJohn Marino // combination is meaningless, so we provide only a declaration 664*e4b17023SJohn Marino // and no definition. 665*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 666*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash> 667*e4b17023SJohn Marino struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; 668*e4b17023SJohn Marino 669*e4b17023SJohn Marino // Specialization: hash function and range-hashing function, no 670*e4b17023SJohn Marino // caching of hash codes. 671*e4b17023SJohn Marino // Provides typedef and accessor required by TR1. 672*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 673*e4b17023SJohn Marino typename _H1, typename _H2> 674*e4b17023SJohn Marino struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 675*e4b17023SJohn Marino _Default_ranged_hash, false> 676*e4b17023SJohn Marino // See PR53067. 677*e4b17023SJohn Marino : public _Hashtable_ebo_helper<0, _ExtractKey>, 678*e4b17023SJohn Marino public _Hashtable_ebo_helper<1, _H1>, 679*e4b17023SJohn Marino public _Hashtable_ebo_helper<2, _H2> 680*e4b17023SJohn Marino { 681*e4b17023SJohn Marino private: 682*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 683*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<1, _H1> _EboH1; 684*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<2, _H2> _EboH2; 685*e4b17023SJohn Marino 686*e4b17023SJohn Marino public: 687*e4b17023SJohn Marino typedef _H1 hasher; 688*e4b17023SJohn Marino 689*e4b17023SJohn Marino hasher 690*e4b17023SJohn Marino hash_function() const 691*e4b17023SJohn Marino { return _M_h1(); } 692*e4b17023SJohn Marino 693*e4b17023SJohn Marino protected: 694*e4b17023SJohn Marino // We need the default constructor for the local iterators. 695*e4b17023SJohn Marino _Hash_code_base() = default; 696*e4b17023SJohn Marino _Hash_code_base(const _ExtractKey& __ex, 697*e4b17023SJohn Marino const _H1& __h1, const _H2& __h2, 698*e4b17023SJohn Marino const _Default_ranged_hash&) 699*e4b17023SJohn Marino : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } 700*e4b17023SJohn Marino 701*e4b17023SJohn Marino typedef std::size_t _Hash_code_type; 702*e4b17023SJohn Marino 703*e4b17023SJohn Marino _Hash_code_type 704*e4b17023SJohn Marino _M_hash_code(const _Key& __k) const 705*e4b17023SJohn Marino { return _M_h1()(__k); } 706*e4b17023SJohn Marino 707*e4b17023SJohn Marino std::size_t 708*e4b17023SJohn Marino _M_bucket_index(const _Key&, _Hash_code_type __c, 709*e4b17023SJohn Marino std::size_t __n) const 710*e4b17023SJohn Marino { return _M_h2()(__c, __n); } 711*e4b17023SJohn Marino 712*e4b17023SJohn Marino std::size_t 713*e4b17023SJohn Marino _M_bucket_index(const _Hash_node<_Value, false>* __p, 714*e4b17023SJohn Marino std::size_t __n) const 715*e4b17023SJohn Marino { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } 716*e4b17023SJohn Marino 717*e4b17023SJohn Marino void 718*e4b17023SJohn Marino _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 719*e4b17023SJohn Marino { } 720*e4b17023SJohn Marino 721*e4b17023SJohn Marino void 722*e4b17023SJohn Marino _M_copy_code(_Hash_node<_Value, false>*, 723*e4b17023SJohn Marino const _Hash_node<_Value, false>*) const 724*e4b17023SJohn Marino { } 725*e4b17023SJohn Marino 726*e4b17023SJohn Marino void 727*e4b17023SJohn Marino _M_swap(_Hash_code_base& __x) 728*e4b17023SJohn Marino { 729*e4b17023SJohn Marino std::swap(_M_extract(), __x._M_extract()); 730*e4b17023SJohn Marino std::swap(_M_h1(), __x._M_h1()); 731*e4b17023SJohn Marino std::swap(_M_h2(), __x._M_h2()); 732*e4b17023SJohn Marino } 733*e4b17023SJohn Marino 734*e4b17023SJohn Marino protected: 735*e4b17023SJohn Marino const _ExtractKey& 736*e4b17023SJohn Marino _M_extract() const { return _EboExtractKey::_S_cget(*this); } 737*e4b17023SJohn Marino _ExtractKey& 738*e4b17023SJohn Marino _M_extract() { return _EboExtractKey::_S_get(*this); } 739*e4b17023SJohn Marino const _H1& 740*e4b17023SJohn Marino _M_h1() const { return _EboH1::_S_cget(*this); } 741*e4b17023SJohn Marino _H1& 742*e4b17023SJohn Marino _M_h1() { return _EboH1::_S_get(*this); } 743*e4b17023SJohn Marino const _H2& 744*e4b17023SJohn Marino _M_h2() const { return _EboH2::_S_cget(*this); } 745*e4b17023SJohn Marino _H2& 746*e4b17023SJohn Marino _M_h2() { return _EboH2::_S_get(*this); } 747*e4b17023SJohn Marino }; 748*e4b17023SJohn Marino 749*e4b17023SJohn Marino // Specialization: hash function and range-hashing function, 750*e4b17023SJohn Marino // caching hash codes. H is provided but ignored. Provides 751*e4b17023SJohn Marino // typedef and accessor required by TR1. 752*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 753*e4b17023SJohn Marino typename _H1, typename _H2> 754*e4b17023SJohn Marino struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 755*e4b17023SJohn Marino _Default_ranged_hash, true> 756*e4b17023SJohn Marino // See PR53067. 757*e4b17023SJohn Marino : public _Hashtable_ebo_helper<0, _ExtractKey>, 758*e4b17023SJohn Marino public _Hashtable_ebo_helper<1, _H1>, 759*e4b17023SJohn Marino public _Hashtable_ebo_helper<2, _H2> 760*e4b17023SJohn Marino { 761*e4b17023SJohn Marino private: 762*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 763*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<1, _H1> _EboH1; 764*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<2, _H2> _EboH2; 765*e4b17023SJohn Marino 766*e4b17023SJohn Marino public: 767*e4b17023SJohn Marino typedef _H1 hasher; 768*e4b17023SJohn Marino 769*e4b17023SJohn Marino hasher 770*e4b17023SJohn Marino hash_function() const 771*e4b17023SJohn Marino { return _M_h1(); } 772*e4b17023SJohn Marino 773*e4b17023SJohn Marino protected: 774*e4b17023SJohn Marino _Hash_code_base(const _ExtractKey& __ex, 775*e4b17023SJohn Marino const _H1& __h1, const _H2& __h2, 776*e4b17023SJohn Marino const _Default_ranged_hash&) 777*e4b17023SJohn Marino : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } 778*e4b17023SJohn Marino 779*e4b17023SJohn Marino typedef std::size_t _Hash_code_type; 780*e4b17023SJohn Marino 781*e4b17023SJohn Marino _Hash_code_type 782*e4b17023SJohn Marino _M_hash_code(const _Key& __k) const 783*e4b17023SJohn Marino { return _M_h1()(__k); } 784*e4b17023SJohn Marino 785*e4b17023SJohn Marino std::size_t 786*e4b17023SJohn Marino _M_bucket_index(const _Key&, _Hash_code_type __c, 787*e4b17023SJohn Marino std::size_t __n) const 788*e4b17023SJohn Marino { return _M_h2()(__c, __n); } 789*e4b17023SJohn Marino 790*e4b17023SJohn Marino std::size_t 791*e4b17023SJohn Marino _M_bucket_index(const _Hash_node<_Value, true>* __p, 792*e4b17023SJohn Marino std::size_t __n) const 793*e4b17023SJohn Marino { return _M_h2()(__p->_M_hash_code, __n); } 794*e4b17023SJohn Marino 795*e4b17023SJohn Marino void 796*e4b17023SJohn Marino _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const 797*e4b17023SJohn Marino { __n->_M_hash_code = __c; } 798*e4b17023SJohn Marino 799*e4b17023SJohn Marino void 800*e4b17023SJohn Marino _M_copy_code(_Hash_node<_Value, true>* __to, 801*e4b17023SJohn Marino const _Hash_node<_Value, true>* __from) const 802*e4b17023SJohn Marino { __to->_M_hash_code = __from->_M_hash_code; } 803*e4b17023SJohn Marino 804*e4b17023SJohn Marino void 805*e4b17023SJohn Marino _M_swap(_Hash_code_base& __x) 806*e4b17023SJohn Marino { 807*e4b17023SJohn Marino std::swap(_M_extract(), __x._M_extract()); 808*e4b17023SJohn Marino std::swap(_M_h1(), __x._M_h1()); 809*e4b17023SJohn Marino std::swap(_M_h2(), __x._M_h2()); 810*e4b17023SJohn Marino } 811*e4b17023SJohn Marino 812*e4b17023SJohn Marino protected: 813*e4b17023SJohn Marino const _ExtractKey& 814*e4b17023SJohn Marino _M_extract() const { return _EboExtractKey::_S_cget(*this); } 815*e4b17023SJohn Marino _ExtractKey& 816*e4b17023SJohn Marino _M_extract() { return _EboExtractKey::_S_get(*this); } 817*e4b17023SJohn Marino const _H1& 818*e4b17023SJohn Marino _M_h1() const { return _EboH1::_S_cget(*this); } 819*e4b17023SJohn Marino _H1& 820*e4b17023SJohn Marino _M_h1() { return _EboH1::_S_get(*this); } 821*e4b17023SJohn Marino const _H2& 822*e4b17023SJohn Marino _M_h2() const { return _EboH2::_S_cget(*this); } 823*e4b17023SJohn Marino _H2& 824*e4b17023SJohn Marino _M_h2() { return _EboH2::_S_get(*this); } 825*e4b17023SJohn Marino }; 826*e4b17023SJohn Marino 827*e4b17023SJohn Marino template <typename _Key, typename _Value, typename _ExtractKey, 828*e4b17023SJohn Marino typename _Equal, typename _HashCodeType, 829*e4b17023SJohn Marino bool __cache_hash_code> 830*e4b17023SJohn Marino struct _Equal_helper; 831*e4b17023SJohn Marino 832*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 833*e4b17023SJohn Marino typename _Equal, typename _HashCodeType> 834*e4b17023SJohn Marino struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> 835*e4b17023SJohn Marino { 836*e4b17023SJohn Marino static bool 837*e4b17023SJohn Marino _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 838*e4b17023SJohn Marino const _Key& __k, _HashCodeType __c, 839*e4b17023SJohn Marino _Hash_node<_Value, true>* __n) 840*e4b17023SJohn Marino { return __c == __n->_M_hash_code 841*e4b17023SJohn Marino && __eq(__k, __extract(__n->_M_v)); } 842*e4b17023SJohn Marino }; 843*e4b17023SJohn Marino 844*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 845*e4b17023SJohn Marino typename _Equal, typename _HashCodeType> 846*e4b17023SJohn Marino struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> 847*e4b17023SJohn Marino { 848*e4b17023SJohn Marino static bool 849*e4b17023SJohn Marino _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 850*e4b17023SJohn Marino const _Key& __k, _HashCodeType, 851*e4b17023SJohn Marino _Hash_node<_Value, false>* __n) 852*e4b17023SJohn Marino { return __eq(__k, __extract(__n->_M_v)); } 853*e4b17023SJohn Marino }; 854*e4b17023SJohn Marino 855*e4b17023SJohn Marino // Helper class adding management of _Equal functor to _Hash_code_base 856*e4b17023SJohn Marino // type. 857*e4b17023SJohn Marino template<typename _Key, typename _Value, 858*e4b17023SJohn Marino typename _ExtractKey, typename _Equal, 859*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash, 860*e4b17023SJohn Marino bool __cache_hash_code> 861*e4b17023SJohn Marino struct _Hashtable_base 862*e4b17023SJohn Marino // See PR53067. 863*e4b17023SJohn Marino : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 864*e4b17023SJohn Marino __cache_hash_code>, 865*e4b17023SJohn Marino public _Hashtable_ebo_helper<0, _Equal> 866*e4b17023SJohn Marino { 867*e4b17023SJohn Marino private: 868*e4b17023SJohn Marino typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual; 869*e4b17023SJohn Marino 870*e4b17023SJohn Marino protected: 871*e4b17023SJohn Marino typedef _Hash_code_base<_Key, _Value, _ExtractKey, 872*e4b17023SJohn Marino _H1, _H2, _Hash, __cache_hash_code> _HCBase; 873*e4b17023SJohn Marino typedef typename _HCBase::_Hash_code_type _Hash_code_type; 874*e4b17023SJohn Marino 875*e4b17023SJohn Marino _Hashtable_base(const _ExtractKey& __ex, 876*e4b17023SJohn Marino const _H1& __h1, const _H2& __h2, 877*e4b17023SJohn Marino const _Hash& __hash, const _Equal& __eq) 878*e4b17023SJohn Marino : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { } 879*e4b17023SJohn Marino 880*e4b17023SJohn Marino bool 881*e4b17023SJohn Marino _M_equals(const _Key& __k, _Hash_code_type __c, 882*e4b17023SJohn Marino _Hash_node<_Value, __cache_hash_code>* __n) const 883*e4b17023SJohn Marino { 884*e4b17023SJohn Marino typedef _Equal_helper<_Key, _Value, _ExtractKey, 885*e4b17023SJohn Marino _Equal, _Hash_code_type, 886*e4b17023SJohn Marino __cache_hash_code> _EqualHelper; 887*e4b17023SJohn Marino return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 888*e4b17023SJohn Marino __k, __c, __n); 889*e4b17023SJohn Marino } 890*e4b17023SJohn Marino 891*e4b17023SJohn Marino void 892*e4b17023SJohn Marino _M_swap(_Hashtable_base& __x) 893*e4b17023SJohn Marino { 894*e4b17023SJohn Marino _HCBase::_M_swap(__x); 895*e4b17023SJohn Marino std::swap(_M_eq(), __x._M_eq()); 896*e4b17023SJohn Marino } 897*e4b17023SJohn Marino 898*e4b17023SJohn Marino protected: 899*e4b17023SJohn Marino const _Equal& 900*e4b17023SJohn Marino _M_eq() const { return _EboEqual::_S_cget(*this); } 901*e4b17023SJohn Marino _Equal& 902*e4b17023SJohn Marino _M_eq() { return _EboEqual::_S_get(*this); } 903*e4b17023SJohn Marino }; 904*e4b17023SJohn Marino 905*e4b17023SJohn Marino // Local iterators, used to iterate within a bucket but not between 906*e4b17023SJohn Marino // buckets. 907*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 908*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash, 909*e4b17023SJohn Marino bool __cache_hash_code> 910*e4b17023SJohn Marino struct _Local_iterator_base; 911*e4b17023SJohn Marino 912*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 913*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash> 914*e4b17023SJohn Marino struct _Local_iterator_base<_Key, _Value, _ExtractKey, 915*e4b17023SJohn Marino _H1, _H2, _Hash, true> 916*e4b17023SJohn Marino // See PR53067. 917*e4b17023SJohn Marino : public _H2 918*e4b17023SJohn Marino { 919*e4b17023SJohn Marino _Local_iterator_base() = default; 920*e4b17023SJohn Marino _Local_iterator_base(_Hash_node<_Value, true>* __p, 921*e4b17023SJohn Marino std::size_t __bkt, std::size_t __bkt_count) 922*e4b17023SJohn Marino : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 923*e4b17023SJohn Marino 924*e4b17023SJohn Marino void 925*e4b17023SJohn Marino _M_incr() 926*e4b17023SJohn Marino { 927*e4b17023SJohn Marino _M_cur = _M_cur->_M_next(); 928*e4b17023SJohn Marino if (_M_cur) 929*e4b17023SJohn Marino { 930*e4b17023SJohn Marino std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count); 931*e4b17023SJohn Marino if (__bkt != _M_bucket) 932*e4b17023SJohn Marino _M_cur = nullptr; 933*e4b17023SJohn Marino } 934*e4b17023SJohn Marino } 935*e4b17023SJohn Marino 936*e4b17023SJohn Marino const _H2& _M_h2() const 937*e4b17023SJohn Marino { return *this; } 938*e4b17023SJohn Marino 939*e4b17023SJohn Marino _Hash_node<_Value, true>* _M_cur; 940*e4b17023SJohn Marino std::size_t _M_bucket; 941*e4b17023SJohn Marino std::size_t _M_bucket_count; 942*e4b17023SJohn Marino }; 943*e4b17023SJohn Marino 944*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 945*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash> 946*e4b17023SJohn Marino struct _Local_iterator_base<_Key, _Value, _ExtractKey, 947*e4b17023SJohn Marino _H1, _H2, _Hash, false> 948*e4b17023SJohn Marino // See PR53067. 949*e4b17023SJohn Marino : public _Hash_code_base<_Key, _Value, _ExtractKey, 950*e4b17023SJohn Marino _H1, _H2, _Hash, false> 951*e4b17023SJohn Marino { 952*e4b17023SJohn Marino _Local_iterator_base() = default; 953*e4b17023SJohn Marino _Local_iterator_base(_Hash_node<_Value, false>* __p, 954*e4b17023SJohn Marino std::size_t __bkt, std::size_t __bkt_count) 955*e4b17023SJohn Marino : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 956*e4b17023SJohn Marino 957*e4b17023SJohn Marino void 958*e4b17023SJohn Marino _M_incr() 959*e4b17023SJohn Marino { 960*e4b17023SJohn Marino _M_cur = _M_cur->_M_next(); 961*e4b17023SJohn Marino if (_M_cur) 962*e4b17023SJohn Marino { 963*e4b17023SJohn Marino std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count); 964*e4b17023SJohn Marino if (__bkt != _M_bucket) 965*e4b17023SJohn Marino _M_cur = nullptr; 966*e4b17023SJohn Marino } 967*e4b17023SJohn Marino } 968*e4b17023SJohn Marino 969*e4b17023SJohn Marino _Hash_node<_Value, false>* _M_cur; 970*e4b17023SJohn Marino std::size_t _M_bucket; 971*e4b17023SJohn Marino std::size_t _M_bucket_count; 972*e4b17023SJohn Marino }; 973*e4b17023SJohn Marino 974*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 975*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash, bool __cache> 976*e4b17023SJohn Marino inline bool 977*e4b17023SJohn Marino operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, 978*e4b17023SJohn Marino _H1, _H2, _Hash, __cache>& __x, 979*e4b17023SJohn Marino const _Local_iterator_base<_Key, _Value, _ExtractKey, 980*e4b17023SJohn Marino _H1, _H2, _Hash, __cache>& __y) 981*e4b17023SJohn Marino { return __x._M_cur == __y._M_cur; } 982*e4b17023SJohn Marino 983*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 984*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash, bool __cache> 985*e4b17023SJohn Marino inline bool 986*e4b17023SJohn Marino operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, 987*e4b17023SJohn Marino _H1, _H2, _Hash, __cache>& __x, 988*e4b17023SJohn Marino const _Local_iterator_base<_Key, _Value, _ExtractKey, 989*e4b17023SJohn Marino _H1, _H2, _Hash, __cache>& __y) 990*e4b17023SJohn Marino { return __x._M_cur != __y._M_cur; } 991*e4b17023SJohn Marino 992*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 993*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash, 994*e4b17023SJohn Marino bool __constant_iterators, bool __cache> 995*e4b17023SJohn Marino struct _Local_iterator 996*e4b17023SJohn Marino : public _Local_iterator_base<_Key, _Value, _ExtractKey, 997*e4b17023SJohn Marino _H1, _H2, _Hash, __cache> 998*e4b17023SJohn Marino { 999*e4b17023SJohn Marino typedef _Value value_type; 1000*e4b17023SJohn Marino typedef typename std::conditional<__constant_iterators, 1001*e4b17023SJohn Marino const _Value*, _Value*>::type 1002*e4b17023SJohn Marino pointer; 1003*e4b17023SJohn Marino typedef typename std::conditional<__constant_iterators, 1004*e4b17023SJohn Marino const _Value&, _Value&>::type 1005*e4b17023SJohn Marino reference; 1006*e4b17023SJohn Marino typedef std::ptrdiff_t difference_type; 1007*e4b17023SJohn Marino typedef std::forward_iterator_tag iterator_category; 1008*e4b17023SJohn Marino 1009*e4b17023SJohn Marino _Local_iterator() = default; 1010*e4b17023SJohn Marino 1011*e4b17023SJohn Marino explicit 1012*e4b17023SJohn Marino _Local_iterator(_Hash_node<_Value, __cache>* __p, 1013*e4b17023SJohn Marino std::size_t __bkt, std::size_t __bkt_count) 1014*e4b17023SJohn Marino : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 1015*e4b17023SJohn Marino __cache>(__p, __bkt, __bkt_count) 1016*e4b17023SJohn Marino { } 1017*e4b17023SJohn Marino 1018*e4b17023SJohn Marino reference 1019*e4b17023SJohn Marino operator*() const 1020*e4b17023SJohn Marino { return this->_M_cur->_M_v; } 1021*e4b17023SJohn Marino 1022*e4b17023SJohn Marino pointer 1023*e4b17023SJohn Marino operator->() const 1024*e4b17023SJohn Marino { return std::__addressof(this->_M_cur->_M_v); } 1025*e4b17023SJohn Marino 1026*e4b17023SJohn Marino _Local_iterator& 1027*e4b17023SJohn Marino operator++() 1028*e4b17023SJohn Marino { 1029*e4b17023SJohn Marino this->_M_incr(); 1030*e4b17023SJohn Marino return *this; 1031*e4b17023SJohn Marino } 1032*e4b17023SJohn Marino 1033*e4b17023SJohn Marino _Local_iterator 1034*e4b17023SJohn Marino operator++(int) 1035*e4b17023SJohn Marino { 1036*e4b17023SJohn Marino _Local_iterator __tmp(*this); 1037*e4b17023SJohn Marino this->_M_incr(); 1038*e4b17023SJohn Marino return __tmp; 1039*e4b17023SJohn Marino } 1040*e4b17023SJohn Marino }; 1041*e4b17023SJohn Marino 1042*e4b17023SJohn Marino template<typename _Key, typename _Value, typename _ExtractKey, 1043*e4b17023SJohn Marino typename _H1, typename _H2, typename _Hash, 1044*e4b17023SJohn Marino bool __constant_iterators, bool __cache> 1045*e4b17023SJohn Marino struct _Local_const_iterator 1046*e4b17023SJohn Marino : public _Local_iterator_base<_Key, _Value, _ExtractKey, 1047*e4b17023SJohn Marino _H1, _H2, _Hash, __cache> 1048*e4b17023SJohn Marino { 1049*e4b17023SJohn Marino typedef _Value value_type; 1050*e4b17023SJohn Marino typedef const _Value* pointer; 1051*e4b17023SJohn Marino typedef const _Value& reference; 1052*e4b17023SJohn Marino typedef std::ptrdiff_t difference_type; 1053*e4b17023SJohn Marino typedef std::forward_iterator_tag iterator_category; 1054*e4b17023SJohn Marino 1055*e4b17023SJohn Marino _Local_const_iterator() = default; 1056*e4b17023SJohn Marino 1057*e4b17023SJohn Marino explicit 1058*e4b17023SJohn Marino _Local_const_iterator(_Hash_node<_Value, __cache>* __p, 1059*e4b17023SJohn Marino std::size_t __bkt, std::size_t __bkt_count) 1060*e4b17023SJohn Marino : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 1061*e4b17023SJohn Marino __cache>(__p, __bkt, __bkt_count) 1062*e4b17023SJohn Marino { } 1063*e4b17023SJohn Marino 1064*e4b17023SJohn Marino _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 1065*e4b17023SJohn Marino _H1, _H2, _Hash, 1066*e4b17023SJohn Marino __constant_iterators, 1067*e4b17023SJohn Marino __cache>& __x) 1068*e4b17023SJohn Marino : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 1069*e4b17023SJohn Marino __cache>(__x._M_cur, __x._M_bucket, 1070*e4b17023SJohn Marino __x._M_bucket_count) 1071*e4b17023SJohn Marino { } 1072*e4b17023SJohn Marino 1073*e4b17023SJohn Marino reference 1074*e4b17023SJohn Marino operator*() const 1075*e4b17023SJohn Marino { return this->_M_cur->_M_v; } 1076*e4b17023SJohn Marino 1077*e4b17023SJohn Marino pointer 1078*e4b17023SJohn Marino operator->() const 1079*e4b17023SJohn Marino { return std::__addressof(this->_M_cur->_M_v); } 1080*e4b17023SJohn Marino 1081*e4b17023SJohn Marino _Local_const_iterator& 1082*e4b17023SJohn Marino operator++() 1083*e4b17023SJohn Marino { 1084*e4b17023SJohn Marino this->_M_incr(); 1085*e4b17023SJohn Marino return *this; 1086*e4b17023SJohn Marino } 1087*e4b17023SJohn Marino 1088*e4b17023SJohn Marino _Local_const_iterator 1089*e4b17023SJohn Marino operator++(int) 1090*e4b17023SJohn Marino { 1091*e4b17023SJohn Marino _Local_const_iterator __tmp(*this); 1092*e4b17023SJohn Marino this->_M_incr(); 1093*e4b17023SJohn Marino return __tmp; 1094*e4b17023SJohn Marino } 1095*e4b17023SJohn Marino }; 1096*e4b17023SJohn Marino 1097*e4b17023SJohn Marino 1098*e4b17023SJohn Marino // Class template _Equality_base. This is for implementing equality 1099*e4b17023SJohn Marino // comparison for unordered containers, per N3068, by John Lakos and 1100*e4b17023SJohn Marino // Pablo Halpern. Algorithmically, we follow closely the reference 1101*e4b17023SJohn Marino // implementations therein. 1102*e4b17023SJohn Marino template<typename _ExtractKey, bool __unique_keys, 1103*e4b17023SJohn Marino typename _Hashtable> 1104*e4b17023SJohn Marino struct _Equality_base; 1105*e4b17023SJohn Marino 1106*e4b17023SJohn Marino template<typename _ExtractKey, typename _Hashtable> 1107*e4b17023SJohn Marino struct _Equality_base<_ExtractKey, true, _Hashtable> 1108*e4b17023SJohn Marino { 1109*e4b17023SJohn Marino bool _M_equal(const _Hashtable&) const; 1110*e4b17023SJohn Marino }; 1111*e4b17023SJohn Marino 1112*e4b17023SJohn Marino template<typename _ExtractKey, typename _Hashtable> 1113*e4b17023SJohn Marino bool 1114*e4b17023SJohn Marino _Equality_base<_ExtractKey, true, _Hashtable>:: 1115*e4b17023SJohn Marino _M_equal(const _Hashtable& __other) const 1116*e4b17023SJohn Marino { 1117*e4b17023SJohn Marino const _Hashtable* __this = static_cast<const _Hashtable*>(this); 1118*e4b17023SJohn Marino 1119*e4b17023SJohn Marino if (__this->size() != __other.size()) 1120*e4b17023SJohn Marino return false; 1121*e4b17023SJohn Marino 1122*e4b17023SJohn Marino for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 1123*e4b17023SJohn Marino { 1124*e4b17023SJohn Marino const auto __ity = __other.find(_ExtractKey()(*__itx)); 1125*e4b17023SJohn Marino if (__ity == __other.end() || !bool(*__ity == *__itx)) 1126*e4b17023SJohn Marino return false; 1127*e4b17023SJohn Marino } 1128*e4b17023SJohn Marino return true; 1129*e4b17023SJohn Marino } 1130*e4b17023SJohn Marino 1131*e4b17023SJohn Marino template<typename _ExtractKey, typename _Hashtable> 1132*e4b17023SJohn Marino struct _Equality_base<_ExtractKey, false, _Hashtable> 1133*e4b17023SJohn Marino { 1134*e4b17023SJohn Marino bool _M_equal(const _Hashtable&) const; 1135*e4b17023SJohn Marino 1136*e4b17023SJohn Marino private: 1137*e4b17023SJohn Marino template<typename _Uiterator> 1138*e4b17023SJohn Marino static bool 1139*e4b17023SJohn Marino _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 1140*e4b17023SJohn Marino }; 1141*e4b17023SJohn Marino 1142*e4b17023SJohn Marino // See std::is_permutation in N3068. 1143*e4b17023SJohn Marino template<typename _ExtractKey, typename _Hashtable> 1144*e4b17023SJohn Marino template<typename _Uiterator> 1145*e4b17023SJohn Marino bool 1146*e4b17023SJohn Marino _Equality_base<_ExtractKey, false, _Hashtable>:: 1147*e4b17023SJohn Marino _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 1148*e4b17023SJohn Marino _Uiterator __first2) 1149*e4b17023SJohn Marino { 1150*e4b17023SJohn Marino for (; __first1 != __last1; ++__first1, ++__first2) 1151*e4b17023SJohn Marino if (!(*__first1 == *__first2)) 1152*e4b17023SJohn Marino break; 1153*e4b17023SJohn Marino 1154*e4b17023SJohn Marino if (__first1 == __last1) 1155*e4b17023SJohn Marino return true; 1156*e4b17023SJohn Marino 1157*e4b17023SJohn Marino _Uiterator __last2 = __first2; 1158*e4b17023SJohn Marino std::advance(__last2, std::distance(__first1, __last1)); 1159*e4b17023SJohn Marino 1160*e4b17023SJohn Marino for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 1161*e4b17023SJohn Marino { 1162*e4b17023SJohn Marino _Uiterator __tmp = __first1; 1163*e4b17023SJohn Marino while (__tmp != __it1 && !bool(*__tmp == *__it1)) 1164*e4b17023SJohn Marino ++__tmp; 1165*e4b17023SJohn Marino 1166*e4b17023SJohn Marino // We've seen this one before. 1167*e4b17023SJohn Marino if (__tmp != __it1) 1168*e4b17023SJohn Marino continue; 1169*e4b17023SJohn Marino 1170*e4b17023SJohn Marino std::ptrdiff_t __n2 = 0; 1171*e4b17023SJohn Marino for (__tmp = __first2; __tmp != __last2; ++__tmp) 1172*e4b17023SJohn Marino if (*__tmp == *__it1) 1173*e4b17023SJohn Marino ++__n2; 1174*e4b17023SJohn Marino 1175*e4b17023SJohn Marino if (!__n2) 1176*e4b17023SJohn Marino return false; 1177*e4b17023SJohn Marino 1178*e4b17023SJohn Marino std::ptrdiff_t __n1 = 0; 1179*e4b17023SJohn Marino for (__tmp = __it1; __tmp != __last1; ++__tmp) 1180*e4b17023SJohn Marino if (*__tmp == *__it1) 1181*e4b17023SJohn Marino ++__n1; 1182*e4b17023SJohn Marino 1183*e4b17023SJohn Marino if (__n1 != __n2) 1184*e4b17023SJohn Marino return false; 1185*e4b17023SJohn Marino } 1186*e4b17023SJohn Marino return true; 1187*e4b17023SJohn Marino } 1188*e4b17023SJohn Marino 1189*e4b17023SJohn Marino template<typename _ExtractKey, typename _Hashtable> 1190*e4b17023SJohn Marino bool 1191*e4b17023SJohn Marino _Equality_base<_ExtractKey, false, _Hashtable>:: 1192*e4b17023SJohn Marino _M_equal(const _Hashtable& __other) const 1193*e4b17023SJohn Marino { 1194*e4b17023SJohn Marino const _Hashtable* __this = static_cast<const _Hashtable*>(this); 1195*e4b17023SJohn Marino 1196*e4b17023SJohn Marino if (__this->size() != __other.size()) 1197*e4b17023SJohn Marino return false; 1198*e4b17023SJohn Marino 1199*e4b17023SJohn Marino for (auto __itx = __this->begin(); __itx != __this->end();) 1200*e4b17023SJohn Marino { 1201*e4b17023SJohn Marino const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 1202*e4b17023SJohn Marino const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 1203*e4b17023SJohn Marino 1204*e4b17023SJohn Marino if (std::distance(__xrange.first, __xrange.second) 1205*e4b17023SJohn Marino != std::distance(__yrange.first, __yrange.second)) 1206*e4b17023SJohn Marino return false; 1207*e4b17023SJohn Marino 1208*e4b17023SJohn Marino if (!_S_is_permutation(__xrange.first, 1209*e4b17023SJohn Marino __xrange.second, 1210*e4b17023SJohn Marino __yrange.first)) 1211*e4b17023SJohn Marino return false; 1212*e4b17023SJohn Marino 1213*e4b17023SJohn Marino __itx = __xrange.second; 1214*e4b17023SJohn Marino } 1215*e4b17023SJohn Marino return true; 1216*e4b17023SJohn Marino } 1217*e4b17023SJohn Marino 1218*e4b17023SJohn Marino _GLIBCXX_END_NAMESPACE_VERSION 1219*e4b17023SJohn Marino } // namespace __detail 1220*e4b17023SJohn Marino } // namespace std 1221*e4b17023SJohn Marino 1222*e4b17023SJohn Marino #endif // _HASHTABLE_POLICY_H 1223