libstdc++
|
00001 // Internal policy header for unordered_set and unordered_map -*- C++ -*- 00002 00003 // Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file bits/hashtable_policy.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. 00028 * @headername{unordered_map,unordered_set} 00029 */ 00030 00031 #ifndef _HASHTABLE_POLICY_H 00032 #define _HASHTABLE_POLICY_H 1 00033 00034 namespace std _GLIBCXX_VISIBILITY(default) 00035 { 00036 namespace __detail 00037 { 00038 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00039 00040 // Helper function: return distance(first, last) for forward 00041 // iterators, or 0 for input iterators. 00042 template<class _Iterator> 00043 inline typename std::iterator_traits<_Iterator>::difference_type 00044 __distance_fw(_Iterator __first, _Iterator __last, 00045 std::input_iterator_tag) 00046 { return 0; } 00047 00048 template<class _Iterator> 00049 inline typename std::iterator_traits<_Iterator>::difference_type 00050 __distance_fw(_Iterator __first, _Iterator __last, 00051 std::forward_iterator_tag) 00052 { return std::distance(__first, __last); } 00053 00054 template<class _Iterator> 00055 inline typename std::iterator_traits<_Iterator>::difference_type 00056 __distance_fw(_Iterator __first, _Iterator __last) 00057 { 00058 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; 00059 return __distance_fw(__first, __last, _Tag()); 00060 } 00061 00062 // Helper type used to detect when the hash functor is noexcept qualified or 00063 // not 00064 template <typename _Key, typename _Hash> 00065 struct __is_noexcept_hash : std::integral_constant<bool, 00066 noexcept(declval<const _Hash&>()(declval<const _Key&>()))> 00067 {}; 00068 00069 // Auxiliary types used for all instantiations of _Hashtable: nodes 00070 // and iterators. 00071 00072 // Nodes, used to wrap elements stored in the hash table. A policy 00073 // template parameter of class template _Hashtable controls whether 00074 // nodes also store a hash code. In some cases (e.g. strings) this 00075 // may be a performance win. 00076 struct _Hash_node_base 00077 { 00078 _Hash_node_base* _M_nxt; 00079 00080 _Hash_node_base() 00081 : _M_nxt() { } 00082 _Hash_node_base(_Hash_node_base* __next) 00083 : _M_nxt(__next) { } 00084 }; 00085 00086 template<typename _Value, bool __cache_hash_code> 00087 struct _Hash_node; 00088 00089 template<typename _Value> 00090 struct _Hash_node<_Value, true> : _Hash_node_base 00091 { 00092 _Value _M_v; 00093 std::size_t _M_hash_code; 00094 00095 template<typename... _Args> 00096 _Hash_node(_Args&&... __args) 00097 : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { } 00098 00099 _Hash_node* _M_next() const 00100 { return static_cast<_Hash_node*>(_M_nxt); } 00101 }; 00102 00103 template<typename _Value> 00104 struct _Hash_node<_Value, false> : _Hash_node_base 00105 { 00106 _Value _M_v; 00107 00108 template<typename... _Args> 00109 _Hash_node(_Args&&... __args) 00110 : _M_v(std::forward<_Args>(__args)...) { } 00111 00112 _Hash_node* _M_next() const 00113 { return static_cast<_Hash_node*>(_M_nxt); } 00114 }; 00115 00116 // Node iterators, used to iterate through all the hashtable. 00117 template<typename _Value, bool __cache> 00118 struct _Node_iterator_base 00119 { 00120 _Node_iterator_base(_Hash_node<_Value, __cache>* __p) 00121 : _M_cur(__p) { } 00122 00123 void 00124 _M_incr() 00125 { _M_cur = _M_cur->_M_next(); } 00126 00127 _Hash_node<_Value, __cache>* _M_cur; 00128 }; 00129 00130 template<typename _Value, bool __cache> 00131 inline bool 00132 operator==(const _Node_iterator_base<_Value, __cache>& __x, 00133 const _Node_iterator_base<_Value, __cache>& __y) 00134 { return __x._M_cur == __y._M_cur; } 00135 00136 template<typename _Value, bool __cache> 00137 inline bool 00138 operator!=(const _Node_iterator_base<_Value, __cache>& __x, 00139 const _Node_iterator_base<_Value, __cache>& __y) 00140 { return __x._M_cur != __y._M_cur; } 00141 00142 template<typename _Value, bool __constant_iterators, bool __cache> 00143 struct _Node_iterator 00144 : public _Node_iterator_base<_Value, __cache> 00145 { 00146 typedef _Value value_type; 00147 typedef typename std::conditional<__constant_iterators, 00148 const _Value*, _Value*>::type 00149 pointer; 00150 typedef typename std::conditional<__constant_iterators, 00151 const _Value&, _Value&>::type 00152 reference; 00153 typedef std::ptrdiff_t difference_type; 00154 typedef std::forward_iterator_tag iterator_category; 00155 00156 _Node_iterator() 00157 : _Node_iterator_base<_Value, __cache>(0) { } 00158 00159 explicit 00160 _Node_iterator(_Hash_node<_Value, __cache>* __p) 00161 : _Node_iterator_base<_Value, __cache>(__p) { } 00162 00163 reference 00164 operator*() const 00165 { return this->_M_cur->_M_v; } 00166 00167 pointer 00168 operator->() const 00169 { return std::__addressof(this->_M_cur->_M_v); } 00170 00171 _Node_iterator& 00172 operator++() 00173 { 00174 this->_M_incr(); 00175 return *this; 00176 } 00177 00178 _Node_iterator 00179 operator++(int) 00180 { 00181 _Node_iterator __tmp(*this); 00182 this->_M_incr(); 00183 return __tmp; 00184 } 00185 }; 00186 00187 template<typename _Value, bool __constant_iterators, bool __cache> 00188 struct _Node_const_iterator 00189 : public _Node_iterator_base<_Value, __cache> 00190 { 00191 typedef _Value value_type; 00192 typedef const _Value* pointer; 00193 typedef const _Value& reference; 00194 typedef std::ptrdiff_t difference_type; 00195 typedef std::forward_iterator_tag iterator_category; 00196 00197 _Node_const_iterator() 00198 : _Node_iterator_base<_Value, __cache>(0) { } 00199 00200 explicit 00201 _Node_const_iterator(_Hash_node<_Value, __cache>* __p) 00202 : _Node_iterator_base<_Value, __cache>(__p) { } 00203 00204 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 00205 __cache>& __x) 00206 : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } 00207 00208 reference 00209 operator*() const 00210 { return this->_M_cur->_M_v; } 00211 00212 pointer 00213 operator->() const 00214 { return std::__addressof(this->_M_cur->_M_v); } 00215 00216 _Node_const_iterator& 00217 operator++() 00218 { 00219 this->_M_incr(); 00220 return *this; 00221 } 00222 00223 _Node_const_iterator 00224 operator++(int) 00225 { 00226 _Node_const_iterator __tmp(*this); 00227 this->_M_incr(); 00228 return __tmp; 00229 } 00230 }; 00231 00232 // Many of class template _Hashtable's template parameters are policy 00233 // classes. These are defaults for the policies. 00234 00235 // Default range hashing function: use division to fold a large number 00236 // into the range [0, N). 00237 struct _Mod_range_hashing 00238 { 00239 typedef std::size_t first_argument_type; 00240 typedef std::size_t second_argument_type; 00241 typedef std::size_t result_type; 00242 00243 result_type 00244 operator()(first_argument_type __num, second_argument_type __den) const 00245 { return __num % __den; } 00246 }; 00247 00248 // Default ranged hash function H. In principle it should be a 00249 // function object composed from objects of type H1 and H2 such that 00250 // h(k, N) = h2(h1(k), N), but that would mean making extra copies of 00251 // h1 and h2. So instead we'll just use a tag to tell class template 00252 // hashtable to do that composition. 00253 struct _Default_ranged_hash { }; 00254 00255 // Default value for rehash policy. Bucket size is (usually) the 00256 // smallest prime that keeps the load factor small enough. 00257 struct _Prime_rehash_policy 00258 { 00259 _Prime_rehash_policy(float __z = 1.0) 00260 : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { } 00261 00262 float 00263 max_load_factor() const noexcept 00264 { return _M_max_load_factor; } 00265 00266 // Return a bucket size no smaller than n. 00267 std::size_t 00268 _M_next_bkt(std::size_t __n) const; 00269 00270 // Return a bucket count appropriate for n elements 00271 std::size_t 00272 _M_bkt_for_elements(std::size_t __n) const; 00273 00274 // __n_bkt is current bucket count, __n_elt is current element count, 00275 // and __n_ins is number of elements to be inserted. Do we need to 00276 // increase bucket count? If so, return make_pair(true, n), where n 00277 // is the new bucket count. If not, return make_pair(false, 0). 00278 std::pair<bool, std::size_t> 00279 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 00280 std::size_t __n_ins) const; 00281 00282 typedef std::pair<std::size_t, std::size_t> _State; 00283 00284 _State 00285 _M_state() const 00286 { return std::make_pair(_M_prev_resize, _M_next_resize); } 00287 00288 void 00289 _M_reset(const _State& __state) 00290 { 00291 _M_prev_resize = __state.first; 00292 _M_next_resize = __state.second; 00293 } 00294 00295 enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; 00296 00297 float _M_max_load_factor; 00298 mutable std::size_t _M_prev_resize; 00299 mutable std::size_t _M_next_resize; 00300 }; 00301 00302 extern const unsigned long __prime_list[]; 00303 00304 // XXX This is a hack. There's no good reason for any of 00305 // _Prime_rehash_policy's member functions to be inline. 00306 00307 // Return a prime no smaller than n. 00308 inline std::size_t 00309 _Prime_rehash_policy:: 00310 _M_next_bkt(std::size_t __n) const 00311 { 00312 // Optimize lookups involving the first elements of __prime_list. 00313 // (useful to speed-up, eg, constructors) 00314 static const unsigned char __fast_bkt[12] 00315 = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; 00316 00317 if (__n <= 11) 00318 { 00319 _M_prev_resize = 0; 00320 _M_next_resize 00321 = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); 00322 return __fast_bkt[__n]; 00323 } 00324 00325 const unsigned long* __p 00326 = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n); 00327 00328 // Shrink will take place only if the number of elements is small enough 00329 // so that the prime number 2 steps before __p is large enough to still 00330 // conform to the max load factor: 00331 _M_prev_resize 00332 = __builtin_floor(*(__p - 2) * (long double)_M_max_load_factor); 00333 00334 // Let's guaranty that a minimal grow step of 11 is used 00335 if (*__p - __n < 11) 00336 __p = std::lower_bound(__p, __prime_list + _S_n_primes, __n + 11); 00337 _M_next_resize = __builtin_ceil(*__p * (long double)_M_max_load_factor); 00338 return *__p; 00339 } 00340 00341 // Return the smallest prime p such that alpha p >= n, where alpha 00342 // is the load factor. 00343 inline std::size_t 00344 _Prime_rehash_policy:: 00345 _M_bkt_for_elements(std::size_t __n) const 00346 { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); } 00347 00348 // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 00349 // If p > __n_bkt, return make_pair(true, p); otherwise return 00350 // make_pair(false, 0). In principle this isn't very different from 00351 // _M_bkt_for_elements. 00352 00353 // The only tricky part is that we're caching the element count at 00354 // which we need to rehash, so we don't have to do a floating-point 00355 // multiply for every insertion. 00356 00357 inline std::pair<bool, std::size_t> 00358 _Prime_rehash_policy:: 00359 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 00360 std::size_t __n_ins) const 00361 { 00362 if (__n_elt + __n_ins >= _M_next_resize) 00363 { 00364 long double __min_bkts = (__n_elt + __n_ins) 00365 / (long double)_M_max_load_factor; 00366 if (__min_bkts >= __n_bkt) 00367 return std::make_pair(true, 00368 _M_next_bkt(__builtin_floor(__min_bkts) + 1)); 00369 else 00370 { 00371 _M_next_resize 00372 = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); 00373 return std::make_pair(false, 0); 00374 } 00375 } 00376 else if (__n_elt + __n_ins < _M_prev_resize) 00377 { 00378 long double __min_bkts = (__n_elt + __n_ins) 00379 / (long double)_M_max_load_factor; 00380 return std::make_pair(true, 00381 _M_next_bkt(__builtin_floor(__min_bkts) + 1)); 00382 } 00383 else 00384 return std::make_pair(false, 0); 00385 } 00386 00387 // Base classes for std::_Hashtable. We define these base classes 00388 // because in some cases we want to do different things depending 00389 // on the value of a policy class. In some cases the policy class 00390 // affects which member functions and nested typedefs are defined; 00391 // we handle that by specializing base class templates. Several of 00392 // the base class templates need to access other members of class 00393 // template _Hashtable, so we use the "curiously recurring template 00394 // pattern" for them. 00395 00396 // class template _Map_base. If the hashtable has a value type of 00397 // the form pair<T1, T2> and a key extraction policy that returns the 00398 // first part of the pair, the hashtable gets a mapped_type typedef. 00399 // If it satisfies those criteria and also has unique keys, then it 00400 // also gets an operator[]. 00401 template<typename _Key, typename _Value, typename _Ex, bool __unique, 00402 typename _Hashtable> 00403 struct _Map_base { }; 00404 00405 template<typename _Key, typename _Pair, typename _Hashtable> 00406 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> 00407 { 00408 typedef typename _Pair::second_type mapped_type; 00409 }; 00410 00411 template<typename _Key, typename _Pair, typename _Hashtable> 00412 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> 00413 { 00414 typedef typename _Pair::second_type mapped_type; 00415 00416 mapped_type& 00417 operator[](const _Key& __k); 00418 00419 mapped_type& 00420 operator[](_Key&& __k); 00421 00422 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00423 // DR 761. unordered_map needs an at() member function. 00424 mapped_type& 00425 at(const _Key& __k); 00426 00427 const mapped_type& 00428 at(const _Key& __k) const; 00429 }; 00430 00431 template<typename _Key, typename _Pair, typename _Hashtable> 00432 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00433 true, _Hashtable>::mapped_type& 00434 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00435 operator[](const _Key& __k) 00436 { 00437 _Hashtable* __h = static_cast<_Hashtable*>(this); 00438 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00439 std::size_t __n = __h->_M_bucket_index(__k, __code); 00440 00441 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 00442 if (!__p) 00443 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), 00444 __n, __code)->second; 00445 return (__p->_M_v).second; 00446 } 00447 00448 template<typename _Key, typename _Pair, typename _Hashtable> 00449 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00450 true, _Hashtable>::mapped_type& 00451 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00452 operator[](_Key&& __k) 00453 { 00454 _Hashtable* __h = static_cast<_Hashtable*>(this); 00455 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00456 std::size_t __n = __h->_M_bucket_index(__k, __code); 00457 00458 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 00459 if (!__p) 00460 return __h->_M_insert_bucket(std::make_pair(std::move(__k), 00461 mapped_type()), 00462 __n, __code)->second; 00463 return (__p->_M_v).second; 00464 } 00465 00466 template<typename _Key, typename _Pair, typename _Hashtable> 00467 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00468 true, _Hashtable>::mapped_type& 00469 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00470 at(const _Key& __k) 00471 { 00472 _Hashtable* __h = static_cast<_Hashtable*>(this); 00473 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00474 std::size_t __n = __h->_M_bucket_index(__k, __code); 00475 00476 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 00477 if (!__p) 00478 __throw_out_of_range(__N("_Map_base::at")); 00479 return (__p->_M_v).second; 00480 } 00481 00482 template<typename _Key, typename _Pair, typename _Hashtable> 00483 const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00484 true, _Hashtable>::mapped_type& 00485 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00486 at(const _Key& __k) const 00487 { 00488 const _Hashtable* __h = static_cast<const _Hashtable*>(this); 00489 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00490 std::size_t __n = __h->_M_bucket_index(__k, __code); 00491 00492 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 00493 if (!__p) 00494 __throw_out_of_range(__N("_Map_base::at")); 00495 return (__p->_M_v).second; 00496 } 00497 00498 // class template _Rehash_base. Give hashtable the max_load_factor 00499 // functions and reserve iff the rehash policy is _Prime_rehash_policy. 00500 template<typename _RehashPolicy, typename _Hashtable> 00501 struct _Rehash_base { }; 00502 00503 template<typename _Hashtable> 00504 struct _Rehash_base<_Prime_rehash_policy, _Hashtable> 00505 { 00506 float 00507 max_load_factor() const noexcept 00508 { 00509 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 00510 return __this->__rehash_policy().max_load_factor(); 00511 } 00512 00513 void 00514 max_load_factor(float __z) 00515 { 00516 _Hashtable* __this = static_cast<_Hashtable*>(this); 00517 __this->__rehash_policy(_Prime_rehash_policy(__z)); 00518 } 00519 00520 void 00521 reserve(std::size_t __n) 00522 { 00523 _Hashtable* __this = static_cast<_Hashtable*>(this); 00524 __this->rehash(__builtin_ceil(__n / max_load_factor())); 00525 } 00526 }; 00527 00528 // Helper class using EBO when it is not forbidden, type is not final, 00529 // and when it worth it, type is empty. 00530 template<int _Nm, typename _Tp, 00531 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> 00532 struct _Hashtable_ebo_helper; 00533 00534 // Specialization using EBO. 00535 template<int _Nm, typename _Tp> 00536 struct _Hashtable_ebo_helper<_Nm, _Tp, true> 00537 // See PR53067. 00538 : public _Tp 00539 { 00540 _Hashtable_ebo_helper() = default; 00541 _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) 00542 { } 00543 00544 static const _Tp& 00545 _S_cget(const _Hashtable_ebo_helper& __eboh) 00546 { return static_cast<const _Tp&>(__eboh); } 00547 00548 static _Tp& 00549 _S_get(_Hashtable_ebo_helper& __eboh) 00550 { return static_cast<_Tp&>(__eboh); } 00551 }; 00552 00553 // Specialization not using EBO. 00554 template<int _Nm, typename _Tp> 00555 struct _Hashtable_ebo_helper<_Nm, _Tp, false> 00556 { 00557 _Hashtable_ebo_helper() = default; 00558 _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) 00559 { } 00560 00561 static const _Tp& 00562 _S_cget(const _Hashtable_ebo_helper& __eboh) 00563 { return __eboh._M_tp; } 00564 00565 static _Tp& 00566 _S_get(_Hashtable_ebo_helper& __eboh) 00567 { return __eboh._M_tp; } 00568 00569 private: 00570 _Tp _M_tp; 00571 }; 00572 00573 // Class template _Hash_code_base. Encapsulates two policy issues that 00574 // aren't quite orthogonal. 00575 // (1) the difference between using a ranged hash function and using 00576 // the combination of a hash function and a range-hashing function. 00577 // In the former case we don't have such things as hash codes, so 00578 // we have a dummy type as placeholder. 00579 // (2) Whether or not we cache hash codes. Caching hash codes is 00580 // meaningless if we have a ranged hash function. 00581 // We also put the key extraction objects here, for convenience. 00582 // 00583 // Each specialization derives from one or more of the template parameters to 00584 // benefit from Ebo. This is important as this type is inherited in some cases 00585 // by the _Local_iterator_base type used to implement local_iterator and 00586 // const_local_iterator. As with any iterator type we prefer to make it as 00587 // small as possible. 00588 00589 // Primary template: unused except as a hook for specializations. 00590 template<typename _Key, typename _Value, typename _ExtractKey, 00591 typename _H1, typename _H2, typename _Hash, 00592 bool __cache_hash_code> 00593 struct _Hash_code_base; 00594 00595 // Specialization: ranged hash function, no caching hash codes. H1 00596 // and H2 are provided but ignored. We define a dummy hash code type. 00597 template<typename _Key, typename _Value, typename _ExtractKey, 00598 typename _H1, typename _H2, typename _Hash> 00599 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> 00600 // See PR53067. 00601 : public _Hashtable_ebo_helper<0, _ExtractKey>, 00602 public _Hashtable_ebo_helper<1, _Hash> 00603 { 00604 private: 00605 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 00606 typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; 00607 00608 protected: 00609 // We need the default constructor for the local iterators. 00610 _Hash_code_base() = default; 00611 _Hash_code_base(const _ExtractKey& __ex, 00612 const _H1&, const _H2&, const _Hash& __h) 00613 : _EboExtractKey(__ex), _EboHash(__h) { } 00614 00615 typedef void* _Hash_code_type; 00616 00617 _Hash_code_type 00618 _M_hash_code(const _Key& __key) const 00619 { return 0; } 00620 00621 std::size_t 00622 _M_bucket_index(const _Key& __k, _Hash_code_type, 00623 std::size_t __n) const 00624 { return _M_ranged_hash()(__k, __n); } 00625 00626 std::size_t 00627 _M_bucket_index(const _Hash_node<_Value, false>* __p, 00628 std::size_t __n) const 00629 { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } 00630 00631 void 00632 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 00633 { } 00634 00635 void 00636 _M_copy_code(_Hash_node<_Value, false>*, 00637 const _Hash_node<_Value, false>*) const 00638 { } 00639 00640 void 00641 _M_swap(_Hash_code_base& __x) 00642 { 00643 std::swap(_M_extract(), __x._M_extract()); 00644 std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 00645 } 00646 00647 protected: 00648 const _ExtractKey& 00649 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 00650 _ExtractKey& 00651 _M_extract() { return _EboExtractKey::_S_get(*this); } 00652 const _Hash& 00653 _M_ranged_hash() const { return _EboHash::_S_cget(*this); } 00654 _Hash& 00655 _M_ranged_hash() { return _EboHash::_S_get(*this); } 00656 }; 00657 00658 // No specialization for ranged hash function while caching hash codes. 00659 // That combination is meaningless, and trying to do it is an error. 00660 00661 // Specialization: ranged hash function, cache hash codes. This 00662 // combination is meaningless, so we provide only a declaration 00663 // and no definition. 00664 template<typename _Key, typename _Value, typename _ExtractKey, 00665 typename _H1, typename _H2, typename _Hash> 00666 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; 00667 00668 // Specialization: hash function and range-hashing function, no 00669 // caching of hash codes. 00670 // Provides typedef and accessor required by TR1. 00671 template<typename _Key, typename _Value, typename _ExtractKey, 00672 typename _H1, typename _H2> 00673 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 00674 _Default_ranged_hash, false> 00675 // See PR53067. 00676 : public _Hashtable_ebo_helper<0, _ExtractKey>, 00677 public _Hashtable_ebo_helper<1, _H1>, 00678 public _Hashtable_ebo_helper<2, _H2> 00679 { 00680 private: 00681 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 00682 typedef _Hashtable_ebo_helper<1, _H1> _EboH1; 00683 typedef _Hashtable_ebo_helper<2, _H2> _EboH2; 00684 00685 public: 00686 typedef _H1 hasher; 00687 00688 hasher 00689 hash_function() const 00690 { return _M_h1(); } 00691 00692 protected: 00693 // We need the default constructor for the local iterators. 00694 _Hash_code_base() = default; 00695 _Hash_code_base(const _ExtractKey& __ex, 00696 const _H1& __h1, const _H2& __h2, 00697 const _Default_ranged_hash&) 00698 : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } 00699 00700 typedef std::size_t _Hash_code_type; 00701 00702 _Hash_code_type 00703 _M_hash_code(const _Key& __k) const 00704 { return _M_h1()(__k); } 00705 00706 std::size_t 00707 _M_bucket_index(const _Key&, _Hash_code_type __c, 00708 std::size_t __n) const 00709 { return _M_h2()(__c, __n); } 00710 00711 std::size_t 00712 _M_bucket_index(const _Hash_node<_Value, false>* __p, 00713 std::size_t __n) const 00714 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } 00715 00716 void 00717 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 00718 { } 00719 00720 void 00721 _M_copy_code(_Hash_node<_Value, false>*, 00722 const _Hash_node<_Value, false>*) const 00723 { } 00724 00725 void 00726 _M_swap(_Hash_code_base& __x) 00727 { 00728 std::swap(_M_extract(), __x._M_extract()); 00729 std::swap(_M_h1(), __x._M_h1()); 00730 std::swap(_M_h2(), __x._M_h2()); 00731 } 00732 00733 protected: 00734 const _ExtractKey& 00735 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 00736 _ExtractKey& 00737 _M_extract() { return _EboExtractKey::_S_get(*this); } 00738 const _H1& 00739 _M_h1() const { return _EboH1::_S_cget(*this); } 00740 _H1& 00741 _M_h1() { return _EboH1::_S_get(*this); } 00742 const _H2& 00743 _M_h2() const { return _EboH2::_S_cget(*this); } 00744 _H2& 00745 _M_h2() { return _EboH2::_S_get(*this); } 00746 }; 00747 00748 // Specialization: hash function and range-hashing function, 00749 // caching hash codes. H is provided but ignored. Provides 00750 // typedef and accessor required by TR1. 00751 template<typename _Key, typename _Value, typename _ExtractKey, 00752 typename _H1, typename _H2> 00753 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 00754 _Default_ranged_hash, true> 00755 // See PR53067. 00756 : public _Hashtable_ebo_helper<0, _ExtractKey>, 00757 public _Hashtable_ebo_helper<1, _H1>, 00758 public _Hashtable_ebo_helper<2, _H2> 00759 { 00760 private: 00761 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 00762 typedef _Hashtable_ebo_helper<1, _H1> _EboH1; 00763 typedef _Hashtable_ebo_helper<2, _H2> _EboH2; 00764 00765 public: 00766 typedef _H1 hasher; 00767 00768 hasher 00769 hash_function() const 00770 { return _M_h1(); } 00771 00772 protected: 00773 _Hash_code_base(const _ExtractKey& __ex, 00774 const _H1& __h1, const _H2& __h2, 00775 const _Default_ranged_hash&) 00776 : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } 00777 00778 typedef std::size_t _Hash_code_type; 00779 00780 _Hash_code_type 00781 _M_hash_code(const _Key& __k) const 00782 { return _M_h1()(__k); } 00783 00784 std::size_t 00785 _M_bucket_index(const _Key&, _Hash_code_type __c, 00786 std::size_t __n) const 00787 { return _M_h2()(__c, __n); } 00788 00789 std::size_t 00790 _M_bucket_index(const _Hash_node<_Value, true>* __p, 00791 std::size_t __n) const 00792 { return _M_h2()(__p->_M_hash_code, __n); } 00793 00794 void 00795 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const 00796 { __n->_M_hash_code = __c; } 00797 00798 void 00799 _M_copy_code(_Hash_node<_Value, true>* __to, 00800 const _Hash_node<_Value, true>* __from) const 00801 { __to->_M_hash_code = __from->_M_hash_code; } 00802 00803 void 00804 _M_swap(_Hash_code_base& __x) 00805 { 00806 std::swap(_M_extract(), __x._M_extract()); 00807 std::swap(_M_h1(), __x._M_h1()); 00808 std::swap(_M_h2(), __x._M_h2()); 00809 } 00810 00811 protected: 00812 const _ExtractKey& 00813 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 00814 _ExtractKey& 00815 _M_extract() { return _EboExtractKey::_S_get(*this); } 00816 const _H1& 00817 _M_h1() const { return _EboH1::_S_cget(*this); } 00818 _H1& 00819 _M_h1() { return _EboH1::_S_get(*this); } 00820 const _H2& 00821 _M_h2() const { return _EboH2::_S_cget(*this); } 00822 _H2& 00823 _M_h2() { return _EboH2::_S_get(*this); } 00824 }; 00825 00826 template <typename _Key, typename _Value, typename _ExtractKey, 00827 typename _Equal, typename _HashCodeType, 00828 bool __cache_hash_code> 00829 struct _Equal_helper; 00830 00831 template<typename _Key, typename _Value, typename _ExtractKey, 00832 typename _Equal, typename _HashCodeType> 00833 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> 00834 { 00835 static bool 00836 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 00837 const _Key& __k, _HashCodeType __c, 00838 _Hash_node<_Value, true>* __n) 00839 { return __c == __n->_M_hash_code 00840 && __eq(__k, __extract(__n->_M_v)); } 00841 }; 00842 00843 template<typename _Key, typename _Value, typename _ExtractKey, 00844 typename _Equal, typename _HashCodeType> 00845 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> 00846 { 00847 static bool 00848 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 00849 const _Key& __k, _HashCodeType, 00850 _Hash_node<_Value, false>* __n) 00851 { return __eq(__k, __extract(__n->_M_v)); } 00852 }; 00853 00854 // Helper class adding management of _Equal functor to _Hash_code_base 00855 // type. 00856 template<typename _Key, typename _Value, 00857 typename _ExtractKey, typename _Equal, 00858 typename _H1, typename _H2, typename _Hash, 00859 bool __cache_hash_code> 00860 struct _Hashtable_base 00861 // See PR53067. 00862 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 00863 __cache_hash_code>, 00864 public _Hashtable_ebo_helper<0, _Equal> 00865 { 00866 private: 00867 typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual; 00868 00869 protected: 00870 typedef _Hash_code_base<_Key, _Value, _ExtractKey, 00871 _H1, _H2, _Hash, __cache_hash_code> _HCBase; 00872 typedef typename _HCBase::_Hash_code_type _Hash_code_type; 00873 00874 _Hashtable_base(const _ExtractKey& __ex, 00875 const _H1& __h1, const _H2& __h2, 00876 const _Hash& __hash, const _Equal& __eq) 00877 : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { } 00878 00879 bool 00880 _M_equals(const _Key& __k, _Hash_code_type __c, 00881 _Hash_node<_Value, __cache_hash_code>* __n) const 00882 { 00883 typedef _Equal_helper<_Key, _Value, _ExtractKey, 00884 _Equal, _Hash_code_type, 00885 __cache_hash_code> _EqualHelper; 00886 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 00887 __k, __c, __n); 00888 } 00889 00890 void 00891 _M_swap(_Hashtable_base& __x) 00892 { 00893 _HCBase::_M_swap(__x); 00894 std::swap(_M_eq(), __x._M_eq()); 00895 } 00896 00897 protected: 00898 const _Equal& 00899 _M_eq() const { return _EboEqual::_S_cget(*this); } 00900 _Equal& 00901 _M_eq() { return _EboEqual::_S_get(*this); } 00902 }; 00903 00904 // Local iterators, used to iterate within a bucket but not between 00905 // buckets. 00906 template<typename _Key, typename _Value, typename _ExtractKey, 00907 typename _H1, typename _H2, typename _Hash, 00908 bool __cache_hash_code> 00909 struct _Local_iterator_base; 00910 00911 template<typename _Key, typename _Value, typename _ExtractKey, 00912 typename _H1, typename _H2, typename _Hash> 00913 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 00914 _H1, _H2, _Hash, true> 00915 // See PR53067. 00916 : public _H2 00917 { 00918 _Local_iterator_base() = default; 00919 _Local_iterator_base(_Hash_node<_Value, true>* __p, 00920 std::size_t __bkt, std::size_t __bkt_count) 00921 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 00922 00923 void 00924 _M_incr() 00925 { 00926 _M_cur = _M_cur->_M_next(); 00927 if (_M_cur) 00928 { 00929 std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count); 00930 if (__bkt != _M_bucket) 00931 _M_cur = nullptr; 00932 } 00933 } 00934 00935 const _H2& _M_h2() const 00936 { return *this; } 00937 00938 _Hash_node<_Value, true>* _M_cur; 00939 std::size_t _M_bucket; 00940 std::size_t _M_bucket_count; 00941 }; 00942 00943 template<typename _Key, typename _Value, typename _ExtractKey, 00944 typename _H1, typename _H2, typename _Hash> 00945 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 00946 _H1, _H2, _Hash, false> 00947 // See PR53067. 00948 : public _Hash_code_base<_Key, _Value, _ExtractKey, 00949 _H1, _H2, _Hash, false> 00950 { 00951 _Local_iterator_base() = default; 00952 _Local_iterator_base(_Hash_node<_Value, false>* __p, 00953 std::size_t __bkt, std::size_t __bkt_count) 00954 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 00955 00956 void 00957 _M_incr() 00958 { 00959 _M_cur = _M_cur->_M_next(); 00960 if (_M_cur) 00961 { 00962 std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count); 00963 if (__bkt != _M_bucket) 00964 _M_cur = nullptr; 00965 } 00966 } 00967 00968 _Hash_node<_Value, false>* _M_cur; 00969 std::size_t _M_bucket; 00970 std::size_t _M_bucket_count; 00971 }; 00972 00973 template<typename _Key, typename _Value, typename _ExtractKey, 00974 typename _H1, typename _H2, typename _Hash, bool __cache> 00975 inline bool 00976 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, 00977 _H1, _H2, _Hash, __cache>& __x, 00978 const _Local_iterator_base<_Key, _Value, _ExtractKey, 00979 _H1, _H2, _Hash, __cache>& __y) 00980 { return __x._M_cur == __y._M_cur; } 00981 00982 template<typename _Key, typename _Value, typename _ExtractKey, 00983 typename _H1, typename _H2, typename _Hash, bool __cache> 00984 inline bool 00985 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, 00986 _H1, _H2, _Hash, __cache>& __x, 00987 const _Local_iterator_base<_Key, _Value, _ExtractKey, 00988 _H1, _H2, _Hash, __cache>& __y) 00989 { return __x._M_cur != __y._M_cur; } 00990 00991 template<typename _Key, typename _Value, typename _ExtractKey, 00992 typename _H1, typename _H2, typename _Hash, 00993 bool __constant_iterators, bool __cache> 00994 struct _Local_iterator 00995 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 00996 _H1, _H2, _Hash, __cache> 00997 { 00998 typedef _Value value_type; 00999 typedef typename std::conditional<__constant_iterators, 01000 const _Value*, _Value*>::type 01001 pointer; 01002 typedef typename std::conditional<__constant_iterators, 01003 const _Value&, _Value&>::type 01004 reference; 01005 typedef std::ptrdiff_t difference_type; 01006 typedef std::forward_iterator_tag iterator_category; 01007 01008 _Local_iterator() = default; 01009 01010 explicit 01011 _Local_iterator(_Hash_node<_Value, __cache>* __p, 01012 std::size_t __bkt, std::size_t __bkt_count) 01013 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 01014 __cache>(__p, __bkt, __bkt_count) 01015 { } 01016 01017 reference 01018 operator*() const 01019 { return this->_M_cur->_M_v; } 01020 01021 pointer 01022 operator->() const 01023 { return std::__addressof(this->_M_cur->_M_v); } 01024 01025 _Local_iterator& 01026 operator++() 01027 { 01028 this->_M_incr(); 01029 return *this; 01030 } 01031 01032 _Local_iterator 01033 operator++(int) 01034 { 01035 _Local_iterator __tmp(*this); 01036 this->_M_incr(); 01037 return __tmp; 01038 } 01039 }; 01040 01041 template<typename _Key, typename _Value, typename _ExtractKey, 01042 typename _H1, typename _H2, typename _Hash, 01043 bool __constant_iterators, bool __cache> 01044 struct _Local_const_iterator 01045 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 01046 _H1, _H2, _Hash, __cache> 01047 { 01048 typedef _Value value_type; 01049 typedef const _Value* pointer; 01050 typedef const _Value& reference; 01051 typedef std::ptrdiff_t difference_type; 01052 typedef std::forward_iterator_tag iterator_category; 01053 01054 _Local_const_iterator() = default; 01055 01056 explicit 01057 _Local_const_iterator(_Hash_node<_Value, __cache>* __p, 01058 std::size_t __bkt, std::size_t __bkt_count) 01059 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 01060 __cache>(__p, __bkt, __bkt_count) 01061 { } 01062 01063 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 01064 _H1, _H2, _Hash, 01065 __constant_iterators, 01066 __cache>& __x) 01067 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 01068 __cache>(__x._M_cur, __x._M_bucket, 01069 __x._M_bucket_count) 01070 { } 01071 01072 reference 01073 operator*() const 01074 { return this->_M_cur->_M_v; } 01075 01076 pointer 01077 operator->() const 01078 { return std::__addressof(this->_M_cur->_M_v); } 01079 01080 _Local_const_iterator& 01081 operator++() 01082 { 01083 this->_M_incr(); 01084 return *this; 01085 } 01086 01087 _Local_const_iterator 01088 operator++(int) 01089 { 01090 _Local_const_iterator __tmp(*this); 01091 this->_M_incr(); 01092 return __tmp; 01093 } 01094 }; 01095 01096 01097 // Class template _Equality_base. This is for implementing equality 01098 // comparison for unordered containers, per N3068, by John Lakos and 01099 // Pablo Halpern. Algorithmically, we follow closely the reference 01100 // implementations therein. 01101 template<typename _ExtractKey, bool __unique_keys, 01102 typename _Hashtable> 01103 struct _Equality_base; 01104 01105 template<typename _ExtractKey, typename _Hashtable> 01106 struct _Equality_base<_ExtractKey, true, _Hashtable> 01107 { 01108 bool _M_equal(const _Hashtable&) const; 01109 }; 01110 01111 template<typename _ExtractKey, typename _Hashtable> 01112 bool 01113 _Equality_base<_ExtractKey, true, _Hashtable>:: 01114 _M_equal(const _Hashtable& __other) const 01115 { 01116 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 01117 01118 if (__this->size() != __other.size()) 01119 return false; 01120 01121 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 01122 { 01123 const auto __ity = __other.find(_ExtractKey()(*__itx)); 01124 if (__ity == __other.end() || !bool(*__ity == *__itx)) 01125 return false; 01126 } 01127 return true; 01128 } 01129 01130 template<typename _ExtractKey, typename _Hashtable> 01131 struct _Equality_base<_ExtractKey, false, _Hashtable> 01132 { 01133 bool _M_equal(const _Hashtable&) const; 01134 01135 private: 01136 template<typename _Uiterator> 01137 static bool 01138 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 01139 }; 01140 01141 // See std::is_permutation in N3068. 01142 template<typename _ExtractKey, typename _Hashtable> 01143 template<typename _Uiterator> 01144 bool 01145 _Equality_base<_ExtractKey, false, _Hashtable>:: 01146 _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 01147 _Uiterator __first2) 01148 { 01149 for (; __first1 != __last1; ++__first1, ++__first2) 01150 if (!(*__first1 == *__first2)) 01151 break; 01152 01153 if (__first1 == __last1) 01154 return true; 01155 01156 _Uiterator __last2 = __first2; 01157 std::advance(__last2, std::distance(__first1, __last1)); 01158 01159 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 01160 { 01161 _Uiterator __tmp = __first1; 01162 while (__tmp != __it1 && !bool(*__tmp == *__it1)) 01163 ++__tmp; 01164 01165 // We've seen this one before. 01166 if (__tmp != __it1) 01167 continue; 01168 01169 std::ptrdiff_t __n2 = 0; 01170 for (__tmp = __first2; __tmp != __last2; ++__tmp) 01171 if (*__tmp == *__it1) 01172 ++__n2; 01173 01174 if (!__n2) 01175 return false; 01176 01177 std::ptrdiff_t __n1 = 0; 01178 for (__tmp = __it1; __tmp != __last1; ++__tmp) 01179 if (*__tmp == *__it1) 01180 ++__n1; 01181 01182 if (__n1 != __n2) 01183 return false; 01184 } 01185 return true; 01186 } 01187 01188 template<typename _ExtractKey, typename _Hashtable> 01189 bool 01190 _Equality_base<_ExtractKey, false, _Hashtable>:: 01191 _M_equal(const _Hashtable& __other) const 01192 { 01193 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 01194 01195 if (__this->size() != __other.size()) 01196 return false; 01197 01198 for (auto __itx = __this->begin(); __itx != __this->end();) 01199 { 01200 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 01201 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 01202 01203 if (std::distance(__xrange.first, __xrange.second) 01204 != std::distance(__yrange.first, __yrange.second)) 01205 return false; 01206 01207 if (!_S_is_permutation(__xrange.first, 01208 __xrange.second, 01209 __yrange.first)) 01210 return false; 01211 01212 __itx = __xrange.second; 01213 } 01214 return true; 01215 } 01216 01217 _GLIBCXX_END_NAMESPACE_VERSION 01218 } // namespace __detail 01219 } // namespace std 01220 01221 #endif // _HASHTABLE_POLICY_H