/src/xpdf-4.06/goo/GHash.cc

Source
//========================================================================
//
// GHash.cc
//
// Copyright 2001-2003 Glyph & Cog, LLC
//
//========================================================================

#include <aconf.h>

#include "gmem.h"
#include "gmempp.h"
#include "GString.h"
#include "GHash.h"

//------------------------------------------------------------------------

struct GHashBucket {
  GString *key;
  union {
    void *p;
    int i;
  } val;
  GHashBucket *next;
};

struct GHashIter {
  int h;
  GHashBucket *p;
};

//------------------------------------------------------------------------

GHash::GHash(GBool deleteKeysA) {
  int h;

  deleteKeys = deleteKeysA;
  size = 7;
  tab = (GHashBucket **)gmallocn(size, sizeof(GHashBucket *));
  for (h = 0; h < size; ++h) {
    tab[h] = NULL;
  }
  len = 0;
}

GHash::~GHash() {
  GHashBucket *p;
  int h;

  for (h = 0; h < size; ++h) {
    while (tab[h]) {
      p = tab[h];
      tab[h] = p->next;
      if (deleteKeys) {
  delete p->key;
      }
      delete p;
    }
  }
  gfree(tab);
}

void GHash::add(GString *key, void *val) {
  GHashBucket *p;
  int h;

  // expand the table if necessary
  if (len >= size) {
    expand();
  }

  // add the new symbol
  p = new GHashBucket;
  p->key = key;
  p->val.p = val;
  h = hash(key);
  p->next = tab[h];
  tab[h] = p;
  ++len;
}

void GHash::add(GString *key, int val) {
  GHashBucket *p;
  int h;

  // expand the table if necessary
  if (len >= size) {
    expand();
  }

  // add the new symbol
  p = new GHashBucket;
  p->key = key;
  p->val.i = val;
  h = hash(key);
  p->next = tab[h];
  tab[h] = p;
  ++len;
}

void GHash::replace(GString *key, void *val) {
  GHashBucket *p;
  int h;

  if ((p = find(key, &h))) {
    p->val.p = val;
    if (deleteKeys) {
      delete key;
    }
  } else {
    add(key, val);
  }
}

void GHash::replace(GString *key, int val) {
  GHashBucket *p;
  int h;

  if ((p = find(key, &h))) {
    p->val.i = val;
    if (deleteKeys) {
      delete key;
    }
  } else {
    add(key, val);
  }
}

void *GHash::lookup(GString *key) {
  GHashBucket *p;
  int h;

  if (!(p = find(key, &h))) {
    return NULL;
  }
  return p->val.p;
}

int GHash::lookupInt(GString *key) {
  GHashBucket *p;
  int h;

  if (!(p = find(key, &h))) {
    return 0;
  }
  return p->val.i;
}

void *GHash::lookup(const char *key) {
  GHashBucket *p;
  int h;

  if (!(p = find(key, &h))) {
    return NULL;
  }
  return p->val.p;
}

int GHash::lookupInt(const char *key) {
  GHashBucket *p;
  int h;

  if (!(p = find(key, &h))) {
    return 0;
  }
  return p->val.i;
}

void *GHash::remove(GString *key) {
  GHashBucket *p;
  GHashBucket **q;
  void *val;
  int h;

  if (!(p = find(key, &h))) {
    return NULL;
  }
  q = &tab[h];
  while (*q != p) {
    q = &((*q)->next);
  }
  *q = p->next;
  if (deleteKeys) {
    delete p->key;
  }
  val = p->val.p;
  delete p;
  --len;
  return val;
}

int GHash::removeInt(GString *key) {
  GHashBucket *p;
  GHashBucket **q;
  int val;
  int h;

  if (!(p = find(key, &h))) {
    return 0;
  }
  q = &tab[h];
  while (*q != p) {
    q = &((*q)->next);
  }
  *q = p->next;
  if (deleteKeys) {
    delete p->key;
  }
  val = p->val.i;
  delete p;
  --len;
  return val;
}

void *GHash::remove(const char *key) {
  GHashBucket *p;
  GHashBucket **q;
  void *val;
  int h;

  if (!(p = find(key, &h))) {
    return NULL;
  }
  q = &tab[h];
  while (*q != p) {
    q = &((*q)->next);
  }
  *q = p->next;
  if (deleteKeys) {
    delete p->key;
  }
  val = p->val.p;
  delete p;
  --len;
  return val;
}

int GHash::removeInt(const char *key) {
  GHashBucket *p;
  GHashBucket **q;
  int val;
  int h;

  if (!(p = find(key, &h))) {
    return 0;
  }
  q = &tab[h];
  while (*q != p) {
    q = &((*q)->next);
  }
  *q = p->next;
  if (deleteKeys) {
    delete p->key;
  }
  val = p->val.i;
  delete p;
  --len;
  return val;
}

void GHash::startIter(GHashIter **iter) {
  *iter = new GHashIter;
  (*iter)->h = -1;
  (*iter)->p = NULL;
}

GBool GHash::getNext(GHashIter **iter, GString **key, void **val) {
  if (!*iter) {
    return gFalse;
  }
  if ((*iter)->p) {
    (*iter)->p = (*iter)->p->next;
  }
  while (!(*iter)->p) {
    if (++(*iter)->h == size) {
      delete *iter;
      *iter = NULL;
      return gFalse;
    }
    (*iter)->p = tab[(*iter)->h];
  }
  *key = (*iter)->p->key;
  *val = (*iter)->p->val.p;
  return gTrue;
}

GBool GHash::getNext(GHashIter **iter, GString **key, int *val) {
  if (!*iter) {
    return gFalse;
  }
  if ((*iter)->p) {
    (*iter)->p = (*iter)->p->next;
  }
  while (!(*iter)->p) {
    if (++(*iter)->h == size) {
      delete *iter;
      *iter = NULL;
      return gFalse;
    }
    (*iter)->p = tab[(*iter)->h];
  }
  *key = (*iter)->p->key;
  *val = (*iter)->p->val.i;
  return gTrue;
}

void GHash::killIter(GHashIter **iter) {
  delete *iter;
  *iter = NULL;
}

void GHash::expand() {
  GHashBucket **oldTab;
  GHashBucket *p;
  int oldSize, h, i;

  oldSize = size;
  oldTab = tab;
  size = 2*size + 1;
  tab = (GHashBucket **)gmallocn(size, sizeof(GHashBucket *));
  for (h = 0; h < size; ++h) {
    tab[h] = NULL;
  }
  for (i = 0; i < oldSize; ++i) {
    while (oldTab[i]) {
      p = oldTab[i];
      oldTab[i] = oldTab[i]->next;
      h = hash(p->key);
      p->next = tab[h];
      tab[h] = p;
    }
  }
  gfree(oldTab);
}

GHashBucket *GHash::find(GString *key, int *h) {
  GHashBucket *p;

  *h = hash(key);
  for (p = tab[*h]; p; p = p->next) {
    if (!p->key->cmp(key)) {
      return p;
    }
  }
  return NULL;
}

GHashBucket *GHash::find(const char *key, int *h) {
  GHashBucket *p;

  *h = hash(key);
  for (p = tab[*h]; p; p = p->next) {
    if (!p->key->cmp(key)) {
      return p;
    }
  }
  return NULL;
}

int GHash::hash(GString *key) {
  const char *p;
  unsigned int h;
  int i;

  h = 0;
  for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
    h = 17 * h + (int)(*p & 0xff);
  }
  return (int)(h % size);
}

int GHash::hash(const char *key) {
  const char *p;
  unsigned int h;

  h = 0;
  for (p = key; *p; ++p) {
    h = 17 * h + (int)(*p & 0xff);
  }
  return (int)(h % size);
}

Coverage Report

Created: 2026-02-04 06:14

