Sierra Toolkit Version of the Day
hashtable_eastl.cpp
00001 /*
00002 Copyright (C) 2009-2010 Electronic Arts, Inc.  All rights reserved.
00003 
00004 Redistribution and use in source and binary forms, with or without
00005 modification, are permitted provided that the following conditions
00006 are met:
00007 
00008 1.  Redistributions of source code must retain the above copyright
00009     notice, this list of conditions and the following disclaimer.
00010 2.  Redistributions in binary form must reproduce the above copyright
00011     notice, this list of conditions and the following disclaimer in the
00012     documentation and/or other materials provided with the distribution.
00013 3.  Neither the name of Electronic Arts, Inc. ("EA") nor the names of
00014     its contributors may be used to endorse or promote products derived
00015     from this software without specific prior written permission.
00016 
00017 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
00018 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00019 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00020 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
00021 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00022 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00023 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00024 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027 */
00028 
00030 // EASTL/hashtable.cpp
00031 //
00032 // Copyright (c) 2005, Electronic Arts. All rights reserved.
00033 // Written and maintained by Paul Pedriana.
00035 
00036 
00037 
00038 #include <stk_util/util/hashtable_eastl.h>
00039 #include <stk_util/util/utility_eastl.h>
00040 #include <math.h>  // Not all compilers support <cmath> and std::ceil(), which we need below.
00041 #include <stddef.h>
00042 
00043 
00044 #ifdef _MSC_VER
00045     #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++.
00046 #endif
00047 
00048 
00049 namespace eastl
00050 {
00051 
00058     EASTL_API void* gpEmptyBucketArray[2] = { NULL, (void*)uintptr_t(~0) };
00059 
00060 
00061 
00070     const uint32_t gPrimeNumberArray[] =
00071     {
00072         2u, 3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u, 29u, 31u,
00073         37u, 41u, 43u, 47u, 53u, 59u, 61u, 67u, 71u, 73u, 79u,
00074         83u, 89u, 97u, 103u, 109u, 113u, 127u, 137u, 139u, 149u,
00075         157u, 167u, 179u, 193u, 199u, 211u, 227u, 241u, 257u,
00076         277u, 293u, 313u, 337u, 359u, 383u, 409u, 439u, 467u,
00077         503u, 541u, 577u, 619u, 661u, 709u, 761u, 823u, 887u,
00078         953u, 1031u, 1109u, 1193u, 1289u, 1381u, 1493u, 1613u,
00079         1741u, 1879u, 2029u, 2179u, 2357u, 2549u, 2753u, 2971u,
00080         3209u, 3469u, 3739u, 4027u, 4349u, 4703u, 5087u, 5503u,
00081         5953u, 6427u, 6949u, 7517u, 8123u, 8783u, 9497u, 10273u,
00082         11113u, 12011u, 12983u, 14033u, 15173u, 16411u, 17749u,
00083         19183u, 20753u, 22447u, 24281u, 26267u, 28411u, 30727u,
00084         33223u, 35933u, 38873u, 42043u, 45481u, 49201u, 53201u,
00085         57557u, 62233u, 67307u, 72817u, 78779u, 85229u, 92203u,
00086         99733u, 107897u, 116731u, 126271u, 136607u, 147793u,
00087         159871u, 172933u, 187091u, 202409u, 218971u, 236897u,
00088         256279u, 277261u, 299951u, 324503u, 351061u, 379787u,
00089         410857u, 444487u, 480881u, 520241u, 562841u, 608903u,
00090         658753u, 712697u, 771049u, 834181u, 902483u, 976369u,
00091         1056323u, 1142821u, 1236397u, 1337629u, 1447153u, 1565659u,
00092         1693859u, 1832561u, 1982627u, 2144977u, 2320627u, 2510653u,
00093         2716249u, 2938679u, 3179303u, 3439651u, 3721303u, 4026031u,
00094         4355707u, 4712381u, 5098259u, 5515729u, 5967347u, 6456007u,
00095         6984629u, 7556579u, 8175383u, 8844859u, 9569143u, 10352717u,
00096         11200489u, 12117689u, 13109983u, 14183539u, 15345007u,
00097         16601593u, 17961079u, 19431899u, 21023161u, 22744717u,
00098         24607243u, 26622317u, 28802401u, 31160981u, 33712729u,
00099         36473443u, 39460231u, 42691603u, 46187573u, 49969847u,
00100         54061849u, 58488943u, 63278561u, 68460391u, 74066549u,
00101         80131819u, 86693767u, 93793069u, 101473717u, 109783337u,
00102         118773397u, 128499677u, 139022417u, 150406843u, 162723577u,
00103         176048909u, 190465427u, 206062531u, 222936881u, 241193053u,
00104         260944219u, 282312799u, 305431229u, 330442829u, 357502601u,
00105         386778277u, 418451333u, 452718089u, 489790921u, 529899637u,
00106         573292817u, 620239453u, 671030513u, 725980837u, 785430967u,
00107         849749479u, 919334987u, 994618837u, 1076067617u, 1164186217u,
00108         1259520799u, 1362662261u, 1474249943u, 1594975441u,
00109         1725587117u, 1866894511u, 2019773507u, 2185171673u,
00110         2364114217u, 2557710269u, 2767159799u, 2993761039u,
00111         3238918481u, 3504151727u, 3791104843u, 4101556399u,
00112         4294967291u,
00113         4294967291u // Sentinel so we don't have to test result of lower_bound
00114     };
00115 
00116 
00121     const uint32_t kPrimeCount = (sizeof(gPrimeNumberArray) / sizeof(gPrimeNumberArray[0]) - 1);
00122 
00123 
00127     uint32_t prime_rehash_policy::GetPrevBucketCountOnly(uint32_t nBucketCountHint)
00128     {
00129         const uint32_t nPrime = *(eastl::upper_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, nBucketCountHint) - 1);
00130         return nPrime;
00131     }
00132 
00133 
00138     uint32_t prime_rehash_policy::GetPrevBucketCount(uint32_t nBucketCountHint) const
00139     {
00140         const uint32_t nPrime = *(eastl::upper_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, nBucketCountHint) - 1);
00141 
00142         mnNextResize = (uint32_t)ceil(nPrime * mfMaxLoadFactor);
00143         return nPrime;
00144     }
00145 
00146 
00151     uint32_t prime_rehash_policy::GetNextBucketCount(uint32_t nBucketCountHint) const
00152     {
00153         const uint32_t nPrime = *eastl::lower_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, nBucketCountHint);
00154 
00155         mnNextResize = (uint32_t)ceil(nPrime * mfMaxLoadFactor);
00156         return nPrime;
00157     }
00158 
00159 
00164     uint32_t prime_rehash_policy::GetBucketCount(uint32_t nElementCount) const
00165     {
00166         const uint32_t nMinBucketCount = (uint32_t)(nElementCount / mfMaxLoadFactor);
00167         const uint32_t nPrime          = *eastl::lower_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, nMinBucketCount);
00168 
00169         mnNextResize = (uint32_t)ceil(nPrime * mfMaxLoadFactor);
00170         return nPrime;
00171     }
00172 
00173 
00180     eastl::pair<bool, uint32_t>
00181     prime_rehash_policy::GetRehashRequired(uint32_t nBucketCount, uint32_t nElementCount, uint32_t nElementAdd) const
00182     {
00183         if((nElementCount + nElementAdd) > mnNextResize) // It is significant that we specify > next resize and not >= next resize.
00184         {
00185             if(nBucketCount == 1) // We force rehashing to occur if the bucket count is < 2.
00186                 nBucketCount = 0;
00187 
00188             float fMinBucketCount = (nElementCount + nElementAdd) / mfMaxLoadFactor;
00189 
00190             if(fMinBucketCount > (float)nBucketCount)
00191             {
00192                 fMinBucketCount       = eastl::max_alt(fMinBucketCount, mfGrowthFactor * nBucketCount);
00193                 const uint32_t nPrime = *eastl::lower_bound(gPrimeNumberArray, gPrimeNumberArray + kPrimeCount, (uint32_t)fMinBucketCount);
00194                 mnNextResize          = (uint32_t)ceil(nPrime * mfMaxLoadFactor);
00195 
00196                 return eastl::pair<bool, uint32_t>(true, nPrime);
00197             }
00198             else
00199             {
00200                 mnNextResize = (uint32_t)ceil(nBucketCount * mfMaxLoadFactor);
00201                 return eastl::pair<bool, uint32_t>(false, (uint32_t)0);
00202             }
00203         }
00204 
00205         return eastl::pair<bool, uint32_t>(false, (uint32_t)0);
00206     }
00207 
00208 
00209 } // namespace eastl
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends