Sierra Toolkit  Version of the Day
hashtable_eastl.cpp
1 /*
2 Copyright (C) 2009-2010 Electronic Arts, Inc. All rights reserved.
3 
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
6 are met:
7 
8 1. Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13 3. Neither the name of Electronic Arts, Inc. ("EA") nor the names of
14  its contributors may be used to endorse or promote products derived
15  from this software without specific prior written permission.
16 
17 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
18 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28 
30 // EASTL/hashtable.cpp
31 //
32 // Copyright (c) 2005, Electronic Arts. All rights reserved.
33 // Written and maintained by Paul Pedriana.
35 
36 
37 
38 #include <stk_util/util/hashtable_eastl.h>
39 #include <stk_util/util/utility_eastl.h>
40 #include <math.h> // Not all compilers support <cmath> and std::ceil(), which we need below.
41 #include <stddef.h>
42 
43 
44 #ifdef _MSC_VER
45  #pragma warning(disable: 4267) // 'argument' : conversion from 'size_t' to 'const uint32_t', possible loss of data. This is a bogus warning resulting from a bug in VC++.
46 #endif
47 
48 
49 namespace eastl
50 {
51 
58  EASTL_API void* gpEmptyBucketArray[2] = { NULL, (void*)uintptr_t(~0) };
59 
60 
61 
70  const uint32_t gPrimeNumberArray[] =
71  {
72  2u, 3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u, 29u, 31u,
73  37u, 41u, 43u, 47u, 53u, 59u, 61u, 67u, 71u, 73u, 79u,
74  83u, 89u, 97u, 103u, 109u, 113u, 127u, 137u, 139u, 149u,
75  157u, 167u, 179u, 193u, 199u, 211u, 227u, 241u, 257u,
76  277u, 293u, 313u, 337u, 359u, 383u, 409u, 439u, 467u,
77  503u, 541u, 577u, 619u, 661u, 709u, 761u, 823u, 887u,
78  953u, 1031u, 1109u, 1193u, 1289u, 1381u, 1493u, 1613u,
79  1741u, 1879u, 2029u, 2179u, 2357u, 2549u, 2753u, 2971u,
80  3209u, 3469u, 3739u, 4027u, 4349u, 4703u, 5087u, 5503u,
81  5953u, 6427u, 6949u, 7517u, 8123u, 8783u, 9497u, 10273u,
82  11113u, 12011u, 12983u, 14033u, 15173u, 16411u, 17749u,
83  19183u, 20753u, 22447u, 24281u, 26267u, 28411u, 30727u,
84  33223u, 35933u, 38873u, 42043u, 45481u, 49201u, 53201u,
85  57557u, 62233u, 67307u, 72817u, 78779u, 85229u, 92203u,
86  99733u, 107897u, 116731u, 126271u, 136607u, 147793u,
87  159871u, 172933u, 187091u, 202409u, 218971u, 236897u,
88  256279u, 277261u, 299951u, 324503u, 351061u, 379787u,
89  410857u, 444487u, 480881u, 520241u, 562841u, 608903u,
90  658753u, 712697u, 771049u, 834181u, 902483u, 976369u,
91  1056323u, 1142821u, 1236397u, 1337629u, 1447153u, 1565659u,
92  1693859u, 1832561u, 1982627u, 2144977u, 2320627u, 2510653u,
93  2716249u, 2938679u, 3179303u, 3439651u, 3721303u, 4026031u,
94  4355707u, 4712381u, 5098259u, 5515729u, 5967347u, 6456007u,
95  6984629u, 7556579u, 8175383u, 8844859u, 9569143u, 10352717u,
96  11200489u, 12117689u, 13109983u, 14183539u, 15345007u,
97  16601593u, 17961079u, 19431899u, 21023161u, 22744717u,
98  24607243u, 26622317u, 28802401u, 31160981u, 33712729u,
99  36473443u, 39460231u, 42691603u, 46187573u, 49969847u,
100  54061849u, 58488943u, 63278561u, 68460391u, 74066549u,
101  80131819u, 86693767u, 93793069u, 101473717u, 109783337u,
102  118773397u, 128499677u, 139022417u, 150406843u, 162723577u,
103  176048909u, 190465427u, 206062531u, 222936881u, 241193053u,
104  260944219u, 282312799u, 305431229u, 330442829u, 357502601u,
105  386778277u, 418451333u, 452718089u, 489790921u, 529899637u,
106  573292817u, 620239453u, 671030513u, 725980837u, 785430967u,
107  849749479u, 919334987u, 994618837u, 1076067617u, 1164186217u,
108  1259520799u, 1362662261u, 1474249943u, 1594975441u,
109  1725587117u, 1866894511u, 2019773507u, 2185171673u,
110  2364114217u, 2557710269u, 2767159799u, 2993761039u,
111  3238918481u, 3504151727u, 3791104843u, 4101556399u,
112  4294967291u,
113  4294967291u // Sentinel so we don't have to test result of lower_bound
114  };
115 
116 
121  const uint32_t kPrimeCount = (sizeof(gPrimeNumberArray) / sizeof(gPrimeNumberArray[0]) - 1);
122 
123 
127  uint32_t prime_rehash_policy::GetPrevBucketCountOnly(uint32_t nBucketCountHint)
128  {
129  const uint32_t nPrime = *(eastl::upper_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, nBucketCountHint) - 1);
130  return nPrime;
131  }
132 
133 
138  uint32_t prime_rehash_policy::GetPrevBucketCount(uint32_t nBucketCountHint) const
139  {
140  const uint32_t nPrime = *(eastl::upper_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, nBucketCountHint) - 1);
141 
142  mnNextResize = (uint32_t)ceil(nPrime * mfMaxLoadFactor);
143  return nPrime;
144  }
145 
146 
151  uint32_t prime_rehash_policy::GetNextBucketCount(uint32_t nBucketCountHint) const
152  {
153  const uint32_t nPrime = *eastl::lower_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, nBucketCountHint);
154 
155  mnNextResize = (uint32_t)ceil(nPrime * mfMaxLoadFactor);
156  return nPrime;
157  }
158 
159 
164  uint32_t prime_rehash_policy::GetBucketCount(uint32_t nElementCount) const
165  {
166  const uint32_t nMinBucketCount = (uint32_t)(nElementCount / mfMaxLoadFactor);
167  const uint32_t nPrime = *eastl::lower_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, nMinBucketCount);
168 
169  mnNextResize = (uint32_t)ceil(nPrime * mfMaxLoadFactor);
170  return nPrime;
171  }
172 
173 
181  prime_rehash_policy::GetRehashRequired(uint32_t nBucketCount, uint32_t nElementCount, uint32_t nElementAdd) const
182  {
183  if((nElementCount + nElementAdd) > mnNextResize) // It is significant that we specify > next resize and not >= next resize.
184  {
185  if(nBucketCount == 1) // We force rehashing to occur if the bucket count is < 2.
186  nBucketCount = 0;
187 
188  float fMinBucketCount = (nElementCount + nElementAdd) / mfMaxLoadFactor;
189 
190  if(fMinBucketCount > (float)nBucketCount)
191  {
192  fMinBucketCount = eastl::max_alt(fMinBucketCount, mfGrowthFactor * nBucketCount);
193  const uint32_t nPrime = *eastl::lower_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, (uint32_t)fMinBucketCount);
194  mnNextResize = (uint32_t)ceil(nPrime * mfMaxLoadFactor);
195 
196  return eastl::pair<bool, uint32_t>(true, nPrime);
197  }
198  else
199  {
200  mnNextResize = (uint32_t)ceil(nBucketCount * mfMaxLoadFactor);
201  return eastl::pair<bool, uint32_t>(false, (uint32_t)0);
202  }
203  }
204 
205  return eastl::pair<bool, uint32_t>(false, (uint32_t)0);
206  }
207 
208 
209 } // namespace eastl
EASTL_API void * gpEmptyBucketArray[2]
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T &value)
uint32_t GetBucketCount(uint32_t nElementCount) const
uint32_t GetPrevBucketCount(uint32_t nBucketCountHint) const
const uint32_t kPrimeCount
eastl::pair< bool, uint32_t > GetRehashRequired(uint32_t nBucketCount, uint32_t nElementCount, uint32_t nElementAdd) const
uint32_t GetNextBucketCount(uint32_t nBucketCountHint) const
const T & max_alt(const T &a, const T &b)
static uint32_t GetPrevBucketCountOnly(uint32_t nBucketCountHint)
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T &value)
const uint32_t gPrimeNumberArray[]
EA Standard Template Library.