Line	Count	Source
1		//========================================================================
2		//
3		// GHash.cc
4		//
5		// Copyright 2001-2003 Glyph & Cog, LLC
6		//
7		//========================================================================
8
9		#include <aconf.h>
10
11		#include "gmem.h"
12		#include "gmempp.h"
13		#include "GString.h"
14		#include "GHash.h"
15
16		//------------------------------------------------------------------------
17
18		struct GHashBucket {
19		GString *key;
20		union {
21		void *p;
22		int i;
23		} val;
24		GHashBucket *next;
25		};
26
27		struct GHashIter {
28		int h;
29		GHashBucket *p;
30		};
31
32		//------------------------------------------------------------------------
33
34	3.21M	GHash::GHash(GBool deleteKeysA) {
35	3.21M	int h;
36
37	3.21M	deleteKeys = deleteKeysA;
38	3.21M	size = 7;
39	3.21M	tab = (GHashBucket *)gmallocn(size, sizeof(GHashBucket ));
40	25.7M	for (h = 0; h < size; ++h) {
41	22.5M	tab[h] = NULL;
42	22.5M	}
43	3.21M	len = 0;
44	3.21M	}
45
46	3.21M	GHash::~GHash() {
47	3.21M	GHashBucket *p;
48	3.21M	int h;
49
50	27.2M	for (h = 0; h < size; ++h) {
51	25.3M	while (tab[h]) {
52	1.28M	p = tab[h];
53	1.28M	tab[h] = p->next;
54	1.28M	if (deleteKeys) {
55	201k	delete p->key;
56	201k	}
57	1.28M	delete p;
58	1.28M	}
59	24.0M	}
60	3.21M	gfree(tab);
61	3.21M	}
62
63	1.19M	void GHash::add(GString key, void val) {
64	1.19M	GHashBucket *p;
65	1.19M	int h;
66
67		// expand the table if necessary
68	1.19M	if (len >= size) {
69	8.54k	expand();
70	8.54k	}
71
72		// add the new symbol
73	1.19M	p = new GHashBucket;
74	1.19M	p->key = key;
75	1.19M	p->val.p = val;
76	1.19M	h = hash(key);
77	1.19M	p->next = tab[h];
78	1.19M	tab[h] = p;
79	1.19M	++len;
80	1.19M	}
81
82	97.3k	void GHash::add(GString *key, int val) {
83	97.3k	GHashBucket *p;
84	97.3k	int h;
85
86		// expand the table if necessary
87	97.3k	if (len >= size) {
88	2.89k	expand();
89	2.89k	}
90
91		// add the new symbol
92	97.3k	p = new GHashBucket;
93	97.3k	p->key = key;
94	97.3k	p->val.i = val;
95	97.3k	h = hash(key);
96	97.3k	p->next = tab[h];
97	97.3k	tab[h] = p;
98	97.3k	++len;
99	97.3k	}
100
101	0	void GHash::replace(GString key, void val) {
102	0	GHashBucket *p;
103	0	int h;
104
105	0	if ((p = find(key, &h))) {
106	0	p->val.p = val;
107	0	if (deleteKeys) {
108	0	delete key;
109	0	}
110	0	} else {
111	0	add(key, val);
112	0	}
113	0	}
114
115	44.9k	void GHash::replace(GString *key, int val) {
116	44.9k	GHashBucket *p;
117	44.9k	int h;
118
119	44.9k	if ((p = find(key, &h))) {
120	15.0k	p->val.i = val;
121	15.0k	if (deleteKeys) {
122	0	delete key;
123	0	}
124	29.8k	} else {
125	29.8k	add(key, val);
126	29.8k	}
127	44.9k	}
128
129	69.8k	void GHash::lookup(GString key) {
130	69.8k	GHashBucket *p;
131	69.8k	int h;
132
133	69.8k	if (!(p = find(key, &h))) {
134	69.8k	return NULL;
135	69.8k	}
136	6	return p->val.p;
137	69.8k	}
138
139	53.0k	int GHash::lookupInt(GString *key) {
140	53.0k	GHashBucket *p;
141	53.0k	int h;
142
143	53.0k	if (!(p = find(key, &h))) {
144	37.9k	return 0;
145	37.9k	}
146	15.0k	return p->val.i;
147	53.0k	}
148
149	1.55M	void GHash::lookup(const char key) {
150	1.55M	GHashBucket *p;
151	1.55M	int h;
152
153	1.55M	if (!(p = find(key, &h))) {
154	1.44M	return NULL;
155	1.44M	}
156	108k	return p->val.p;
157	1.55M	}
158
159	634k	int GHash::lookupInt(const char *key) {
160	634k	GHashBucket *p;
161	634k	int h;
162
163	634k	if (!(p = find(key, &h))) {
164	575k	return 0;
165	575k	}
166	59.5k	return p->val.i;
167	634k	}
168
169	0	void GHash::remove(GString key) {
170	0	GHashBucket *p;
171	0	GHashBucket **q;
172	0	void *val;
173	0	int h;
174
175	0	if (!(p = find(key, &h))) {
176	0	return NULL;
177	0	}
178	0	q = &tab[h];
179	0	while (*q != p) {
180	0	q = &((*q)->next);
181	0	}
182	0	*q = p->next;
183	0	if (deleteKeys) {
184	0	delete p->key;
185	0	}
186	0	val = p->val.p;
187	0	delete p;
188	0	--len;
189	0	return val;
190	0	}
191
192	1.91k	int GHash::removeInt(GString *key) {
193	1.91k	GHashBucket *p;
194	1.91k	GHashBucket **q;
195	1.91k	int val;
196	1.91k	int h;
197
198	1.91k	if (!(p = find(key, &h))) {
199	68	return 0;
200	68	}
201	1.85k	q = &tab[h];
202	1.89k	while (*q != p) {
203	39	q = &((*q)->next);
204	39	}
205	1.85k	*q = p->next;
206	1.85k	if (deleteKeys) {
207	1.85k	delete p->key;
208	1.85k	}
209	1.85k	val = p->val.i;
210	1.85k	delete p;
211	1.85k	--len;
212	1.85k	return val;
213	1.91k	}
214
215	0	void GHash::remove(const char key) {
216	0	GHashBucket *p;
217	0	GHashBucket **q;
218	0	void *val;
219	0	int h;
220
221	0	if (!(p = find(key, &h))) {
222	0	return NULL;
223	0	}
224	0	q = &tab[h];
225	0	while (*q != p) {
226	0	q = &((*q)->next);
227	0	}
228	0	*q = p->next;
229	0	if (deleteKeys) {
230	0	delete p->key;
231	0	}
232	0	val = p->val.p;
233	0	delete p;
234	0	--len;
235	0	return val;
236	0	}
237
238	5.46k	int GHash::removeInt(const char *key) {
239	5.46k	GHashBucket *p;
240	5.46k	GHashBucket **q;
241	5.46k	int val;
242	5.46k	int h;
243
244	5.46k	if (!(p = find(key, &h))) {
245	144	return 0;
246	144	}
247	5.31k	q = &tab[h];
248	5.64k	while (*q != p) {
249	324	q = &((*q)->next);
250	324	}
251	5.31k	*q = p->next;
252	5.31k	if (deleteKeys) {
253	5.31k	delete p->key;
254	5.31k	}
255	5.31k	val = p->val.i;
256	5.31k	delete p;
257	5.31k	--len;
258	5.31k	return val;
259	5.46k	}
260
261	3.15M	void GHash::startIter(GHashIter **iter) {
262	3.15M	*iter = new GHashIter;
263	3.15M	(*iter)->h = -1;
264	3.15M	(*iter)->p = NULL;
265	3.15M	}
266
267	4.35M	GBool GHash::getNext(GHashIter iter, GString key, void **val) {
268	4.35M	if (!*iter) {
269	0	return gFalse;
270	0	}
271	4.35M	if ((*iter)->p) {
272	1.19M	(iter)->p = (iter)->p->next;
273	1.19M	}
274	27.8M	while (!(*iter)->p) {
275	26.6M	if (++(*iter)->h == size) {
276	3.15M	delete *iter;
277	3.15M	*iter = NULL;
278	3.15M	return gFalse;
279	3.15M	}
280	23.5M	(iter)->p = tab[(iter)->h];
281	23.5M	}
282	1.19M	key = (iter)->p->key;
283	1.19M	val = (iter)->p->val.p;
284	1.19M	return gTrue;
285	4.35M	}
286
287	0	GBool GHash::getNext(GHashIter iter, GString key, int *val) {
288	0	if (!*iter) {
289	0	return gFalse;
290	0	}
291	0	if ((*iter)->p) {
292	0	(iter)->p = (iter)->p->next;
293	0	}
294	0	while (!(*iter)->p) {
295	0	if (++(*iter)->h == size) {
296	0	delete *iter;
297	0	*iter = NULL;
298	0	return gFalse;
299	0	}
300	0	(iter)->p = tab[(iter)->h];
301	0	}
302	0	key = (iter)->p->key;
303	0	val = (iter)->p->val.i;
304	0	return gTrue;
305	0	}
306
307	6	void GHash::killIter(GHashIter **iter) {
308	6	delete *iter;
309	6	*iter = NULL;
310	6	}
311
312	11.4k	void GHash::expand() {
313	11.4k	GHashBucket **oldTab;
314	11.4k	GHashBucket *p;
315	11.4k	int oldSize, h, i;
316
317	11.4k	oldSize = size;
318	11.4k	oldTab = tab;
319	11.4k	size = 2*size + 1;
320	11.4k	tab = (GHashBucket *)gmallocn(size, sizeof(GHashBucket ));
321	3.05M	for (h = 0; h < size; ++h) {
322	3.04M	tab[h] = NULL;
323	3.04M	}
324	1.52M	for (i = 0; i < oldSize; ++i) {
325	3.03M	while (oldTab[i]) {
326	1.51M	p = oldTab[i];
327	1.51M	oldTab[i] = oldTab[i]->next;
328	1.51M	h = hash(p->key);
329	1.51M	p->next = tab[h];
330	1.51M	tab[h] = p;
331	1.51M	}
332	1.51M	}
333	11.4k	gfree(oldTab);
334	11.4k	}
335
336	169k	GHashBucket GHash::find(GString key, int *h) {
337	169k	GHashBucket *p;
338
339	169k	*h = hash(key);
340	182k	for (p = tab[*h]; p; p = p->next) {
341	45.2k	if (!p->key->cmp(key)) {
342	32.0k	return p;
343	32.0k	}
344	45.2k	}
345	137k	return NULL;
346	169k	}
347
348	2.19M	GHashBucket GHash::find(const char key, int *h) {
349	2.19M	GHashBucket *p;
350
351	2.19M	*h = hash(key);
352	2.26M	for (p = tab[*h]; p; p = p->next) {
353	245k	if (!p->key->cmp(key)) {
354	173k	return p;
355	173k	}
356	245k	}
357	2.02M	return NULL;
358	2.19M	}
359
360	2.98M	int GHash::hash(GString *key) {
361	2.98M	const char *p;
362	2.98M	unsigned int h;
363	2.98M	int i;
364
365	2.98M	h = 0;
366	29.7M	for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
367	26.8M	h = 17 * h + (int)(*p & 0xff);
368	26.8M	}
369	2.98M	return (int)(h % size);
370	2.98M	}
371
372	2.19M	int GHash::hash(const char *key) {
373	2.19M	const char *p;
374	2.19M	unsigned int h;
375
376	2.19M	h = 0;
377	25.3M	for (p = key; *p; ++p) {
378	23.1M	h = 17 * h + (int)(*p & 0xff);
379	23.1M	}
380	2.19M	return (int)(h % size);
381	2.19M	}