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

Generated on Thu Nov 1 17:35:58 2007 for libstdc++ by  doxygen 1.5.1