epoc32/include/stdapis/stlport/stl/_hashtable.c
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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_PUSH_CLEANUP_ITEM(_BucketVector, &__tmp);
   344       _STLP_TRY {
   345         for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
   346           _Node* __first = (_Node*)_M_buckets[__bucket];
   347           while (__first) {
   348             size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
   349             _M_buckets[__bucket] = __first->_M_next;
   350             __first->_M_next = (_Node*)__tmp[__new_bucket];
   351             __tmp[__new_bucket] = __first;
   352             __first = (_Node*)_M_buckets[__bucket];          
   353           }
   354         }
   355         _M_buckets.swap(__tmp);
   356       }
   357       _STLP_CATCH_ALL {
   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         _STLP_RETHROW;
   366     }
   367 #ifdef _STLP_USE_TRAP_LEAVE
   368       CleanupStack::Pop();
   369 #endif
   370 
   371     }
   372   }
   373 }
   374 
   375 template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
   376 void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
   377   ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
   378 {
   379   _Node* __cur = (_Node*)_M_buckets[__n];
   380   if (__cur == __first)
   381     _M_erase_bucket(__n, __last);
   382   else {
   383     _Node* __next;
   384     for (__next = __cur->_M_next; 
   385          __next != __first; 
   386          __cur = __next, __next = __cur->_M_next)
   387       ;
   388     while (__next != __last) {
   389       __cur->_M_next = __next->_M_next;
   390       _M_delete_node(__next);
   391       __next = __cur->_M_next;
   392       --_M_num_elements._M_data;
   393     }
   394   }
   395 }
   396 
   397 template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
   398 void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
   399   ::_M_erase_bucket(const size_type __n, _Node* __last)
   400 {
   401   _Node* __cur = (_Node*)_M_buckets[__n];
   402   while (__cur && __cur != __last) {
   403     _Node* __next = __cur->_M_next;
   404     _M_delete_node(__cur);
   405     __cur = __next;
   406     _M_buckets[__n] = __cur;
   407     --_M_num_elements._M_data;
   408   }
   409 }
   410 
   411 template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
   412 void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::clear()
   413 {
   414   for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
   415     _Node* __cur = (_Node*)_M_buckets[__i];
   416     while (__cur != 0) {
   417       _Node* __next = __cur->_M_next;
   418       _M_delete_node(__cur);
   419       __cur = __next;
   420     }
   421     _M_buckets[__i] = 0;
   422   }
   423   _M_num_elements._M_data = 0;
   424 }
   425 
   426     
   427 template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
   428 void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
   429   ::_M_copy_from(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht)
   430 {
   431   _M_buckets.clear();
   432   _M_buckets.reserve(__ht._M_buckets.size());
   433   _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (void*) 0);
   434   _STLP_TRY {
   435     for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
   436       const _Node* __cur = (_Node*)__ht._M_buckets[__i];
   437       if (__cur) {
   438         _Node* __xcopy = _M_new_node(__cur->_M_val);
   439         _M_buckets[__i] = __xcopy;
   440 
   441         for (_Node* __next = __cur->_M_next; 
   442              __next; 
   443              __cur = __next, __next = __cur->_M_next) {
   444           __xcopy->_M_next = _M_new_node(__next->_M_val);
   445           __xcopy = __xcopy->_M_next;
   446         }
   447       }
   448     }
   449     _M_num_elements._M_data = __ht._M_num_elements._M_data;
   450   }
   451   _STLP_UNWIND(clear());
   452 }
   453 
   454 # undef __iterator__ 
   455 # undef const_iterator
   456 # undef __size_type__
   457 # undef __reference__
   458 # undef size_type       
   459 # undef value_type      
   460 # undef key_type        
   461 # undef _Node            
   462 # undef __stl_num_primes
   463 # undef hashtable
   464 
   465 _STLP_END_NAMESPACE
   466 
   467 #endif /*  _STLP_HASHTABLE_C */
   468 
   469 // Local Variables:
   470 // mode:C++
   471 // End: