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