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