|
0
|
1 module dmd.StringTable;
|
|
|
2
|
|
114
|
3 import dmd.common;
|
|
0
|
4 import dmd.StringValue;
|
|
|
5 import dmd.StringEntry;
|
|
|
6 import dmd.Dchar;
|
|
|
7
|
|
|
8 import core.stdc.stdlib;
|
|
|
9 import core.stdc.string;
|
|
|
10
|
|
4
|
11 import core.memory;
|
|
2
|
12
|
|
174
|
13 import std.stdio;
|
|
|
14
|
|
178
|
15 struct StringTable
|
|
0
|
16 {
|
|
178
|
17 Object[string] table;
|
|
180
|
18 /*
|
|
178
|
19 ~this()
|
|
|
20 {
|
|
|
21 foreach (k, v; table) {
|
|
|
22 delete v;
|
|
|
23 }
|
|
|
24 }
|
|
180
|
25 */
|
|
178
|
26 Object* lookup(string s)
|
|
|
27 {
|
|
|
28 return s in table;
|
|
|
29 }
|
|
|
30
|
|
|
31 Object* insert(string s)
|
|
|
32 {
|
|
|
33 auto value = s in table;
|
|
|
34 if (value !is null) {
|
|
|
35 return null;
|
|
|
36 }
|
|
|
37
|
|
|
38 table[s] = null;
|
|
|
39
|
|
|
40 return s in table;
|
|
|
41 }
|
|
|
42
|
|
|
43 Object* update(string s)
|
|
|
44 {
|
|
|
45 auto value = s in table;
|
|
|
46 if (value !is null) {
|
|
|
47 return value;
|
|
|
48 }
|
|
|
49
|
|
|
50 table[s] = null;
|
|
|
51
|
|
|
52 return s in table;
|
|
|
53 }
|
|
|
54
|
|
|
55 /*
|
|
|
56 StringValue* lookup(string s)
|
|
|
57 {
|
|
|
58 if (auto p = s in table) {
|
|
|
59 return *p;
|
|
|
60 }
|
|
|
61
|
|
|
62 return null;
|
|
|
63 }
|
|
|
64
|
|
|
65 StringValue* insert(string s)
|
|
|
66 {
|
|
|
67 if (auto p = s in table) {
|
|
|
68 return null;
|
|
|
69 }
|
|
|
70
|
|
|
71 auto value = new StringValue();
|
|
|
72 value.lstring.string_ = s;
|
|
|
73 table[s] = value;
|
|
|
74
|
|
|
75 return value;
|
|
|
76 }
|
|
|
77
|
|
|
78 StringValue* update(string s)
|
|
|
79 {
|
|
|
80 if (auto p = s in table) {
|
|
|
81 return *p;
|
|
|
82 }
|
|
|
83
|
|
|
84 auto value = new StringValue();
|
|
|
85 value.lstring.string_ = s;
|
|
|
86 table[s] = value;
|
|
|
87
|
|
|
88 return value;
|
|
|
89 }
|
|
|
90 */
|
|
|
91
|
|
|
92 /*
|
|
0
|
93 void** table;
|
|
|
94 uint count;
|
|
|
95 uint tabledim;
|
|
|
96
|
|
|
97 this(uint size = 37)
|
|
|
98 {
|
|
178
|
99 register();
|
|
4
|
100 table = cast(void**)GC.calloc(size * (void*).sizeof);
|
|
0
|
101 memset(table, 0, size * (void*).sizeof);
|
|
|
102 tabledim = size;
|
|
|
103 count = 0;
|
|
|
104 }
|
|
174
|
105
|
|
0
|
106 ~this()
|
|
|
107 {
|
|
|
108 /// TODO: is it *really* needed?
|
|
|
109 // Zero out dangling pointers to help garbage collector.
|
|
|
110 // Should zero out StringEntry's too.
|
|
|
111 ///for (uint i = 0; i < count; i++) {
|
|
|
112 /// table[i] = null;
|
|
|
113 ///}
|
|
|
114
|
|
2
|
115 ///free(table);
|
|
0
|
116 //table = null;
|
|
|
117 }
|
|
|
118
|
|
|
119 StringValue* lookup(immutable(dchar_t)[] s)
|
|
|
120 {
|
|
174
|
121 StringEntry* se = *search(s);
|
|
0
|
122 if (se !is null)
|
|
|
123 return &se.value;
|
|
|
124 else
|
|
|
125 return null;
|
|
|
126 }
|
|
174
|
127
|
|
0
|
128 StringValue* insert(immutable(dchar_t)[] s)
|
|
|
129 {
|
|
174
|
130 StringEntry** pse = search(s);
|
|
0
|
131 StringEntry* se = *pse;
|
|
|
132 if (se !is null)
|
|
|
133 return null; // error: already in table
|
|
|
134 else
|
|
|
135 {
|
|
|
136 se = new StringEntry(s);
|
|
|
137 *pse = se;
|
|
174
|
138 ++count;
|
|
0
|
139 }
|
|
|
140
|
|
|
141 return &se.value;
|
|
|
142 }
|
|
178
|
143
|
|
174
|
144 void insertCopy(StringEntry* proto)
|
|
|
145 {
|
|
|
146 StringEntry** pse = search(proto.value.lstring.string_);
|
|
|
147 StringEntry* se = *pse;
|
|
|
148 if (se is null)
|
|
|
149 {
|
|
|
150 se = new StringEntry(proto);
|
|
|
151 *pse = se;
|
|
|
152 ++count;
|
|
|
153 }
|
|
|
154 }
|
|
|
155
|
|
0
|
156 StringValue* update(immutable(dchar_t)[] s)
|
|
|
157 {
|
|
174
|
158 StringEntry** pse = search(s);
|
|
|
159 StringEntry* se = *pse;
|
|
0
|
160 if (se is null) // not in table: so create new entry
|
|
|
161 {
|
|
|
162 se = new StringEntry(s);
|
|
|
163 *pse = se;
|
|
174
|
164 ++count;
|
|
0
|
165 }
|
|
|
166 return &se.value;
|
|
|
167 }
|
|
|
168
|
|
174
|
169 void copyTo(StringTable stringTable)
|
|
|
170 {
|
|
|
171 for (int u = 0; u < tabledim; ++u) {
|
|
|
172 StringEntry** se = cast(StringEntry**)&table[u];
|
|
|
173 copyNode(*se, stringTable);
|
|
|
174 }
|
|
|
175 }
|
|
|
176
|
|
0
|
177 private:
|
|
174
|
178 void copyNode(StringEntry* node, StringTable stringTable)
|
|
|
179 {
|
|
|
180 if (node is null) {
|
|
|
181 return;
|
|
|
182 }
|
|
|
183
|
|
|
184 copyNode(node.left, stringTable);
|
|
|
185 stringTable.insertCopy(node);
|
|
|
186 copyNode(node.right, stringTable);
|
|
|
187 }
|
|
|
188
|
|
|
189 StringEntry** search(immutable(dchar_t)[] s)
|
|
0
|
190 {
|
|
|
191 int cmp;
|
|
|
192
|
|
|
193 //printf("StringTable::search(%p,%d)\n",s,len);
|
|
|
194 hash_t hash = Dchar.calcHash(s.ptr, s.length);
|
|
|
195 uint u = hash % tabledim;
|
|
|
196 StringEntry** se = cast(StringEntry**)&table[u];
|
|
|
197 //printf("\thash = %d, u = %d\n",hash,u);
|
|
|
198 while (*se)
|
|
|
199 {
|
|
|
200 cmp = (*se).hash - hash;
|
|
|
201 if (cmp == 0)
|
|
|
202 {
|
|
|
203 cmp = (*se).value.lstring.len() - s.length;
|
|
|
204 if (cmp == 0)
|
|
|
205 {
|
|
|
206 cmp = Dchar.memcmp(s.ptr, (*se).value.lstring.toDchars().ptr, s.length);
|
|
|
207 if (cmp == 0)
|
|
|
208 break;
|
|
|
209 }
|
|
|
210 }
|
|
|
211 if (cmp < 0)
|
|
|
212 se = &(*se).left;
|
|
|
213 else
|
|
|
214 se = &(*se).right;
|
|
|
215 }
|
|
|
216
|
|
|
217 //printf("\treturn %p, %p\n",se, (*se));
|
|
174
|
218 return se;
|
|
0
|
219 }
|
|
178
|
220 */
|
|
174
|
221 }
|
