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