1.1 --- a/epoc32/include/stdapis/stlportv5/stl/_hashtable.c Wed Mar 31 12:27:01 2010 +0100
1.2 +++ b/epoc32/include/stdapis/stlportv5/stl/_hashtable.c Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -1,5 +1,5 @@
1.4 /*
1.5 - *
1.6 + * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.
1.7 *
1.8 * Copyright (c) 1994
1.9 * Hewlett-Packard Company
1.10 @@ -10,13 +10,13 @@
1.11 * Copyright (c) 1997
1.12 * Moscow Center for SPARC Technology
1.13 *
1.14 - * Copyright (c) 1999
1.15 + * Copyright (c) 1999
1.16 * Boris Fomitchev
1.17 *
1.18 * This material is provided "as is", with absolutely no warranty expressed
1.19 * or implied. Any use is at your own risk.
1.20 *
1.21 - * Permission to use or copy this software for any purpose is hereby granted
1.22 + * Permission to use or copy this software for any purpose is hereby granted
1.23 * without fee, provided the above notices are retained on all copies.
1.24 * Permission to modify the code and to distribute modified code is granted,
1.25 * provided the above notices are retained, and a notice that the code was
1.26 @@ -27,16 +27,17 @@
1.27 #define _STLP_HASHTABLE_C
1.28
1.29 #ifndef _STLP_INTERNAL_HASHTABLE_H
1.30 -# include <stl/_hashtable.h>
1.31 -#endif
1.32 -
1.33 -#ifdef _STLP_DEBUG
1.34 -# define hashtable __WORKAROUND_DBG_RENAME(hashtable)
1.35 +# include <stl/_hashtable.h>
1.36 #endif
1.37
1.38 _STLP_BEGIN_NAMESPACE
1.39
1.40 -# define __PRIME_LIST_BODY { \
1.41 +#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
1.42 +
1.43 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.44 +
1.45 +# define __PRIME_LIST_BODY { \
1.46 + 7ul, 23ul, \
1.47 53ul, 97ul, 193ul, 389ul, 769ul, \
1.48 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, \
1.49 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, \
1.50 @@ -45,422 +46,432 @@
1.51 1610612741ul, 3221225473ul, 4294967291ul \
1.52 }
1.53
1.54 -#if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
1.55 -template <class _Tp>
1.56 -const size_t _Stl_prime<_Tp>::_M_list[__stl_num_primes] = __PRIME_LIST_BODY;
1.57 -#else
1.58 -__DECLARE_INSTANCE(const size_t,
1.59 - _Stl_prime_type::_M_list[], =__PRIME_LIST_BODY);
1.60 -#endif /* _STLP_STATIC_TEMPLATE_DATA */
1.61 +template <class _Dummy>
1.62 +size_t _STLP_CALL
1.63 +_Stl_prime<_Dummy>::_S_max_nb_buckets() {
1.64 + const size_t _list[] = __PRIME_LIST_BODY;
1.65 +# ifndef __MWERKS__
1.66 + return _list[(sizeof(_list)/sizeof(_list[0])) - 1];
1.67 +# else
1.68 + // it has to be 30 * (sizeof(_list[0]) to get the last element of the array
1.69 + return _list[30 * (sizeof(_list[0])/sizeof(size_t)) - 1]; // stupid MWERKS!
1.70 +# endif
1.71 +}
1.72
1.73 -# undef __PRIME_LIST_BODY
1.74 +template <class _Dummy>
1.75 +size_t _STLP_CALL
1.76 +_Stl_prime<_Dummy>::_S_next_size(size_t __n) {
1.77 + static const size_t _list[] = __PRIME_LIST_BODY;
1.78 + const size_t* __first = _list;
1.79 +# ifndef __MWERKS__
1.80 + const size_t* __last = _list + (sizeof(_list)/sizeof(_list[0]));
1.81 +# else
1.82 + // it has to be 30 * (sizeof(_list[0]) to get the last element of the array
1.83 + const size_t* __last = _list + ((30*sizeof(_list[0]))/sizeof(size_t)); // stupid MWERKS
1.84 +# endif
1.85 + const size_t* pos = __lower_bound(__first, __last, __n,
1.86 + __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
1.87 + return (pos == __last ? *(__last - 1) : *pos);
1.88 +}
1.89 +
1.90 +# undef __PRIME_LIST_BODY
1.91 +
1.92 +_STLP_MOVE_TO_STD_NAMESPACE
1.93 +
1.94 +#endif
1.95 +
1.96 +#if defined (_STLP_DEBUG)
1.97 +# define hashtable _STLP_NON_DBG_NAME(hashtable)
1.98 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.99 +#endif
1.100
1.101 // fbp: these defines are for outline methods definitions.
1.102 // needed to definitions to be portable. Should not be used in method bodies.
1.103
1.104 -# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
1.105 +#if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
1.106 # define __size_type__ size_t
1.107 # define size_type size_t
1.108 -# define value_type _Val
1.109 -# define key_type _Key
1.110 -# define _Node _Hashtable_node<_Val>
1.111 +# define value_type _Val
1.112 +# define key_type _Key
1.113 # define __reference__ _Val&
1.114
1.115 -# define __iterator__ _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>
1.116 -# define __const_iterator__ _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>
1.117 -# else
1.118 -# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::size_type
1.119 -# define __reference__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::reference
1.120 -# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::iterator
1.121 -# endif
1.122 +# define __iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits, \
1.123 + _Key, _HF, _ExK, _EqK, _All>
1.124 +# define __const_iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_ConstTraits, \
1.125 + _Key, _HF, _ExK, _EqK, _All>
1.126 +#else
1.127 +# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::size_type
1.128 +# define __reference__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::reference
1.129 +# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::iterator
1.130 +# define __const_iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::const_iterator
1.131 +#endif
1.132
1.133 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
1.134 - class _All>
1.135 -_Hashtable_node<_Val>*
1.136 -_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_skip_to_next() {
1.137 - size_t __bucket = _M_ht->_M_bkt_num(_M_cur->_M_val);
1.138 - size_t __h_sz;
1.139 - __h_sz = this->_M_ht->bucket_count();
1.140 +/*
1.141 + * This method is too difficult to implement for hashtable that do not
1.142 + * require a sorted operation on the stored type.
1.143 +template <class _Val, class _Key, class _HF,
1.144 + class _Traits, class _ExK, class _EqK, class _All>
1.145 +bool hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_equal(
1.146 + const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht1,
1.147 + const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht2) {
1.148 + return __ht1._M_buckets == __ht2._M_buckets &&
1.149 + __ht1._M_elems == __ht2._M_elems;
1.150 +}
1.151 +*/
1.152
1.153 - _Node* __i=0;
1.154 - while (__i==0 && ++__bucket < __h_sz)
1.155 - __i = (_Node*)_M_ht->_M_buckets[__bucket];
1.156 - return __i;
1.157 +/* Returns the iterator before the first iterator of the bucket __n and set
1.158 + * __n to the first previous bucket having the same first iterator as bucket
1.159 + * __n.
1.160 + */
1.161 +template <class _Val, class _Key, class _HF,
1.162 + class _Traits, class _ExK, class _EqK, class _All>
1.163 +__iterator__
1.164 +hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.165 + ::_M_before_begin(size_type &__n) const {
1.166 + return _S_before_begin(_M_elems, _M_buckets, __n);
1.167 }
1.168
1.169 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
1.170 - class _All>
1.171 -__size_type__
1.172 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_next_size(size_type __n) const {
1.173 - const size_type* __first = (const size_type*)_Stl_prime_type::_M_list;
1.174 - const size_type* __last = (const size_type*)_Stl_prime_type::_M_list + (int)__stl_num_primes;
1.175 - const size_type* pos = __lower_bound(__first, __last, __n, __less((size_type*)0), (ptrdiff_t*)0);
1.176 - return (pos == __last ? *(__last - 1) : *pos);
1.177 +template <class _Val, class _Key, class _HF,
1.178 + class _Traits, class _ExK, class _EqK, class _All>
1.179 +__iterator__
1.180 +hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.181 + ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
1.182 + size_type &__n) {
1.183 + _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);
1.184 + typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);
1.185 +
1.186 + _ElemsIte __pos(*__bpos);
1.187 + if (__pos == __mutable_elems.begin()) {
1.188 + __n = 0;
1.189 + return __mutable_elems.before_begin();
1.190 + }
1.191 +
1.192 + typename _BucketVector::const_iterator __bcur(__bpos);
1.193 + _BucketType *__pos_node = __pos._M_node;
1.194 + for (--__bcur; __pos_node == *__bcur; --__bcur) {}
1.195 +
1.196 + __n = __bcur - __buckets.begin() + 1;
1.197 + _ElemsIte __cur(*__bcur);
1.198 + _ElemsIte __prev = __cur++;
1.199 + for (; __cur != __pos; ++__prev, ++__cur) {}
1.200 + return __prev;
1.201 }
1.202
1.203 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.204 -bool
1.205 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_equal(
1.206 - const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht1,
1.207 - const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht2)
1.208 -{
1.209 - // typedef _Hashtable_node<_Val> _Node;
1.210 - if (__ht1.bucket_count() != __ht2.bucket_count())
1.211 - return false;
1.212 - for (size_t __n = 0; __n < __ht1.bucket_count(); ++__n) {
1.213 - const _Node* __cur1 = __ht1._M_get_bucket(__n);
1.214 - const _Node* __cur2 = __ht2._M_get_bucket(__n);
1.215 - for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val;
1.216 - __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
1.217 - {}
1.218 - if (__cur1 || __cur2)
1.219 - return false;
1.220 - }
1.221 - return true;
1.222 -}
1.223
1.224 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.225 -pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> , bool>
1.226 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.227 - ::insert_unique_noresize(const value_type& __obj)
1.228 -{
1.229 - const size_type __n = _M_bkt_num(__obj);
1.230 - _Node* __first = (_Node*)_M_buckets[__n];
1.231 +template <class _Val, class _Key, class _HF,
1.232 + class _Traits, class _ExK, class _EqK, class _All>
1.233 +__iterator__
1.234 +hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.235 + ::_M_insert_noresize(size_type __n, const value_type& __obj) {
1.236 + //We always insert this element as 1st in the bucket to not break
1.237 + //the elements order as equal elements must be kept next to each other.
1.238 + size_type __prev = __n;
1.239 + _ElemsIte __pos = _M_before_begin(__prev)._M_ite;
1.240
1.241 - for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
1.242 - if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
1.243 - return pair<iterator, bool>(iterator(__cur, this), false);
1.244 -
1.245 - _Node* __tmp = _M_new_node(__obj);
1.246 - __tmp->_M_next = __first;
1.247 - _M_buckets[__n] = __tmp;
1.248 - ++_M_num_elements._M_data;
1.249 - return pair<iterator, bool>(iterator(__tmp, this), true);
1.250 + fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1,
1.251 + _M_elems.insert_after(__pos, __obj)._M_node);
1.252 + ++_M_num_elements;
1.253 + return iterator(_ElemsIte(_M_buckets[__n]));
1.254 }
1.255
1.256 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.257 -__iterator__
1.258 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.259 - ::insert_equal_noresize(const value_type& __obj)
1.260 -{
1.261 +template <class _Val, class _Key, class _HF,
1.262 + class _Traits, class _ExK, class _EqK, class _All>
1.263 +pair<__iterator__, bool>
1.264 +hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.265 + ::insert_unique_noresize(const value_type& __obj) {
1.266 const size_type __n = _M_bkt_num(__obj);
1.267 - _Node* __first = (_Node*)_M_buckets[__n];
1.268 + _ElemsIte __cur(_M_buckets[__n]);
1.269 + _ElemsIte __last(_M_buckets[__n + 1]);
1.270
1.271 - for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
1.272 - if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
1.273 - _Node* __tmp = _M_new_node(__obj);
1.274 - __tmp->_M_next = __cur->_M_next;
1.275 - __cur->_M_next = __tmp;
1.276 - ++_M_num_elements._M_data;
1.277 - return iterator(__tmp, this);
1.278 + if (__cur != __last) {
1.279 + for (; __cur != __last; ++__cur) {
1.280 + if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
1.281 + //We check that equivalent keys have equals hash code as otherwise, on resize,
1.282 + //equivalent value might not be in the same bucket
1.283 + _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
1.284 + return pair<iterator, bool>(iterator(__cur), false);
1.285 + }
1.286 }
1.287 + /* Here we do not rely on the _M_insert_noresize method as we know
1.288 + * that we cannot break element orders, elements are unique, and
1.289 + * insertion after the first bucket element is faster than what is
1.290 + * done in _M_insert_noresize.
1.291 + */
1.292 + __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj);
1.293 + ++_M_num_elements;
1.294 + return pair<iterator, bool>(iterator(__cur), true);
1.295 + }
1.296
1.297 - _Node* __tmp = _M_new_node(__obj);
1.298 - __tmp->_M_next = __first;
1.299 - _M_buckets[__n] = __tmp;
1.300 - ++_M_num_elements._M_data;
1.301 - return iterator(__tmp, this);
1.302 + return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true);
1.303 }
1.304
1.305 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.306 -__reference__
1.307 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_insert(const value_type& __obj)
1.308 -{
1.309 - resize(_M_num_elements._M_data + 1);
1.310 +template <class _Val, class _Key, class _HF,
1.311 + class _Traits, class _ExK, class _EqK, class _All>
1.312 +__iterator__
1.313 +hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.314 + ::insert_equal_noresize(const value_type& __obj) {
1.315 + const size_type __n = _M_bkt_num(__obj);
1.316 + {
1.317 + _ElemsIte __cur(_M_buckets[__n]);
1.318 + _ElemsIte __last(_M_buckets[__n + 1]);
1.319
1.320 - size_type __n = _M_bkt_num(__obj);
1.321 - _Node* __first = (_Node*)_M_buckets[__n];
1.322 + for (; __cur != __last; ++__cur) {
1.323 + if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
1.324 + //We check that equivalent keys have equals hash code as otherwise, on resize,
1.325 + //equivalent value might not be in the same bucket
1.326 + _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
1.327 + ++_M_num_elements;
1.328 + return _M_elems.insert_after(__cur, __obj);
1.329 + }
1.330 + }
1.331 + }
1.332
1.333 - _Node* __tmp = _M_new_node(__obj);
1.334 - __tmp->_M_next = __first;
1.335 - _M_buckets[__n] = __tmp;
1.336 - ++_M_num_elements._M_data;
1.337 - return __tmp->_M_val;
1.338 + return _M_insert_noresize(__n, __obj);
1.339 }
1.340
1.341 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.342 -__reference__
1.343 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::find_or_insert(const value_type& __obj)
1.344 -{
1.345 +template <class _Val, class _Key, class _HF,
1.346 + class _Traits, class _ExK, class _EqK, class _All>
1.347 +__reference__
1.348 +hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.349 + ::_M_insert(const value_type& __obj) {
1.350 + resize(_M_num_elements + 1);
1.351 + return *insert_unique_noresize(__obj).first;
1.352 +}
1.353
1.354 +/*
1.355 +template <class _Val, class _Key, class _HF,
1.356 + class _Traits, class _ExK, class _EqK, class _All>
1.357 +__reference__
1.358 +hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.359 + ::find_or_insert(const value_type& __obj) {
1.360 _Node* __first = _M_find(_M_get_key(__obj));
1.361 if (__first)
1.362 return __first->_M_val;
1.363 else
1.364 return _M_insert(__obj);
1.365 }
1.366 +*/
1.367
1.368 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.369 -pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>,
1.370 - _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> >
1.371 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::equal_range(const key_type& __key)
1.372 -{
1.373 - typedef pair<iterator, iterator> _Pii;
1.374 +template <class _Val, class _Key, class _HF,
1.375 + class _Traits, class _ExK, class _EqK, class _All>
1.376 +__size_type__
1.377 +hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.378 + ::erase(const key_type& __key) {
1.379 const size_type __n = _M_bkt_num_key(__key);
1.380
1.381 - for (_Node* __first = (_Node*)_M_buckets[__n]; __first; __first = __first->_M_next)
1.382 - if (_M_equals(_M_get_key(__first->_M_val), __key)) {
1.383 - for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next)
1.384 - if (!_M_equals(_M_get_key(__cur->_M_val), __key))
1.385 - return _Pii(iterator(__first, this), iterator(__cur, this));
1.386 - for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
1.387 - if (_M_buckets[__m])
1.388 - return _Pii(iterator(__first, this),
1.389 - iterator((_Node*)_M_buckets[__m], this));
1.390 - return _Pii(iterator(__first, this), end());
1.391 - }
1.392 - return _Pii(end(), end());
1.393 -}
1.394 + _ElemsIte __cur(_M_buckets[__n]);
1.395 + _ElemsIte __last(_M_buckets[__n + 1]);
1.396 + if (__cur == __last)
1.397 + return 0;
1.398
1.399 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.400 -pair< _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>,
1.401 - _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> >
1.402 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.403 - ::equal_range(const key_type& __key) const
1.404 -{
1.405 - typedef pair<const_iterator, const_iterator> _Pii;
1.406 - const size_type __n = _M_bkt_num_key(__key);
1.407 -
1.408 - for (const _Node* __first = (_Node*)_M_buckets[__n] ;
1.409 - __first;
1.410 - __first = __first->_M_next) {
1.411 - if (_M_equals(_M_get_key(__first->_M_val), __key)) {
1.412 - for (const _Node* __cur = __first->_M_next;
1.413 - __cur;
1.414 - __cur = __cur->_M_next)
1.415 - if (!_M_equals(_M_get_key(__cur->_M_val), __key))
1.416 - return _Pii(const_iterator(__first, this),
1.417 - const_iterator(__cur, this));
1.418 - for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
1.419 - if (_M_buckets[__m])
1.420 - return _Pii(const_iterator(__first, this),
1.421 - const_iterator((_Node*)_M_buckets[__m], this));
1.422 - return _Pii(const_iterator(__first, this), end());
1.423 + size_type __erased = 0;
1.424 + if (_M_equals(_M_get_key(*__cur), __key)) {
1.425 + //We look for the pos before __cur:
1.426 + size_type __prev_b = __n;
1.427 + _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
1.428 + do {
1.429 + __cur = _M_elems.erase_after(__prev);
1.430 + ++__erased;
1.431 + } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
1.432 + fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node);
1.433 + }
1.434 + else {
1.435 + _ElemsIte __prev = __cur++;
1.436 + for (; __cur != __last; ++__prev, ++__cur) {
1.437 + if (_M_equals(_M_get_key(*__cur), __key)) {
1.438 + do {
1.439 + __cur = _M_elems.erase_after(__prev);
1.440 + ++__erased;
1.441 + } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
1.442 + break;
1.443 + }
1.444 }
1.445 }
1.446 - return _Pii(end(), end());
1.447 -}
1.448
1.449 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.450 -__size_type__
1.451 -hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const key_type& __key)
1.452 -{
1.453 - const size_type __n = _M_bkt_num_key(__key);
1.454 - _Node* __first = (_Node*)_M_buckets[__n];
1.455 - size_type __erased = 0;
1.456 -
1.457 - if (__first) {
1.458 - _Node* __cur = __first;
1.459 - _Node* __next = __cur->_M_next;
1.460 - while (__next) {
1.461 - if (_M_equals(_M_get_key(__next->_M_val), __key)) {
1.462 - __cur->_M_next = __next->_M_next;
1.463 - _M_delete_node(__next);
1.464 - __next = __cur->_M_next;
1.465 - ++__erased;
1.466 - --_M_num_elements._M_data;
1.467 - }
1.468 - else {
1.469 - __cur = __next;
1.470 - __next = __cur->_M_next;
1.471 - }
1.472 - }
1.473 - if (_M_equals(_M_get_key(__first->_M_val), __key)) {
1.474 - _M_buckets[__n] = __first->_M_next;
1.475 - _M_delete_node(__first);
1.476 - ++__erased;
1.477 - --_M_num_elements._M_data;
1.478 - }
1.479 - }
1.480 + _M_num_elements -= __erased;
1.481 return __erased;
1.482 }
1.483
1.484 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.485 -void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const const_iterator& __it)
1.486 -{
1.487 - // const iterator& __it = __REINTERPRET_CAST(const iterator&,_c_it);
1.488 - const _Node* __p = __it._M_cur;
1.489 - if (__p) {
1.490 - const size_type __n = _M_bkt_num(__p->_M_val);
1.491 - _Node* __cur = (_Node*)_M_buckets[__n];
1.492 +template <class _Val, class _Key, class _HF,
1.493 + class _Traits, class _ExK, class _EqK, class _All>
1.494 +void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.495 + ::erase(const_iterator __it) {
1.496 + const size_type __n = _M_bkt_num(*__it);
1.497 + _ElemsIte __cur(_M_buckets[__n]);
1.498
1.499 - if (__cur == __p) {
1.500 - _M_buckets[__n] = __cur->_M_next;
1.501 - _M_delete_node(__cur);
1.502 - --_M_num_elements._M_data;
1.503 - }
1.504 - else {
1.505 - _Node* __next = __cur->_M_next;
1.506 - while (__next) {
1.507 - if (__next == __p) {
1.508 - __cur->_M_next = __next->_M_next;
1.509 - _M_delete_node(__next);
1.510 - --_M_num_elements._M_data;
1.511 - break;
1.512 - }
1.513 - else {
1.514 - __cur = __next;
1.515 - __next = __cur->_M_next;
1.516 - }
1.517 + if (__cur == __it._M_ite) {
1.518 + size_type __prev_b = __n;
1.519 + _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
1.520 + fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
1.521 + _M_elems.erase_after(__prev)._M_node);
1.522 + --_M_num_elements;
1.523 + }
1.524 + else {
1.525 + _ElemsIte __prev = __cur++;
1.526 + _ElemsIte __last(_M_buckets[__n + 1]);
1.527 + for (; __cur != __last; ++__prev, ++__cur) {
1.528 + if (__cur == __it._M_ite) {
1.529 + _M_elems.erase_after(__prev);
1.530 + --_M_num_elements;
1.531 + break;
1.532 }
1.533 }
1.534 }
1.535 }
1.536
1.537 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.538 -void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.539 - ::erase(const_iterator _c_first, const_iterator _c_last)
1.540 -{
1.541 - iterator& __first = (iterator&)_c_first;
1.542 - iterator& __last = (iterator&)_c_last;
1.543 - size_type __f_bucket = __first._M_cur ?
1.544 - _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
1.545 - size_type __l_bucket = __last._M_cur ?
1.546 - _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
1.547 - if (__first._M_cur == __last._M_cur)
1.548 +template <class _Val, class _Key, class _HF,
1.549 + class _Traits, class _ExK, class _EqK, class _All>
1.550 +void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.551 + ::erase(const_iterator __first, const_iterator __last) {
1.552 + if (__first == __last)
1.553 return;
1.554 - else if (__f_bucket == __l_bucket)
1.555 - _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
1.556 + size_type __f_bucket = _M_bkt_num(*__first);
1.557 + size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1);
1.558 +
1.559 + _ElemsIte __cur(_M_buckets[__f_bucket]);
1.560 + _ElemsIte __prev;
1.561 + if (__cur == __first._M_ite) {
1.562 + __prev = _M_before_begin(__f_bucket)._M_ite;
1.563 + }
1.564 else {
1.565 - _M_erase_bucket(__f_bucket, __first._M_cur, 0);
1.566 - for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
1.567 - _M_erase_bucket(__n, 0);
1.568 - if (__l_bucket != _M_buckets.size())
1.569 - _M_erase_bucket(__l_bucket, __last._M_cur);
1.570 + _ElemsIte __last(_M_buckets[++__f_bucket]);
1.571 + __prev = __cur++;
1.572 + for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur);
1.573 }
1.574 + //We do not use the slist::erase_after method taking a range to count the
1.575 + //number of erased elements:
1.576 + while (__cur != __last._M_ite) {
1.577 + __cur = _M_elems.erase_after(__prev);
1.578 + --_M_num_elements;
1.579 + }
1.580 + fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
1.581 }
1.582
1.583 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.584 -void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.585 - ::resize(size_type __num_elements_hint)
1.586 -{
1.587 - const size_type __old_n = _M_buckets.size();
1.588 - if (__num_elements_hint > __old_n) {
1.589 - const size_type __n = _M_next_size(__num_elements_hint);
1.590 - if (__n > __old_n) {
1.591 - _BucketVector __tmp(__n, (void*)(0),
1.592 - _M_buckets.get_allocator());
1.593 - _STLP_PUSH_CLEANUP_ITEM(_BucketVector, &__tmp);
1.594 - _STLP_TRY {
1.595 - for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
1.596 - _Node* __first = (_Node*)_M_buckets[__bucket];
1.597 - while (__first) {
1.598 - size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
1.599 - _M_buckets[__bucket] = __first->_M_next;
1.600 - __first->_M_next = (_Node*)__tmp[__new_bucket];
1.601 - __tmp[__new_bucket] = __first;
1.602 - __first = (_Node*)_M_buckets[__bucket];
1.603 - }
1.604 - }
1.605 - _M_buckets.swap(__tmp);
1.606 - }
1.607 - _STLP_CATCH_ALL {
1.608 - for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
1.609 - while (__tmp[__bucket]) {
1.610 - _Node* __next = ((_Node*)__tmp[__bucket])->_M_next;
1.611 - _M_delete_node((_Node*)__tmp[__bucket]);
1.612 - __tmp[__bucket] = __next;
1.613 - }
1.614 - }
1.615 - _STLP_RETHROW;
1.616 - }
1.617 -#ifdef _STLP_USE_TRAP_LEAVE
1.618 - CleanupStack::Pop();
1.619 +template <class _Val, class _Key, class _HF,
1.620 + class _Traits, class _ExK, class _EqK, class _All>
1.621 +void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.622 + ::rehash(size_type __num_buckets_hint) {
1.623 + if ((bucket_count() >= __num_buckets_hint) &&
1.624 + (max_load_factor() > load_factor()))
1.625 + return;
1.626 +
1.627 + //Here if max_load_factor is lower than 1.0 the resulting value might not be representable
1.628 + //as a size_type. The result concerning the respect of the max_load_factor will then be
1.629 + //undefined.
1.630 + __num_buckets_hint = (max) (__num_buckets_hint, (size_type)((float)size() / max_load_factor()));
1.631 + size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
1.632 + _M_rehash(__num_buckets);
1.633 +}
1.634 +
1.635 +template <class _Val, class _Key, class _HF,
1.636 + class _Traits, class _ExK, class _EqK, class _All>
1.637 +void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.638 + ::resize(size_type __num_elements_hint) {
1.639 + if (((float)__num_elements_hint / (float)bucket_count() <= max_load_factor()) &&
1.640 + (max_load_factor() >= load_factor())) {
1.641 + return;
1.642 + }
1.643 +
1.644 + size_type __num_buckets_hint = (size_type)((float)(max) (__num_elements_hint, size()) / max_load_factor());
1.645 + size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
1.646 +#if defined (_STLP_DEBUG)
1.647 + _M_check();
1.648 #endif
1.649 + _M_rehash(__num_buckets);
1.650 +}
1.651
1.652 +template <class _Val, class _Key, class _HF,
1.653 + class _Traits, class _ExK, class _EqK, class _All>
1.654 +void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.655 + ::_M_rehash(size_type __num_buckets) {
1.656 + _ElemsCont __tmp_elems(_M_elems.get_allocator());
1.657 + _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator());
1.658 + _ElemsIte __cur, __last(_M_elems.end());
1.659 + while (!_M_elems.empty()) {
1.660 + __cur = _M_elems.begin();
1.661 + size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets);
1.662 + _ElemsIte __ite(__cur), __before_ite(__cur);
1.663 + for (++__ite;
1.664 + __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite));
1.665 + ++__ite, ++__before_ite) {}
1.666 + size_type __prev_bucket = __new_bucket;
1.667 + _ElemsIte __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite;
1.668 + __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite);
1.669 + fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node);
1.670 + }
1.671 + _M_elems.swap(__tmp_elems);
1.672 + _M_buckets.swap(__tmp);
1.673 +}
1.674 +
1.675 +#if defined (_STLP_DEBUG)
1.676 +template <class _Val, class _Key, class _HF,
1.677 + class _Traits, class _ExK, class _EqK, class _All>
1.678 +void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_check() const {
1.679 + //We check that hash code of stored keys haven't change and also that equivalent
1.680 + //relation hasn't been modified
1.681 + size_t __num_buckets = bucket_count();
1.682 + for (size_t __b = 0; __b < __num_buckets; ++__b) {
1.683 + _ElemsIte __cur(_M_buckets[__b]), __last(_M_buckets[__b + 1]);
1.684 + _ElemsIte __fst(__cur), __snd(__cur);
1.685 + for (; __cur != __last; ++__cur) {
1.686 + _STLP_ASSERT( _M_bkt_num(*__cur, __num_buckets) == __b )
1.687 + _STLP_ASSERT( !_M_equals(_M_get_key(*__fst), _M_get_key(*__cur)) || _M_equals(_M_get_key(*__snd), _M_get_key(*__cur)) )
1.688 + if (__fst != __snd)
1.689 + ++__fst;
1.690 + if (__snd != __cur)
1.691 + ++__snd;
1.692 }
1.693 }
1.694 }
1.695 +#endif
1.696
1.697 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.698 -void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.699 - ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1.700 -{
1.701 - _Node* __cur = (_Node*)_M_buckets[__n];
1.702 - if (__cur == __first)
1.703 - _M_erase_bucket(__n, __last);
1.704 - else {
1.705 - _Node* __next;
1.706 - for (__next = __cur->_M_next;
1.707 - __next != __first;
1.708 - __cur = __next, __next = __cur->_M_next)
1.709 - ;
1.710 - while (__next != __last) {
1.711 - __cur->_M_next = __next->_M_next;
1.712 - _M_delete_node(__next);
1.713 - __next = __cur->_M_next;
1.714 - --_M_num_elements._M_data;
1.715 +template <class _Val, class _Key, class _HF,
1.716 + class _Traits, class _ExK, class _EqK, class _All>
1.717 +void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::clear() {
1.718 + _M_elems.clear();
1.719 + _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0));
1.720 + _M_num_elements = 0;
1.721 +}
1.722 +
1.723 +template <class _Val, class _Key, class _HF,
1.724 + class _Traits, class _ExK, class _EqK, class _All>
1.725 +void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.726 + ::_M_copy_from(const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht) {
1.727 + _M_elems.clear();
1.728 + _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end());
1.729 + _M_buckets.resize(__ht._M_buckets.size());
1.730 + _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end());
1.731 + _ElemsIte __dst(_M_elems.begin());
1.732 + typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()),
1.733 + __src_end_b(__ht._M_buckets.end());
1.734 + typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end());
1.735 + for (; __src != __src_end; ++__src, ++__dst) {
1.736 + for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) {
1.737 + if (*__src_b == __src._M_node) {
1.738 + *__dst_b = __dst._M_node;
1.739 + }
1.740 + else
1.741 + break;
1.742 }
1.743 }
1.744 + fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0));
1.745 + _M_num_elements = __ht._M_num_elements;
1.746 + _M_max_load_factor = __ht._M_max_load_factor;
1.747 }
1.748
1.749 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.750 -void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.751 - ::_M_erase_bucket(const size_type __n, _Node* __last)
1.752 -{
1.753 - _Node* __cur = (_Node*)_M_buckets[__n];
1.754 - while (__cur && __cur != __last) {
1.755 - _Node* __next = __cur->_M_next;
1.756 - _M_delete_node(__cur);
1.757 - __cur = __next;
1.758 - _M_buckets[__n] = __cur;
1.759 - --_M_num_elements._M_data;
1.760 - }
1.761 -}
1.762 +#undef __iterator__
1.763 +#undef const_iterator
1.764 +#undef __size_type__
1.765 +#undef __reference__
1.766 +#undef size_type
1.767 +#undef value_type
1.768 +#undef key_type
1.769 +#undef __stl_num_primes
1.770
1.771 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.772 -void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::clear()
1.773 -{
1.774 - for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
1.775 - _Node* __cur = (_Node*)_M_buckets[__i];
1.776 - while (__cur != 0) {
1.777 - _Node* __next = __cur->_M_next;
1.778 - _M_delete_node(__cur);
1.779 - __cur = __next;
1.780 - }
1.781 - _M_buckets[__i] = 0;
1.782 - }
1.783 - _M_num_elements._M_data = 0;
1.784 -}
1.785 -
1.786 -
1.787 -template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.788 -void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.789 - ::_M_copy_from(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht)
1.790 -{
1.791 - _M_buckets.clear();
1.792 - _M_buckets.reserve(__ht._M_buckets.size());
1.793 - _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (void*) 0);
1.794 - _STLP_TRY {
1.795 - for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1.796 - const _Node* __cur = (_Node*)__ht._M_buckets[__i];
1.797 - if (__cur) {
1.798 - _Node* __xcopy = _M_new_node(__cur->_M_val);
1.799 - _M_buckets[__i] = __xcopy;
1.800 -
1.801 - for (_Node* __next = __cur->_M_next;
1.802 - __next;
1.803 - __cur = __next, __next = __cur->_M_next) {
1.804 - __xcopy->_M_next = _M_new_node(__next->_M_val);
1.805 - __xcopy = __xcopy->_M_next;
1.806 - }
1.807 - }
1.808 - }
1.809 - _M_num_elements._M_data = __ht._M_num_elements._M_data;
1.810 - }
1.811 - _STLP_UNWIND(clear());
1.812 -}
1.813 -
1.814 -# undef __iterator__
1.815 -# undef const_iterator
1.816 -# undef __size_type__
1.817 -# undef __reference__
1.818 -# undef size_type
1.819 -# undef value_type
1.820 -# undef key_type
1.821 -# undef _Node
1.822 -# undef __stl_num_primes
1.823 -# undef hashtable
1.824 +#if defined (_STLP_DEBUG)
1.825 +# undef hashtable
1.826 +_STLP_MOVE_TO_STD_NAMESPACE
1.827 +#endif
1.828
1.829 _STLP_END_NAMESPACE
1.830