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

Source (jump to first uncovered line)
//========================================================================
//
// GHash.cc
//
// Copyright 2001-2003 Glyph & Cog, LLC
//
//========================================================================

#include <aconf.h>

#ifdef USE_GCC_PRAGMAS
#pragma implementation
#endif

#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: 2023-09-25 06:41

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