williamr@2: /*
williamr@4:  * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.
williamr@2:  *
williamr@2:  * Copyright (c) 1994
williamr@2:  * Hewlett-Packard Company
williamr@2:  *
williamr@2:  * Copyright (c) 1996,1997
williamr@2:  * Silicon Graphics Computer Systems, Inc.
williamr@2:  *
williamr@2:  * Copyright (c) 1997
williamr@2:  * Moscow Center for SPARC Technology
williamr@2:  *
williamr@4:  * Copyright (c) 1999
williamr@2:  * Boris Fomitchev
williamr@2:  *
williamr@2:  * This material is provided "as is", with absolutely no warranty expressed
williamr@2:  * or implied. Any use is at your own risk.
williamr@2:  *
williamr@4:  * Permission to use or copy this software for any purpose is hereby granted
williamr@2:  * without fee, provided the above notices are retained on all copies.
williamr@2:  * Permission to modify the code and to distribute modified code is granted,
williamr@2:  * provided the above notices are retained, and a notice that the code was
williamr@2:  * modified is included with the above copyright notice.
williamr@2:  *
williamr@2:  */
williamr@2: #ifndef _STLP_HASHTABLE_C
williamr@2: #define _STLP_HASHTABLE_C
williamr@2: 
williamr@2: #ifndef _STLP_INTERNAL_HASHTABLE_H
williamr@4: #  include <stl/_hashtable.h>
williamr@2: #endif
williamr@2: 
williamr@2: _STLP_BEGIN_NAMESPACE
williamr@2: 
williamr@4: #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
williamr@4: 
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: 
williamr@4: #  define __PRIME_LIST_BODY { \
williamr@4:   7ul,          23ul, \
williamr@2:   53ul,         97ul,         193ul,       389ul,       769ul,      \
williamr@2:   1543ul,       3079ul,       6151ul,      12289ul,     24593ul,    \
williamr@2:   49157ul,      98317ul,      196613ul,    393241ul,    786433ul,   \
williamr@2:   1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul, \
williamr@2:   50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,\
williamr@2:   1610612741ul, 3221225473ul, 4294967291ul  \
williamr@2: }
williamr@2: 
williamr@4: template <class _Dummy>
williamr@4: size_t _STLP_CALL
williamr@4: _Stl_prime<_Dummy>::_S_max_nb_buckets() {
williamr@4:   const size_t _list[] = __PRIME_LIST_BODY;
williamr@4: #  ifndef __MWERKS__
williamr@4:   return _list[(sizeof(_list)/sizeof(_list[0])) - 1];
williamr@4: #  else
williamr@4:   // it has to be 30 * (sizeof(_list[0]) to get the last element of the array
williamr@4:   return _list[30 * (sizeof(_list[0])/sizeof(size_t)) - 1]; // stupid MWERKS!
williamr@4: #  endif
williamr@4: }
williamr@2: 
williamr@4: template <class _Dummy>
williamr@4: size_t _STLP_CALL
williamr@4: _Stl_prime<_Dummy>::_S_next_size(size_t __n) {
williamr@4:   static const size_t _list[] = __PRIME_LIST_BODY;
williamr@4:   const size_t* __first = _list;
williamr@4: #  ifndef __MWERKS__
williamr@4:   const size_t* __last =  _list + (sizeof(_list)/sizeof(_list[0]));
williamr@4: #  else
williamr@4:   // it has to be 30 * (sizeof(_list[0]) to get the last element of the array
williamr@4:   const size_t* __last =  _list + ((30*sizeof(_list[0]))/sizeof(size_t)); // stupid MWERKS
williamr@4: #  endif
williamr@4:   const size_t* pos = __lower_bound(__first, __last, __n, 
williamr@4:                                     __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
williamr@4:   return (pos == __last ? *(__last - 1) : *pos);
williamr@4: }
williamr@4: 
williamr@4: #  undef __PRIME_LIST_BODY
williamr@4: 
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: 
williamr@4: #endif
williamr@4: 
williamr@4: #if defined (_STLP_DEBUG)
williamr@4: #  define hashtable _STLP_NON_DBG_NAME(hashtable)
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: #endif
williamr@2: 
williamr@2: // fbp: these defines are for outline methods definitions.
williamr@2: // needed to definitions to be portable. Should not be used in method bodies.
williamr@2: 
williamr@4: #if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
williamr@2: #  define __size_type__       size_t
williamr@2: #  define size_type           size_t
williamr@4: #  define value_type          _Val
williamr@4: #  define key_type            _Key
williamr@2: #  define __reference__       _Val&
williamr@2: 
williamr@4: #  define __iterator__        _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits, \
williamr@4:                                            _Key, _HF, _ExK, _EqK, _All>
williamr@4: #  define __const_iterator__  _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_ConstTraits, \
williamr@4:                                            _Key, _HF, _ExK, _EqK, _All>
williamr@4: #else
williamr@4: #  define __size_type__       _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::size_type
williamr@4: #  define __reference__       _STLP_TYPENAME_ON_RETURN_TYPE  hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::reference
williamr@4: #  define __iterator__        _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::iterator
williamr@4: #  define __const_iterator__  _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::const_iterator
williamr@4: #endif
williamr@2: 
williamr@4: /*
williamr@4:  * This method is too difficult to implement for hashtable that do not
williamr@4:  * require a sorted operation on the stored type.
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: bool hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_equal(
williamr@4:               const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht1,
williamr@4:               const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht2) {
williamr@4:   return __ht1._M_buckets == __ht2._M_buckets &&
williamr@4:          __ht1._M_elems == __ht2._M_elems;
williamr@4: }
williamr@4: */
williamr@2: 
williamr@4: /* Returns the iterator before the first iterator of the bucket __n and set
williamr@4:  * __n to the first previous bucket having the same first iterator as bucket
williamr@4:  * __n.
williamr@4:  */
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: __iterator__
williamr@4: hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::_M_before_begin(size_type &__n) const {
williamr@4:   return _S_before_begin(_M_elems, _M_buckets, __n);
williamr@2: }
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: __iterator__
williamr@4: hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
williamr@4:                     size_type &__n) {
williamr@4:   _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);
williamr@4:   typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);
williamr@4: 
williamr@4:   _ElemsIte __pos(*__bpos);
williamr@4:   if (__pos == __mutable_elems.begin()) {
williamr@4:     __n = 0;
williamr@4:     return __mutable_elems.before_begin();
williamr@4:   }
williamr@4: 
williamr@4:   typename _BucketVector::const_iterator __bcur(__bpos);
williamr@4:   _BucketType *__pos_node = __pos._M_node;
williamr@4:   for (--__bcur; __pos_node == *__bcur; --__bcur) {}
williamr@4: 
williamr@4:   __n = __bcur - __buckets.begin() + 1;
williamr@4:   _ElemsIte __cur(*__bcur);
williamr@4:   _ElemsIte __prev = __cur++;
williamr@4:   for (; __cur != __pos; ++__prev, ++__cur) {}
williamr@4:   return __prev;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: __iterator__
williamr@4: hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::_M_insert_noresize(size_type __n, const value_type& __obj) {
williamr@4:   //We always insert this element as 1st in the bucket to not break
williamr@4:   //the elements order as equal elements must be kept next to each other.
williamr@4:   size_type __prev = __n;
williamr@4:   _ElemsIte __pos = _M_before_begin(__prev)._M_ite;
williamr@2: 
williamr@4:   fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1,
williamr@4:        _M_elems.insert_after(__pos, __obj)._M_node);
williamr@4:   ++_M_num_elements;
williamr@4:   return iterator(_ElemsIte(_M_buckets[__n]));
williamr@2: }
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: pair<__iterator__, bool>
williamr@4: hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::insert_unique_noresize(const value_type& __obj) {
williamr@2:   const size_type __n = _M_bkt_num(__obj);
williamr@4:   _ElemsIte __cur(_M_buckets[__n]);
williamr@4:   _ElemsIte __last(_M_buckets[__n + 1]);
williamr@2: 
williamr@4:   if (__cur != __last) {
williamr@4:     for (; __cur != __last; ++__cur) {
williamr@4:       if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
williamr@4:         //We check that equivalent keys have equals hash code as otherwise, on resize,
williamr@4:         //equivalent value might not be in the same bucket
williamr@4:         _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
williamr@4:         return pair<iterator, bool>(iterator(__cur), false);
williamr@4:       }
williamr@2:     }
williamr@4:     /* Here we do not rely on the _M_insert_noresize method as we know
williamr@4:      * that we cannot break element orders, elements are unique, and
williamr@4:      * insertion after the first bucket element is faster than what is
williamr@4:      * done in _M_insert_noresize.
williamr@4:      */
williamr@4:     __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj);
williamr@4:     ++_M_num_elements;
williamr@4:     return pair<iterator, bool>(iterator(__cur), true);
williamr@4:   }
williamr@2: 
williamr@4:   return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true);
williamr@2: }
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: __iterator__
williamr@4: hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::insert_equal_noresize(const value_type& __obj) {
williamr@4:   const size_type __n = _M_bkt_num(__obj);
williamr@4:   {
williamr@4:     _ElemsIte __cur(_M_buckets[__n]);
williamr@4:     _ElemsIte __last(_M_buckets[__n + 1]);
williamr@2: 
williamr@4:     for (; __cur != __last; ++__cur) {
williamr@4:       if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
williamr@4:         //We check that equivalent keys have equals hash code as otherwise, on resize,
williamr@4:         //equivalent value might not be in the same bucket
williamr@4:         _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
williamr@4:         ++_M_num_elements;
williamr@4:         return _M_elems.insert_after(__cur, __obj);
williamr@4:       }
williamr@4:     }
williamr@4:   }
williamr@2: 
williamr@4:   return _M_insert_noresize(__n, __obj);
williamr@2: }
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: __reference__
williamr@4: hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::_M_insert(const value_type& __obj) {
williamr@4:   resize(_M_num_elements + 1);
williamr@4:   return *insert_unique_noresize(__obj).first;
williamr@4: }
williamr@2: 
williamr@4: /*
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: __reference__
williamr@4: hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::find_or_insert(const value_type& __obj) {
williamr@2:   _Node* __first = _M_find(_M_get_key(__obj));
williamr@2:   if (__first)
williamr@2:     return __first->_M_val;
williamr@2:   else
williamr@2:     return _M_insert(__obj);
williamr@2: }
williamr@4: */
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: __size_type__
williamr@4: hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::erase(const key_type& __key) {
williamr@2:   const size_type __n = _M_bkt_num_key(__key);
williamr@2: 
williamr@4:   _ElemsIte __cur(_M_buckets[__n]);
williamr@4:   _ElemsIte __last(_M_buckets[__n + 1]);
williamr@4:   if (__cur == __last)
williamr@4:     return 0;
williamr@2: 
williamr@4:   size_type __erased = 0;
williamr@4:   if (_M_equals(_M_get_key(*__cur), __key)) {
williamr@4:     //We look for the pos before __cur:
williamr@4:     size_type __prev_b = __n;
williamr@4:     _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
williamr@4:     do {
williamr@4:       __cur = _M_elems.erase_after(__prev);
williamr@4:       ++__erased;
williamr@4:     } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
williamr@4:     fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node);
williamr@4:   }
williamr@4:   else {
williamr@4:     _ElemsIte __prev = __cur++;
williamr@4:     for (; __cur != __last; ++__prev, ++__cur) {
williamr@4:       if (_M_equals(_M_get_key(*__cur), __key)) {
williamr@4:         do {
williamr@4:           __cur = _M_elems.erase_after(__prev);
williamr@4:           ++__erased;
williamr@4:         } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
williamr@4:         break;
williamr@4:       }
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@4:   _M_num_elements -= __erased;
williamr@2:   return __erased;
williamr@2: }
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::erase(const_iterator __it) {
williamr@4:   const size_type __n = _M_bkt_num(*__it);
williamr@4:   _ElemsIte __cur(_M_buckets[__n]);
williamr@2: 
williamr@4:   if (__cur == __it._M_ite) {
williamr@4:     size_type __prev_b = __n;
williamr@4:     _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
williamr@4:     fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
williamr@4:          _M_elems.erase_after(__prev)._M_node);
williamr@4:     --_M_num_elements;
williamr@4:   }
williamr@4:   else {
williamr@4:     _ElemsIte __prev = __cur++;
williamr@4:     _ElemsIte __last(_M_buckets[__n + 1]);
williamr@4:     for (; __cur != __last; ++__prev, ++__cur) {
williamr@4:       if (__cur == __it._M_ite) {
williamr@4:         _M_elems.erase_after(__prev);
williamr@4:         --_M_num_elements;
williamr@4:         break;
williamr@2:       }
williamr@2:     }
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::erase(const_iterator __first, const_iterator __last) {
williamr@4:   if (__first == __last)
williamr@2:     return;
williamr@4:   size_type __f_bucket = _M_bkt_num(*__first);
williamr@4:   size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1);
williamr@4: 
williamr@4:   _ElemsIte __cur(_M_buckets[__f_bucket]);
williamr@4:   _ElemsIte __prev;
williamr@4:   if (__cur == __first._M_ite) {
williamr@4:     __prev = _M_before_begin(__f_bucket)._M_ite;
williamr@4:   }
williamr@2:   else {
williamr@4:     _ElemsIte __last(_M_buckets[++__f_bucket]);
williamr@4:     __prev = __cur++;
williamr@4:     for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur);
williamr@2:   }
williamr@4:   //We do not use the slist::erase_after method taking a range to count the
williamr@4:   //number of erased elements:
williamr@4:   while (__cur != __last._M_ite) {
williamr@4:     __cur = _M_elems.erase_after(__prev);
williamr@4:     --_M_num_elements;
williamr@4:   }
williamr@4:   fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
williamr@2: }
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::rehash(size_type __num_buckets_hint) {
williamr@4:   if ((bucket_count() >= __num_buckets_hint) &&
williamr@4:       (max_load_factor() > load_factor()))
williamr@4:     return;
williamr@4: 
williamr@4:   //Here if max_load_factor is lower than 1.0 the resulting value might not be representable
williamr@4:   //as a size_type. The result concerning the respect of the max_load_factor will then be
williamr@4:   //undefined.
williamr@4:   __num_buckets_hint = (max) (__num_buckets_hint, (size_type)((float)size() / max_load_factor()));
williamr@4:   size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
williamr@4:   _M_rehash(__num_buckets);
williamr@4: }
williamr@4: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::resize(size_type __num_elements_hint) {
williamr@4:   if (((float)__num_elements_hint / (float)bucket_count() <= max_load_factor()) &&
williamr@4:       (max_load_factor() >= load_factor())) {
williamr@4:     return;
williamr@4:   }
williamr@4: 
williamr@4:   size_type __num_buckets_hint = (size_type)((float)(max) (__num_elements_hint, size()) / max_load_factor());
williamr@4:   size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
williamr@4: #if defined (_STLP_DEBUG)
williamr@4:   _M_check();
williamr@2: #endif
williamr@4:   _M_rehash(__num_buckets);
williamr@4: }
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::_M_rehash(size_type __num_buckets) {
williamr@4:   _ElemsCont __tmp_elems(_M_elems.get_allocator());
williamr@4:   _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator());
williamr@4:   _ElemsIte __cur, __last(_M_elems.end());
williamr@4:   while (!_M_elems.empty()) {
williamr@4:     __cur = _M_elems.begin();
williamr@4:     size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets);
williamr@4:     _ElemsIte __ite(__cur), __before_ite(__cur);
williamr@4:     for (++__ite;
williamr@4:          __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite));
williamr@4:          ++__ite, ++__before_ite) {}
williamr@4:     size_type __prev_bucket = __new_bucket;
williamr@4:     _ElemsIte  __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite;
williamr@4:     __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite);
williamr@4:     fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node);
williamr@4:   }
williamr@4:   _M_elems.swap(__tmp_elems);
williamr@4:   _M_buckets.swap(__tmp);
williamr@4: }
williamr@4: 
williamr@4: #if defined (_STLP_DEBUG)
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_check() const {
williamr@4:   //We check that hash code of stored keys haven't change and also that equivalent
williamr@4:   //relation hasn't been modified
williamr@4:   size_t __num_buckets = bucket_count();
williamr@4:   for (size_t __b = 0; __b < __num_buckets; ++__b) {
williamr@4:     _ElemsIte __cur(_M_buckets[__b]), __last(_M_buckets[__b + 1]);
williamr@4:     _ElemsIte __fst(__cur), __snd(__cur);
williamr@4:     for (; __cur != __last; ++__cur) {
williamr@4:       _STLP_ASSERT( _M_bkt_num(*__cur, __num_buckets) == __b )
williamr@4:       _STLP_ASSERT( !_M_equals(_M_get_key(*__fst), _M_get_key(*__cur)) || _M_equals(_M_get_key(*__snd), _M_get_key(*__cur)) )
williamr@4:       if (__fst != __snd)
williamr@4:         ++__fst;
williamr@4:       if (__snd != __cur)
williamr@4:         ++__snd;
williamr@2:     }
williamr@2:   }
williamr@2: }
williamr@4: #endif
williamr@2: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::clear() {
williamr@4:   _M_elems.clear();
williamr@4:   _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0));
williamr@4:   _M_num_elements = 0;
williamr@4: }
williamr@4: 
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4:   ::_M_copy_from(const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht) {
williamr@4:   _M_elems.clear();
williamr@4:   _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end());
williamr@4:   _M_buckets.resize(__ht._M_buckets.size());
williamr@4:   _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end());
williamr@4:   _ElemsIte __dst(_M_elems.begin());
williamr@4:   typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()),
williamr@4:                                          __src_end_b(__ht._M_buckets.end());
williamr@4:   typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end());
williamr@4:   for (; __src != __src_end; ++__src, ++__dst) {
williamr@4:     for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) {
williamr@4:       if (*__src_b == __src._M_node) {
williamr@4:         *__dst_b = __dst._M_node;
williamr@4:       }
williamr@4:       else
williamr@4:         break;
williamr@2:     }
williamr@2:   }
williamr@4:   fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0));
williamr@4:   _M_num_elements = __ht._M_num_elements;
williamr@4:   _M_max_load_factor = __ht._M_max_load_factor;
williamr@2: }
williamr@2: 
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 __stl_num_primes
williamr@2: 
williamr@4: #if defined (_STLP_DEBUG)
williamr@4: #  undef hashtable
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: #endif
williamr@2: 
williamr@2: _STLP_END_NAMESPACE
williamr@2: 
williamr@2: #endif /*  _STLP_HASHTABLE_C */
williamr@2: 
williamr@2: // Local Variables:
williamr@2: // mode:C++
williamr@2: // End: