|
1
|
1
|
|
336
|
2 // Copyright (c) 1999-2008 by Digital Mars
|
|
1
|
3 // All Rights Reserved
|
|
|
4 // written by Walter Bright
|
|
336
|
5 // http://www.digitalmars.com
|
|
1
|
6 // License for redistribution is by either the Artistic License
|
|
|
7 // in artistic.txt, or the GNU General Public License in gnu.txt.
|
|
|
8 // See the included readme.txt for details.
|
|
|
9
|
|
|
10
|
|
|
11 #include <stdio.h>
|
|
|
12 #include <string.h>
|
|
|
13 #include <stdlib.h>
|
|
|
14
|
|
|
15 #include "root.h"
|
|
|
16 #include "mem.h"
|
|
|
17 #include "dchar.h"
|
|
|
18 #include "lstring.h"
|
|
|
19 #include "stringtable.h"
|
|
|
20
|
|
|
21 StringTable::StringTable(unsigned size)
|
|
|
22 {
|
|
|
23 table = (void **)mem.calloc(size, sizeof(void *));
|
|
|
24 tabledim = size;
|
|
|
25 count = 0;
|
|
|
26 }
|
|
|
27
|
|
|
28 StringTable::~StringTable()
|
|
|
29 {
|
|
|
30 unsigned i;
|
|
|
31
|
|
|
32 // Zero out dangling pointers to help garbage collector.
|
|
|
33 // Should zero out StringEntry's too.
|
|
|
34 for (i = 0; i < count; i++)
|
|
|
35 table[i] = NULL;
|
|
|
36
|
|
|
37 mem.free(table);
|
|
|
38 table = NULL;
|
|
|
39 }
|
|
|
40
|
|
|
41 struct StringEntry
|
|
|
42 {
|
|
|
43 StringEntry *left;
|
|
|
44 StringEntry *right;
|
|
|
45 hash_t hash;
|
|
|
46
|
|
|
47 StringValue value;
|
|
|
48
|
|
|
49 static StringEntry *alloc(const dchar *s, unsigned len);
|
|
|
50 };
|
|
|
51
|
|
|
52 StringEntry *StringEntry::alloc(const dchar *s, unsigned len)
|
|
|
53 {
|
|
|
54 StringEntry *se;
|
|
|
55
|
|
|
56 se = (StringEntry *) mem.calloc(1,sizeof(StringEntry) - sizeof(Lstring) + Lstring::size(len));
|
|
|
57 se->value.lstring.length = len;
|
|
|
58 se->hash = Dchar::calcHash(s,len);
|
|
|
59 memcpy(se->value.lstring.string, s, len * sizeof(dchar));
|
|
|
60 return se;
|
|
|
61 }
|
|
|
62
|
|
|
63 void **StringTable::search(const dchar *s, unsigned len)
|
|
|
64 {
|
|
|
65 hash_t hash;
|
|
|
66 unsigned u;
|
|
|
67 int cmp;
|
|
|
68 StringEntry **se;
|
|
|
69
|
|
|
70 //printf("StringTable::search(%p,%d)\n",s,len);
|
|
|
71 hash = Dchar::calcHash(s,len);
|
|
|
72 u = hash % tabledim;
|
|
|
73 se = (StringEntry **)&table[u];
|
|
|
74 //printf("\thash = %d, u = %d\n",hash,u);
|
|
|
75 while (*se)
|
|
|
76 {
|
|
|
77 cmp = (*se)->hash - hash;
|
|
|
78 if (cmp == 0)
|
|
|
79 {
|
|
|
80 cmp = (*se)->value.lstring.len() - len;
|
|
|
81 if (cmp == 0)
|
|
|
82 {
|
|
|
83 cmp = Dchar::memcmp(s,(*se)->value.lstring.toDchars(),len);
|
|
|
84 if (cmp == 0)
|
|
|
85 break;
|
|
|
86 }
|
|
|
87 }
|
|
|
88 if (cmp < 0)
|
|
|
89 se = &(*se)->left;
|
|
|
90 else
|
|
|
91 se = &(*se)->right;
|
|
|
92 }
|
|
|
93 //printf("\treturn %p, %p\n",se, (*se));
|
|
|
94 return (void **)se;
|
|
|
95 }
|
|
|
96
|
|
|
97 StringValue *StringTable::lookup(const dchar *s, unsigned len)
|
|
|
98 { StringEntry *se;
|
|
|
99
|
|
|
100 se = *(StringEntry **)search(s,len);
|
|
|
101 if (se)
|
|
|
102 return &se->value;
|
|
|
103 else
|
|
|
104 return NULL;
|
|
|
105 }
|
|
|
106
|
|
|
107 StringValue *StringTable::update(const dchar *s, unsigned len)
|
|
|
108 { StringEntry **pse;
|
|
|
109 StringEntry *se;
|
|
|
110
|
|
|
111 pse = (StringEntry **)search(s,len);
|
|
|
112 se = *pse;
|
|
|
113 if (!se) // not in table: so create new entry
|
|
|
114 {
|
|
|
115 se = StringEntry::alloc(s, len);
|
|
|
116 *pse = se;
|
|
|
117 }
|
|
|
118 return &se->value;
|
|
|
119 }
|
|
|
120
|
|
|
121 StringValue *StringTable::insert(const dchar *s, unsigned len)
|
|
|
122 { StringEntry **pse;
|
|
|
123 StringEntry *se;
|
|
|
124
|
|
|
125 pse = (StringEntry **)search(s,len);
|
|
|
126 se = *pse;
|
|
|
127 if (se)
|
|
|
128 return NULL; // error: already in table
|
|
|
129 else
|
|
|
130 {
|
|
|
131 se = StringEntry::alloc(s, len);
|
|
|
132 *pse = se;
|
|
|
133 }
|
|
|
134 return &se->value;
|
|
|
135 }
|
|
|
136
|
|
|
137
|
|
|
138
|
|
|
139
|
