stl_hash.h
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:32k
源码类别:

STL

开发平台:

Visual C++

  1. /*
  2.  * Copyright (c) 1996,1997
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  *
  13.  *
  14.  * Copyright (c) 1994
  15.  * Hewlett-Packard Company
  16.  *
  17.  * Permission to use, copy, modify, distribute and sell this software
  18.  * and its documentation for any purpose is hereby granted without fee,
  19.  * provided that the above copyright notice appear in all copies and
  20.  * that both that copyright notice and this permission notice appear
  21.  * in supporting documentation.  Hewlett-Packard Company makes no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied warranty.
  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. #ifndef __SGI_STL_INTERNAL_HASHTABLE_H
  30. #define __SGI_STL_INTERNAL_HASHTABLE_H
  31. // Hashtable class, used to implement the hashed associative containers
  32. // hash_set, hash_map, hash_multiset, and hash_multimap.
  33. #include <stl_algobase.h>
  34. #include <stl_alloc.h>
  35. #include <stl_construct.h>
  36. #include <stl_tempbuf.h>
  37. #include <stl_algo.h>
  38. #include <stl_uninitialized.h>
  39. #include <stl_function.h>
  40. #include <stl_vector.h>
  41. #include <stl_hash_fun.h>
  42. __STL_BEGIN_NAMESPACE
  43. template <class _Val>
  44. struct _Hashtable_node
  45. {
  46.   _Hashtable_node* _M_next;
  47.   _Val _M_val;
  48. };  
  49. template <class _Val, class _Key, class _HashFcn,
  50.           class _ExtractKey, class _EqualKey, class _Alloc = alloc>
  51. class hashtable;
  52. template <class _Val, class _Key, class _HashFcn,
  53.           class _ExtractKey, class _EqualKey, class _Alloc>
  54. struct _Hashtable_iterator;
  55. template <class _Val, class _Key, class _HashFcn,
  56.           class _ExtractKey, class _EqualKey, class _Alloc>
  57. struct _Hashtable_const_iterator;
  58. template <class _Val, class _Key, class _HashFcn,
  59.           class _ExtractKey, class _EqualKey, class _Alloc>
  60. struct _Hashtable_iterator {
  61.   typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
  62.           _Hashtable;
  63.   typedef _Hashtable_iterator<_Val, _Key, _HashFcn, 
  64.                               _ExtractKey, _EqualKey, _Alloc>
  65.           iterator;
  66.   typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 
  67.                                     _ExtractKey, _EqualKey, _Alloc>
  68.           const_iterator;
  69.   typedef _Hashtable_node<_Val> _Node;
  70.   typedef forward_iterator_tag iterator_category;
  71.   typedef _Val value_type;
  72.   typedef ptrdiff_t difference_type;
  73.   typedef size_t size_type;
  74.   typedef _Val& reference;
  75.   typedef _Val* pointer;
  76.   _Node* _M_cur;
  77.   _Hashtable* _M_ht;
  78.   _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 
  79.     : _M_cur(__n), _M_ht(__tab) {}
  80.   _Hashtable_iterator() {}
  81.   reference operator*() const { return _M_cur->_M_val; }
  82. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  83.   pointer operator->() const { return &(operator*()); }
  84. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  85.   iterator& operator++();
  86.   iterator operator++(int);
  87.   bool operator==(const iterator& __it) const
  88.     { return _M_cur == __it._M_cur; }
  89.   bool operator!=(const iterator& __it) const
  90.     { return _M_cur != __it._M_cur; }
  91. };
  92. template <class _Val, class _Key, class _HashFcn,
  93.           class _ExtractKey, class _EqualKey, class _Alloc>
  94. struct _Hashtable_const_iterator {
  95.   typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
  96.           _Hashtable;
  97.   typedef _Hashtable_iterator<_Val,_Key,_HashFcn, 
  98.                               _ExtractKey,_EqualKey,_Alloc>
  99.           iterator;
  100.   typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 
  101.                                     _ExtractKey, _EqualKey, _Alloc>
  102.           const_iterator;
  103.   typedef _Hashtable_node<_Val> _Node;
  104.   typedef forward_iterator_tag iterator_category;
  105.   typedef _Val value_type;
  106.   typedef ptrdiff_t difference_type;
  107.   typedef size_t size_type;
  108.   typedef const _Val& reference;
  109.   typedef const _Val* pointer;
  110.   const _Node* _M_cur;
  111.   const _Hashtable* _M_ht;
  112.   _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
  113.     : _M_cur(__n), _M_ht(__tab) {}
  114.   _Hashtable_const_iterator() {}
  115.   _Hashtable_const_iterator(const iterator& __it) 
  116.     : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {}
  117.   reference operator*() const { return _M_cur->_M_val; }
  118. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  119.   pointer operator->() const { return &(operator*()); }
  120. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  121.   const_iterator& operator++();
  122.   const_iterator operator++(int);
  123.   bool operator==(const const_iterator& __it) const 
  124.     { return _M_cur == __it._M_cur; }
  125.   bool operator!=(const const_iterator& __it) const 
  126.     { return _M_cur != __it._M_cur; }
  127. };
  128. // Note: assumes long is at least 32 bits.
  129. enum { __stl_num_primes = 28 };
  130. static const unsigned long __stl_prime_list[__stl_num_primes] =
  131. {
  132.   53ul,         97ul,         193ul,       389ul,       769ul,
  133.   1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  134.   49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  135.   1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  136.   50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul, 
  137.   1610612741ul, 3221225473ul, 4294967291ul
  138. };
  139. inline unsigned long __stl_next_prime(unsigned long __n)
  140. {
  141.   const unsigned long* __first = __stl_prime_list;
  142.   const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes;
  143.   const unsigned long* pos = lower_bound(__first, __last, __n);
  144.   return pos == __last ? *(__last - 1) : *pos;
  145. }
  146. // Forward declaration of operator==.
  147. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  148. class hashtable;
  149. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  150. bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
  151.                 const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2);
  152. // Hashtables handle allocators a bit differently than other containers
  153. //  do.  If we're using standard-conforming allocators, then a hashtable
  154. //  unconditionally has a member variable to hold its allocator, even if
  155. //  it so happens that all instances of the allocator type are identical.
  156. // This is because, for hashtables, this extra storage is negligible.  
  157. //  Additionally, a base class wouldn't serve any other purposes; it 
  158. //  wouldn't, for example, simplify the exception-handling code.
  159. template <class _Val, class _Key, class _HashFcn,
  160.           class _ExtractKey, class _EqualKey, class _Alloc>
  161. class hashtable {
  162. public:
  163.   typedef _Key key_type;
  164.   typedef _Val value_type;
  165.   typedef _HashFcn hasher;
  166.   typedef _EqualKey key_equal;
  167.   typedef size_t            size_type;
  168.   typedef ptrdiff_t         difference_type;
  169.   typedef value_type*       pointer;
  170.   typedef const value_type* const_pointer;
  171.   typedef value_type&       reference;
  172.   typedef const value_type& const_reference;
  173.   hasher hash_funct() const { return _M_hash; }
  174.   key_equal key_eq() const { return _M_equals; }
  175. private:
  176.   typedef _Hashtable_node<_Val> _Node;
  177. #ifdef __STL_USE_STD_ALLOCATORS
  178. public:
  179.   typedef typename _Alloc_traits<_Val,_Alloc>::allocator_type allocator_type;
  180.   allocator_type get_allocator() const { return _M_node_allocator; }
  181. private:
  182.   typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator;
  183.   _Node* _M_get_node() { return _M_node_allocator.allocate(1); }
  184.   void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); }
  185. # define __HASH_ALLOC_INIT(__a) _M_node_allocator(__a), 
  186. #else /* __STL_USE_STD_ALLOCATORS */
  187. public:
  188.   typedef _Alloc allocator_type;
  189.   allocator_type get_allocator() const { return allocator_type(); }
  190. private:
  191.   typedef simple_alloc<_Node, _Alloc> _M_node_allocator_type;
  192.   _Node* _M_get_node() { return _M_node_allocator_type::allocate(1); }
  193.   void _M_put_node(_Node* __p) { _M_node_allocator_type::deallocate(__p, 1); }
  194. # define __HASH_ALLOC_INIT(__a)
  195. #endif /* __STL_USE_STD_ALLOCATORS */
  196. private:
  197.   hasher                _M_hash;
  198.   key_equal             _M_equals;
  199.   _ExtractKey           _M_get_key;
  200.   vector<_Node*,_Alloc> _M_buckets;
  201.   size_type             _M_num_elements;
  202. public:
  203.   typedef _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
  204.           iterator;
  205.   typedef _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,
  206.                                     _Alloc>
  207.           const_iterator;
  208.   friend struct
  209.   _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>;
  210.   friend struct
  211.   _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>;
  212. public:
  213.   hashtable(size_type __n,
  214.             const _HashFcn&    __hf,
  215.             const _EqualKey&   __eql,
  216.             const _ExtractKey& __ext,
  217.             const allocator_type& __a = allocator_type())
  218.     : __HASH_ALLOC_INIT(__a)
  219.       _M_hash(__hf),
  220.       _M_equals(__eql),
  221.       _M_get_key(__ext),
  222.       _M_buckets(__a),
  223.       _M_num_elements(0)
  224.   {
  225.     _M_initialize_buckets(__n);
  226.   }
  227.   hashtable(size_type __n,
  228.             const _HashFcn&    __hf,
  229.             const _EqualKey&   __eql,
  230.             const allocator_type& __a = allocator_type())
  231.     : __HASH_ALLOC_INIT(__a)
  232.       _M_hash(__hf),
  233.       _M_equals(__eql),
  234.       _M_get_key(_ExtractKey()),
  235.       _M_buckets(__a),
  236.       _M_num_elements(0)
  237.   {
  238.     _M_initialize_buckets(__n);
  239.   }
  240.   hashtable(const hashtable& __ht)
  241.     : __HASH_ALLOC_INIT(__ht.get_allocator())
  242.       _M_hash(__ht._M_hash),
  243.       _M_equals(__ht._M_equals),
  244.       _M_get_key(__ht._M_get_key),
  245.       _M_buckets(__ht.get_allocator()),
  246.       _M_num_elements(0)
  247.   {
  248.     _M_copy_from(__ht);
  249.   }
  250. #undef __HASH_ALLOC_INIT
  251.   hashtable& operator= (const hashtable& __ht)
  252.   {
  253.     if (&__ht != this) {
  254.       clear();
  255.       _M_hash = __ht._M_hash;
  256.       _M_equals = __ht._M_equals;
  257.       _M_get_key = __ht._M_get_key;
  258.       _M_copy_from(__ht);
  259.     }
  260.     return *this;
  261.   }
  262.   ~hashtable() { clear(); }
  263.   size_type size() const { return _M_num_elements; }
  264.   size_type max_size() const { return size_type(-1); }
  265.   bool empty() const { return size() == 0; }
  266.   void swap(hashtable& __ht)
  267.   {
  268.     __STD::swap(_M_hash, __ht._M_hash);
  269.     __STD::swap(_M_equals, __ht._M_equals);
  270.     __STD::swap(_M_get_key, __ht._M_get_key);
  271.     _M_buckets.swap(__ht._M_buckets);
  272.     __STD::swap(_M_num_elements, __ht._M_num_elements);
  273.   }
  274.   iterator begin()
  275.   { 
  276.     for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
  277.       if (_M_buckets[__n])
  278.         return iterator(_M_buckets[__n], this);
  279.     return end();
  280.   }
  281.   iterator end() { return iterator(0, this); }
  282.   const_iterator begin() const
  283.   {
  284.     for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
  285.       if (_M_buckets[__n])
  286.         return const_iterator(_M_buckets[__n], this);
  287.     return end();
  288.   }
  289.   const_iterator end() const { return const_iterator(0, this); }
  290. #ifdef __STL_MEMBER_TEMPLATES
  291.   template <class _Vl, class _Ky, class _HF, class _Ex, class _Eq, class _Al>
  292.   friend bool operator== (const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
  293.                           const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
  294. #else /* __STL_MEMBER_TEMPLATES */
  295.   friend bool __STD_QUALIFIER
  296.   operator== __STL_NULL_TMPL_ARGS (const hashtable&, const hashtable&);
  297. #endif /* __STL_MEMBER_TEMPLATES */
  298. public:
  299.   size_type bucket_count() const { return _M_buckets.size(); }
  300.   size_type max_bucket_count() const
  301.     { return __stl_prime_list[(int)__stl_num_primes - 1]; } 
  302.   size_type elems_in_bucket(size_type __bucket) const
  303.   {
  304.     size_type __result = 0;
  305.     for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
  306.       __result += 1;
  307.     return __result;
  308.   }
  309.   pair<iterator, bool> insert_unique(const value_type& __obj)
  310.   {
  311.     resize(_M_num_elements + 1);
  312.     return insert_unique_noresize(__obj);
  313.   }
  314.   iterator insert_equal(const value_type& __obj)
  315.   {
  316.     resize(_M_num_elements + 1);
  317.     return insert_equal_noresize(__obj);
  318.   }
  319.   pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
  320.   iterator insert_equal_noresize(const value_type& __obj);
  321.  
  322. #ifdef __STL_MEMBER_TEMPLATES
  323.   template <class _InputIterator>
  324.   void insert_unique(_InputIterator __f, _InputIterator __l)
  325.   {
  326.     insert_unique(__f, __l, __ITERATOR_CATEGORY(__f));
  327.   }
  328.   template <class _InputIterator>
  329.   void insert_equal(_InputIterator __f, _InputIterator __l)
  330.   {
  331.     insert_equal(__f, __l, __ITERATOR_CATEGORY(__f));
  332.   }
  333.   template <class _InputIterator>
  334.   void insert_unique(_InputIterator __f, _InputIterator __l,
  335.                      input_iterator_tag)
  336.   {
  337.     for ( ; __f != __l; ++__f)
  338.       insert_unique(*__f);
  339.   }
  340.   template <class _InputIterator>
  341.   void insert_equal(_InputIterator __f, _InputIterator __l,
  342.                     input_iterator_tag)
  343.   {
  344.     for ( ; __f != __l; ++__f)
  345.       insert_equal(*__f);
  346.   }
  347.   template <class _ForwardIterator>
  348.   void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
  349.                      forward_iterator_tag)
  350.   {
  351.     size_type __n = 0;
  352.     distance(__f, __l, __n);
  353.     resize(_M_num_elements + __n);
  354.     for ( ; __n > 0; --__n, ++__f)
  355.       insert_unique_noresize(*__f);
  356.   }
  357.   template <class _ForwardIterator>
  358.   void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
  359.                     forward_iterator_tag)
  360.   {
  361.     size_type __n = 0;
  362.     distance(__f, __l, __n);
  363.     resize(_M_num_elements + __n);
  364.     for ( ; __n > 0; --__n, ++__f)
  365.       insert_equal_noresize(*__f);
  366.   }
  367. #else /* __STL_MEMBER_TEMPLATES */
  368.   void insert_unique(const value_type* __f, const value_type* __l)
  369.   {
  370.     size_type __n = __l - __f;
  371.     resize(_M_num_elements + __n);
  372.     for ( ; __n > 0; --__n, ++__f)
  373.       insert_unique_noresize(*__f);
  374.   }
  375.   void insert_equal(const value_type* __f, const value_type* __l)
  376.   {
  377.     size_type __n = __l - __f;
  378.     resize(_M_num_elements + __n);
  379.     for ( ; __n > 0; --__n, ++__f)
  380.       insert_equal_noresize(*__f);
  381.   }
  382.   void insert_unique(const_iterator __f, const_iterator __l)
  383.   {
  384.     size_type __n = 0;
  385.     distance(__f, __l, __n);
  386.     resize(_M_num_elements + __n);
  387.     for ( ; __n > 0; --__n, ++__f)
  388.       insert_unique_noresize(*__f);
  389.   }
  390.   void insert_equal(const_iterator __f, const_iterator __l)
  391.   {
  392.     size_type __n = 0;
  393.     distance(__f, __l, __n);
  394.     resize(_M_num_elements + __n);
  395.     for ( ; __n > 0; --__n, ++__f)
  396.       insert_equal_noresize(*__f);
  397.   }
  398. #endif /*__STL_MEMBER_TEMPLATES */
  399.   reference find_or_insert(const value_type& __obj);
  400.   iterator find(const key_type& __key) 
  401.   {
  402.     size_type __n = _M_bkt_num_key(__key);
  403.     _Node* __first;
  404.     for ( __first = _M_buckets[__n];
  405.           __first && !_M_equals(_M_get_key(__first->_M_val), __key);
  406.           __first = __first->_M_next)
  407.       {}
  408.     return iterator(__first, this);
  409.   } 
  410.   const_iterator find(const key_type& __key) const
  411.   {
  412.     size_type __n = _M_bkt_num_key(__key);
  413.     const _Node* __first;
  414.     for ( __first = _M_buckets[__n];
  415.           __first && !_M_equals(_M_get_key(__first->_M_val), __key);
  416.           __first = __first->_M_next)
  417.       {}
  418.     return const_iterator(__first, this);
  419.   } 
  420.   size_type count(const key_type& __key) const
  421.   {
  422.     const size_type __n = _M_bkt_num_key(__key);
  423.     size_type __result = 0;
  424.     for (const _Node* __cur = _M_buckets[__n]; __cur; __cur = __cur->_M_next)
  425.       if (_M_equals(_M_get_key(__cur->_M_val), __key))
  426.         ++__result;
  427.     return __result;
  428.   }
  429.   pair<iterator, iterator> 
  430.   equal_range(const key_type& __key);
  431.   pair<const_iterator, const_iterator> 
  432.   equal_range(const key_type& __key) const;
  433.   size_type erase(const key_type& __key);
  434.   void erase(const iterator& __it);
  435.   void erase(iterator __first, iterator __last);
  436.   void erase(const const_iterator& __it);
  437.   void erase(const_iterator __first, const_iterator __last);
  438.   void resize(size_type __num_elements_hint);
  439.   void clear();
  440. private:
  441.   size_type _M_next_size(size_type __n) const
  442.     { return __stl_next_prime(__n); }
  443.   void _M_initialize_buckets(size_type __n)
  444.   {
  445.     const size_type __n_buckets = _M_next_size(__n);
  446.     _M_buckets.reserve(__n_buckets);
  447.     _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
  448.     _M_num_elements = 0;
  449.   }
  450.   size_type _M_bkt_num_key(const key_type& __key) const
  451.   {
  452.     return _M_bkt_num_key(__key, _M_buckets.size());
  453.   }
  454.   size_type _M_bkt_num(const value_type& __obj) const
  455.   {
  456.     return _M_bkt_num_key(_M_get_key(__obj));
  457.   }
  458.   size_type _M_bkt_num_key(const key_type& __key, size_t __n) const
  459.   {
  460.     return _M_hash(__key) % __n;
  461.   }
  462.   size_type _M_bkt_num(const value_type& __obj, size_t __n) const
  463.   {
  464.     return _M_bkt_num_key(_M_get_key(__obj), __n);
  465.   }
  466.   _Node* _M_new_node(const value_type& __obj)
  467.   {
  468.     _Node* __n = _M_get_node();
  469.     __n->_M_next = 0;
  470.     __STL_TRY {
  471.       construct(&__n->_M_val, __obj);
  472.       return __n;
  473.     }
  474.     __STL_UNWIND(_M_put_node(__n));
  475.   }
  476.   
  477.   void _M_delete_node(_Node* __n)
  478.   {
  479.     destroy(&__n->_M_val);
  480.     _M_put_node(__n);
  481.   }
  482.   void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
  483.   void _M_erase_bucket(const size_type __n, _Node* __last);
  484.   void _M_copy_from(const hashtable& __ht);
  485. };
  486. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  487.           class _All>
  488. _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&
  489. _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++()
  490. {
  491.   const _Node* __old = _M_cur;
  492.   _M_cur = _M_cur->_M_next;
  493.   if (!_M_cur) {
  494.     size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
  495.     while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
  496.       _M_cur = _M_ht->_M_buckets[__bucket];
  497.   }
  498.   return *this;
  499. }
  500. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  501.           class _All>
  502. inline _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>
  503. _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int)
  504. {
  505.   iterator __tmp = *this;
  506.   ++*this;
  507.   return __tmp;
  508. }
  509. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  510.           class _All>
  511. _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&
  512. _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++()
  513. {
  514.   const _Node* __old = _M_cur;
  515.   _M_cur = _M_cur->_M_next;
  516.   if (!_M_cur) {
  517.     size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
  518.     while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
  519.       _M_cur = _M_ht->_M_buckets[__bucket];
  520.   }
  521.   return *this;
  522. }
  523. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  524.           class _All>
  525. inline _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>
  526. _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int)
  527. {
  528.   const_iterator __tmp = *this;
  529.   ++*this;
  530.   return __tmp;
  531. }
  532. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  533. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  534.           class _All>
  535. inline forward_iterator_tag
  536. iterator_category(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&)
  537. {
  538.   return forward_iterator_tag();
  539. }
  540. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  541.           class _All>
  542. inline _Val* 
  543. value_type(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&)
  544. {
  545.   return (_Val*) 0;
  546. }
  547. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  548.           class _All>
  549. inline hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::difference_type*
  550. distance_type(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&)
  551. {
  552.   return (hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::difference_type*) 0;
  553. }
  554. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  555.           class _All>
  556. inline forward_iterator_tag
  557. iterator_category(const _Hashtable_const_iterator<_Val,_Key,_HF,
  558.                                                   _ExK,_EqK,_All>&)
  559. {
  560.   return forward_iterator_tag();
  561. }
  562. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  563.           class _All>
  564. inline _Val* 
  565. value_type(const _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&)
  566. {
  567.   return (_Val*) 0;
  568. }
  569. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  570.           class _All>
  571. inline hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::difference_type*
  572. distance_type(const _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&)
  573. {
  574.   return (hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::difference_type*) 0;
  575. }
  576. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  577. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  578. bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
  579.                 const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2)
  580. {
  581.   typedef typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::_Node _Node;
  582.   if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
  583.     return false;
  584.   for (int __n = 0; __n < __ht1._M_buckets.size(); ++__n) {
  585.     _Node* __cur1 = __ht1._M_buckets[__n];
  586.     _Node* __cur2 = __ht2._M_buckets[__n];
  587.     for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val;
  588.           __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
  589.       {}
  590.     if (__cur1 || __cur2)
  591.       return false;
  592.   }
  593.   return true;
  594. }  
  595. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  596. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  597. inline bool operator!=(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
  598.                        const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) {
  599.   return !(__ht1 == __ht2);
  600. }
  601. template <class _Val, class _Key, class _HF, class _Extract, class _EqKey, 
  602.           class _All>
  603. inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
  604.                  hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) {
  605.   __ht1.swap(__ht2);
  606. }
  607. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  608. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  609. pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool> 
  610. hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  611.   ::insert_unique_noresize(const value_type& __obj)
  612. {
  613.   const size_type __n = _M_bkt_num(__obj);
  614.   _Node* __first = _M_buckets[__n];
  615.   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 
  616.     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
  617.       return pair<iterator, bool>(iterator(__cur, this), false);
  618.   _Node* __tmp = _M_new_node(__obj);
  619.   __tmp->_M_next = __first;
  620.   _M_buckets[__n] = __tmp;
  621.   ++_M_num_elements;
  622.   return pair<iterator, bool>(iterator(__tmp, this), true);
  623. }
  624. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  625. typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator 
  626. hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  627.   ::insert_equal_noresize(const value_type& __obj)
  628. {
  629.   const size_type __n = _M_bkt_num(__obj);
  630.   _Node* __first = _M_buckets[__n];
  631.   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 
  632.     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
  633.       _Node* __tmp = _M_new_node(__obj);
  634.       __tmp->_M_next = __cur->_M_next;
  635.       __cur->_M_next = __tmp;
  636.       ++_M_num_elements;
  637.       return iterator(__tmp, this);
  638.     }
  639.   _Node* __tmp = _M_new_node(__obj);
  640.   __tmp->_M_next = __first;
  641.   _M_buckets[__n] = __tmp;
  642.   ++_M_num_elements;
  643.   return iterator(__tmp, this);
  644. }
  645. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  646. typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference 
  647. hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj)
  648. {
  649.   resize(_M_num_elements + 1);
  650.   size_type __n = _M_bkt_num(__obj);
  651.   _Node* __first = _M_buckets[__n];
  652.   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
  653.     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
  654.       return __cur->_M_val;
  655.   _Node* __tmp = _M_new_node(__obj);
  656.   __tmp->_M_next = __first;
  657.   _M_buckets[__n] = __tmp;
  658.   ++_M_num_elements;
  659.   return __tmp->_M_val;
  660. }
  661. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  662. pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator,
  663.      typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator> 
  664. hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::equal_range(const key_type& __key)
  665. {
  666.   typedef pair<iterator, iterator> _Pii;
  667.   const size_type __n = _M_bkt_num_key(__key);
  668.   for (_Node* __first = _M_buckets[__n]; __first; __first = __first->_M_next)
  669.     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
  670.       for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next)
  671.         if (!_M_equals(_M_get_key(__cur->_M_val), __key))
  672.           return _Pii(iterator(__first, this), iterator(__cur, this));
  673.       for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
  674.         if (_M_buckets[__m])
  675.           return _Pii(iterator(__first, this),
  676.                      iterator(_M_buckets[__m], this));
  677.       return _Pii(iterator(__first, this), end());
  678.     }
  679.   return _Pii(end(), end());
  680. }
  681. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  682. pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator, 
  683.      typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator> 
  684. hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  685.   ::equal_range(const key_type& __key) const
  686. {
  687.   typedef pair<const_iterator, const_iterator> _Pii;
  688.   const size_type __n = _M_bkt_num_key(__key);
  689.   for (const _Node* __first = _M_buckets[__n] ;
  690.        __first; 
  691.        __first = __first->_M_next) {
  692.     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
  693.       for (const _Node* __cur = __first->_M_next;
  694.            __cur;
  695.            __cur = __cur->_M_next)
  696.         if (!_M_equals(_M_get_key(__cur->_M_val), __key))
  697.           return _Pii(const_iterator(__first, this),
  698.                       const_iterator(__cur, this));
  699.       for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
  700.         if (_M_buckets[__m])
  701.           return _Pii(const_iterator(__first, this),
  702.                       const_iterator(_M_buckets[__m], this));
  703.       return _Pii(const_iterator(__first, this), end());
  704.     }
  705.   }
  706.   return _Pii(end(), end());
  707. }
  708. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  709. typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type 
  710. hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key)
  711. {
  712.   const size_type __n = _M_bkt_num_key(__key);
  713.   _Node* __first = _M_buckets[__n];
  714.   size_type __erased = 0;
  715.   if (__first) {
  716.     _Node* __cur = __first;
  717.     _Node* __next = __cur->_M_next;
  718.     while (__next) {
  719.       if (_M_equals(_M_get_key(__next->_M_val), __key)) {
  720.         __cur->_M_next = __next->_M_next;
  721.         _M_delete_node(__next);
  722.         __next = __cur->_M_next;
  723.         ++__erased;
  724.         --_M_num_elements;
  725.       }
  726.       else {
  727.         __cur = __next;
  728.         __next = __cur->_M_next;
  729.       }
  730.     }
  731.     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
  732.       _M_buckets[__n] = __first->_M_next;
  733.       _M_delete_node(__first);
  734.       ++__erased;
  735.       --_M_num_elements;
  736.     }
  737.   }
  738.   return __erased;
  739. }
  740. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  741. void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const iterator& __it)
  742. {
  743.   _Node* __p = __it._M_cur;
  744.   if (__p) {
  745.     const size_type __n = _M_bkt_num(__p->_M_val);
  746.     _Node* __cur = _M_buckets[__n];
  747.     if (__cur == __p) {
  748.       _M_buckets[__n] = __cur->_M_next;
  749.       _M_delete_node(__cur);
  750.       --_M_num_elements;
  751.     }
  752.     else {
  753.       _Node* __next = __cur->_M_next;
  754.       while (__next) {
  755.         if (__next == __p) {
  756.           __cur->_M_next = __next->_M_next;
  757.           _M_delete_node(__next);
  758.           --_M_num_elements;
  759.           break;
  760.         }
  761.         else {
  762.           __cur = __next;
  763.           __next = __cur->_M_next;
  764.         }
  765.       }
  766.     }
  767.   }
  768. }
  769. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  770. void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  771.   ::erase(iterator __first, iterator __last)
  772. {
  773.   size_type __f_bucket = __first._M_cur ? 
  774.     _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
  775.   size_type __l_bucket = __last._M_cur ? 
  776.     _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
  777.   if (__first._M_cur == __last._M_cur)
  778.     return;
  779.   else if (__f_bucket == __l_bucket)
  780.     _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
  781.   else {
  782.     _M_erase_bucket(__f_bucket, __first._M_cur, 0);
  783.     for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
  784.       _M_erase_bucket(__n, 0);
  785.     if (__l_bucket != _M_buckets.size())
  786.       _M_erase_bucket(__l_bucket, __last._M_cur);
  787.   }
  788. }
  789. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  790. inline void
  791. hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const_iterator __first,
  792.                                              const_iterator __last)
  793. {
  794.   erase(iterator(const_cast<_Node*>(__first._M_cur),
  795.                  const_cast<hashtable*>(__first._M_ht)),
  796.         iterator(const_cast<_Node*>(__last._M_cur),
  797.                  const_cast<hashtable*>(__last._M_ht)));
  798. }
  799. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  800. inline void
  801. hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const const_iterator& __it)
  802. {
  803.   erase(iterator(const_cast<_Node*>(__it._M_cur),
  804.                  const_cast<hashtable*>(__it._M_ht)));
  805. }
  806. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  807. void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  808.   ::resize(size_type __num_elements_hint)
  809. {
  810.   const size_type __old_n = _M_buckets.size();
  811.   if (__num_elements_hint > __old_n) {
  812.     const size_type __n = _M_next_size(__num_elements_hint);
  813.     if (__n > __old_n) {
  814.       vector<_Node*, _All> __tmp(__n, (_Node*)(0),
  815.                                  _M_buckets.get_allocator());
  816.       __STL_TRY {
  817.         for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
  818.           _Node* __first = _M_buckets[__bucket];
  819.           while (__first) {
  820.             size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
  821.             _M_buckets[__bucket] = __first->_M_next;
  822.             __first->_M_next = __tmp[__new_bucket];
  823.             __tmp[__new_bucket] = __first;
  824.             __first = _M_buckets[__bucket];          
  825.           }
  826.         }
  827.         _M_buckets.swap(__tmp);
  828.       }
  829. #         ifdef __STL_USE_EXCEPTIONS
  830.       catch(...) {
  831.         for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
  832.           while (__tmp[__bucket]) {
  833.             _Node* __next = __tmp[__bucket]->_M_next;
  834.             _M_delete_node(__tmp[__bucket]);
  835.             __tmp[__bucket] = __next;
  836.           }
  837.         }
  838.         throw;
  839.       }
  840. #         endif /* __STL_USE_EXCEPTIONS */
  841.     }
  842.   }
  843. }
  844. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  845. void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  846.   ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
  847. {
  848.   _Node* __cur = _M_buckets[__n];
  849.   if (__cur == __first)
  850.     _M_erase_bucket(__n, __last);
  851.   else {
  852.     _Node* __next;
  853.     for (__next = __cur->_M_next; 
  854.          __next != __first; 
  855.          __cur = __next, __next = __cur->_M_next)
  856.       ;
  857.     while (__next != __last) {
  858.       __cur->_M_next = __next->_M_next;
  859.       _M_delete_node(__next);
  860.       __next = __cur->_M_next;
  861.       --_M_num_elements;
  862.     }
  863.   }
  864. }
  865. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  866. void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  867.   ::_M_erase_bucket(const size_type __n, _Node* __last)
  868. {
  869.   _Node* __cur = _M_buckets[__n];
  870.   while (__cur != __last) {
  871.     _Node* __next = __cur->_M_next;
  872.     _M_delete_node(__cur);
  873.     __cur = __next;
  874.     _M_buckets[__n] = __cur;
  875.     --_M_num_elements;
  876.   }
  877. }
  878. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  879. void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear()
  880. {
  881.   for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
  882.     _Node* __cur = _M_buckets[__i];
  883.     while (__cur != 0) {
  884.       _Node* __next = __cur->_M_next;
  885.       _M_delete_node(__cur);
  886.       __cur = __next;
  887.     }
  888.     _M_buckets[__i] = 0;
  889.   }
  890.   _M_num_elements = 0;
  891. }
  892.     
  893. template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
  894. void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  895.   ::_M_copy_from(const hashtable& __ht)
  896. {
  897.   _M_buckets.clear();
  898.   _M_buckets.reserve(__ht._M_buckets.size());
  899.   _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
  900.   __STL_TRY {
  901.     for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
  902.       const _Node* __cur = __ht._M_buckets[__i];
  903.       if (__cur) {
  904.         _Node* __copy = _M_new_node(__cur->_M_val);
  905.         _M_buckets[__i] = __copy;
  906.         for (_Node* __next = __cur->_M_next; 
  907.              __next; 
  908.              __cur = __next, __next = __cur->_M_next) {
  909.           __copy->_M_next = _M_new_node(__next->_M_val);
  910.           __copy = __copy->_M_next;
  911.         }
  912.       }
  913.     }
  914.     _M_num_elements = __ht._M_num_elements;
  915.   }
  916.   __STL_UNWIND(clear());
  917. }
  918. __STL_END_NAMESPACE
  919. #endif /* __SGI_STL_INTERNAL_HASHTABLE_H */
  920. // Local Variables:
  921. // mode:C++
  922. // End: