← Back to branch summary

~ubuntu-branches/ubuntu/wily/luatex/wily

« back to all changes in this revision

Viewing changes to source/libs/xpdf/xpdf-3.02/goo/GHash.cc

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Preining
  • Date: 2010-04-29 00:47:19 UTC
  • mfrom: (1.1.10 upstream)
  • Revision ID: james.westby@ubuntu.com-20100429004719-o42etkqe90n97b9e
Tags: 0.60.1-1
* new upstream release, adapt build-script patch
* disable patch: upstream-epstopdf_cc_no_xpdf_patching, included upstream
* disable patch: libpoppler-0.12, not needed anymore

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/libs/xpdf/xpdf-3.02/goo/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
}