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

Generated on Wed Sep 8 10:19:34 2004 for libstdc++-v3 Source by doxygen 1.3.8