hashtable.h

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

Generated on Sun Sep 12 15:49:57 2004 for libstdc++ source by doxygen 1.3.8