60 #ifndef EASTL_INTERNAL_HASHTABLE_H 61 #define EASTL_INTERNAL_HASHTABLE_H 64 #include <stk_util/util/config_eastl.h> 65 #include <stk_util/util/type_traits_eastl.h> 66 #include <stk_util/util/allocator_eastl.h> 67 #include <stk_util/util/iterator_eastl.h> 68 #include <stk_util/util/functional_eastl.h> 69 #include <stk_util/util/utility_eastl.h> 70 #include <stk_util/util/algorithm_eastl.h> 74 #pragma warning(push, 0) 85 #pragma warning(disable: 4512) // 'class' : assignment operator could not be generated. 86 #pragma warning(disable: 4530) // C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc 97 #ifndef EASTL_HASHTABLE_DEFAULT_NAME 98 #define EASTL_HASHTABLE_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hashtable" // Unless the user overrides something, this is "EASTL hashtable". 104 #ifndef EASTL_HASHTABLE_DEFAULT_ALLOCATOR 105 #define EASTL_HASHTABLE_DEFAULT_ALLOCATOR allocator_type(EASTL_HASHTABLE_DEFAULT_NAME) 128 template <
typename Value,
bool bCacheHashCode>
131 template <
typename Value>
136 eastl_size_t mnHashCode;
139 template <
typename Value>
155 template <
typename Value,
bool bCacheHashCode>
168 { mpNode = mpNode->mpNext; }
180 template <
typename Value,
bool bConst,
bool bCacheHashCode>
187 typedef Value value_type;
190 typedef ptrdiff_t difference_type;
191 typedef EASTL_ITC_NS::forward_iterator_tag iterator_category;
201 {
return base_type::mpNode->mValue; }
204 {
return &(base_type::mpNode->mValue); }
207 { base_type::increment();
return *
this; }
210 {
node_iterator temp(*
this); base_type::increment();
return temp; }
226 template <
typename Value,
bool bCacheHashCode>
243 : mpNode(pNode), mpBucket(pBucket) { }
245 void increment_bucket()
248 while(*mpBucket == NULL)
255 mpNode = mpNode->mpNext;
257 while(mpNode == NULL)
258 mpNode = *++mpBucket;
276 template <
typename Value,
bool bConst,
bool bCacheHashCode>
284 typedef Value value_type;
287 typedef ptrdiff_t difference_type;
288 typedef EASTL_ITC_NS::forward_iterator_tag iterator_category;
301 {
return base_type::mpNode->mValue; }
304 {
return &(base_type::mpNode->mValue); }
307 { base_type::increment();
return *
this; }
313 {
return base_type::mpNode; }
330 template <
typename Iterator>
331 inline typename eastl::iterator_traits<Iterator>::difference_type
335 template <
typename Iterator>
336 inline typename eastl::iterator_traits<Iterator>::difference_type
337 distance_fw_impl(Iterator first, Iterator last, EASTL_ITC_NS::forward_iterator_tag)
338 {
return eastl::distance(first, last); }
340 template <
typename Iterator>
341 inline typename eastl::iterator_traits<Iterator>::difference_type
342 ht_distance(Iterator first, Iterator last)
344 typedef typename eastl::iterator_traits<Iterator>::iterator_category IC;
360 uint32_t operator()(uint32_t r, uint32_t n)
const 384 float mfMaxLoadFactor;
385 float mfGrowthFactor;
386 mutable uint32_t mnNextResize;
390 : mfMaxLoadFactor(fMaxLoadFactor), mfGrowthFactor(2.f), mnNextResize(0) { }
392 float GetMaxLoadFactor()
const 393 {
return mfMaxLoadFactor; }
397 static uint32_t GetPrevBucketCountOnly(uint32_t nBucketCountHint);
401 uint32_t GetPrevBucketCount(uint32_t nBucketCountHint)
const;
405 uint32_t GetNextBucketCount(uint32_t nBucketCountHint)
const;
409 uint32_t GetBucketCount(uint32_t nElementCount)
const;
416 GetRehashRequired(uint32_t nBucketCount, uint32_t nElementCount, uint32_t nElementAdd)
const;
440 template <
typename RehashPolicy,
typename Hashtable>
443 template <
typename Hashtable>
448 float get_max_load_factor()
const 450 const Hashtable*
const pThis =
static_cast<const Hashtable*
>(
this);
451 return pThis->rehash_policy().GetMaxLoadFactor();
456 void set_max_load_factor(
float fMaxLoadFactor)
458 Hashtable*
const pThis =
static_cast<Hashtable*
>(
this);
459 pThis->rehash_policy(prime_rehash_policy(fMaxLoadFactor));
480 template <
typename Key,
typename Value,
typename ExtractKey,
typename Equal,
481 typename H1,
typename H2,
typename H,
bool bCacheHashCode>
490 template <
typename Key,
typename Value,
typename ExtractKey,
typename Equal,
typename H1,
typename H2,
typename H>
494 ExtractKey mExtractKey;
499 H1 hash_function()
const 502 Equal equal_function()
const 505 const Equal& key_eq()
const 512 typedef void* hash_code_t;
513 typedef uint32_t bucket_index_t;
515 hash_code_base(
const ExtractKey& extractKey,
const Equal& eq,
const H1&,
const H2&,
const H& h)
516 : mExtractKey(extractKey), mEqual(eq), mRangedHash(h) { }
518 hash_code_t get_hash_code(
const Key& key)
const 521 bucket_index_t bucket_index(hash_code_t, uint32_t)
const 522 {
return (bucket_index_t)0; }
524 bucket_index_t bucket_index(
const Key& key, hash_code_t, uint32_t nBucketCount)
const 525 {
return (bucket_index_t)mRangedHash(key, nBucketCount); }
528 {
return (bucket_index_t)mRangedHash(mExtractKey(pNode->mValue), nBucketCount); }
531 {
return mEqual(key, mExtractKey(pNode->mValue)); }
560 template <
typename Key,
typename Value,
typename ExtractKey,
typename Equal,
typename H1,
typename H2,
typename H>
561 struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>;
571 template <
typename Key,
typename Value,
typename ExtractKey,
typename Equal,
typename H1,
typename H2>
575 ExtractKey mExtractKey;
583 H1 hash_function()
const 586 Equal equal_function()
const 589 const Equal& key_eq()
const 596 typedef uint32_t hash_code_t;
597 typedef uint32_t bucket_index_t;
601 : mExtractKey(ex), mEqual(eq), m_h1(h1), m_h2(h2) { }
603 hash_code_t get_hash_code(
const Key& key)
const 604 {
return (hash_code_t)m_h1(key); }
606 bucket_index_t bucket_index(hash_code_t c, uint32_t nBucketCount)
const 607 {
return (bucket_index_t)m_h2(c, nBucketCount); }
609 bucket_index_t bucket_index(
const Key&, hash_code_t c, uint32_t nBucketCount)
const 610 {
return (bucket_index_t)m_h2(c, nBucketCount); }
612 bucket_index_t bucket_index(
const node_type* pNode, uint32_t nBucketCount)
const 613 {
return (bucket_index_t)m_h2((hash_code_t)m_h1(mExtractKey(pNode->mValue)), nBucketCount); }
615 bool compare(
const Key& key, hash_code_t, node_type* pNode)
const 616 {
return mEqual(key, mExtractKey(pNode->mValue)); }
618 void copy_code(node_type*,
const node_type*)
const 621 void set_code(node_type*, hash_code_t)
const 642 template <
typename Key,
typename Value,
typename ExtractKey,
typename Equal,
typename H1,
typename H2>
646 ExtractKey mExtractKey;
654 H1 hash_function()
const 657 Equal equal_function()
const 660 const Equal& key_eq()
const 667 typedef uint32_t hash_code_t;
668 typedef uint32_t bucket_index_t;
672 : mExtractKey(ex), mEqual(eq), m_h1(h1), m_h2(h2) { }
674 hash_code_t get_hash_code(
const Key& key)
const 675 {
return (hash_code_t)m_h1(key); }
677 bucket_index_t bucket_index(hash_code_t c, uint32_t nBucketCount)
const 678 {
return (bucket_index_t)m_h2(c, nBucketCount); }
680 bucket_index_t bucket_index(
const Key&, hash_code_t c, uint32_t nBucketCount)
const 681 {
return (bucket_index_t)m_h2(c, nBucketCount); }
683 bucket_index_t bucket_index(
const node_type* pNode, uint32_t nBucketCount)
const 684 {
return (bucket_index_t)m_h2((uint32_t)pNode->mnHashCode, nBucketCount); }
686 bool compare(
const Key& key, hash_code_t c, node_type* pNode)
const 687 {
return (pNode->mnHashCode == c) && mEqual(key, mExtractKey(pNode->mValue)); }
689 void copy_code(node_type* pDest,
const node_type* pSource)
const 690 { pDest->mnHashCode = pSource->mnHashCode; }
692 void set_code(node_type* pDest, hash_code_t c)
const 693 { pDest->mnHashCode = c; }
785 template <
typename Key,
typename Value,
typename Allocator,
typename ExtractKey,
786 typename Equal,
typename H1,
typename H2,
typename H,
787 typename RehashPolicy,
bool bCacheHashCode,
bool bMutableIterators,
bool bUniqueKeys>
789 :
public rehash_base<RehashPolicy, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys> >,
790 public hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, bCacheHashCode>
793 typedef Key key_type;
794 typedef Value value_type;
795 typedef typename ExtractKey::result_type mapped_type;
797 typedef typename hash_code_base_type::hash_code_t hash_code_t;
798 typedef Allocator allocator_type;
799 typedef Equal key_equal;
800 typedef ptrdiff_t difference_type;
801 typedef eastl_size_t size_type;
802 typedef value_type& reference;
803 typedef const value_type& const_reference;
812 typedef hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H,
813 RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys>
this_type;
814 typedef RehashPolicy rehash_policy_type;
815 typedef ExtractKey extract_key_type;
820 using hash_code_base_type::key_eq;
821 using hash_code_base_type::hash_function;
822 using hash_code_base_type::mExtractKey;
823 using hash_code_base_type::get_hash_code;
824 using hash_code_base_type::bucket_index;
825 using hash_code_base_type::compare;
826 using hash_code_base_type::set_code;
828 static const bool kCacheHashCode = bCacheHashCode;
832 kKeyAlignment = EASTL_ALIGN_OF(key_type),
833 kKeyAlignmentOffset = 0,
834 kValueAlignment = EASTL_ALIGN_OF(value_type),
835 kValueAlignmentOffset = 0,
836 kAllocFlagBuckets = 0x00400000
841 size_type mnBucketCount;
842 size_type mnElementCount;
843 RehashPolicy mRehashPolicy;
844 allocator_type mAllocator;
847 hashtable(size_type nBucketCount,
const H1&,
const H2&,
const H&,
const Equal&,
const ExtractKey&,
848 const allocator_type&
allocator = EASTL_HASHTABLE_DEFAULT_ALLOCATOR);
850 template <
typename FowardIterator>
851 hashtable(FowardIterator first, FowardIterator last, size_type nBucketCount,
852 const H1&,
const H2&,
const H&,
const Equal&,
const ExtractKey&,
853 const allocator_type&
allocator = EASTL_HASHTABLE_DEFAULT_ALLOCATOR);
858 allocator_type& get_allocator();
859 void set_allocator(
const allocator_type&
allocator);
870 i.increment_bucket();
878 i.increment_bucket();
883 {
return iterator(mpBucketArray + mnBucketCount); }
901 {
return mnElementCount == 0; }
903 size_type size()
const 904 {
return mnElementCount; }
906 size_type bucket_count()
const 907 {
return mnBucketCount; }
909 size_type bucket_size(size_type n)
const 910 {
return (size_type)eastl::distance(begin(n), end(n)); }
916 float load_factor()
const 917 {
return (
float)mnElementCount / (float)mnBucketCount; }
934 {
return mRehashPolicy; }
942 insert_return_type insert(
const value_type& value);
943 iterator insert(const_iterator,
const value_type& value);
945 template <
typename InputIterator>
946 void insert(InputIterator first, InputIterator last);
949 iterator erase(iterator position);
950 iterator erase(iterator first, iterator last);
953 size_type erase(
const key_type& k);
956 void clear(
bool clearBuckets);
958 void rehash(size_type nBucketCount);
961 iterator find(
const key_type& key);
962 const_iterator find(
const key_type& key)
const;
979 template <
typename U,
typename UHash,
typename BinaryPredicate>
980 iterator
find_as(
const U& u, UHash uhash, BinaryPredicate predicate);
982 template <
typename U,
typename UHash,
typename BinaryPredicate>
983 const_iterator
find_as(
const U& u, UHash uhash, BinaryPredicate predicate)
const;
985 template <
typename U>
988 template <
typename U>
989 const_iterator
find_as(
const U& u)
const;
996 size_type count(
const key_type& k)
const;
1002 bool validate()
const;
1003 int validate_iterator(const_iterator i)
const;
1006 node_type* DoAllocateNode(
const value_type& value);
1007 node_type* DoAllocateNodeFromKey(
const key_type& key);
1008 void DoFreeNode(node_type* pNode);
1009 void DoFreeNodes(node_type** pBucketArray, size_type);
1011 node_type** DoAllocateBuckets(size_type n);
1012 void DoFreeBuckets(node_type** pBucketArray, size_type n);
1015 iterator DoInsertValue(
const value_type& value, false_type);
1018 iterator DoInsertKey(
const key_type& key, false_type);
1020 void DoRehash(size_type nBucketCount);
1021 node_type* DoFindNode(node_type* pNode,
const key_type& k, hash_code_t c)
const;
1023 template <
typename U,
typename BinaryPredicate>
1024 node_type* DoFindNode(node_type* pNode,
const U& u, BinaryPredicate predicate)
const;
1026 node_type* DoFindNode(node_type* pNode, hash_code_t c)
const;
1038 template <
typename Value,
bool bCacheHashCode>
1039 inline bool operator==(
const node_iterator_base<Value, bCacheHashCode>& a,
const node_iterator_base<Value, bCacheHashCode>& b)
1040 {
return a.mpNode == b.mpNode; }
1042 template <
typename Value,
bool bCacheHashCode>
1043 inline bool operator!=(
const node_iterator_base<Value, bCacheHashCode>& a,
const node_iterator_base<Value, bCacheHashCode>& b)
1044 {
return a.mpNode != b.mpNode; }
1053 template <
typename Value,
bool bCacheHashCode>
1054 inline bool operator==(
const hashtable_iterator_base<Value, bCacheHashCode>& a,
const hashtable_iterator_base<Value, bCacheHashCode>& b)
1055 {
return a.mpNode == b.mpNode; }
1057 template <
typename Value,
bool bCacheHashCode>
1058 inline bool operator!=(
const hashtable_iterator_base<Value, bCacheHashCode>& a,
const hashtable_iterator_base<Value, bCacheHashCode>& b)
1059 {
return a.mpNode != b.mpNode; }
1068 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1069 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1070 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>
1071 ::hashtable(size_type nBucketCount,
const H1& h1,
const H2& h2,
const H& h,
1072 const Eq& eq,
const EK& ek,
const allocator_type& allocator)
1073 : rehash_base<RP, hashtable>(),
1074 hash_code_base<K, V, EK, Eq, H1, H2, H, bC>(ek, eq, h1, h2, h),
1078 mAllocator(allocator)
1080 if(nBucketCount < 2)
1084 EASTL_ASSERT(nBucketCount < 10000000);
1085 mnBucketCount = (size_type)mRehashPolicy.GetNextBucketCount((uint32_t)nBucketCount);
1086 mpBucketArray = DoAllocateBuckets(mnBucketCount);
1092 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1093 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1094 template <
typename FowardIterator>
1095 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::hashtable(FowardIterator first, FowardIterator last, size_type nBucketCount,
1096 const H1& h1,
const H2& h2,
const H& h,
1097 const Eq& eq,
const EK& ek,
const allocator_type& allocator)
1098 : rehash_base<rehash_policy_type, hashtable>(),
1099 hash_code_base<key_type, value_type, extract_key_type, key_equal, h1_type, h2_type, h_type, kCacheHashCode>(ek, eq, h1, h2, h),
1103 mAllocator(allocator)
1105 if(nBucketCount < 2)
1107 const size_type nElementCount = (size_type)eastl::ht_distance(first, last);
1108 mnBucketCount = (size_type)mRehashPolicy.GetBucketCount((uint32_t)nElementCount);
1112 EASTL_ASSERT(nBucketCount < 10000000);
1113 mnBucketCount = nBucketCount;
1116 mpBucketArray = DoAllocateBuckets(mnBucketCount);
1118 #if EASTL_EXCEPTIONS_ENABLED 1122 for(; first != last; ++first)
1124 #if EASTL_EXCEPTIONS_ENABLED 1129 DoFreeBuckets(mpBucketArray, mnBucketCount);
1137 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1138 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1139 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::hashtable(
const this_type& x)
1140 : rehash_base<RP, hashtable>(x),
1141 hash_code_base<K, V, EK, Eq, H1, H2, H, bC>(x),
1142 mnBucketCount(x.mnBucketCount),
1143 mnElementCount(x.mnElementCount),
1144 mRehashPolicy(x.mRehashPolicy),
1145 mAllocator(x.mAllocator)
1149 mpBucketArray = DoAllocateBuckets(mnBucketCount);
1151 #if EASTL_EXCEPTIONS_ENABLED 1155 for(size_type i = 0; i < x.mnBucketCount; ++i)
1157 node_type* pNodeSource = x.mpBucketArray[i];
1158 node_type** ppNodeDest = mpBucketArray + i;
1162 *ppNodeDest = DoAllocateNode(pNodeSource->mValue);
1163 copy_code(*ppNodeDest, pNodeSource);
1164 ppNodeDest = &(*ppNodeDest)->mpNext;
1165 pNodeSource = pNodeSource->mpNext;
1168 #if EASTL_EXCEPTIONS_ENABLED 1173 DoFreeBuckets(mpBucketArray, mnBucketCount);
1188 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1189 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1190 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::allocator_type&
1191 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::get_allocator()
1198 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1199 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1200 inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::set_allocator(
const allocator_type& allocator)
1202 mAllocator = allocator;
1207 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1208 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1209 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::this_type&
1210 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::operator=(
const this_type& x)
1216 #if EASTL_ALLOCATOR_COPY_ENABLED 1217 mAllocator = x.mAllocator;
1220 insert(x.begin(), x.end());
1227 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1228 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1229 inline hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::~hashtable()
1232 DoFreeBuckets(mpBucketArray, mnBucketCount);
1237 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1238 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1239 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1240 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNode(
const value_type& value)
1242 node_type*
const pNode = (node_type*)
allocate_memory(mAllocator,
sizeof(node_type), kValueAlignment, kValueAlignmentOffset);
1244 #if EASTL_EXCEPTIONS_ENABLED 1248 ::new(&pNode->mValue) value_type(value);
1249 pNode->mpNext = NULL;
1251 #if EASTL_EXCEPTIONS_ENABLED 1255 EASTLFree(mAllocator, pNode,
sizeof(node_type));
1263 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1264 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1265 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1266 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNodeFromKey(
const key_type& key)
1268 node_type*
const pNode = (node_type*)
allocate_memory(mAllocator,
sizeof(node_type), kValueAlignment, kValueAlignmentOffset);
1270 #if EASTL_EXCEPTIONS_ENABLED 1274 ::new(&pNode->mValue) value_type(key);
1275 pNode->mpNext = NULL;
1277 #if EASTL_EXCEPTIONS_ENABLED 1281 EASTLFree(mAllocator, pNode,
sizeof(node_type));
1289 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1290 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1291 inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeNode(node_type* pNode)
1293 pNode->~node_type();
1294 EASTLFree(mAllocator, pNode,
sizeof(node_type));
1299 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1300 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1301 void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeNodes(node_type** pNodeArray, size_type n)
1303 for(size_type i = 0; i < n; ++i)
1305 node_type* pNode = pNodeArray[i];
1308 node_type*
const pTempNode = pNode;
1309 pNode = pNode->mpNext;
1310 DoFreeNode(pTempNode);
1312 pNodeArray[i] = NULL;
1318 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1319 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1320 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type**
1321 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateBuckets(size_type n)
1325 EASTL_ASSERT(n > 1);
1326 EASTL_CT_ASSERT(kAllocFlagBuckets == 0x00400000);
1327 node_type**
const pBucketArray = (node_type**)EASTLAllocFlags(mAllocator, (n + 1) *
sizeof(node_type*), kAllocFlagBuckets);
1329 memset(pBucketArray, 0, n *
sizeof(node_type*));
1330 pBucketArray[n] =
reinterpret_cast<node_type*
>((uintptr_t)~0);
1331 return pBucketArray;
1336 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1337 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1338 inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeBuckets(node_type** pBucketArray, size_type n)
1344 EASTLFree(mAllocator, pBucketArray, (n + 1) *
sizeof(node_type*));
1349 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1350 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1351 void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::swap(this_type& x)
1353 if(mAllocator == x.mAllocator)
1356 hash_code_base<K, V, EK, Eq, H1, H2, H, bC>::base_swap(x);
1364 const this_type temp(*
this);
1371 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1372 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1373 inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::rehash_policy(
const rehash_policy_type& rehashPolicy)
1375 mRehashPolicy = rehashPolicy;
1377 const size_type nBuckets = rehashPolicy.
GetBucketCount((uint32_t)mnElementCount);
1379 if(nBuckets > mnBucketCount)
1385 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1386 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1387 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator 1388 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find(
const key_type& k)
1390 const hash_code_t c = get_hash_code(k);
1391 const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1393 node_type*
const pNode = DoFindNode(mpBucketArray[n], k, c);
1394 return pNode ? iterator(pNode, mpBucketArray + n) : iterator(mpBucketArray + mnBucketCount);
1399 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1400 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1401 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
1402 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find(
const key_type& k)
const 1404 const hash_code_t c = get_hash_code(k);
1405 const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1407 node_type*
const pNode = DoFindNode(mpBucketArray[n], k, c);
1408 return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount);
1413 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1414 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1415 template <
typename U,
typename UHash,
typename BinaryPredicate>
1416 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1417 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(
const U& other, UHash uhash, BinaryPredicate predicate)
1419 const hash_code_t c = (hash_code_t)uhash(other);
1420 const size_type n = (size_type)(c % mnBucketCount);
1422 node_type*
const pNode = DoFindNode(mpBucketArray[n], other, predicate);
1423 return pNode ?
iterator(pNode, mpBucketArray + n) :
iterator(mpBucketArray + mnBucketCount);
1428 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1429 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1430 template <
typename U,
typename UHash,
typename BinaryPredicate>
1431 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator 1432 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(
const U& other, UHash uhash, BinaryPredicate predicate)
const 1434 const hash_code_t c = (hash_code_t)uhash(other);
1435 const size_type n = (size_type)(c % mnBucketCount);
1437 node_type*
const pNode = DoFindNode(mpBucketArray[n], other, predicate);
1438 return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount);
1456 template <
typename H,
typename U>
1458 {
return hashTable.find_as(u,
eastl::hash<U>(), eastl::equal_to_2<const typename H::key_type, U>()); }
1460 template <
typename H,
typename U>
1461 inline typename H::const_iterator hashtable_find(
const H& hashTable, U u)
1462 {
return hashTable.find_as(u,
eastl::hash<U>(), eastl::equal_to_2<const typename H::key_type, U>()); }
1466 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1467 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1468 template <
typename U>
1469 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1470 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(
const U& other)
1477 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1478 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1479 template <
typename U>
1480 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
1481 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(
const U& other)
const 1488 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1489 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1490 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1491 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_by_hash(hash_code_t c)
1493 const size_type n = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
1495 node_type*
const pNode = DoFindNode(mpBucketArray[n], c);
1496 return pNode ?
iterator(pNode, mpBucketArray + n) :
iterator(mpBucketArray + mnBucketCount);
1500 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1501 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1502 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator 1503 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_by_hash(hash_code_t c)
const 1505 const size_type n = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
1507 node_type*
const pNode = DoFindNode(mpBucketArray[n], c);
1508 return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount);
1512 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1513 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1514 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::size_type
1515 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::count(
const key_type& k)
const 1517 const hash_code_t c = get_hash_code(k);
1518 const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1519 size_type result = 0;
1523 for(node_type* pNode = mpBucketArray[n]; pNode; pNode = pNode->mpNext)
1525 if(compare(k, c, pNode))
1533 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1534 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1535 eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator,
1536 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator>
1537 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::equal_range(
const key_type& k)
1539 const hash_code_t c = get_hash_code(k);
1540 const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1542 node_type** head = mpBucketArray + n;
1543 node_type* pNode = DoFindNode(*head, k, c);
1547 node_type* p1 = pNode->mpNext;
1549 for(; p1; p1 = p1->mpNext)
1551 if(!compare(k, c, p1))
1555 iterator first(pNode, head);
1556 iterator last(p1, head);
1559 last.increment_bucket();
1565 iterator(mpBucketArray + mnBucketCount));
1571 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1572 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1573 eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator,
1574 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator>
1575 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::equal_range(
const key_type& k)
const 1577 const hash_code_t c = get_hash_code(k);
1578 const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1579 node_type** head = mpBucketArray + n;
1580 node_type* pNode = DoFindNode(*head, k, c);
1584 node_type* p1 = pNode->mpNext;
1586 for(; p1; p1 = p1->mpNext)
1588 if(!compare(k, c, p1))
1592 const_iterator first(pNode, head);
1593 const_iterator last(p1, head);
1596 last.increment_bucket();
1602 const_iterator(mpBucketArray + mnBucketCount));
1607 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1608 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1609 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1610 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFindNode(node_type* pNode,
const key_type& k, hash_code_t c)
const 1612 for(; pNode; pNode = pNode->mpNext)
1614 if(compare(k, c, pNode))
1622 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1623 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1624 template <
typename U,
typename BinaryPredicate>
1625 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1626 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFindNode(node_type* pNode,
const U& other, BinaryPredicate predicate)
const 1628 for(; pNode; pNode = pNode->mpNext)
1630 if(predicate(mExtractKey(pNode->mValue), other))
1638 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1639 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1640 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1641 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFindNode(node_type* pNode, hash_code_t c)
const 1643 for(; pNode; pNode = pNode->mpNext)
1645 if(pNode->mnHashCode == c)
1653 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1654 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1655 eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator,
bool>
1656 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(
const value_type& value, true_type)
1658 const key_type& k = mExtractKey(value);
1659 const hash_code_t c = get_hash_code(k);
1660 size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1661 node_type*
const pNode = DoFindNode(mpBucketArray[n], k, c);
1665 const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
1669 node_type*
const pNodeNew = DoAllocateNode(value);
1670 set_code(pNodeNew, c);
1672 #if EASTL_EXCEPTIONS_ENABLED 1678 n = (size_type)bucket_index(k, c, (uint32_t)bRehash.second);
1679 DoRehash(bRehash.second);
1682 EASTL_ASSERT((
void**)mpBucketArray != &gpEmptyBucketArray[0]);
1683 pNodeNew->mpNext = mpBucketArray[n];
1684 mpBucketArray[n] = pNodeNew;
1688 #if EASTL_EXCEPTIONS_ENABLED 1692 DoFreeNode(pNodeNew);
1703 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1704 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1705 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1706 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(
const value_type& value, false_type)
1708 const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
1711 DoRehash(bRehash.second);
1713 const key_type& k = mExtractKey(value);
1714 const hash_code_t c = get_hash_code(k);
1715 const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1717 node_type*
const pNodeNew = DoAllocateNode(value);
1718 set_code(pNodeNew, c);
1726 node_type*
const pNodePrev = DoFindNode(mpBucketArray[n], k, c);
1728 if(pNodePrev == NULL)
1730 EASTL_ASSERT((
void**)mpBucketArray != &gpEmptyBucketArray[0]);
1731 pNodeNew->mpNext = mpBucketArray[n];
1732 mpBucketArray[n] = pNodeNew;
1736 pNodeNew->mpNext = pNodePrev->mpNext;
1737 pNodePrev->mpNext = pNodeNew;
1742 return iterator(pNodeNew, mpBucketArray + n);
1747 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1748 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1749 eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator,
bool>
1750 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertKey(
const key_type& key, true_type)
1752 const hash_code_t c = get_hash_code(key);
1753 size_type n = (size_type)bucket_index(key, c, (uint32_t)mnBucketCount);
1754 node_type*
const pNode = DoFindNode(mpBucketArray[n], key, c);
1758 const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
1762 node_type*
const pNodeNew = DoAllocateNodeFromKey(key);
1763 set_code(pNodeNew, c);
1765 #if EASTL_EXCEPTIONS_ENABLED 1771 n = (size_type)bucket_index(key, c, (uint32_t)bRehash.second);
1772 DoRehash(bRehash.second);
1775 EASTL_ASSERT((
void**)mpBucketArray != &gpEmptyBucketArray[0]);
1776 pNodeNew->mpNext = mpBucketArray[n];
1777 mpBucketArray[n] = pNodeNew;
1781 #if EASTL_EXCEPTIONS_ENABLED 1785 DoFreeNode(pNodeNew);
1796 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1797 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1798 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1799 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertKey(
const key_type& key, false_type)
1801 const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
1804 DoRehash(bRehash.second);
1806 const hash_code_t c = get_hash_code(key);
1807 const size_type n = (size_type)bucket_index(key, c, (uint32_t)mnBucketCount);
1809 node_type*
const pNodeNew = DoAllocateNodeFromKey(key);
1810 set_code(pNodeNew, c);
1818 node_type*
const pNodePrev = DoFindNode(mpBucketArray[n], key, c);
1820 if(pNodePrev == NULL)
1822 EASTL_ASSERT((
void**)mpBucketArray != &gpEmptyBucketArray[0]);
1823 pNodeNew->mpNext = mpBucketArray[n];
1824 mpBucketArray[n] = pNodeNew;
1828 pNodeNew->mpNext = pNodePrev->mpNext;
1829 pNodePrev->mpNext = pNodeNew;
1834 return iterator(pNodeNew, mpBucketArray + n);
1839 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1840 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1841 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
1842 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(
const value_type& value)
1844 return DoInsertValue(value, integral_constant<bool, bU>());
1849 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1850 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1851 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1852 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(const_iterator,
const value_type& value)
1856 #ifdef __MWERKS__ // The Metrowerks compiler has a bug. 1857 insert_return_type result =
insert(value);
1858 return result.first;
1860 #elif defined(__GNUC__) && (__GNUC__ < 3) // If using old GCC (GCC 2.x has a bug which we work around) 1861 EASTL_ASSERT(empty());
1862 DoInsertValue(value, integral_constant<bool, bU>());
1865 insert_return_type result = DoInsertValue(value, integral_constant<bool, bU>());
1866 return result.first;
1872 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1873 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1874 template <
typename InputIterator>
1876 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(InputIterator first, InputIterator last)
1878 const uint32_t nElementAdd = (uint32_t)eastl::ht_distance(first, last);
1879 const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, nElementAdd);
1882 DoRehash(bRehash.second);
1884 for(; first != last; ++first)
1886 #ifdef __MWERKS__ // The Metrowerks compiler has a bug. 1889 DoInsertValue(*first, integral_constant<bool, bU>());
1896 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1897 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1898 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1899 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(iterator i)
1904 node_type* pNode = i.mpNode;
1905 node_type* pNodeCurrent = *i.mpBucket;
1907 if(pNodeCurrent == pNode)
1908 *i.mpBucket = pNodeCurrent->mpNext;
1913 node_type* pNodeNext = pNodeCurrent->mpNext;
1915 while(pNodeNext != pNode)
1917 pNodeCurrent = pNodeNext;
1918 pNodeNext = pNodeCurrent->mpNext;
1921 pNodeCurrent->mpNext = pNodeNext->mpNext;
1932 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1933 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1934 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1935 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(iterator first, iterator last)
1937 while(first != last)
1938 first = erase(first);
1944 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1945 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1946 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::reverse_iterator
1947 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(reverse_iterator position)
1949 return reverse_iterator(erase((++position).base()));
1954 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1955 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1956 inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::reverse_iterator
1957 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(reverse_iterator first, reverse_iterator last)
1966 return reverse_iterator(erase((++last).base(), (++first).base()));
1971 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
1972 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
1973 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::size_type
1974 hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(
const key_type& k)
1980 const hash_code_t c = get_hash_code(k);
1981 const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1982 const size_type nElementCountSaved = mnElementCount;
1984 node_type** pBucketArray = mpBucketArray + n;
1986 while(*pBucketArray && !compare(k, c, *pBucketArray))
1987 pBucketArray = &(*pBucketArray)->mpNext;
1989 while(*pBucketArray && compare(k, c, *pBucketArray))
1991 node_type*
const pNode = *pBucketArray;
1992 *pBucketArray = pNode->mpNext;
1997 return nElementCountSaved - mnElementCount;
2002 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2003 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2004 inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::clear()
2006 DoFreeNodes(mpBucketArray, mnBucketCount);
2012 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2013 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2014 inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::clear(
bool clearBuckets)
2016 DoFreeNodes(mpBucketArray, mnBucketCount);
2019 DoFreeBuckets(mpBucketArray, mnBucketCount);
2027 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2028 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2029 inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::reset()
2038 mpBucketArray = (node_type**)&gpEmptyBucketArray[0];
2041 memcpy(&mpBucketArray, &p,
sizeof(mpBucketArray));
2045 mRehashPolicy.mnNextResize = 0;
2050 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2051 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2052 inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::rehash(size_type nBucketCount)
2056 DoRehash(nBucketCount);
2061 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2062 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2063 void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoRehash(size_type nNewBucketCount)
2065 node_type**
const pBucketArray = DoAllocateBuckets(nNewBucketCount);
2067 #if EASTL_EXCEPTIONS_ENABLED 2073 for(size_type i = 0; i < mnBucketCount; ++i)
2075 while((pNode = mpBucketArray[i]) != NULL)
2077 const size_type nNewBucketIndex = (size_type)bucket_index(pNode, (uint32_t)nNewBucketCount);
2079 mpBucketArray[i] = pNode->mpNext;
2080 pNode->mpNext = pBucketArray[nNewBucketIndex];
2081 pBucketArray[nNewBucketIndex] = pNode;
2085 DoFreeBuckets(mpBucketArray, mnBucketCount);
2086 mnBucketCount = nNewBucketCount;
2087 mpBucketArray = pBucketArray;
2088 #if EASTL_EXCEPTIONS_ENABLED 2095 DoFreeNodes(pBucketArray, nNewBucketCount);
2096 DoFreeBuckets(pBucketArray, nNewBucketCount);
2097 DoFreeNodes(mpBucketArray, mnBucketCount);
2105 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2106 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2107 inline bool hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::validate()
const 2110 if(gpEmptyBucketArray[0] != NULL)
2113 if(gpEmptyBucketArray[1] != (
void*)uintptr_t(~0))
2118 if(mnBucketCount == 0)
2123 if((
void**)mpBucketArray == &gpEmptyBucketArray[0])
2128 if(mnBucketCount != 1)
2133 if(mnBucketCount < 2)
2138 size_type nElementCount = 0;
2140 for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
2143 if(nElementCount != mnElementCount)
2152 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2153 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2154 int hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::validate_iterator(const_iterator i)
const 2158 for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
2161 return (isf_valid | isf_current | isf_can_dereference);
2165 return (isf_valid | isf_current);
2176 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2177 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2178 inline bool operator==(
const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
2179 const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
2181 return (a.size() == b.size()) &&
eastl::equal(a.begin(), a.end(), b.begin());
2187 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2188 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2189 inline bool operator<(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
2190 const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
2199 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2200 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2201 inline bool operator!=(
const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
2202 const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
2208 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2209 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2210 inline bool operator>(
const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
2211 const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
2217 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2218 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2219 inline bool operator<=(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
2220 const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
2226 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2227 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2228 inline bool operator>=(
const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
2229 const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
2235 template <
typename K,
typename V,
typename A,
typename EK,
typename Eq,
2236 typename H1,
typename H2,
typename H,
typename RP,
bool bC,
bool bM,
bool bU>
2237 inline void swap(
const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
2238 const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
2248 #pragma warning(pop) 2251 #endif // Header include guard iterator find_by_hash(hash_code_t c)
const rehash_policy_type & rehash_policy() const
EASTL_API void * gpEmptyBucketArray[2]
uint32_t GetBucketCount(uint32_t nElementCount) const
H::iterator hashtable_find(H &hashTable, U u)
eastl::iterator_traits< Iterator >::difference_type distance_fw_impl(Iterator first, Iterator last, EASTL_ITC_NS::input_iterator_tag)
iterator find_as(const U &u, UHash uhash, BinaryPredicate predicate)
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
void reset(MPI_Comm new_comm)
Function reset determines new parallel_size and parallel_rank. Flushes, closes, and reopens log files...
void * allocate_memory(Allocator &a, size_t n, size_t alignment, size_t alignmentOffset)
Part * find(const PartVector &parts, const std::string &name)
Find a part by name in a collection of parts.
EA Standard Template Library.
bool insert(PartVector &v, Part &part)
Insert a part into a properly ordered collection of parts. Returns true if this is a new insertion...
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)