Back to index

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