1.1 --- a/epoc32/include/stdapis/stlport/stl/_hashtable.c Tue Nov 24 13:55:44 2009 +0000
1.2 +++ b/epoc32/include/stdapis/stlport/stl/_hashtable.c Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -1,1 +1,471 @@
1.4 -_hashtable.c
1.5 +/*
1.6 + *
1.7 + *
1.8 + * Copyright (c) 1994
1.9 + * Hewlett-Packard Company
1.10 + *
1.11 + * Copyright (c) 1996,1997
1.12 + * Silicon Graphics Computer Systems, Inc.
1.13 + *
1.14 + * Copyright (c) 1997
1.15 + * Moscow Center for SPARC Technology
1.16 + *
1.17 + * Copyright (c) 1999
1.18 + * Boris Fomitchev
1.19 + *
1.20 + * This material is provided "as is", with absolutely no warranty expressed
1.21 + * or implied. Any use is at your own risk.
1.22 + *
1.23 + * Permission to use or copy this software for any purpose is hereby granted
1.24 + * without fee, provided the above notices are retained on all copies.
1.25 + * Permission to modify the code and to distribute modified code is granted,
1.26 + * provided the above notices are retained, and a notice that the code was
1.27 + * modified is included with the above copyright notice.
1.28 + *
1.29 + */
1.30 +#ifndef _STLP_HASHTABLE_C
1.31 +#define _STLP_HASHTABLE_C
1.32 +
1.33 +#ifndef _STLP_INTERNAL_HASHTABLE_H
1.34 +# include <stl/_hashtable.h>
1.35 +#endif
1.36 +
1.37 +#ifdef _STLP_DEBUG
1.38 +# define hashtable __WORKAROUND_DBG_RENAME(hashtable)
1.39 +#endif
1.40 +
1.41 +_STLP_BEGIN_NAMESPACE
1.42 +
1.43 +# define __PRIME_LIST_BODY { \
1.44 + 53ul, 97ul, 193ul, 389ul, 769ul, \
1.45 + 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, \
1.46 + 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, \
1.47 + 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, \
1.48 + 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,\
1.49 + 1610612741ul, 3221225473ul, 4294967291ul \
1.50 +}
1.51 +
1.52 +#if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
1.53 +template <class _Tp>
1.54 +const size_t _Stl_prime<_Tp>::_M_list[__stl_num_primes] = __PRIME_LIST_BODY;
1.55 +#else
1.56 +__DECLARE_INSTANCE(const size_t,
1.57 + _Stl_prime_type::_M_list[], =__PRIME_LIST_BODY);
1.58 +#endif /* _STLP_STATIC_TEMPLATE_DATA */
1.59 +
1.60 +# undef __PRIME_LIST_BODY
1.61 +
1.62 +// fbp: these defines are for outline methods definitions.
1.63 +// needed to definitions to be portable. Should not be used in method bodies.
1.64 +
1.65 +# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
1.66 +# define __size_type__ size_t
1.67 +# define size_type size_t
1.68 +# define value_type _Val
1.69 +# define key_type _Key
1.70 +# define _Node _Hashtable_node<_Val>
1.71 +# define __reference__ _Val&
1.72 +
1.73 +# define __iterator__ _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>
1.74 +# define __const_iterator__ _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>
1.75 +# else
1.76 +# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::size_type
1.77 +# define __reference__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::reference
1.78 +# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::iterator
1.79 +# endif
1.80 +
1.81 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
1.82 + class _All>
1.83 +_Hashtable_node<_Val>*
1.84 +_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_skip_to_next() {
1.85 + size_t __bucket = _M_ht->_M_bkt_num(_M_cur->_M_val);
1.86 + size_t __h_sz;
1.87 + __h_sz = this->_M_ht->bucket_count();
1.88 +
1.89 + _Node* __i=0;
1.90 + while (__i==0 && ++__bucket < __h_sz)
1.91 + __i = (_Node*)_M_ht->_M_buckets[__bucket];
1.92 + return __i;
1.93 +}
1.94 +
1.95 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
1.96 + class _All>
1.97 +__size_type__
1.98 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_next_size(size_type __n) const {
1.99 + const size_type* __first = (const size_type*)_Stl_prime_type::_M_list;
1.100 + const size_type* __last = (const size_type*)_Stl_prime_type::_M_list + (int)__stl_num_primes;
1.101 + const size_type* pos = __lower_bound(__first, __last, __n, __less((size_type*)0), (ptrdiff_t*)0);
1.102 + return (pos == __last ? *(__last - 1) : *pos);
1.103 +}
1.104 +
1.105 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.106 +bool
1.107 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_equal(
1.108 + const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht1,
1.109 + const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht2)
1.110 +{
1.111 + // typedef _Hashtable_node<_Val> _Node;
1.112 + if (__ht1.bucket_count() != __ht2.bucket_count())
1.113 + return false;
1.114 + for (size_t __n = 0; __n < __ht1.bucket_count(); ++__n) {
1.115 + const _Node* __cur1 = __ht1._M_get_bucket(__n);
1.116 + const _Node* __cur2 = __ht2._M_get_bucket(__n);
1.117 + for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val;
1.118 + __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
1.119 + {}
1.120 + if (__cur1 || __cur2)
1.121 + return false;
1.122 + }
1.123 + return true;
1.124 +}
1.125 +
1.126 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.127 +pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> , bool>
1.128 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.129 + ::insert_unique_noresize(const value_type& __obj)
1.130 +{
1.131 + const size_type __n = _M_bkt_num(__obj);
1.132 + _Node* __first = (_Node*)_M_buckets[__n];
1.133 +
1.134 + for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
1.135 + if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
1.136 + return pair<iterator, bool>(iterator(__cur, this), false);
1.137 +
1.138 + _Node* __tmp = _M_new_node(__obj);
1.139 + __tmp->_M_next = __first;
1.140 + _M_buckets[__n] = __tmp;
1.141 + ++_M_num_elements._M_data;
1.142 + return pair<iterator, bool>(iterator(__tmp, this), true);
1.143 +}
1.144 +
1.145 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.146 +__iterator__
1.147 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.148 + ::insert_equal_noresize(const value_type& __obj)
1.149 +{
1.150 + const size_type __n = _M_bkt_num(__obj);
1.151 + _Node* __first = (_Node*)_M_buckets[__n];
1.152 +
1.153 + for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
1.154 + if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
1.155 + _Node* __tmp = _M_new_node(__obj);
1.156 + __tmp->_M_next = __cur->_M_next;
1.157 + __cur->_M_next = __tmp;
1.158 + ++_M_num_elements._M_data;
1.159 + return iterator(__tmp, this);
1.160 + }
1.161 +
1.162 + _Node* __tmp = _M_new_node(__obj);
1.163 + __tmp->_M_next = __first;
1.164 + _M_buckets[__n] = __tmp;
1.165 + ++_M_num_elements._M_data;
1.166 + return iterator(__tmp, this);
1.167 +}
1.168 +
1.169 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.170 +__reference__
1.171 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_insert(const value_type& __obj)
1.172 +{
1.173 + resize(_M_num_elements._M_data + 1);
1.174 +
1.175 + size_type __n = _M_bkt_num(__obj);
1.176 + _Node* __first = (_Node*)_M_buckets[__n];
1.177 +
1.178 + _Node* __tmp = _M_new_node(__obj);
1.179 + __tmp->_M_next = __first;
1.180 + _M_buckets[__n] = __tmp;
1.181 + ++_M_num_elements._M_data;
1.182 + return __tmp->_M_val;
1.183 +}
1.184 +
1.185 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.186 +__reference__
1.187 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::find_or_insert(const value_type& __obj)
1.188 +{
1.189 +
1.190 + _Node* __first = _M_find(_M_get_key(__obj));
1.191 + if (__first)
1.192 + return __first->_M_val;
1.193 + else
1.194 + return _M_insert(__obj);
1.195 +}
1.196 +
1.197 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.198 +pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>,
1.199 + _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> >
1.200 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::equal_range(const key_type& __key)
1.201 +{
1.202 + typedef pair<iterator, iterator> _Pii;
1.203 + const size_type __n = _M_bkt_num_key(__key);
1.204 +
1.205 + for (_Node* __first = (_Node*)_M_buckets[__n]; __first; __first = __first->_M_next)
1.206 + if (_M_equals(_M_get_key(__first->_M_val), __key)) {
1.207 + for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next)
1.208 + if (!_M_equals(_M_get_key(__cur->_M_val), __key))
1.209 + return _Pii(iterator(__first, this), iterator(__cur, this));
1.210 + for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
1.211 + if (_M_buckets[__m])
1.212 + return _Pii(iterator(__first, this),
1.213 + iterator((_Node*)_M_buckets[__m], this));
1.214 + return _Pii(iterator(__first, this), end());
1.215 + }
1.216 + return _Pii(end(), end());
1.217 +}
1.218 +
1.219 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.220 +pair< _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>,
1.221 + _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> >
1.222 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.223 + ::equal_range(const key_type& __key) const
1.224 +{
1.225 + typedef pair<const_iterator, const_iterator> _Pii;
1.226 + const size_type __n = _M_bkt_num_key(__key);
1.227 +
1.228 + for (const _Node* __first = (_Node*)_M_buckets[__n] ;
1.229 + __first;
1.230 + __first = __first->_M_next) {
1.231 + if (_M_equals(_M_get_key(__first->_M_val), __key)) {
1.232 + for (const _Node* __cur = __first->_M_next;
1.233 + __cur;
1.234 + __cur = __cur->_M_next)
1.235 + if (!_M_equals(_M_get_key(__cur->_M_val), __key))
1.236 + return _Pii(const_iterator(__first, this),
1.237 + const_iterator(__cur, this));
1.238 + for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
1.239 + if (_M_buckets[__m])
1.240 + return _Pii(const_iterator(__first, this),
1.241 + const_iterator((_Node*)_M_buckets[__m], this));
1.242 + return _Pii(const_iterator(__first, this), end());
1.243 + }
1.244 + }
1.245 + return _Pii(end(), end());
1.246 +}
1.247 +
1.248 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.249 +__size_type__
1.250 +hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const key_type& __key)
1.251 +{
1.252 + const size_type __n = _M_bkt_num_key(__key);
1.253 + _Node* __first = (_Node*)_M_buckets[__n];
1.254 + size_type __erased = 0;
1.255 +
1.256 + if (__first) {
1.257 + _Node* __cur = __first;
1.258 + _Node* __next = __cur->_M_next;
1.259 + while (__next) {
1.260 + if (_M_equals(_M_get_key(__next->_M_val), __key)) {
1.261 + __cur->_M_next = __next->_M_next;
1.262 + _M_delete_node(__next);
1.263 + __next = __cur->_M_next;
1.264 + ++__erased;
1.265 + --_M_num_elements._M_data;
1.266 + }
1.267 + else {
1.268 + __cur = __next;
1.269 + __next = __cur->_M_next;
1.270 + }
1.271 + }
1.272 + if (_M_equals(_M_get_key(__first->_M_val), __key)) {
1.273 + _M_buckets[__n] = __first->_M_next;
1.274 + _M_delete_node(__first);
1.275 + ++__erased;
1.276 + --_M_num_elements._M_data;
1.277 + }
1.278 + }
1.279 + return __erased;
1.280 +}
1.281 +
1.282 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.283 +void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const const_iterator& __it)
1.284 +{
1.285 + // const iterator& __it = __REINTERPRET_CAST(const iterator&,_c_it);
1.286 + const _Node* __p = __it._M_cur;
1.287 + if (__p) {
1.288 + const size_type __n = _M_bkt_num(__p->_M_val);
1.289 + _Node* __cur = (_Node*)_M_buckets[__n];
1.290 +
1.291 + if (__cur == __p) {
1.292 + _M_buckets[__n] = __cur->_M_next;
1.293 + _M_delete_node(__cur);
1.294 + --_M_num_elements._M_data;
1.295 + }
1.296 + else {
1.297 + _Node* __next = __cur->_M_next;
1.298 + while (__next) {
1.299 + if (__next == __p) {
1.300 + __cur->_M_next = __next->_M_next;
1.301 + _M_delete_node(__next);
1.302 + --_M_num_elements._M_data;
1.303 + break;
1.304 + }
1.305 + else {
1.306 + __cur = __next;
1.307 + __next = __cur->_M_next;
1.308 + }
1.309 + }
1.310 + }
1.311 + }
1.312 +}
1.313 +
1.314 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.315 +void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.316 + ::erase(const_iterator _c_first, const_iterator _c_last)
1.317 +{
1.318 + iterator& __first = (iterator&)_c_first;
1.319 + iterator& __last = (iterator&)_c_last;
1.320 + size_type __f_bucket = __first._M_cur ?
1.321 + _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
1.322 + size_type __l_bucket = __last._M_cur ?
1.323 + _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
1.324 + if (__first._M_cur == __last._M_cur)
1.325 + return;
1.326 + else if (__f_bucket == __l_bucket)
1.327 + _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
1.328 + else {
1.329 + _M_erase_bucket(__f_bucket, __first._M_cur, 0);
1.330 + for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
1.331 + _M_erase_bucket(__n, 0);
1.332 + if (__l_bucket != _M_buckets.size())
1.333 + _M_erase_bucket(__l_bucket, __last._M_cur);
1.334 + }
1.335 +}
1.336 +
1.337 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.338 +void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.339 + ::resize(size_type __num_elements_hint)
1.340 +{
1.341 + const size_type __old_n = _M_buckets.size();
1.342 + if (__num_elements_hint > __old_n) {
1.343 + const size_type __n = _M_next_size(__num_elements_hint);
1.344 + if (__n > __old_n) {
1.345 + _BucketVector __tmp(__n, (void*)(0),
1.346 + _M_buckets.get_allocator());
1.347 + _STLP_PUSH_CLEANUP_ITEM(_BucketVector, &__tmp);
1.348 + _STLP_TRY {
1.349 + for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
1.350 + _Node* __first = (_Node*)_M_buckets[__bucket];
1.351 + while (__first) {
1.352 + size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
1.353 + _M_buckets[__bucket] = __first->_M_next;
1.354 + __first->_M_next = (_Node*)__tmp[__new_bucket];
1.355 + __tmp[__new_bucket] = __first;
1.356 + __first = (_Node*)_M_buckets[__bucket];
1.357 + }
1.358 + }
1.359 + _M_buckets.swap(__tmp);
1.360 + }
1.361 + _STLP_CATCH_ALL {
1.362 + for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
1.363 + while (__tmp[__bucket]) {
1.364 + _Node* __next = ((_Node*)__tmp[__bucket])->_M_next;
1.365 + _M_delete_node((_Node*)__tmp[__bucket]);
1.366 + __tmp[__bucket] = __next;
1.367 + }
1.368 + }
1.369 + _STLP_RETHROW;
1.370 + }
1.371 +#ifdef _STLP_USE_TRAP_LEAVE
1.372 + CleanupStack::Pop();
1.373 +#endif
1.374 +
1.375 + }
1.376 + }
1.377 +}
1.378 +
1.379 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.380 +void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.381 + ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1.382 +{
1.383 + _Node* __cur = (_Node*)_M_buckets[__n];
1.384 + if (__cur == __first)
1.385 + _M_erase_bucket(__n, __last);
1.386 + else {
1.387 + _Node* __next;
1.388 + for (__next = __cur->_M_next;
1.389 + __next != __first;
1.390 + __cur = __next, __next = __cur->_M_next)
1.391 + ;
1.392 + while (__next != __last) {
1.393 + __cur->_M_next = __next->_M_next;
1.394 + _M_delete_node(__next);
1.395 + __next = __cur->_M_next;
1.396 + --_M_num_elements._M_data;
1.397 + }
1.398 + }
1.399 +}
1.400 +
1.401 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.402 +void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.403 + ::_M_erase_bucket(const size_type __n, _Node* __last)
1.404 +{
1.405 + _Node* __cur = (_Node*)_M_buckets[__n];
1.406 + while (__cur && __cur != __last) {
1.407 + _Node* __next = __cur->_M_next;
1.408 + _M_delete_node(__cur);
1.409 + __cur = __next;
1.410 + _M_buckets[__n] = __cur;
1.411 + --_M_num_elements._M_data;
1.412 + }
1.413 +}
1.414 +
1.415 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.416 +void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::clear()
1.417 +{
1.418 + for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
1.419 + _Node* __cur = (_Node*)_M_buckets[__i];
1.420 + while (__cur != 0) {
1.421 + _Node* __next = __cur->_M_next;
1.422 + _M_delete_node(__cur);
1.423 + __cur = __next;
1.424 + }
1.425 + _M_buckets[__i] = 0;
1.426 + }
1.427 + _M_num_elements._M_data = 0;
1.428 +}
1.429 +
1.430 +
1.431 +template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.432 +void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.433 + ::_M_copy_from(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht)
1.434 +{
1.435 + _M_buckets.clear();
1.436 + _M_buckets.reserve(__ht._M_buckets.size());
1.437 + _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (void*) 0);
1.438 + _STLP_TRY {
1.439 + for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1.440 + const _Node* __cur = (_Node*)__ht._M_buckets[__i];
1.441 + if (__cur) {
1.442 + _Node* __xcopy = _M_new_node(__cur->_M_val);
1.443 + _M_buckets[__i] = __xcopy;
1.444 +
1.445 + for (_Node* __next = __cur->_M_next;
1.446 + __next;
1.447 + __cur = __next, __next = __cur->_M_next) {
1.448 + __xcopy->_M_next = _M_new_node(__next->_M_val);
1.449 + __xcopy = __xcopy->_M_next;
1.450 + }
1.451 + }
1.452 + }
1.453 + _M_num_elements._M_data = __ht._M_num_elements._M_data;
1.454 + }
1.455 + _STLP_UNWIND(clear());
1.456 +}
1.457 +
1.458 +# undef __iterator__
1.459 +# undef const_iterator
1.460 +# undef __size_type__
1.461 +# undef __reference__
1.462 +# undef size_type
1.463 +# undef value_type
1.464 +# undef key_type
1.465 +# undef _Node
1.466 +# undef __stl_num_primes
1.467 +# undef hashtable
1.468 +
1.469 +_STLP_END_NAMESPACE
1.470 +
1.471 +#endif /* _STLP_HASHTABLE_C */
1.472 +
1.473 +// Local Variables:
1.474 +// mode:C++
1.475 +// End: