sinc with TL rev. 38618.
[luatex.git] / source / libs / poppler / poppler-0.37.0 / goo / GooHash.cc
blobf4a92f17506ded1ed964c27ae60af5974a8f751a
1 //========================================================================
2 //
3 // GooHash.cc
4 //
5 // Copyright 2001-2003 Glyph & Cog, LLC
6 //
7 //========================================================================
9 #include <config.h>
11 #ifdef USE_GCC_PRAGMAS
12 #pragma implementation
13 #endif
15 #include "gmem.h"
16 #include "GooString.h"
17 #include "GooHash.h"
19 //------------------------------------------------------------------------
21 struct GooHashBucket {
22 GooString *key;
23 union {
24 void *p;
25 int i;
26 } val;
27 GooHashBucket *next;
30 struct GooHashIter {
31 int h;
32 GooHashBucket *p;
35 //------------------------------------------------------------------------
37 GooHash::GooHash(GBool deleteKeysA) {
38 int h;
40 deleteKeys = deleteKeysA;
41 size = 7;
42 tab = (GooHashBucket **)gmallocn(size, sizeof(GooHashBucket *));
43 for (h = 0; h < size; ++h) {
44 tab[h] = NULL;
46 len = 0;
49 GooHash::~GooHash() {
50 GooHashBucket *p;
51 int h;
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;
60 delete p;
63 gfree(tab);
66 void GooHash::add(GooString *key, void *val) {
67 GooHashBucket *p;
68 int h;
70 // expand the table if necessary
71 if (len >= size) {
72 expand();
75 // add the new symbol
76 p = new GooHashBucket;
77 p->key = key;
78 p->val.p = val;
79 h = hash(key);
80 p->next = tab[h];
81 tab[h] = p;
82 ++len;
85 void GooHash::add(GooString *key, int val) {
86 GooHashBucket *p;
87 int h;
89 // expand the table if necessary
90 if (len >= size) {
91 expand();
94 // add the new symbol
95 p = new GooHashBucket;
96 p->key = key;
97 p->val.i = val;
98 h = hash(key);
99 p->next = tab[h];
100 tab[h] = p;
101 ++len;
104 void GooHash::replace(GooString *key, void *val) {
105 GooHashBucket *p;
106 int h;
108 if ((p = find(key, &h))) {
109 p->val.p = val;
110 if (deleteKeys) {
111 delete key;
113 } else {
114 add(key, val);
118 void GooHash::replace(GooString *key, int val) {
119 GooHashBucket *p;
120 int h;
122 if ((p = find(key, &h))) {
123 p->val.i = val;
124 if (deleteKeys) {
125 delete key;
127 } else {
128 add(key, val);
132 void *GooHash::lookup(GooString *key) {
133 GooHashBucket *p;
134 int h;
136 if (!(p = find(key, &h))) {
137 return NULL;
139 return p->val.p;
142 int GooHash::lookupInt(GooString *key) {
143 GooHashBucket *p;
144 int h;
146 if (!(p = find(key, &h))) {
147 return 0;
149 return p->val.i;
152 void *GooHash::lookup(const char *key) {
153 GooHashBucket *p;
154 int h;
156 if (!(p = find(key, &h))) {
157 return NULL;
159 return p->val.p;
162 int GooHash::lookupInt(const char *key) {
163 GooHashBucket *p;
164 int h;
166 if (!(p = find(key, &h))) {
167 return 0;
169 return p->val.i;
172 void *GooHash::remove(GooString *key) {
173 GooHashBucket *p;
174 GooHashBucket **q;
175 void *val;
176 int h;
178 if (!(p = find(key, &h))) {
179 return NULL;
181 q = &tab[h];
182 while (*q != p) {
183 q = &((*q)->next);
185 *q = p->next;
186 if (deleteKeys) {
187 delete p->key;
189 val = p->val.p;
190 delete p;
191 --len;
192 return val;
195 int GooHash::removeInt(GooString *key) {
196 GooHashBucket *p;
197 GooHashBucket **q;
198 int val;
199 int h;
201 if (!(p = find(key, &h))) {
202 return 0;
204 q = &tab[h];
205 while (*q != p) {
206 q = &((*q)->next);
208 *q = p->next;
209 if (deleteKeys) {
210 delete p->key;
212 val = p->val.i;
213 delete p;
214 --len;
215 return val;
218 void *GooHash::remove(const char *key) {
219 GooHashBucket *p;
220 GooHashBucket **q;
221 void *val;
222 int h;
224 if (!(p = find(key, &h))) {
225 return NULL;
227 q = &tab[h];
228 while (*q != p) {
229 q = &((*q)->next);
231 *q = p->next;
232 if (deleteKeys) {
233 delete p->key;
235 val = p->val.p;
236 delete p;
237 --len;
238 return val;
241 int GooHash::removeInt(const char *key) {
242 GooHashBucket *p;
243 GooHashBucket **q;
244 int val;
245 int h;
247 if (!(p = find(key, &h))) {
248 return 0;
250 q = &tab[h];
251 while (*q != p) {
252 q = &((*q)->next);
254 *q = p->next;
255 if (deleteKeys) {
256 delete p->key;
258 val = p->val.i;
259 delete p;
260 --len;
261 return val;
264 void GooHash::startIter(GooHashIter **iter) {
265 *iter = new GooHashIter;
266 (*iter)->h = -1;
267 (*iter)->p = NULL;
270 GBool GooHash::getNext(GooHashIter **iter, GooString **key, void **val) {
271 if (!*iter) {
272 return gFalse;
274 if ((*iter)->p) {
275 (*iter)->p = (*iter)->p->next;
277 while (!(*iter)->p) {
278 if (++(*iter)->h == size) {
279 delete *iter;
280 *iter = NULL;
281 return gFalse;
283 (*iter)->p = tab[(*iter)->h];
285 *key = (*iter)->p->key;
286 *val = (*iter)->p->val.p;
287 return gTrue;
290 GBool GooHash::getNext(GooHashIter **iter, GooString **key, int *val) {
291 if (!*iter) {
292 return gFalse;
294 if ((*iter)->p) {
295 (*iter)->p = (*iter)->p->next;
297 while (!(*iter)->p) {
298 if (++(*iter)->h == size) {
299 delete *iter;
300 *iter = NULL;
301 return gFalse;
303 (*iter)->p = tab[(*iter)->h];
305 *key = (*iter)->p->key;
306 *val = (*iter)->p->val.i;
307 return gTrue;
310 void GooHash::killIter(GooHashIter **iter) {
311 delete *iter;
312 *iter = NULL;
315 void GooHash::expand() {
316 GooHashBucket **oldTab;
317 GooHashBucket *p;
318 int oldSize, h, i;
320 oldSize = size;
321 oldTab = tab;
322 size = 2*size + 1;
323 tab = (GooHashBucket **)gmallocn(size, sizeof(GooHashBucket *));
324 for (h = 0; h < size; ++h) {
325 tab[h] = NULL;
327 for (i = 0; i < oldSize; ++i) {
328 while (oldTab[i]) {
329 p = oldTab[i];
330 oldTab[i] = oldTab[i]->next;
331 h = hash(p->key);
332 p->next = tab[h];
333 tab[h] = p;
336 gfree(oldTab);
339 GooHashBucket *GooHash::find(GooString *key, int *h) {
340 GooHashBucket *p;
342 *h = hash(key);
343 for (p = tab[*h]; p; p = p->next) {
344 if (!p->key->cmp(key)) {
345 return p;
348 return NULL;
351 GooHashBucket *GooHash::find(const char *key, int *h) {
352 GooHashBucket *p;
354 *h = hash(key);
355 for (p = tab[*h]; p; p = p->next) {
356 if (!p->key->cmp(key)) {
357 return p;
360 return NULL;
363 int GooHash::hash(GooString *key) {
364 const char *p;
365 unsigned int h;
366 int i;
368 h = 0;
369 for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
370 h = 17 * h + (int)(*p & 0xff);
372 return (int)(h % size);
375 int GooHash::hash(const char *key) {
376 const char *p;
377 unsigned int h;
379 h = 0;
380 for (p = key; *p; ++p) {
381 h = 17 * h + (int)(*p & 0xff);
383 return (int)(h % size);