# hashtable.h

Go to the documentation of this file.

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