source: trunk/poppler/mypoppler/goo/GooHash.cc @ 461

Last change on this file since 461 was 2, checked in by Eugene Romanenko, 15 years ago

First import

File size: 6.1 KB
Line 
1//========================================================================
2//
3// GooHash.cc
4//
5// Copyright 2001-2003 Glyph & Cog, LLC
6//
7//========================================================================
8
9#include <config.h>
10
11#ifdef USE_GCC_PRAGMAS
12#pragma implementation
13#endif
14
15#include "gmem.h"
16#include "GooString.h"
17#include "GooHash.h"
18
19//------------------------------------------------------------------------
20
21struct GooHashBucket {
22  GooString *key;
23  union {
24    void *p;
25    int i;
26  } val;
27  GooHashBucket *next;
28};
29
30struct GooHashIter {
31  int h;
32  GooHashBucket *p;
33};
34
35//------------------------------------------------------------------------
36
37GooHash::GooHash(GBool deleteKeysA) {
38  int h;
39
40  deleteKeys = deleteKeysA;
41  size = 7;
42  tab = (GooHashBucket **)gmallocn(size, sizeof(GooHashBucket *));
43  for (h = 0; h < size; ++h) {
44    tab[h] = NULL;
45  }
46  len = 0;
47}
48
49GooHash::~GooHash() {
50  GooHashBucket *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
66void GooHash::add(GooString *key, void *val) {
67  GooHashBucket *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 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;
83}
84
85void GooHash::add(GooString *key, int val) {
86  GooHashBucket *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 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;
102}
103
104void GooHash::replace(GooString *key, void *val) {
105  GooHashBucket *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
116void GooHash::replace(GooString *key, int val) {
117  GooHashBucket *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
128void *GooHash::lookup(GooString *key) {
129  GooHashBucket *p;
130  int h;
131
132  if (!(p = find(key, &h))) {
133    return NULL;
134  }
135  return p->val.p;
136}
137
138int GooHash::lookupInt(GooString *key) {
139  GooHashBucket *p;
140  int h;
141
142  if (!(p = find(key, &h))) {
143    return 0;
144  }
145  return p->val.i;
146}
147
148void *GooHash::lookup(char *key) {
149  GooHashBucket *p;
150  int h;
151
152  if (!(p = find(key, &h))) {
153    return NULL;
154  }
155  return p->val.p;
156}
157
158int GooHash::lookupInt(char *key) {
159  GooHashBucket *p;
160  int h;
161
162  if (!(p = find(key, &h))) {
163    return 0;
164  }
165  return p->val.i;
166}
167
168void *GooHash::remove(GooString *key) {
169  GooHashBucket *p;
170  GooHashBucket **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
191int GooHash::removeInt(GooString *key) {
192  GooHashBucket *p;
193  GooHashBucket **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
214void *GooHash::remove(char *key) {
215  GooHashBucket *p;
216  GooHashBucket **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
237int GooHash::removeInt(char *key) {
238  GooHashBucket *p;
239  GooHashBucket **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
260void GooHash::startIter(GooHashIter **iter) {
261  *iter = new GooHashIter;
262  (*iter)->h = -1;
263  (*iter)->p = NULL;
264}
265
266GBool GooHash::getNext(GooHashIter **iter, GooString **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
286GBool GooHash::getNext(GooHashIter **iter, GooString **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
306void GooHash::killIter(GooHashIter **iter) {
307  delete *iter;
308  *iter = NULL;
309}
310
311void GooHash::expand() {
312  GooHashBucket **oldTab;
313  GooHashBucket *p;
314  int oldSize, h, i;
315
316  oldSize = size;
317  oldTab = tab;
318  size = 2*size + 1;
319  tab = (GooHashBucket **)gmallocn(size, sizeof(GooHashBucket *));
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
335GooHashBucket *GooHash::find(GooString *key, int *h) {
336  GooHashBucket *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
347GooHashBucket *GooHash::find(char *key, int *h) {
348  GooHashBucket *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
359int GooHash::hash(GooString *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
371int GooHash::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}
Note: See TracBrowser for help on using the repository browser.