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