added missing {
[swftools.git] / pdf2swf / xpdf / GHash.cc
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 "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 }