]>
Commit | Line | Data |
---|---|---|
ef416fc2 | 1 | //======================================================================== |
2 | // | |
3 | // GHash.cc | |
4 | // | |
5 | // Copyright 2001-2003 Glyph & Cog, LLC | |
6 | // | |
7 | //======================================================================== | |
8 | ||
9 | #include <config.h> | |
10 | ||
11 | #ifdef USE_GCC_PRAGMAS | |
12 | #pragma implementation | |
13 | #endif | |
14 | ||
15 | #include "gmem.h" | |
16 | #include "GString.h" | |
17 | #include "GHash.h" | |
18 | ||
19 | //------------------------------------------------------------------------ | |
20 | ||
21 | struct GHashBucket { | |
22 | GString *key; | |
23 | union { | |
24 | void *p; | |
25 | int i; | |
26 | } val; | |
27 | GHashBucket *next; | |
28 | }; | |
29 | ||
30 | struct GHashIter { | |
31 | int h; | |
32 | GHashBucket *p; | |
33 | }; | |
34 | ||
35 | //------------------------------------------------------------------------ | |
36 | ||
37 | GHash::GHash(GBool deleteKeysA) { | |
38 | int h; | |
39 | ||
40 | deleteKeys = deleteKeysA; | |
41 | size = 7; | |
42 | tab = (GHashBucket **)gmallocn(size, sizeof(GHashBucket *)); | |
43 | for (h = 0; h < size; ++h) { | |
44 | tab[h] = NULL; | |
45 | } | |
46 | len = 0; | |
47 | } | |
48 | ||
49 | GHash::~GHash() { | |
50 | GHashBucket *p; | |
51 | int h; | |
52 | ||
53 | for (h = 0; h < size; ++h) { | |
54 | while (tab[h]) { | |
55 | p = tab[h]; | |
56 | tab[h] = p->next; | |
57 | if (deleteKeys) { | |
58 | delete p->key; | |
59 | } | |
60 | delete p; | |
61 | } | |
62 | } | |
63 | gfree(tab); | |
64 | } | |
65 | ||
66 | void GHash::add(GString *key, void *val) { | |
67 | GHashBucket *p; | |
68 | int h; | |
69 | ||
70 | // expand the table if necessary | |
71 | if (len >= size) { | |
72 | expand(); | |
73 | } | |
74 | ||
75 | // add the new symbol | |
76 | p = new GHashBucket; | |
77 | p->key = key; | |
78 | p->val.p = val; | |
79 | h = hash(key); | |
80 | p->next = tab[h]; | |
81 | tab[h] = p; | |
82 | ++len; | |
83 | } | |
84 | ||
85 | void GHash::add(GString *key, int val) { | |
86 | GHashBucket *p; | |
87 | int h; | |
88 | ||
89 | // expand the table if necessary | |
90 | if (len >= size) { | |
91 | expand(); | |
92 | } | |
93 | ||
94 | // add the new symbol | |
95 | p = new GHashBucket; | |
96 | p->key = key; | |
97 | p->val.i = val; | |
98 | h = hash(key); | |
99 | p->next = tab[h]; | |
100 | tab[h] = p; | |
101 | ++len; | |
102 | } | |
103 | ||
104 | void GHash::replace(GString *key, void *val) { | |
105 | GHashBucket *p; | |
106 | int h; | |
107 | ||
108 | if ((p = find(key, &h))) { | |
109 | p->val.p = val; | |
110 | delete key; | |
111 | } else { | |
112 | add(key, val); | |
113 | } | |
114 | } | |
115 | ||
116 | void GHash::replace(GString *key, int val) { | |
117 | GHashBucket *p; | |
118 | int h; | |
119 | ||
120 | if ((p = find(key, &h))) { | |
121 | p->val.i = val; | |
122 | delete key; | |
123 | } else { | |
124 | add(key, val); | |
125 | } | |
126 | } | |
127 | ||
128 | void *GHash::lookup(GString *key) { | |
129 | GHashBucket *p; | |
130 | int h; | |
131 | ||
132 | if (!(p = find(key, &h))) { | |
133 | return NULL; | |
134 | } | |
135 | return p->val.p; | |
136 | } | |
137 | ||
138 | int GHash::lookupInt(GString *key) { | |
139 | GHashBucket *p; | |
140 | int h; | |
141 | ||
142 | if (!(p = find(key, &h))) { | |
143 | return 0; | |
144 | } | |
145 | return p->val.i; | |
146 | } | |
147 | ||
148 | void *GHash::lookup(char *key) { | |
149 | GHashBucket *p; | |
150 | int h; | |
151 | ||
152 | if (!(p = find(key, &h))) { | |
153 | return NULL; | |
154 | } | |
155 | return p->val.p; | |
156 | } | |
157 | ||
158 | int GHash::lookupInt(char *key) { | |
159 | GHashBucket *p; | |
160 | int h; | |
161 | ||
162 | if (!(p = find(key, &h))) { | |
163 | return 0; | |
164 | } | |
165 | return p->val.i; | |
166 | } | |
167 | ||
168 | void *GHash::remove(GString *key) { | |
169 | GHashBucket *p; | |
170 | GHashBucket **q; | |
171 | void *val; | |
172 | int h; | |
173 | ||
174 | if (!(p = find(key, &h))) { | |
175 | return NULL; | |
176 | } | |
177 | q = &tab[h]; | |
178 | while (*q != p) { | |
179 | q = &((*q)->next); | |
180 | } | |
181 | *q = p->next; | |
182 | if (deleteKeys) { | |
183 | delete p->key; | |
184 | } | |
185 | val = p->val.p; | |
186 | delete p; | |
187 | --len; | |
188 | return val; | |
189 | } | |
190 | ||
191 | int GHash::removeInt(GString *key) { | |
192 | GHashBucket *p; | |
193 | GHashBucket **q; | |
194 | int val; | |
195 | int h; | |
196 | ||
197 | if (!(p = find(key, &h))) { | |
198 | return 0; | |
199 | } | |
200 | q = &tab[h]; | |
201 | while (*q != p) { | |
202 | q = &((*q)->next); | |
203 | } | |
204 | *q = p->next; | |
205 | if (deleteKeys) { | |
206 | delete p->key; | |
207 | } | |
208 | val = p->val.i; | |
209 | delete p; | |
210 | --len; | |
211 | return val; | |
212 | } | |
213 | ||
214 | void *GHash::remove(char *key) { | |
215 | GHashBucket *p; | |
216 | GHashBucket **q; | |
217 | void *val; | |
218 | int h; | |
219 | ||
220 | if (!(p = find(key, &h))) { | |
221 | return NULL; | |
222 | } | |
223 | q = &tab[h]; | |
224 | while (*q != p) { | |
225 | q = &((*q)->next); | |
226 | } | |
227 | *q = p->next; | |
228 | if (deleteKeys) { | |
229 | delete p->key; | |
230 | } | |
231 | val = p->val.p; | |
232 | delete p; | |
233 | --len; | |
234 | return val; | |
235 | } | |
236 | ||
237 | int GHash::removeInt(char *key) { | |
238 | GHashBucket *p; | |
239 | GHashBucket **q; | |
240 | int val; | |
241 | int h; | |
242 | ||
243 | if (!(p = find(key, &h))) { | |
244 | return 0; | |
245 | } | |
246 | q = &tab[h]; | |
247 | while (*q != p) { | |
248 | q = &((*q)->next); | |
249 | } | |
250 | *q = p->next; | |
251 | if (deleteKeys) { | |
252 | delete p->key; | |
253 | } | |
254 | val = p->val.i; | |
255 | delete p; | |
256 | --len; | |
257 | return val; | |
258 | } | |
259 | ||
260 | void GHash::startIter(GHashIter **iter) { | |
261 | *iter = new GHashIter; | |
262 | (*iter)->h = -1; | |
263 | (*iter)->p = NULL; | |
264 | } | |
265 | ||
266 | GBool GHash::getNext(GHashIter **iter, GString **key, void **val) { | |
267 | if (!*iter) { | |
268 | return gFalse; | |
269 | } | |
270 | if ((*iter)->p) { | |
271 | (*iter)->p = (*iter)->p->next; | |
272 | } | |
273 | while (!(*iter)->p) { | |
274 | if (++(*iter)->h == size) { | |
275 | delete *iter; | |
276 | *iter = NULL; | |
277 | return gFalse; | |
278 | } | |
279 | (*iter)->p = tab[(*iter)->h]; | |
280 | } | |
281 | *key = (*iter)->p->key; | |
282 | *val = (*iter)->p->val.p; | |
283 | return gTrue; | |
284 | } | |
285 | ||
286 | GBool GHash::getNext(GHashIter **iter, GString **key, int *val) { | |
287 | if (!*iter) { | |
288 | return gFalse; | |
289 | } | |
290 | if ((*iter)->p) { | |
291 | (*iter)->p = (*iter)->p->next; | |
292 | } | |
293 | while (!(*iter)->p) { | |
294 | if (++(*iter)->h == size) { | |
295 | delete *iter; | |
296 | *iter = NULL; | |
297 | return gFalse; | |
298 | } | |
299 | (*iter)->p = tab[(*iter)->h]; | |
300 | } | |
301 | *key = (*iter)->p->key; | |
302 | *val = (*iter)->p->val.i; | |
303 | return gTrue; | |
304 | } | |
305 | ||
306 | void GHash::killIter(GHashIter **iter) { | |
307 | delete *iter; | |
308 | *iter = NULL; | |
309 | } | |
310 | ||
311 | void GHash::expand() { | |
312 | GHashBucket **oldTab; | |
313 | GHashBucket *p; | |
314 | int oldSize, h, i; | |
315 | ||
316 | oldSize = size; | |
317 | oldTab = tab; | |
318 | size = 2*size + 1; | |
319 | tab = (GHashBucket **)gmallocn(size, sizeof(GHashBucket *)); | |
320 | for (h = 0; h < size; ++h) { | |
321 | tab[h] = NULL; | |
322 | } | |
323 | for (i = 0; i < oldSize; ++i) { | |
324 | while (oldTab[i]) { | |
325 | p = oldTab[i]; | |
326 | oldTab[i] = oldTab[i]->next; | |
327 | h = hash(p->key); | |
328 | p->next = tab[h]; | |
329 | tab[h] = p; | |
330 | } | |
331 | } | |
332 | gfree(oldTab); | |
333 | } | |
334 | ||
335 | GHashBucket *GHash::find(GString *key, int *h) { | |
336 | GHashBucket *p; | |
337 | ||
338 | *h = hash(key); | |
339 | for (p = tab[*h]; p; p = p->next) { | |
340 | if (!p->key->cmp(key)) { | |
341 | return p; | |
342 | } | |
343 | } | |
344 | return NULL; | |
345 | } | |
346 | ||
347 | GHashBucket *GHash::find(char *key, int *h) { | |
348 | GHashBucket *p; | |
349 | ||
350 | *h = hash(key); | |
351 | for (p = tab[*h]; p; p = p->next) { | |
352 | if (!p->key->cmp(key)) { | |
353 | return p; | |
354 | } | |
355 | } | |
356 | return NULL; | |
357 | } | |
358 | ||
359 | int GHash::hash(GString *key) { | |
360 | char *p; | |
361 | unsigned int h; | |
362 | int i; | |
363 | ||
364 | h = 0; | |
365 | for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) { | |
366 | h = 17 * h + (int)(*p & 0xff); | |
367 | } | |
368 | return (int)(h % size); | |
369 | } | |
370 | ||
371 | int GHash::hash(char *key) { | |
372 | char *p; | |
373 | unsigned int h; | |
374 | ||
375 | h = 0; | |
376 | for (p = key; *p; ++p) { | |
377 | h = 17 * h + (int)(*p & 0xff); | |
378 | } | |
379 | return (int)(h % size); | |
380 | } |