williamr@4: /* williamr@4: * williamr@4: * williamr@4: * Copyright (c) 1994 williamr@4: * Hewlett-Packard Company williamr@4: * williamr@4: * Copyright (c) 1996,1997 williamr@4: * Silicon Graphics Computer Systems, Inc. williamr@4: * williamr@4: * Copyright (c) 1997 williamr@4: * Moscow Center for SPARC Technology williamr@4: * williamr@4: * Copyright (c) 1999 williamr@4: * Boris Fomitchev williamr@4: * williamr@4: * This material is provided "as is", with absolutely no warranty expressed williamr@4: * or implied. Any use is at your own risk. williamr@4: * williamr@4: * Permission to use or copy this software for any purpose is hereby granted williamr@4: * without fee, provided the above notices are retained on all copies. williamr@4: * Permission to modify the code and to distribute modified code is granted, williamr@4: * provided the above notices are retained, and a notice that the code was williamr@4: * modified is included with the above copyright notice. williamr@4: * williamr@4: */ williamr@4: #ifndef _STLP_HASHTABLE_C williamr@4: #define _STLP_HASHTABLE_C williamr@4: williamr@4: #ifndef _STLP_INTERNAL_HASHTABLE_H williamr@4: # include williamr@4: #endif williamr@4: williamr@4: #ifdef _STLP_DEBUG williamr@4: # define hashtable __WORKAROUND_DBG_RENAME(hashtable) williamr@4: #endif williamr@4: williamr@4: _STLP_BEGIN_NAMESPACE williamr@4: williamr@4: # define __PRIME_LIST_BODY { \ williamr@4: 53ul, 97ul, 193ul, 389ul, 769ul, \ williamr@4: 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, \ williamr@4: 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, \ williamr@4: 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, \ williamr@4: 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,\ williamr@4: 1610612741ul, 3221225473ul, 4294967291ul \ williamr@4: } williamr@4: williamr@4: #if ( _STLP_STATIC_TEMPLATE_DATA > 0 ) williamr@4: template williamr@4: const size_t _Stl_prime<_Tp>::_M_list[__stl_num_primes] = __PRIME_LIST_BODY; williamr@4: #else williamr@4: __DECLARE_INSTANCE(const size_t, williamr@4: _Stl_prime_type::_M_list[], =__PRIME_LIST_BODY); williamr@4: #endif /* _STLP_STATIC_TEMPLATE_DATA */ williamr@4: williamr@4: # undef __PRIME_LIST_BODY williamr@4: williamr@4: // fbp: these defines are for outline methods definitions. williamr@4: // needed to definitions to be portable. Should not be used in method bodies. williamr@4: williamr@4: # if defined ( _STLP_NESTED_TYPE_PARAM_BUG ) williamr@4: # define __size_type__ size_t williamr@4: # define size_type size_t williamr@4: # define value_type _Val williamr@4: # define key_type _Key williamr@4: # define _Node _Hashtable_node<_Val> williamr@4: # define __reference__ _Val& williamr@4: williamr@4: # define __iterator__ _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> williamr@4: # define __const_iterator__ _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> williamr@4: # else williamr@4: # define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::size_type williamr@4: # define __reference__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::reference williamr@4: # define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>::iterator williamr@4: # endif williamr@4: williamr@4: template williamr@4: _Hashtable_node<_Val>* williamr@4: _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_skip_to_next() { williamr@4: size_t __bucket = _M_ht->_M_bkt_num(_M_cur->_M_val); williamr@4: size_t __h_sz; williamr@4: __h_sz = this->_M_ht->bucket_count(); williamr@4: williamr@4: _Node* __i=0; williamr@4: while (__i==0 && ++__bucket < __h_sz) williamr@4: __i = (_Node*)_M_ht->_M_buckets[__bucket]; williamr@4: return __i; williamr@4: } williamr@4: williamr@4: template williamr@4: __size_type__ williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_next_size(size_type __n) const { williamr@4: const size_type* __first = (const size_type*)_Stl_prime_type::_M_list; williamr@4: const size_type* __last = (const size_type*)_Stl_prime_type::_M_list + (int)__stl_num_primes; williamr@4: const size_type* pos = __lower_bound(__first, __last, __n, __less((size_type*)0), (ptrdiff_t*)0); williamr@4: return (pos == __last ? *(__last - 1) : *pos); williamr@4: } williamr@4: williamr@4: template williamr@4: bool williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_equal( williamr@4: const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht1, williamr@4: const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht2) williamr@4: { williamr@4: // typedef _Hashtable_node<_Val> _Node; williamr@4: if (__ht1.bucket_count() != __ht2.bucket_count()) williamr@4: return false; williamr@4: for (size_t __n = 0; __n < __ht1.bucket_count(); ++__n) { williamr@4: const _Node* __cur1 = __ht1._M_get_bucket(__n); williamr@4: const _Node* __cur2 = __ht2._M_get_bucket(__n); williamr@4: for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val; williamr@4: __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) williamr@4: {} williamr@4: if (__cur1 || __cur2) williamr@4: return false; williamr@4: } williamr@4: return true; williamr@4: } williamr@4: williamr@4: template williamr@4: pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> , bool> williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@4: ::insert_unique_noresize(const value_type& __obj) williamr@4: { williamr@4: const size_type __n = _M_bkt_num(__obj); williamr@4: _Node* __first = (_Node*)_M_buckets[__n]; williamr@4: williamr@4: for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) williamr@4: if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) williamr@4: return pair(iterator(__cur, this), false); williamr@4: williamr@4: _Node* __tmp = _M_new_node(__obj); williamr@4: __tmp->_M_next = __first; williamr@4: _M_buckets[__n] = __tmp; williamr@4: ++_M_num_elements._M_data; williamr@4: return pair(iterator(__tmp, this), true); williamr@4: } williamr@4: williamr@4: template williamr@4: __iterator__ williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@4: ::insert_equal_noresize(const value_type& __obj) williamr@4: { williamr@4: const size_type __n = _M_bkt_num(__obj); williamr@4: _Node* __first = (_Node*)_M_buckets[__n]; williamr@4: williamr@4: for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) williamr@4: if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) { williamr@4: _Node* __tmp = _M_new_node(__obj); williamr@4: __tmp->_M_next = __cur->_M_next; williamr@4: __cur->_M_next = __tmp; williamr@4: ++_M_num_elements._M_data; williamr@4: return iterator(__tmp, this); williamr@4: } williamr@4: williamr@4: _Node* __tmp = _M_new_node(__obj); williamr@4: __tmp->_M_next = __first; williamr@4: _M_buckets[__n] = __tmp; williamr@4: ++_M_num_elements._M_data; williamr@4: return iterator(__tmp, this); williamr@4: } williamr@4: williamr@4: template williamr@4: __reference__ williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::_M_insert(const value_type& __obj) williamr@4: { williamr@4: resize(_M_num_elements._M_data + 1); williamr@4: williamr@4: size_type __n = _M_bkt_num(__obj); williamr@4: _Node* __first = (_Node*)_M_buckets[__n]; williamr@4: williamr@4: _Node* __tmp = _M_new_node(__obj); williamr@4: __tmp->_M_next = __first; williamr@4: _M_buckets[__n] = __tmp; williamr@4: ++_M_num_elements._M_data; williamr@4: return __tmp->_M_val; williamr@4: } williamr@4: williamr@4: template williamr@4: __reference__ williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::find_or_insert(const value_type& __obj) williamr@4: { williamr@4: williamr@4: _Node* __first = _M_find(_M_get_key(__obj)); williamr@4: if (__first) williamr@4: return __first->_M_val; williamr@4: else williamr@4: return _M_insert(__obj); williamr@4: } williamr@4: williamr@4: template williamr@4: pair< _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>, williamr@4: _Ht_iterator<_Val, _Nonconst_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> > williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::equal_range(const key_type& __key) williamr@4: { williamr@4: typedef pair _Pii; williamr@4: const size_type __n = _M_bkt_num_key(__key); williamr@4: williamr@4: for (_Node* __first = (_Node*)_M_buckets[__n]; __first; __first = __first->_M_next) williamr@4: if (_M_equals(_M_get_key(__first->_M_val), __key)) { williamr@4: for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next) williamr@4: if (!_M_equals(_M_get_key(__cur->_M_val), __key)) williamr@4: return _Pii(iterator(__first, this), iterator(__cur, this)); williamr@4: for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) williamr@4: if (_M_buckets[__m]) williamr@4: return _Pii(iterator(__first, this), williamr@4: iterator((_Node*)_M_buckets[__m], this)); williamr@4: return _Pii(iterator(__first, this), end()); williamr@4: } williamr@4: return _Pii(end(), end()); williamr@4: } williamr@4: williamr@4: template williamr@4: pair< _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All>, williamr@4: _Ht_iterator<_Val, _Const_traits<_Val>, _Key, _HF, _ExK, _EqK, _All> > williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@4: ::equal_range(const key_type& __key) const williamr@4: { williamr@4: typedef pair _Pii; williamr@4: const size_type __n = _M_bkt_num_key(__key); williamr@4: williamr@4: for (const _Node* __first = (_Node*)_M_buckets[__n] ; williamr@4: __first; williamr@4: __first = __first->_M_next) { williamr@4: if (_M_equals(_M_get_key(__first->_M_val), __key)) { williamr@4: for (const _Node* __cur = __first->_M_next; williamr@4: __cur; williamr@4: __cur = __cur->_M_next) williamr@4: if (!_M_equals(_M_get_key(__cur->_M_val), __key)) williamr@4: return _Pii(const_iterator(__first, this), williamr@4: const_iterator(__cur, this)); williamr@4: for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) williamr@4: if (_M_buckets[__m]) williamr@4: return _Pii(const_iterator(__first, this), williamr@4: const_iterator((_Node*)_M_buckets[__m], this)); williamr@4: return _Pii(const_iterator(__first, this), end()); williamr@4: } williamr@4: } williamr@4: return _Pii(end(), end()); williamr@4: } williamr@4: williamr@4: template williamr@4: __size_type__ williamr@4: hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const key_type& __key) williamr@4: { williamr@4: const size_type __n = _M_bkt_num_key(__key); williamr@4: _Node* __first = (_Node*)_M_buckets[__n]; williamr@4: size_type __erased = 0; williamr@4: williamr@4: if (__first) { williamr@4: _Node* __cur = __first; williamr@4: _Node* __next = __cur->_M_next; williamr@4: while (__next) { williamr@4: if (_M_equals(_M_get_key(__next->_M_val), __key)) { williamr@4: __cur->_M_next = __next->_M_next; williamr@4: _M_delete_node(__next); williamr@4: __next = __cur->_M_next; williamr@4: ++__erased; williamr@4: --_M_num_elements._M_data; williamr@4: } williamr@4: else { williamr@4: __cur = __next; williamr@4: __next = __cur->_M_next; williamr@4: } williamr@4: } williamr@4: if (_M_equals(_M_get_key(__first->_M_val), __key)) { williamr@4: _M_buckets[__n] = __first->_M_next; williamr@4: _M_delete_node(__first); williamr@4: ++__erased; williamr@4: --_M_num_elements._M_data; williamr@4: } williamr@4: } williamr@4: return __erased; williamr@4: } williamr@4: williamr@4: template williamr@4: void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::erase(const const_iterator& __it) williamr@4: { williamr@4: // const iterator& __it = __REINTERPRET_CAST(const iterator&,_c_it); williamr@4: const _Node* __p = __it._M_cur; williamr@4: if (__p) { williamr@4: const size_type __n = _M_bkt_num(__p->_M_val); williamr@4: _Node* __cur = (_Node*)_M_buckets[__n]; williamr@4: williamr@4: if (__cur == __p) { williamr@4: _M_buckets[__n] = __cur->_M_next; williamr@4: _M_delete_node(__cur); williamr@4: --_M_num_elements._M_data; williamr@4: } williamr@4: else { williamr@4: _Node* __next = __cur->_M_next; williamr@4: while (__next) { williamr@4: if (__next == __p) { williamr@4: __cur->_M_next = __next->_M_next; williamr@4: _M_delete_node(__next); williamr@4: --_M_num_elements._M_data; williamr@4: break; williamr@4: } williamr@4: else { williamr@4: __cur = __next; williamr@4: __next = __cur->_M_next; williamr@4: } williamr@4: } williamr@4: } williamr@4: } williamr@4: } williamr@4: williamr@4: template williamr@4: void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@4: ::erase(const_iterator _c_first, const_iterator _c_last) williamr@4: { williamr@4: iterator& __first = (iterator&)_c_first; williamr@4: iterator& __last = (iterator&)_c_last; williamr@4: size_type __f_bucket = __first._M_cur ? williamr@4: _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size(); williamr@4: size_type __l_bucket = __last._M_cur ? williamr@4: _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size(); williamr@4: if (__first._M_cur == __last._M_cur) williamr@4: return; williamr@4: else if (__f_bucket == __l_bucket) williamr@4: _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); williamr@4: else { williamr@4: _M_erase_bucket(__f_bucket, __first._M_cur, 0); williamr@4: for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) williamr@4: _M_erase_bucket(__n, 0); williamr@4: if (__l_bucket != _M_buckets.size()) williamr@4: _M_erase_bucket(__l_bucket, __last._M_cur); williamr@4: } williamr@4: } williamr@4: williamr@4: template williamr@4: void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@4: ::resize(size_type __num_elements_hint) williamr@4: { williamr@4: const size_type __old_n = _M_buckets.size(); williamr@4: if (__num_elements_hint > __old_n) { williamr@4: const size_type __n = _M_next_size(__num_elements_hint); williamr@4: if (__n > __old_n) { williamr@4: _BucketVector __tmp(__n, (void*)(0), williamr@4: _M_buckets.get_allocator()); williamr@4: _STLP_PUSH_CLEANUP_ITEM(_BucketVector, &__tmp); williamr@4: _STLP_TRY { williamr@4: for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) { williamr@4: _Node* __first = (_Node*)_M_buckets[__bucket]; williamr@4: while (__first) { williamr@4: size_type __new_bucket = _M_bkt_num(__first->_M_val, __n); williamr@4: _M_buckets[__bucket] = __first->_M_next; williamr@4: __first->_M_next = (_Node*)__tmp[__new_bucket]; williamr@4: __tmp[__new_bucket] = __first; williamr@4: __first = (_Node*)_M_buckets[__bucket]; williamr@4: } williamr@4: } williamr@4: _M_buckets.swap(__tmp); williamr@4: } williamr@4: _STLP_CATCH_ALL { williamr@4: for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) { williamr@4: while (__tmp[__bucket]) { williamr@4: _Node* __next = ((_Node*)__tmp[__bucket])->_M_next; williamr@4: _M_delete_node((_Node*)__tmp[__bucket]); williamr@4: __tmp[__bucket] = __next; williamr@4: } williamr@4: } williamr@4: _STLP_RETHROW; williamr@4: } williamr@4: #ifdef _STLP_USE_TRAP_LEAVE williamr@4: CleanupStack::Pop(); williamr@4: #endif williamr@4: williamr@4: } williamr@4: } williamr@4: } williamr@4: williamr@4: template williamr@4: void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@4: ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) williamr@4: { williamr@4: _Node* __cur = (_Node*)_M_buckets[__n]; williamr@4: if (__cur == __first) williamr@4: _M_erase_bucket(__n, __last); williamr@4: else { williamr@4: _Node* __next; williamr@4: for (__next = __cur->_M_next; williamr@4: __next != __first; williamr@4: __cur = __next, __next = __cur->_M_next) williamr@4: ; williamr@4: while (__next != __last) { williamr@4: __cur->_M_next = __next->_M_next; williamr@4: _M_delete_node(__next); williamr@4: __next = __cur->_M_next; williamr@4: --_M_num_elements._M_data; williamr@4: } williamr@4: } williamr@4: } williamr@4: williamr@4: template williamr@4: void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@4: ::_M_erase_bucket(const size_type __n, _Node* __last) williamr@4: { williamr@4: _Node* __cur = (_Node*)_M_buckets[__n]; williamr@4: while (__cur && __cur != __last) { williamr@4: _Node* __next = __cur->_M_next; williamr@4: _M_delete_node(__cur); williamr@4: __cur = __next; williamr@4: _M_buckets[__n] = __cur; williamr@4: --_M_num_elements._M_data; williamr@4: } williamr@4: } williamr@4: williamr@4: template williamr@4: void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::clear() williamr@4: { williamr@4: for (size_type __i = 0; __i < _M_buckets.size(); ++__i) { williamr@4: _Node* __cur = (_Node*)_M_buckets[__i]; williamr@4: while (__cur != 0) { williamr@4: _Node* __next = __cur->_M_next; williamr@4: _M_delete_node(__cur); williamr@4: __cur = __next; williamr@4: } williamr@4: _M_buckets[__i] = 0; williamr@4: } williamr@4: _M_num_elements._M_data = 0; williamr@4: } williamr@4: williamr@4: williamr@4: template williamr@4: void hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@4: ::_M_copy_from(const hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>& __ht) williamr@4: { williamr@4: _M_buckets.clear(); williamr@4: _M_buckets.reserve(__ht._M_buckets.size()); williamr@4: _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (void*) 0); williamr@4: _STLP_TRY { williamr@4: for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { williamr@4: const _Node* __cur = (_Node*)__ht._M_buckets[__i]; williamr@4: if (__cur) { williamr@4: _Node* __xcopy = _M_new_node(__cur->_M_val); williamr@4: _M_buckets[__i] = __xcopy; williamr@4: williamr@4: for (_Node* __next = __cur->_M_next; williamr@4: __next; williamr@4: __cur = __next, __next = __cur->_M_next) { williamr@4: __xcopy->_M_next = _M_new_node(__next->_M_val); williamr@4: __xcopy = __xcopy->_M_next; williamr@4: } williamr@4: } williamr@4: } williamr@4: _M_num_elements._M_data = __ht._M_num_elements._M_data; williamr@4: } williamr@4: _STLP_UNWIND(clear()); williamr@4: } williamr@4: williamr@4: # undef __iterator__ williamr@4: # undef const_iterator williamr@4: # undef __size_type__ williamr@4: # undef __reference__ williamr@4: # undef size_type williamr@4: # undef value_type williamr@4: # undef key_type williamr@4: # undef _Node williamr@4: # undef __stl_num_primes williamr@4: # undef hashtable williamr@4: williamr@4: _STLP_END_NAMESPACE williamr@4: williamr@4: #endif /* _STLP_HASHTABLE_C */ williamr@4: williamr@4: // Local Variables: williamr@4: // mode:C++ williamr@4: // End: