test: epoc32/include/stdapis/stlportv5/stl/

     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

    29 #ifndef _STLP_INTERNAL_HASHTABLE_H

    30 # include <stl/_hashtable.h>

    31 #endif

    33 #ifdef _STLP_DEBUG

    34 #  define hashtable __WORKAROUND_DBG_RENAME(hashtable)

    35 #endif

    37 _STLP_BEGIN_NAMESPACE

    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 }

    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 */

    56 # undef __PRIME_LIST_BODY

    58 // fbp: these defines are for outline methods definitions.

    59 // needed to definitions to be portable. Should not be used in method bodies.

    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&

    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

    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();

    85   _Node* __i=0;

    86   while (__i==0 && ++__bucket < __h_sz)

    87     __i = (_Node*)_M_ht->_M_buckets[__bucket];

    88   return __i;

    89 }

    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 }

   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 }

   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];

   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);

   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 }

   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];

   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     }

   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 }

   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);

   171   size_type __n = _M_bkt_num(__obj);

   172   _Node* __first = (_Node*)_M_buckets[__n];

   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 }

   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 {

   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 }

   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);

   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 }

   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);

   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 }

   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;

   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 }

   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];

   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 }

   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 }

   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

   371     }

   372   }

   373 }

   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 }

   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 }

   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 }

   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;

   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 }

   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

   465 _STLP_END_NAMESPACE

   467 #endif /*  _STLP_HASHTABLE_C */

   469 // Local Variables:

   470 // mode:C++

   471 // End:

author	William Roberts <williamr@symbian.org>
	Wed, 31 Mar 2010 12:27:01 +0100
branch	Symbian2
changeset 3	e1b950c65cb4
parent 2	epoc32/include/stdapis/stlport/stl/_hashtable.c@2fe1408b6811
child 4	837f303aceeb
permissions	-rw-r--r--