Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/ctfconv/hash.c	Lines:	43	106	40.6 %
Date:	2017-11-07	Branches:	19	72	26.4 %


/*	$OpenBSD: hash.c,v 1.2 2017/08/11 14:58:56 jasper Exp $ */

/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "hash.h"

struct _hash_record {
	uint32_t	hv;
	struct hash_entry	*p;
};

struct hash {
	struct _hash_record 	*t;
	unsigned int 		size;
	unsigned int 		total;
	unsigned int 		deleted;
};

#define DELETED		((struct hash_entry *)h)
#define NONE		(h->size)

/* Don't bother changing the hash table if the change is small enough.  */
#define MINSIZE		(1UL << 4)
#define MINDELETED	4

static void hash_resize(struct hash *);
static uint32_t hash_interval(const char *, const char **);
static unsigned int hash_qlookup(struct hash *, const char *);


/* hash_delete only frees the hash structure. Use hash_first/hash_next
 * to free entries as well.  */
void
hash_delete(struct hash *h)
{
	free(h->t);
	h->t = NULL;
}

static void
hash_resize(struct hash *h)
{
	struct _hash_record *n;
	size_t ns;
	unsigned int	j;
	unsigned int	i, incr;

	if (4 * h->deleted < h->total) {
		if (h->size >= (UINT_MAX >> 1U))
			ns = UINT_MAX;
		else
			ns = h->size << 1U;
	} else if (3 * h->deleted > 2 * h->total)
		ns = h->size >> 1U;
	else
		ns = h->size;
	if (ns < MINSIZE)
		ns = MINSIZE;

	n = calloc(ns, sizeof(struct _hash_record));
	if (!n)
		return;

	for (j = 0; j < h->size; j++) {
		if (h->t[j].p != NULL && h->t[j].p != DELETED) {
			i = h->t[j].hv % ns;
			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
			while (n[i].p != NULL) {
				i += incr;
				if (i >= ns)
					i -= ns;
			}
			n[i].hv = h->t[j].hv;
			n[i].p = h->t[j].p;
		}
	}
	free(h->t);
	h->t = n;
	h->size = ns;
	h->total -= h->deleted;
	h->deleted = 0;
}

void *
hash_remove(struct hash *h, unsigned int i)
{
	void		*result = (void *)h->t[i].p;

	if (result == NULL || result == DELETED)
		return NULL;

	h->t[i].p = DELETED;
	h->deleted++;
	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
		hash_resize(h);
	return result;
}

void
hash_insert(struct hash *h, unsigned int i, struct hash_entry *p,
    const char *key)
{
	p->hkey = key;

	if (h->t[i].p == DELETED) {
		h->deleted--;
		h->t[i].p = p;
	} else {
		h->t[i].p = p;
		/* Arbitrary resize boundary.  Tweak if not efficient enough. */
		if (++h->total * 4 > h->size * 3)
			hash_resize(h);
	}
}

void *
hash_first(struct hash *h, unsigned int *pos)
{
	*pos = 0;
	return hash_next(h, pos);
}

void *
hash_next(struct hash *h, unsigned int *pos)
{
	for (; *pos < h->size; (*pos)++)
		if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
			return (void *)h->t[(*pos)++].p;
	return NULL;
}

struct hash *
hash_init(unsigned int size)
{
	struct hash *h;

	h = calloc(1, sizeof(*h));
	if (h == NULL)
		return NULL;

	h->size = 1UL << size;
	if (h->size < MINSIZE)
		h->size = MINSIZE;
	/* Copy info so that caller may free it.  */
	h->total = h->deleted = 0;
	h->t = calloc(h->size, sizeof(struct _hash_record));
	if (h->t == NULL) {
		free(h);
		return NULL;
	}

	return h;
}

static uint32_t
hash_interval(const char *s, const char **e)
{
	uint32_t k;

	if (!*e)
		*e = s + strlen(s);
	if (s == *e)
		k = 0;
	else
		k = *s++;
	while (s != *e)
		k =  ((k << 2) | (k >> 30)) ^ *s++;
	return k;
}

