|
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
|
|
0
|
13 class StringTable
|
|
|
14 {
|
|
|
15 void** table;
|
|
|
16 uint count;
|
|
|
17 uint tabledim;
|
|
|
18
|
|
|
19 this(uint size = 37)
|
|
|
20 {
|
|
4
|
21 table = cast(void**)GC.calloc(size * (void*).sizeof);
|
|
0
|
22 memset(table, 0, size * (void*).sizeof);
|
|
|
23 tabledim = size;
|
|
|
24 count = 0;
|
|
|
25 }
|
|
|
26
|
|
|
27 ~this()
|
|
|
28 {
|
|
|
29 /// TODO: is it *really* needed?
|
|
|
30 // Zero out dangling pointers to help garbage collector.
|
|
|
31 // Should zero out StringEntry's too.
|
|
|
32 ///for (uint i = 0; i < count; i++) {
|
|
|
33 /// table[i] = null;
|
|
|
34 ///}
|
|
|
35
|
|
2
|
36 ///free(table);
|
|
0
|
37 //table = null;
|
|
|
38 }
|
|
|
39
|
|
|
40 StringValue* lookup(immutable(dchar_t)[] s)
|
|
|
41 {
|
|
|
42 StringEntry* se = *cast(StringEntry**)search(s);
|
|
|
43 if (se !is null)
|
|
|
44 return &se.value;
|
|
|
45 else
|
|
|
46 return null;
|
|
|
47 }
|
|
|
48
|
|
|
49 StringValue* insert(immutable(dchar_t)[] s)
|
|
|
50 {
|
|
|
51 StringEntry** pse = cast(StringEntry**)search(s);
|
|
|
52 StringEntry* se = *pse;
|
|
|
53 if (se !is null)
|
|
|
54 return null; // error: already in table
|
|
|
55 else
|
|
|
56 {
|
|
|
57 se = new StringEntry(s);
|
|
|
58 *pse = se;
|
|
|
59 }
|
|
|
60
|
|
|
61 return &se.value;
|
|
|
62 }
|
|
|
63
|
|
|
64 StringValue* update(immutable(dchar_t)[] s)
|
|
|
65 {
|
|
|
66 StringEntry **pse;
|
|
|
67 StringEntry *se;
|
|
|
68
|
|
|
69 pse = cast(StringEntry**)search(s);
|
|
|
70 se = *pse;
|
|
|
71 if (se is null) // not in table: so create new entry
|
|
|
72 {
|
|
|
73 se = new StringEntry(s);
|
|
|
74 *pse = se;
|
|
|
75 }
|
|
|
76 return &se.value;
|
|
|
77 }
|
|
|
78
|
|
|
79 private:
|
|
|
80 void** search(immutable(dchar_t)[] s)
|
|
|
81 {
|
|
|
82 int cmp;
|
|
|
83
|
|
|
84 //printf("StringTable::search(%p,%d)\n",s,len);
|
|
|
85 hash_t hash = Dchar.calcHash(s.ptr, s.length);
|
|
|
86 uint u = hash % tabledim;
|
|
|
87 StringEntry** se = cast(StringEntry**)&table[u];
|
|
|
88 //printf("\thash = %d, u = %d\n",hash,u);
|
|
|
89 while (*se)
|
|
|
90 {
|
|
|
91 cmp = (*se).hash - hash;
|
|
|
92 if (cmp == 0)
|
|
|
93 {
|
|
|
94 cmp = (*se).value.lstring.len() - s.length;
|
|
|
95 if (cmp == 0)
|
|
|
96 {
|
|
|
97 cmp = Dchar.memcmp(s.ptr, (*se).value.lstring.toDchars().ptr, s.length);
|
|
|
98 if (cmp == 0)
|
|
|
99 break;
|
|
|
100 }
|
|
|
101 }
|
|
|
102 if (cmp < 0)
|
|
|
103 se = &(*se).left;
|
|
|
104 else
|
|
|
105 se = &(*se).right;
|
|
|
106 }
|
|
|
107
|
|
|
108 //printf("\treturn %p, %p\n",se, (*se));
|
|
|
109 return cast(void**)se;
|
|
|
110 }
|
|
|
111 } |
