home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _hashtable.h < prev    next >
C/C++ Source or Header  |  2002-01-10  |  19KB  |  632 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Copyright (c) 1996,1997
  7.  * Silicon Graphics Computer Systems, Inc.
  8.  *
  9.  * Copyright (c) 1997
  10.  * Moscow Center for SPARC Technology
  11.  *
  12.  * Copyright (c) 1999 
  13.  * Boris Fomitchev
  14.  *
  15.  * This material is provided "as is", with absolutely no warranty expressed
  16.  * or implied. Any use is at your own risk.
  17.  *
  18.  * Permission to use or copy this software for any purpose is hereby granted 
  19.  * without fee, provided the above notices are retained on all copies.
  20.  * Permission to modify the code and to distribute modified code is granted,
  21.  * provided the above notices are retained, and a notice that the code was
  22.  * modified is included with the above copyright notice.
  23.  *
  24.  */
  25.  
  26. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29.  
  30. #ifndef _STLP_INTERNAL_HASHTABLE_H
  31. #define _STLP_INTERNAL_HASHTABLE_H
  32.  
  33. # ifndef _STLP_INTERNAL_VECTOR_H
  34. #  include <stl/_vector.h>
  35. # endif
  36.  
  37. # ifndef _STLP_INTERNAL_ITERATOR_H
  38. #  include <stl/_iterator.h>
  39. # endif
  40.  
  41. # ifndef _STLP_INTERNAL_FUNCTION_H
  42. #  include <stl/_function_base.h>
  43. # endif
  44.  
  45. # ifndef _STLP_INTERNAL_ALGOBASE_H
  46. #  include <stl/_algobase.h>
  47. # endif
  48.  
  49. # ifndef _STLP_HASH_FUN_H
  50. #  include <stl/_hash_fun.h>
  51. # endif
  52.  
  53. // Hashtable class, used to implement the hashed associative containers
  54. // hash_set, hash_map, hash_multiset, and hash_multimap.
  55.  
  56. #ifdef _STLP_DEBUG
  57. #  define hashtable __WORKAROUND_DBG_RENAME(hashtable)
  58. #endif
  59.  
  60. _STLP_BEGIN_NAMESPACE
  61.  
  62. template <class _Val>
  63. struct _Hashtable_node
  64. {
  65.   typedef _Hashtable_node<_Val> _Self;
  66.   _Self* _M_next;
  67.   _Val _M_val;
  68.   __TRIVIAL_STUFF(_Hashtable_node)
  69. };  
  70.  
  71. // some compilers require the names of template parameters to be the same
  72. template <class _Val, class _Key, class _HF,
  73.           class _ExK, class _EqK, class _All>
  74. class hashtable;
  75.  
  76. template <class _Val, class _Key, class _HF,
  77.           class _ExK, class _EqK, class _All>
  78. struct _Hashtable_iterator
  79. {
  80.   typedef hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  81.           _Hashtable;
  82.   typedef _Hashtable_node<_Val> _Node;
  83.  
  84.   _Node* _M_cur;
  85.   _Hashtable* _M_ht;
  86.  
  87.   _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 
  88.     : _M_cur(__n), _M_ht(__tab) {}
  89.   _Hashtable_iterator() {}
  90.  
  91.   _Node* _M_skip_to_next();
  92. };
  93.  
  94.  
  95. template <class _Val, class _Traits, class _Key, class _HF,
  96.           class _ExK, class _EqK, class _All>
  97. struct _Ht_iterator : public _Hashtable_iterator< _Val, _Key,_HF, _ExK,_EqK,_All>
  98. {
  99.   
  100.   typedef _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> _Base;
  101.  
  102.   //  typedef _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All> iterator;
  103.   //  typedef _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All> const_iterator;
  104.   typedef _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All> _Self;
  105.  
  106.   typedef hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> _Hashtable;
  107.   typedef _Hashtable_node<_Val> _Node;
  108.  
  109.   typedef _Val value_type;
  110.   typedef forward_iterator_tag iterator_category;
  111.   typedef ptrdiff_t difference_type;
  112.   typedef size_t size_type;
  113.   typedef typename _Traits::reference reference;
  114.   typedef typename _Traits::pointer   pointer;
  115.  
  116.   _Ht_iterator(const _Node* __n, const _Hashtable* __tab) :
  117.     _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>((_Node*)__n, (_Hashtable*)__tab) {}
  118.   _Ht_iterator() {}
  119.   _Ht_iterator(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __it) : 
  120.     _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>(__it) {}
  121.  
  122.   reference operator*() const { 
  123.       return this->_M_cur->_M_val; 
  124.   }
  125.   _STLP_DEFINE_ARROW_OPERATOR
  126.  
  127.   _Self& operator++() {
  128.     _Node* __n = this->_M_cur->_M_next;
  129.     this->_M_cur =  (__n !=0 ? __n : this->_M_skip_to_next());
  130.     return *this;
  131.   }
  132.   inline  _Self operator++(int) {
  133.      _Self __tmp = *this;
  134.     ++*this;
  135.     return __tmp;
  136.   }
  137. };
  138.  
  139. template <class _Val, class _Traits, class _Traits1, class _Key, class _HF,
  140.           class _ExK, class _EqK, class _All>
  141. inline bool 
  142. operator==(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>& __x, 
  143.        const _Ht_iterator<_Val, _Traits1,_Key,_HF,_ExK,_EqK,_All>& __y) { 
  144.   return __x._M_cur == __y._M_cur; 
  145. }
  146.  
  147. #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
  148. template <class _Val, class _Key, class _HF,
  149.           class _ExK, class _EqK, class _All>
  150. inline bool 
  151. operator!=(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& __x, 
  152.        const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& __y) { 
  153.   return __x._M_cur != __y._M_cur; 
  154. }
  155. #else
  156.  
  157. # if (defined (__GNUC__) && (__GNUC_MINOR__ < 8))
  158. template <class _Val, class _Key, class _HF,
  159.           class _ExK, class _EqK, class _All>
  160. inline bool
  161. operator!=(const _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __x,
  162.            const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __y) {
  163.   return __x._M_cur != __y._M_cur;
  164. }
  165. # endif
  166.  
  167. template <class _Val, class _Key, class _HF,
  168.           class _ExK, class _EqK, class _All>
  169. inline bool 
  170. operator!=(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __x, 
  171.        const _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __y) { 
  172.   return __x._M_cur != __y._M_cur; 
  173. }
  174. #endif
  175.  
  176. # ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
  177. template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
  178. inline _Val* value_type(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (_Val*) 0; }
  179. template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
  180. inline forward_iterator_tag iterator_category(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return forward_iterator_tag(); }
  181. template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
  182. inline ptrdiff_t* distance_type(const _Ht_iterator<_Val,_Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (ptrdiff_t*) 0; }
  183. #endif
  184.  
  185. #define __stl_num_primes  28
  186. template <class _Tp>
  187. class _Stl_prime {
  188. public:
  189.   static const size_t _M_list[__stl_num_primes];
  190. };
  191.  
  192. # if defined (_STLP_USE_TEMPLATE_EXPORT) 
  193. _STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>;
  194. # endif
  195.  
  196. typedef _Stl_prime<bool> _Stl_prime_type;
  197.  
  198.  
  199. // Hashtables handle allocators a bit differently than other containers
  200. //  do.  If we're using standard-conforming allocators, then a hashtable
  201. //  unconditionally has a member variable to hold its allocator, even if
  202. //  it so happens that all instances of the allocator type are identical.
  203. // This is because, for hashtables, this extra storage is negligible.  
  204. //  Additionally, a base class wouldn't serve any other purposes; it 
  205. //  wouldn't, for example, simplify the exception-handling code.
  206. template <class _Val, class _Key, class _HF,
  207.           class _ExK, class _EqK, class _All>
  208. class hashtable {
  209.   typedef hashtable<_Val, _Key, _HF, _ExK, _EqK, _All> _Self;
  210. public:
  211.   typedef _Key key_type;
  212.   typedef _Val value_type;
  213.   typedef _HF hasher;
  214.   typedef _EqK key_equal;
  215.  
  216.   typedef size_t            size_type;
  217.   typedef ptrdiff_t         difference_type;
  218.   typedef value_type*       pointer;
  219.   typedef const value_type* const_pointer;
  220.   typedef value_type&       reference;
  221.   typedef const value_type& const_reference;
  222.   typedef forward_iterator_tag _Iterator_category;
  223.  
  224.   hasher hash_funct() const { return _M_hash; }
  225.   key_equal key_eq() const { return _M_equals; }
  226.  
  227. private:
  228.   typedef _Hashtable_node<_Val> _Node;
  229.  
  230. private:
  231.   _STLP_FORCE_ALLOCATORS(_Val, _All)
  232.   typedef typename _Alloc_traits<_Node, _All>::allocator_type _M_node_allocator_type;
  233.   typedef typename _Alloc_traits<void*, _All>::allocator_type _M_node_ptr_allocator_type;
  234.   typedef __vector__<void*, _M_node_ptr_allocator_type> _BucketVector;
  235. public:
  236.   typedef typename _Alloc_traits<_Val,_All>::allocator_type allocator_type;
  237.   allocator_type get_allocator() const { 
  238.     return _STLP_CONVERT_ALLOCATOR((const _M_node_allocator_type&)_M_num_elements, _Val); 
  239.   }
  240. private:
  241.   hasher                _M_hash;
  242.   key_equal             _M_equals;
  243.   _ExK                  _M_get_key;
  244.   _BucketVector         _M_buckets;
  245.   _STLP_alloc_proxy<size_type, _Node, _M_node_allocator_type>  _M_num_elements;
  246.   const _Node* _M_get_bucket(size_t __n) const { return (_Node*)_M_buckets[__n]; }
  247.  
  248. public:
  249.   typedef _Const_traits<_Val> __const_val_traits;
  250.   typedef _Nonconst_traits<_Val> __nonconst_val_traits;
  251.   typedef _Ht_iterator<_Val, __const_val_traits,_Key,_HF,_ExK,_EqK, _All> const_iterator;
  252.   typedef _Ht_iterator<_Val, __nonconst_val_traits,_Key,_HF,_ExK,_EqK,_All> iterator;
  253.   friend struct _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>;
  254.   friend struct _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>;
  255.   friend struct _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK, _All>;
  256.  
  257. public:
  258.   hashtable(size_type __n,
  259.             const _HF&  __hf,
  260.             const _EqK& __eql,
  261.             const _ExK& __ext,
  262.             const allocator_type& __a = allocator_type())
  263.     :
  264.       _M_hash(__hf),
  265.       _M_equals(__eql),
  266.       _M_get_key(__ext),
  267.       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a,void*)),
  268.       _M_num_elements(_STLP_CONVERT_ALLOCATOR(__a,_Node), (size_type)0)
  269.   {
  270.     _M_initialize_buckets(__n);
  271.   }
  272.  
  273.   hashtable(size_type __n,
  274.             const _HF&    __hf,
  275.             const _EqK&   __eql,
  276.             const allocator_type& __a = allocator_type())
  277.     :
  278.       _M_hash(__hf),
  279.       _M_equals(__eql),
  280.       _M_get_key(_ExK()),
  281.       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a,void*)),
  282.       _M_num_elements(_STLP_CONVERT_ALLOCATOR(__a,_Node), (size_type)0)
  283.   {
  284.     _M_initialize_buckets(__n);
  285.   }
  286.  
  287.   hashtable(const _Self& __ht)
  288.     :
  289.       _M_hash(__ht._M_hash),
  290.       _M_equals(__ht._M_equals),
  291.       _M_get_key(__ht._M_get_key),
  292.       _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(),void*)),
  293.       _M_num_elements((const _M_node_allocator_type&)__ht._M_num_elements, (size_type)0)
  294.   {
  295.     _M_copy_from(__ht);
  296.   }
  297.  
  298.   _Self& operator= (const _Self& __ht)
  299.   {
  300.     if (&__ht != this) {
  301.       clear();
  302.       _M_hash = __ht._M_hash;
  303.       _M_equals = __ht._M_equals;
  304.       _M_get_key = __ht._M_get_key;
  305.       _M_copy_from(__ht);
  306.     }
  307.     return *this;
  308.   }
  309.  
  310.   ~hashtable() { clear(); }
  311.  
  312.   size_type size() const { return _M_num_elements._M_data; }
  313.   size_type max_size() const { return size_type(-1); }
  314.   bool empty() const { return size() == 0; }
  315.  
  316.   void swap(_Self& __ht)
  317.   {
  318.     _STLP_STD::swap(_M_hash, __ht._M_hash);
  319.     _STLP_STD::swap(_M_equals, __ht._M_equals);
  320.     _STLP_STD::swap(_M_get_key, __ht._M_get_key);
  321.     _M_buckets.swap(__ht._M_buckets);
  322.     _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
  323.   }
  324.  
  325.   iterator begin()
  326.   { 
  327.     for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
  328.       if (_M_buckets[__n])
  329.         return iterator((_Node*)_M_buckets[__n], this);
  330.     return end();
  331.   }
  332.  
  333.   iterator end() { return iterator((_Node*)0, this); }
  334.  
  335.   const_iterator begin() const
  336.   {
  337.     for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
  338.       if (_M_buckets[__n])
  339.         return const_iterator((_Node*)_M_buckets[__n], this);
  340.     return end();
  341.   }
  342.  
  343.   const_iterator end() const { return const_iterator((_Node*)0, this); }
  344.  
  345.   static bool _STLP_CALL _M_equal (const hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>&,
  346.             const hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>&);
  347.  
  348. public:
  349.  
  350.   size_type bucket_count() const { return _M_buckets.size(); }
  351.  
  352.   size_type max_bucket_count() const
  353.     { return _Stl_prime_type::_M_list[(int)__stl_num_primes - 1]; } 
  354.  
  355.   size_type elems_in_bucket(size_type __bucket) const
  356.   {
  357.     size_type __result = 0;
  358.     for (_Node* __cur = (_Node*)_M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
  359.       __result += 1;
  360.     return __result;
  361.   }
  362.  
  363.   pair<iterator, bool> insert_unique(const value_type& __obj)
  364.   {
  365.     resize(_M_num_elements._M_data + 1);
  366.     return insert_unique_noresize(__obj);
  367.   }
  368.  
  369.   iterator insert_equal(const value_type& __obj)
  370.   {
  371.     resize(_M_num_elements._M_data + 1);
  372.     return insert_equal_noresize(__obj);
  373.   }
  374.  
  375.   pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
  376.   iterator insert_equal_noresize(const value_type& __obj);
  377.  
  378. #ifdef _STLP_MEMBER_TEMPLATES
  379.   template <class _InputIterator>
  380.   void insert_unique(_InputIterator __f, _InputIterator __l)
  381.   {
  382.     insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator));
  383.   }
  384.  
  385.   template <class _InputIterator>
  386.   void insert_equal(_InputIterator __f, _InputIterator __l)
  387.   {
  388.     insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator));
  389.   }
  390.  
  391.   template <class _InputIterator>
  392.   void insert_unique(_InputIterator __f, _InputIterator __l,
  393.                      const input_iterator_tag &)
  394.   {
  395.     for ( ; __f != __l; ++__f)
  396.       insert_unique(*__f);
  397.   }
  398.  
  399.   template <class _InputIterator>
  400.   void insert_equal(_InputIterator __f, _InputIterator __l,
  401.                     const input_iterator_tag &)
  402.   {
  403.     for ( ; __f != __l; ++__f)
  404.       insert_equal(*__f);
  405.   }
  406.  
  407.   template <class _ForwardIterator>
  408.   void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
  409.                      const forward_iterator_tag &)
  410.   {
  411.     size_type __n = distance(__f, __l);
  412.     resize(_M_num_elements._M_data + __n);
  413.     for ( ; __n > 0; --__n, ++__f)
  414.       insert_unique_noresize(*__f);
  415.   }
  416.  
  417.   template <class _ForwardIterator>
  418.   void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
  419.                     const forward_iterator_tag &)
  420.   {
  421.     size_type __n = distance(__f, __l);
  422.     resize(_M_num_elements._M_data + __n);
  423.     for ( ; __n > 0; --__n, ++__f)
  424.       insert_equal_noresize(*__f);
  425.   }
  426.  
  427. #else /* _STLP_MEMBER_TEMPLATES */
  428.   void insert_unique(const value_type* __f, const value_type* __l)
  429.   {
  430.     size_type __n = __l - __f;
  431.     resize(_M_num_elements._M_data + __n);
  432.     for ( ; __n > 0; --__n, ++__f)
  433.       insert_unique_noresize(*__f);
  434.   }
  435.  
  436.   void insert_equal(const value_type* __f, const value_type* __l)
  437.   {
  438.     size_type __n = __l - __f;
  439.     resize(_M_num_elements._M_data + __n);
  440.     for ( ; __n > 0; --__n, ++__f)
  441.       insert_equal_noresize(*__f);
  442.   }
  443.  
  444.   void insert_unique(const_iterator __f, const_iterator __l)
  445.   {
  446.     size_type __n = distance(__f, __l);
  447.     resize(_M_num_elements._M_data + __n);
  448.     for ( ; __n > 0; --__n, ++__f)
  449.       insert_unique_noresize(*__f);
  450.   }
  451.  
  452.   void insert_equal(const_iterator __f, const_iterator __l)
  453.   {
  454.     size_type __n = distance(__f, __l);
  455.     resize(_M_num_elements._M_data + __n);
  456.     for ( ; __n > 0; --__n, ++__f)
  457.       insert_equal_noresize(*__f);
  458.   }
  459. #endif /*_STLP_MEMBER_TEMPLATES */
  460.  
  461.   reference find_or_insert(const value_type& __obj);
  462.  
  463. private:
  464. # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )  && !(defined(__MRC__)||defined(__SC__))
  465.   template <class _KT> 
  466.    _Node* _M_find(const _KT& __key) const
  467. # else
  468.    _Node* _M_find(const key_type& __key) const
  469. # endif
  470.   {
  471.     size_type __n = _M_hash(__key)% _M_buckets.size();
  472.     _Node* __first;
  473.     for ( __first = (_Node*)_M_buckets[__n];
  474.           __first && !_M_equals(_M_get_key(__first->_M_val), __key);
  475.           __first = __first->_M_next)
  476.       {}
  477.     return __first;
  478.   } 
  479.  
  480. public:
  481. # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )  && !(defined(__MRC__)||defined(__SC__))
  482.   template <class _KT> 
  483.   iterator find(const _KT& __key) 
  484. # else
  485.   iterator find(const key_type& __key) 
  486. # endif
  487.   {
  488.     return iterator(_M_find(__key), this);
  489.   } 
  490.  
  491. # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )  && !(defined(__MRC__)||defined(__SC__))
  492.   template <class _KT> 
  493.   const_iterator find(const _KT& __key) const
  494. # else
  495.   const_iterator find(const key_type& __key) const
  496. # endif
  497.   {
  498.     return const_iterator(_M_find(__key), this);
  499.   } 
  500.  
  501.   size_type count(const key_type& __key) const
  502.   {
  503.     const size_type __n = _M_bkt_num_key(__key);
  504.     size_type __result = 0;
  505.  
  506.     for (const _Node* __cur = (_Node*)_M_buckets[__n]; __cur; __cur = __cur->_M_next)
  507.       if (_M_equals(_M_get_key(__cur->_M_val), __key))
  508.         ++__result;
  509.     return __result;
  510.   }
  511.  
  512.   pair<iterator, iterator> 
  513.   equal_range(const key_type& __key);
  514.  
  515.   pair<const_iterator, const_iterator> 
  516.   equal_range(const key_type& __key) const;
  517.  
  518.   size_type erase(const key_type& __key);
  519.   //   void erase(const iterator& __it); `
  520.   void erase(const const_iterator& __it) ;
  521.  
  522.   //  void erase(const const_iterator& __first, const const_iterator __last) {
  523.   //     erase((const iterator&)__first, (const iterator&)__last);
  524.   //  }
  525.   void erase(const_iterator __first, const_iterator __last);
  526.   void resize(size_type __num_elements_hint);
  527.   void clear();
  528.  
  529. public:
  530.   // this is for hash_map::operator[]
  531.   reference _M_insert(const value_type& __obj);
  532.  
  533. private:
  534.  
  535.   size_type _M_next_size(size_type __n) const;
  536.  
  537.   void _M_initialize_buckets(size_type __n)
  538.   {
  539.     const size_type __n_buckets = _M_next_size(__n);
  540.     _M_buckets.reserve(__n_buckets);
  541.     _M_buckets.insert(_M_buckets.end(), __n_buckets, (void*) 0);
  542.     _M_num_elements._M_data = 0;
  543.   }
  544.  
  545.   size_type _M_bkt_num_key(const key_type& __key) const
  546.   {
  547.     return _M_bkt_num_key(__key, _M_buckets.size());
  548.   }
  549.  
  550.   size_type _M_bkt_num(const value_type& __obj) const
  551.   {
  552.     return _M_bkt_num_key(_M_get_key(__obj));
  553.   }
  554.  
  555.   size_type _M_bkt_num_key(const key_type& __key, size_t __n) const
  556.   {
  557.     return _M_hash(__key) % __n;
  558.   }
  559.  
  560.   size_type _M_bkt_num(const value_type& __obj, size_t __n) const
  561.   {
  562.     return _M_bkt_num_key(_M_get_key(__obj), __n);
  563.   }
  564.  
  565.   _Node* _M_new_node(const value_type& __obj)
  566.   {
  567.     _Node* __n = _M_num_elements.allocate(1);
  568.     __n->_M_next = 0;
  569.     _STLP_TRY {
  570.       _Construct(&__n->_M_val, __obj);
  571.       //      return __n;
  572.     }
  573.     _STLP_UNWIND(_M_num_elements.deallocate(__n, 1));
  574.     return __n;
  575.   }
  576.   
  577.   void _M_delete_node(_Node* __n)
  578.   {
  579.     _Destroy(&__n->_M_val);
  580.     _M_num_elements.deallocate(__n, 1);
  581.   }
  582.  
  583.   void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
  584.   void _M_erase_bucket(const size_type __n, _Node* __last);
  585.  
  586.   void _M_copy_from(const _Self& __ht);
  587. };
  588.  
  589. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  590. inline bool _STLP_CALL operator==(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht1,
  591.                        const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht2)
  592. {
  593.   return hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_equal( __ht1, __ht2 );
  594. }
  595.  
  596. #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
  597.  
  598. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  599. inline bool _STLP_CALL operator!=(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
  600.                        const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) {
  601.   return !(__ht1 == __ht2);
  602. }
  603.  
  604. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  605.           class _All>
  606. inline void _STLP_CALL swap(hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>& __ht1,
  607.                  hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>& __ht2) {
  608.   __ht1.swap(__ht2);
  609. }
  610.  
  611. #endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
  612.  
  613. _STLP_END_NAMESPACE
  614.  
  615. # undef hashtable
  616.  
  617. # if !defined (_STLP_LINK_TIME_INSTANTIATION)
  618. #  include <stl/_hashtable.c>
  619. # endif
  620.  
  621. # if defined (_STLP_DEBUG)
  622. #  include <stl/debug/_hashtable.h>
  623. # endif
  624.  
  625. #endif /* _STLP_INTERNAL_HASHTABLE_H */
  626.  
  627. // Local Variables:
  628. // mode:C++
  629. // End:
  630.  
  631.  
  632.