GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/ctfconv/hash.c Lines: 0 102 0.0 %
Date: 2017-11-13 Branches: 0 72 0.0 %

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
	p->hkey = key;
123
124
	if (h->t[i].p == DELETED) {
125
		h->deleted--;
126
		h->t[i].p = p;
127
	} else {
128
		h->t[i].p = p;
129
		/* Arbitrary resize boundary.  Tweak if not efficient enough. */
130
		if (++h->total * 4 > h->size * 3)
131
			hash_resize(h);
132
	}
133
}
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
	h = calloc(1, sizeof(*h));
157
	if (h == NULL)
158
		return NULL;
159
160
	h->size = 1UL << size;
161
	if (h->size < MINSIZE)
162
		h->size = MINSIZE;
163
	/* Copy info so that caller may free it.  */
164
	h->total = h->deleted = 0;
165
	h->t = calloc(h->size, sizeof(struct _hash_record));
166
	if (h->t == NULL) {
167
		free(h);
168
		return NULL;
169
	}
170
171
	return h;
172
}
173
174
static uint32_t
175
hash_interval(const char *s, const char **e)
176
{
177
	uint32_t k;
178
179
	if (!*e)
180
		*e = s + strlen(s);
181
	if (s == *e)
182
		k = 0;
183
	else
184
		k = *s++;
185
	while (s != *e)
186
		k =  ((k << 2) | (k >> 30)) ^ *s++;
187
	return k;
188
}
189
190
static unsigned int
191
hash_qlookup(struct hash *h, const char *start)
192
{
193
	const char *end = NULL;
194
	unsigned int i, incr;
195
	unsigned int empty;
196
	uint32_t hv;
197
198
	hv = hash_interval(start, &end);
199
200
	empty = NONE;
201
	i = hv % h->size;
202
	incr = ((hv % (h->size-2)) & ~1) + 1;
203
	while (h->t[i].p != NULL) {
204
		if (h->t[i].p == DELETED) {
205
			if (empty == NONE)
206
				empty = i;
207
		} else if (h->t[i].hv == hv &&
208
		    strncmp(h->t[i].p->hkey, start, end - start) == 0 &&
209
		    (h->t[i].p->hkey)[end-start] == '\0') {
210
			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
				return i;
217
			}
218
		}
219
		i += incr;
220
		if (i >= h->size)
221
			i -= h->size;
222
	}
223
224
	/* Found an empty position.  */
225
	if (empty != NONE)
226
		i = empty;
227
	h->t[i].hv = hv;
228
	return i;
229
}
230
231
struct hash_entry *
232
hash_find(struct hash *h, const char *start, unsigned int *slot)
233
{
234
	unsigned int i;
235
236
	i = hash_qlookup(h, start);
237
	if (slot != NULL)
238
		*slot = i;
239
240
	if (h->t[i].p == DELETED)
241
		return NULL;
242
243
	return h->t[i].p;
244
}