Mercurial > projects > ddmd
view dmd/StringTable.d @ 0:10317f0c89a5
Initial commit
author | korDen |
---|---|
date | Sat, 24 Oct 2009 08:42:06 +0400 |
parents | |
children | 7427ded8caf7 |
line wrap: on
line source
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; } }