libstdc++
|
00001 // hashtable.h header -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /** @file bits/hashtable.h 00027 * This is an internal header file, included by other library headers. 00028 * Do not attempt to use it directly. @headername{unordered_map, unordered_set} 00029 */ 00030 00031 #ifndef _HASHTABLE_H 00032 #define _HASHTABLE_H 1 00033 00034 #pragma GCC system_header 00035 00036 #include <bits/hashtable_policy.h> 00037 00038 namespace std _GLIBCXX_VISIBILITY(default) 00039 { 00040 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00041 00042 // Class template _Hashtable, class definition. 00043 00044 // Meaning of class template _Hashtable's template parameters 00045 00046 // _Key and _Value: arbitrary CopyConstructible types. 00047 00048 // _Allocator: an allocator type ([lib.allocator.requirements]) whose 00049 // value type is Value. As a conforming extension, we allow for 00050 // value type != Value. 00051 00052 // _ExtractKey: function object that takes an object of type Value 00053 // and returns a value of type _Key. 00054 00055 // _Equal: function object that takes two objects of type k and returns 00056 // a bool-like value that is true if the two objects are considered equal. 00057 00058 // _H1: the hash function. A unary function object with argument type 00059 // Key and result type size_t. Return values should be distributed 00060 // over the entire range [0, numeric_limits<size_t>:::max()]. 00061 00062 // _H2: the range-hashing function (in the terminology of Tavori and 00063 // Dreizin). A binary function object whose argument types and result 00064 // type are all size_t. Given arguments r and N, the return value is 00065 // in the range [0, N). 00066 00067 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function 00068 // whose argument types are _Key and size_t and whose result type is 00069 // size_t. Given arguments k and N, the return value is in the range 00070 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other 00071 // than the default, _H1 and _H2 are ignored. 00072 00073 // _RehashPolicy: Policy class with three members, all of which govern 00074 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller 00075 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate 00076 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) 00077 // determines whether, if the current bucket count is n_bkt and the 00078 // current element count is n_elt, we need to increase the bucket 00079 // count. If so, returns make_pair(true, n), where n is the new 00080 // bucket count. If not, returns make_pair(false, <anything>). 00081 00082 // __cache_hash_code: bool. true if we store the value of the hash 00083 // function along with the value. This is a time-space tradeoff. 00084 // Storing it may improve lookup speed by reducing the number of times 00085 // we need to call the Equal function. 00086 00087 // __constant_iterators: bool. true if iterator and const_iterator are 00088 // both constant iterator types. This is true for unordered_set and 00089 // unordered_multiset, false for unordered_map and unordered_multimap. 00090 00091 // __unique_keys: bool. true if the return value of _Hashtable::count(k) 00092 // is always at most one, false if it may be an arbitrary number. This 00093 // true for unordered_set and unordered_map, false for unordered_multiset 00094 // and unordered_multimap. 00095 /** 00096 * Here's _Hashtable data structure, each _Hashtable has: 00097 * - _Bucket[] _M_buckets 00098 * - _Hash_node_base _M_before_begin 00099 * - size_type _M_bucket_count 00100 * - size_type _M_element_count 00101 * 00102 * with _Bucket being _Hash_node* and _Hash_node constaining: 00103 * - _Hash_node* _M_next 00104 * - Tp _M_value 00105 * - size_t _M_code if cache_hash_code is true 00106 * 00107 * In terms of Standard containers the hastable is like the aggregation of: 00108 * - std::forward_list<_Node> containing the elements 00109 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets 00110 * 00111 * The non-empty buckets contain the node before the first bucket node. This 00112 * design allow to implement something like a std::forward_list::insert_after 00113 * on container insertion and std::forward_list::erase_after on container 00114 * erase calls. _M_before_begin is equivalent to 00115 * std::foward_list::before_begin. Empty buckets are containing nullptr. 00116 * Note that one of the non-empty bucket contains &_M_before_begin which is 00117 * not a derefenrenceable node so the node pointers in buckets shall never be 00118 * derefenrenced, only its next node can be. 00119 * 00120 * Walk through a bucket nodes require a check on the hash code to see if the 00121 * node is still in the bucket. Such a design impose a quite efficient hash 00122 * functor and is one of the reasons it is highly advise to set 00123 * __cache_hash_code to true. 00124 * 00125 * The container iterators are simply built from nodes. This way incrementing 00126 * the iterator is perfectly efficient independent of how many empty buckets 00127 * there are in the container. 00128 * 00129 * On insert we compute element hash code and thanks to it find the bucket 00130 * index. If the element must be inserted on an empty bucket we add it at the 00131 * beginning of the singly linked list and make the bucket point to 00132 * _M_before_begin. The bucket that used to point to _M_before_begin, if any, 00133 * is updated to point to its new before begin node. 00134 * 00135 * On erase, the simple iterator design impose to use the hash functor to get 00136 * the index of the bucket to update. For this reason, when __cache_hash_code 00137 * is set to false, there is a static assertion that the hash functor cannot 00138 * throw. 00139 */ 00140 00141 template<typename _Key, typename _Value, typename _Allocator, 00142 typename _ExtractKey, typename _Equal, 00143 typename _H1, typename _H2, typename _Hash, 00144 typename _RehashPolicy, 00145 bool __cache_hash_code, 00146 bool __constant_iterators, 00147 bool __unique_keys> 00148 class _Hashtable 00149 : public __detail::_Rehash_base<_RehashPolicy, 00150 _Hashtable<_Key, _Value, _Allocator, 00151 _ExtractKey, 00152 _Equal, _H1, _H2, _Hash, 00153 _RehashPolicy, 00154 __cache_hash_code, 00155 __constant_iterators, 00156 __unique_keys> >, 00157 public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00158 _H1, _H2, _Hash, __cache_hash_code>, 00159 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, 00160 _Hashtable<_Key, _Value, _Allocator, 00161 _ExtractKey, 00162 _Equal, _H1, _H2, _Hash, 00163 _RehashPolicy, 00164 __cache_hash_code, 00165 __constant_iterators, 00166 __unique_keys> >, 00167 public __detail::_Equality_base<_ExtractKey, __unique_keys, 00168 _Hashtable<_Key, _Value, _Allocator, 00169 _ExtractKey, 00170 _Equal, _H1, _H2, _Hash, 00171 _RehashPolicy, 00172 __cache_hash_code, 00173 __constant_iterators, 00174 __unique_keys> > 00175 { 00176 template<typename _Cond> 00177 using __if_hash_code_cached 00178 = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>; 00179 00180 template<typename _Cond> 00181 using __if_hash_code_not_cached 00182 = __or_<integral_constant<bool, __cache_hash_code>, _Cond>; 00183 00184 // When hash codes are not cached the hash functor shall not throw 00185 // because it is used in methods (erase, swap...) that shall not throw. 00186 static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key, 00187 _H1>>::value, 00188 "Cache the hash code or qualify your hash functor with noexcept"); 00189 00190 // Following two static assertions are necessary to guarantee that 00191 // swapping two hashtable instances won't invalidate associated local 00192 // iterators. 00193 00194 // When hash codes are cached local iterator only uses H2 which must then 00195 // be empty. 00196 static_assert(__if_hash_code_cached<is_empty<_H2>>::value, 00197 "Functor used to map hash code to bucket index must be empty"); 00198 00199 typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey, 00200 _H1, _H2, _Hash, 00201 __cache_hash_code> _HCBase; 00202 00203 // When hash codes are not cached local iterator is going to use _HCBase 00204 // above to compute node bucket index so it has to be empty. 00205 static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value, 00206 "Cache the hash code or make functors involved in hash code" 00207 " and bucket index computation empty"); 00208 00209 public: 00210 typedef _Allocator allocator_type; 00211 typedef _Value value_type; 00212 typedef _Key key_type; 00213 typedef _Equal key_equal; 00214 // mapped_type, if present, comes from _Map_base. 00215 // hasher, if present, comes from _Hash_code_base. 00216 typedef typename _Allocator::pointer pointer; 00217 typedef typename _Allocator::const_pointer const_pointer; 00218 typedef typename _Allocator::reference reference; 00219 typedef typename _Allocator::const_reference const_reference; 00220 00221 typedef std::size_t size_type; 00222 typedef std::ptrdiff_t difference_type; 00223 typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey, 00224 _H1, _H2, _Hash, 00225 __constant_iterators, 00226 __cache_hash_code> 00227 local_iterator; 00228 typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey, 00229 _H1, _H2, _Hash, 00230 __constant_iterators, 00231 __cache_hash_code> 00232 const_local_iterator; 00233 typedef __detail::_Node_iterator<value_type, __constant_iterators, 00234 __cache_hash_code> 00235 iterator; 00236 typedef __detail::_Node_const_iterator<value_type, 00237 __constant_iterators, 00238 __cache_hash_code> 00239 const_iterator; 00240 00241 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, 00242 typename _Hashtable2> 00243 friend struct __detail::_Map_base; 00244 00245 private: 00246 typedef typename _RehashPolicy::_State _RehashPolicyState; 00247 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; 00248 typedef typename _Allocator::template rebind<_Node>::other 00249 _Node_allocator_type; 00250 typedef __detail::_Hash_node_base _BaseNode; 00251 typedef _BaseNode* _Bucket; 00252 typedef typename _Allocator::template rebind<_Bucket>::other 00253 _Bucket_allocator_type; 00254 00255 typedef typename _Allocator::template rebind<_Value>::other 00256 _Value_allocator_type; 00257 00258 _Node_allocator_type _M_node_allocator; 00259 _Bucket* _M_buckets; 00260 size_type _M_bucket_count; 00261 _BaseNode _M_before_begin; 00262 size_type _M_element_count; 00263 _RehashPolicy _M_rehash_policy; 00264 00265 template<typename... _Args> 00266 _Node* 00267 _M_allocate_node(_Args&&... __args); 00268 00269 void 00270 _M_deallocate_node(_Node* __n); 00271 00272 // Deallocate the linked list of nodes pointed to by __n 00273 void 00274 _M_deallocate_nodes(_Node* __n); 00275 00276 _Bucket* 00277 _M_allocate_buckets(size_type __n); 00278 00279 void 00280 _M_deallocate_buckets(_Bucket*, size_type __n); 00281 00282 // Gets bucket begin, deals with the fact that non-empty buckets contain 00283 // their before begin node. 00284 _Node* 00285 _M_bucket_begin(size_type __bkt) const; 00286 00287 _Node* 00288 _M_begin() const 00289 { return static_cast<_Node*>(_M_before_begin._M_nxt); } 00290 00291 public: 00292 // Constructor, destructor, assignment, swap 00293 _Hashtable(size_type __bucket_hint, 00294 const _H1&, const _H2&, const _Hash&, 00295 const _Equal&, const _ExtractKey&, 00296 const allocator_type&); 00297 00298 template<typename _InputIterator> 00299 _Hashtable(_InputIterator __first, _InputIterator __last, 00300 size_type __bucket_hint, 00301 const _H1&, const _H2&, const _Hash&, 00302 const _Equal&, const _ExtractKey&, 00303 const allocator_type&); 00304 00305 _Hashtable(const _Hashtable&); 00306 00307 _Hashtable(_Hashtable&&); 00308 00309 _Hashtable& 00310 operator=(const _Hashtable& __ht) 00311 { 00312 _Hashtable __tmp(__ht); 00313 this->swap(__tmp); 00314 return *this; 00315 } 00316 00317 _Hashtable& 00318 operator=(_Hashtable&& __ht) 00319 { 00320 // NB: DR 1204. 00321 // NB: DR 675. 00322 this->clear(); 00323 this->swap(__ht); 00324 return *this; 00325 } 00326 00327 ~_Hashtable() noexcept; 00328 00329 void swap(_Hashtable&); 00330 00331 // Basic container operations 00332 iterator 00333 begin() noexcept 00334 { return iterator(_M_begin()); } 00335 00336 const_iterator 00337 begin() const noexcept 00338 { return const_iterator(_M_begin()); } 00339 00340 iterator 00341 end() noexcept 00342 { return iterator(nullptr); } 00343 00344 const_iterator 00345 end() const noexcept 00346 { return const_iterator(nullptr); } 00347 00348 const_iterator 00349 cbegin() const noexcept 00350 { return const_iterator(_M_begin()); } 00351 00352 const_iterator 00353 cend() const noexcept 00354 { return const_iterator(nullptr); } 00355 00356 size_type 00357 size() const noexcept 00358 { return _M_element_count; } 00359 00360 bool 00361 empty() const noexcept 00362 { return size() == 0; } 00363 00364 allocator_type 00365 get_allocator() const noexcept 00366 { return allocator_type(_M_node_allocator); } 00367 00368 size_type 00369 max_size() const noexcept 00370 { return _M_node_allocator.max_size(); } 00371 00372 // Observers 00373 key_equal 00374 key_eq() const 00375 { return this->_M_eq(); } 00376 00377 // hash_function, if present, comes from _Hash_code_base. 00378 00379 // Bucket operations 00380 size_type 00381 bucket_count() const noexcept 00382 { return _M_bucket_count; } 00383 00384 size_type 00385 max_bucket_count() const noexcept 00386 { return max_size(); } 00387 00388 size_type 00389 bucket_size(size_type __n) const 00390 { return std::distance(begin(__n), end(__n)); } 00391 00392 size_type 00393 bucket(const key_type& __k) const 00394 { return _M_bucket_index(__k, this->_M_hash_code(__k)); } 00395 00396 local_iterator 00397 begin(size_type __n) 00398 { return local_iterator(_M_bucket_begin(__n), __n, 00399 _M_bucket_count); } 00400 00401 local_iterator 00402 end(size_type __n) 00403 { return local_iterator(nullptr, __n, _M_bucket_count); } 00404 00405 const_local_iterator 00406 begin(size_type __n) const 00407 { return const_local_iterator(_M_bucket_begin(__n), __n, 00408 _M_bucket_count); } 00409 00410 const_local_iterator 00411 end(size_type __n) const 00412 { return const_local_iterator(nullptr, __n, _M_bucket_count); } 00413 00414 // DR 691. 00415 const_local_iterator 00416 cbegin(size_type __n) const 00417 { return const_local_iterator(_M_bucket_begin(__n), __n, 00418 _M_bucket_count); } 00419 00420 const_local_iterator 00421 cend(size_type __n) const 00422 { return const_local_iterator(nullptr, __n, _M_bucket_count); } 00423 00424 float 00425 load_factor() const noexcept 00426 { 00427 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 00428 } 00429 00430 // max_load_factor, if present, comes from _Rehash_base. 00431 00432 // Generalization of max_load_factor. Extension, not found in TR1. Only 00433 // useful if _RehashPolicy is something other than the default. 00434 const _RehashPolicy& 00435 __rehash_policy() const 00436 { return _M_rehash_policy; } 00437 00438 void 00439 __rehash_policy(const _RehashPolicy&); 00440 00441 // Lookup. 00442 iterator 00443 find(const key_type& __k); 00444 00445 const_iterator 00446 find(const key_type& __k) const; 00447 00448 size_type 00449 count(const key_type& __k) const; 00450 00451 std::pair<iterator, iterator> 00452 equal_range(const key_type& __k); 00453 00454 std::pair<const_iterator, const_iterator> 00455 equal_range(const key_type& __k) const; 00456 00457 private: 00458 // Bucket index computation helpers. 00459 size_type 00460 _M_bucket_index(_Node* __n) const 00461 { return _HCBase::_M_bucket_index(__n, _M_bucket_count); } 00462 00463 size_type 00464 _M_bucket_index(const key_type& __k, 00465 typename _Hashtable::_Hash_code_type __c) const 00466 { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); } 00467 00468 // Find and insert helper functions and types 00469 // Find the node before the one matching the criteria. 00470 _BaseNode* 00471 _M_find_before_node(size_type, const key_type&, 00472 typename _Hashtable::_Hash_code_type) const; 00473 00474 _Node* 00475 _M_find_node(size_type __bkt, const key_type& __key, 00476 typename _Hashtable::_Hash_code_type __c) const 00477 { 00478 _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c); 00479 if (__before_n) 00480 return static_cast<_Node*>(__before_n->_M_nxt); 00481 return nullptr; 00482 } 00483 00484 // Insert a node at the beginning of a bucket. 00485 void 00486 _M_insert_bucket_begin(size_type, _Node*); 00487 00488 // Remove the bucket first node 00489 void 00490 _M_remove_bucket_begin(size_type __bkt, _Node* __next_n, 00491 size_type __next_bkt); 00492 00493 // Get the node before __n in the bucket __bkt 00494 _BaseNode* 00495 _M_get_previous_node(size_type __bkt, _BaseNode* __n); 00496 00497 template<typename _Arg> 00498 iterator 00499 _M_insert_bucket(_Arg&&, size_type, 00500 typename _Hashtable::_Hash_code_type); 00501 00502 typedef typename std::conditional<__unique_keys, 00503 std::pair<iterator, bool>, 00504 iterator>::type 00505 _Insert_Return_Type; 00506 00507 typedef typename std::conditional<__unique_keys, 00508 std::_Select1st<_Insert_Return_Type>, 00509 std::_Identity<_Insert_Return_Type> 00510 >::type 00511 _Insert_Conv_Type; 00512 00513 protected: 00514 template<typename... _Args> 00515 std::pair<iterator, bool> 00516 _M_emplace(std::true_type, _Args&&... __args); 00517 00518 template<typename... _Args> 00519 iterator 00520 _M_emplace(std::false_type, _Args&&... __args); 00521 00522 template<typename _Arg> 00523 std::pair<iterator, bool> 00524 _M_insert(_Arg&&, std::true_type); 00525 00526 template<typename _Arg> 00527 iterator 00528 _M_insert(_Arg&&, std::false_type); 00529 00530 public: 00531 // Emplace, insert and erase 00532 template<typename... _Args> 00533 _Insert_Return_Type 00534 emplace(_Args&&... __args) 00535 { return _M_emplace(integral_constant<bool, __unique_keys>(), 00536 std::forward<_Args>(__args)...); } 00537 00538 template<typename... _Args> 00539 iterator 00540 emplace_hint(const_iterator, _Args&&... __args) 00541 { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); } 00542 00543 _Insert_Return_Type 00544 insert(const value_type& __v) 00545 { return _M_insert(__v, integral_constant<bool, __unique_keys>()); } 00546 00547 iterator 00548 insert(const_iterator, const value_type& __v) 00549 { return _Insert_Conv_Type()(insert(__v)); } 00550 00551 template<typename _Pair, typename = typename 00552 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>, 00553 std::is_convertible<_Pair, 00554 value_type>>::value>::type> 00555 _Insert_Return_Type 00556 insert(_Pair&& __v) 00557 { return _M_insert(std::forward<_Pair>(__v), 00558 integral_constant<bool, __unique_keys>()); } 00559 00560 template<typename _Pair, typename = typename 00561 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>, 00562 std::is_convertible<_Pair, 00563 value_type>>::value>::type> 00564 iterator 00565 insert(const_iterator, _Pair&& __v) 00566 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); } 00567 00568 template<typename _InputIterator> 00569 void 00570 insert(_InputIterator __first, _InputIterator __last); 00571 00572 void 00573 insert(initializer_list<value_type> __l) 00574 { this->insert(__l.begin(), __l.end()); } 00575 00576 iterator 00577 erase(const_iterator); 00578 00579 // LWG 2059. 00580 iterator 00581 erase(iterator __it) 00582 { return erase(const_iterator(__it)); } 00583 00584 size_type 00585 erase(const key_type&); 00586 00587 iterator 00588 erase(const_iterator, const_iterator); 00589 00590 void 00591 clear() noexcept; 00592 00593 // Set number of buckets to be appropriate for container of n element. 00594 void rehash(size_type __n); 00595 00596 // DR 1189. 00597 // reserve, if present, comes from _Rehash_base. 00598 00599 private: 00600 // Helper rehash method used when keys are unique. 00601 void _M_rehash_aux(size_type __n, std::true_type); 00602 00603 // Helper rehash method used when keys can be non-unique. 00604 void _M_rehash_aux(size_type __n, std::false_type); 00605 00606 // Unconditionally change size of bucket array to n, restore hash policy 00607 // state to __state on exception. 00608 void _M_rehash(size_type __n, const _RehashPolicyState& __state); 00609 }; 00610 00611 00612 // Definitions of class template _Hashtable's out-of-line member functions. 00613 template<typename _Key, typename _Value, 00614 typename _Allocator, typename _ExtractKey, typename _Equal, 00615 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00616 bool __chc, bool __cit, bool __uk> 00617 template<typename... _Args> 00618 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00619 _H1, _H2, _Hash, _RehashPolicy, 00620 __chc, __cit, __uk>::_Node* 00621 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00622 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00623 _M_allocate_node(_Args&&... __args) 00624 { 00625 _Node* __n = _M_node_allocator.allocate(1); 00626 __try 00627 { 00628 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); 00629 return __n; 00630 } 00631 __catch(...) 00632 { 00633 _M_node_allocator.deallocate(__n, 1); 00634 __throw_exception_again; 00635 } 00636 } 00637 00638 template<typename _Key, typename _Value, 00639 typename _Allocator, typename _ExtractKey, typename _Equal, 00640 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00641 bool __chc, bool __cit, bool __uk> 00642 void 00643 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00644 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00645 _M_deallocate_node(_Node* __n) 00646 { 00647 _M_node_allocator.destroy(__n); 00648 _M_node_allocator.deallocate(__n, 1); 00649 } 00650 00651 template<typename _Key, typename _Value, 00652 typename _Allocator, typename _ExtractKey, typename _Equal, 00653 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00654 bool __chc, bool __cit, bool __uk> 00655 void 00656 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00657 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00658 _M_deallocate_nodes(_Node* __n) 00659 { 00660 while (__n) 00661 { 00662 _Node* __tmp = __n; 00663 __n = __n->_M_next(); 00664 _M_deallocate_node(__tmp); 00665 } 00666 } 00667 00668 template<typename _Key, typename _Value, 00669 typename _Allocator, typename _ExtractKey, typename _Equal, 00670 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00671 bool __chc, bool __cit, bool __uk> 00672 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00673 _H1, _H2, _Hash, _RehashPolicy, 00674 __chc, __cit, __uk>::_Bucket* 00675 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00676 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00677 _M_allocate_buckets(size_type __n) 00678 { 00679 _Bucket_allocator_type __alloc(_M_node_allocator); 00680 00681 _Bucket* __p = __alloc.allocate(__n); 00682 __builtin_memset(__p, 0, __n * sizeof(_Bucket)); 00683 return __p; 00684 } 00685 00686 template<typename _Key, typename _Value, 00687 typename _Allocator, typename _ExtractKey, typename _Equal, 00688 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00689 bool __chc, bool __cit, bool __uk> 00690 void 00691 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00692 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00693 _M_deallocate_buckets(_Bucket* __p, size_type __n) 00694 { 00695 _Bucket_allocator_type __alloc(_M_node_allocator); 00696 __alloc.deallocate(__p, __n); 00697 } 00698 00699 template<typename _Key, typename _Value, 00700 typename _Allocator, typename _ExtractKey, typename _Equal, 00701 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00702 bool __chc, bool __cit, bool __uk> 00703 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 00704 _Equal, _H1, _H2, _Hash, _RehashPolicy, 00705 __chc, __cit, __uk>::_Node* 00706 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00707 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00708 _M_bucket_begin(size_type __bkt) const 00709 { 00710 _BaseNode* __n = _M_buckets[__bkt]; 00711 return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr; 00712 } 00713 00714 template<typename _Key, typename _Value, 00715 typename _Allocator, typename _ExtractKey, typename _Equal, 00716 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00717 bool __chc, bool __cit, bool __uk> 00718 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00719 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00720 _Hashtable(size_type __bucket_hint, 00721 const _H1& __h1, const _H2& __h2, const _Hash& __h, 00722 const _Equal& __eq, const _ExtractKey& __exk, 00723 const allocator_type& __a) 00724 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 00725 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00726 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, 00727 __eq), 00728 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 00729 _M_node_allocator(__a), 00730 _M_bucket_count(0), 00731 _M_element_count(0), 00732 _M_rehash_policy() 00733 { 00734 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 00735 // We don't want the rehash policy to ask for the hashtable to shrink 00736 // on the first insertion so we need to reset its previous resize level. 00737 _M_rehash_policy._M_prev_resize = 0; 00738 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00739 } 00740 00741 template<typename _Key, typename _Value, 00742 typename _Allocator, typename _ExtractKey, typename _Equal, 00743 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00744 bool __chc, bool __cit, bool __uk> 00745 template<typename _InputIterator> 00746 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00747 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00748 _Hashtable(_InputIterator __f, _InputIterator __l, 00749 size_type __bucket_hint, 00750 const _H1& __h1, const _H2& __h2, const _Hash& __h, 00751 const _Equal& __eq, const _ExtractKey& __exk, 00752 const allocator_type& __a) 00753 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 00754 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00755 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, 00756 __eq), 00757 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 00758 _M_node_allocator(__a), 00759 _M_bucket_count(0), 00760 _M_element_count(0), 00761 _M_rehash_policy() 00762 { 00763 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), 00764 _M_rehash_policy. 00765 _M_bkt_for_elements(__detail:: 00766 __distance_fw(__f, 00767 __l))); 00768 // We don't want the rehash policy to ask for the hashtable to shrink 00769 // on the first insertion so we need to reset its previous resize 00770 // level. 00771 _M_rehash_policy._M_prev_resize = 0; 00772 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00773 __try 00774 { 00775 for (; __f != __l; ++__f) 00776 this->insert(*__f); 00777 } 00778 __catch(...) 00779 { 00780 clear(); 00781 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00782 __throw_exception_again; 00783 } 00784 } 00785 00786 template<typename _Key, typename _Value, 00787 typename _Allocator, typename _ExtractKey, typename _Equal, 00788 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00789 bool __chc, bool __cit, bool __uk> 00790 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00791 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00792 _Hashtable(const _Hashtable& __ht) 00793 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 00794 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00795 _H1, _H2, _Hash, __chc>(__ht), 00796 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 00797 _M_node_allocator(__ht._M_node_allocator), 00798 _M_bucket_count(__ht._M_bucket_count), 00799 _M_element_count(__ht._M_element_count), 00800 _M_rehash_policy(__ht._M_rehash_policy) 00801 { 00802 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00803 __try 00804 { 00805 if (!__ht._M_before_begin._M_nxt) 00806 return; 00807 00808 // First deal with the special first node pointed to by 00809 // _M_before_begin. 00810 const _Node* __ht_n = __ht._M_begin(); 00811 _Node* __this_n = _M_allocate_node(__ht_n->_M_v); 00812 this->_M_copy_code(__this_n, __ht_n); 00813 _M_before_begin._M_nxt = __this_n; 00814 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; 00815 00816 // Then deal with other nodes. 00817 _BaseNode* __prev_n = __this_n; 00818 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) 00819 { 00820 __this_n = _M_allocate_node(__ht_n->_M_v); 00821 __prev_n->_M_nxt = __this_n; 00822 this->_M_copy_code(__this_n, __ht_n); 00823 size_type __bkt = _M_bucket_index(__this_n); 00824 if (!_M_buckets[__bkt]) 00825 _M_buckets[__bkt] = __prev_n; 00826 __prev_n = __this_n; 00827 } 00828 } 00829 __catch(...) 00830 { 00831 clear(); 00832 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00833 __throw_exception_again; 00834 } 00835 } 00836 00837 template<typename _Key, typename _Value, 00838 typename _Allocator, typename _ExtractKey, typename _Equal, 00839 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00840 bool __chc, bool __cit, bool __uk> 00841 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00842 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00843 _Hashtable(_Hashtable&& __ht) 00844 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 00845 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00846 _H1, _H2, _Hash, __chc>(__ht), 00847 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 00848 _M_node_allocator(std::move(__ht._M_node_allocator)), 00849 _M_buckets(__ht._M_buckets), 00850 _M_bucket_count(__ht._M_bucket_count), 00851 _M_before_begin(__ht._M_before_begin._M_nxt), 00852 _M_element_count(__ht._M_element_count), 00853 _M_rehash_policy(__ht._M_rehash_policy) 00854 { 00855 // Update, if necessary, bucket pointing to before begin that hasn't move. 00856 if (_M_begin()) 00857 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 00858 __ht._M_rehash_policy = _RehashPolicy(); 00859 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0); 00860 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count); 00861 __ht._M_before_begin._M_nxt = nullptr; 00862 __ht._M_element_count = 0; 00863 } 00864 00865 template<typename _Key, typename _Value, 00866 typename _Allocator, typename _ExtractKey, typename _Equal, 00867 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00868 bool __chc, bool __cit, bool __uk> 00869 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00870 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00871 ~_Hashtable() noexcept 00872 { 00873 clear(); 00874 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00875 } 00876 00877 template<typename _Key, typename _Value, 00878 typename _Allocator, typename _ExtractKey, typename _Equal, 00879 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00880 bool __chc, bool __cit, bool __uk> 00881 void 00882 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00883 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00884 swap(_Hashtable& __x) 00885 { 00886 // The only base class with member variables is hash_code_base. We 00887 // define _Hash_code_base::_M_swap because different specializations 00888 // have different members. 00889 this->_M_swap(__x); 00890 00891 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00892 // 431. Swapping containers with unequal allocators. 00893 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 00894 __x._M_node_allocator); 00895 00896 std::swap(_M_rehash_policy, __x._M_rehash_policy); 00897 std::swap(_M_buckets, __x._M_buckets); 00898 std::swap(_M_bucket_count, __x._M_bucket_count); 00899 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); 00900 std::swap(_M_element_count, __x._M_element_count); 00901 // Fix buckets containing the _M_before_begin pointers that can't be 00902 // swapped. 00903 if (_M_begin()) 00904 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 00905 if (__x._M_begin()) 00906 __x._M_buckets[__x._M_bucket_index(__x._M_begin())] 00907 = &(__x._M_before_begin); 00908 } 00909 00910 template<typename _Key, typename _Value, 00911 typename _Allocator, typename _ExtractKey, typename _Equal, 00912 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00913 bool __chc, bool __cit, bool __uk> 00914 void 00915 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00916 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00917 __rehash_policy(const _RehashPolicy& __pol) 00918 { 00919 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 00920 if (__n_bkt != _M_bucket_count) 00921 _M_rehash(__n_bkt, _M_rehash_policy._M_state()); 00922 _M_rehash_policy = __pol; 00923 } 00924 00925 template<typename _Key, typename _Value, 00926 typename _Allocator, typename _ExtractKey, typename _Equal, 00927 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00928 bool __chc, bool __cit, bool __uk> 00929 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00930 _H1, _H2, _Hash, _RehashPolicy, 00931 __chc, __cit, __uk>::iterator 00932 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00933 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00934 find(const key_type& __k) 00935 { 00936 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00937 std::size_t __n = _M_bucket_index(__k, __code); 00938 _Node* __p = _M_find_node(__n, __k, __code); 00939 return __p ? iterator(__p) : this->end(); 00940 } 00941 00942 template<typename _Key, typename _Value, 00943 typename _Allocator, typename _ExtractKey, typename _Equal, 00944 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00945 bool __chc, bool __cit, bool __uk> 00946 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00947 _H1, _H2, _Hash, _RehashPolicy, 00948 __chc, __cit, __uk>::const_iterator 00949 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00950 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00951 find(const key_type& __k) const 00952 { 00953 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00954 std::size_t __n = _M_bucket_index(__k, __code); 00955 _Node* __p = _M_find_node(__n, __k, __code); 00956 return __p ? const_iterator(__p) : this->end(); 00957 } 00958 00959 template<typename _Key, typename _Value, 00960 typename _Allocator, typename _ExtractKey, typename _Equal, 00961 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00962 bool __chc, bool __cit, bool __uk> 00963 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00964 _H1, _H2, _Hash, _RehashPolicy, 00965 __chc, __cit, __uk>::size_type 00966 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00967 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00968 count(const key_type& __k) const 00969 { 00970 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00971 std::size_t __n = _M_bucket_index(__k, __code); 00972 _Node* __p = _M_bucket_begin(__n); 00973 if (!__p) 00974 return 0; 00975 00976 std::size_t __result = 0; 00977 for (;; __p = __p->_M_next()) 00978 { 00979 if (this->_M_equals(__k, __code, __p)) 00980 ++__result; 00981 else if (__result) 00982 // All equivalent values are next to each other, if we found a not 00983 // equivalent value after an equivalent one it means that we won't 00984 // find anymore an equivalent value. 00985 break; 00986 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 00987 break; 00988 } 00989 return __result; 00990 } 00991 00992 template<typename _Key, typename _Value, 00993 typename _Allocator, typename _ExtractKey, typename _Equal, 00994 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00995 bool __chc, bool __cit, bool __uk> 00996 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 00997 _ExtractKey, _Equal, _H1, 00998 _H2, _Hash, _RehashPolicy, 00999 __chc, __cit, __uk>::iterator, 01000 typename _Hashtable<_Key, _Value, _Allocator, 01001 _ExtractKey, _Equal, _H1, 01002 _H2, _Hash, _RehashPolicy, 01003 __chc, __cit, __uk>::iterator> 01004 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01005 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01006 equal_range(const key_type& __k) 01007 { 01008 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01009 std::size_t __n = _M_bucket_index(__k, __code); 01010 _Node* __p = _M_find_node(__n, __k, __code); 01011 01012 if (__p) 01013 { 01014 _Node* __p1 = __p->_M_next(); 01015 while (__p1 && _M_bucket_index(__p1) == __n 01016 && this->_M_equals(__k, __code, __p1)) 01017 __p1 = __p1->_M_next(); 01018 01019 return std::make_pair(iterator(__p), iterator(__p1)); 01020 } 01021 else 01022 return std::make_pair(this->end(), this->end()); 01023 } 01024 01025 template<typename _Key, typename _Value, 01026 typename _Allocator, typename _ExtractKey, typename _Equal, 01027 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01028 bool __chc, bool __cit, bool __uk> 01029 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 01030 _ExtractKey, _Equal, _H1, 01031 _H2, _Hash, _RehashPolicy, 01032 __chc, __cit, __uk>::const_iterator, 01033 typename _Hashtable<_Key, _Value, _Allocator, 01034 _ExtractKey, _Equal, _H1, 01035 _H2, _Hash, _RehashPolicy, 01036 __chc, __cit, __uk>::const_iterator> 01037 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01038 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01039 equal_range(const key_type& __k) const 01040 { 01041 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01042 std::size_t __n = _M_bucket_index(__k, __code); 01043 _Node* __p = _M_find_node(__n, __k, __code); 01044 01045 if (__p) 01046 { 01047 _Node* __p1 = __p->_M_next(); 01048 while (__p1 && _M_bucket_index(__p1) == __n 01049 && this->_M_equals(__k, __code, __p1)) 01050 __p1 = __p1->_M_next(); 01051 01052 return std::make_pair(const_iterator(__p), const_iterator(__p1)); 01053 } 01054 else 01055 return std::make_pair(this->end(), this->end()); 01056 } 01057 01058 // Find the node whose key compares equal to k in the bucket n. Return nullptr 01059 // if no node is found. 01060 template<typename _Key, typename _Value, 01061 typename _Allocator, typename _ExtractKey, typename _Equal, 01062 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01063 bool __chc, bool __cit, bool __uk> 01064 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 01065 _Equal, _H1, _H2, _Hash, _RehashPolicy, 01066 __chc, __cit, __uk>::_BaseNode* 01067 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01068 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01069 _M_find_before_node(size_type __n, const key_type& __k, 01070 typename _Hashtable::_Hash_code_type __code) const 01071 { 01072 _BaseNode* __prev_p = _M_buckets[__n]; 01073 if (!__prev_p) 01074 return nullptr; 01075 _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); 01076 for (;; __p = __p->_M_next()) 01077 { 01078 if (this->_M_equals(__k, __code, __p)) 01079 return __prev_p; 01080 if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n) 01081 break; 01082 __prev_p = __p; 01083 } 01084 return nullptr; 01085 } 01086 01087 template<typename _Key, typename _Value, 01088 typename _Allocator, typename _ExtractKey, typename _Equal, 01089 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01090 bool __chc, bool __cit, bool __uk> 01091 void 01092 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01093 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01094 _M_insert_bucket_begin(size_type __bkt, _Node* __new_node) 01095 { 01096 if (_M_buckets[__bkt]) 01097 { 01098 // Bucket is not empty, we just need to insert the new node after the 01099 // bucket before begin. 01100 __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt; 01101 _M_buckets[__bkt]->_M_nxt = __new_node; 01102 } 01103 else 01104 { 01105 // The bucket is empty, the new node is inserted at the beginning of 01106 // the singly linked list and the bucket will contain _M_before_begin 01107 // pointer. 01108 __new_node->_M_nxt = _M_before_begin._M_nxt; 01109 _M_before_begin._M_nxt = __new_node; 01110 if (__new_node->_M_nxt) 01111 // We must update former begin bucket that is pointing to 01112 // _M_before_begin. 01113 _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node; 01114 _M_buckets[__bkt] = &_M_before_begin; 01115 } 01116 } 01117 01118 template<typename _Key, typename _Value, 01119 typename _Allocator, typename _ExtractKey, typename _Equal, 01120 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01121 bool __chc, bool __cit, bool __uk> 01122 void 01123 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01124 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01125 _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt) 01126 { 01127 if (!__next || __next_bkt != __bkt) 01128 { 01129 // Bucket is now empty 01130 // First update next bucket if any 01131 if (__next) 01132 _M_buckets[__next_bkt] = _M_buckets[__bkt]; 01133 // Second update before begin node if necessary 01134 if (&_M_before_begin == _M_buckets[__bkt]) 01135 _M_before_begin._M_nxt = __next; 01136 _M_buckets[__bkt] = nullptr; 01137 } 01138 } 01139 01140 template<typename _Key, typename _Value, 01141 typename _Allocator, typename _ExtractKey, typename _Equal, 01142 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01143 bool __chc, bool __cit, bool __uk> 01144 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 01145 _Equal, _H1, _H2, _Hash, _RehashPolicy, 01146 __chc, __cit, __uk>::_BaseNode* 01147 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01148 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01149 _M_get_previous_node(size_type __bkt, _BaseNode* __n) 01150 { 01151 _BaseNode* __prev_n = _M_buckets[__bkt]; 01152 while (__prev_n->_M_nxt != __n) 01153 __prev_n = __prev_n->_M_nxt; 01154 return __prev_n; 01155 } 01156 01157 template<typename _Key, typename _Value, 01158 typename _Allocator, typename _ExtractKey, typename _Equal, 01159 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01160 bool __chc, bool __cit, bool __uk> 01161 template<typename... _Args> 01162 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 01163 _ExtractKey, _Equal, _H1, 01164 _H2, _Hash, _RehashPolicy, 01165 __chc, __cit, __uk>::iterator, bool> 01166 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01167 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01168 _M_emplace(std::true_type, _Args&&... __args) 01169 { 01170 // First build the node to get access to the hash code 01171 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); 01172 __try 01173 { 01174 const key_type& __k = this->_M_extract()(__new_node->_M_v); 01175 typename _Hashtable::_Hash_code_type __code 01176 = this->_M_hash_code(__k); 01177 size_type __bkt = _M_bucket_index(__k, __code); 01178 01179 if (_Node* __p = _M_find_node(__bkt, __k, __code)) 01180 { 01181 // There is already an equivalent node, no insertion 01182 _M_deallocate_node(__new_node); 01183 return std::make_pair(iterator(__p), false); 01184 } 01185 01186 // We are going to insert this node 01187 this->_M_store_code(__new_node, __code); 01188 const _RehashPolicyState& __saved_state 01189 = _M_rehash_policy._M_state(); 01190 std::pair<bool, std::size_t> __do_rehash 01191 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01192 _M_element_count, 1); 01193 01194 if (__do_rehash.first) 01195 { 01196 _M_rehash(__do_rehash.second, __saved_state); 01197 __bkt = _M_bucket_index(__k, __code); 01198 } 01199 01200 _M_insert_bucket_begin(__bkt, __new_node); 01201 ++_M_element_count; 01202 return std::make_pair(iterator(__new_node), true); 01203 } 01204 __catch(...) 01205 { 01206 _M_deallocate_node(__new_node); 01207 __throw_exception_again; 01208 } 01209 } 01210 01211 template<typename _Key, typename _Value, 01212 typename _Allocator, typename _ExtractKey, typename _Equal, 01213 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01214 bool __chc, bool __cit, bool __uk> 01215 template<typename... _Args> 01216 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01217 _H1, _H2, _Hash, _RehashPolicy, 01218 __chc, __cit, __uk>::iterator 01219 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01220 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01221 _M_emplace(std::false_type, _Args&&... __args) 01222 { 01223 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01224 std::pair<bool, std::size_t> __do_rehash 01225 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01226 _M_element_count, 1); 01227 01228 // First build the node to get its hash code. 01229 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); 01230 __try 01231 { 01232 const key_type& __k = this->_M_extract()(__new_node->_M_v); 01233 typename _Hashtable::_Hash_code_type __code 01234 = this->_M_hash_code(__k); 01235 this->_M_store_code(__new_node, __code); 01236 01237 // Second, do rehash if necessary. 01238 if (__do_rehash.first) 01239 _M_rehash(__do_rehash.second, __saved_state); 01240 01241 // Third, find the node before an equivalent one. 01242 size_type __bkt = _M_bucket_index(__k, __code); 01243 _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code); 01244 01245 if (__prev) 01246 { 01247 // Insert after the node before the equivalent one. 01248 __new_node->_M_nxt = __prev->_M_nxt; 01249 __prev->_M_nxt = __new_node; 01250 } 01251 else 01252 // The inserted node has no equivalent in the hashtable. We must 01253 // insert the new node at the beginning of the bucket to preserve 01254 // equivalent elements relative positions. 01255 _M_insert_bucket_begin(__bkt, __new_node); 01256 ++_M_element_count; 01257 return iterator(__new_node); 01258 } 01259 __catch(...) 01260 { 01261 _M_deallocate_node(__new_node); 01262 __throw_exception_again; 01263 } 01264 } 01265 01266 // Insert v in bucket n (assumes no element with its key already present). 01267 template<typename _Key, typename _Value, 01268 typename _Allocator, typename _ExtractKey, typename _Equal, 01269 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01270 bool __chc, bool __cit, bool __uk> 01271 template<typename _Arg> 01272 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01273 _H1, _H2, _Hash, _RehashPolicy, 01274 __chc, __cit, __uk>::iterator 01275 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01276 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01277 _M_insert_bucket(_Arg&& __v, size_type __n, 01278 typename _Hashtable::_Hash_code_type __code) 01279 { 01280 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01281 std::pair<bool, std::size_t> __do_rehash 01282 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01283 _M_element_count, 1); 01284 01285 if (__do_rehash.first) 01286 { 01287 const key_type& __k = this->_M_extract()(__v); 01288 __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second); 01289 } 01290 01291 _Node* __new_node = nullptr; 01292 __try 01293 { 01294 // Allocate the new node before doing the rehash so that we 01295 // don't do a rehash if the allocation throws. 01296 __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 01297 this->_M_store_code(__new_node, __code); 01298 if (__do_rehash.first) 01299 _M_rehash(__do_rehash.second, __saved_state); 01300 01301 _M_insert_bucket_begin(__n, __new_node); 01302 ++_M_element_count; 01303 return iterator(__new_node); 01304 } 01305 __catch(...) 01306 { 01307 if (!__new_node) 01308 _M_rehash_policy._M_reset(__saved_state); 01309 else 01310 _M_deallocate_node(__new_node); 01311 __throw_exception_again; 01312 } 01313 } 01314 01315 // Insert v if no element with its key is already present. 01316 template<typename _Key, typename _Value, 01317 typename _Allocator, typename _ExtractKey, typename _Equal, 01318 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01319 bool __chc, bool __cit, bool __uk> 01320 template<typename _Arg> 01321 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 01322 _ExtractKey, _Equal, _H1, 01323 _H2, _Hash, _RehashPolicy, 01324 __chc, __cit, __uk>::iterator, bool> 01325 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01326 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01327 _M_insert(_Arg&& __v, std::true_type) 01328 { 01329 const key_type& __k = this->_M_extract()(__v); 01330 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01331 size_type __n = _M_bucket_index(__k, __code); 01332 01333 if (_Node* __p = _M_find_node(__n, __k, __code)) 01334 return std::make_pair(iterator(__p), false); 01335 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v), 01336 __n, __code), true); 01337 } 01338 01339 // Insert v unconditionally. 01340 template<typename _Key, typename _Value, 01341 typename _Allocator, typename _ExtractKey, typename _Equal, 01342 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01343 bool __chc, bool __cit, bool __uk> 01344 template<typename _Arg> 01345 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01346 _H1, _H2, _Hash, _RehashPolicy, 01347 __chc, __cit, __uk>::iterator 01348 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01349 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01350 _M_insert(_Arg&& __v, std::false_type) 01351 { 01352 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01353 std::pair<bool, std::size_t> __do_rehash 01354 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01355 _M_element_count, 1); 01356 01357 // First compute the hash code so that we don't do anything if it throws. 01358 typename _Hashtable::_Hash_code_type __code 01359 = this->_M_hash_code(this->_M_extract()(__v)); 01360 01361 _Node* __new_node = nullptr; 01362 __try 01363 { 01364 // Second allocate new node so that we don't rehash if it throws. 01365 __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 01366 this->_M_store_code(__new_node, __code); 01367 if (__do_rehash.first) 01368 _M_rehash(__do_rehash.second, __saved_state); 01369 01370 // Third, find the node before an equivalent one. 01371 size_type __bkt = _M_bucket_index(__new_node); 01372 _BaseNode* __prev 01373 = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v), 01374 __code); 01375 if (__prev) 01376 { 01377 // Insert after the node before the equivalent one. 01378 __new_node->_M_nxt = __prev->_M_nxt; 01379 __prev->_M_nxt = __new_node; 01380 } 01381 else 01382 // The inserted node has no equivalent in the hashtable. We must 01383 // insert the new node at the beginning of the bucket to preserve 01384 // equivalent elements relative positions. 01385 _M_insert_bucket_begin(__bkt, __new_node); 01386 ++_M_element_count; 01387 return iterator(__new_node); 01388 } 01389 __catch(...) 01390 { 01391 if (!__new_node) 01392 _M_rehash_policy._M_reset(__saved_state); 01393 else 01394 _M_deallocate_node(__new_node); 01395 __throw_exception_again; 01396 } 01397 } 01398 01399 template<typename _Key, typename _Value, 01400 typename _Allocator, typename _ExtractKey, typename _Equal, 01401 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01402 bool __chc, bool __cit, bool __uk> 01403 template<typename _InputIterator> 01404 void 01405 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01406 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01407 insert(_InputIterator __first, _InputIterator __last) 01408 { 01409 size_type __n_elt = __detail::__distance_fw(__first, __last); 01410 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01411 std::pair<bool, std::size_t> __do_rehash 01412 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01413 _M_element_count, __n_elt); 01414 if (__do_rehash.first) 01415 _M_rehash(__do_rehash.second, __saved_state); 01416 01417 for (; __first != __last; ++__first) 01418 this->insert(*__first); 01419 } 01420 01421 template<typename _Key, typename _Value, 01422 typename _Allocator, typename _ExtractKey, typename _Equal, 01423 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01424 bool __chc, bool __cit, bool __uk> 01425 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01426 _H1, _H2, _Hash, _RehashPolicy, 01427 __chc, __cit, __uk>::iterator 01428 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01429 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01430 erase(const_iterator __it) 01431 { 01432 _Node* __n = __it._M_cur; 01433 std::size_t __bkt = _M_bucket_index(__n); 01434 01435 // Look for previous node to unlink it from the erased one, this is why 01436 // we need buckets to contain the before begin to make this research fast. 01437 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); 01438 if (__n == _M_bucket_begin(__bkt)) 01439 _M_remove_bucket_begin(__bkt, __n->_M_next(), 01440 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 01441 else if (__n->_M_nxt) 01442 { 01443 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 01444 if (__next_bkt != __bkt) 01445 _M_buckets[__next_bkt] = __prev_n; 01446 } 01447 01448 __prev_n->_M_nxt = __n->_M_nxt; 01449 iterator __result(__n->_M_next()); 01450 _M_deallocate_node(__n); 01451 --_M_element_count; 01452 01453 return __result; 01454 } 01455 01456 template<typename _Key, typename _Value, 01457 typename _Allocator, typename _ExtractKey, typename _Equal, 01458 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01459 bool __chc, bool __cit, bool __uk> 01460 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01461 _H1, _H2, _Hash, _RehashPolicy, 01462 __chc, __cit, __uk>::size_type 01463 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01464 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01465 erase(const key_type& __k) 01466 { 01467 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01468 std::size_t __bkt = _M_bucket_index(__k, __code); 01469 // Look for the node before the first matching node. 01470 _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code); 01471 if (!__prev_n) 01472 return 0; 01473 _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt); 01474 bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n; 01475 01476 // We found a matching node, start deallocation loop from it 01477 std::size_t __next_bkt = __bkt; 01478 _Node* __next_n = __n; 01479 size_type __result = 0; 01480 _Node* __saved_n = nullptr; 01481 do 01482 { 01483 _Node* __p = __next_n; 01484 __next_n = __p->_M_next(); 01485 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01486 // 526. Is it undefined if a function in the standard changes 01487 // in parameters? 01488 if (std::__addressof(this->_M_extract()(__p->_M_v)) 01489 != std::__addressof(__k)) 01490 _M_deallocate_node(__p); 01491 else 01492 __saved_n = __p; 01493 --_M_element_count; 01494 ++__result; 01495 if (!__next_n) 01496 break; 01497 __next_bkt = _M_bucket_index(__next_n); 01498 } 01499 while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n)); 01500 01501 if (__saved_n) 01502 _M_deallocate_node(__saved_n); 01503 if (__is_bucket_begin) 01504 _M_remove_bucket_begin(__bkt, __next_n, __next_bkt); 01505 else if (__next_n && __next_bkt != __bkt) 01506 _M_buckets[__next_bkt] = __prev_n; 01507 if (__prev_n) 01508 __prev_n->_M_nxt = __next_n; 01509 return __result; 01510 } 01511 01512 template<typename _Key, typename _Value, 01513 typename _Allocator, typename _ExtractKey, typename _Equal, 01514 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01515 bool __chc, bool __cit, bool __uk> 01516 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01517 _H1, _H2, _Hash, _RehashPolicy, 01518 __chc, __cit, __uk>::iterator 01519 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01520 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01521 erase(const_iterator __first, const_iterator __last) 01522 { 01523 _Node* __n = __first._M_cur; 01524 _Node* __last_n = __last._M_cur; 01525 if (__n == __last_n) 01526 return iterator(__n); 01527 01528 std::size_t __bkt = _M_bucket_index(__n); 01529 01530 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); 01531 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); 01532 std::size_t __n_bkt = __bkt; 01533 for (;;) 01534 { 01535 do 01536 { 01537 _Node* __tmp = __n; 01538 __n = __n->_M_next(); 01539 _M_deallocate_node(__tmp); 01540 --_M_element_count; 01541 if (!__n) 01542 break; 01543 __n_bkt = _M_bucket_index(__n); 01544 } 01545 while (__n != __last_n && __n_bkt == __bkt); 01546 if (__is_bucket_begin) 01547 _M_remove_bucket_begin(__bkt, __n, __n_bkt); 01548 if (__n == __last_n) 01549 break; 01550 __is_bucket_begin = true; 01551 __bkt = __n_bkt; 01552 } 01553 01554 if (__n && (__n_bkt != __bkt || __is_bucket_begin)) 01555 _M_buckets[__n_bkt] = __prev_n; 01556 __prev_n->_M_nxt = __n; 01557 return iterator(__n); 01558 } 01559 01560 template<typename _Key, typename _Value, 01561 typename _Allocator, typename _ExtractKey, typename _Equal, 01562 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01563 bool __chc, bool __cit, bool __uk> 01564 void 01565 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01566 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01567 clear() noexcept 01568 { 01569 _M_deallocate_nodes(_M_begin()); 01570 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket)); 01571 _M_element_count = 0; 01572 _M_before_begin._M_nxt = nullptr; 01573 } 01574 01575 template<typename _Key, typename _Value, 01576 typename _Allocator, typename _ExtractKey, typename _Equal, 01577 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01578 bool __chc, bool __cit, bool __uk> 01579 void 01580 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01581 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01582 rehash(size_type __n) 01583 { 01584 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01585 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), 01586 _M_rehash_policy._M_bkt_for_elements(_M_element_count 01587 + 1)), 01588 __saved_state); 01589 } 01590 01591 template<typename _Key, typename _Value, 01592 typename _Allocator, typename _ExtractKey, typename _Equal, 01593 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01594 bool __chc, bool __cit, bool __uk> 01595 void 01596 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01597 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01598 _M_rehash(size_type __n, const _RehashPolicyState& __state) 01599 { 01600 __try 01601 { 01602 _M_rehash_aux(__n, integral_constant<bool, __uk>()); 01603 } 01604 __catch(...) 01605 { 01606 // A failure here means that buckets allocation failed. We only 01607 // have to restore hash policy previous state. 01608 _M_rehash_policy._M_reset(__state); 01609 __throw_exception_again; 01610 } 01611 } 01612 01613 // Rehash when there is no equivalent elements. 01614 template<typename _Key, typename _Value, 01615 typename _Allocator, typename _ExtractKey, typename _Equal, 01616 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01617 bool __chc, bool __cit, bool __uk> 01618 void 01619 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01620 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01621 _M_rehash_aux(size_type __n, std::true_type) 01622 { 01623 _Bucket* __new_buckets = _M_allocate_buckets(__n); 01624 _Node* __p = _M_begin(); 01625 _M_before_begin._M_nxt = nullptr; 01626 std::size_t __bbegin_bkt; 01627 while (__p) 01628 { 01629 _Node* __next = __p->_M_next(); 01630 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); 01631 if (!__new_buckets[__bkt]) 01632 { 01633 __p->_M_nxt = _M_before_begin._M_nxt; 01634 _M_before_begin._M_nxt = __p; 01635 __new_buckets[__bkt] = &_M_before_begin; 01636 if (__p->_M_nxt) 01637 __new_buckets[__bbegin_bkt] = __p; 01638 __bbegin_bkt = __bkt; 01639 } 01640 else 01641 { 01642 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 01643 __new_buckets[__bkt]->_M_nxt = __p; 01644 } 01645 __p = __next; 01646 } 01647 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 01648 _M_bucket_count = __n; 01649 _M_buckets = __new_buckets; 01650 } 01651 01652 // Rehash when there can be equivalent elements, preserve their relative 01653 // order. 01654 template<typename _Key, typename _Value, 01655 typename _Allocator, typename _ExtractKey, typename _Equal, 01656 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01657 bool __chc, bool __cit, bool __uk> 01658 void 01659 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01660 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01661 _M_rehash_aux(size_type __n, std::false_type) 01662 { 01663 _Bucket* __new_buckets = _M_allocate_buckets(__n); 01664 01665 _Node* __p = _M_begin(); 01666 _M_before_begin._M_nxt = nullptr; 01667 std::size_t __bbegin_bkt; 01668 std::size_t __prev_bkt; 01669 _Node* __prev_p = nullptr; 01670 bool __check_bucket = false; 01671 01672 while (__p) 01673 { 01674 _Node* __next = __p->_M_next(); 01675 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); 01676 01677 if (__prev_p && __prev_bkt == __bkt) 01678 { 01679 // Previous insert was already in this bucket, we insert after 01680 // the previously inserted one to preserve equivalent elements 01681 // relative order. 01682 __p->_M_nxt = __prev_p->_M_nxt; 01683 __prev_p->_M_nxt = __p; 01684 01685 // Inserting after a node in a bucket require to check that we 01686 // haven't change the bucket last node, in this case next 01687 // bucket containing its before begin node must be updated. We 01688 // schedule a check as soon as we move out of the sequence of 01689 // equivalent nodes to limit the number of checks. 01690 __check_bucket = true; 01691 } 01692 else 01693 { 01694 if (__check_bucket) 01695 { 01696 // Check if we shall update the next bucket because of insertions 01697 // into __prev_bkt bucket. 01698 if (__prev_p->_M_nxt) 01699 { 01700 std::size_t __next_bkt 01701 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); 01702 if (__next_bkt != __prev_bkt) 01703 __new_buckets[__next_bkt] = __prev_p; 01704 } 01705 __check_bucket = false; 01706 } 01707 if (!__new_buckets[__bkt]) 01708 { 01709 __p->_M_nxt = _M_before_begin._M_nxt; 01710 _M_before_begin._M_nxt = __p; 01711 __new_buckets[__bkt] = &_M_before_begin; 01712 if (__p->_M_nxt) 01713 __new_buckets[__bbegin_bkt] = __p; 01714 __bbegin_bkt = __bkt; 01715 } 01716 else 01717 { 01718 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 01719 __new_buckets[__bkt]->_M_nxt = __p; 01720 } 01721 } 01722 01723 __prev_p = __p; 01724 __prev_bkt = __bkt; 01725 __p = __next; 01726 } 01727 01728 if (__check_bucket && __prev_p->_M_nxt) 01729 { 01730 std::size_t __next_bkt 01731 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); 01732 if (__next_bkt != __prev_bkt) 01733 __new_buckets[__next_bkt] = __prev_p; 01734 } 01735 01736 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 01737 _M_bucket_count = __n; 01738 _M_buckets = __new_buckets; 01739 } 01740 01741 _GLIBCXX_END_NAMESPACE_VERSION 01742 } // namespace std 01743 01744 #endif // _HASHTABLE_H