libstdc++
|
00001 // Internal policy header for unordered_set and unordered_map -*- C++ -*- 00002 00003 // Copyright (C) 2010-2013 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 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00037 00038 template<typename _Key, typename _Value, typename _Alloc, 00039 typename _ExtractKey, typename _Equal, 00040 typename _H1, typename _H2, typename _Hash, 00041 typename _RehashPolicy, typename _Traits> 00042 class _Hashtable; 00043 00044 _GLIBCXX_END_NAMESPACE_VERSION 00045 00046 namespace __detail 00047 { 00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00049 00050 /** 00051 * @defgroup hashtable-detail Base and Implementation Classes 00052 * @ingroup unordered_associative_containers 00053 * @{ 00054 */ 00055 template<typename _Key, typename _Value, 00056 typename _ExtractKey, typename _Equal, 00057 typename _H1, typename _H2, typename _Hash, typename _Traits> 00058 struct _Hashtable_base; 00059 00060 // Helper function: return distance(first, last) for forward 00061 // iterators, or 0 for input iterators. 00062 template<class _Iterator> 00063 inline typename std::iterator_traits<_Iterator>::difference_type 00064 __distance_fw(_Iterator __first, _Iterator __last, 00065 std::input_iterator_tag) 00066 { return 0; } 00067 00068 template<class _Iterator> 00069 inline typename std::iterator_traits<_Iterator>::difference_type 00070 __distance_fw(_Iterator __first, _Iterator __last, 00071 std::forward_iterator_tag) 00072 { return std::distance(__first, __last); } 00073 00074 template<class _Iterator> 00075 inline typename std::iterator_traits<_Iterator>::difference_type 00076 __distance_fw(_Iterator __first, _Iterator __last) 00077 { 00078 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; 00079 return __distance_fw(__first, __last, _Tag()); 00080 } 00081 00082 // Helper type used to detect whether the hash functor is noexcept. 00083 template <typename _Key, typename _Hash> 00084 struct __is_noexcept_hash : std::integral_constant<bool, 00085 noexcept(declval<const _Hash&>()(declval<const _Key&>()))> 00086 { }; 00087 00088 struct _Identity 00089 { 00090 template<typename _Tp> 00091 _Tp&& 00092 operator()(_Tp&& __x) const 00093 { return std::forward<_Tp>(__x); } 00094 }; 00095 00096 struct _Select1st 00097 { 00098 template<typename _Tp> 00099 auto 00100 operator()(_Tp&& __x) const 00101 -> decltype(std::get<0>(std::forward<_Tp>(__x))) 00102 { return std::get<0>(std::forward<_Tp>(__x)); } 00103 }; 00104 00105 // Auxiliary types used for all instantiations of _Hashtable nodes 00106 // and iterators. 00107 00108 /** 00109 * struct _Hashtable_traits 00110 * 00111 * Important traits for hash tables. 00112 * 00113 * @tparam _Cache_hash_code Boolean value. True if the value of 00114 * the hash function is stored along with the value. This is a 00115 * time-space tradeoff. Storing it may improve lookup speed by 00116 * reducing the number of times we need to call the _Equal 00117 * function. 00118 * 00119 * @tparam _Constant_iterators Boolean value. True if iterator and 00120 * const_iterator are both constant iterator types. This is true 00121 * for unordered_set and unordered_multiset, false for 00122 * unordered_map and unordered_multimap. 00123 * 00124 * @tparam _Unique_keys Boolean value. True if the return value 00125 * of _Hashtable::count(k) is always at most one, false if it may 00126 * be an arbitrary number. This is true for unordered_set and 00127 * unordered_map, false for unordered_multiset and 00128 * unordered_multimap. 00129 */ 00130 template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys> 00131 struct _Hashtable_traits 00132 { 00133 template<bool _Cond> 00134 using __bool_constant = integral_constant<bool, _Cond>; 00135 00136 using __hash_cached = __bool_constant<_Cache_hash_code>; 00137 using __constant_iterators = __bool_constant<_Constant_iterators>; 00138 using __unique_keys = __bool_constant<_Unique_keys>; 00139 }; 00140 00141 /** 00142 * struct _Hash_node_base 00143 * 00144 * Nodes, used to wrap elements stored in the hash table. A policy 00145 * template parameter of class template _Hashtable controls whether 00146 * nodes also store a hash code. In some cases (e.g. strings) this 00147 * may be a performance win. 00148 */ 00149 struct _Hash_node_base 00150 { 00151 _Hash_node_base* _M_nxt; 00152 00153 _Hash_node_base() : _M_nxt() { } 00154 00155 _Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { } 00156 }; 00157 00158 /** 00159 * Primary template struct _Hash_node. 00160 */ 00161 template<typename _Value, bool _Cache_hash_code> 00162 struct _Hash_node; 00163 00164 /** 00165 * Specialization for nodes with caches, struct _Hash_node. 00166 * 00167 * Base class is __detail::_Hash_node_base. 00168 */ 00169 template<typename _Value> 00170 struct _Hash_node<_Value, true> : _Hash_node_base 00171 { 00172 _Value _M_v; 00173 std::size_t _M_hash_code; 00174 00175 template<typename... _Args> 00176 _Hash_node(_Args&&... __args) 00177 : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { } 00178 00179 _Hash_node* 00180 _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } 00181 }; 00182 00183 /** 00184 * Specialization for nodes without caches, struct _Hash_node. 00185 * 00186 * Base class is __detail::_Hash_node_base. 00187 */ 00188 template<typename _Value> 00189 struct _Hash_node<_Value, false> : _Hash_node_base 00190 { 00191 _Value _M_v; 00192 00193 template<typename... _Args> 00194 _Hash_node(_Args&&... __args) 00195 : _M_v(std::forward<_Args>(__args)...) { } 00196 00197 _Hash_node* 00198 _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } 00199 }; 00200 00201 /// Base class for node iterators. 00202 template<typename _Value, bool _Cache_hash_code> 00203 struct _Node_iterator_base 00204 { 00205 using __node_type = _Hash_node<_Value, _Cache_hash_code>; 00206 00207 __node_type* _M_cur; 00208 00209 _Node_iterator_base(__node_type* __p) 00210 : _M_cur(__p) { } 00211 00212 void 00213 _M_incr() 00214 { _M_cur = _M_cur->_M_next(); } 00215 }; 00216 00217 template<typename _Value, bool _Cache_hash_code> 00218 inline bool 00219 operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, 00220 const _Node_iterator_base<_Value, _Cache_hash_code >& __y) 00221 { return __x._M_cur == __y._M_cur; } 00222 00223 template<typename _Value, bool _Cache_hash_code> 00224 inline bool 00225 operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, 00226 const _Node_iterator_base<_Value, _Cache_hash_code>& __y) 00227 { return __x._M_cur != __y._M_cur; } 00228 00229 /// Node iterators, used to iterate through all the hashtable. 00230 template<typename _Value, bool __constant_iterators, bool __cache> 00231 struct _Node_iterator 00232 : public _Node_iterator_base<_Value, __cache> 00233 { 00234 private: 00235 using __base_type = _Node_iterator_base<_Value, __cache>; 00236 using __node_type = typename __base_type::__node_type; 00237 00238 public: 00239 typedef _Value value_type; 00240 typedef std::ptrdiff_t difference_type; 00241 typedef std::forward_iterator_tag iterator_category; 00242 00243 using pointer = typename std::conditional<__constant_iterators, 00244 const _Value*, _Value*>::type; 00245 00246 using reference = typename std::conditional<__constant_iterators, 00247 const _Value&, _Value&>::type; 00248 00249 _Node_iterator() 00250 : __base_type(0) { } 00251 00252 explicit 00253 _Node_iterator(__node_type* __p) 00254 : __base_type(__p) { } 00255 00256 reference 00257 operator*() const 00258 { return this->_M_cur->_M_v; } 00259 00260 pointer 00261 operator->() const 00262 { return std::__addressof(this->_M_cur->_M_v); } 00263 00264 _Node_iterator& 00265 operator++() 00266 { 00267 this->_M_incr(); 00268 return *this; 00269 } 00270 00271 _Node_iterator 00272 operator++(int) 00273 { 00274 _Node_iterator __tmp(*this); 00275 this->_M_incr(); 00276 return __tmp; 00277 } 00278 }; 00279 00280 /// Node const_iterators, used to iterate through all the hashtable. 00281 template<typename _Value, bool __constant_iterators, bool __cache> 00282 struct _Node_const_iterator 00283 : public _Node_iterator_base<_Value, __cache> 00284 { 00285 private: 00286 using __base_type = _Node_iterator_base<_Value, __cache>; 00287 using __node_type = typename __base_type::__node_type; 00288 00289 public: 00290 typedef _Value value_type; 00291 typedef std::ptrdiff_t difference_type; 00292 typedef std::forward_iterator_tag iterator_category; 00293 00294 typedef const _Value* pointer; 00295 typedef const _Value& reference; 00296 00297 _Node_const_iterator() 00298 : __base_type(0) { } 00299 00300 explicit 00301 _Node_const_iterator(__node_type* __p) 00302 : __base_type(__p) { } 00303 00304 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 00305 __cache>& __x) 00306 : __base_type(__x._M_cur) { } 00307 00308 reference 00309 operator*() const 00310 { return this->_M_cur->_M_v; } 00311 00312 pointer 00313 operator->() const 00314 { return std::__addressof(this->_M_cur->_M_v); } 00315 00316 _Node_const_iterator& 00317 operator++() 00318 { 00319 this->_M_incr(); 00320 return *this; 00321 } 00322 00323 _Node_const_iterator 00324 operator++(int) 00325 { 00326 _Node_const_iterator __tmp(*this); 00327 this->_M_incr(); 00328 return __tmp; 00329 } 00330 }; 00331 00332 // Many of class template _Hashtable's template parameters are policy 00333 // classes. These are defaults for the policies. 00334 00335 /// Default range hashing function: use division to fold a large number 00336 /// into the range [0, N). 00337 struct _Mod_range_hashing 00338 { 00339 typedef std::size_t first_argument_type; 00340 typedef std::size_t second_argument_type; 00341 typedef std::size_t result_type; 00342 00343 result_type 00344 operator()(first_argument_type __num, second_argument_type __den) const 00345 { return __num % __den; } 00346 }; 00347 00348 /// Default ranged hash function H. In principle it should be a 00349 /// function object composed from objects of type H1 and H2 such that 00350 /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of 00351 /// h1 and h2. So instead we'll just use a tag to tell class template 00352 /// hashtable to do that composition. 00353 struct _Default_ranged_hash { }; 00354 00355 /// Default value for rehash policy. Bucket size is (usually) the 00356 /// smallest prime that keeps the load factor small enough. 00357 struct _Prime_rehash_policy 00358 { 00359 _Prime_rehash_policy(float __z = 1.0) 00360 : _M_max_load_factor(__z), _M_next_resize(0) { } 00361 00362 float 00363 max_load_factor() const noexcept 00364 { return _M_max_load_factor; } 00365 00366 // Return a bucket size no smaller than n. 00367 std::size_t 00368 _M_next_bkt(std::size_t __n) const; 00369 00370 // Return a bucket count appropriate for n elements 00371 std::size_t 00372 _M_bkt_for_elements(std::size_t __n) const 00373 { return __builtin_ceil(__n / (long double)_M_max_load_factor); } 00374 00375 // __n_bkt is current bucket count, __n_elt is current element count, 00376 // and __n_ins is number of elements to be inserted. Do we need to 00377 // increase bucket count? If so, return make_pair(true, n), where n 00378 // is the new bucket count. If not, return make_pair(false, 0). 00379 std::pair<bool, std::size_t> 00380 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 00381 std::size_t __n_ins) const; 00382 00383 typedef std::size_t _State; 00384 00385 _State 00386 _M_state() const 00387 { return _M_next_resize; } 00388 00389 void 00390 _M_reset(_State __state) 00391 { _M_next_resize = __state; } 00392 00393 enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; 00394 00395 static const std::size_t _S_growth_factor = 2; 00396 00397 float _M_max_load_factor; 00398 mutable std::size_t _M_next_resize; 00399 }; 00400 00401 // Base classes for std::_Hashtable. We define these base classes 00402 // because in some cases we want to do different things depending on 00403 // the value of a policy class. In some cases the policy class 00404 // affects which member functions and nested typedefs are defined; 00405 // we handle that by specializing base class templates. Several of 00406 // the base class templates need to access other members of class 00407 // template _Hashtable, so we use a variant of the "Curiously 00408 // Recurring Template Pattern" (CRTP) technique. 00409 00410 /** 00411 * Primary class template _Map_base. 00412 * 00413 * If the hashtable has a value type of the form pair<T1, T2> and a 00414 * key extraction policy (_ExtractKey) that returns the first part 00415 * of the pair, the hashtable gets a mapped_type typedef. If it 00416 * satisfies those criteria and also has unique keys, then it also 00417 * gets an operator[]. 00418 */ 00419 template<typename _Key, typename _Value, typename _Alloc, 00420 typename _ExtractKey, typename _Equal, 00421 typename _H1, typename _H2, typename _Hash, 00422 typename _RehashPolicy, typename _Traits, 00423 bool _Unique_keys = _Traits::__unique_keys::value> 00424 struct _Map_base { }; 00425 00426 /// Partial specialization, __unique_keys set to false. 00427 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00428 typename _H1, typename _H2, typename _Hash, 00429 typename _RehashPolicy, typename _Traits> 00430 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00431 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 00432 { 00433 using mapped_type = typename std::tuple_element<1, _Pair>::type; 00434 }; 00435 00436 /// Partial specialization, __unique_keys set to true. 00437 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00438 typename _H1, typename _H2, typename _Hash, 00439 typename _RehashPolicy, typename _Traits> 00440 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00441 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 00442 { 00443 private: 00444 using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, 00445 _Select1st, 00446 _Equal, _H1, _H2, _Hash, 00447 _Traits>; 00448 00449 using __hashtable = _Hashtable<_Key, _Pair, _Alloc, 00450 _Select1st, _Equal, 00451 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 00452 00453 using __hash_code = typename __hashtable_base::__hash_code; 00454 using __node_type = typename __hashtable_base::__node_type; 00455 00456 public: 00457 using key_type = typename __hashtable_base::key_type; 00458 using iterator = typename __hashtable_base::iterator; 00459 using mapped_type = typename std::tuple_element<1, _Pair>::type; 00460 00461 mapped_type& 00462 operator[](const key_type& __k); 00463 00464 mapped_type& 00465 operator[](key_type&& __k); 00466 00467 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00468 // DR 761. unordered_map needs an at() member function. 00469 mapped_type& 00470 at(const key_type& __k); 00471 00472 const mapped_type& 00473 at(const key_type& __k) const; 00474 }; 00475 00476 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00477 typename _H1, typename _H2, typename _Hash, 00478 typename _RehashPolicy, typename _Traits> 00479 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00480 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 00481 ::mapped_type& 00482 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00483 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 00484 operator[](const key_type& __k) 00485 { 00486 __hashtable* __h = static_cast<__hashtable*>(this); 00487 __hash_code __code = __h->_M_hash_code(__k); 00488 std::size_t __n = __h->_M_bucket_index(__k, __code); 00489 __node_type* __p = __h->_M_find_node(__n, __k, __code); 00490 00491 if (!__p) 00492 { 00493 __p = __h->_M_allocate_node(std::piecewise_construct, 00494 std::tuple<const key_type&>(__k), 00495 std::tuple<>()); 00496 return __h->_M_insert_unique_node(__n, __code, __p)->second; 00497 } 00498 00499 return (__p->_M_v).second; 00500 } 00501 00502 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00503 typename _H1, typename _H2, typename _Hash, 00504 typename _RehashPolicy, typename _Traits> 00505 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00506 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 00507 ::mapped_type& 00508 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00509 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 00510 operator[](key_type&& __k) 00511 { 00512 __hashtable* __h = static_cast<__hashtable*>(this); 00513 __hash_code __code = __h->_M_hash_code(__k); 00514 std::size_t __n = __h->_M_bucket_index(__k, __code); 00515 __node_type* __p = __h->_M_find_node(__n, __k, __code); 00516 00517 if (!__p) 00518 { 00519 __p = __h->_M_allocate_node(std::piecewise_construct, 00520 std::forward_as_tuple(std::move(__k)), 00521 std::tuple<>()); 00522 return __h->_M_insert_unique_node(__n, __code, __p)->second; 00523 } 00524 00525 return (__p->_M_v).second; 00526 } 00527 00528 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00529 typename _H1, typename _H2, typename _Hash, 00530 typename _RehashPolicy, typename _Traits> 00531 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00532 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 00533 ::mapped_type& 00534 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00535 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 00536 at(const key_type& __k) 00537 { 00538 __hashtable* __h = static_cast<__hashtable*>(this); 00539 __hash_code __code = __h->_M_hash_code(__k); 00540 std::size_t __n = __h->_M_bucket_index(__k, __code); 00541 __node_type* __p = __h->_M_find_node(__n, __k, __code); 00542 00543 if (!__p) 00544 __throw_out_of_range(__N("_Map_base::at")); 00545 return (__p->_M_v).second; 00546 } 00547 00548 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00549 typename _H1, typename _H2, typename _Hash, 00550 typename _RehashPolicy, typename _Traits> 00551 const typename _Map_base<_Key, _Pair, _Alloc, _Select1st, 00552 _Equal, _H1, _H2, _Hash, _RehashPolicy, 00553 _Traits, true>::mapped_type& 00554 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00555 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 00556 at(const key_type& __k) const 00557 { 00558 const __hashtable* __h = static_cast<const __hashtable*>(this); 00559 __hash_code __code = __h->_M_hash_code(__k); 00560 std::size_t __n = __h->_M_bucket_index(__k, __code); 00561 __node_type* __p = __h->_M_find_node(__n, __k, __code); 00562 00563 if (!__p) 00564 __throw_out_of_range(__N("_Map_base::at")); 00565 return (__p->_M_v).second; 00566 } 00567 00568 /** 00569 * Primary class template _Insert_base. 00570 * 00571 * insert member functions appropriate to all _Hashtables. 00572 */ 00573 template<typename _Key, typename _Value, typename _Alloc, 00574 typename _ExtractKey, typename _Equal, 00575 typename _H1, typename _H2, typename _Hash, 00576 typename _RehashPolicy, typename _Traits> 00577 struct _Insert_base 00578 { 00579 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 00580 _Equal, _H1, _H2, _Hash, 00581 _RehashPolicy, _Traits>; 00582 00583 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, 00584 _Equal, _H1, _H2, _Hash, 00585 _Traits>; 00586 00587 using value_type = typename __hashtable_base::value_type; 00588 using iterator = typename __hashtable_base::iterator; 00589 using const_iterator = typename __hashtable_base::const_iterator; 00590 using size_type = typename __hashtable_base::size_type; 00591 00592 using __unique_keys = typename __hashtable_base::__unique_keys; 00593 using __ireturn_type = typename __hashtable_base::__ireturn_type; 00594 using __iconv_type = typename __hashtable_base::__iconv_type; 00595 00596 __hashtable& 00597 _M_conjure_hashtable() 00598 { return *(static_cast<__hashtable*>(this)); } 00599 00600 __ireturn_type 00601 insert(const value_type& __v) 00602 { 00603 __hashtable& __h = _M_conjure_hashtable(); 00604 return __h._M_insert(__v, __unique_keys()); 00605 } 00606 00607 iterator 00608 insert(const_iterator, const value_type& __v) 00609 { return __iconv_type()(insert(__v)); } 00610 00611 void 00612 insert(initializer_list<value_type> __l) 00613 { this->insert(__l.begin(), __l.end()); } 00614 00615 template<typename _InputIterator> 00616 void 00617 insert(_InputIterator __first, _InputIterator __last); 00618 }; 00619 00620 template<typename _Key, typename _Value, typename _Alloc, 00621 typename _ExtractKey, typename _Equal, 00622 typename _H1, typename _H2, typename _Hash, 00623 typename _RehashPolicy, typename _Traits> 00624 template<typename _InputIterator> 00625 void 00626 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 00627 _RehashPolicy, _Traits>:: 00628 insert(_InputIterator __first, _InputIterator __last) 00629 { 00630 using __rehash_type = typename __hashtable::__rehash_type; 00631 using __rehash_state = typename __hashtable::__rehash_state; 00632 using pair_type = std::pair<bool, std::size_t>; 00633 00634 size_type __n_elt = __detail::__distance_fw(__first, __last); 00635 00636 __hashtable& __h = _M_conjure_hashtable(); 00637 __rehash_type& __rehash = __h._M_rehash_policy; 00638 const __rehash_state& __saved_state = __rehash._M_state(); 00639 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count, 00640 __h._M_element_count, 00641 __n_elt); 00642 00643 if (__do_rehash.first) 00644 __h._M_rehash(__do_rehash.second, __saved_state); 00645 00646 for (; __first != __last; ++__first) 00647 __h._M_insert(*__first, __unique_keys()); 00648 } 00649 00650 /** 00651 * Primary class template _Insert. 00652 * 00653 * Select insert member functions appropriate to _Hashtable policy choices. 00654 */ 00655 template<typename _Key, typename _Value, typename _Alloc, 00656 typename _ExtractKey, typename _Equal, 00657 typename _H1, typename _H2, typename _Hash, 00658 typename _RehashPolicy, typename _Traits, 00659 bool _Constant_iterators = _Traits::__constant_iterators::value, 00660 bool _Unique_keys = _Traits::__unique_keys::value> 00661 struct _Insert; 00662 00663 /// Specialization. 00664 template<typename _Key, typename _Value, typename _Alloc, 00665 typename _ExtractKey, typename _Equal, 00666 typename _H1, typename _H2, typename _Hash, 00667 typename _RehashPolicy, typename _Traits> 00668 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 00669 _RehashPolicy, _Traits, true, true> 00670 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 00671 _H1, _H2, _Hash, _RehashPolicy, _Traits> 00672 { 00673 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 00674 _Equal, _H1, _H2, _Hash, 00675 _RehashPolicy, _Traits>; 00676 using value_type = typename __base_type::value_type; 00677 using iterator = typename __base_type::iterator; 00678 using const_iterator = typename __base_type::const_iterator; 00679 00680 using __unique_keys = typename __base_type::__unique_keys; 00681 using __hashtable = typename __base_type::__hashtable; 00682 00683 using __base_type::insert; 00684 00685 std::pair<iterator, bool> 00686 insert(value_type&& __v) 00687 { 00688 __hashtable& __h = this->_M_conjure_hashtable(); 00689 return __h._M_insert(std::move(__v), __unique_keys()); 00690 } 00691 00692 iterator 00693 insert(const_iterator, value_type&& __v) 00694 { return insert(std::move(__v)).first; } 00695 }; 00696 00697 /// Specialization. 00698 template<typename _Key, typename _Value, typename _Alloc, 00699 typename _ExtractKey, typename _Equal, 00700 typename _H1, typename _H2, typename _Hash, 00701 typename _RehashPolicy, typename _Traits> 00702 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 00703 _RehashPolicy, _Traits, true, false> 00704 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 00705 _H1, _H2, _Hash, _RehashPolicy, _Traits> 00706 { 00707 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 00708 _Equal, _H1, _H2, _Hash, 00709 _RehashPolicy, _Traits>; 00710 using value_type = typename __base_type::value_type; 00711 using iterator = typename __base_type::iterator; 00712 using const_iterator = typename __base_type::const_iterator; 00713 00714 using __unique_keys = typename __base_type::__unique_keys; 00715 using __hashtable = typename __base_type::__hashtable; 00716 00717 using __base_type::insert; 00718 00719 iterator 00720 insert(value_type&& __v) 00721 { 00722 __hashtable& __h = this->_M_conjure_hashtable(); 00723 return __h._M_insert(std::move(__v), __unique_keys()); 00724 } 00725 00726 iterator 00727 insert(const_iterator, value_type&& __v) 00728 { return insert(std::move(__v)); } 00729 }; 00730 00731 /// Specialization. 00732 template<typename _Key, typename _Value, typename _Alloc, 00733 typename _ExtractKey, typename _Equal, 00734 typename _H1, typename _H2, typename _Hash, 00735 typename _RehashPolicy, typename _Traits, bool _Unique_keys> 00736 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 00737 _RehashPolicy, _Traits, false, _Unique_keys> 00738 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 00739 _H1, _H2, _Hash, _RehashPolicy, _Traits> 00740 { 00741 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 00742 _Equal, _H1, _H2, _Hash, 00743 _RehashPolicy, _Traits>; 00744 using value_type = typename __base_type::value_type; 00745 using iterator = typename __base_type::iterator; 00746 using const_iterator = typename __base_type::const_iterator; 00747 00748 using __unique_keys = typename __base_type::__unique_keys; 00749 using __hashtable = typename __base_type::__hashtable; 00750 using __ireturn_type = typename __base_type::__ireturn_type; 00751 using __iconv_type = typename __base_type::__iconv_type; 00752 00753 using __base_type::insert; 00754 00755 template<typename _Pair> 00756 using __is_cons = std::is_constructible<value_type, _Pair&&>; 00757 00758 template<typename _Pair> 00759 using _IFcons = std::enable_if<__is_cons<_Pair>::value>; 00760 00761 template<typename _Pair> 00762 using _IFconsp = typename _IFcons<_Pair>::type; 00763 00764 template<typename _Pair, typename = _IFconsp<_Pair>> 00765 __ireturn_type 00766 insert(_Pair&& __v) 00767 { 00768 __hashtable& __h = this->_M_conjure_hashtable(); 00769 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v)); 00770 } 00771 00772 template<typename _Pair, typename = _IFconsp<_Pair>> 00773 iterator 00774 insert(const_iterator, _Pair&& __v) 00775 { return __iconv_type()(insert(std::forward<_Pair>(__v))); } 00776 }; 00777 00778 /** 00779 * Primary class template _Rehash_base. 00780 * 00781 * Give hashtable the max_load_factor functions and reserve iff the 00782 * rehash policy is _Prime_rehash_policy. 00783 */ 00784 template<typename _Key, typename _Value, typename _Alloc, 00785 typename _ExtractKey, typename _Equal, 00786 typename _H1, typename _H2, typename _Hash, 00787 typename _RehashPolicy, typename _Traits> 00788 struct _Rehash_base; 00789 00790 /// Specialization. 00791 template<typename _Key, typename _Value, typename _Alloc, 00792 typename _ExtractKey, typename _Equal, 00793 typename _H1, typename _H2, typename _Hash, typename _Traits> 00794 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 00795 _H1, _H2, _Hash, _Prime_rehash_policy, _Traits> 00796 { 00797 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 00798 _Equal, _H1, _H2, _Hash, 00799 _Prime_rehash_policy, _Traits>; 00800 00801 float 00802 max_load_factor() const noexcept 00803 { 00804 const __hashtable* __this = static_cast<const __hashtable*>(this); 00805 return __this->__rehash_policy().max_load_factor(); 00806 } 00807 00808 void 00809 max_load_factor(float __z) 00810 { 00811 __hashtable* __this = static_cast<__hashtable*>(this); 00812 __this->__rehash_policy(_Prime_rehash_policy(__z)); 00813 } 00814 00815 void 00816 reserve(std::size_t __n) 00817 { 00818 __hashtable* __this = static_cast<__hashtable*>(this); 00819 __this->rehash(__builtin_ceil(__n / max_load_factor())); 00820 } 00821 }; 00822 00823 /** 00824 * Primary class template _Hashtable_ebo_helper. 00825 * 00826 * Helper class using EBO when it is not forbidden, type is not 00827 * final, and when it worth it, type is empty. 00828 */ 00829 template<int _Nm, typename _Tp, 00830 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> 00831 struct _Hashtable_ebo_helper; 00832 00833 /// Specialization using EBO. 00834 template<int _Nm, typename _Tp> 00835 struct _Hashtable_ebo_helper<_Nm, _Tp, true> 00836 : private _Tp 00837 { 00838 _Hashtable_ebo_helper() = default; 00839 00840 _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) 00841 { } 00842 00843 static const _Tp& 00844 _S_cget(const _Hashtable_ebo_helper& __eboh) 00845 { return static_cast<const _Tp&>(__eboh); } 00846 00847 static _Tp& 00848 _S_get(_Hashtable_ebo_helper& __eboh) 00849 { return static_cast<_Tp&>(__eboh); } 00850 }; 00851 00852 /// Specialization not using EBO. 00853 template<int _Nm, typename _Tp> 00854 struct _Hashtable_ebo_helper<_Nm, _Tp, false> 00855 { 00856 _Hashtable_ebo_helper() = default; 00857 00858 _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) 00859 { } 00860 00861 static const _Tp& 00862 _S_cget(const _Hashtable_ebo_helper& __eboh) 00863 { return __eboh._M_tp; } 00864 00865 static _Tp& 00866 _S_get(_Hashtable_ebo_helper& __eboh) 00867 { return __eboh._M_tp; } 00868 00869 private: 00870 _Tp _M_tp; 00871 }; 00872 00873 /** 00874 * Primary class template _Local_iterator_base. 00875 * 00876 * Base class for local iterators, used to iterate within a bucket 00877 * but not between buckets. 00878 */ 00879 template<typename _Key, typename _Value, typename _ExtractKey, 00880 typename _H1, typename _H2, typename _Hash, 00881 bool __cache_hash_code> 00882 struct _Local_iterator_base; 00883 00884 /** 00885 * Primary class template _Hash_code_base. 00886 * 00887 * Encapsulates two policy issues that aren't quite orthogonal. 00888 * (1) the difference between using a ranged hash function and using 00889 * the combination of a hash function and a range-hashing function. 00890 * In the former case we don't have such things as hash codes, so 00891 * we have a dummy type as placeholder. 00892 * (2) Whether or not we cache hash codes. Caching hash codes is 00893 * meaningless if we have a ranged hash function. 00894 * 00895 * We also put the key extraction objects here, for convenience. 00896 * Each specialization derives from one or more of the template 00897 * parameters to benefit from Ebo. This is important as this type 00898 * is inherited in some cases by the _Local_iterator_base type used 00899 * to implement local_iterator and const_local_iterator. As with 00900 * any iterator type we prefer to make it as small as possible. 00901 * 00902 * Primary template is unused except as a hook for specializations. 00903 */ 00904 template<typename _Key, typename _Value, typename _ExtractKey, 00905 typename _H1, typename _H2, typename _Hash, 00906 bool __cache_hash_code> 00907 struct _Hash_code_base; 00908 00909 /// Specialization: ranged hash function, no caching hash codes. H1 00910 /// and H2 are provided but ignored. We define a dummy hash code type. 00911 template<typename _Key, typename _Value, typename _ExtractKey, 00912 typename _H1, typename _H2, typename _Hash> 00913 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> 00914 : private _Hashtable_ebo_helper<0, _ExtractKey>, 00915 private _Hashtable_ebo_helper<1, _Hash> 00916 { 00917 private: 00918 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 00919 using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>; 00920 00921 protected: 00922 typedef void* __hash_code; 00923 typedef _Hash_node<_Value, false> __node_type; 00924 00925 // We need the default constructor for the local iterators. 00926 _Hash_code_base() = default; 00927 00928 _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&, 00929 const _Hash& __h) 00930 : __ebo_extract_key(__ex), __ebo_hash(__h) { } 00931 00932 __hash_code 00933 _M_hash_code(const _Key& __key) const 00934 { return 0; } 00935 00936 std::size_t 00937 _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const 00938 { return _M_ranged_hash()(__k, __n); } 00939 00940 std::size_t 00941 _M_bucket_index(const __node_type* __p, std::size_t __n) const 00942 { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } 00943 00944 void 00945 _M_store_code(__node_type*, __hash_code) const 00946 { } 00947 00948 void 00949 _M_copy_code(__node_type*, const __node_type*) const 00950 { } 00951 00952 void 00953 _M_swap(_Hash_code_base& __x) 00954 { 00955 std::swap(_M_extract(), __x._M_extract()); 00956 std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 00957 } 00958 00959 const _ExtractKey& 00960 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 00961 00962 _ExtractKey& 00963 _M_extract() { return __ebo_extract_key::_S_get(*this); } 00964 00965 const _Hash& 00966 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); } 00967 00968 _Hash& 00969 _M_ranged_hash() { return __ebo_hash::_S_get(*this); } 00970 }; 00971 00972 // No specialization for ranged hash function while caching hash codes. 00973 // That combination is meaningless, and trying to do it is an error. 00974 00975 /// Specialization: ranged hash function, cache hash codes. This 00976 /// combination is meaningless, so we provide only a declaration 00977 /// and no definition. 00978 template<typename _Key, typename _Value, typename _ExtractKey, 00979 typename _H1, typename _H2, typename _Hash> 00980 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; 00981 00982 /// Specialization: hash function and range-hashing function, no 00983 /// caching of hash codes. 00984 /// Provides typedef and accessor required by C++ 11. 00985 template<typename _Key, typename _Value, typename _ExtractKey, 00986 typename _H1, typename _H2> 00987 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 00988 _Default_ranged_hash, false> 00989 : private _Hashtable_ebo_helper<0, _ExtractKey>, 00990 private _Hashtable_ebo_helper<1, _H1>, 00991 private _Hashtable_ebo_helper<2, _H2> 00992 { 00993 private: 00994 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 00995 using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; 00996 using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; 00997 00998 public: 00999 typedef _H1 hasher; 01000 01001 hasher 01002 hash_function() const 01003 { return _M_h1(); } 01004 01005 protected: 01006 typedef std::size_t __hash_code; 01007 typedef _Hash_node<_Value, false> __node_type; 01008 01009 // We need the default constructor for the local iterators. 01010 _Hash_code_base() = default; 01011 01012 _Hash_code_base(const _ExtractKey& __ex, 01013 const _H1& __h1, const _H2& __h2, 01014 const _Default_ranged_hash&) 01015 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 01016 01017 __hash_code 01018 _M_hash_code(const _Key& __k) const 01019 { return _M_h1()(__k); } 01020 01021 std::size_t 01022 _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const 01023 { return _M_h2()(__c, __n); } 01024 01025 std::size_t 01026 _M_bucket_index(const __node_type* __p, 01027 std::size_t __n) const 01028 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } 01029 01030 void 01031 _M_store_code(__node_type*, __hash_code) const 01032 { } 01033 01034 void 01035 _M_copy_code(__node_type*, const __node_type*) const 01036 { } 01037 01038 void 01039 _M_swap(_Hash_code_base& __x) 01040 { 01041 std::swap(_M_extract(), __x._M_extract()); 01042 std::swap(_M_h1(), __x._M_h1()); 01043 std::swap(_M_h2(), __x._M_h2()); 01044 } 01045 01046 const _ExtractKey& 01047 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 01048 01049 _ExtractKey& 01050 _M_extract() { return __ebo_extract_key::_S_get(*this); } 01051 01052 const _H1& 01053 _M_h1() const { return __ebo_h1::_S_cget(*this); } 01054 01055 _H1& 01056 _M_h1() { return __ebo_h1::_S_get(*this); } 01057 01058 const _H2& 01059 _M_h2() const { return __ebo_h2::_S_cget(*this); } 01060 01061 _H2& 01062 _M_h2() { return __ebo_h2::_S_get(*this); } 01063 }; 01064 01065 /// Specialization: hash function and range-hashing function, 01066 /// caching hash codes. H is provided but ignored. Provides 01067 /// typedef and accessor required by C++ 11. 01068 template<typename _Key, typename _Value, typename _ExtractKey, 01069 typename _H1, typename _H2> 01070 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 01071 _Default_ranged_hash, true> 01072 : private _Hashtable_ebo_helper<0, _ExtractKey>, 01073 private _Hashtable_ebo_helper<1, _H1>, 01074 private _Hashtable_ebo_helper<2, _H2> 01075 { 01076 private: 01077 // Gives access to _M_h2() to the local iterator implementation. 01078 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, 01079 _Default_ranged_hash, true>; 01080 01081 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 01082 using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; 01083 using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; 01084 01085 public: 01086 typedef _H1 hasher; 01087 01088 hasher 01089 hash_function() const 01090 { return _M_h1(); } 01091 01092 protected: 01093 typedef std::size_t __hash_code; 01094 typedef _Hash_node<_Value, true> __node_type; 01095 01096 _Hash_code_base(const _ExtractKey& __ex, 01097 const _H1& __h1, const _H2& __h2, 01098 const _Default_ranged_hash&) 01099 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 01100 01101 __hash_code 01102 _M_hash_code(const _Key& __k) const 01103 { return _M_h1()(__k); } 01104 01105 std::size_t 01106 _M_bucket_index(const _Key&, __hash_code __c, 01107 std::size_t __n) const 01108 { return _M_h2()(__c, __n); } 01109 01110 std::size_t 01111 _M_bucket_index(const __node_type* __p, std::size_t __n) const 01112 { return _M_h2()(__p->_M_hash_code, __n); } 01113 01114 void 01115 _M_store_code(__node_type* __n, __hash_code __c) const 01116 { __n->_M_hash_code = __c; } 01117 01118 void 01119 _M_copy_code(__node_type* __to, const __node_type* __from) const 01120 { __to->_M_hash_code = __from->_M_hash_code; } 01121 01122 void 01123 _M_swap(_Hash_code_base& __x) 01124 { 01125 std::swap(_M_extract(), __x._M_extract()); 01126 std::swap(_M_h1(), __x._M_h1()); 01127 std::swap(_M_h2(), __x._M_h2()); 01128 } 01129 01130 const _ExtractKey& 01131 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 01132 01133 _ExtractKey& 01134 _M_extract() { return __ebo_extract_key::_S_get(*this); } 01135 01136 const _H1& 01137 _M_h1() const { return __ebo_h1::_S_cget(*this); } 01138 01139 _H1& 01140 _M_h1() { return __ebo_h1::_S_get(*this); } 01141 01142 const _H2& 01143 _M_h2() const { return __ebo_h2::_S_cget(*this); } 01144 01145 _H2& 01146 _M_h2() { return __ebo_h2::_S_get(*this); } 01147 }; 01148 01149 /** 01150 * Primary class template _Equal_helper. 01151 * 01152 */ 01153 template <typename _Key, typename _Value, typename _ExtractKey, 01154 typename _Equal, typename _HashCodeType, 01155 bool __cache_hash_code> 01156 struct _Equal_helper; 01157 01158 /// Specialization. 01159 template<typename _Key, typename _Value, typename _ExtractKey, 01160 typename _Equal, typename _HashCodeType> 01161 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> 01162 { 01163 static bool 01164 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 01165 const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n) 01166 { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); } 01167 }; 01168 01169 /// Specialization. 01170 template<typename _Key, typename _Value, typename _ExtractKey, 01171 typename _Equal, typename _HashCodeType> 01172 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> 01173 { 01174 static bool 01175 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 01176 const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n) 01177 { return __eq(__k, __extract(__n->_M_v)); } 01178 }; 01179 01180 01181 /// Specialization. 01182 template<typename _Key, typename _Value, typename _ExtractKey, 01183 typename _H1, typename _H2, typename _Hash> 01184 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 01185 _H1, _H2, _Hash, true> 01186 : private _Hashtable_ebo_helper<0, _H2> 01187 { 01188 protected: 01189 using __base_type = _Hashtable_ebo_helper<0, _H2>; 01190 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 01191 _H1, _H2, _Hash, true>; 01192 01193 public: 01194 _Local_iterator_base() = default; 01195 _Local_iterator_base(const __hash_code_base& __base, 01196 _Hash_node<_Value, true>* __p, 01197 std::size_t __bkt, std::size_t __bkt_count) 01198 : __base_type(__base._M_h2()), 01199 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 01200 01201 void 01202 _M_incr() 01203 { 01204 _M_cur = _M_cur->_M_next(); 01205 if (_M_cur) 01206 { 01207 std::size_t __bkt 01208 = __base_type::_S_get(*this)(_M_cur->_M_hash_code, 01209 _M_bucket_count); 01210 if (__bkt != _M_bucket) 01211 _M_cur = nullptr; 01212 } 01213 } 01214 01215 _Hash_node<_Value, true>* _M_cur; 01216 std::size_t _M_bucket; 01217 std::size_t _M_bucket_count; 01218 }; 01219 01220 /// Specialization. 01221 template<typename _Key, typename _Value, typename _ExtractKey, 01222 typename _H1, typename _H2, typename _Hash> 01223 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 01224 _H1, _H2, _Hash, false> 01225 : private _Hash_code_base<_Key, _Value, _ExtractKey, 01226 _H1, _H2, _Hash, false> 01227 { 01228 protected: 01229 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 01230 _H1, _H2, _Hash, false>; 01231 01232 public: 01233 _Local_iterator_base() = default; 01234 _Local_iterator_base(const __hash_code_base& __base, 01235 _Hash_node<_Value, false>* __p, 01236 std::size_t __bkt, std::size_t __bkt_count) 01237 : __hash_code_base(__base), 01238 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 01239 01240 void 01241 _M_incr() 01242 { 01243 _M_cur = _M_cur->_M_next(); 01244 if (_M_cur) 01245 { 01246 std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count); 01247 if (__bkt != _M_bucket) 01248 _M_cur = nullptr; 01249 } 01250 } 01251 01252 _Hash_node<_Value, false>* _M_cur; 01253 std::size_t _M_bucket; 01254 std::size_t _M_bucket_count; 01255 }; 01256 01257 template<typename _Key, typename _Value, typename _ExtractKey, 01258 typename _H1, typename _H2, typename _Hash, bool __cache> 01259 inline bool 01260 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, 01261 _H1, _H2, _Hash, __cache>& __x, 01262 const _Local_iterator_base<_Key, _Value, _ExtractKey, 01263 _H1, _H2, _Hash, __cache>& __y) 01264 { return __x._M_cur == __y._M_cur; } 01265 01266 template<typename _Key, typename _Value, typename _ExtractKey, 01267 typename _H1, typename _H2, typename _Hash, bool __cache> 01268 inline bool 01269 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, 01270 _H1, _H2, _Hash, __cache>& __x, 01271 const _Local_iterator_base<_Key, _Value, _ExtractKey, 01272 _H1, _H2, _Hash, __cache>& __y) 01273 { return __x._M_cur != __y._M_cur; } 01274 01275 /// local iterators 01276 template<typename _Key, typename _Value, typename _ExtractKey, 01277 typename _H1, typename _H2, typename _Hash, 01278 bool __constant_iterators, bool __cache> 01279 struct _Local_iterator 01280 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 01281 _H1, _H2, _Hash, __cache> 01282 { 01283 private: 01284 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, 01285 _H1, _H2, _Hash, __cache>; 01286 using __hash_code_base = typename __base_type::__hash_code_base; 01287 public: 01288 typedef _Value value_type; 01289 typedef typename std::conditional<__constant_iterators, 01290 const _Value*, _Value*>::type 01291 pointer; 01292 typedef typename std::conditional<__constant_iterators, 01293 const _Value&, _Value&>::type 01294 reference; 01295 typedef std::ptrdiff_t difference_type; 01296 typedef std::forward_iterator_tag iterator_category; 01297 01298 _Local_iterator() = default; 01299 01300 _Local_iterator(const __hash_code_base& __base, 01301 _Hash_node<_Value, __cache>* __p, 01302 std::size_t __bkt, std::size_t __bkt_count) 01303 : __base_type(__base, __p, __bkt, __bkt_count) 01304 { } 01305 01306 reference 01307 operator*() const 01308 { return this->_M_cur->_M_v; } 01309 01310 pointer 01311 operator->() const 01312 { return std::__addressof(this->_M_cur->_M_v); } 01313 01314 _Local_iterator& 01315 operator++() 01316 { 01317 this->_M_incr(); 01318 return *this; 01319 } 01320 01321 _Local_iterator 01322 operator++(int) 01323 { 01324 _Local_iterator __tmp(*this); 01325 this->_M_incr(); 01326 return __tmp; 01327 } 01328 }; 01329 01330 /// local const_iterators 01331 template<typename _Key, typename _Value, typename _ExtractKey, 01332 typename _H1, typename _H2, typename _Hash, 01333 bool __constant_iterators, bool __cache> 01334 struct _Local_const_iterator 01335 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 01336 _H1, _H2, _Hash, __cache> 01337 { 01338 private: 01339 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, 01340 _H1, _H2, _Hash, __cache>; 01341 using __hash_code_base = typename __base_type::__hash_code_base; 01342 01343 public: 01344 typedef _Value value_type; 01345 typedef const _Value* pointer; 01346 typedef const _Value& reference; 01347 typedef std::ptrdiff_t difference_type; 01348 typedef std::forward_iterator_tag iterator_category; 01349 01350 _Local_const_iterator() = default; 01351 01352 _Local_const_iterator(const __hash_code_base& __base, 01353 _Hash_node<_Value, __cache>* __p, 01354 std::size_t __bkt, std::size_t __bkt_count) 01355 : __base_type(__base, __p, __bkt, __bkt_count) 01356 { } 01357 01358 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 01359 _H1, _H2, _Hash, 01360 __constant_iterators, 01361 __cache>& __x) 01362 : __base_type(__x) 01363 { } 01364 01365 reference 01366 operator*() const 01367 { return this->_M_cur->_M_v; } 01368 01369 pointer 01370 operator->() const 01371 { return std::__addressof(this->_M_cur->_M_v); } 01372 01373 _Local_const_iterator& 01374 operator++() 01375 { 01376 this->_M_incr(); 01377 return *this; 01378 } 01379 01380 _Local_const_iterator 01381 operator++(int) 01382 { 01383 _Local_const_iterator __tmp(*this); 01384 this->_M_incr(); 01385 return __tmp; 01386 } 01387 }; 01388 01389 /** 01390 * Primary class template _Hashtable_base. 01391 * 01392 * Helper class adding management of _Equal functor to 01393 * _Hash_code_base type. 01394 * 01395 * Base class templates are: 01396 * - __detail::_Hash_code_base 01397 * - __detail::_Hashtable_ebo_helper 01398 */ 01399 template<typename _Key, typename _Value, 01400 typename _ExtractKey, typename _Equal, 01401 typename _H1, typename _H2, typename _Hash, typename _Traits> 01402 struct _Hashtable_base 01403 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 01404 _Traits::__hash_cached::value>, 01405 private _Hashtable_ebo_helper<0, _Equal> 01406 { 01407 public: 01408 typedef _Key key_type; 01409 typedef _Value value_type; 01410 typedef _Equal key_equal; 01411 typedef std::size_t size_type; 01412 typedef std::ptrdiff_t difference_type; 01413 01414 using __traits_type = _Traits; 01415 using __hash_cached = typename __traits_type::__hash_cached; 01416 using __constant_iterators = typename __traits_type::__constant_iterators; 01417 using __unique_keys = typename __traits_type::__unique_keys; 01418 01419 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 01420 _H1, _H2, _Hash, 01421 __hash_cached::value>; 01422 01423 using __hash_code = typename __hash_code_base::__hash_code; 01424 using __node_type = typename __hash_code_base::__node_type; 01425 01426 using iterator = __detail::_Node_iterator<value_type, 01427 __constant_iterators::value, 01428 __hash_cached::value>; 01429 01430 using const_iterator = __detail::_Node_const_iterator<value_type, 01431 __constant_iterators::value, 01432 __hash_cached::value>; 01433 01434 using local_iterator = __detail::_Local_iterator<key_type, value_type, 01435 _ExtractKey, _H1, _H2, _Hash, 01436 __constant_iterators::value, 01437 __hash_cached::value>; 01438 01439 using const_local_iterator = __detail::_Local_const_iterator<key_type, 01440 value_type, 01441 _ExtractKey, _H1, _H2, _Hash, 01442 __constant_iterators::value, 01443 __hash_cached::value>; 01444 01445 using __ireturn_type = typename std::conditional<__unique_keys::value, 01446 std::pair<iterator, bool>, 01447 iterator>::type; 01448 01449 using __iconv_type = typename std::conditional<__unique_keys::value, 01450 _Select1st, _Identity 01451 >::type; 01452 private: 01453 using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; 01454 using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, 01455 __hash_code, __hash_cached::value>; 01456 01457 protected: 01458 using __node_base = __detail::_Hash_node_base; 01459 using __bucket_type = __node_base*; 01460 01461 _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, 01462 const _Hash& __hash, const _Equal& __eq) 01463 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) 01464 { } 01465 01466 bool 01467 _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const 01468 { 01469 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 01470 __k, __c, __n); 01471 } 01472 01473 void 01474 _M_swap(_Hashtable_base& __x) 01475 { 01476 __hash_code_base::_M_swap(__x); 01477 std::swap(_M_eq(), __x._M_eq()); 01478 } 01479 01480 const _Equal& 01481 _M_eq() const { return _EqualEBO::_S_cget(*this); } 01482 01483 _Equal& 01484 _M_eq() { return _EqualEBO::_S_get(*this); } 01485 }; 01486 01487 /** 01488 * struct _Equality_base. 01489 * 01490 * Common types and functions for class _Equality. 01491 */ 01492 struct _Equality_base 01493 { 01494 protected: 01495 template<typename _Uiterator> 01496 static bool 01497 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 01498 }; 01499 01500 // See std::is_permutation in N3068. 01501 template<typename _Uiterator> 01502 bool 01503 _Equality_base:: 01504 _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 01505 _Uiterator __first2) 01506 { 01507 for (; __first1 != __last1; ++__first1, ++__first2) 01508 if (!(*__first1 == *__first2)) 01509 break; 01510 01511 if (__first1 == __last1) 01512 return true; 01513 01514 _Uiterator __last2 = __first2; 01515 std::advance(__last2, std::distance(__first1, __last1)); 01516 01517 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 01518 { 01519 _Uiterator __tmp = __first1; 01520 while (__tmp != __it1 && !bool(*__tmp == *__it1)) 01521 ++__tmp; 01522 01523 // We've seen this one before. 01524 if (__tmp != __it1) 01525 continue; 01526 01527 std::ptrdiff_t __n2 = 0; 01528 for (__tmp = __first2; __tmp != __last2; ++__tmp) 01529 if (*__tmp == *__it1) 01530 ++__n2; 01531 01532 if (!__n2) 01533 return false; 01534 01535 std::ptrdiff_t __n1 = 0; 01536 for (__tmp = __it1; __tmp != __last1; ++__tmp) 01537 if (*__tmp == *__it1) 01538 ++__n1; 01539 01540 if (__n1 != __n2) 01541 return false; 01542 } 01543 return true; 01544 } 01545 01546 /** 01547 * Primary class template _Equality. 01548 * 01549 * This is for implementing equality comparison for unordered 01550 * containers, per N3068, by John Lakos and Pablo Halpern. 01551 * Algorithmically, we follow closely the reference implementations 01552 * therein. 01553 */ 01554 template<typename _Key, typename _Value, typename _Alloc, 01555 typename _ExtractKey, typename _Equal, 01556 typename _H1, typename _H2, typename _Hash, 01557 typename _RehashPolicy, typename _Traits, 01558 bool _Unique_keys = _Traits::__unique_keys::value> 01559 struct _Equality; 01560 01561 /// Specialization. 01562 template<typename _Key, typename _Value, typename _Alloc, 01563 typename _ExtractKey, typename _Equal, 01564 typename _H1, typename _H2, typename _Hash, 01565 typename _RehashPolicy, typename _Traits> 01566 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01567 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 01568 { 01569 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01570 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 01571 01572 bool 01573 _M_equal(const __hashtable&) const; 01574 }; 01575 01576 template<typename _Key, typename _Value, typename _Alloc, 01577 typename _ExtractKey, typename _Equal, 01578 typename _H1, typename _H2, typename _Hash, 01579 typename _RehashPolicy, typename _Traits> 01580 bool 01581 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01582 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 01583 _M_equal(const __hashtable& __other) const 01584 { 01585 const __hashtable* __this = static_cast<const __hashtable*>(this); 01586 01587 if (__this->size() != __other.size()) 01588 return false; 01589 01590 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 01591 { 01592 const auto __ity = __other.find(_ExtractKey()(*__itx)); 01593 if (__ity == __other.end() || !bool(*__ity == *__itx)) 01594 return false; 01595 } 01596 return true; 01597 } 01598 01599 /// Specialization. 01600 template<typename _Key, typename _Value, typename _Alloc, 01601 typename _ExtractKey, typename _Equal, 01602 typename _H1, typename _H2, typename _Hash, 01603 typename _RehashPolicy, typename _Traits> 01604 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01605 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 01606 : public _Equality_base 01607 { 01608 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01609 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 01610 01611 bool 01612 _M_equal(const __hashtable&) const; 01613 }; 01614 01615 template<typename _Key, typename _Value, typename _Alloc, 01616 typename _ExtractKey, typename _Equal, 01617 typename _H1, typename _H2, typename _Hash, 01618 typename _RehashPolicy, typename _Traits> 01619 bool 01620 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01621 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: 01622 _M_equal(const __hashtable& __other) const 01623 { 01624 const __hashtable* __this = static_cast<const __hashtable*>(this); 01625 01626 if (__this->size() != __other.size()) 01627 return false; 01628 01629 for (auto __itx = __this->begin(); __itx != __this->end();) 01630 { 01631 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 01632 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 01633 01634 if (std::distance(__xrange.first, __xrange.second) 01635 != std::distance(__yrange.first, __yrange.second)) 01636 return false; 01637 01638 if (!_S_is_permutation(__xrange.first, __xrange.second, 01639 __yrange.first)) 01640 return false; 01641 01642 __itx = __xrange.second; 01643 } 01644 return true; 01645 } 01646 01647 /** 01648 * This type is to combine a _Hash_node_base instance with an allocator 01649 * instance through inheritance to benefit from EBO when possible. 01650 */ 01651 template<typename _NodeAlloc> 01652 struct _Before_begin : public _NodeAlloc 01653 { 01654 _Hash_node_base _M_node; 01655 01656 _Before_begin(const _Before_begin&) = default; 01657 _Before_begin(_Before_begin&&) = default; 01658 01659 template<typename _Alloc> 01660 _Before_begin(_Alloc&& __a) 01661 : _NodeAlloc(std::forward<_Alloc>(__a)) 01662 { } 01663 }; 01664 01665 //@} hashtable-detail 01666 _GLIBCXX_END_NAMESPACE_VERSION 01667 } // namespace __detail 01668 } // namespace std 01669 01670 #endif // _HASHTABLE_POLICY_H