19720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 29720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1994 39720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hewlett-Packard Company 49720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 59720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1996,1997 69720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Silicon Graphics Computer Systems, Inc. 79720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 89720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1997 99720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Moscow Center for SPARC Technology 109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1999 129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Boris Fomitchev 139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This material is provided "as is", with absolutely no warranty expressed 159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or implied. Any use is at your own risk. 169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to use or copy this software for any purpose is hereby granted 189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * without fee, provided the above notices are retained on all copies. 199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to modify the code and to distribute modified code is granted, 209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * provided the above notices are retained, and a notice that the code was 219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * modified is included with the above copyright notice. 229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_HASHTABLE_C 259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_HASHTABLE_C 269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_HASHTABLE_H 289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_hashtable.h> 299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) 349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __PRIME_LIST_BODY { \ 389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7ul, 23ul, \ 399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 53ul, 97ul, 193ul, 389ul, 769ul, \ 409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, \ 419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, \ 429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, \ 439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,\ 449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1610612741ul, 3221225473ul, 4294967291ul \ 459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Dummy> 48e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottconst size_t* _STLP_CALL 49e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_Stl_prime<_Dummy>::_S_primes(size_t &__size) { 50e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott static const size_t _list[] = __PRIME_LIST_BODY; 519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifndef __MWERKS__ 52e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __size = sizeof(_list) / sizeof(_list[0]); 539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# else 54e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __size = 30; 559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif 56e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _list; 57e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 58e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 59e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _Dummy> 60e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottsize_t _STLP_CALL 61e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_Stl_prime<_Dummy>::_S_max_nb_buckets() { 62e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_t __size; 63e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const size_t* __first = _S_primes(__size); 64e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return *(__first + __size - 1); 659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Dummy> 689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocksize_t _STLP_CALL 699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Stl_prime<_Dummy>::_S_next_size(size_t __n) { 70e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_t __size; 71e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const size_t* __first = _S_primes(__size); 72e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const size_t* __last = __first + __size; 739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_t* pos = __lower_bound(__first, __last, __n, 749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0); 759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return (pos == __last ? *(__last - 1) : *pos); 769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 78e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _Dummy> 79e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid _STLP_CALL 80e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_Stl_prime<_Dummy>::_S_prev_sizes(size_t __n, size_t const*&__begin, size_t const*&__pos) { 81e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_t __size; 82e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __begin = _S_primes(__size); 83e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const size_t* __last = __begin + __size; 84e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __pos = __lower_bound(__begin, __last, __n, 85e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0); 86e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 87e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (__pos== __last) 88e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott --__pos; 89e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott else if (*__pos == __n) { 90e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (__pos != __begin) 91e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott --__pos; 92e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 93e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 94e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __PRIME_LIST_BODY 969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define hashtable _STLP_NON_DBG_NAME(hashtable) 1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// fbp: these defines are for outline methods definitions. 1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// needed to definitions to be portable. Should not be used in method bodies. 1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined ( _STLP_NESTED_TYPE_PARAM_BUG ) 1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __size_type__ size_t 1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define size_type size_t 1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define value_type _Val 1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define key_type _Key 1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __reference__ _Val& 1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits, \ 1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Key, _HF, _ExK, _EqK, _All> 1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __const_iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_ConstTraits, \ 1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Key, _HF, _ExK, _EqK, _All> 1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::size_type 1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __reference__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::reference 1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::iterator 1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __const_iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::const_iterator 1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This method is too difficult to implement for hashtable that do not 1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * require a sorted operation on the stored type. 1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_equal( 1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht1, 1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht2) { 1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __ht1._M_buckets == __ht2._M_buckets && 1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __ht1._M_elems == __ht2._M_elems; 1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block*/ 1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* Returns the iterator before the first iterator of the bucket __n and set 1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * __n to the first previous bucket having the same first iterator as bucket 1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * __n. 1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__iterator__ 1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockhashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::_M_before_begin(size_type &__n) const { 1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_before_begin(_M_elems, _M_buckets, __n); 1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__iterator__ 1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockhashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets, 1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type &__n) { 1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems); 1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n); 1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __pos(*__bpos); 1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pos == __mutable_elems.begin()) { 1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __n = 0; 1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __mutable_elems.before_begin(); 1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typename _BucketVector::const_iterator __bcur(__bpos); 1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BucketType *__pos_node = __pos._M_node; 1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (--__bcur; __pos_node == *__bcur; --__bcur); 1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __n = __bcur - __buckets.begin() + 1; 1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(*__bcur); 1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __prev = __cur++; 1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __cur != __pos; ++__prev, ++__cur); 1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __prev; 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__iterator__ 1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockhashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::_M_insert_noresize(size_type __n, const value_type& __obj) { 1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //We always insert this element as 1st in the bucket to not break 1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //the elements order as equal elements must be kept next to each other. 1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __prev = __n; 1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __pos = _M_before_begin(__prev)._M_ite; 1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1, 1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems.insert_after(__pos, __obj)._M_node); 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++_M_num_elements; 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return iterator(_ElemsIte(_M_buckets[__n])); 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpair<__iterator__, bool> 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockhashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::insert_unique_noresize(const value_type& __obj) { 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_type __n = _M_bkt_num(__obj); 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(_M_buckets[__n]); 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __last(_M_buckets[__n + 1]); 2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__cur != __last) { 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __cur != __last; ++__cur) { 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) { 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //We check that equivalent keys have equals hash code as otherwise, on resize, 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //equivalent value might not be in the same bucket 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj))) 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<iterator, bool>(iterator(__cur), false); 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block /* Here we do not rely on the _M_insert_noresize method as we know 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * that we cannot break element orders, elements are unique, and 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * insertion after the first bucket element is faster than what is 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * done in _M_insert_noresize. 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj); 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++_M_num_elements; 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<iterator, bool>(iterator(__cur), true); 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true); 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__iterator__ 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockhashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::insert_equal_noresize(const value_type& __obj) { 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_type __n = _M_bkt_num(__obj); 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(_M_buckets[__n]); 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __last(_M_buckets[__n + 1]); 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __cur != __last; ++__cur) { 2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) { 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //We check that equivalent keys have equals hash code as otherwise, on resize, 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //equivalent value might not be in the same bucket 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj))) 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++_M_num_elements; 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _M_elems.insert_after(__cur, __obj); 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _M_insert_noresize(__n, __obj); 2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__reference__ 2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockhashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::_M_insert(const value_type& __obj) { 255e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_enlarge(_M_num_elements + 1); 2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return *insert_unique_noresize(__obj).first; 2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__size_type__ 2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockhashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::erase(const key_type& __key) { 2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_type __n = _M_bkt_num_key(__key); 2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(_M_buckets[__n]); 2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __last(_M_buckets[__n + 1]); 2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__cur == __last) 2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 0; 2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __erased = 0; 2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_equals(_M_get_key(*__cur), __key)) { 2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //We look for the pos before __cur: 2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __prev_b = __n; 2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite; 2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block do { 2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __cur = _M_elems.erase_after(__prev); 2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__erased; 2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key)); 2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node); 2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 2839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __prev = __cur++; 2849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __cur != __last; ++__prev, ++__cur) { 2859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_equals(_M_get_key(*__cur), __key)) { 2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block do { 2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __cur = _M_elems.erase_after(__prev); 2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__erased; 2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key)); 2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 2919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements -= __erased; 296e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_reduce(); 2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __erased; 2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::erase(const_iterator __it) { 3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_type __n = _M_bkt_num(*__it); 3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(_M_buckets[__n]); 3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 307e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_type __erased = 0; 3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__cur == __it._M_ite) { 3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __prev_b = __n; 3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite; 3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, 3129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems.erase_after(__prev)._M_node); 313e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ++__erased; 3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __prev = __cur++; 3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __last(_M_buckets[__n + 1]); 3189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __cur != __last; ++__prev, ++__cur) { 3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__cur == __it._M_ite) { 3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems.erase_after(__prev); 321e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ++__erased; 3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 326e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 327e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_num_elements -= __erased; 328e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_reduce(); 3299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 3329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 3349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::erase(const_iterator __first, const_iterator __last) { 3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __f_bucket = _M_bkt_num(*__first); 3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1); 3399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(_M_buckets[__f_bucket]); 3419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __prev; 3429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__cur == __first._M_ite) { 3439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __prev = _M_before_begin(__f_bucket)._M_ite; 3449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __last(_M_buckets[++__f_bucket]); 3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __prev = __cur++; 3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur); 3499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 350e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_type __erased = 0; 3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //We do not use the slist::erase_after method taking a range to count the 3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //number of erased elements: 3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__cur != __last._M_ite) { 3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __cur = _M_elems.erase_after(__prev); 355e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ++__erased; 3569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node); 358e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_num_elements -= __erased; 359e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_reduce(); 3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 3649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 3659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::rehash(size_type __num_buckets_hint) { 366e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (bucket_count() >= __num_buckets_hint) { 367e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // We are trying to reduce number of buckets, we have to validate it: 368e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_type __limit_num_buckets = (size_type)((float)size() / max_load_factor()); 369e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (__num_buckets_hint < __limit_num_buckets) { 370e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Targetted number of buckets __num_buckets_hint would break 371e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // load_factor() <= max_load_factor() rule. 372e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return; 373e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 374e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 375e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 376e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_rehash(__num_buckets_hint); 377e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 378e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 379e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _Val, class _Key, class _HF, 380e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott class _Traits, class _ExK, class _EqK, class _All> 381e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 382e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ::_M_enlarge(size_type __to_size) { 383e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_type __num_buckets = bucket_count(); 384e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_type __num_buckets_hint = (size_type)((float)__to_size / max_load_factor()); 385e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (__num_buckets_hint <= __num_buckets) { 3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 387e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 388e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint); 3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_rehash(__num_buckets); 3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 3949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 396e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ::_M_reduce() { 397e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_type __num_buckets = bucket_count(); 398e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // We only try to reduce the hashtable if the theorical load factor 399e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // is lower than a fraction of the max load factor: 400e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // 4 factor is coming from the fact that prime number list is almost a 401e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // geometrical suite with reason 2, as we try to jump 2 levels is means 402e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // a 4 factor. 403e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if ((float)size() / (float)__num_buckets > max_load_factor() / 4.0f) 4049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 405e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 406e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const size_type *__first; 407e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const size_type *__prev; 408e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV _Stl_prime_type::_S_prev_sizes(__num_buckets, __first, __prev); 409e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 410e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /* We are only going to reduce number of buckets if moving to yet the previous number 411e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * of buckets in the prime numbers would respect the load rule. Otherwise algorithm 412e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * successively removing and adding an element would each time perform an expensive 413e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * rehash operation. */ 414e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const size_type *__prev_prev = __prev; 415e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (__prev_prev != __first) { 416e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott --__prev_prev; 417e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if ((float)size() / (float)*__prev_prev > max_load_factor()) 418e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return; 419e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 420e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott else { 421e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (*__prev >= __num_buckets) 422e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return; 4239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 425e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Can we reduce further: 426e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott while (__prev_prev != __first) { 427e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott --__prev_prev; 428e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if ((float)size() / (float)*__prev_prev > max_load_factor()) 429e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // We cannot reduce further. 430e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott break; 431e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott --__prev; 432e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 433e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 434e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_rehash(*__prev); 435e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 436e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 437e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _Val, class _Key, class _HF, 438e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott class _Traits, class _ExK, class _EqK, class _All> 439e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 440e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott ::_M_resize() { 441e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (load_factor() > max_load_factor()) { 442e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // We have to enlarge 443e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_enlarge(size()); 444e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 445e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott else { 446e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // We can try to reduce size: 447e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_reduce(); 448e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 4499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 4549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::_M_rehash(size_type __num_buckets) { 455e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (_STLP_DEBUG) 456e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_check(); 457e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 4589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsCont __tmp_elems(_M_elems.get_allocator()); 4599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator()); 4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur, __last(_M_elems.end()); 4619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (!_M_elems.empty()) { 4629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __cur = _M_elems.begin(); 4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets); 4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __ite(__cur), __before_ite(__cur); 4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (++__ite; 4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite)); 4679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__ite, ++__before_ite); 4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __prev_bucket = __new_bucket; 4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite; 4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite); 4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node); 4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems.swap(__tmp_elems); 4749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets.swap(__tmp); 4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 4809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_check() const { 4819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //We check that hash code of stored keys haven't change and also that equivalent 4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //relation hasn't been modified 4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __num_buckets = bucket_count(); 4849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (size_t __b = 0; __b < __num_buckets; ++__b) { 4859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(_M_buckets[__b]), __last(_M_buckets[__b + 1]); 4869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __fst(__cur), __snd(__cur); 4879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __cur != __last; ++__cur) { 4889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT( _M_bkt_num(*__cur, __num_buckets) == __b ) 4899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT( !_M_equals(_M_get_key(*__fst), _M_get_key(*__cur)) || _M_equals(_M_get_key(*__snd), _M_get_key(*__cur)) ) 4909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__fst != __snd) 4919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__fst; 4929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__snd != __cur) 4939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__snd; 4949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 4989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 5009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 5019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::clear() { 5029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems.clear(); 5039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0)); 5049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements = 0; 5059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 5089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 5099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 5109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ::_M_copy_from(const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht) { 5119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems.clear(); 5129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end()); 5139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets.resize(__ht._M_buckets.size()); 5149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end()); 5159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __dst(_M_elems.begin()); 5169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()), 5179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __src_end_b(__ht._M_buckets.end()); 5189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end()); 5199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __src != __src_end; ++__src, ++__dst) { 5209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) { 5219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__src_b == __src._M_node) { 5229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__dst_b = __dst._M_node; 5239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 5259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 5269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0)); 5299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements = __ht._M_num_elements; 5309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_max_load_factor = __ht._M_max_load_factor; 5319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef __iterator__ 5349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef const_iterator 5359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef __size_type__ 5369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef __reference__ 5379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef size_type 5389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef value_type 5399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef key_type 5409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef __stl_num_primes 5419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 5439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef hashtable 5449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 5459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 5469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 5489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_HASHTABLE_C */ 5509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 5529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 5539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 554