Mercurial > projects > ddmd

comparison dmd/StringTable.d @ 0:10317f0c89a5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial commit
author korDen
date Sat, 24 Oct 2009 08:42:06 +0400
parents
children 7427ded8caf7
comparison
equal deleted inserted replaced
-1:000000000000 0:10317f0c89a5
1 module dmd.StringTable;
2
3 import dmd.StringValue;
4 import dmd.StringEntry;
5 import dmd.Dchar;
6
7 import core.stdc.stdlib;
8 import core.stdc.string;
9
10 class StringTable
11 {
12 void** table;
13 uint count;
14 uint tabledim;
15
16 this(uint size = 37)
17 {
18 table = cast(void**)calloc(size, (void*).sizeof);
19 memset(table, 0, size * (void*).sizeof);
20 tabledim = size;
21 count = 0;
22 }
23
24 ~this()
25 {
26 /// TODO: is it *really* needed?
27 // Zero out dangling pointers to help garbage collector.
28 // Should zero out StringEntry's too.
29 ///for (uint i = 0; i < count; i++) {
30 /// table[i] = null;
31 ///}
32
33 free(table);
34 //table = null;
35 }
36
37 StringValue* lookup(immutable(dchar_t)[] s)
38 {
39 StringEntry* se = *cast(StringEntry**)search(s);
40 if (se !is null)
41 return &se.value;
42 else
43 return null;
44 }
45
46 StringValue* insert(immutable(dchar_t)[] s)
47 {
48 StringEntry** pse = cast(StringEntry**)search(s);
49 StringEntry* se = *pse;
50 if (se !is null)
51 return null; // error: already in table
52 else
53 {
54 se = new StringEntry(s);
55 *pse = se;
56 }
57
58 return &se.value;
59 }
60
61 StringValue* update(immutable(dchar_t)[] s)
62 {
63 StringEntry **pse;
64 StringEntry *se;
65
66 pse = cast(StringEntry**)search(s);
67 se = *pse;
68 if (se is null) // not in table: so create new entry
69 {
70 se = new StringEntry(s);
71 *pse = se;
72 }
73 return &se.value;
74 }
75
76 private:
77 void** search(immutable(dchar_t)[] s)
78 {
79 int cmp;
80
81 //printf("StringTable::search(%p,%d)\n",s,len);
82 hash_t hash = Dchar.calcHash(s.ptr, s.length);
83 uint u = hash % tabledim;
84 StringEntry** se = cast(StringEntry**)&table[u];
85 //printf("\thash = %d, u = %d\n",hash,u);
86 while (*se)
87 {
88 cmp = (*se).hash - hash;
89 if (cmp == 0)
90 {
91 cmp = (*se).value.lstring.len() - s.length;
92 if (cmp == 0)
93 {
94 cmp = Dchar.memcmp(s.ptr, (*se).value.lstring.toDchars().ptr, s.length);
95 if (cmp == 0)
96 break;
97 }
98 }
99 if (cmp < 0)
100 se = &(*se).left;
101 else
102 se = &(*se).right;
103 }
104
105 //printf("\treturn %p, %p\n",se, (*se));
106 return cast(void**)se;
107 }
108 }