1dd0e26c2497edfb00213b2d468caa49c4af72f5
[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 **)gmalloc(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::lookup(GString *key) {
105   GHashBucket *p;
106   int h;
107
108   if (!(p = find(key, &h))) {
109     return NULL;
110   }
111   return p->val.p;
112 }
113
114 int GHash::lookupInt(GString *key) {
115   GHashBucket *p;
116   int h;
117
118   if (!(p = find(key, &h))) {
119     return 0;
120   }
121   return p->val.i;
122 }
123
124 void *GHash::lookup(char *key) {
125   GHashBucket *p;
126   int h;
127
128   if (!(p = find(key, &h))) {
129     return NULL;
130   }
131   return p->val.p;
132 }
133
134 int GHash::lookupInt(char *key) {
135   GHashBucket *p;
136   int h;
137
138   if (!(p = find(key, &h))) {
139     return 0;
140   }
141   return p->val.i;
142 }
143
144 void *GHash::remove(GString *key) {
145   GHashBucket *p;
146   GHashBucket **q;
147   void *val;
148   int h;
149
150   if (!(p = find(key, &h))) {
151     return NULL;
152   }
153   q = &tab[h];
154   while (*q != p) {
155     q = &((*q)->next);
156   }
157   *q = p->next;
158   if (deleteKeys) {
159     delete p->key;
160   }
161   val = p->val.p;
162   delete p;
163   --len;
164   return val;
165 }
166
167 int GHash::removeInt(GString *key) {
168   GHashBucket *p;
169   GHashBucket **q;
170   int val;
171   int h;
172
173   if (!(p = find(key, &h))) {
174     return 0;
175   }
176   q = &tab[h];
177   while (*q != p) {
178     q = &((*q)->next);
179   }
180   *q = p->next;
181   if (deleteKeys) {
182     delete p->key;
183   }
184   val = p->val.i;
185   delete p;
186   --len;
187   return val;
188 }
189
190 void *GHash::remove(char *key) {
191   GHashBucket *p;
192   GHashBucket **q;
193   void *val;
194   int h;
195
196   if (!(p = find(key, &h))) {
197     return NULL;
198   }
199   q = &tab[h];
200   while (*q != p) {
201     q = &((*q)->next);
202   }
203   *q = p->next;
204   if (deleteKeys) {
205     delete p->key;
206   }
207   val = p->val.p;
208   delete p;
209   --len;
210   return val;
211 }
212
213 int GHash::removeInt(char *key) {
214   GHashBucket *p;
215   GHashBucket **q;
216   int val;
217   int h;
218
219   if (!(p = find(key, &h))) {
220     return 0;
221   }
222   q = &tab[h];
223   while (*q != p) {
224     q = &((*q)->next);
225   }
226   *q = p->next;
227   if (deleteKeys) {
228     delete p->key;
229   }
230   val = p->val.i;
231   delete p;
232   --len;
233   return val;
234 }
235
236 void GHash::startIter(GHashIter **iter) {
237   *iter = new GHashIter;
238   (*iter)->h = -1;
239   (*iter)->p = NULL;
240 }
241
242 GBool GHash::getNext(GHashIter **iter, GString **key, void **val) {
243   if (!*iter) {
244     return gFalse;
245   }
246   if ((*iter)->p) {
247     (*iter)->p = (*iter)->p->next;
248   }
249   while (!(*iter)->p) {
250     if (++(*iter)->h == size) {
251       delete *iter;
252       *iter = NULL;
253       return gFalse;
254     }
255     (*iter)->p = tab[(*iter)->h];
256   }
257   *key = (*iter)->p->key;
258   *val = (*iter)->p->val.p;
259   return gTrue;
260 }
261
262 GBool GHash::getNext(GHashIter **iter, GString **key, int *val) {
263   if (!*iter) {
264     return gFalse;
265   }
266   if ((*iter)->p) {
267     (*iter)->p = (*iter)->p->next;
268   }
269   while (!(*iter)->p) {
270     if (++(*iter)->h == size) {
271       delete *iter;
272       *iter = NULL;
273       return gFalse;
274     }
275     (*iter)->p = tab[(*iter)->h];
276   }
277   *key = (*iter)->p->key;
278   *val = (*iter)->p->val.i;
279   return gTrue;
280 }
281
282 void GHash::killIter(GHashIter **iter) {
283   delete *iter;
284   *iter = NULL;
285 }
286
287 void GHash::expand() {
288   GHashBucket **oldTab;
289   GHashBucket *p;
290   int oldSize, h, i;
291
292   oldSize = size;
293   oldTab = tab;
294   size = 2*size + 1;
295   tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
296   for (h = 0; h < size; ++h) {
297     tab[h] = NULL;
298   }
299   for (i = 0; i < oldSize; ++i) {
300     while (oldTab[i]) {
301       p = oldTab[i];
302       oldTab[i] = oldTab[i]->next;
303       h = hash(p->key);
304       p->next = tab[h];
305       tab[h] = p;
306     }
307   }
308   gfree(oldTab);
309 }
310
311 GHashBucket *GHash::find(GString *key, int *h) {
312   GHashBucket *p;
313
314   *h = hash(key);
315   for (p = tab[*h]; p; p = p->next) {
316     if (!p->key->cmp(key)) {
317       return p;
318     }
319   }
320   return NULL;
321 }
322
323 GHashBucket *GHash::find(char *key, int *h) {
324   GHashBucket *p;
325
326   *h = hash(key);
327   for (p = tab[*h]; p; p = p->next) {
328     if (!p->key->cmp(key)) {
329       return p;
330     }
331   }
332   return NULL;
333 }
334
335 int GHash::hash(GString *key) {
336   char *p;
337   unsigned int h;
338   int i;
339
340   h = 0;
341   for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
342     h = 17 * h + (int)(*p & 0xff);
343   }
344   return (int)(h % size);
345 }
346
347 int GHash::hash(char *key) {
348   char *p;
349   unsigned int h;
350
351   h = 0;
352   for (p = key; *p; ++p) {
353     h = 17 * h + (int)(*p & 0xff);
354   }
355   return (int)(h % size);
356 }