// Copyright (C) 2015 ChaosForge Ltd
// http://chaosforge.org/
//
// This file is part of Nova libraries. 
// For conditions of distribution and use, see copying.txt file in root folder.

#include "nv/stl/container/hash_table.hh"
#include "nv/stl/container/hash_table_policy.hh"

using namespace nv;

static const uint32 s_primes[] =
{
	         2U,          3U,          5U,          7U,         11U,         13U,         17U,         19U,
	        23U,         29U,         31U,         37U,         41U,         43U,         47U,         53U,
	        59U,         61U,         67U,         71U,         73U,         79U,         83U,         89U,
	        97U,        103U,        109U,        113U,        127U,        137U,        139U,        149U,
	       157U,        167U,        179U,        193U,        199U,        211U,        227U,        241U,
	       257U,        277U,        293U,        313U,        337U,        359U,        383U,        409U,
	       439U,        467U,        503U,        541U,        577U,        619U,        661U,        709U,
	       761U,        823U,        887U,        953U,       1031U,       1109U,       1193U,       1289U,
	      1381U,       1493U,       1613U,       1741U,       1879U,       2029U,       2179U,       2357U,
	      2549U,       2753U,       2971U,       3209U,       3469U,       3739U,       4027U,       4349U, 
	      4703U,       5087U,       5503U,       5953U,       6427U,       6949U,       7517U,       8123U,
	      8783U,       9497U,      10273U,      11113U,      12011U,      12983U,      14033U,      15173U,
	     16411U,      17749U,      19183U,      20753U,      22447U,      24281U,      26267U,      28411U,
	     30727U,      33223U,      35933U,      38873U,      42043U,      45481U,      49201U,      53201U,
	     57557U,      62233U,      67307U,      72817U,      78779U,      85229U,      92203U,      99733U,
	    107897U,     116731U,     126271U,     136607U,     147793U,     159871U,     172933U,     187091U,
	    202409U,     218971U,     236897U,     256279U,     277261U,     299951U,     324503U,     351061U,  
	    379787U,     410857U,     444487U,     480881U,     520241U,     562841U,     608903U,     658753U,
	    712697U,     771049U,     834181U,     902483U,     976369U,    1056323U,    1142821U,    1236397U,
	   1337629U,    1447153U,    1565659U,    1693859U,    1832561U,    1982627U,    2144977U,    2320627U,
	   2510653U,    2716249U,    2938679U,    3179303U,    3439651U,    3721303U,    4026031U,    4355707U,
	   4712381U,    5098259U,    5515729U,    5967347U,    6456007U,    6984629U,    7556579U,    8175383U,
	   8844859U,    9569143U,   10352717U,   11200489U,   12117689U,   13109983U,   14183539U,   15345007U,
	  16601593U,   17961079U,   19431899U,   21023161U,   22744717U,   24607243U,   26622317U,   28802401U,
	  31160981U,   33712729U,   36473443U,   39460231U,   42691603U,   46187573U,   49969847U,   54061849U,
	  58488943U,   63278561U,   68460391U,   74066549U,   80131819U,   86693767U,   93793069U,  101473717U,
	 109783337U,  118773397U,  128499677U,  139022417U,  150406843U,  162723577U,  176048909U,  190465427U,
	 206062531U,  222936881U,  241193053U,  260944219U,  282312799U,  305431229U,  330442829U,  357502601U,
	 386778277U,  418451333U,  452718089U,  489790921U,  529899637U,  573292817U,  620239453U,  671030513U,
	 725980837U,  785430967U,  849749479U,  919334987U,  994618837U, 1076067617U, 1164186217U, 1259520799U,
	1362662261U, 1474249943U, 1594975441U, 1725587117U, 1866894511U, 2019773507U, 2185171673U, 2364114217U,
	2557710269U, 2767159799U, 2993761039U, 3238918481U, 3504151727U, 3791104843U, 4101556399U, 4294967291U,
	4294967291U // sentinel
};

//static const nv::uint32 s_primes_size = ( sizeof( s_primes ) / sizeof( *s_primes ) );

namespace nv
{
	void* g_hash_table_empty[2] = { nullptr, reinterpret_cast<void*>( uintptr_t( ~0 ) ) };
}

nv::uint32 nv::get_prime_larger_or_equal_to( nv::uint32 value )
{
	NV_ASSERT( value < 4294967291, "value too large!" );
	if ( value < 3 ) return 2;
	uint32 i = 0;
	while ( s_primes[i] < value ) ++i;
	return s_primes[i];
}