module dmd.StringTable;

import dmd.common;
import dmd.StringValue;
import dmd.StringEntry;
import dmd.Dchar;

import core.stdc.stdlib;
import core.stdc.string;

import core.memory;

class StringTable
{
    void** table;
    uint count;
    uint tabledim;

    this(uint size = 37)
	{
		table = cast(void**)GC.calloc(size * (void*).sizeof);
		memset(table, 0, size * (void*).sizeof);
		tabledim = size;
		count = 0;
	}
	
    ~this()
	{
		/// TODO: is it *really* needed?
		// Zero out dangling pointers to help garbage collector.
		// Should zero out StringEntry's too.
		///for (uint i = 0; i < count; i++) {
		///	table[i] = null;
		///}

		///free(table);
		//table = null;
	}

    StringValue* lookup(immutable(dchar_t)[] s)
	{
		StringEntry* se = *cast(StringEntry**)search(s);
		if (se !is null)
			return &se.value;
		else
			return null;
	}
	
    StringValue* insert(immutable(dchar_t)[] s)
	{
		StringEntry** pse = cast(StringEntry**)search(s);
		StringEntry* se = *pse;
		if (se !is null)
			return null;		// error: already in table
		else
		{
			se = new StringEntry(s);
			*pse = se;
		}

		return &se.value;
	}
	
    StringValue* update(immutable(dchar_t)[] s)
	{
		StringEntry **pse;
		StringEntry *se;

		pse = cast(StringEntry**)search(s);
		se = *pse;
		if (se is null)			// not in table: so create new entry
		{
			se = new StringEntry(s);
			*pse = se;
		}
		return &se.value;
	}

private:
    void** search(immutable(dchar_t)[] s)
	{
		int cmp;

		//printf("StringTable::search(%p,%d)\n",s,len);
		hash_t hash = Dchar.calcHash(s.ptr, s.length);
		uint u = hash % tabledim;
		StringEntry** se = cast(StringEntry**)&table[u];
		//printf("\thash = %d, u = %d\n",hash,u);
		while (*se)
		{
			cmp = (*se).hash - hash;
			if (cmp == 0)
			{
				cmp = (*se).value.lstring.len() - s.length;
				if (cmp == 0)
				{
					cmp = Dchar.memcmp(s.ptr, (*se).value.lstring.toDchars().ptr, s.length);
					if (cmp == 0)
						break;
				}
			}
			if (cmp < 0)
				se = &(*se).left;
			else
				se = &(*se).right;
		}

		//printf("\treturn %p, %p\n",se, (*se));
		return cast(void**)se;
	}
}