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

Generated on Thu Jul 23 21:16:08 2009 for libstdc++ by  doxygen 1.5.8