static unsigned int
hash_qlookup(struct hash *h, const char *start)
{
	const char *end = NULL;
	unsigned int i, incr;
	unsigned int empty;
	uint32_t hv;

	hv = hash_interval(start, &end);

	empty = NONE;
	i = hv % h->size;
	incr = ((hv % (h->size-2)) & ~1) + 1;
	while (h->t[i].p != NULL) {
		if (h->t[i].p == DELETED) {
			if (empty == NONE)
				empty = i;
		} else if (h->t[i].hv == hv &&
		    strncmp(h->t[i].p->hkey, start, end - start) == 0 &&
		    (h->t[i].p->hkey)[end-start] == '\0') {
			if (empty != NONE) {
				h->t[empty].hv = hv;
				h->t[empty].p = h->t[i].p;
				h->t[i].p = DELETED;
				return empty;
			} else {
				return i;
			}
		}
		i += incr;
		if (i >= h->size)
			i -= h->size;
	}

	/* Found an empty position.  */
	if (empty != NONE)
		i = empty;
	h->t[i].hv = hv;
	return i;
}

struct hash_entry *
hash_find(struct hash *h, const char *start, unsigned int *slot)
{
	unsigned int i;

	i = hash_qlookup(h, start);
	if (slot != NULL)
		*slot = i;

	if (h->t[i].p == DELETED)
		return NULL;

	return h->t[i].p;
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: hash.c,v 1.2 2017/08/11 14:58:56 jasper Exp $ */
2
3			/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
4			*
5			* Permission to use, copy, modify, and distribute this software for any
6			* purpose with or without fee is hereby granted, provided that the above
7			* copyright notice and this permission notice appear in all copies.
8			*
9			* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10			* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11			* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12			* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13			* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14			* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15			* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16			*/
17
18			#include <stddef.h>
19			#include <stdint.h>
20			#include <stdlib.h>
21			#include <string.h>
22			#include <limits.h>
23
24			#include "hash.h"
25
26			struct _hash_record {
27			uint32_t hv;
28			struct hash_entry *p;
29			};
30
31			struct hash {
32			struct _hash_record *t;
33			unsigned int size;
34			unsigned int total;
35			unsigned int deleted;
36			};
37
38			#define DELETED ((struct hash_entry *)h)
39			#define NONE (h->size)
40
41			/* Don't bother changing the hash table if the change is small enough. */
42			#define MINSIZE (1UL << 4)
43			#define MINDELETED 4
44
45			static void hash_resize(struct hash *);
46			static uint32_t hash_interval(const char , const char *);
47			static unsigned int hash_qlookup(struct hash , const char );
48
49
50			/* hash_delete only frees the hash structure. Use hash_first/hash_next
51			* to free entries as well. */
52			void
53			hash_delete(struct hash *h)
54			{
55			free(h->t);
56			h->t = NULL;
57			}
58
59			static void
60			hash_resize(struct hash *h)
61			{
62			struct _hash_record *n;
63			size_t ns;
64			unsigned int j;
65			unsigned int i, incr;
66
67			if (4 * h->deleted < h->total) {
68			if (h->size >= (UINT_MAX >> 1U))
69			ns = UINT_MAX;
70			else
71			ns = h->size << 1U;
72			} else if (3 * h->deleted > 2 * h->total)
73			ns = h->size >> 1U;
74			else
75			ns = h->size;
76			if (ns < MINSIZE)
77			ns = MINSIZE;
78
79			n = calloc(ns, sizeof(struct _hash_record));
80			if (!n)
81			return;
82
83			for (j = 0; j < h->size; j++) {
84			if (h->t[j].p != NULL && h->t[j].p != DELETED) {
85			i = h->t[j].hv % ns;
86			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
87			while (n[i].p != NULL) {
88			i += incr;
89			if (i >= ns)
90			i -= ns;
91			}
92			n[i].hv = h->t[j].hv;
93			n[i].p = h->t[j].p;
94			}
95			}
96			free(h->t);
97			h->t = n;
98			h->size = ns;
99			h->total -= h->deleted;
100			h->deleted = 0;
101			}
102
103			void *
104			hash_remove(struct hash *h, unsigned int i)
105			{
106			void result = (void )h->t[i].p;
107
108			if (result == NULL \|\| result == DELETED)
109			return NULL;
110
111			h->t[i].p = DELETED;
112			h->deleted++;
113			if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
114			hash_resize(h);
115			return result;
116			}
117
118			void
119			hash_insert(struct hash h, unsigned int i, struct hash_entry p,
120			const char *key)
121			{
122		20	p->hkey = key;
123
124	✗✓	10	if (h->t[i].p == DELETED) {
125			h->deleted--;
126			h->t[i].p = p;
127			} else {
128		10	h->t[i].p = p;
129			/* Arbitrary resize boundary. Tweak if not efficient enough. */
130	✗✓	10	if (++h->total * 4 > h->size * 3)
131			hash_resize(h);
132			}
133		10	}
134
135			void *
136			hash_first(struct hash h, unsigned int pos)
137			{
138			*pos = 0;
139			return hash_next(h, pos);
140			}
141
142			void *
143			hash_next(struct hash h, unsigned int pos)
144			{
145			for (; pos < h->size; (pos)++)
146			if (h->t[pos].p != DELETED && h->t[pos].p != NULL)
147			return (void )h->t[(pos)++].p;
148			return NULL;
149			}
150
151			struct hash *
152			hash_init(unsigned int size)
153			{
154			struct hash *h;
155
156		4	h = calloc(1, sizeof(*h));
157	✗✓	2	if (h == NULL)
158			return NULL;
159
160		2	h->size = 1UL << size;
161	✗✓	2	if (h->size < MINSIZE)
162			h->size = MINSIZE;
163			/* Copy info so that caller may free it. */
164		2	h->total = h->deleted = 0;
165		2	h->t = calloc(h->size, sizeof(struct _hash_record));
166	✗✓	2	if (h->t == NULL) {
167			free(h);
168			return NULL;
169			}
170
171		2	return h;
172		2	}
173
174			static uint32_t
175			hash_interval(const char s, const char *e)
176			{
177			uint32_t k;
178
179	✓✗	32	if (!*e)
180		16	*e = s + strlen(s);
181	✗✓	16	if (s == *e)
182			k = 0;
183			else
184		16	k = *s++;
185	✓✓	152	while (s != *e)
186		68	k = ((k << 2) \| (k >> 30)) ^ *s++;
187		16	return k;
188			}
189
190			static unsigned int
191			hash_qlookup(struct hash h, const char start)
192			{
193		32	const char *end = NULL;
194			unsigned int i, incr;
195			unsigned int empty;
196			uint32_t hv;
197
198		16	hv = hash_interval(start, &end);
199
200		16	empty = NONE;
201		16	i = hv % h->size;
202		16	incr = ((hv % (h->size-2)) & ~1) + 1;
203	✓✓	32	while (h->t[i].p != NULL) {
204	✗✓	6	if (h->t[i].p == DELETED) {
205			if (empty == NONE)
206			empty = i;
207	✓✗✓✗	12	} else if (h->t[i].hv == hv &&
208	✓✗	6	strncmp(h->t[i].p->hkey, start, end - start) == 0 &&
209		6	(h->t[i].p->hkey)[end-start] == '\0') {
210	✗✓	6	if (empty != NONE) {
211			h->t[empty].hv = hv;
212			h->t[empty].p = h->t[i].p;
213			h->t[i].p = DELETED;
214			return empty;
215			} else {
216		6	return i;
217			}
218			}
219			i += incr;
220			if (i >= h->size)
221			i -= h->size;
222			}
223
224			/* Found an empty position. */
225	✗✓	10	if (empty != NONE)
226			i = empty;
227		10	h->t[i].hv = hv;
228		10	return i;
229		16	}
230
231			struct hash_entry *
232			hash_find(struct hash h, const char start, unsigned int *slot)
233			{
234			unsigned int i;
235
236		32	i = hash_qlookup(h, start);
237	✓✗	16	if (slot != NULL)
238		16	*slot = i;
239
240	✗✓	16	if (h->t[i].p == DELETED)
241			return NULL;
242
243		16	return h->t[i].p;
244		16	}