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