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 static const std::size_t _S_growth_factor = 2; 00298 00299 float _M_max_load_factor; 00300 mutable std::size_t _M_prev_resize; 00301 mutable std::size_t _M_next_resize; 00302 }; 00303 00304 extern const unsigned long __prime_list[]; 00305 00306 // XXX This is a hack. There's no good reason for any of 00307 // _Prime_rehash_policy's member functions to be inline. 00308 00309 // Return a prime no smaller than n. 00310 inline std::size_t 00311 _Prime_rehash_policy:: 00312 _M_next_bkt(std::size_t __n) const 00313 { 00314 // Optimize lookups involving the first elements of __prime_list. 00315 // (useful to speed-up, eg, constructors) 00316 static const unsigned char __fast_bkt[12] 00317 = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; 00318 00319 const std::size_t __grown_n = __n * _S_growth_factor; 00320 if (__grown_n <= 11) 00321 { 00322 _M_prev_resize = 0; 00323 _M_next_resize 00324 = __builtin_ceil(__fast_bkt[__grown_n] 00325 * (long double)_M_max_load_factor); 00326 return __fast_bkt[__grown_n]; 00327 } 00328 00329 const unsigned long* __next_bkt 00330 = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, 00331 __grown_n); 00332 const unsigned long* __prev_bkt 00333 = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor); 00334 00335 _M_prev_resize 00336 = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor); 00337 _M_next_resize 00338 = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); 00339 return *__next_bkt; 00340 } 00341 00342 // Return the smallest prime p such that alpha p >= n, where alpha 00343 // is the load factor. 00344 inline std::size_t 00345 _Prime_rehash_policy:: 00346 _M_bkt_for_elements(std::size_t __n) const 00347 { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); } 00348 00349 // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 00350 // If p > __n_bkt, return make_pair(true, p); otherwise return 00351 // make_pair(false, 0). In principle this isn't very different from 00352 // _M_bkt_for_elements. 00353 00354 // The only tricky part is that we're caching the element count at 00355 // which we need to rehash, so we don't have to do a floating-point 00356 // multiply for every insertion. 00357 00358 inline std::pair<bool, std::size_t> 00359 _Prime_rehash_policy:: 00360 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 00361 std::size_t __n_ins) const 00362 { 00363 if (__n_elt + __n_ins >= _M_next_resize) 00364 { 00365 long double __min_bkts = (__n_elt + __n_ins) 00366 / (long double)_M_max_load_factor; 00367 if (__min_bkts >= __n_bkt) 00368 return std::make_pair(true, 00369 _M_next_bkt(__builtin_floor(__min_bkts) + 1)); 00370 else 00371 { 00372 _M_next_resize 00373 = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); 00374 return std::make_pair(false, 0); 00375 } 00376 } 00377 else if (__n_elt + __n_ins < _M_prev_resize) 00378 { 00379 long double __min_bkts = (__n_elt + __n_ins) 00380 / (long double)_M_max_load_factor; 00381 return std::make_pair(true, 00382 _M_next_bkt(__builtin_floor(__min_bkts) + 1)); 00383 } 00384 else 00385 return std::make_pair(false, 0); 00386 } 00387 00388 // Base classes for std::_Hashtable. We define these base classes 00389 // because in some cases we want to do different things depending 00390 // on the value of a policy class. In some cases the policy class 00391 // affects which member functions and nested typedefs are defined; 00392 // we handle that by specializing base class templates. Several of 00393 // the base class templates need to access other members of class 00394 // template _Hashtable, so we use the "curiously recurring template 00395 // pattern" for them. 00396 00397 // class template _Map_base. If the hashtable has a value type of 00398 // the form pair<T1, T2> and a key extraction policy that returns the 00399 // first part of the pair, the hashtable gets a mapped_type typedef. 00400 // If it satisfies those criteria and also has unique keys, then it 00401 // also gets an operator[]. 00402 template<typename _Key, typename _Value, typename _Ex, bool __unique, 00403 typename _Hashtable> 00404 struct _Map_base { }; 00405 00406 template<typename _Key, typename _Pair, typename _Hashtable> 00407 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> 00408 { 00409 typedef typename _Pair::second_type mapped_type; 00410 }; 00411 00412 template<typename _Key, typename _Pair, typename _Hashtable> 00413 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> 00414 { 00415 typedef typename _Pair::second_type mapped_type; 00416 00417 mapped_type& 00418 operator[](const _Key& __k); 00419 00420 mapped_type& 00421 operator[](_Key&& __k); 00422 00423 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00424 // DR 761. unordered_map needs an at() member function. 00425 mapped_type& 00426 at(const _Key& __k); 00427 00428 const mapped_type& 00429 at(const _Key& __k) const; 00430 }; 00431 00432 template<typename _Key, typename _Pair, typename _Hashtable> 00433 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00434 true, _Hashtable>::mapped_type& 00435 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00436 operator[](const _Key& __k) 00437 { 00438 _Hashtable* __h = static_cast<_Hashtable*>(this); 00439 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00440 std::size_t __n = __h->_M_bucket_index(__k, __code); 00441 00442 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 00443 if (!__p) 00444 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), 00445 __n, __code)->second; 00446 return (__p->_M_v).second; 00447 } 00448 00449 template<typename _Key, typename _Pair, typename _Hashtable> 00450 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00451 true, _Hashtable>::mapped_type& 00452 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00453 operator[](_Key&& __k) 00454 { 00455 _Hashtable* __h = static_cast<_Hashtable*>(this); 00456 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00457 std::size_t __n = __h->_M_bucket_index(__k, __code); 00458 00459 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 00460 if (!__p) 00461 return __h->_M_insert_bucket(std::make_pair(std::move(__k), 00462 mapped_type()), 00463 __n, __code)->second; 00464 return (__p->_M_v).second; 00465 } 00466 00467 template<typename _Key, typename _Pair, typename _Hashtable> 00468 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00469 true, _Hashtable>::mapped_type& 00470 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00471 at(const _Key& __k) 00472 { 00473 _Hashtable* __h = static_cast<_Hashtable*>(this); 00474 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00475 std::size_t __n = __h->_M_bucket_index(__k, __code); 00476 00477 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 00478 if (!__p) 00479 __throw_out_of_range(__N("_Map_base::at")); 00480 return (__p->_M_v).second; 00481 } 00482 00483 template<typename _Key, typename _Pair, typename _Hashtable> 00484 const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00485 true, _Hashtable>::mapped_type& 00486 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00487 at(const _Key& __k) const 00488 { 00489 const _Hashtable* __h = static_cast<const _Hashtable*>(this); 00490 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00491 std::size_t __n = __h->_M_bucket_index(__k, __code); 00492 00493 typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); 00494 if (!__p) 00495 __throw_out_of_range(__N("_Map_base::at")); 00496 return (__p->_M_v).second; 00497 } 00498 00499 // class template _Rehash_base. Give hashtable the max_load_factor 00500 // functions and reserve iff the rehash policy is _Prime_rehash_policy. 00501 template<typename _RehashPolicy, typename _Hashtable> 00502 struct _Rehash_base { }; 00503 00504 template<typename _Hashtable> 00505 struct _Rehash_base<_Prime_rehash_policy, _Hashtable> 00506 { 00507 float 00508 max_load_factor() const noexcept 00509 { 00510 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 00511 return __this->__rehash_policy().max_load_factor(); 00512 } 00513 00514 void 00515 max_load_factor(float __z) 00516 { 00517 _Hashtable* __this = static_cast<_Hashtable*>(this); 00518 __this->__rehash_policy(_Prime_rehash_policy(__z)); 00519 } 00520 00521 void 00522 reserve(std::size_t __n) 00523 { 00524 _Hashtable* __this = static_cast<_Hashtable*>(this); 00525 __this->rehash(__builtin_ceil(__n / max_load_factor())); 00526 } 00527 }; 00528 00529 // Helper class using EBO when it is not forbidden, type is not final, 00530 // and when it worth it, type is empty. 00531 template<int _Nm, typename _Tp, 00532 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> 00533 struct _Hashtable_ebo_helper; 00534 00535 // Specialization using EBO. 00536 template<int _Nm, typename _Tp> 00537 struct _Hashtable_ebo_helper<_Nm, _Tp, true> 00538 // See PR53067. 00539 : public _Tp 00540 { 00541 _Hashtable_ebo_helper() = default; 00542 _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) 00543 { } 00544 00545 static const _Tp& 00546 _S_cget(const _Hashtable_ebo_helper& __eboh) 00547 { return static_cast<const _Tp&>(__eboh); } 00548 00549 static _Tp& 00550 _S_get(_Hashtable_ebo_helper& __eboh) 00551 { return static_cast<_Tp&>(__eboh); } 00552 }; 00553 00554 // Specialization not using EBO. 00555 template<int _Nm, typename _Tp> 00556 struct _Hashtable_ebo_helper<_Nm, _Tp, false> 00557 { 00558 _Hashtable_ebo_helper() = default; 00559 _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) 00560 { } 00561 00562 static const _Tp& 00563 _S_cget(const _Hashtable_ebo_helper& __eboh) 00564 { return __eboh._M_tp; } 00565 00566 static _Tp& 00567 _S_get(_Hashtable_ebo_helper& __eboh) 00568 { return __eboh._M_tp; } 00569 00570 private: 00571 _Tp _M_tp; 00572 }; 00573 00574 // Class template _Hash_code_base. Encapsulates two policy issues that 00575 // aren't quite orthogonal. 00576 // (1) the difference between using a ranged hash function and using 00577 // the combination of a hash function and a range-hashing function. 00578 // In the former case we don't have such things as hash codes, so 00579 // we have a dummy type as placeholder. 00580 // (2) Whether or not we cache hash codes. Caching hash codes is 00581 // meaningless if we have a ranged hash function. 00582 // We also put the key extraction objects here, for convenience. 00583 // 00584 // Each specialization derives from one or more of the template parameters to 00585 // benefit from Ebo. This is important as this type is inherited in some cases 00586 // by the _Local_iterator_base type used to implement local_iterator and 00587 // const_local_iterator. As with any iterator type we prefer to make it as 00588 // small as possible. 00589 00590 // Primary template: unused except as a hook for specializations. 00591 template<typename _Key, typename _Value, typename _ExtractKey, 00592 typename _H1, typename _H2, typename _Hash, 00593 bool __cache_hash_code> 00594 struct _Hash_code_base; 00595 00596 // Specialization: ranged hash function, no caching hash codes. H1 00597 // and H2 are provided but ignored. We define a dummy hash code type. 00598 template<typename _Key, typename _Value, typename _ExtractKey, 00599 typename _H1, typename _H2, typename _Hash> 00600 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> 00601 // See PR53067. 00602 : public _Hashtable_ebo_helper<0, _ExtractKey>, 00603 public _Hashtable_ebo_helper<1, _Hash> 00604 { 00605 private: 00606 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 00607 typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; 00608 00609 protected: 00610 // We need the default constructor for the local iterators. 00611 _Hash_code_base() = default; 00612 _Hash_code_base(const _ExtractKey& __ex, 00613 const _H1&, const _H2&, const _Hash& __h) 00614 : _EboExtractKey(__ex), _EboHash(__h) { } 00615 00616 typedef void* _Hash_code_type; 00617 00618 _Hash_code_type 00619 _M_hash_code(const _Key& __key) const 00620 { return 0; } 00621 00622 std::size_t 00623 _M_bucket_index(const _Key& __k, _Hash_code_type, 00624 std::size_t __n) const 00625 { return _M_ranged_hash()(__k, __n); } 00626 00627 std::size_t 00628 _M_bucket_index(const _Hash_node<_Value, false>* __p, 00629 std::size_t __n) const 00630 { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } 00631 00632 void 00633 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 00634 { } 00635 00636 void 00637 _M_copy_code(_Hash_node<_Value, false>*, 00638 const _Hash_node<_Value, false>*) const 00639 { } 00640 00641 void 00642 _M_swap(_Hash_code_base& __x) 00643 { 00644 std::swap(_M_extract(), __x._M_extract()); 00645 std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 00646 } 00647 00648 protected: 00649 const _ExtractKey& 00650 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 00651 _ExtractKey& 00652 _M_extract() { return _EboExtractKey::_S_get(*this); } 00653 const _Hash& 00654 _M_ranged_hash() const { return _EboHash::_S_cget(*this); } 00655 _Hash& 00656 _M_ranged_hash() { return _EboHash::_S_get(*this); } 00657 }; 00658 00659 // No specialization for ranged hash function while caching hash codes. 00660 // That combination is meaningless, and trying to do it is an error. 00661 00662 // Specialization: ranged hash function, cache hash codes. This 00663 // combination is meaningless, so we provide only a declaration 00664 // and no definition. 00665 template<typename _Key, typename _Value, typename _ExtractKey, 00666 typename _H1, typename _H2, typename _Hash> 00667 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; 00668 00669 // Specialization: hash function and range-hashing function, no 00670 // caching of hash codes. 00671 // Provides typedef and accessor required by TR1. 00672 template<typename _Key, typename _Value, typename _ExtractKey, 00673 typename _H1, typename _H2> 00674 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 00675 _Default_ranged_hash, false> 00676 // See PR53067. 00677 : public _Hashtable_ebo_helper<0, _ExtractKey>, 00678 public _Hashtable_ebo_helper<1, _H1>, 00679 public _Hashtable_ebo_helper<2, _H2> 00680 { 00681 private: 00682 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 00683 typedef _Hashtable_ebo_helper<1, _H1> _EboH1; 00684 typedef _Hashtable_ebo_helper<2, _H2> _EboH2; 00685 00686 public: 00687 typedef _H1 hasher; 00688 00689 hasher 00690 hash_function() const 00691 { return _M_h1(); } 00692 00693 protected: 00694 // We need the default constructor for the local iterators. 00695 _Hash_code_base() = default; 00696 _Hash_code_base(const _ExtractKey& __ex, 00697 const _H1& __h1, const _H2& __h2, 00698 const _Default_ranged_hash&) 00699 : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } 00700 00701 typedef std::size_t _Hash_code_type; 00702 00703 _Hash_code_type 00704 _M_hash_code(const _Key& __k) const 00705 { return _M_h1()(__k); } 00706 00707 std::size_t 00708 _M_bucket_index(const _Key&, _Hash_code_type __c, 00709 std::size_t __n) const 00710 { return _M_h2()(__c, __n); } 00711 00712 std::size_t 00713 _M_bucket_index(const _Hash_node<_Value, false>* __p, 00714 std::size_t __n) const 00715 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } 00716 00717 void 00718 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 00719 { } 00720 00721 void 00722 _M_copy_code(_Hash_node<_Value, false>*, 00723 const _Hash_node<_Value, false>*) const 00724 { } 00725 00726 void 00727 _M_swap(_Hash_code_base& __x) 00728 { 00729 std::swap(_M_extract(), __x._M_extract()); 00730 std::swap(_M_h1(), __x._M_h1()); 00731 std::swap(_M_h2(), __x._M_h2()); 00732 } 00733 00734 protected: 00735 const _ExtractKey& 00736 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 00737 _ExtractKey& 00738 _M_extract() { return _EboExtractKey::_S_get(*this); } 00739 const _H1& 00740 _M_h1() const { return _EboH1::_S_cget(*this); } 00741 _H1& 00742 _M_h1() { return _EboH1::_S_get(*this); } 00743 const _H2& 00744 _M_h2() const { return _EboH2::_S_cget(*this); } 00745 _H2& 00746 _M_h2() { return _EboH2::_S_get(*this); } 00747 }; 00748 00749 // Specialization: hash function and range-hashing function, 00750 // caching hash codes. H is provided but ignored. Provides 00751 // typedef and accessor required by TR1. 00752 template<typename _Key, typename _Value, typename _ExtractKey, 00753 typename _H1, typename _H2> 00754 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 00755 _Default_ranged_hash, true> 00756 // See PR53067. 00757 : public _Hashtable_ebo_helper<0, _ExtractKey>, 00758 public _Hashtable_ebo_helper<1, _H1>, 00759 public _Hashtable_ebo_helper<2, _H2> 00760 { 00761 private: 00762 typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; 00763 typedef _Hashtable_ebo_helper<1, _H1> _EboH1; 00764 typedef _Hashtable_ebo_helper<2, _H2> _EboH2; 00765 00766 public: 00767 typedef _H1 hasher; 00768 00769 hasher 00770 hash_function() const 00771 { return _M_h1(); } 00772 00773 protected: 00774 _Hash_code_base(const _ExtractKey& __ex, 00775 const _H1& __h1, const _H2& __h2, 00776 const _Default_ranged_hash&) 00777 : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } 00778 00779 typedef std::size_t _Hash_code_type; 00780 00781 _Hash_code_type 00782 _M_hash_code(const _Key& __k) const 00783 { return _M_h1()(__k); } 00784 00785 std::size_t 00786 _M_bucket_index(const _Key&, _Hash_code_type __c, 00787 std::size_t __n) const 00788 { return _M_h2()(__c, __n); } 00789 00790 std::size_t 00791 _M_bucket_index(const _Hash_node<_Value, true>* __p, 00792 std::size_t __n) const 00793 { return _M_h2()(__p->_M_hash_code, __n); } 00794 00795 void 00796 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const 00797 { __n->_M_hash_code = __c; } 00798 00799 void 00800 _M_copy_code(_Hash_node<_Value, true>* __to, 00801 const _Hash_node<_Value, true>* __from) const 00802 { __to->_M_hash_code = __from->_M_hash_code; } 00803 00804 void 00805 _M_swap(_Hash_code_base& __x) 00806 { 00807 std::swap(_M_extract(), __x._M_extract()); 00808 std::swap(_M_h1(), __x._M_h1()); 00809 std::swap(_M_h2(), __x._M_h2()); 00810 } 00811 00812 protected: 00813 const _ExtractKey& 00814 _M_extract() const { return _EboExtractKey::_S_cget(*this); } 00815 _ExtractKey& 00816 _M_extract() { return _EboExtractKey::_S_get(*this); } 00817 const _H1& 00818 _M_h1() const { return _EboH1::_S_cget(*this); } 00819 _H1& 00820 _M_h1() { return _EboH1::_S_get(*this); } 00821 const _H2& 00822 _M_h2() const { return _EboH2::_S_cget(*this); } 00823 _H2& 00824 _M_h2() { return _EboH2::_S_get(*this); } 00825 }; 00826 00827 template <typename _Key, typename _Value, typename _ExtractKey, 00828 typename _Equal, typename _HashCodeType, 00829 bool __cache_hash_code> 00830 struct _Equal_helper; 00831 00832 template<typename _Key, typename _Value, typename _ExtractKey, 00833 typename _Equal, typename _HashCodeType> 00834 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> 00835 { 00836 static bool 00837 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 00838 const _Key& __k, _HashCodeType __c, 00839 _Hash_node<_Value, true>* __n) 00840 { return __c == __n->_M_hash_code 00841 && __eq(__k, __extract(__n->_M_v)); } 00842 }; 00843 00844 template<typename _Key, typename _Value, typename _ExtractKey, 00845 typename _Equal, typename _HashCodeType> 00846 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> 00847 { 00848 static bool 00849 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 00850 const _Key& __k, _HashCodeType, 00851 _Hash_node<_Value, false>* __n) 00852 { return __eq(__k, __extract(__n->_M_v)); } 00853 }; 00854 00855 // Helper class adding management of _Equal functor to _Hash_code_base 00856 // type. 00857 template<typename _Key, typename _Value, 00858 typename _ExtractKey, typename _Equal, 00859 typename _H1, typename _H2, typename _Hash, 00860 bool __cache_hash_code> 00861 struct _Hashtable_base 00862 // See PR53067. 00863 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 00864 __cache_hash_code>, 00865 public _Hashtable_ebo_helper<0, _Equal> 00866 { 00867 private: 00868 typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual; 00869 00870 protected: 00871 typedef _Hash_code_base<_Key, _Value, _ExtractKey, 00872 _H1, _H2, _Hash, __cache_hash_code> _HCBase; 00873 typedef typename _HCBase::_Hash_code_type _Hash_code_type; 00874 00875 _Hashtable_base(const _ExtractKey& __ex, 00876 const _H1& __h1, const _H2& __h2, 00877 const _Hash& __hash, const _Equal& __eq) 00878 : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { } 00879 00880 bool 00881 _M_equals(const _Key& __k, _Hash_code_type __c, 00882 _Hash_node<_Value, __cache_hash_code>* __n) const 00883 { 00884 typedef _Equal_helper<_Key, _Value, _ExtractKey, 00885 _Equal, _Hash_code_type, 00886 __cache_hash_code> _EqualHelper; 00887 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 00888 __k, __c, __n); 00889 } 00890 00891 void 00892 _M_swap(_Hashtable_base& __x) 00893 { 00894 _HCBase::_M_swap(__x); 00895 std::swap(_M_eq(), __x._M_eq()); 00896 } 00897 00898 protected: 00899 const _Equal& 00900 _M_eq() const { return _EboEqual::_S_cget(*this); } 00901 _Equal& 00902 _M_eq() { return _EboEqual::_S_get(*this); } 00903 }; 00904 00905 // Local iterators, used to iterate within a bucket but not between 00906 // buckets. 00907 template<typename _Key, typename _Value, typename _ExtractKey, 00908 typename _H1, typename _H2, typename _Hash, 00909 bool __cache_hash_code> 00910 struct _Local_iterator_base; 00911 00912 template<typename _Key, typename _Value, typename _ExtractKey, 00913 typename _H1, typename _H2, typename _Hash> 00914 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 00915 _H1, _H2, _Hash, true> 00916 // See PR53067. 00917 : public _H2 00918 { 00919 _Local_iterator_base() = default; 00920 _Local_iterator_base(_Hash_node<_Value, true>* __p, 00921 std::size_t __bkt, std::size_t __bkt_count) 00922 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 00923 00924 void 00925 _M_incr() 00926 { 00927 _M_cur = _M_cur->_M_next(); 00928 if (_M_cur) 00929 { 00930 std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count); 00931 if (__bkt != _M_bucket) 00932 _M_cur = nullptr; 00933 } 00934 } 00935 00936 const _H2& _M_h2() const 00937 { return *this; } 00938 00939 _Hash_node<_Value, true>* _M_cur; 00940 std::size_t _M_bucket; 00941 std::size_t _M_bucket_count; 00942 }; 00943 00944 template<typename _Key, typename _Value, typename _ExtractKey, 00945 typename _H1, typename _H2, typename _Hash> 00946 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 00947 _H1, _H2, _Hash, false> 00948 // See PR53067. 00949 : public _Hash_code_base<_Key, _Value, _ExtractKey, 00950 _H1, _H2, _Hash, false> 00951 { 00952 _Local_iterator_base() = default; 00953 _Local_iterator_base(_Hash_node<_Value, false>* __p, 00954 std::size_t __bkt, std::size_t __bkt_count) 00955 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 00956 00957 void 00958 _M_incr() 00959 { 00960 _M_cur = _M_cur->_M_next(); 00961 if (_M_cur) 00962 { 00963 std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count); 00964 if (__bkt != _M_bucket) 00965 _M_cur = nullptr; 00966 } 00967 } 00968 00969 _Hash_node<_Value, false>* _M_cur; 00970 std::size_t _M_bucket; 00971 std::size_t _M_bucket_count; 00972 }; 00973 00974 template<typename _Key, typename _Value, typename _ExtractKey, 00975 typename _H1, typename _H2, typename _Hash, bool __cache> 00976 inline bool 00977 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, 00978 _H1, _H2, _Hash, __cache>& __x, 00979 const _Local_iterator_base<_Key, _Value, _ExtractKey, 00980 _H1, _H2, _Hash, __cache>& __y) 00981 { return __x._M_cur == __y._M_cur; } 00982 00983 template<typename _Key, typename _Value, typename _ExtractKey, 00984 typename _H1, typename _H2, typename _Hash, bool __cache> 00985 inline bool 00986 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, 00987 _H1, _H2, _Hash, __cache>& __x, 00988 const _Local_iterator_base<_Key, _Value, _ExtractKey, 00989 _H1, _H2, _Hash, __cache>& __y) 00990 { return __x._M_cur != __y._M_cur; } 00991 00992 template<typename _Key, typename _Value, typename _ExtractKey, 00993 typename _H1, typename _H2, typename _Hash, 00994 bool __constant_iterators, bool __cache> 00995 struct _Local_iterator 00996 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 00997 _H1, _H2, _Hash, __cache> 00998 { 00999 typedef _Value value_type; 01000 typedef typename std::conditional<__constant_iterators, 01001 const _Value*, _Value*>::type 01002 pointer; 01003 typedef typename std::conditional<__constant_iterators, 01004 const _Value&, _Value&>::type 01005 reference; 01006 typedef std::ptrdiff_t difference_type; 01007 typedef std::forward_iterator_tag iterator_category; 01008 01009 _Local_iterator() = default; 01010 01011 explicit 01012 _Local_iterator(_Hash_node<_Value, __cache>* __p, 01013 std::size_t __bkt, std::size_t __bkt_count) 01014 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 01015 __cache>(__p, __bkt, __bkt_count) 01016 { } 01017 01018 reference 01019 operator*() const 01020 { return this->_M_cur->_M_v; } 01021 01022 pointer 01023 operator->() const 01024 { return std::__addressof(this->_M_cur->_M_v); } 01025 01026 _Local_iterator& 01027 operator++() 01028 { 01029 this->_M_incr(); 01030 return *this; 01031 } 01032 01033 _Local_iterator 01034 operator++(int) 01035 { 01036 _Local_iterator __tmp(*this); 01037 this->_M_incr(); 01038 return __tmp; 01039 } 01040 }; 01041 01042 template<typename _Key, typename _Value, typename _ExtractKey, 01043 typename _H1, typename _H2, typename _Hash, 01044 bool __constant_iterators, bool __cache> 01045 struct _Local_const_iterator 01046 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 01047 _H1, _H2, _Hash, __cache> 01048 { 01049 typedef _Value value_type; 01050 typedef const _Value* pointer; 01051 typedef const _Value& reference; 01052 typedef std::ptrdiff_t difference_type; 01053 typedef std::forward_iterator_tag iterator_category; 01054 01055 _Local_const_iterator() = default; 01056 01057 explicit 01058 _Local_const_iterator(_Hash_node<_Value, __cache>* __p, 01059 std::size_t __bkt, std::size_t __bkt_count) 01060 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 01061 __cache>(__p, __bkt, __bkt_count) 01062 { } 01063 01064 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 01065 _H1, _H2, _Hash, 01066 __constant_iterators, 01067 __cache>& __x) 01068 : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 01069 __cache>(__x._M_cur, __x._M_bucket, 01070 __x._M_bucket_count) 01071 { } 01072 01073 reference 01074 operator*() const 01075 { return this->_M_cur->_M_v; } 01076 01077 pointer 01078 operator->() const 01079 { return std::__addressof(this->_M_cur->_M_v); } 01080 01081 _Local_const_iterator& 01082 operator++() 01083 { 01084 this->_M_incr(); 01085 return *this; 01086 } 01087 01088 _Local_const_iterator 01089 operator++(int) 01090 { 01091 _Local_const_iterator __tmp(*this); 01092 this->_M_incr(); 01093 return __tmp; 01094 } 01095 }; 01096 01097 01098 // Class template _Equality_base. This is for implementing equality 01099 // comparison for unordered containers, per N3068, by John Lakos and 01100 // Pablo Halpern. Algorithmically, we follow closely the reference 01101 // implementations therein. 01102 template<typename _ExtractKey, bool __unique_keys, 01103 typename _Hashtable> 01104 struct _Equality_base; 01105 01106 template<typename _ExtractKey, typename _Hashtable> 01107 struct _Equality_base<_ExtractKey, true, _Hashtable> 01108 { 01109 bool _M_equal(const _Hashtable&) const; 01110 }; 01111 01112 template<typename _ExtractKey, typename _Hashtable> 01113 bool 01114 _Equality_base<_ExtractKey, true, _Hashtable>:: 01115 _M_equal(const _Hashtable& __other) const 01116 { 01117 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 01118 01119 if (__this->size() != __other.size()) 01120 return false; 01121 01122 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 01123 { 01124 const auto __ity = __other.find(_ExtractKey()(*__itx)); 01125 if (__ity == __other.end() || !bool(*__ity == *__itx)) 01126 return false; 01127 } 01128 return true; 01129 } 01130 01131 template<typename _ExtractKey, typename _Hashtable> 01132 struct _Equality_base<_ExtractKey, false, _Hashtable> 01133 { 01134 bool _M_equal(const _Hashtable&) const; 01135 01136 private: 01137 template<typename _Uiterator> 01138 static bool 01139 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 01140 }; 01141 01142 // See std::is_permutation in N3068. 01143 template<typename _ExtractKey, typename _Hashtable> 01144 template<typename _Uiterator> 01145 bool 01146 _Equality_base<_ExtractKey, false, _Hashtable>:: 01147 _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 01148 _Uiterator __first2) 01149 { 01150 for (; __first1 != __last1; ++__first1, ++__first2) 01151 if (!(*__first1 == *__first2)) 01152 break; 01153 01154 if (__first1 == __last1) 01155 return true; 01156 01157 _Uiterator __last2 = __first2; 01158 std::advance(__last2, std::distance(__first1, __last1)); 01159 01160 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 01161 { 01162 _Uiterator __tmp = __first1; 01163 while (__tmp != __it1 && !bool(*__tmp == *__it1)) 01164 ++__tmp; 01165 01166 // We've seen this one before. 01167 if (__tmp != __it1) 01168 continue; 01169 01170 std::ptrdiff_t __n2 = 0; 01171 for (__tmp = __first2; __tmp != __last2; ++__tmp) 01172 if (*__tmp == *__it1) 01173 ++__n2; 01174 01175 if (!__n2) 01176 return false; 01177 01178 std::ptrdiff_t __n1 = 0; 01179 for (__tmp = __it1; __tmp != __last1; ++__tmp) 01180 if (*__tmp == *__it1) 01181 ++__n1; 01182 01183 if (__n1 != __n2) 01184 return false; 01185 } 01186 return true; 01187 } 01188 01189 template<typename _ExtractKey, typename _Hashtable> 01190 bool 01191 _Equality_base<_ExtractKey, false, _Hashtable>:: 01192 _M_equal(const _Hashtable& __other) const 01193 { 01194 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 01195 01196 if (__this->size() != __other.size()) 01197 return false; 01198 01199 for (auto __itx = __this->begin(); __itx != __this->end();) 01200 { 01201 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 01202 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 01203 01204 if (std::distance(__xrange.first, __xrange.second) 01205 != std::distance(__yrange.first, __yrange.second)) 01206 return false; 01207 01208 if (!_S_is_permutation(__xrange.first, 01209 __xrange.second, 01210 __yrange.first)) 01211 return false; 01212 01213 __itx = __xrange.second; 01214 } 01215 return true; 01216 } 01217 01218 _GLIBCXX_END_NAMESPACE_VERSION 01219 } // namespace __detail 01220 } // namespace std 01221 01222 #endif // _HASHTABLE_POLICY_H