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