|
0
|
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 } |
