libstdc++
|
00001 // Internal policy header for unordered_set and unordered_map -*- C++ -*- 00002 00003 // Copyright (C) 2010, 2011 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 // Auxiliary types used for all instantiations of _Hashtable: nodes 00063 // and iterators. 00064 00065 // Nodes, used to wrap elements stored in the hash table. A policy 00066 // template parameter of class template _Hashtable controls whether 00067 // nodes also store a hash code. In some cases (e.g. strings) this 00068 // may be a performance win. 00069 template<typename _Value, bool __cache_hash_code> 00070 struct _Hash_node; 00071 00072 template<typename _Value> 00073 struct _Hash_node<_Value, true> 00074 { 00075 _Value _M_v; 00076 std::size_t _M_hash_code; 00077 _Hash_node* _M_next; 00078 00079 template<typename... _Args> 00080 _Hash_node(_Args&&... __args) 00081 : _M_v(std::forward<_Args>(__args)...), 00082 _M_hash_code(), _M_next() { } 00083 }; 00084 00085 template<typename _Value> 00086 struct _Hash_node<_Value, false> 00087 { 00088 _Value _M_v; 00089 _Hash_node* _M_next; 00090 00091 template<typename... _Args> 00092 _Hash_node(_Args&&... __args) 00093 : _M_v(std::forward<_Args>(__args)...), 00094 _M_next() { } 00095 }; 00096 00097 // Local iterators, used to iterate within a bucket but not between 00098 // buckets. 00099 template<typename _Value, bool __cache> 00100 struct _Node_iterator_base 00101 { 00102 _Node_iterator_base(_Hash_node<_Value, __cache>* __p) 00103 : _M_cur(__p) { } 00104 00105 void 00106 _M_incr() 00107 { _M_cur = _M_cur->_M_next; } 00108 00109 _Hash_node<_Value, __cache>* _M_cur; 00110 }; 00111 00112 template<typename _Value, bool __cache> 00113 inline bool 00114 operator==(const _Node_iterator_base<_Value, __cache>& __x, 00115 const _Node_iterator_base<_Value, __cache>& __y) 00116 { return __x._M_cur == __y._M_cur; } 00117 00118 template<typename _Value, bool __cache> 00119 inline bool 00120 operator!=(const _Node_iterator_base<_Value, __cache>& __x, 00121 const _Node_iterator_base<_Value, __cache>& __y) 00122 { return __x._M_cur != __y._M_cur; } 00123 00124 template<typename _Value, bool __constant_iterators, bool __cache> 00125 struct _Node_iterator 00126 : public _Node_iterator_base<_Value, __cache> 00127 { 00128 typedef _Value value_type; 00129 typedef typename std::conditional<__constant_iterators, 00130 const _Value*, _Value*>::type 00131 pointer; 00132 typedef typename std::conditional<__constant_iterators, 00133 const _Value&, _Value&>::type 00134 reference; 00135 typedef std::ptrdiff_t difference_type; 00136 typedef std::forward_iterator_tag iterator_category; 00137 00138 _Node_iterator() 00139 : _Node_iterator_base<_Value, __cache>(0) { } 00140 00141 explicit 00142 _Node_iterator(_Hash_node<_Value, __cache>* __p) 00143 : _Node_iterator_base<_Value, __cache>(__p) { } 00144 00145 reference 00146 operator*() const 00147 { return this->_M_cur->_M_v; } 00148 00149 pointer 00150 operator->() const 00151 { return std::__addressof(this->_M_cur->_M_v); } 00152 00153 _Node_iterator& 00154 operator++() 00155 { 00156 this->_M_incr(); 00157 return *this; 00158 } 00159 00160 _Node_iterator 00161 operator++(int) 00162 { 00163 _Node_iterator __tmp(*this); 00164 this->_M_incr(); 00165 return __tmp; 00166 } 00167 }; 00168 00169 template<typename _Value, bool __constant_iterators, bool __cache> 00170 struct _Node_const_iterator 00171 : public _Node_iterator_base<_Value, __cache> 00172 { 00173 typedef _Value value_type; 00174 typedef const _Value* pointer; 00175 typedef const _Value& reference; 00176 typedef std::ptrdiff_t difference_type; 00177 typedef std::forward_iterator_tag iterator_category; 00178 00179 _Node_const_iterator() 00180 : _Node_iterator_base<_Value, __cache>(0) { } 00181 00182 explicit 00183 _Node_const_iterator(_Hash_node<_Value, __cache>* __p) 00184 : _Node_iterator_base<_Value, __cache>(__p) { } 00185 00186 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 00187 __cache>& __x) 00188 : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } 00189 00190 reference 00191 operator*() const 00192 { return this->_M_cur->_M_v; } 00193 00194 pointer 00195 operator->() const 00196 { return std::__addressof(this->_M_cur->_M_v); } 00197 00198 _Node_const_iterator& 00199 operator++() 00200 { 00201 this->_M_incr(); 00202 return *this; 00203 } 00204 00205 _Node_const_iterator 00206 operator++(int) 00207 { 00208 _Node_const_iterator __tmp(*this); 00209 this->_M_incr(); 00210 return __tmp; 00211 } 00212 }; 00213 00214 template<typename _Value, bool __cache> 00215 struct _Hashtable_iterator_base 00216 { 00217 _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, 00218 _Hash_node<_Value, __cache>** __bucket) 00219 : _M_cur_node(__node), _M_cur_bucket(__bucket) { } 00220 00221 void 00222 _M_incr() 00223 { 00224 _M_cur_node = _M_cur_node->_M_next; 00225 if (!_M_cur_node) 00226 _M_incr_bucket(); 00227 } 00228 00229 void 00230 _M_incr_bucket(); 00231 00232 _Hash_node<_Value, __cache>* _M_cur_node; 00233 _Hash_node<_Value, __cache>** _M_cur_bucket; 00234 }; 00235 00236 // Global iterators, used for arbitrary iteration within a hash 00237 // table. Larger and more expensive than local iterators. 00238 template<typename _Value, bool __cache> 00239 void 00240 _Hashtable_iterator_base<_Value, __cache>:: 00241 _M_incr_bucket() 00242 { 00243 ++_M_cur_bucket; 00244 00245 // This loop requires the bucket array to have a non-null sentinel. 00246 while (!*_M_cur_bucket) 00247 ++_M_cur_bucket; 00248 _M_cur_node = *_M_cur_bucket; 00249 } 00250 00251 template<typename _Value, bool __cache> 00252 inline bool 00253 operator==(const _Hashtable_iterator_base<_Value, __cache>& __x, 00254 const _Hashtable_iterator_base<_Value, __cache>& __y) 00255 { return __x._M_cur_node == __y._M_cur_node; } 00256 00257 template<typename _Value, bool __cache> 00258 inline bool 00259 operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x, 00260 const _Hashtable_iterator_base<_Value, __cache>& __y) 00261 { return __x._M_cur_node != __y._M_cur_node; } 00262 00263 template<typename _Value, bool __constant_iterators, bool __cache> 00264 struct _Hashtable_iterator 00265 : public _Hashtable_iterator_base<_Value, __cache> 00266 { 00267 typedef _Value value_type; 00268 typedef typename std::conditional<__constant_iterators, 00269 const _Value*, _Value*>::type 00270 pointer; 00271 typedef typename std::conditional<__constant_iterators, 00272 const _Value&, _Value&>::type 00273 reference; 00274 typedef std::ptrdiff_t difference_type; 00275 typedef std::forward_iterator_tag iterator_category; 00276 00277 _Hashtable_iterator() 00278 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } 00279 00280 _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, 00281 _Hash_node<_Value, __cache>** __b) 00282 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } 00283 00284 explicit 00285 _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) 00286 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } 00287 00288 reference 00289 operator*() const 00290 { return this->_M_cur_node->_M_v; } 00291 00292 pointer 00293 operator->() const 00294 { return std::__addressof(this->_M_cur_node->_M_v); } 00295 00296 _Hashtable_iterator& 00297 operator++() 00298 { 00299 this->_M_incr(); 00300 return *this; 00301 } 00302 00303 _Hashtable_iterator 00304 operator++(int) 00305 { 00306 _Hashtable_iterator __tmp(*this); 00307 this->_M_incr(); 00308 return __tmp; 00309 } 00310 }; 00311 00312 template<typename _Value, bool __constant_iterators, bool __cache> 00313 struct _Hashtable_const_iterator 00314 : public _Hashtable_iterator_base<_Value, __cache> 00315 { 00316 typedef _Value value_type; 00317 typedef const _Value* pointer; 00318 typedef const _Value& reference; 00319 typedef std::ptrdiff_t difference_type; 00320 typedef std::forward_iterator_tag iterator_category; 00321 00322 _Hashtable_const_iterator() 00323 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } 00324 00325 _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p, 00326 _Hash_node<_Value, __cache>** __b) 00327 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } 00328 00329 explicit 00330 _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) 00331 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } 00332 00333 _Hashtable_const_iterator(const _Hashtable_iterator<_Value, 00334 __constant_iterators, __cache>& __x) 00335 : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node, 00336 __x._M_cur_bucket) { } 00337 00338 reference 00339 operator*() const 00340 { return this->_M_cur_node->_M_v; } 00341 00342 pointer 00343 operator->() const 00344 { return std::__addressof(this->_M_cur_node->_M_v); } 00345 00346 _Hashtable_const_iterator& 00347 operator++() 00348 { 00349 this->_M_incr(); 00350 return *this; 00351 } 00352 00353 _Hashtable_const_iterator 00354 operator++(int) 00355 { 00356 _Hashtable_const_iterator __tmp(*this); 00357 this->_M_incr(); 00358 return __tmp; 00359 } 00360 }; 00361 00362 00363 // Many of class template _Hashtable's template parameters are policy 00364 // classes. These are defaults for the policies. 00365 00366 // Default range hashing function: use division to fold a large number 00367 // into the range [0, N). 00368 struct _Mod_range_hashing 00369 { 00370 typedef std::size_t first_argument_type; 00371 typedef std::size_t second_argument_type; 00372 typedef std::size_t result_type; 00373 00374 result_type 00375 operator()(first_argument_type __num, second_argument_type __den) const 00376 { return __num % __den; } 00377 }; 00378 00379 // Default ranged hash function H. In principle it should be a 00380 // function object composed from objects of type H1 and H2 such that 00381 // h(k, N) = h2(h1(k), N), but that would mean making extra copies of 00382 // h1 and h2. So instead we'll just use a tag to tell class template 00383 // hashtable to do that composition. 00384 struct _Default_ranged_hash { }; 00385 00386 // Default value for rehash policy. Bucket size is (usually) the 00387 // smallest prime that keeps the load factor small enough. 00388 struct _Prime_rehash_policy 00389 { 00390 _Prime_rehash_policy(float __z = 1.0) 00391 : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { } 00392 00393 float 00394 max_load_factor() const 00395 { return _M_max_load_factor; } 00396 00397 // Return a bucket size no smaller than n. 00398 std::size_t 00399 _M_next_bkt(std::size_t __n) const; 00400 00401 // Return a bucket count appropriate for n elements 00402 std::size_t 00403 _M_bkt_for_elements(std::size_t __n) const; 00404 00405 // __n_bkt is current bucket count, __n_elt is current element count, 00406 // and __n_ins is number of elements to be inserted. Do we need to 00407 // increase bucket count? If so, return make_pair(true, n), where n 00408 // is the new bucket count. If not, return make_pair(false, 0). 00409 std::pair<bool, std::size_t> 00410 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 00411 std::size_t __n_ins) const; 00412 00413 enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; 00414 00415 float _M_max_load_factor; 00416 float _M_growth_factor; 00417 mutable std::size_t _M_next_resize; 00418 }; 00419 00420 extern const unsigned long __prime_list[]; 00421 00422 // XXX This is a hack. There's no good reason for any of 00423 // _Prime_rehash_policy's member functions to be inline. 00424 00425 // Return a prime no smaller than n. 00426 inline std::size_t 00427 _Prime_rehash_policy:: 00428 _M_next_bkt(std::size_t __n) const 00429 { 00430 const unsigned long* __p = std::lower_bound(__prime_list, __prime_list 00431 + _S_n_primes, __n); 00432 _M_next_resize = 00433 static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor)); 00434 return *__p; 00435 } 00436 00437 // Return the smallest prime p such that alpha p >= n, where alpha 00438 // is the load factor. 00439 inline std::size_t 00440 _Prime_rehash_policy:: 00441 _M_bkt_for_elements(std::size_t __n) const 00442 { 00443 const float __min_bkts = __n / _M_max_load_factor; 00444 const unsigned long* __p = std::lower_bound(__prime_list, __prime_list 00445 + _S_n_primes, __min_bkts); 00446 _M_next_resize = 00447 static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor)); 00448 return *__p; 00449 } 00450 00451 // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 00452 // If p > __n_bkt, return make_pair(true, p); otherwise return 00453 // make_pair(false, 0). In principle this isn't very different from 00454 // _M_bkt_for_elements. 00455 00456 // The only tricky part is that we're caching the element count at 00457 // which we need to rehash, so we don't have to do a floating-point 00458 // multiply for every insertion. 00459 00460 inline std::pair<bool, std::size_t> 00461 _Prime_rehash_policy:: 00462 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 00463 std::size_t __n_ins) const 00464 { 00465 if (__n_elt + __n_ins > _M_next_resize) 00466 { 00467 float __min_bkts = ((float(__n_ins) + float(__n_elt)) 00468 / _M_max_load_factor); 00469 if (__min_bkts > __n_bkt) 00470 { 00471 __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); 00472 const unsigned long* __p = 00473 std::lower_bound(__prime_list, __prime_list + _S_n_primes, 00474 __min_bkts); 00475 _M_next_resize = static_cast<std::size_t> 00476 (__builtin_ceil(*__p * _M_max_load_factor)); 00477 return std::make_pair(true, *__p); 00478 } 00479 else 00480 { 00481 _M_next_resize = static_cast<std::size_t> 00482 (__builtin_ceil(__n_bkt * _M_max_load_factor)); 00483 return std::make_pair(false, 0); 00484 } 00485 } 00486 else 00487 return std::make_pair(false, 0); 00488 } 00489 00490 // Base classes for std::_Hashtable. We define these base classes 00491 // because in some cases we want to do different things depending 00492 // on the value of a policy class. In some cases the policy class 00493 // affects which member functions and nested typedefs are defined; 00494 // we handle that by specializing base class templates. Several of 00495 // the base class templates need to access other members of class 00496 // template _Hashtable, so we use the "curiously recurring template 00497 // pattern" for them. 00498 00499 // class template _Map_base. If the hashtable has a value type of 00500 // the form pair<T1, T2> and a key extraction policy that returns the 00501 // first part of the pair, the hashtable gets a mapped_type typedef. 00502 // If it satisfies those criteria and also has unique keys, then it 00503 // also gets an operator[]. 00504 template<typename _Key, typename _Value, typename _Ex, bool __unique, 00505 typename _Hashtable> 00506 struct _Map_base { }; 00507 00508 template<typename _Key, typename _Pair, typename _Hashtable> 00509 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> 00510 { 00511 typedef typename _Pair::second_type mapped_type; 00512 }; 00513 00514 template<typename _Key, typename _Pair, typename _Hashtable> 00515 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> 00516 { 00517 typedef typename _Pair::second_type mapped_type; 00518 00519 mapped_type& 00520 operator[](const _Key& __k); 00521 00522 mapped_type& 00523 operator[](_Key&& __k); 00524 00525 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00526 // DR 761. unordered_map needs an at() member function. 00527 mapped_type& 00528 at(const _Key& __k); 00529 00530 const mapped_type& 00531 at(const _Key& __k) const; 00532 }; 00533 00534 template<typename _Key, typename _Pair, typename _Hashtable> 00535 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00536 true, _Hashtable>::mapped_type& 00537 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00538 operator[](const _Key& __k) 00539 { 00540 _Hashtable* __h = static_cast<_Hashtable*>(this); 00541 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00542 std::size_t __n = __h->_M_bucket_index(__k, __code, 00543 __h->_M_bucket_count); 00544 00545 typename _Hashtable::_Node* __p = 00546 __h->_M_find_node(__h->_M_buckets[__n], __k, __code); 00547 if (!__p) 00548 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), 00549 __n, __code)->second; 00550 return (__p->_M_v).second; 00551 } 00552 00553 template<typename _Key, typename _Pair, typename _Hashtable> 00554 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00555 true, _Hashtable>::mapped_type& 00556 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00557 operator[](_Key&& __k) 00558 { 00559 _Hashtable* __h = static_cast<_Hashtable*>(this); 00560 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00561 std::size_t __n = __h->_M_bucket_index(__k, __code, 00562 __h->_M_bucket_count); 00563 00564 typename _Hashtable::_Node* __p = 00565 __h->_M_find_node(__h->_M_buckets[__n], __k, __code); 00566 if (!__p) 00567 return __h->_M_insert_bucket(std::make_pair(std::move(__k), 00568 mapped_type()), 00569 __n, __code)->second; 00570 return (__p->_M_v).second; 00571 } 00572 00573 template<typename _Key, typename _Pair, typename _Hashtable> 00574 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00575 true, _Hashtable>::mapped_type& 00576 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00577 at(const _Key& __k) 00578 { 00579 _Hashtable* __h = static_cast<_Hashtable*>(this); 00580 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00581 std::size_t __n = __h->_M_bucket_index(__k, __code, 00582 __h->_M_bucket_count); 00583 00584 typename _Hashtable::_Node* __p = 00585 __h->_M_find_node(__h->_M_buckets[__n], __k, __code); 00586 if (!__p) 00587 __throw_out_of_range(__N("_Map_base::at")); 00588 return (__p->_M_v).second; 00589 } 00590 00591 template<typename _Key, typename _Pair, typename _Hashtable> 00592 const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 00593 true, _Hashtable>::mapped_type& 00594 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 00595 at(const _Key& __k) const 00596 { 00597 const _Hashtable* __h = static_cast<const _Hashtable*>(this); 00598 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 00599 std::size_t __n = __h->_M_bucket_index(__k, __code, 00600 __h->_M_bucket_count); 00601 00602 typename _Hashtable::_Node* __p = 00603 __h->_M_find_node(__h->_M_buckets[__n], __k, __code); 00604 if (!__p) 00605 __throw_out_of_range(__N("_Map_base::at")); 00606 return (__p->_M_v).second; 00607 } 00608 00609 // class template _Rehash_base. Give hashtable the max_load_factor 00610 // functions and reserve iff the rehash policy is _Prime_rehash_policy. 00611 template<typename _RehashPolicy, typename _Hashtable> 00612 struct _Rehash_base { }; 00613 00614 template<typename _Hashtable> 00615 struct _Rehash_base<_Prime_rehash_policy, _Hashtable> 00616 { 00617 float 00618 max_load_factor() const 00619 { 00620 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 00621 return __this->__rehash_policy().max_load_factor(); 00622 } 00623 00624 void 00625 max_load_factor(float __z) 00626 { 00627 _Hashtable* __this = static_cast<_Hashtable*>(this); 00628 __this->__rehash_policy(_Prime_rehash_policy(__z)); 00629 } 00630 00631 void 00632 reserve(std::size_t __n) 00633 { 00634 _Hashtable* __this = static_cast<_Hashtable*>(this); 00635 __this->rehash(__builtin_ceil(__n / max_load_factor())); 00636 } 00637 }; 00638 00639 // Class template _Hash_code_base. Encapsulates two policy issues that 00640 // aren't quite orthogonal. 00641 // (1) the difference between using a ranged hash function and using 00642 // the combination of a hash function and a range-hashing function. 00643 // In the former case we don't have such things as hash codes, so 00644 // we have a dummy type as placeholder. 00645 // (2) Whether or not we cache hash codes. Caching hash codes is 00646 // meaningless if we have a ranged hash function. 00647 // We also put the key extraction and equality comparison function 00648 // objects here, for convenience. 00649 00650 // Primary template: unused except as a hook for specializations. 00651 template<typename _Key, typename _Value, 00652 typename _ExtractKey, typename _Equal, 00653 typename _H1, typename _H2, typename _Hash, 00654 bool __cache_hash_code> 00655 struct _Hash_code_base; 00656 00657 // Specialization: ranged hash function, no caching hash codes. H1 00658 // and H2 are provided but ignored. We define a dummy hash code type. 00659 template<typename _Key, typename _Value, 00660 typename _ExtractKey, typename _Equal, 00661 typename _H1, typename _H2, typename _Hash> 00662 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 00663 _Hash, false> 00664 { 00665 protected: 00666 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 00667 const _H1&, const _H2&, const _Hash& __h) 00668 : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } 00669 00670 typedef void* _Hash_code_type; 00671 00672 _Hash_code_type 00673 _M_hash_code(const _Key& __key) const 00674 { return 0; } 00675 00676 std::size_t 00677 _M_bucket_index(const _Key& __k, _Hash_code_type, 00678 std::size_t __n) const 00679 { return _M_ranged_hash(__k, __n); } 00680 00681 std::size_t 00682 _M_bucket_index(const _Hash_node<_Value, false>* __p, 00683 std::size_t __n) const 00684 { return _M_ranged_hash(_M_extract(__p->_M_v), __n); } 00685 00686 bool 00687 _M_compare(const _Key& __k, _Hash_code_type, 00688 _Hash_node<_Value, false>* __n) const 00689 { return _M_eq(__k, _M_extract(__n->_M_v)); } 00690 00691 void 00692 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 00693 { } 00694 00695 void 00696 _M_copy_code(_Hash_node<_Value, false>*, 00697 const _Hash_node<_Value, false>*) const 00698 { } 00699 00700 void 00701 _M_swap(_Hash_code_base& __x) 00702 { 00703 std::swap(_M_extract, __x._M_extract); 00704 std::swap(_M_eq, __x._M_eq); 00705 std::swap(_M_ranged_hash, __x._M_ranged_hash); 00706 } 00707 00708 protected: 00709 _ExtractKey _M_extract; 00710 _Equal _M_eq; 00711 _Hash _M_ranged_hash; 00712 }; 00713 00714 00715 // No specialization for ranged hash function while caching hash codes. 00716 // That combination is meaningless, and trying to do it is an error. 00717 00718 00719 // Specialization: ranged hash function, cache hash codes. This 00720 // combination is meaningless, so we provide only a declaration 00721 // and no definition. 00722 template<typename _Key, typename _Value, 00723 typename _ExtractKey, typename _Equal, 00724 typename _H1, typename _H2, typename _Hash> 00725 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 00726 _Hash, true>; 00727 00728 // Specialization: hash function and range-hashing function, no 00729 // caching of hash codes. H is provided but ignored. Provides 00730 // typedef and accessor required by TR1. 00731 template<typename _Key, typename _Value, 00732 typename _ExtractKey, typename _Equal, 00733 typename _H1, typename _H2> 00734 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 00735 _Default_ranged_hash, false> 00736 { 00737 typedef _H1 hasher; 00738 00739 hasher 00740 hash_function() const 00741 { return _M_h1; } 00742 00743 protected: 00744 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 00745 const _H1& __h1, const _H2& __h2, 00746 const _Default_ranged_hash&) 00747 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } 00748 00749 typedef std::size_t _Hash_code_type; 00750 00751 _Hash_code_type 00752 _M_hash_code(const _Key& __k) const 00753 { return _M_h1(__k); } 00754 00755 std::size_t 00756 _M_bucket_index(const _Key&, _Hash_code_type __c, 00757 std::size_t __n) const 00758 { return _M_h2(__c, __n); } 00759 00760 std::size_t 00761 _M_bucket_index(const _Hash_node<_Value, false>* __p, 00762 std::size_t __n) const 00763 { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); } 00764 00765 bool 00766 _M_compare(const _Key& __k, _Hash_code_type, 00767 _Hash_node<_Value, false>* __n) const 00768 { return _M_eq(__k, _M_extract(__n->_M_v)); } 00769 00770 void 00771 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 00772 { } 00773 00774 void 00775 _M_copy_code(_Hash_node<_Value, false>*, 00776 const _Hash_node<_Value, false>*) const 00777 { } 00778 00779 void 00780 _M_swap(_Hash_code_base& __x) 00781 { 00782 std::swap(_M_extract, __x._M_extract); 00783 std::swap(_M_eq, __x._M_eq); 00784 std::swap(_M_h1, __x._M_h1); 00785 std::swap(_M_h2, __x._M_h2); 00786 } 00787 00788 protected: 00789 _ExtractKey _M_extract; 00790 _Equal _M_eq; 00791 _H1 _M_h1; 00792 _H2 _M_h2; 00793 }; 00794 00795 // Specialization: hash function and range-hashing function, 00796 // caching hash codes. H is provided but ignored. Provides 00797 // typedef and accessor required by TR1. 00798 template<typename _Key, typename _Value, 00799 typename _ExtractKey, typename _Equal, 00800 typename _H1, typename _H2> 00801 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 00802 _Default_ranged_hash, true> 00803 { 00804 typedef _H1 hasher; 00805 00806 hasher 00807 hash_function() const 00808 { return _M_h1; } 00809 00810 protected: 00811 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 00812 const _H1& __h1, const _H2& __h2, 00813 const _Default_ranged_hash&) 00814 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } 00815 00816 typedef std::size_t _Hash_code_type; 00817 00818 _Hash_code_type 00819 _M_hash_code(const _Key& __k) const 00820 { return _M_h1(__k); } 00821 00822 std::size_t 00823 _M_bucket_index(const _Key&, _Hash_code_type __c, 00824 std::size_t __n) const 00825 { return _M_h2(__c, __n); } 00826 00827 std::size_t 00828 _M_bucket_index(const _Hash_node<_Value, true>* __p, 00829 std::size_t __n) const 00830 { return _M_h2(__p->_M_hash_code, __n); } 00831 00832 bool 00833 _M_compare(const _Key& __k, _Hash_code_type __c, 00834 _Hash_node<_Value, true>* __n) const 00835 { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } 00836 00837 void 00838 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const 00839 { __n->_M_hash_code = __c; } 00840 00841 void 00842 _M_copy_code(_Hash_node<_Value, true>* __to, 00843 const _Hash_node<_Value, true>* __from) const 00844 { __to->_M_hash_code = __from->_M_hash_code; } 00845 00846 void 00847 _M_swap(_Hash_code_base& __x) 00848 { 00849 std::swap(_M_extract, __x._M_extract); 00850 std::swap(_M_eq, __x._M_eq); 00851 std::swap(_M_h1, __x._M_h1); 00852 std::swap(_M_h2, __x._M_h2); 00853 } 00854 00855 protected: 00856 _ExtractKey _M_extract; 00857 _Equal _M_eq; 00858 _H1 _M_h1; 00859 _H2 _M_h2; 00860 }; 00861 00862 00863 // Class template _Equality_base. This is for implementing equality 00864 // comparison for unordered containers, per N3068, by John Lakos and 00865 // Pablo Halpern. Algorithmically, we follow closely the reference 00866 // implementations therein. 00867 template<typename _ExtractKey, bool __unique_keys, 00868 typename _Hashtable> 00869 struct _Equality_base; 00870 00871 template<typename _ExtractKey, typename _Hashtable> 00872 struct _Equality_base<_ExtractKey, true, _Hashtable> 00873 { 00874 bool _M_equal(const _Hashtable&) const; 00875 }; 00876 00877 template<typename _ExtractKey, typename _Hashtable> 00878 bool 00879 _Equality_base<_ExtractKey, true, _Hashtable>:: 00880 _M_equal(const _Hashtable& __other) const 00881 { 00882 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 00883 00884 if (__this->size() != __other.size()) 00885 return false; 00886 00887 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 00888 { 00889 const auto __ity = __other.find(_ExtractKey()(*__itx)); 00890 if (__ity == __other.end() || *__ity != *__itx) 00891 return false; 00892 } 00893 return true; 00894 } 00895 00896 template<typename _ExtractKey, typename _Hashtable> 00897 struct _Equality_base<_ExtractKey, false, _Hashtable> 00898 { 00899 bool _M_equal(const _Hashtable&) const; 00900 00901 private: 00902 template<typename _Uiterator> 00903 static bool 00904 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 00905 }; 00906 00907 // See std::is_permutation in N3068. 00908 template<typename _ExtractKey, typename _Hashtable> 00909 template<typename _Uiterator> 00910 bool 00911 _Equality_base<_ExtractKey, false, _Hashtable>:: 00912 _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 00913 _Uiterator __first2) 00914 { 00915 for (; __first1 != __last1; ++__first1, ++__first2) 00916 if (!(*__first1 == *__first2)) 00917 break; 00918 00919 if (__first1 == __last1) 00920 return true; 00921 00922 _Uiterator __last2 = __first2; 00923 std::advance(__last2, std::distance(__first1, __last1)); 00924 00925 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 00926 { 00927 _Uiterator __tmp = __first1; 00928 while (__tmp != __it1 && !(*__tmp == *__it1)) 00929 ++__tmp; 00930 00931 // We've seen this one before. 00932 if (__tmp != __it1) 00933 continue; 00934 00935 std::ptrdiff_t __n2 = 0; 00936 for (__tmp = __first2; __tmp != __last2; ++__tmp) 00937 if (*__tmp == *__it1) 00938 ++__n2; 00939 00940 if (!__n2) 00941 return false; 00942 00943 std::ptrdiff_t __n1 = 0; 00944 for (__tmp = __it1; __tmp != __last1; ++__tmp) 00945 if (*__tmp == *__it1) 00946 ++__n1; 00947 00948 if (__n1 != __n2) 00949 return false; 00950 } 00951 return true; 00952 } 00953 00954 template<typename _ExtractKey, typename _Hashtable> 00955 bool 00956 _Equality_base<_ExtractKey, false, _Hashtable>:: 00957 _M_equal(const _Hashtable& __other) const 00958 { 00959 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 00960 00961 if (__this->size() != __other.size()) 00962 return false; 00963 00964 for (auto __itx = __this->begin(); __itx != __this->end();) 00965 { 00966 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 00967 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 00968 00969 if (std::distance(__xrange.first, __xrange.second) 00970 != std::distance(__yrange.first, __yrange.second)) 00971 return false; 00972 00973 if (!_S_is_permutation(__xrange.first, 00974 __xrange.second, 00975 __yrange.first)) 00976 return false; 00977 00978 __itx = __xrange.second; 00979 } 00980 return true; 00981 } 00982 00983 _GLIBCXX_END_NAMESPACE_VERSION 00984 } // namespace __detail 00985 } // namespace std 00986 00987 #endif // _HASHTABLE_POLICY_H