| [391] | 1 | // Copyright (C) 2015 ChaosForge Ltd
|
|---|
| 2 | // http://chaosforge.org/
|
|---|
| 3 | //
|
|---|
| 4 | // This file is part of NV Libraries.
|
|---|
| 5 | // For conditions of distribution and use, see copyright notice in nv.hh
|
|---|
| 6 |
|
|---|
| 7 | #include "nv/stl/container/hash_table.hh"
|
|---|
| 8 | #include "nv/stl/container/hash_table_policy.hh"
|
|---|
| 9 |
|
|---|
| 10 | using namespace nv;
|
|---|
| 11 |
|
|---|
| 12 | static const uint32 s_primes[] =
|
|---|
| 13 | {
|
|---|
| 14 | 2U, 3U, 5U, 7U, 11U, 13U, 17U, 19U,
|
|---|
| 15 | 23U, 29U, 31U, 37U, 41U, 43U, 47U, 53U,
|
|---|
| 16 | 59U, 61U, 67U, 71U, 73U, 79U, 83U, 89U,
|
|---|
| 17 | 97U, 103U, 109U, 113U, 127U, 137U, 139U, 149U,
|
|---|
| 18 | 157U, 167U, 179U, 193U, 199U, 211U, 227U, 241U,
|
|---|
| 19 | 257U, 277U, 293U, 313U, 337U, 359U, 383U, 409U,
|
|---|
| 20 | 439U, 467U, 503U, 541U, 577U, 619U, 661U, 709U,
|
|---|
| 21 | 761U, 823U, 887U, 953U, 1031U, 1109U, 1193U, 1289U,
|
|---|
| 22 | 1381U, 1493U, 1613U, 1741U, 1879U, 2029U, 2179U, 2357U,
|
|---|
| 23 | 2549U, 2753U, 2971U, 3209U, 3469U, 3739U, 4027U, 4349U,
|
|---|
| 24 | 4703U, 5087U, 5503U, 5953U, 6427U, 6949U, 7517U, 8123U,
|
|---|
| 25 | 8783U, 9497U, 10273U, 11113U, 12011U, 12983U, 14033U, 15173U,
|
|---|
| 26 | 16411U, 17749U, 19183U, 20753U, 22447U, 24281U, 26267U, 28411U,
|
|---|
| 27 | 30727U, 33223U, 35933U, 38873U, 42043U, 45481U, 49201U, 53201U,
|
|---|
| 28 | 57557U, 62233U, 67307U, 72817U, 78779U, 85229U, 92203U, 99733U,
|
|---|
| 29 | 107897U, 116731U, 126271U, 136607U, 147793U, 159871U, 172933U, 187091U,
|
|---|
| 30 | 202409U, 218971U, 236897U, 256279U, 277261U, 299951U, 324503U, 351061U,
|
|---|
| 31 | 379787U, 410857U, 444487U, 480881U, 520241U, 562841U, 608903U, 658753U,
|
|---|
| 32 | 712697U, 771049U, 834181U, 902483U, 976369U, 1056323U, 1142821U, 1236397U,
|
|---|
| 33 | 1337629U, 1447153U, 1565659U, 1693859U, 1832561U, 1982627U, 2144977U, 2320627U,
|
|---|
| 34 | 2510653U, 2716249U, 2938679U, 3179303U, 3439651U, 3721303U, 4026031U, 4355707U,
|
|---|
| 35 | 4712381U, 5098259U, 5515729U, 5967347U, 6456007U, 6984629U, 7556579U, 8175383U,
|
|---|
| 36 | 8844859U, 9569143U, 10352717U, 11200489U, 12117689U, 13109983U, 14183539U, 15345007U,
|
|---|
| 37 | 16601593U, 17961079U, 19431899U, 21023161U, 22744717U, 24607243U, 26622317U, 28802401U,
|
|---|
| 38 | 31160981U, 33712729U, 36473443U, 39460231U, 42691603U, 46187573U, 49969847U, 54061849U,
|
|---|
| 39 | 58488943U, 63278561U, 68460391U, 74066549U, 80131819U, 86693767U, 93793069U, 101473717U,
|
|---|
| 40 | 109783337U, 118773397U, 128499677U, 139022417U, 150406843U, 162723577U, 176048909U, 190465427U,
|
|---|
| 41 | 206062531U, 222936881U, 241193053U, 260944219U, 282312799U, 305431229U, 330442829U, 357502601U,
|
|---|
| 42 | 386778277U, 418451333U, 452718089U, 489790921U, 529899637U, 573292817U, 620239453U, 671030513U,
|
|---|
| 43 | 725980837U, 785430967U, 849749479U, 919334987U, 994618837U, 1076067617U, 1164186217U, 1259520799U,
|
|---|
| 44 | 1362662261U, 1474249943U, 1594975441U, 1725587117U, 1866894511U, 2019773507U, 2185171673U, 2364114217U,
|
|---|
| 45 | 2557710269U, 2767159799U, 2993761039U, 3238918481U, 3504151727U, 3791104843U, 4101556399U, 4294967291U,
|
|---|
| 46 | 4294967291U // sentinel
|
|---|
| 47 | };
|
|---|
| 48 |
|
|---|
| 49 | static const nv::uint32 s_primes_size = ( sizeof( s_primes ) / sizeof( *s_primes ) );
|
|---|
| 50 |
|
|---|
| 51 | namespace nv
|
|---|
| 52 | {
|
|---|
| 53 | void* g_hash_table_empty[2] = { nullptr, (void*)uintptr_t( ~0 ) };
|
|---|
| 54 | }
|
|---|
| 55 |
|
|---|
| 56 | nv::uint32 nv::get_prime_larger_or_equal_to( nv::uint32 value )
|
|---|
| 57 | {
|
|---|
| 58 | NV_ASSERT( value < 4294967291, "value too large!" );
|
|---|
| 59 | if ( value < 3 ) return 2;
|
|---|
| 60 | uint32 i = 0;
|
|---|
| 61 | while ( s_primes[i] < value ) ++i;
|
|---|
| 62 | return s_primes[i];
|
|---|
| 63 | }
|
|---|
