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