stl_hashtable.h

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

Generated on Wed Sep 29 13:54:51 2004 for libstdc++-v3 Source by doxygen 1.3.7