- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_hashtable.h

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