libstdc++
|
00001 // Hashtable implementation used by containers -*- C++ -*- 00002 00003 // Copyright (C) 2001-2013 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 /* 00026 * Copyright (c) 1996,1997 00027 * Silicon Graphics Computer Systems, Inc. 00028 * 00029 * Permission to use, copy, modify, distribute and sell this software 00030 * and its documentation for any purpose is hereby granted without fee, 00031 * provided that the above copyright notice appear in all copies and 00032 * that both that copyright notice and this permission notice appear 00033 * in supporting documentation. Silicon Graphics makes no 00034 * representations about the suitability of this software for any 00035 * purpose. It is provided "as is" without express or implied warranty. 00036 * 00037 * 00038 * Copyright (c) 1994 00039 * Hewlett-Packard Company 00040 * 00041 * Permission to use, copy, modify, distribute and sell this software 00042 * and its documentation for any purpose is hereby granted without fee, 00043 * provided that the above copyright notice appear in all copies and 00044 * that both that copyright notice and this permission notice appear 00045 * in supporting documentation. Hewlett-Packard Company makes no 00046 * representations about the suitability of this software for any 00047 * purpose. It is provided "as is" without express or implied warranty. 00048 * 00049 */ 00050 00051 /** @file backward/hashtable.h 00052 * This file is a GNU extension to the Standard C++ Library (possibly 00053 * containing extensions from the HP/SGI STL subset). 00054 */ 00055 00056 #ifndef _BACKWARD_HASHTABLE_H 00057 #define _BACKWARD_HASHTABLE_H 1 00058 00059 // Hashtable class, used to implement the hashed associative containers 00060 // hash_set, hash_map, hash_multiset, and hash_multimap. 00061 00062 #include <vector> 00063 #include <iterator> 00064 #include <algorithm> 00065 #include <bits/stl_function.h> 00066 #include <backward/hash_fun.h> 00067 00068 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00069 { 00070 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00071 00072 using std::size_t; 00073 using std::ptrdiff_t; 00074 using std::forward_iterator_tag; 00075 using std::input_iterator_tag; 00076 using std::_Construct; 00077 using std::_Destroy; 00078 using std::distance; 00079 using std::vector; 00080 using std::pair; 00081 using std::__iterator_category; 00082 00083 template<class _Val> 00084 struct _Hashtable_node 00085 { 00086 _Hashtable_node* _M_next; 00087 _Val _M_val; 00088 }; 00089 00090 template<class _Val, class _Key, class _HashFcn, class _ExtractKey, 00091 class _EqualKey, class _Alloc = std::allocator<_Val> > 00092 class hashtable; 00093 00094 template<class _Val, class _Key, class _HashFcn, 00095 class _ExtractKey, class _EqualKey, class _Alloc> 00096 struct _Hashtable_iterator; 00097 00098 template<class _Val, class _Key, class _HashFcn, 00099 class _ExtractKey, class _EqualKey, class _Alloc> 00100 struct _Hashtable_const_iterator; 00101 00102 template<class _Val, class _Key, class _HashFcn, 00103 class _ExtractKey, class _EqualKey, class _Alloc> 00104 struct _Hashtable_iterator 00105 { 00106 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 00107 _Hashtable; 00108 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, 00109 _ExtractKey, _EqualKey, _Alloc> 00110 iterator; 00111 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 00112 _ExtractKey, _EqualKey, _Alloc> 00113 const_iterator; 00114 typedef _Hashtable_node<_Val> _Node; 00115 typedef forward_iterator_tag iterator_category; 00116 typedef _Val value_type; 00117 typedef ptrdiff_t difference_type; 00118 typedef size_t size_type; 00119 typedef _Val& reference; 00120 typedef _Val* pointer; 00121 00122 _Node* _M_cur; 00123 _Hashtable* _M_ht; 00124 00125 _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 00126 : _M_cur(__n), _M_ht(__tab) { } 00127 00128 _Hashtable_iterator() { } 00129 00130 reference 00131 operator*() const 00132 { return _M_cur->_M_val; } 00133 00134 pointer 00135 operator->() const 00136 { return &(operator*()); } 00137 00138 iterator& 00139 operator++(); 00140 00141 iterator 00142 operator++(int); 00143 00144 bool 00145 operator==(const iterator& __it) const 00146 { return _M_cur == __it._M_cur; } 00147 00148 bool 00149 operator!=(const iterator& __it) const 00150 { return _M_cur != __it._M_cur; } 00151 }; 00152 00153 template<class _Val, class _Key, class _HashFcn, 00154 class _ExtractKey, class _EqualKey, class _Alloc> 00155 struct _Hashtable_const_iterator 00156 { 00157 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 00158 _Hashtable; 00159 typedef _Hashtable_iterator<_Val,_Key,_HashFcn, 00160 _ExtractKey,_EqualKey,_Alloc> 00161 iterator; 00162 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 00163 _ExtractKey, _EqualKey, _Alloc> 00164 const_iterator; 00165 typedef _Hashtable_node<_Val> _Node; 00166 00167 typedef forward_iterator_tag iterator_category; 00168 typedef _Val value_type; 00169 typedef ptrdiff_t difference_type; 00170 typedef size_t size_type; 00171 typedef const _Val& reference; 00172 typedef const _Val* pointer; 00173 00174 const _Node* _M_cur; 00175 const _Hashtable* _M_ht; 00176 00177 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) 00178 : _M_cur(__n), _M_ht(__tab) { } 00179 00180 _Hashtable_const_iterator() { } 00181 00182 _Hashtable_const_iterator(const iterator& __it) 00183 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { } 00184 00185 reference 00186 operator*() const 00187 { return _M_cur->_M_val; } 00188 00189 pointer 00190 operator->() const 00191 { return &(operator*()); } 00192 00193 const_iterator& 00194 operator++(); 00195 00196 const_iterator 00197 operator++(int); 00198 00199 bool 00200 operator==(const const_iterator& __it) const 00201 { return _M_cur == __it._M_cur; } 00202 00203 bool 00204 operator!=(const const_iterator& __it) const 00205 { return _M_cur != __it._M_cur; } 00206 }; 00207 00208 // Note: assumes long is at least 32 bits. 00209 enum { _S_num_primes = 29 }; 00210 00211 template<typename _PrimeType> 00212 struct _Hashtable_prime_list 00213 { 00214 static const _PrimeType __stl_prime_list[_S_num_primes]; 00215 00216 static const _PrimeType* 00217 _S_get_prime_list(); 00218 }; 00219 00220 template<typename _PrimeType> const _PrimeType 00221 _Hashtable_prime_list<_PrimeType>::__stl_prime_list[_S_num_primes] = 00222 { 00223 5ul, 53ul, 97ul, 193ul, 389ul, 00224 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 00225 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 00226 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 00227 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 00228 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul 00229 }; 00230 00231 template<class _PrimeType> inline const _PrimeType* 00232 _Hashtable_prime_list<_PrimeType>::_S_get_prime_list() 00233 { 00234 return __stl_prime_list; 00235 } 00236 00237 inline unsigned long 00238 __stl_next_prime(unsigned long __n) 00239 { 00240 const unsigned long* __first = _Hashtable_prime_list<unsigned long>::_S_get_prime_list(); 00241 const unsigned long* __last = __first + (int)_S_num_primes; 00242 const unsigned long* pos = std::lower_bound(__first, __last, __n); 00243 return pos == __last ? *(__last - 1) : *pos; 00244 } 00245 00246 // Forward declaration of operator==. 00247 template<class _Val, class _Key, class _HF, class _Ex, 00248 class _Eq, class _All> 00249 class hashtable; 00250 00251 template<class _Val, class _Key, class _HF, class _Ex, 00252 class _Eq, class _All> 00253 bool 00254 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 00255 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2); 00256 00257 // Hashtables handle allocators a bit differently than other 00258 // containers do. If we're using standard-conforming allocators, then 00259 // a hashtable unconditionally has a member variable to hold its 00260 // allocator, even if it so happens that all instances of the 00261 // allocator type are identical. This is because, for hashtables, 00262 // this extra storage is negligible. Additionally, a base class 00263 // wouldn't serve any other purposes; it wouldn't, for example, 00264 // simplify the exception-handling code. 00265 template<class _Val, class _Key, class _HashFcn, 00266 class _ExtractKey, class _EqualKey, class _Alloc> 00267 class hashtable 00268 { 00269 public: 00270 typedef _Key key_type; 00271 typedef _Val value_type; 00272 typedef _HashFcn hasher; 00273 typedef _EqualKey key_equal; 00274 00275 typedef size_t size_type; 00276 typedef ptrdiff_t difference_type; 00277 typedef value_type* pointer; 00278 typedef const value_type* const_pointer; 00279 typedef value_type& reference; 00280 typedef const value_type& const_reference; 00281 00282 hasher 00283 hash_funct() const 00284 { return _M_hash; } 00285 00286 key_equal 00287 key_eq() const 00288 { return _M_equals; } 00289 00290 private: 00291 typedef _Hashtable_node<_Val> _Node; 00292 00293 public: 00294 typedef typename _Alloc::template rebind<value_type>::other allocator_type; 00295 allocator_type 00296 get_allocator() const 00297 { return _M_node_allocator; } 00298 00299 private: 00300 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc; 00301 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc; 00302 typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type; 00303 00304 _Node_Alloc _M_node_allocator; 00305 00306 _Node* 00307 _M_get_node() 00308 { return _M_node_allocator.allocate(1); } 00309 00310 void 00311 _M_put_node(_Node* __p) 00312 { _M_node_allocator.deallocate(__p, 1); } 00313 00314 private: 00315 hasher _M_hash; 00316 key_equal _M_equals; 00317 _ExtractKey _M_get_key; 00318 _Vector_type _M_buckets; 00319 size_type _M_num_elements; 00320 00321 public: 00322 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, 00323 _EqualKey, _Alloc> 00324 iterator; 00325 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 00326 _EqualKey, _Alloc> 00327 const_iterator; 00328 00329 friend struct 00330 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>; 00331 00332 friend struct 00333 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 00334 _EqualKey, _Alloc>; 00335 00336 public: 00337 hashtable(size_type __n, const _HashFcn& __hf, 00338 const _EqualKey& __eql, const _ExtractKey& __ext, 00339 const allocator_type& __a = allocator_type()) 00340 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 00341 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) 00342 { _M_initialize_buckets(__n); } 00343 00344 hashtable(size_type __n, const _HashFcn& __hf, 00345 const _EqualKey& __eql, 00346 const allocator_type& __a = allocator_type()) 00347 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 00348 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) 00349 { _M_initialize_buckets(__n); } 00350 00351 hashtable(const hashtable& __ht) 00352 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash), 00353 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), 00354 _M_buckets(__ht.get_allocator()), _M_num_elements(0) 00355 { _M_copy_from(__ht); } 00356 00357 hashtable& 00358 operator= (const hashtable& __ht) 00359 { 00360 if (&__ht != this) 00361 { 00362 clear(); 00363 _M_hash = __ht._M_hash; 00364 _M_equals = __ht._M_equals; 00365 _M_get_key = __ht._M_get_key; 00366 _M_copy_from(__ht); 00367 } 00368 return *this; 00369 } 00370 00371 ~hashtable() 00372 { clear(); } 00373 00374 size_type 00375 size() const 00376 { return _M_num_elements; } 00377 00378 size_type 00379 max_size() const 00380 { return size_type(-1); } 00381 00382 bool 00383 empty() const 00384 { return size() == 0; } 00385 00386 void 00387 swap(hashtable& __ht) 00388 { 00389 std::swap(_M_hash, __ht._M_hash); 00390 std::swap(_M_equals, __ht._M_equals); 00391 std::swap(_M_get_key, __ht._M_get_key); 00392 _M_buckets.swap(__ht._M_buckets); 00393 std::swap(_M_num_elements, __ht._M_num_elements); 00394 } 00395 00396 iterator 00397 begin() 00398 { 00399 for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 00400 if (_M_buckets[__n]) 00401 return iterator(_M_buckets[__n], this); 00402 return end(); 00403 } 00404 00405 iterator 00406 end() 00407 { return iterator(0, this); } 00408 00409 const_iterator 00410 begin() const 00411 { 00412 for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 00413 if (_M_buckets[__n]) 00414 return const_iterator(_M_buckets[__n], this); 00415 return end(); 00416 } 00417 00418 const_iterator 00419 end() const 00420 { return const_iterator(0, this); } 00421 00422 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, 00423 class _Al> 00424 friend bool 00425 operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, 00426 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); 00427 00428 public: 00429 size_type 00430 bucket_count() const 00431 { return _M_buckets.size(); } 00432 00433 size_type 00434 max_bucket_count() const 00435 { return _Hashtable_prime_list<unsigned long>:: 00436 _S_get_prime_list()[(int)_S_num_primes - 1]; 00437 } 00438 00439 size_type 00440 elems_in_bucket(size_type __bucket) const 00441 { 00442 size_type __result = 0; 00443 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next) 00444 __result += 1; 00445 return __result; 00446 } 00447 00448 pair<iterator, bool> 00449 insert_unique(const value_type& __obj) 00450 { 00451 resize(_M_num_elements + 1); 00452 return insert_unique_noresize(__obj); 00453 } 00454 00455 iterator 00456 insert_equal(const value_type& __obj) 00457 { 00458 resize(_M_num_elements + 1); 00459 return insert_equal_noresize(__obj); 00460 } 00461 00462 pair<iterator, bool> 00463 insert_unique_noresize(const value_type& __obj); 00464 00465 iterator 00466 insert_equal_noresize(const value_type& __obj); 00467 00468 template<class _InputIterator> 00469 void 00470 insert_unique(_InputIterator __f, _InputIterator __l) 00471 { insert_unique(__f, __l, __iterator_category(__f)); } 00472 00473 template<class _InputIterator> 00474 void 00475 insert_equal(_InputIterator __f, _InputIterator __l) 00476 { insert_equal(__f, __l, __iterator_category(__f)); } 00477 00478 template<class _InputIterator> 00479 void 00480 insert_unique(_InputIterator __f, _InputIterator __l, 00481 input_iterator_tag) 00482 { 00483 for ( ; __f != __l; ++__f) 00484 insert_unique(*__f); 00485 } 00486 00487 template<class _InputIterator> 00488 void 00489 insert_equal(_InputIterator __f, _InputIterator __l, 00490 input_iterator_tag) 00491 { 00492 for ( ; __f != __l; ++__f) 00493 insert_equal(*__f); 00494 } 00495 00496 template<class _ForwardIterator> 00497 void 00498 insert_unique(_ForwardIterator __f, _ForwardIterator __l, 00499 forward_iterator_tag) 00500 { 00501 size_type __n = distance(__f, __l); 00502 resize(_M_num_elements + __n); 00503 for ( ; __n > 0; --__n, ++__f) 00504 insert_unique_noresize(*__f); 00505 } 00506 00507 template<class _ForwardIterator> 00508 void 00509 insert_equal(_ForwardIterator __f, _ForwardIterator __l, 00510 forward_iterator_tag) 00511 { 00512 size_type __n = distance(__f, __l); 00513 resize(_M_num_elements + __n); 00514 for ( ; __n > 0; --__n, ++__f) 00515 insert_equal_noresize(*__f); 00516 } 00517 00518 reference 00519 find_or_insert(const value_type& __obj); 00520 00521 iterator 00522 find(const key_type& __key) 00523 { 00524 size_type __n = _M_bkt_num_key(__key); 00525 _Node* __first; 00526 for (__first = _M_buckets[__n]; 00527 __first && !_M_equals(_M_get_key(__first->_M_val), __key); 00528 __first = __first->_M_next) 00529 { } 00530 return iterator(__first, this); 00531 } 00532 00533 const_iterator 00534 find(const key_type& __key) const 00535 { 00536 size_type __n = _M_bkt_num_key(__key); 00537 const _Node* __first; 00538 for (__first = _M_buckets[__n]; 00539 __first && !_M_equals(_M_get_key(__first->_M_val), __key); 00540 __first = __first->_M_next) 00541 { } 00542 return const_iterator(__first, this); 00543 } 00544 00545 size_type 00546 count(const key_type& __key) const 00547 { 00548 const size_type __n = _M_bkt_num_key(__key); 00549 size_type __result = 0; 00550 00551 for (const _Node* __cur = _M_buckets[__n]; __cur; 00552 __cur = __cur->_M_next) 00553 if (_M_equals(_M_get_key(__cur->_M_val), __key)) 00554 ++__result; 00555 return __result; 00556 } 00557 00558 pair<iterator, iterator> 00559 equal_range(const key_type& __key); 00560 00561 pair<const_iterator, const_iterator> 00562 equal_range(const key_type& __key) const; 00563 00564 size_type 00565 erase(const key_type& __key); 00566 00567 void 00568 erase(const iterator& __it); 00569 00570 void 00571 erase(iterator __first, iterator __last); 00572 00573 void 00574 erase(const const_iterator& __it); 00575 00576 void 00577 erase(const_iterator __first, const_iterator __last); 00578 00579 void 00580 resize(size_type __num_elements_hint); 00581 00582 void 00583 clear(); 00584 00585 private: 00586 size_type 00587 _M_next_size(size_type __n) const 00588 { return __stl_next_prime(__n); } 00589 00590 void 00591 _M_initialize_buckets(size_type __n) 00592 { 00593 const size_type __n_buckets = _M_next_size(__n); 00594 _M_buckets.reserve(__n_buckets); 00595 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); 00596 _M_num_elements = 0; 00597 } 00598 00599 size_type 00600 _M_bkt_num_key(const key_type& __key) const 00601 { return _M_bkt_num_key(__key, _M_buckets.size()); } 00602 00603 size_type 00604 _M_bkt_num(const value_type& __obj) const 00605 { return _M_bkt_num_key(_M_get_key(__obj)); } 00606 00607 size_type 00608 _M_bkt_num_key(const key_type& __key, size_t __n) const 00609 { return _M_hash(__key) % __n; } 00610 00611 size_type 00612 _M_bkt_num(const value_type& __obj, size_t __n) const 00613 { return _M_bkt_num_key(_M_get_key(__obj), __n); } 00614 00615 _Node* 00616 _M_new_node(const value_type& __obj) 00617 { 00618 _Node* __n = _M_get_node(); 00619 __n->_M_next = 0; 00620 __try 00621 { 00622 this->get_allocator().construct(&__n->_M_val, __obj); 00623 return __n; 00624 } 00625 __catch(...) 00626 { 00627 _M_put_node(__n); 00628 __throw_exception_again; 00629 } 00630 } 00631 00632 void 00633 _M_delete_node(_Node* __n) 00634 { 00635 this->get_allocator().destroy(&__n->_M_val); 00636 _M_put_node(__n); 00637 } 00638 00639 void 00640 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); 00641 00642 void 00643 _M_erase_bucket(const size_type __n, _Node* __last); 00644 00645 void 00646 _M_copy_from(const hashtable& __ht); 00647 }; 00648 00649 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 00650 class _All> 00651 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 00652 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 00653 operator++() 00654 { 00655 const _Node* __old = _M_cur; 00656 _M_cur = _M_cur->_M_next; 00657 if (!_M_cur) 00658 { 00659 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 00660 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 00661 _M_cur = _M_ht->_M_buckets[__bucket]; 00662 } 00663 return *this; 00664 } 00665 00666 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 00667 class _All> 00668 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 00669 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 00670 operator++(int) 00671 { 00672 iterator __tmp = *this; 00673 ++*this; 00674 return __tmp; 00675 } 00676 00677 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 00678 class _All> 00679 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 00680 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 00681 operator++() 00682 { 00683 const _Node* __old = _M_cur; 00684 _M_cur = _M_cur->_M_next; 00685 if (!_M_cur) 00686 { 00687 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 00688 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 00689 _M_cur = _M_ht->_M_buckets[__bucket]; 00690 } 00691 return *this; 00692 } 00693 00694 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 00695 class _All> 00696 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 00697 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 00698 operator++(int) 00699 { 00700 const_iterator __tmp = *this; 00701 ++*this; 00702 return __tmp; 00703 } 00704 00705 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00706 bool 00707 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 00708 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 00709 { 00710 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node; 00711 00712 if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) 00713 return false; 00714 00715 for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) 00716 { 00717 _Node* __cur1 = __ht1._M_buckets[__n]; 00718 _Node* __cur2 = __ht2._M_buckets[__n]; 00719 // Check same length of lists 00720 for (; __cur1 && __cur2; 00721 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) 00722 { } 00723 if (__cur1 || __cur2) 00724 return false; 00725 // Now check one's elements are in the other 00726 for (__cur1 = __ht1._M_buckets[__n] ; __cur1; 00727 __cur1 = __cur1->_M_next) 00728 { 00729 bool _found__cur1 = false; 00730 for (__cur2 = __ht2._M_buckets[__n]; 00731 __cur2; __cur2 = __cur2->_M_next) 00732 { 00733 if (__cur1->_M_val == __cur2->_M_val) 00734 { 00735 _found__cur1 = true; 00736 break; 00737 } 00738 } 00739 if (!_found__cur1) 00740 return false; 00741 } 00742 } 00743 return true; 00744 } 00745 00746 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00747 inline bool 00748 operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 00749 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 00750 { return !(__ht1 == __ht2); } 00751 00752 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, 00753 class _All> 00754 inline void 00755 swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, 00756 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) 00757 { __ht1.swap(__ht2); } 00758 00759 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00760 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool> 00761 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 00762 insert_unique_noresize(const value_type& __obj) 00763 { 00764 const size_type __n = _M_bkt_num(__obj); 00765 _Node* __first = _M_buckets[__n]; 00766 00767 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 00768 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 00769 return pair<iterator, bool>(iterator(__cur, this), false); 00770 00771 _Node* __tmp = _M_new_node(__obj); 00772 __tmp->_M_next = __first; 00773 _M_buckets[__n] = __tmp; 00774 ++_M_num_elements; 00775 return pair<iterator, bool>(iterator(__tmp, this), true); 00776 } 00777 00778 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00779 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator 00780 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 00781 insert_equal_noresize(const value_type& __obj) 00782 { 00783 const size_type __n = _M_bkt_num(__obj); 00784 _Node* __first = _M_buckets[__n]; 00785 00786 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 00787 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 00788 { 00789 _Node* __tmp = _M_new_node(__obj); 00790 __tmp->_M_next = __cur->_M_next; 00791 __cur->_M_next = __tmp; 00792 ++_M_num_elements; 00793 return iterator(__tmp, this); 00794 } 00795 00796 _Node* __tmp = _M_new_node(__obj); 00797 __tmp->_M_next = __first; 00798 _M_buckets[__n] = __tmp; 00799 ++_M_num_elements; 00800 return iterator(__tmp, this); 00801 } 00802 00803 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00804 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference 00805 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 00806 find_or_insert(const value_type& __obj) 00807 { 00808 resize(_M_num_elements + 1); 00809 00810 size_type __n = _M_bkt_num(__obj); 00811 _Node* __first = _M_buckets[__n]; 00812 00813 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 00814 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 00815 return __cur->_M_val; 00816 00817 _Node* __tmp = _M_new_node(__obj); 00818 __tmp->_M_next = __first; 00819 _M_buckets[__n] = __tmp; 00820 ++_M_num_elements; 00821 return __tmp->_M_val; 00822 } 00823 00824 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00825 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, 00826 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator> 00827 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 00828 equal_range(const key_type& __key) 00829 { 00830 typedef pair<iterator, iterator> _Pii; 00831 const size_type __n = _M_bkt_num_key(__key); 00832 00833 for (_Node* __first = _M_buckets[__n]; __first; 00834 __first = __first->_M_next) 00835 if (_M_equals(_M_get_key(__first->_M_val), __key)) 00836 { 00837 for (_Node* __cur = __first->_M_next; __cur; 00838 __cur = __cur->_M_next) 00839 if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 00840 return _Pii(iterator(__first, this), iterator(__cur, this)); 00841 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 00842 if (_M_buckets[__m]) 00843 return _Pii(iterator(__first, this), 00844 iterator(_M_buckets[__m], this)); 00845 return _Pii(iterator(__first, this), end()); 00846 } 00847 return _Pii(end(), end()); 00848 } 00849 00850 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00851 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator, 00852 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator> 00853 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 00854 equal_range(const key_type& __key) const 00855 { 00856 typedef pair<const_iterator, const_iterator> _Pii; 00857 const size_type __n = _M_bkt_num_key(__key); 00858 00859 for (const _Node* __first = _M_buckets[__n]; __first; 00860 __first = __first->_M_next) 00861 { 00862 if (_M_equals(_M_get_key(__first->_M_val), __key)) 00863 { 00864 for (const _Node* __cur = __first->_M_next; __cur; 00865 __cur = __cur->_M_next) 00866 if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 00867 return _Pii(const_iterator(__first, this), 00868 const_iterator(__cur, this)); 00869 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 00870 if (_M_buckets[__m]) 00871 return _Pii(const_iterator(__first, this), 00872 const_iterator(_M_buckets[__m], this)); 00873 return _Pii(const_iterator(__first, this), end()); 00874 } 00875 } 00876 return _Pii(end(), end()); 00877 } 00878 00879 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00880 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type 00881 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 00882 erase(const key_type& __key) 00883 { 00884 const size_type __n = _M_bkt_num_key(__key); 00885 _Node* __first = _M_buckets[__n]; 00886 _Node* __saved_slot = 0; 00887 size_type __erased = 0; 00888 00889 if (__first) 00890 { 00891 _Node* __cur = __first; 00892 _Node* __next = __cur->_M_next; 00893 while (__next) 00894 { 00895 if (_M_equals(_M_get_key(__next->_M_val), __key)) 00896 { 00897 if (&_M_get_key(__next->_M_val) != &__key) 00898 { 00899 __cur->_M_next = __next->_M_next; 00900 _M_delete_node(__next); 00901 __next = __cur->_M_next; 00902 ++__erased; 00903 --_M_num_elements; 00904 } 00905 else 00906 { 00907 __saved_slot = __cur; 00908 __cur = __next; 00909 __next = __cur->_M_next; 00910 } 00911 } 00912 else 00913 { 00914 __cur = __next; 00915 __next = __cur->_M_next; 00916 } 00917 } 00918 bool __delete_first = _M_equals(_M_get_key(__first->_M_val), __key); 00919 if (__saved_slot) 00920 { 00921 __next = __saved_slot->_M_next; 00922 __saved_slot->_M_next = __next->_M_next; 00923 _M_delete_node(__next); 00924 ++__erased; 00925 --_M_num_elements; 00926 } 00927 if (__delete_first) 00928 { 00929 _M_buckets[__n] = __first->_M_next; 00930 _M_delete_node(__first); 00931 ++__erased; 00932 --_M_num_elements; 00933 } 00934 } 00935 return __erased; 00936 } 00937 00938 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00939 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 00940 erase(const iterator& __it) 00941 { 00942 _Node* __p = __it._M_cur; 00943 if (__p) 00944 { 00945 const size_type __n = _M_bkt_num(__p->_M_val); 00946 _Node* __cur = _M_buckets[__n]; 00947 00948 if (__cur == __p) 00949 { 00950 _M_buckets[__n] = __cur->_M_next; 00951 _M_delete_node(__cur); 00952 --_M_num_elements; 00953 } 00954 else 00955 { 00956 _Node* __next = __cur->_M_next; 00957 while (__next) 00958 { 00959 if (__next == __p) 00960 { 00961 __cur->_M_next = __next->_M_next; 00962 _M_delete_node(__next); 00963 --_M_num_elements; 00964 break; 00965 } 00966 else 00967 { 00968 __cur = __next; 00969 __next = __cur->_M_next; 00970 } 00971 } 00972 } 00973 } 00974 } 00975 00976 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 00977 void 00978 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 00979 erase(iterator __first, iterator __last) 00980 { 00981 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) 00982 : _M_buckets.size(); 00983 00984 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) 00985 : _M_buckets.size(); 00986 00987 if (__first._M_cur == __last._M_cur) 00988 return; 00989 else if (__f_bucket == __l_bucket) 00990 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); 00991 else 00992 { 00993 _M_erase_bucket(__f_bucket, __first._M_cur, 0); 00994 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) 00995 _M_erase_bucket(__n, 0); 00996 if (__l_bucket != _M_buckets.size()) 00997 _M_erase_bucket(__l_bucket, __last._M_cur); 00998 } 00999 } 01000 01001 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 01002 inline void 01003 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 01004 erase(const_iterator __first, const_iterator __last) 01005 { 01006 erase(iterator(const_cast<_Node*>(__first._M_cur), 01007 const_cast<hashtable*>(__first._M_ht)), 01008 iterator(const_cast<_Node*>(__last._M_cur), 01009 const_cast<hashtable*>(__last._M_ht))); 01010 } 01011 01012 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 01013 inline void 01014 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 01015 erase(const const_iterator& __it) 01016 { erase(iterator(const_cast<_Node*>(__it._M_cur), 01017 const_cast<hashtable*>(__it._M_ht))); } 01018 01019 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 01020 void 01021 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 01022 resize(size_type __num_elements_hint) 01023 { 01024 const size_type __old_n = _M_buckets.size(); 01025 if (__num_elements_hint > __old_n) 01026 { 01027 const size_type __n = _M_next_size(__num_elements_hint); 01028 if (__n > __old_n) 01029 { 01030 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator()); 01031 __try 01032 { 01033 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) 01034 { 01035 _Node* __first = _M_buckets[__bucket]; 01036 while (__first) 01037 { 01038 size_type __new_bucket = _M_bkt_num(__first->_M_val, 01039 __n); 01040 _M_buckets[__bucket] = __first->_M_next; 01041 __first->_M_next = __tmp[__new_bucket]; 01042 __tmp[__new_bucket] = __first; 01043 __first = _M_buckets[__bucket]; 01044 } 01045 } 01046 _M_buckets.swap(__tmp); 01047 } 01048 __catch(...) 01049 { 01050 for (size_type __bucket = 0; __bucket < __tmp.size(); 01051 ++__bucket) 01052 { 01053 while (__tmp[__bucket]) 01054 { 01055 _Node* __next = __tmp[__bucket]->_M_next; 01056 _M_delete_node(__tmp[__bucket]); 01057 __tmp[__bucket] = __next; 01058 } 01059 } 01060 __throw_exception_again; 01061 } 01062 } 01063 } 01064 } 01065 01066 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 01067 void 01068 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 01069 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) 01070 { 01071 _Node* __cur = _M_buckets[__n]; 01072 if (__cur == __first) 01073 _M_erase_bucket(__n, __last); 01074 else 01075 { 01076 _Node* __next; 01077 for (__next = __cur->_M_next; 01078 __next != __first; 01079 __cur = __next, __next = __cur->_M_next) 01080 ; 01081 while (__next != __last) 01082 { 01083 __cur->_M_next = __next->_M_next; 01084 _M_delete_node(__next); 01085 __next = __cur->_M_next; 01086 --_M_num_elements; 01087 } 01088 } 01089 } 01090 01091 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 01092 void 01093 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 01094 _M_erase_bucket(const size_type __n, _Node* __last) 01095 { 01096 _Node* __cur = _M_buckets[__n]; 01097 while (__cur != __last) 01098 { 01099 _Node* __next = __cur->_M_next; 01100 _M_delete_node(__cur); 01101 __cur = __next; 01102 _M_buckets[__n] = __cur; 01103 --_M_num_elements; 01104 } 01105 } 01106 01107 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 01108 void 01109 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 01110 clear() 01111 { 01112 if (_M_num_elements == 0) 01113 return; 01114 01115 for (size_type __i = 0; __i < _M_buckets.size(); ++__i) 01116 { 01117 _Node* __cur = _M_buckets[__i]; 01118 while (__cur != 0) 01119 { 01120 _Node* __next = __cur->_M_next; 01121 _M_delete_node(__cur); 01122 __cur = __next; 01123 } 01124 _M_buckets[__i] = 0; 01125 } 01126 _M_num_elements = 0; 01127 } 01128 01129 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 01130 void 01131 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 01132 _M_copy_from(const hashtable& __ht) 01133 { 01134 _M_buckets.clear(); 01135 _M_buckets.reserve(__ht._M_buckets.size()); 01136 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); 01137 __try 01138 { 01139 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { 01140 const _Node* __cur = __ht._M_buckets[__i]; 01141 if (__cur) 01142 { 01143 _Node* __local_copy = _M_new_node(__cur->_M_val); 01144 _M_buckets[__i] = __local_copy; 01145 01146 for (_Node* __next = __cur->_M_next; 01147 __next; 01148 __cur = __next, __next = __cur->_M_next) 01149 { 01150 __local_copy->_M_next = _M_new_node(__next->_M_val); 01151 __local_copy = __local_copy->_M_next; 01152 } 01153 } 01154 } 01155 _M_num_elements = __ht._M_num_elements; 01156 } 01157 __catch(...) 01158 { 01159 clear(); 01160 __throw_exception_again; 01161 } 01162 } 01163 01164 _GLIBCXX_END_NAMESPACE_VERSION 01165 } // namespace 01166 01167 #endif