libstdc++
|
00001 // Internal policy header for unordered_set and unordered_map -*- C++ -*- 00002 00003 // Copyright (C) 2010-2019 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 #include <tuple> // for std::tuple, std::forward_as_tuple 00035 #include <limits> // for std::numeric_limits 00036 #include <bits/stl_algobase.h> // for std::min. 00037 00038 namespace std _GLIBCXX_VISIBILITY(default) 00039 { 00040 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00041 00042 template<typename _Key, typename _Value, typename _Alloc, 00043 typename _ExtractKey, typename _Equal, 00044 typename _H1, typename _H2, typename _Hash, 00045 typename _RehashPolicy, typename _Traits> 00046 class _Hashtable; 00047 00048 namespace __detail 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/1 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 __first != __last ? 1 : 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 { return __distance_fw(__first, __last, 00078 std::__iterator_category(__first)); } 00079 00080 struct _Identity 00081 { 00082 template<typename _Tp> 00083 _Tp&& 00084 operator()(_Tp&& __x) const 00085 { return std::forward<_Tp>(__x); } 00086 }; 00087 00088 struct _Select1st 00089 { 00090 template<typename _Tp> 00091 auto 00092 operator()(_Tp&& __x) const 00093 -> decltype(std::get<0>(std::forward<_Tp>(__x))) 00094 { return std::get<0>(std::forward<_Tp>(__x)); } 00095 }; 00096 00097 template<typename _NodeAlloc> 00098 struct _Hashtable_alloc; 00099 00100 // Functor recycling a pool of nodes and using allocation once the pool is 00101 // empty. 00102 template<typename _NodeAlloc> 00103 struct _ReuseOrAllocNode 00104 { 00105 private: 00106 using __node_alloc_type = _NodeAlloc; 00107 using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>; 00108 using __node_alloc_traits = 00109 typename __hashtable_alloc::__node_alloc_traits; 00110 using __node_type = typename __hashtable_alloc::__node_type; 00111 00112 public: 00113 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h) 00114 : _M_nodes(__nodes), _M_h(__h) { } 00115 _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete; 00116 00117 ~_ReuseOrAllocNode() 00118 { _M_h._M_deallocate_nodes(_M_nodes); } 00119 00120 template<typename _Arg> 00121 __node_type* 00122 operator()(_Arg&& __arg) const 00123 { 00124 if (_M_nodes) 00125 { 00126 __node_type* __node = _M_nodes; 00127 _M_nodes = _M_nodes->_M_next(); 00128 __node->_M_nxt = nullptr; 00129 auto& __a = _M_h._M_node_allocator(); 00130 __node_alloc_traits::destroy(__a, __node->_M_valptr()); 00131 __try 00132 { 00133 __node_alloc_traits::construct(__a, __node->_M_valptr(), 00134 std::forward<_Arg>(__arg)); 00135 } 00136 __catch(...) 00137 { 00138 _M_h._M_deallocate_node_ptr(__node); 00139 __throw_exception_again; 00140 } 00141 return __node; 00142 } 00143 return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); 00144 } 00145 00146 private: 00147 mutable __node_type* _M_nodes; 00148 __hashtable_alloc& _M_h; 00149 }; 00150 00151 // Functor similar to the previous one but without any pool of nodes to 00152 // recycle. 00153 template<typename _NodeAlloc> 00154 struct _AllocNode 00155 { 00156 private: 00157 using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; 00158 using __node_type = typename __hashtable_alloc::__node_type; 00159 00160 public: 00161 _AllocNode(__hashtable_alloc& __h) 00162 : _M_h(__h) { } 00163 00164 template<typename _Arg> 00165 __node_type* 00166 operator()(_Arg&& __arg) const 00167 { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); } 00168 00169 private: 00170 __hashtable_alloc& _M_h; 00171 }; 00172 00173 // Auxiliary types used for all instantiations of _Hashtable nodes 00174 // and iterators. 00175 00176 /** 00177 * struct _Hashtable_traits 00178 * 00179 * Important traits for hash tables. 00180 * 00181 * @tparam _Cache_hash_code Boolean value. True if the value of 00182 * the hash function is stored along with the value. This is a 00183 * time-space tradeoff. Storing it may improve lookup speed by 00184 * reducing the number of times we need to call the _Equal 00185 * function. 00186 * 00187 * @tparam _Constant_iterators Boolean value. True if iterator and 00188 * const_iterator are both constant iterator types. This is true 00189 * for unordered_set and unordered_multiset, false for 00190 * unordered_map and unordered_multimap. 00191 * 00192 * @tparam _Unique_keys Boolean value. True if the return value 00193 * of _Hashtable::count(k) is always at most one, false if it may 00194 * be an arbitrary number. This is true for unordered_set and 00195 * unordered_map, false for unordered_multiset and 00196 * unordered_multimap. 00197 */ 00198 template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys> 00199 struct _Hashtable_traits 00200 { 00201 using __hash_cached = __bool_constant<_Cache_hash_code>; 00202 using __constant_iterators = __bool_constant<_Constant_iterators>; 00203 using __unique_keys = __bool_constant<_Unique_keys>; 00204 }; 00205 00206 /** 00207 * struct _Hash_node_base 00208 * 00209 * Nodes, used to wrap elements stored in the hash table. A policy 00210 * template parameter of class template _Hashtable controls whether 00211 * nodes also store a hash code. In some cases (e.g. strings) this 00212 * may be a performance win. 00213 */ 00214 struct _Hash_node_base 00215 { 00216 _Hash_node_base* _M_nxt; 00217 00218 _Hash_node_base() noexcept : _M_nxt() { } 00219 00220 _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { } 00221 }; 00222 00223 /** 00224 * struct _Hash_node_value_base 00225 * 00226 * Node type with the value to store. 00227 */ 00228 template<typename _Value> 00229 struct _Hash_node_value_base : _Hash_node_base 00230 { 00231 typedef _Value value_type; 00232 00233 __gnu_cxx::__aligned_buffer<_Value> _M_storage; 00234 00235 _Value* 00236 _M_valptr() noexcept 00237 { return _M_storage._M_ptr(); } 00238 00239 const _Value* 00240 _M_valptr() const noexcept 00241 { return _M_storage._M_ptr(); } 00242 00243 _Value& 00244 _M_v() noexcept 00245 { return *_M_valptr(); } 00246 00247 const _Value& 00248 _M_v() const noexcept 00249 { return *_M_valptr(); } 00250 }; 00251 00252 /** 00253 * Primary template struct _Hash_node. 00254 */ 00255 template<typename _Value, bool _Cache_hash_code> 00256 struct _Hash_node; 00257 00258 /** 00259 * Specialization for nodes with caches, struct _Hash_node. 00260 * 00261 * Base class is __detail::_Hash_node_value_base. 00262 */ 00263 template<typename _Value> 00264 struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value> 00265 { 00266 std::size_t _M_hash_code; 00267 00268 _Hash_node* 00269 _M_next() const noexcept 00270 { return static_cast<_Hash_node*>(this->_M_nxt); } 00271 }; 00272 00273 /** 00274 * Specialization for nodes without caches, struct _Hash_node. 00275 * 00276 * Base class is __detail::_Hash_node_value_base. 00277 */ 00278 template<typename _Value> 00279 struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value> 00280 { 00281 _Hash_node* 00282 _M_next() const noexcept 00283 { return static_cast<_Hash_node*>(this->_M_nxt); } 00284 }; 00285 00286 /// Base class for node iterators. 00287 template<typename _Value, bool _Cache_hash_code> 00288 struct _Node_iterator_base 00289 { 00290 using __node_type = _Hash_node<_Value, _Cache_hash_code>; 00291 00292 __node_type* _M_cur; 00293 00294 _Node_iterator_base(__node_type* __p) noexcept 00295 : _M_cur(__p) { } 00296 00297 void 00298 _M_incr() noexcept 00299 { _M_cur = _M_cur->_M_next(); } 00300 }; 00301 00302 template<typename _Value, bool _Cache_hash_code> 00303 inline bool 00304 operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, 00305 const _Node_iterator_base<_Value, _Cache_hash_code >& __y) 00306 noexcept 00307 { return __x._M_cur == __y._M_cur; } 00308 00309 template<typename _Value, bool _Cache_hash_code> 00310 inline bool 00311 operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, 00312 const _Node_iterator_base<_Value, _Cache_hash_code>& __y) 00313 noexcept 00314 { return __x._M_cur != __y._M_cur; } 00315 00316 /// Node iterators, used to iterate through all the hashtable. 00317 template<typename _Value, bool __constant_iterators, bool __cache> 00318 struct _Node_iterator 00319 : public _Node_iterator_base<_Value, __cache> 00320 { 00321 private: 00322 using __base_type = _Node_iterator_base<_Value, __cache>; 00323 using __node_type = typename __base_type::__node_type; 00324 00325 public: 00326 typedef _Value value_type; 00327 typedef std::ptrdiff_t difference_type; 00328 typedef std::forward_iterator_tag iterator_category; 00329 00330 using pointer = typename std::conditional<__constant_iterators, 00331 const _Value*, _Value*>::type; 00332 00333 using reference = typename std::conditional<__constant_iterators, 00334 const _Value&, _Value&>::type; 00335 00336 _Node_iterator() noexcept 00337 : __base_type(0) { } 00338 00339 explicit 00340 _Node_iterator(__node_type* __p) noexcept 00341 : __base_type(__p) { } 00342 00343 reference 00344 operator*() const noexcept 00345 { return this->_M_cur->_M_v(); } 00346 00347 pointer 00348 operator->() const noexcept 00349 { return this->_M_cur->_M_valptr(); } 00350 00351 _Node_iterator& 00352 operator++() noexcept 00353 { 00354 this->_M_incr(); 00355 return *this; 00356 } 00357 00358 _Node_iterator 00359 operator++(int) noexcept 00360 { 00361 _Node_iterator __tmp(*this); 00362 this->_M_incr(); 00363 return __tmp; 00364 } 00365 }; 00366 00367 /// Node const_iterators, used to iterate through all the hashtable. 00368 template<typename _Value, bool __constant_iterators, bool __cache> 00369 struct _Node_const_iterator 00370 : public _Node_iterator_base<_Value, __cache> 00371 { 00372 private: 00373 using __base_type = _Node_iterator_base<_Value, __cache>; 00374 using __node_type = typename __base_type::__node_type; 00375 00376 public: 00377 typedef _Value value_type; 00378 typedef std::ptrdiff_t difference_type; 00379 typedef std::forward_iterator_tag iterator_category; 00380 00381 typedef const _Value* pointer; 00382 typedef const _Value& reference; 00383 00384 _Node_const_iterator() noexcept 00385 : __base_type(0) { } 00386 00387 explicit 00388 _Node_const_iterator(__node_type* __p) noexcept 00389 : __base_type(__p) { } 00390 00391 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 00392 __cache>& __x) noexcept 00393 : __base_type(__x._M_cur) { } 00394 00395 reference 00396 operator*() const noexcept 00397 { return this->_M_cur->_M_v(); } 00398 00399 pointer 00400 operator->() const noexcept 00401 { return this->_M_cur->_M_valptr(); } 00402 00403 _Node_const_iterator& 00404 operator++() noexcept 00405 { 00406 this->_M_incr(); 00407 return *this; 00408 } 00409 00410 _Node_const_iterator 00411 operator++(int) noexcept 00412 { 00413 _Node_const_iterator __tmp(*this); 00414 this->_M_incr(); 00415 return __tmp; 00416 } 00417 }; 00418 00419 // Many of class template _Hashtable's template parameters are policy 00420 // classes. These are defaults for the policies. 00421 00422 /// Default range hashing function: use division to fold a large number 00423 /// into the range [0, N). 00424 struct _Mod_range_hashing 00425 { 00426 typedef std::size_t first_argument_type; 00427 typedef std::size_t second_argument_type; 00428 typedef std::size_t result_type; 00429 00430 result_type 00431 operator()(first_argument_type __num, 00432 second_argument_type __den) const noexcept 00433 { return __num % __den; } 00434 }; 00435 00436 /// Default ranged hash function H. In principle it should be a 00437 /// function object composed from objects of type H1 and H2 such that 00438 /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of 00439 /// h1 and h2. So instead we'll just use a tag to tell class template 00440 /// hashtable to do that composition. 00441 struct _Default_ranged_hash { }; 00442 00443 /// Default value for rehash policy. Bucket size is (usually) the 00444 /// smallest prime that keeps the load factor small enough. 00445 struct _Prime_rehash_policy 00446 { 00447 using __has_load_factor = std::true_type; 00448 00449 _Prime_rehash_policy(float __z = 1.0) noexcept 00450 : _M_max_load_factor(__z), _M_next_resize(0) { } 00451 00452 float 00453 max_load_factor() const noexcept 00454 { return _M_max_load_factor; } 00455 00456 // Return a bucket size no smaller than n. 00457 std::size_t 00458 _M_next_bkt(std::size_t __n) const; 00459 00460 // Return a bucket count appropriate for n elements 00461 std::size_t 00462 _M_bkt_for_elements(std::size_t __n) const 00463 { return __builtin_ceil(__n / (long double)_M_max_load_factor); } 00464 00465 // __n_bkt is current bucket count, __n_elt is current element count, 00466 // and __n_ins is number of elements to be inserted. Do we need to 00467 // increase bucket count? If so, return make_pair(true, n), where n 00468 // is the new bucket count. If not, return make_pair(false, 0). 00469 std::pair<bool, std::size_t> 00470 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 00471 std::size_t __n_ins) const; 00472 00473 typedef std::size_t _State; 00474 00475 _State 00476 _M_state() const 00477 { return _M_next_resize; } 00478 00479 void 00480 _M_reset() noexcept 00481 { _M_next_resize = 0; } 00482 00483 void 00484 _M_reset(_State __state) 00485 { _M_next_resize = __state; } 00486 00487 static const std::size_t _S_growth_factor = 2; 00488 00489 float _M_max_load_factor; 00490 mutable std::size_t _M_next_resize; 00491 }; 00492 00493 /// Range hashing function assuming that second arg is a power of 2. 00494 struct _Mask_range_hashing 00495 { 00496 typedef std::size_t first_argument_type; 00497 typedef std::size_t second_argument_type; 00498 typedef std::size_t result_type; 00499 00500 result_type 00501 operator()(first_argument_type __num, 00502 second_argument_type __den) const noexcept 00503 { return __num & (__den - 1); } 00504 }; 00505 00506 /// Compute closest power of 2 not less than __n 00507 inline std::size_t 00508 __clp2(std::size_t __n) noexcept 00509 { 00510 // Equivalent to return __n ? std::ceil2(__n) : 0; 00511 if (__n < 2) 00512 return __n; 00513 const unsigned __lz = sizeof(size_t) > sizeof(long) 00514 ? __builtin_clzll(__n - 1ull) 00515 : __builtin_clzl(__n - 1ul); 00516 // Doing two shifts avoids undefined behaviour when __lz == 0. 00517 return (size_t(1) << (numeric_limits<size_t>::digits - __lz - 1)) << 1; 00518 } 00519 00520 /// Rehash policy providing power of 2 bucket numbers. Avoids modulo 00521 /// operations. 00522 struct _Power2_rehash_policy 00523 { 00524 using __has_load_factor = std::true_type; 00525 00526 _Power2_rehash_policy(float __z = 1.0) noexcept 00527 : _M_max_load_factor(__z), _M_next_resize(0) { } 00528 00529 float 00530 max_load_factor() const noexcept 00531 { return _M_max_load_factor; } 00532 00533 // Return a bucket size no smaller than n (as long as n is not above the 00534 // highest power of 2). 00535 std::size_t 00536 _M_next_bkt(std::size_t __n) noexcept 00537 { 00538 const auto __max_width = std::min<size_t>(sizeof(size_t), 8); 00539 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1); 00540 std::size_t __res = __clp2(__n); 00541 00542 if (__res == __n) 00543 __res <<= 1; 00544 00545 if (__res == 0) 00546 __res = __max_bkt; 00547 00548 if (__res == __max_bkt) 00549 // Set next resize to the max value so that we never try to rehash again 00550 // as we already reach the biggest possible bucket number. 00551 // Note that it might result in max_load_factor not being respected. 00552 _M_next_resize = std::size_t(-1); 00553 else 00554 _M_next_resize 00555 = __builtin_ceil(__res * (long double)_M_max_load_factor); 00556 00557 return __res; 00558 } 00559 00560 // Return a bucket count appropriate for n elements 00561 std::size_t 00562 _M_bkt_for_elements(std::size_t __n) const noexcept 00563 { return __builtin_ceil(__n / (long double)_M_max_load_factor); } 00564 00565 // __n_bkt is current bucket count, __n_elt is current element count, 00566 // and __n_ins is number of elements to be inserted. Do we need to 00567 // increase bucket count? If so, return make_pair(true, n), where n 00568 // is the new bucket count. If not, return make_pair(false, 0). 00569 std::pair<bool, std::size_t> 00570 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 00571 std::size_t __n_ins) noexcept 00572 { 00573 if (__n_elt + __n_ins >= _M_next_resize) 00574 { 00575 long double __min_bkts = (__n_elt + __n_ins) 00576 / (long double)_M_max_load_factor; 00577 if (__min_bkts >= __n_bkt) 00578 return std::make_pair(true, 00579 _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1, 00580 __n_bkt * _S_growth_factor))); 00581 00582 _M_next_resize 00583 = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); 00584 return std::make_pair(false, 0); 00585 } 00586 else 00587 return std::make_pair(false, 0); 00588 } 00589 00590 typedef std::size_t _State; 00591 00592 _State 00593 _M_state() const noexcept 00594 { return _M_next_resize; } 00595 00596 void 00597 _M_reset() noexcept 00598 { _M_next_resize = 0; } 00599 00600 void 00601 _M_reset(_State __state) noexcept 00602 { _M_next_resize = __state; } 00603 00604 static const std::size_t _S_growth_factor = 2; 00605 00606 float _M_max_load_factor; 00607 std::size_t _M_next_resize; 00608 }; 00609 00610 // Base classes for std::_Hashtable. We define these base classes 00611 // because in some cases we want to do different things depending on 00612 // the value of a policy class. In some cases the policy class 00613 // affects which member functions and nested typedefs are defined; 00614 // we handle that by specializing base class templates. Several of 00615 // the base class templates need to access other members of class 00616 // template _Hashtable, so we use a variant of the "Curiously 00617 // Recurring Template Pattern" (CRTP) technique. 00618 00619 /** 00620 * Primary class template _Map_base. 00621 * 00622 * If the hashtable has a value type of the form pair<T1, T2> and a 00623 * key extraction policy (_ExtractKey) that returns the first part 00624 * of the pair, the hashtable gets a mapped_type typedef. If it 00625 * satisfies those criteria and also has unique keys, then it also 00626 * gets an operator[]. 00627 */ 00628 template<typename _Key, typename _Value, typename _Alloc, 00629 typename _ExtractKey, typename _Equal, 00630 typename _H1, typename _H2, typename _Hash, 00631 typename _RehashPolicy, typename _Traits, 00632 bool _Unique_keys = _Traits::__unique_keys::value> 00633 struct _Map_base { }; 00634 00635 /// Partial specialization, __unique_keys set to false. 00636 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00637 typename _H1, typename _H2, typename _Hash, 00638 typename _RehashPolicy, typename _Traits> 00639 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00640 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 00641 { 00642 using mapped_type = typename std::tuple_element<1, _Pair>::type; 00643 }; 00644 00645 /// Partial specialization, __unique_keys set to true. 00646 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00647 typename _H1, typename _H2, typename _Hash, 00648 typename _RehashPolicy, typename _Traits> 00649 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00650 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 00651 { 00652 private: 00653 using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, 00654 _Select1st, 00655 _Equal, _H1, _H2, _Hash, 00656 _Traits>; 00657 00658 using __hashtable = _Hashtable<_Key, _Pair, _Alloc, 00659 _Select1st, _Equal, 00660 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 00661 00662 using __hash_code = typename __hashtable_base::__hash_code; 00663 using __node_type = typename __hashtable_base::__node_type; 00664 00665 public: 00666 using key_type = typename __hashtable_base::key_type; 00667 using iterator = typename __hashtable_base::iterator; 00668 using mapped_type = typename std::tuple_element<1, _Pair>::type; 00669 00670 mapped_type& 00671 operator[](const key_type& __k); 00672 00673 mapped_type& 00674 operator[](key_type&& __k); 00675 00676 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00677 // DR 761. unordered_map needs an at() member function. 00678 mapped_type& 00679 at(const key_type& __k); 00680 00681 const mapped_type& 00682 at(const key_type& __k) const; 00683 }; 00684 00685 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00686 typename _H1, typename _H2, typename _Hash, 00687 typename _RehashPolicy, typename _Traits> 00688 auto 00689 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00690 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 00691 operator[](const key_type& __k) 00692 -> mapped_type& 00693 { 00694 __hashtable* __h = static_cast<__hashtable*>(this); 00695 __hash_code __code = __h->_M_hash_code(__k); 00696 std::size_t __n = __h->_M_bucket_index(__k, __code); 00697 __node_type* __p = __h->_M_find_node(__n, __k, __code); 00698 00699 if (!__p) 00700 { 00701 __p = __h->_M_allocate_node(std::piecewise_construct, 00702 std::tuple<const key_type&>(__k), 00703 std::tuple<>()); 00704 return __h->_M_insert_unique_node(__n, __code, __p)->second; 00705 } 00706 00707 return __p->_M_v().second; 00708 } 00709 00710 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00711 typename _H1, typename _H2, typename _Hash, 00712 typename _RehashPolicy, typename _Traits> 00713 auto 00714 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00715 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 00716 operator[](key_type&& __k) 00717 -> mapped_type& 00718 { 00719 __hashtable* __h = static_cast<__hashtable*>(this); 00720 __hash_code __code = __h->_M_hash_code(__k); 00721 std::size_t __n = __h->_M_bucket_index(__k, __code); 00722 __node_type* __p = __h->_M_find_node(__n, __k, __code); 00723 00724 if (!__p) 00725 { 00726 __p = __h->_M_allocate_node(std::piecewise_construct, 00727 std::forward_as_tuple(std::move(__k)), 00728 std::tuple<>()); 00729 return __h->_M_insert_unique_node(__n, __code, __p)->second; 00730 } 00731 00732 return __p->_M_v().second; 00733 } 00734 00735 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00736 typename _H1, typename _H2, typename _Hash, 00737 typename _RehashPolicy, typename _Traits> 00738 auto 00739 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00740 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 00741 at(const key_type& __k) 00742 -> mapped_type& 00743 { 00744 __hashtable* __h = static_cast<__hashtable*>(this); 00745 __hash_code __code = __h->_M_hash_code(__k); 00746 std::size_t __n = __h->_M_bucket_index(__k, __code); 00747 __node_type* __p = __h->_M_find_node(__n, __k, __code); 00748 00749 if (!__p) 00750 __throw_out_of_range(__N("_Map_base::at")); 00751 return __p->_M_v().second; 00752 } 00753 00754 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 00755 typename _H1, typename _H2, typename _Hash, 00756 typename _RehashPolicy, typename _Traits> 00757 auto 00758 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 00759 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 00760 at(const key_type& __k) const 00761 -> const mapped_type& 00762 { 00763 const __hashtable* __h = static_cast<const __hashtable*>(this); 00764 __hash_code __code = __h->_M_hash_code(__k); 00765 std::size_t __n = __h->_M_bucket_index(__k, __code); 00766 __node_type* __p = __h->_M_find_node(__n, __k, __code); 00767 00768 if (!__p) 00769 __throw_out_of_range(__N("_Map_base::at")); 00770 return __p->_M_v().second; 00771 } 00772 00773 /** 00774 * Primary class template _Insert_base. 00775 * 00776 * Defines @c insert member functions appropriate to all _Hashtables. 00777 */ 00778 template<typename _Key, typename _Value, typename _Alloc, 00779 typename _ExtractKey, typename _Equal, 00780 typename _H1, typename _H2, typename _Hash, 00781 typename _RehashPolicy, typename _Traits> 00782 struct _Insert_base 00783 { 00784 protected: 00785 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 00786 _Equal, _H1, _H2, _Hash, 00787 _RehashPolicy, _Traits>; 00788 00789 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, 00790 _Equal, _H1, _H2, _Hash, 00791 _Traits>; 00792 00793 using value_type = typename __hashtable_base::value_type; 00794 using iterator = typename __hashtable_base::iterator; 00795 using const_iterator = typename __hashtable_base::const_iterator; 00796 using size_type = typename __hashtable_base::size_type; 00797 00798 using __unique_keys = typename __hashtable_base::__unique_keys; 00799 using __ireturn_type = typename __hashtable_base::__ireturn_type; 00800 using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>; 00801 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>; 00802 using __node_gen_type = _AllocNode<__node_alloc_type>; 00803 00804 __hashtable& 00805 _M_conjure_hashtable() 00806 { return *(static_cast<__hashtable*>(this)); } 00807 00808 template<typename _InputIterator, typename _NodeGetter> 00809 void 00810 _M_insert_range(_InputIterator __first, _InputIterator __last, 00811 const _NodeGetter&, true_type); 00812 00813 template<typename _InputIterator, typename _NodeGetter> 00814 void 00815 _M_insert_range(_InputIterator __first, _InputIterator __last, 00816 const _NodeGetter&, false_type); 00817 00818 public: 00819 __ireturn_type 00820 insert(const value_type& __v) 00821 { 00822 __hashtable& __h = _M_conjure_hashtable(); 00823 __node_gen_type __node_gen(__h); 00824 return __h._M_insert(__v, __node_gen, __unique_keys()); 00825 } 00826 00827 iterator 00828 insert(const_iterator __hint, const value_type& __v) 00829 { 00830 __hashtable& __h = _M_conjure_hashtable(); 00831 __node_gen_type __node_gen(__h); 00832 return __h._M_insert(__hint, __v, __node_gen, __unique_keys()); 00833 } 00834 00835 void 00836 insert(initializer_list<value_type> __l) 00837 { this->insert(__l.begin(), __l.end()); } 00838 00839 template<typename _InputIterator> 00840 void 00841 insert(_InputIterator __first, _InputIterator __last) 00842 { 00843 __hashtable& __h = _M_conjure_hashtable(); 00844 __node_gen_type __node_gen(__h); 00845 return _M_insert_range(__first, __last, __node_gen, __unique_keys()); 00846 } 00847 }; 00848 00849 template<typename _Key, typename _Value, typename _Alloc, 00850 typename _ExtractKey, typename _Equal, 00851 typename _H1, typename _H2, typename _Hash, 00852 typename _RehashPolicy, typename _Traits> 00853 template<typename _InputIterator, typename _NodeGetter> 00854 void 00855 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 00856 _RehashPolicy, _Traits>:: 00857 _M_insert_range(_InputIterator __first, _InputIterator __last, 00858 const _NodeGetter& __node_gen, true_type) 00859 { 00860 size_type __n_elt = __detail::__distance_fw(__first, __last); 00861 if (__n_elt == 0) 00862 return; 00863 00864 __hashtable& __h = _M_conjure_hashtable(); 00865 for (; __first != __last; ++__first) 00866 { 00867 if (__h._M_insert(*__first, __node_gen, __unique_keys(), 00868 __n_elt).second) 00869 __n_elt = 1; 00870 else if (__n_elt != 1) 00871 --__n_elt; 00872 } 00873 } 00874 00875 template<typename _Key, typename _Value, typename _Alloc, 00876 typename _ExtractKey, typename _Equal, 00877 typename _H1, typename _H2, typename _Hash, 00878 typename _RehashPolicy, typename _Traits> 00879 template<typename _InputIterator, typename _NodeGetter> 00880 void 00881 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 00882 _RehashPolicy, _Traits>:: 00883 _M_insert_range(_InputIterator __first, _InputIterator __last, 00884 const _NodeGetter& __node_gen, false_type) 00885 { 00886 using __rehash_type = typename __hashtable::__rehash_type; 00887 using __rehash_state = typename __hashtable::__rehash_state; 00888 using pair_type = std::pair<bool, std::size_t>; 00889 00890 size_type __n_elt = __detail::__distance_fw(__first, __last); 00891 if (__n_elt == 0) 00892 return; 00893 00894 __hashtable& __h = _M_conjure_hashtable(); 00895 __rehash_type& __rehash = __h._M_rehash_policy; 00896 const __rehash_state& __saved_state = __rehash._M_state(); 00897 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count, 00898 __h._M_element_count, 00899 __n_elt); 00900 00901 if (__do_rehash.first) 00902 __h._M_rehash(__do_rehash.second, __saved_state); 00903 00904 for (; __first != __last; ++__first) 00905 __h._M_insert(*__first, __node_gen, __unique_keys()); 00906 } 00907 00908 /** 00909 * Primary class template _Insert. 00910 * 00911 * Defines @c insert member functions that depend on _Hashtable policies, 00912 * via partial specializations. 00913 */ 00914 template<typename _Key, typename _Value, typename _Alloc, 00915 typename _ExtractKey, typename _Equal, 00916 typename _H1, typename _H2, typename _Hash, 00917 typename _RehashPolicy, typename _Traits, 00918 bool _Constant_iterators = _Traits::__constant_iterators::value> 00919 struct _Insert; 00920 00921 /// Specialization. 00922 template<typename _Key, typename _Value, typename _Alloc, 00923 typename _ExtractKey, typename _Equal, 00924 typename _H1, typename _H2, typename _Hash, 00925 typename _RehashPolicy, typename _Traits> 00926 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 00927 _RehashPolicy, _Traits, true> 00928 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 00929 _H1, _H2, _Hash, _RehashPolicy, _Traits> 00930 { 00931 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 00932 _Equal, _H1, _H2, _Hash, 00933 _RehashPolicy, _Traits>; 00934 00935 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, 00936 _Equal, _H1, _H2, _Hash, 00937 _Traits>; 00938 00939 using value_type = typename __base_type::value_type; 00940 using iterator = typename __base_type::iterator; 00941 using const_iterator = typename __base_type::const_iterator; 00942 00943 using __unique_keys = typename __base_type::__unique_keys; 00944 using __ireturn_type = typename __hashtable_base::__ireturn_type; 00945 using __hashtable = typename __base_type::__hashtable; 00946 using __node_gen_type = typename __base_type::__node_gen_type; 00947 00948 using __base_type::insert; 00949 00950 __ireturn_type 00951 insert(value_type&& __v) 00952 { 00953 __hashtable& __h = this->_M_conjure_hashtable(); 00954 __node_gen_type __node_gen(__h); 00955 return __h._M_insert(std::move(__v), __node_gen, __unique_keys()); 00956 } 00957 00958 iterator 00959 insert(const_iterator __hint, value_type&& __v) 00960 { 00961 __hashtable& __h = this->_M_conjure_hashtable(); 00962 __node_gen_type __node_gen(__h); 00963 return __h._M_insert(__hint, std::move(__v), __node_gen, 00964 __unique_keys()); 00965 } 00966 }; 00967 00968 /// Specialization. 00969 template<typename _Key, typename _Value, typename _Alloc, 00970 typename _ExtractKey, typename _Equal, 00971 typename _H1, typename _H2, typename _Hash, 00972 typename _RehashPolicy, typename _Traits> 00973 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 00974 _RehashPolicy, _Traits, false> 00975 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 00976 _H1, _H2, _Hash, _RehashPolicy, _Traits> 00977 { 00978 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 00979 _Equal, _H1, _H2, _Hash, 00980 _RehashPolicy, _Traits>; 00981 using value_type = typename __base_type::value_type; 00982 using iterator = typename __base_type::iterator; 00983 using const_iterator = typename __base_type::const_iterator; 00984 00985 using __unique_keys = typename __base_type::__unique_keys; 00986 using __hashtable = typename __base_type::__hashtable; 00987 using __ireturn_type = typename __base_type::__ireturn_type; 00988 00989 using __base_type::insert; 00990 00991 template<typename _Pair> 00992 using __is_cons = std::is_constructible<value_type, _Pair&&>; 00993 00994 template<typename _Pair> 00995 using _IFcons = std::enable_if<__is_cons<_Pair>::value>; 00996 00997 template<typename _Pair> 00998 using _IFconsp = typename _IFcons<_Pair>::type; 00999 01000 template<typename _Pair, typename = _IFconsp<_Pair>> 01001 __ireturn_type 01002 insert(_Pair&& __v) 01003 { 01004 __hashtable& __h = this->_M_conjure_hashtable(); 01005 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v)); 01006 } 01007 01008 template<typename _Pair, typename = _IFconsp<_Pair>> 01009 iterator 01010 insert(const_iterator __hint, _Pair&& __v) 01011 { 01012 __hashtable& __h = this->_M_conjure_hashtable(); 01013 return __h._M_emplace(__hint, __unique_keys(), 01014 std::forward<_Pair>(__v)); 01015 } 01016 }; 01017 01018 template<typename _Policy> 01019 using __has_load_factor = typename _Policy::__has_load_factor; 01020 01021 /** 01022 * Primary class template _Rehash_base. 01023 * 01024 * Give hashtable the max_load_factor functions and reserve iff the 01025 * rehash policy supports it. 01026 */ 01027 template<typename _Key, typename _Value, typename _Alloc, 01028 typename _ExtractKey, typename _Equal, 01029 typename _H1, typename _H2, typename _Hash, 01030 typename _RehashPolicy, typename _Traits, 01031 typename = 01032 __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>> 01033 struct _Rehash_base; 01034 01035 /// Specialization when rehash policy doesn't provide load factor management. 01036 template<typename _Key, typename _Value, typename _Alloc, 01037 typename _ExtractKey, typename _Equal, 01038 typename _H1, typename _H2, typename _Hash, 01039 typename _RehashPolicy, typename _Traits> 01040 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01041 _H1, _H2, _Hash, _RehashPolicy, _Traits, 01042 std::false_type> 01043 { 01044 }; 01045 01046 /// Specialization when rehash policy provide load factor management. 01047 template<typename _Key, typename _Value, typename _Alloc, 01048 typename _ExtractKey, typename _Equal, 01049 typename _H1, typename _H2, typename _Hash, 01050 typename _RehashPolicy, typename _Traits> 01051 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01052 _H1, _H2, _Hash, _RehashPolicy, _Traits, 01053 std::true_type> 01054 { 01055 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 01056 _Equal, _H1, _H2, _Hash, 01057 _RehashPolicy, _Traits>; 01058 01059 float 01060 max_load_factor() const noexcept 01061 { 01062 const __hashtable* __this = static_cast<const __hashtable*>(this); 01063 return __this->__rehash_policy().max_load_factor(); 01064 } 01065 01066 void 01067 max_load_factor(float __z) 01068 { 01069 __hashtable* __this = static_cast<__hashtable*>(this); 01070 __this->__rehash_policy(_RehashPolicy(__z)); 01071 } 01072 01073 void 01074 reserve(std::size_t __n) 01075 { 01076 __hashtable* __this = static_cast<__hashtable*>(this); 01077 __this->rehash(__builtin_ceil(__n / max_load_factor())); 01078 } 01079 }; 01080 01081 /** 01082 * Primary class template _Hashtable_ebo_helper. 01083 * 01084 * Helper class using EBO when it is not forbidden (the type is not 01085 * final) and when it is worth it (the type is empty.) 01086 */ 01087 template<int _Nm, typename _Tp, 01088 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> 01089 struct _Hashtable_ebo_helper; 01090 01091 /// Specialization using EBO. 01092 template<int _Nm, typename _Tp> 01093 struct _Hashtable_ebo_helper<_Nm, _Tp, true> 01094 : private _Tp 01095 { 01096 _Hashtable_ebo_helper() = default; 01097 01098 template<typename _OtherTp> 01099 _Hashtable_ebo_helper(_OtherTp&& __tp) 01100 : _Tp(std::forward<_OtherTp>(__tp)) 01101 { } 01102 01103 static const _Tp& 01104 _S_cget(const _Hashtable_ebo_helper& __eboh) 01105 { return static_cast<const _Tp&>(__eboh); } 01106 01107 static _Tp& 01108 _S_get(_Hashtable_ebo_helper& __eboh) 01109 { return static_cast<_Tp&>(__eboh); } 01110 }; 01111 01112 /// Specialization not using EBO. 01113 template<int _Nm, typename _Tp> 01114 struct _Hashtable_ebo_helper<_Nm, _Tp, false> 01115 { 01116 _Hashtable_ebo_helper() = default; 01117 01118 template<typename _OtherTp> 01119 _Hashtable_ebo_helper(_OtherTp&& __tp) 01120 : _M_tp(std::forward<_OtherTp>(__tp)) 01121 { } 01122 01123 static const _Tp& 01124 _S_cget(const _Hashtable_ebo_helper& __eboh) 01125 { return __eboh._M_tp; } 01126 01127 static _Tp& 01128 _S_get(_Hashtable_ebo_helper& __eboh) 01129 { return __eboh._M_tp; } 01130 01131 private: 01132 _Tp _M_tp; 01133 }; 01134 01135 /** 01136 * Primary class template _Local_iterator_base. 01137 * 01138 * Base class for local iterators, used to iterate within a bucket 01139 * but not between buckets. 01140 */ 01141 template<typename _Key, typename _Value, typename _ExtractKey, 01142 typename _H1, typename _H2, typename _Hash, 01143 bool __cache_hash_code> 01144 struct _Local_iterator_base; 01145 01146 /** 01147 * Primary class template _Hash_code_base. 01148 * 01149 * Encapsulates two policy issues that aren't quite orthogonal. 01150 * (1) the difference between using a ranged hash function and using 01151 * the combination of a hash function and a range-hashing function. 01152 * In the former case we don't have such things as hash codes, so 01153 * we have a dummy type as placeholder. 01154 * (2) Whether or not we cache hash codes. Caching hash codes is 01155 * meaningless if we have a ranged hash function. 01156 * 01157 * We also put the key extraction objects here, for convenience. 01158 * Each specialization derives from one or more of the template 01159 * parameters to benefit from Ebo. This is important as this type 01160 * is inherited in some cases by the _Local_iterator_base type used 01161 * to implement local_iterator and const_local_iterator. As with 01162 * any iterator type we prefer to make it as small as possible. 01163 * 01164 * Primary template is unused except as a hook for specializations. 01165 */ 01166 template<typename _Key, typename _Value, typename _ExtractKey, 01167 typename _H1, typename _H2, typename _Hash, 01168 bool __cache_hash_code> 01169 struct _Hash_code_base; 01170 01171 /// Specialization: ranged hash function, no caching hash codes. H1 01172 /// and H2 are provided but ignored. We define a dummy hash code type. 01173 template<typename _Key, typename _Value, typename _ExtractKey, 01174 typename _H1, typename _H2, typename _Hash> 01175 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> 01176 : private _Hashtable_ebo_helper<0, _ExtractKey>, 01177 private _Hashtable_ebo_helper<1, _Hash> 01178 { 01179 private: 01180 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 01181 using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>; 01182 01183 protected: 01184 typedef void* __hash_code; 01185 typedef _Hash_node<_Value, false> __node_type; 01186 01187 // We need the default constructor for the local iterators and _Hashtable 01188 // default constructor. 01189 _Hash_code_base() = default; 01190 01191 _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&, 01192 const _Hash& __h) 01193 : __ebo_extract_key(__ex), __ebo_hash(__h) { } 01194 01195 __hash_code 01196 _M_hash_code(const _Key& __key) const 01197 { return 0; } 01198 01199 std::size_t 01200 _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const 01201 { return _M_ranged_hash()(__k, __n); } 01202 01203 std::size_t 01204 _M_bucket_index(const __node_type* __p, std::size_t __n) const 01205 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(), 01206 (std::size_t)0)) ) 01207 { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); } 01208 01209 void 01210 _M_store_code(__node_type*, __hash_code) const 01211 { } 01212 01213 void 01214 _M_copy_code(__node_type*, const __node_type*) const 01215 { } 01216 01217 void 01218 _M_swap(_Hash_code_base& __x) 01219 { 01220 std::swap(_M_extract(), __x._M_extract()); 01221 std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 01222 } 01223 01224 const _ExtractKey& 01225 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 01226 01227 _ExtractKey& 01228 _M_extract() { return __ebo_extract_key::_S_get(*this); } 01229 01230 const _Hash& 01231 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); } 01232 01233 _Hash& 01234 _M_ranged_hash() { return __ebo_hash::_S_get(*this); } 01235 }; 01236 01237 // No specialization for ranged hash function while caching hash codes. 01238 // That combination is meaningless, and trying to do it is an error. 01239 01240 /// Specialization: ranged hash function, cache hash codes. This 01241 /// combination is meaningless, so we provide only a declaration 01242 /// and no definition. 01243 template<typename _Key, typename _Value, typename _ExtractKey, 01244 typename _H1, typename _H2, typename _Hash> 01245 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; 01246 01247 /// Specialization: hash function and range-hashing function, no 01248 /// caching of hash codes. 01249 /// Provides typedef and accessor required by C++ 11. 01250 template<typename _Key, typename _Value, typename _ExtractKey, 01251 typename _H1, typename _H2> 01252 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 01253 _Default_ranged_hash, false> 01254 : private _Hashtable_ebo_helper<0, _ExtractKey>, 01255 private _Hashtable_ebo_helper<1, _H1>, 01256 private _Hashtable_ebo_helper<2, _H2> 01257 { 01258 private: 01259 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 01260 using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; 01261 using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; 01262 01263 // Gives the local iterator implementation access to _M_bucket_index(). 01264 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, 01265 _Default_ranged_hash, false>; 01266 01267 public: 01268 typedef _H1 hasher; 01269 01270 hasher 01271 hash_function() const 01272 { return _M_h1(); } 01273 01274 protected: 01275 typedef std::size_t __hash_code; 01276 typedef _Hash_node<_Value, false> __node_type; 01277 01278 // We need the default constructor for the local iterators and _Hashtable 01279 // default constructor. 01280 _Hash_code_base() = default; 01281 01282 _Hash_code_base(const _ExtractKey& __ex, 01283 const _H1& __h1, const _H2& __h2, 01284 const _Default_ranged_hash&) 01285 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 01286 01287 __hash_code 01288 _M_hash_code(const _Key& __k) const 01289 { 01290 static_assert(__is_invocable<const _H1&, const _Key&>{}, 01291 "hash function must be invocable with an argument of key type"); 01292 return _M_h1()(__k); 01293 } 01294 01295 std::size_t 01296 _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const 01297 { return _M_h2()(__c, __n); } 01298 01299 std::size_t 01300 _M_bucket_index(const __node_type* __p, std::size_t __n) const 01301 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>())) 01302 && noexcept(declval<const _H2&>()((__hash_code)0, 01303 (std::size_t)0)) ) 01304 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); } 01305 01306 void 01307 _M_store_code(__node_type*, __hash_code) const 01308 { } 01309 01310 void 01311 _M_copy_code(__node_type*, const __node_type*) const 01312 { } 01313 01314 void 01315 _M_swap(_Hash_code_base& __x) 01316 { 01317 std::swap(_M_extract(), __x._M_extract()); 01318 std::swap(_M_h1(), __x._M_h1()); 01319 std::swap(_M_h2(), __x._M_h2()); 01320 } 01321 01322 const _ExtractKey& 01323 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 01324 01325 _ExtractKey& 01326 _M_extract() { return __ebo_extract_key::_S_get(*this); } 01327 01328 const _H1& 01329 _M_h1() const { return __ebo_h1::_S_cget(*this); } 01330 01331 _H1& 01332 _M_h1() { return __ebo_h1::_S_get(*this); } 01333 01334 const _H2& 01335 _M_h2() const { return __ebo_h2::_S_cget(*this); } 01336 01337 _H2& 01338 _M_h2() { return __ebo_h2::_S_get(*this); } 01339 }; 01340 01341 /// Specialization: hash function and range-hashing function, 01342 /// caching hash codes. H is provided but ignored. Provides 01343 /// typedef and accessor required by C++ 11. 01344 template<typename _Key, typename _Value, typename _ExtractKey, 01345 typename _H1, typename _H2> 01346 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 01347 _Default_ranged_hash, true> 01348 : private _Hashtable_ebo_helper<0, _ExtractKey>, 01349 private _Hashtable_ebo_helper<1, _H1>, 01350 private _Hashtable_ebo_helper<2, _H2> 01351 { 01352 private: 01353 // Gives the local iterator implementation access to _M_h2(). 01354 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, 01355 _Default_ranged_hash, true>; 01356 01357 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 01358 using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; 01359 using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; 01360 01361 public: 01362 typedef _H1 hasher; 01363 01364 hasher 01365 hash_function() const 01366 { return _M_h1(); } 01367 01368 protected: 01369 typedef std::size_t __hash_code; 01370 typedef _Hash_node<_Value, true> __node_type; 01371 01372 // We need the default constructor for _Hashtable default constructor. 01373 _Hash_code_base() = default; 01374 _Hash_code_base(const _ExtractKey& __ex, 01375 const _H1& __h1, const _H2& __h2, 01376 const _Default_ranged_hash&) 01377 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 01378 01379 __hash_code 01380 _M_hash_code(const _Key& __k) const 01381 { 01382 static_assert(__is_invocable<const _H1&, const _Key&>{}, 01383 "hash function must be invocable with an argument of key type"); 01384 return _M_h1()(__k); 01385 } 01386 01387 std::size_t 01388 _M_bucket_index(const _Key&, __hash_code __c, 01389 std::size_t __n) const 01390 { return _M_h2()(__c, __n); } 01391 01392 std::size_t 01393 _M_bucket_index(const __node_type* __p, std::size_t __n) const 01394 noexcept( noexcept(declval<const _H2&>()((__hash_code)0, 01395 (std::size_t)0)) ) 01396 { return _M_h2()(__p->_M_hash_code, __n); } 01397 01398 void 01399 _M_store_code(__node_type* __n, __hash_code __c) const 01400 { __n->_M_hash_code = __c; } 01401 01402 void 01403 _M_copy_code(__node_type* __to, const __node_type* __from) const 01404 { __to->_M_hash_code = __from->_M_hash_code; } 01405 01406 void 01407 _M_swap(_Hash_code_base& __x) 01408 { 01409 std::swap(_M_extract(), __x._M_extract()); 01410 std::swap(_M_h1(), __x._M_h1()); 01411 std::swap(_M_h2(), __x._M_h2()); 01412 } 01413 01414 const _ExtractKey& 01415 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 01416 01417 _ExtractKey& 01418 _M_extract() { return __ebo_extract_key::_S_get(*this); } 01419 01420 const _H1& 01421 _M_h1() const { return __ebo_h1::_S_cget(*this); } 01422 01423 _H1& 01424 _M_h1() { return __ebo_h1::_S_get(*this); } 01425 01426 const _H2& 01427 _M_h2() const { return __ebo_h2::_S_cget(*this); } 01428 01429 _H2& 01430 _M_h2() { return __ebo_h2::_S_get(*this); } 01431 }; 01432 01433 /** 01434 * Primary class template _Equal_helper. 01435 * 01436 */ 01437 template <typename _Key, typename _Value, typename _ExtractKey, 01438 typename _Equal, typename _HashCodeType, 01439 bool __cache_hash_code> 01440 struct _Equal_helper; 01441 01442 /// Specialization. 01443 template<typename _Key, typename _Value, typename _ExtractKey, 01444 typename _Equal, typename _HashCodeType> 01445 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> 01446 { 01447 static bool 01448 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 01449 const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n) 01450 { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); } 01451 }; 01452 01453 /// Specialization. 01454 template<typename _Key, typename _Value, typename _ExtractKey, 01455 typename _Equal, typename _HashCodeType> 01456 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> 01457 { 01458 static bool 01459 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 01460 const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n) 01461 { return __eq(__k, __extract(__n->_M_v())); } 01462 }; 01463 01464 01465 /// Partial specialization used when nodes contain a cached hash code. 01466 template<typename _Key, typename _Value, typename _ExtractKey, 01467 typename _H1, typename _H2, typename _Hash> 01468 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 01469 _H1, _H2, _Hash, true> 01470 : private _Hashtable_ebo_helper<0, _H2> 01471 { 01472 protected: 01473 using __base_type = _Hashtable_ebo_helper<0, _H2>; 01474 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 01475 _H1, _H2, _Hash, true>; 01476 01477 _Local_iterator_base() = default; 01478 _Local_iterator_base(const __hash_code_base& __base, 01479 _Hash_node<_Value, true>* __p, 01480 std::size_t __bkt, std::size_t __bkt_count) 01481 : __base_type(__base._M_h2()), 01482 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 01483 01484 void 01485 _M_incr() 01486 { 01487 _M_cur = _M_cur->_M_next(); 01488 if (_M_cur) 01489 { 01490 std::size_t __bkt 01491 = __base_type::_S_get(*this)(_M_cur->_M_hash_code, 01492 _M_bucket_count); 01493 if (__bkt != _M_bucket) 01494 _M_cur = nullptr; 01495 } 01496 } 01497 01498 _Hash_node<_Value, true>* _M_cur; 01499 std::size_t _M_bucket; 01500 std::size_t _M_bucket_count; 01501 01502 public: 01503 const void* 01504 _M_curr() const { return _M_cur; } // for equality ops 01505 01506 std::size_t 01507 _M_get_bucket() const { return _M_bucket; } // for debug mode 01508 }; 01509 01510 // Uninitialized storage for a _Hash_code_base. 01511 // This type is DefaultConstructible and Assignable even if the 01512 // _Hash_code_base type isn't, so that _Local_iterator_base<..., false> 01513 // can be DefaultConstructible and Assignable. 01514 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value> 01515 struct _Hash_code_storage 01516 { 01517 __gnu_cxx::__aligned_buffer<_Tp> _M_storage; 01518 01519 _Tp* 01520 _M_h() { return _M_storage._M_ptr(); } 01521 01522 const _Tp* 01523 _M_h() const { return _M_storage._M_ptr(); } 01524 }; 01525 01526 // Empty partial specialization for empty _Hash_code_base types. 01527 template<typename _Tp> 01528 struct _Hash_code_storage<_Tp, true> 01529 { 01530 static_assert( std::is_empty<_Tp>::value, "Type must be empty" ); 01531 01532 // As _Tp is an empty type there will be no bytes written/read through 01533 // the cast pointer, so no strict-aliasing violation. 01534 _Tp* 01535 _M_h() { return reinterpret_cast<_Tp*>(this); } 01536 01537 const _Tp* 01538 _M_h() const { return reinterpret_cast<const _Tp*>(this); } 01539 }; 01540 01541 template<typename _Key, typename _Value, typename _ExtractKey, 01542 typename _H1, typename _H2, typename _Hash> 01543 using __hash_code_for_local_iter 01544 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey, 01545 _H1, _H2, _Hash, false>>; 01546 01547 // Partial specialization used when hash codes are not cached 01548 template<typename _Key, typename _Value, typename _ExtractKey, 01549 typename _H1, typename _H2, typename _Hash> 01550 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 01551 _H1, _H2, _Hash, false> 01552 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash> 01553 { 01554 protected: 01555 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 01556 _H1, _H2, _Hash, false>; 01557 01558 _Local_iterator_base() : _M_bucket_count(-1) { } 01559 01560 _Local_iterator_base(const __hash_code_base& __base, 01561 _Hash_node<_Value, false>* __p, 01562 std::size_t __bkt, std::size_t __bkt_count) 01563 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) 01564 { _M_init(__base); } 01565 01566 ~_Local_iterator_base() 01567 { 01568 if (_M_bucket_count != -1) 01569 _M_destroy(); 01570 } 01571 01572 _Local_iterator_base(const _Local_iterator_base& __iter) 01573 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket), 01574 _M_bucket_count(__iter._M_bucket_count) 01575 { 01576 if (_M_bucket_count != -1) 01577 _M_init(*__iter._M_h()); 01578 } 01579 01580 _Local_iterator_base& 01581 operator=(const _Local_iterator_base& __iter) 01582 { 01583 if (_M_bucket_count != -1) 01584 _M_destroy(); 01585 _M_cur = __iter._M_cur; 01586 _M_bucket = __iter._M_bucket; 01587 _M_bucket_count = __iter._M_bucket_count; 01588 if (_M_bucket_count != -1) 01589 _M_init(*__iter._M_h()); 01590 return *this; 01591 } 01592 01593 void 01594 _M_incr() 01595 { 01596 _M_cur = _M_cur->_M_next(); 01597 if (_M_cur) 01598 { 01599 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur, 01600 _M_bucket_count); 01601 if (__bkt != _M_bucket) 01602 _M_cur = nullptr; 01603 } 01604 } 01605 01606 _Hash_node<_Value, false>* _M_cur; 01607 std::size_t _M_bucket; 01608 std::size_t _M_bucket_count; 01609 01610 void 01611 _M_init(const __hash_code_base& __base) 01612 { ::new(this->_M_h()) __hash_code_base(__base); } 01613 01614 void 01615 _M_destroy() { this->_M_h()->~__hash_code_base(); } 01616 01617 public: 01618 const void* 01619 _M_curr() const { return _M_cur; } // for equality ops and debug mode 01620 01621 std::size_t 01622 _M_get_bucket() const { return _M_bucket; } // for debug mode 01623 }; 01624 01625 template<typename _Key, typename _Value, typename _ExtractKey, 01626 typename _H1, typename _H2, typename _Hash, bool __cache> 01627 inline bool 01628 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, 01629 _H1, _H2, _Hash, __cache>& __x, 01630 const _Local_iterator_base<_Key, _Value, _ExtractKey, 01631 _H1, _H2, _Hash, __cache>& __y) 01632 { return __x._M_curr() == __y._M_curr(); } 01633 01634 template<typename _Key, typename _Value, typename _ExtractKey, 01635 typename _H1, typename _H2, typename _Hash, bool __cache> 01636 inline bool 01637 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, 01638 _H1, _H2, _Hash, __cache>& __x, 01639 const _Local_iterator_base<_Key, _Value, _ExtractKey, 01640 _H1, _H2, _Hash, __cache>& __y) 01641 { return __x._M_curr() != __y._M_curr(); } 01642 01643 /// local iterators 01644 template<typename _Key, typename _Value, typename _ExtractKey, 01645 typename _H1, typename _H2, typename _Hash, 01646 bool __constant_iterators, bool __cache> 01647 struct _Local_iterator 01648 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 01649 _H1, _H2, _Hash, __cache> 01650 { 01651 private: 01652 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, 01653 _H1, _H2, _Hash, __cache>; 01654 using __hash_code_base = typename __base_type::__hash_code_base; 01655 public: 01656 typedef _Value value_type; 01657 typedef typename std::conditional<__constant_iterators, 01658 const _Value*, _Value*>::type 01659 pointer; 01660 typedef typename std::conditional<__constant_iterators, 01661 const _Value&, _Value&>::type 01662 reference; 01663 typedef std::ptrdiff_t difference_type; 01664 typedef std::forward_iterator_tag iterator_category; 01665 01666 _Local_iterator() = default; 01667 01668 _Local_iterator(const __hash_code_base& __base, 01669 _Hash_node<_Value, __cache>* __p, 01670 std::size_t __bkt, std::size_t __bkt_count) 01671 : __base_type(__base, __p, __bkt, __bkt_count) 01672 { } 01673 01674 reference 01675 operator*() const 01676 { return this->_M_cur->_M_v(); } 01677 01678 pointer 01679 operator->() const 01680 { return this->_M_cur->_M_valptr(); } 01681 01682 _Local_iterator& 01683 operator++() 01684 { 01685 this->_M_incr(); 01686 return *this; 01687 } 01688 01689 _Local_iterator 01690 operator++(int) 01691 { 01692 _Local_iterator __tmp(*this); 01693 this->_M_incr(); 01694 return __tmp; 01695 } 01696 }; 01697 01698 /// local const_iterators 01699 template<typename _Key, typename _Value, typename _ExtractKey, 01700 typename _H1, typename _H2, typename _Hash, 01701 bool __constant_iterators, bool __cache> 01702 struct _Local_const_iterator 01703 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 01704 _H1, _H2, _Hash, __cache> 01705 { 01706 private: 01707 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, 01708 _H1, _H2, _Hash, __cache>; 01709 using __hash_code_base = typename __base_type::__hash_code_base; 01710 01711 public: 01712 typedef _Value value_type; 01713 typedef const _Value* pointer; 01714 typedef const _Value& reference; 01715 typedef std::ptrdiff_t difference_type; 01716 typedef std::forward_iterator_tag iterator_category; 01717 01718 _Local_const_iterator() = default; 01719 01720 _Local_const_iterator(const __hash_code_base& __base, 01721 _Hash_node<_Value, __cache>* __p, 01722 std::size_t __bkt, std::size_t __bkt_count) 01723 : __base_type(__base, __p, __bkt, __bkt_count) 01724 { } 01725 01726 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 01727 _H1, _H2, _Hash, 01728 __constant_iterators, 01729 __cache>& __x) 01730 : __base_type(__x) 01731 { } 01732 01733 reference 01734 operator*() const 01735 { return this->_M_cur->_M_v(); } 01736 01737 pointer 01738 operator->() const 01739 { return this->_M_cur->_M_valptr(); } 01740 01741 _Local_const_iterator& 01742 operator++() 01743 { 01744 this->_M_incr(); 01745 return *this; 01746 } 01747 01748 _Local_const_iterator 01749 operator++(int) 01750 { 01751 _Local_const_iterator __tmp(*this); 01752 this->_M_incr(); 01753 return __tmp; 01754 } 01755 }; 01756 01757 /** 01758 * Primary class template _Hashtable_base. 01759 * 01760 * Helper class adding management of _Equal functor to 01761 * _Hash_code_base type. 01762 * 01763 * Base class templates are: 01764 * - __detail::_Hash_code_base 01765 * - __detail::_Hashtable_ebo_helper 01766 */ 01767 template<typename _Key, typename _Value, 01768 typename _ExtractKey, typename _Equal, 01769 typename _H1, typename _H2, typename _Hash, typename _Traits> 01770 struct _Hashtable_base 01771 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 01772 _Traits::__hash_cached::value>, 01773 private _Hashtable_ebo_helper<0, _Equal> 01774 { 01775 public: 01776 typedef _Key key_type; 01777 typedef _Value value_type; 01778 typedef _Equal key_equal; 01779 typedef std::size_t size_type; 01780 typedef std::ptrdiff_t difference_type; 01781 01782 using __traits_type = _Traits; 01783 using __hash_cached = typename __traits_type::__hash_cached; 01784 using __constant_iterators = typename __traits_type::__constant_iterators; 01785 using __unique_keys = typename __traits_type::__unique_keys; 01786 01787 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 01788 _H1, _H2, _Hash, 01789 __hash_cached::value>; 01790 01791 using __hash_code = typename __hash_code_base::__hash_code; 01792 using __node_type = typename __hash_code_base::__node_type; 01793 01794 using iterator = __detail::_Node_iterator<value_type, 01795 __constant_iterators::value, 01796 __hash_cached::value>; 01797 01798 using const_iterator = __detail::_Node_const_iterator<value_type, 01799 __constant_iterators::value, 01800 __hash_cached::value>; 01801 01802 using local_iterator = __detail::_Local_iterator<key_type, value_type, 01803 _ExtractKey, _H1, _H2, _Hash, 01804 __constant_iterators::value, 01805 __hash_cached::value>; 01806 01807 using const_local_iterator = __detail::_Local_const_iterator<key_type, 01808 value_type, 01809 _ExtractKey, _H1, _H2, _Hash, 01810 __constant_iterators::value, 01811 __hash_cached::value>; 01812 01813 using __ireturn_type = typename std::conditional<__unique_keys::value, 01814 std::pair<iterator, bool>, 01815 iterator>::type; 01816 private: 01817 using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; 01818 using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, 01819 __hash_code, __hash_cached::value>; 01820 01821 protected: 01822 _Hashtable_base() = default; 01823 _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, 01824 const _Hash& __hash, const _Equal& __eq) 01825 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) 01826 { } 01827 01828 bool 01829 _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const 01830 { 01831 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{}, 01832 "key equality predicate must be invocable with two arguments of " 01833 "key type"); 01834 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 01835 __k, __c, __n); 01836 } 01837 01838 void 01839 _M_swap(_Hashtable_base& __x) 01840 { 01841 __hash_code_base::_M_swap(__x); 01842 std::swap(_M_eq(), __x._M_eq()); 01843 } 01844 01845 const _Equal& 01846 _M_eq() const { return _EqualEBO::_S_cget(*this); } 01847 01848 _Equal& 01849 _M_eq() { return _EqualEBO::_S_get(*this); } 01850 }; 01851 01852 /** 01853 * struct _Equality_base. 01854 * 01855 * Common types and functions for class _Equality. 01856 */ 01857 struct _Equality_base 01858 { 01859 protected: 01860 template<typename _Uiterator> 01861 static bool 01862 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 01863 }; 01864 01865 // See std::is_permutation in N3068. 01866 template<typename _Uiterator> 01867 bool 01868 _Equality_base:: 01869 _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 01870 _Uiterator __first2) 01871 { 01872 for (; __first1 != __last1; ++__first1, ++__first2) 01873 if (!(*__first1 == *__first2)) 01874 break; 01875 01876 if (__first1 == __last1) 01877 return true; 01878 01879 _Uiterator __last2 = __first2; 01880 std::advance(__last2, std::distance(__first1, __last1)); 01881 01882 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 01883 { 01884 _Uiterator __tmp = __first1; 01885 while (__tmp != __it1 && !bool(*__tmp == *__it1)) 01886 ++__tmp; 01887 01888 // We've seen this one before. 01889 if (__tmp != __it1) 01890 continue; 01891 01892 std::ptrdiff_t __n2 = 0; 01893 for (__tmp = __first2; __tmp != __last2; ++__tmp) 01894 if (*__tmp == *__it1) 01895 ++__n2; 01896 01897 if (!__n2) 01898 return false; 01899 01900 std::ptrdiff_t __n1 = 0; 01901 for (__tmp = __it1; __tmp != __last1; ++__tmp) 01902 if (*__tmp == *__it1) 01903 ++__n1; 01904 01905 if (__n1 != __n2) 01906 return false; 01907 } 01908 return true; 01909 } 01910 01911 /** 01912 * Primary class template _Equality. 01913 * 01914 * This is for implementing equality comparison for unordered 01915 * containers, per N3068, by John Lakos and Pablo Halpern. 01916 * Algorithmically, we follow closely the reference implementations 01917 * therein. 01918 */ 01919 template<typename _Key, typename _Value, typename _Alloc, 01920 typename _ExtractKey, typename _Equal, 01921 typename _H1, typename _H2, typename _Hash, 01922 typename _RehashPolicy, typename _Traits, 01923 bool _Unique_keys = _Traits::__unique_keys::value> 01924 struct _Equality; 01925 01926 /// Specialization. 01927 template<typename _Key, typename _Value, typename _Alloc, 01928 typename _ExtractKey, typename _Equal, 01929 typename _H1, typename _H2, typename _Hash, 01930 typename _RehashPolicy, typename _Traits> 01931 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01932 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 01933 { 01934 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01935 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 01936 01937 bool 01938 _M_equal(const __hashtable&) const; 01939 }; 01940 01941 template<typename _Key, typename _Value, typename _Alloc, 01942 typename _ExtractKey, typename _Equal, 01943 typename _H1, typename _H2, typename _Hash, 01944 typename _RehashPolicy, typename _Traits> 01945 bool 01946 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01947 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 01948 _M_equal(const __hashtable& __other) const 01949 { 01950 const __hashtable* __this = static_cast<const __hashtable*>(this); 01951 01952 if (__this->size() != __other.size()) 01953 return false; 01954 01955 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 01956 { 01957 const auto __ity = __other.find(_ExtractKey()(*__itx)); 01958 if (__ity == __other.end() || !bool(*__ity == *__itx)) 01959 return false; 01960 } 01961 return true; 01962 } 01963 01964 /// Specialization. 01965 template<typename _Key, typename _Value, typename _Alloc, 01966 typename _ExtractKey, typename _Equal, 01967 typename _H1, typename _H2, typename _Hash, 01968 typename _RehashPolicy, typename _Traits> 01969 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01970 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 01971 : public _Equality_base 01972 { 01973 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01974 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 01975 01976 bool 01977 _M_equal(const __hashtable&) const; 01978 }; 01979 01980 template<typename _Key, typename _Value, typename _Alloc, 01981 typename _ExtractKey, typename _Equal, 01982 typename _H1, typename _H2, typename _Hash, 01983 typename _RehashPolicy, typename _Traits> 01984 bool 01985 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01986 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: 01987 _M_equal(const __hashtable& __other) const 01988 { 01989 const __hashtable* __this = static_cast<const __hashtable*>(this); 01990 01991 if (__this->size() != __other.size()) 01992 return false; 01993 01994 for (auto __itx = __this->begin(); __itx != __this->end();) 01995 { 01996 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 01997 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 01998 01999 if (std::distance(__xrange.first, __xrange.second) 02000 != std::distance(__yrange.first, __yrange.second)) 02001 return false; 02002 02003 if (!_S_is_permutation(__xrange.first, __xrange.second, 02004 __yrange.first)) 02005 return false; 02006 02007 __itx = __xrange.second; 02008 } 02009 return true; 02010 } 02011 02012 /** 02013 * This type deals with all allocation and keeps an allocator instance through 02014 * inheritance to benefit from EBO when possible. 02015 */ 02016 template<typename _NodeAlloc> 02017 struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc> 02018 { 02019 private: 02020 using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>; 02021 public: 02022 using __node_type = typename _NodeAlloc::value_type; 02023 using __node_alloc_type = _NodeAlloc; 02024 // Use __gnu_cxx to benefit from _S_always_equal and al. 02025 using __node_alloc_traits = __gnu_cxx::__alloc_traits<__node_alloc_type>; 02026 02027 using __value_alloc_traits = typename __node_alloc_traits::template 02028 rebind_traits<typename __node_type::value_type>; 02029 02030 using __node_base = __detail::_Hash_node_base; 02031 using __bucket_type = __node_base*; 02032 using __bucket_alloc_type = 02033 __alloc_rebind<__node_alloc_type, __bucket_type>; 02034 using __bucket_alloc_traits = std::allocator_traits<__bucket_alloc_type>; 02035 02036 _Hashtable_alloc() = default; 02037 _Hashtable_alloc(const _Hashtable_alloc&) = default; 02038 _Hashtable_alloc(_Hashtable_alloc&&) = default; 02039 02040 template<typename _Alloc> 02041 _Hashtable_alloc(_Alloc&& __a) 02042 : __ebo_node_alloc(std::forward<_Alloc>(__a)) 02043 { } 02044 02045 __node_alloc_type& 02046 _M_node_allocator() 02047 { return __ebo_node_alloc::_S_get(*this); } 02048 02049 const __node_alloc_type& 02050 _M_node_allocator() const 02051 { return __ebo_node_alloc::_S_cget(*this); } 02052 02053 template<typename... _Args> 02054 __node_type* 02055 _M_allocate_node(_Args&&... __args); 02056 02057 void 02058 _M_deallocate_node(__node_type* __n); 02059 02060 void 02061 _M_deallocate_node_ptr(__node_type* __n); 02062 02063 // Deallocate the linked list of nodes pointed to by __n 02064 void 02065 _M_deallocate_nodes(__node_type* __n); 02066 02067 __bucket_type* 02068 _M_allocate_buckets(std::size_t __n); 02069 02070 void 02071 _M_deallocate_buckets(__bucket_type*, std::size_t __n); 02072 }; 02073 02074 // Definitions of class template _Hashtable_alloc's out-of-line member 02075 // functions. 02076 template<typename _NodeAlloc> 02077 template<typename... _Args> 02078 typename _Hashtable_alloc<_NodeAlloc>::__node_type* 02079 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) 02080 { 02081 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); 02082 __node_type* __n = std::__to_address(__nptr); 02083 __try 02084 { 02085 ::new ((void*)__n) __node_type; 02086 __node_alloc_traits::construct(_M_node_allocator(), 02087 __n->_M_valptr(), 02088 std::forward<_Args>(__args)...); 02089 return __n; 02090 } 02091 __catch(...) 02092 { 02093 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1); 02094 __throw_exception_again; 02095 } 02096 } 02097 02098 template<typename _NodeAlloc> 02099 void 02100 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n) 02101 { 02102 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr()); 02103 _M_deallocate_node_ptr(__n); 02104 } 02105 02106 template<typename _NodeAlloc> 02107 void 02108 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n) 02109 { 02110 typedef typename __node_alloc_traits::pointer _Ptr; 02111 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n); 02112 __n->~__node_type(); 02113 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1); 02114 } 02115 02116 template<typename _NodeAlloc> 02117 void 02118 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n) 02119 { 02120 while (__n) 02121 { 02122 __node_type* __tmp = __n; 02123 __n = __n->_M_next(); 02124 _M_deallocate_node(__tmp); 02125 } 02126 } 02127 02128 template<typename _NodeAlloc> 02129 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type* 02130 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n) 02131 { 02132 __bucket_alloc_type __alloc(_M_node_allocator()); 02133 02134 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n); 02135 __bucket_type* __p = std::__to_address(__ptr); 02136 __builtin_memset(__p, 0, __n * sizeof(__bucket_type)); 02137 return __p; 02138 } 02139 02140 template<typename _NodeAlloc> 02141 void 02142 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts, 02143 std::size_t __n) 02144 { 02145 typedef typename __bucket_alloc_traits::pointer _Ptr; 02146 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts); 02147 __bucket_alloc_type __alloc(_M_node_allocator()); 02148 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n); 02149 } 02150 02151 //@} hashtable-detail 02152 } // namespace __detail 02153 _GLIBCXX_END_NAMESPACE_VERSION 02154 } // namespace std 02155 02156 #endif // _HASHTABLE_POLICY_H