Generated from configure.in
[swftools.git] / pdf2swf / xpdf / GHash.cc
1 //========================================================================
2 //
3 // GHash.cc
4 //
5 // Copyright 2001-2002 Glyph & Cog, LLC
6 //
7 //========================================================================
8
9 #ifdef __GNUC__
10 #pragma implementation
11 #endif
12
13 #include <aconf.h>
14 #include "gmem.h"
15 #include "GString.h"
16 #include "GHash.h"
17
18 //------------------------------------------------------------------------
19
20 struct GHashBucket {
21   GString *key;
22   void *val;
23   GHashBucket *next;
24 };
25
26 struct GHashIter {
27   int h;
28   GHashBucket *p;
29 };
30
31 //------------------------------------------------------------------------
32
33 GHash::GHash(GBool deleteKeysA) {
34   int h;
35
36   deleteKeys = deleteKeysA;
37   size = 7;
38   tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
39   for (h = 0; h < size; ++h) {
40     tab[h] = NULL;
41   }
42   len = 0;
43 }
44
45 GHash::~GHash() {
46   GHashBucket *p;
47   int h;
48
49   for (h = 0; h < size; ++h) {
50     while (tab[h]) {
51       p = tab[h];
52       tab[h] = p->next;
53       if (deleteKeys) {
54         delete p->key;
55       }
56       delete p;
57     }
58   }
59   gfree(tab);
60 }
61
62 void GHash::add(GString *key, void *val) {
63   GHashBucket **oldTab;
64   GHashBucket *p;
65   int oldSize, i, h;
66
67   // expand the table if necessary
68   if (len >= size) {
69     oldSize = size;
70     oldTab = tab;
71     size = 2*size + 1;
72     tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
73     for (h = 0; h < size; ++h) {
74       tab[h] = NULL;
75     }
76     for (i = 0; i < oldSize; ++i) {
77       while (oldTab[i]) {
78         p = oldTab[i];
79         oldTab[i] = oldTab[i]->next;
80         h = hash(p->key);
81         p->next = tab[h];
82         tab[h] = p;
83       }
84     }
85     gfree(oldTab);
86   }
87
88   // add the new symbol
89   p = new GHashBucket;
90   p->key = key;
91   p->val = val;
92   h = hash(key);
93   p->next = tab[h];
94   tab[h] = p;
95   ++len;
96 }
97
98 void *GHash::lookup(GString *key) {
99   GHashBucket *p;
100   int h;
101
102   if (!(p = find(key, &h))) {
103     return NULL;
104   }
105   return p->val;
106 }
107
108 void *GHash::lookup(char *key) {
109   GHashBucket *p;
110   int h;
111
112   if (!(p = find(key, &h))) {
113     return NULL;
114   }
115   return p->val;
116 }
117
118 void *GHash::remove(GString *key) {
119   GHashBucket *p;
120   GHashBucket **q;
121   void *val;
122   int h;
123
124   if (!(p = find(key, &h))) {
125     return NULL;
126   }
127   q = &tab[h];
128   while (*q != p) {
129     q = &((*q)->next);
130   }
131   *q = p->next;
132   if (deleteKeys) {
133     delete p->key;
134   }
135   val = p->val;
136   delete p;
137   --len;
138   return val;
139 }
140
141 void *GHash::remove(char *key) {
142   GHashBucket *p;
143   GHashBucket **q;
144   void *val;
145   int h;
146
147   if (!(p = find(key, &h))) {
148     return NULL;
149   }
150   q = &tab[h];
151   while (*q != p) {
152     q = &((*q)->next);
153   }
154   *q = p->next;
155   if (deleteKeys) {
156     delete p->key;
157   }
158   val = p->val;
159   delete p;
160   --len;
161   return val;
162 }
163
164 void GHash::startIter(GHashIter **iter) {
165   *iter = new GHashIter;
166   (*iter)->h = -1;
167   (*iter)->p = NULL;
168 }
169
170 GBool GHash::getNext(GHashIter **iter, GString **key, void **val) {
171   if (!*iter) {
172     return gFalse;
173   }
174   if ((*iter)->p) {
175     (*iter)->p = (*iter)->p->next;
176   }
177   while (!(*iter)->p) {
178     if (++(*iter)->h == size) {
179       delete *iter;
180       *iter = NULL;
181       return gFalse;
182     }
183     (*iter)->p = tab[(*iter)->h];
184   }
185   *key = (*iter)->p->key;
186   *val = (*iter)->p->val;
187   return gTrue;
188 }
189
190 void GHash::killIter(GHashIter **iter) {
191   delete *iter;
192   *iter = NULL;
193 }
194
195 GHashBucket *GHash::find(GString *key, int *h) {
196   GHashBucket *p;
197
198   *h = hash(key);
199   for (p = tab[*h]; p; p = p->next) {
200     if (!p->key->cmp(key)) {
201       return p;
202     }
203   }
204   return NULL;
205 }
206
207 GHashBucket *GHash::find(char *key, int *h) {
208   GHashBucket *p;
209
210   *h = hash(key);
211   for (p = tab[*h]; p; p = p->next) {
212     if (!p->key->cmp(key)) {
213       return p;
214     }
215   }
216   return NULL;
217 }
218
219 int GHash::hash(GString *key) {
220   char *p;
221   unsigned int h;
222   int i;
223
224   h = 0;
225   for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
226     h = 17 * h + (int)(*p & 0xff);
227   }
228   return (int)(h % size);
229 }
230
231 int GHash::hash(char *key) {
232   char *p;
233   unsigned int h;
234
235   h = 0;
236   for (p = key; *p; ++p) {
237     h = 17 * h + (int)(*p & 0xff);
238   }
239   return (int)(h % size);
240 }