--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dmd/StringTable.d	Sat Oct 24 08:42:06 2009 +0400
@@ -0,0 +1,108 @@
+module dmd.StringTable;
+
+import dmd.StringValue;
+import dmd.StringEntry;
+import dmd.Dchar;
+
+import core.stdc.stdlib;
+import core.stdc.string;
+
+class StringTable
+{
+    void** table;
+    uint count;
+    uint tabledim;
+
+    this(uint size = 37)
+	{
+		table = cast(void**)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;
+	}
+}
\ No newline at end of file