libstdc++
hashtable.h
Go to the documentation of this file.
00001 // Hashtable implementation used by containers -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2015 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