//#define USE_CHAR_TO_ARRAY_INDEX_LUT

#ifdef USE_CHAR_TO_ARRAY_INDEX_LUT
static hh_u8 _CharToIndexArrayRemapper6[256];

#define CHAR_TO_ARRAY_INDEX(__c) _CharToIndexArrayRemapper6[__c]
#else
#define CHAR_TO_ARRAY_INDEX(__c) ((__c) - SNode::FirstValidChar)
#endif

class CStringDictionnary6
{
public:
struct SNode
{
enum
{
// valid chars : '0'-'9','A'-'Z','_','a'-'z'
#ifdef USE_CHAR_TO_ARRAY_INDEX_LUT
CharCount = ('9' - '0' + 1) + 1 /* '_' */ + 2 * ('Z' - 'A' + 1)
#else
FirstValidChar = '0',
LastValidChar = 'z',
CharCount = LastValidChar - FirstValidChar + 1
#endif
};
SScopeLocalEntry m_Data;
hh_u32 m_Count;
hh_u16 m_Childs[CharCount];

SNode()
: m_Data(null),
m_Count(0)
{
memset(m_Childs, 0, sizeof(m_Childs));
}
~SNode()
{
}

bool EligibleForEarlyBranchTermination() const
{
return m_Count == 0 && m_Data.Valid();
}
};

//#define USE_NODE_CACHE

#ifdef USE_NODE_CACHE
TArray<hh_u16> m_NodeCache;
#endif
TArray<SNode> m_NodeList;

hh_u32 _AllocNode()
{
#ifdef USE_NODE_CACHE
if (!m_NodeCache.Empty())
{
hh_u32 id = m_NodeCache.PopBack();
HH_ASSERT(id != 0);
return id;
}
#endif
CGuid id = m_NodeList.PushBack(); // FIXME: handle failure gracefully
if (!id.Valid())
id = 0;
return id;
}

CStringDictionnary6()
{
#ifdef USE_NODE_CACHE
m_NodeCache.Reserve(4);
#endif
m_NodeList.Reserve(4 + 1);
m_NodeList.PushBack();

//printf("NEW STRING DICTIONNARY ! sn = %d, se = %d, cc = %d\n", sizeof(SNode), sizeof(SScopeLocalEntry), SNode::CharCount);

#ifdef USE_CHAR_TO_ARRAY_INDEX_LUT
static bool _LutInitialized = false;
if (!_LutInitialized)
{
memset(_CharToIndexArrayRemapper6, 0, sizeof(_CharToIndexArrayRemapper6));

hh_u8 curId = 0;
for (hh_u32 i = '0'; i <= '9'; i++)
_CharToIndexArrayRemapper6[i] = curId++;
for (hh_u32 i = 'A'; i <= 'Z'; i++)
_CharToIndexArrayRemapper6[i] = curId++;
_CharToIndexArrayRemapper6['_'] = curId++;
for (hh_u32 i = 'a'; i <= 'z'; i++)
_CharToIndexArrayRemapper6[i] = curId++;
}
#endif
}
~CStringDictionnary6()
{
}

bool Empty() const { return m_NodeList.First().m_Count == 0; }

HH_NOINLINE void Clear()
{
#ifdef USE_NODE_CACHE
HH_ASSERT(!m_NodeList.Empty());
if (m_NodeCache.Count() != m_NodeList.Count() - 1)
{
for (hh_u32 i = 0; i < m_NodeList.Count(); i++)
{
if (m_NodeList[i].m_Count != 0)
{
memset(&m_NodeList[i], 0, sizeof(m_NodeList[i]));
}
else
m_NodeList[i].m_Data = null;
}

m_NodeCache.Resize(m_NodeList.Count() - 1);
for (hh_u16 i = 0; i < m_NodeCache.Count(); i++)
{
m_NodeCache[i] = i + 1;
}
}

#else
m_NodeList.Resize(1);
m_NodeList[0].m_Data = null;
if (m_NodeList[0].m_Count != 0)
{
memset(&m_NodeList[0], 0, sizeof(m_NodeList[0]));
}
#endif
}

HH_NOINLINE bool Insert(CCompilerASTNodeDataViewLocal *data)
{
const CSimpleSemiDynamicString &iKey = data->Name();
const char *key = iKey.Data();
const char *keyStop = key + iKey.Length();
if (key != keyStop)
{
hh_u32 next = 0;
hh_u32 n = 0;
hh_u32 index = 0;
do
{
n = next;
index = CHAR_TO_ARRAY_INDEX(*key++);
next = m_NodeList[n].m_Childs[index];
} while (next != 0 && key < keyStop);

if (next == 0)
{
// right, here, we have to add a new node. as this is a new entry,
// we're not going to generate one sub-level for each character left.
// so we might have 5 more characters, but we want to keep it that way.

hh_u32 currentLevel = key - iKey.Data();

while (1)
{
SScopeLocalEntry entry = m_NodeList[n].m_Data;
if (!entry.Valid())
{
if (next == 0)
{
next = _AllocNode();
if (next == 0)
return false;
}
break;
}

hh_u32 targetLevel = entry.m_DataView->Name().Length();

if (currentLevel <= targetLevel)
{
// this node is an early-terminated leaf. split it
HH_ASSERT(m_NodeList[n].m_Count == 0);
// riight. we have to grab this one and re-insert it into its own child:

next = _AllocNode();
if (next == 0)
return false;

hh_u32 index2 = CHAR_TO_ARRAY_INDEX(entry.m_DataView->Name().Data()[currentLevel - 1]);

m_NodeList[next].m_Data = m_NodeList[n].m_Data;
m_NodeList[n].m_Data = null;
m_NodeList[n].m_Childs[index2] = next;
m_NodeList[n].m_Count++;

}

if (currentLevel > iKey.Length())
{
next = 0;
break;
}

index = CHAR_TO_ARRAY_INDEX(iKey.Data()[currentLevel - 1]);
next = m_NodeList[n].m_Childs[index];
if (next == 0)
{
next = _AllocNode();
if (next == 0)
return false;
break;
}
n = next;
++currentLevel;
}

SNode &rn = m_NodeList[n];
if (next != 0)
{
rn.m_Childs[index] = next;
rn.m_Count++;
m_NodeList[next].m_Data = data;
}
else
rn.m_Data = data;
}
else
{
//HH_RELEASE_ASSERT(m_NodeList[n].m_Count != 0);
SScopeLocalEntry entry = m_NodeList[next].m_Data;
hh_u32 currentLevel = key - iKey.Data();
if (entry.Valid())
{
hh_u32 targetLevel = entry.m_DataView->Name().Length();

if (currentLevel < targetLevel)
{
HH_ASSERT(m_NodeList[next].m_Count == 0);
// riight. we have to grab this one and re-insert it into its own child:

hh_u32 n = _AllocNode();
if (next == 0)
return false;
index = CHAR_TO_ARRAY_INDEX(entry.m_DataView->Name().Data()[currentLevel - 1]);

m_NodeList[n].m_Data = m_NodeList[next].m_Data;
m_NodeList[next].m_Data = null;
m_NodeList[next].m_Childs[index] = n;
m_NodeList[next].m_Count++;
}
}

// we're at the right level, and don't have to do anything special.
HH_ASSERT(!m_NodeList[next].m_Data.Valid());
m_NodeList[next].m_Data = data;
}

return true;
}
return false;
}

HH_NOINLINE const SScopeLocalEntry &Find(const CStringView &iKey)
{
/*const hh_u8 *pCache = (const hh_u8*)&m_NodeList[m_NodeList[0].m_Childs[CHAR_TO_ARRAY_INDEX(*iKey.Data())]];
SIMD::PrefetchCacheLine(pCache + 0);
SIMD::PrefetchCacheLine(pCache + 64);*/

hh_u32 next = 0;
hh_u32 n = 0;
hh_i32 i = -hh_i32(iKey.Length());
const char *key = iKey.Data() - i;

do
{
hh_u32 index = CHAR_TO_ARRAY_INDEX(key[i]);
next = m_NodeList[n].m_Childs[index];
if (next == 0)
break;
n = next;
} while (++i != 0);

// see if this is an eligible leaf for early branch termination:
if (m_NodeList[n].m_Data.Valid())
{
if (m_NodeList[n].m_Count == 0)
{
if (m_NodeList[n].m_Data == iKey)
{
return m_NodeList[n].m_Data;
}
}
else if (i == 0)
{
return m_NodeList[n].m_Data;
}
}

return SScopeLocalEntry::Invalid;
}
};