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