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