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