1.1 --- a/epoc32/include/stdapis/stlport/stl/_hashtable.c Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,471 +0,0 @@
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: