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

Generated on Sun Sep 19 16:33:59 2004 for libstdc++-v3 Source by doxygen 1.3.8