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