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 Tue Dec 23 12:34:06 2003 for libstdc++-v3 Source by doxygen 1.3.4