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