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