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