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.c < prev    next >
C/C++ Source or Header  |  2002-02-02  |  16KB  |  469 lines
  1. /*
  2.  *
  3.  *
  4.  * Copyright (c) 1994
  5.  * Hewlett-Packard Company
  6.  *
  7.  * Copyright (c) 1996,1997
  8.  * Silicon Graphics Computer Systems, Inc.
  9.  *
  10.  * Copyright (c) 1997
  11.  * Moscow Center for SPARC Technology
  12.  *
  13.  * Copyright (c) 1999 
  14.  * Boris Fomitchev
  15.  *
  16.  * This material is provided "as is", with absolutely no warranty expressed
  17.  * or implied. Any use is at your own risk.
  18.  *
  19.  * Permission to use or copy this software for any purpose is hereby granted 
  20.  * without fee, provided the above notices are retained on all copies.
  21.  * Permission to modify the code and to distribute modified code is granted,
  22.  * provided the above notices are retained, and a notice that the code was
  23.  * modified is included with the above copyright notice.
  24.  *
  25.  */
  26. #ifndef _STLP_HASHTABLE_C
  27. #define _STLP_HASHTABLE_C
  28.  
  29. #ifndef _STLP_INTERNAL_HASHTABLE_H
  30. # include <stl/_hashtable.h>
  31. #endif
  32.  
  33. #ifdef _STLP_DEBUG
  34. #  define hashtable __WORKAROUND_DBG_RENAME(hashtable)
  35. #endif
  36.  
  37. _STLP_BEGIN_NAMESPACE
  38.  
  39. # define __PRIME_LIST_BODY { \
  40.   53ul,         97ul,         193ul,       389ul,       769ul,      \
  41.   1543ul,       3079ul,       6151ul,      12289ul,     24593ul,    \
  42.   49157ul,      98317ul,      196613ul,    393241ul,    786433ul,   \
  43.   1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul, \
  44.   50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,\
  45.   1610612741ul, 3221225473ul, 4294967291ul  \
  46. }
  47.  
  48. #if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
  49. template <class _Tp>
  50. const size_t _Stl_prime<_Tp>::_M_list[__stl_num_primes] = __PRIME_LIST_BODY;
  51. #else
  52. __DECLARE_INSTANCE(const size_t, 
  53.            _Stl_prime_type::_M_list[], =__PRIME_LIST_BODY);
  54. #endif /* _STLP_STATIC_TEMPLATE_DATA */
  55.  
  56. # undef __PRIME_LIST_BODY
  57.  
  58. // fbp: these defines are for outline methods definitions.
  59. // needed to definitions to be portable. Should not be used in method bodies.
  60.  
  61. # if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
  62. #  define __size_type__       size_t
  63. #  define size_type           size_t
  64. #  define value_type      _Val
  65. #  define key_type        _Key
  66. #  define _Node           _Hashtable_node<_Val>
  67. #  define __reference__       _Val&
  68.  
  69. #  define __iterator__        _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>
  70. #  define __const_iterator__  _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>
  71. # else
  72. #  define __size_type__        _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::size_type
  73. #  define __reference__        _STLP_TYPENAME_ON_RETURN_TYPE  hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::reference
  74. #  define __iterator__         _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::iterator
  75. # endif
  76.  
  77. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  78.           class _All>
  79. _Hashtable_node<_Val>*
  80. _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_skip_to_next() {
  81.   size_t __bucket = _M_ht->_M_bkt_num(_M_cur->_M_val);
  82.   size_t __h_sz;
  83.   __h_sz = this->_M_ht->bucket_count();
  84.  
  85.   _Node* __i=0;
  86.   while (__i==0 && ++__bucket < __h_sz)
  87.     __i = (_Node*)_M_ht->_M_buckets[__bucket];
  88.   return __i;
  89. }
  90.  
  91. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
  92.           class _All>
  93. __size_type__
  94. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_next_size(size_type __n) const    { 
  95.   const size_type* __first = (const size_type*)_Stl_prime_type::_M_list;
  96.   const size_type* __last =  (const size_type*)_Stl_prime_type::_M_list + (int)__stl_num_primes;
  97.   const size_type* pos = __lower_bound(__first, __last, __n, __less((size_type*)0), (ptrdiff_t*)0);
  98.   return (pos == __last ? *(__last - 1) : *pos);
  99. }
  100.  
  101. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  102. bool 
  103. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_equal(
  104.                           const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht1,
  105.                           const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht2)
  106. {
  107.   //  typedef _Hashtable_node<_Val> _Node;
  108.   if (__ht1.bucket_count() != __ht2.bucket_count())
  109.     return false;
  110.   for (size_t __n = 0; __n < __ht1.bucket_count(); ++__n) {
  111.     const _Node* __cur1 = __ht1._M_get_bucket(__n);
  112.     const _Node* __cur2 = __ht2._M_get_bucket(__n);
  113.     for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val;
  114.           __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
  115.       {}
  116.     if (__cur1 || __cur2)
  117.       return false;
  118.   }
  119.   return true;
  120. }  
  121.  
  122. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  123. pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> , bool> 
  124. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  125.   ::insert_unique_noresize(const value_type& __obj)
  126. {
  127.   const size_type __n = _M_bkt_num(__obj);
  128.   _Node* __first = (_Node*)_M_buckets[__n];
  129.  
  130.   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 
  131.     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
  132.       return pair<iterator, bool>(iterator(__cur, this), false);
  133.  
  134.   _Node* __tmp = _M_new_node(__obj);
  135.   __tmp->_M_next = __first;
  136.   _M_buckets[__n] = __tmp;
  137.   ++_M_num_elements._M_data;
  138.   return pair<iterator, bool>(iterator(__tmp, this), true);
  139. }
  140.  
  141. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  142. __iterator__ 
  143. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  144.   ::insert_equal_noresize(const value_type& __obj)
  145. {
  146.   const size_type __n = _M_bkt_num(__obj);
  147.   _Node* __first = (_Node*)_M_buckets[__n];
  148.  
  149.   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 
  150.     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
  151.       _Node* __tmp = _M_new_node(__obj);
  152.       __tmp->_M_next = __cur->_M_next;
  153.       __cur->_M_next = __tmp;
  154.       ++_M_num_elements._M_data;
  155.       return iterator(__tmp, this);
  156.     }
  157.  
  158.   _Node* __tmp = _M_new_node(__obj);
  159.   __tmp->_M_next = __first;
  160.   _M_buckets[__n] = __tmp;
  161.   ++_M_num_elements._M_data;
  162.   return iterator(__tmp, this);
  163. }
  164.  
  165. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  166. __reference__ 
  167. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_insert(const value_type& __obj)
  168. {
  169.   resize(_M_num_elements._M_data + 1);
  170.  
  171.   size_type __n = _M_bkt_num(__obj);
  172.   _Node* __first = (_Node*)_M_buckets[__n];
  173.  
  174.   _Node* __tmp = _M_new_node(__obj);
  175.   __tmp->_M_next = __first;
  176.   _M_buckets[__n] = __tmp;
  177.   ++_M_num_elements._M_data;
  178.   return __tmp->_M_val;
  179. }
  180.  
  181. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  182. __reference__ 
  183. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::find_or_insert(const value_type& __obj)
  184. {
  185.  
  186.   _Node* __first = _M_find(_M_get_key(__obj));
  187.   if (__first)
  188.     return __first->_M_val;
  189.   else
  190.     return _M_insert(__obj);
  191. }
  192.  
  193. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  194. pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>,
  195.       _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> > 
  196. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::equal_range(const key_type& __key)
  197. {
  198.   typedef pair<iterator, iterator> _Pii;
  199.   const size_type __n = _M_bkt_num_key(__key);
  200.  
  201.   for (_Node* __first = (_Node*)_M_buckets[__n]; __first; __first = __first->_M_next)
  202.     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
  203.       for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next)
  204.         if (!_M_equals(_M_get_key(__cur->_M_val), __key))
  205.           return _Pii(iterator(__first, this), iterator(__cur, this));
  206.       for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
  207.         if (_M_buckets[__m])
  208.           return _Pii(iterator(__first, this),
  209.                      iterator((_Node*)_M_buckets[__m], this));
  210.       return _Pii(iterator(__first, this), end());
  211.     }
  212.   return _Pii(end(), end());
  213. }
  214.  
  215. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  216. pair< _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>, 
  217.      _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> > 
  218. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  219.   ::equal_range(const key_type& __key) const
  220. {
  221.   typedef pair<const_iterator, const_iterator> _Pii;
  222.   const size_type __n = _M_bkt_num_key(__key);
  223.  
  224.   for (const _Node* __first = (_Node*)_M_buckets[__n] ;
  225.        __first; 
  226.        __first = __first->_M_next) {
  227.     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
  228.       for (const _Node* __cur = __first->_M_next;
  229.            __cur;
  230.            __cur = __cur->_M_next)
  231.         if (!_M_equals(_M_get_key(__cur->_M_val), __key))
  232.           return _Pii(const_iterator(__first, this),
  233.                       const_iterator(__cur, this));
  234.       for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
  235.         if (_M_buckets[__m])
  236.           return _Pii(const_iterator(__first, this),
  237.                       const_iterator((_Node*)_M_buckets[__m], this));
  238.       return _Pii(const_iterator(__first, this), end());
  239.     }
  240.   }
  241.   return _Pii(end(), end());
  242. }
  243.  
  244. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  245. __size_type__ 
  246. hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const key_type& __key)
  247. {
  248.   const size_type __n = _M_bkt_num_key(__key);
  249.   _Node* __first = (_Node*)_M_buckets[__n];
  250.   size_type __erased = 0;
  251.  
  252.   if (__first) {
  253.     _Node* __cur = __first;
  254.     _Node* __next = __cur->_M_next;
  255.     while (__next) {
  256.       if (_M_equals(_M_get_key(__next->_M_val), __key)) {
  257.         __cur->_M_next = __next->_M_next;
  258.         _M_delete_node(__next);
  259.         __next = __cur->_M_next;
  260.         ++__erased;
  261.         --_M_num_elements._M_data;
  262.       }
  263.       else {
  264.         __cur = __next;
  265.         __next = __cur->_M_next;
  266.       }
  267.     }
  268.     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
  269.       _M_buckets[__n] = __first->_M_next;
  270.       _M_delete_node(__first);
  271.       ++__erased;
  272.       --_M_num_elements._M_data;
  273.     }
  274.   }
  275.   return __erased;
  276. }
  277.  
  278. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  279. void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const const_iterator& __it)
  280. {
  281.   // const iterator& __it = __REINTERPRET_CAST(const iterator&,_c_it);
  282.   const _Node* __p = __it._M_cur;
  283.   if (__p) {
  284.     const size_type __n = _M_bkt_num(__p->_M_val);
  285.     _Node* __cur = (_Node*)_M_buckets[__n];
  286.  
  287.     if (__cur == __p) {
  288.       _M_buckets[__n] = __cur->_M_next;
  289.       _M_delete_node(__cur);
  290.       --_M_num_elements._M_data;
  291.     }
  292.     else {
  293.       _Node* __next = __cur->_M_next;
  294.       while (__next) {
  295.         if (__next == __p) {
  296.           __cur->_M_next = __next->_M_next;
  297.           _M_delete_node(__next);
  298.           --_M_num_elements._M_data;
  299.           break;
  300.         }
  301.         else {
  302.           __cur = __next;
  303.           __next = __cur->_M_next;
  304.         }
  305.       }
  306.     }
  307.   }
  308. }
  309.  
  310. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  311. void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  312.   ::erase(const_iterator _c_first, const_iterator _c_last)
  313. {
  314.   iterator& __first = (iterator&)_c_first;
  315.   iterator& __last = (iterator&)_c_last;
  316.   size_type __f_bucket = __first._M_cur ? 
  317.     _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
  318.   size_type __l_bucket = __last._M_cur ? 
  319.     _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
  320.   if (__first._M_cur == __last._M_cur)
  321.     return;
  322.   else if (__f_bucket == __l_bucket)
  323.     _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
  324.   else {
  325.     _M_erase_bucket(__f_bucket, __first._M_cur, 0);
  326.     for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
  327.       _M_erase_bucket(__n, 0);
  328.     if (__l_bucket != _M_buckets.size())
  329.       _M_erase_bucket(__l_bucket, __last._M_cur);
  330.   }
  331. }
  332.  
  333. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  334. void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  335.   ::resize(size_type __num_elements_hint)
  336. {
  337.   const size_type __old_n = _M_buckets.size();
  338.   if (__num_elements_hint > __old_n) {
  339.     const size_type __n = _M_next_size(__num_elements_hint);
  340.     if (__n > __old_n) {
  341.       _BucketVector __tmp(__n, (void*)(0),
  342.               _M_buckets.get_allocator());
  343.       _STLP_TRY {
  344.         for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
  345.           _Node* __first = (_Node*)_M_buckets[__bucket];
  346.           while (__first) {
  347.             size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
  348.             _M_buckets[__bucket] = __first->_M_next;
  349.             __first->_M_next = (_Node*)__tmp[__new_bucket];
  350.             __tmp[__new_bucket] = __first;
  351.             __first = (_Node*)_M_buckets[__bucket];          
  352.           }
  353.         }
  354.         _M_buckets.swap(__tmp);
  355.       }
  356. #         ifdef _STLP_USE_EXCEPTIONS
  357.       catch(...) {
  358.         for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
  359.           while (__tmp[__bucket]) {
  360.             _Node* __next = ((_Node*)__tmp[__bucket])->_M_next;
  361.             _M_delete_node((_Node*)__tmp[__bucket]);
  362.             __tmp[__bucket] = __next;
  363.           }
  364.         }
  365.         throw;
  366.       }
  367. #         endif /* _STLP_USE_EXCEPTIONS */
  368.     }
  369.   }
  370. }
  371.  
  372. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  373. void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  374.   ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
  375. {
  376.   _Node* __cur = (_Node*)_M_buckets[__n];
  377.   if (__cur == __first)
  378.     _M_erase_bucket(__n, __last);
  379.   else {
  380.     _Node* __next;
  381.     for (__next = __cur->_M_next; 
  382.          __next != __first; 
  383.          __cur = __next, __next = __cur->_M_next)
  384.       ;
  385.     while (__next != __last) {
  386.       __cur->_M_next = __next->_M_next;
  387.       _M_delete_node(__next);
  388.       __next = __cur->_M_next;
  389.       --_M_num_elements._M_data;
  390.     }
  391.   }
  392. }
  393.  
  394. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  395. void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  396.   ::_M_erase_bucket(const size_type __n, _Node* __last)
  397. {
  398.   _Node* __cur = (_Node*)_M_buckets[__n];
  399.   while (__cur && __cur != __last) {
  400.     _Node* __next = __cur->_M_next;
  401.     _M_delete_node(__cur);
  402.     __cur = __next;
  403.     _M_buckets[__n] = __cur;
  404.     --_M_num_elements._M_data;
  405.   }
  406. }
  407.  
  408. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  409. void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::clear()
  410. {
  411.   for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
  412.     _Node* __cur = (_Node*)_M_buckets[__i];
  413.     while (__cur != 0) {
  414.       _Node* __next = __cur->_M_next;
  415.       _M_delete_node(__cur);
  416.       __cur = __next;
  417.     }
  418.     _M_buckets[__i] = 0;
  419.   }
  420.   _M_num_elements._M_data = 0;
  421. }
  422.  
  423.     
  424. template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
  425. void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
  426.   ::_M_copy_from(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht)
  427. {
  428.   _M_buckets.clear();
  429.   _M_buckets.reserve(__ht._M_buckets.size());
  430.   _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (void*) 0);
  431.   _STLP_TRY {
  432.     for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
  433.       const _Node* __cur = (_Node*)__ht._M_buckets[__i];
  434.       if (__cur) {
  435.         _Node* __xcopy = _M_new_node(__cur->_M_val);
  436.         _M_buckets[__i] = __xcopy;
  437.  
  438.         for (_Node* __next = __cur->_M_next; 
  439.              __next; 
  440.              __cur = __next, __next = __cur->_M_next) {
  441.           __xcopy->_M_next = _M_new_node(__next->_M_val);
  442.           __xcopy = __xcopy->_M_next;
  443.         }
  444.       }
  445.     }
  446.     _M_num_elements._M_data = __ht._M_num_elements._M_data;
  447.   }
  448.   _STLP_UNWIND(clear());
  449. }
  450.  
  451. # undef __iterator__ 
  452. # undef const_iterator
  453. # undef __size_type__
  454. # undef __reference__
  455. # undef size_type       
  456. # undef value_type      
  457. # undef key_type        
  458. # undef _Node            
  459. # undef __stl_num_primes
  460. # undef hashtable
  461.  
  462. _STLP_END_NAMESPACE
  463.  
  464. #endif /*  _STLP_HASHTABLE_C */
  465.  
  466. // Local Variables:
  467. // mode:C++
  468. // End:
  469.