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