Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libutil/ohash.c	Lines:	130	141	92.2 %
Date:	2017-11-07	Branches:	72	86	83.7 %


/* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt 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 "ohash.h"

struct _ohash_record {
	uint32_t	hv;
	const char	*p;
};

#define DELETED		((const char *)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 ohash_resize(struct ohash *);


/* This handles the common case of variable length keys, where the
 * key is stored at the end of the record.
 */
void *
ohash_create_entry(struct ohash_info *i, const char *start, const char **end)
{
	char *p;

	if (!*end)
		*end = start + strlen(start);
	p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
	if (p) {
		memcpy(p+i->key_offset, start, *end-start);
		p[i->key_offset + (*end - start)] = '\0';
	}
	return (void *)p;
}

/* hash_delete only frees the hash structure. Use hash_first/hash_next
 * to free entries as well.  */
void
ohash_delete(struct ohash *h)
{
	(h->info.free)(h->t, h->info.data);
#ifndef NDEBUG
	h->t = NULL;
#endif
}

static void
ohash_resize(struct ohash *h)
{
	struct _ohash_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;
#ifdef STATS_HASH
	STAT_HASH_EXPAND++;
	STAT_HASH_SIZE += ns - h->size;
#endif

	n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
	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;
		}
	}
	(h->info.free)(h->t, h->info.data);
	h->t = n;
	h->size = ns;
	h->total -= h->deleted;
	h->deleted = 0;
}

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

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

#ifdef STATS_HASH
	STAT_HASH_ENTRIES--;
#endif
	h->t[i].p = DELETED;
	h->deleted++;
	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
		ohash_resize(h);
	return result;
}

void *
ohash_find(struct ohash *h, unsigned int i)
{
	if (h->t[i].p == DELETED)
		return NULL;
	else
		return (void *)h->t[i].p;
}

void *
ohash_insert(struct ohash *h, unsigned int i, void *p)
{
#ifdef STATS_HASH
	STAT_HASH_ENTRIES++;
#endif
	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)
			ohash_resize(h);
	}
	return p;
}

unsigned int
ohash_entries(struct ohash *h)
{
	return h->total - h->deleted;
}

void *
ohash_first(struct ohash *h, unsigned int *pos)
{
	*pos = 0;
	return ohash_next(h, pos);
}

void *
ohash_next(struct ohash *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;
}

void
ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)
{
	h->size = 1UL << size;
	if (h->size < MINSIZE)
		h->size = MINSIZE;
#ifdef STATS_HASH
	STAT_HASH_CREATION++;
	STAT_HASH_SIZE += h->size;
#endif
	/* Copy info so that caller may free it.  */
	h->info.key_offset = info->key_offset;
	h->info.calloc = info->calloc;
	h->info.free = info->free;
	h->info.alloc = info->alloc;
	h->info.data = info->data;
	h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
		    h->info.data);
	h->total = h->deleted = 0;
}

uint32_t
ohash_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;
}

unsigned int
ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
    uint32_t hv)
{
	unsigned int	i, incr;
	unsigned int	empty;

#ifdef STATS_HASH
	STAT_HASH_LOOKUP++;
#endif
	empty = NONE;
	i = hv % h->size;
	incr = ((hv % (h->size-2)) & ~1) + 1;
	while (h->t[i].p != NULL) {
#ifdef STATS_HASH
		STAT_HASH_LENGTH++;
#endif
		if (h->t[i].p == DELETED) {
			if (empty == NONE)
				empty = i;
		} else if (h->t[i].hv == hv &&
		    strncmp(h->t[i].p+h->info.key_offset, start,
			end - start) == 0 &&
		    (h->t[i].p+h->info.key_offset)[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 {
#ifdef STATS_HASH
				STAT_HASH_POSITIVE++;
#endif
				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;
}

unsigned int
ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
{
	unsigned int	i, incr;
	unsigned int	empty;

#ifdef STATS_HASH
	STAT_HASH_LOOKUP++;
#endif
	empty = NONE;
	i = hv % h->size;
	incr = ((hv % (h->size-2)) & ~1) + 1;
	while (h->t[i].p != NULL) {
#ifdef STATS_HASH
		STAT_HASH_LENGTH++;
#endif
		if (h->t[i].p == DELETED) {
			if (empty == NONE)
				empty = i;
		} else if (h->t[i].hv == hv &&
		    memcmp(h->t[i].p+h->info.key_offset, k, size) == 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 {
#ifdef STATS_HASH
				STAT_HASH_POSITIVE++;
#endif
			}	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;
}

unsigned int
ohash_qlookup(struct ohash *h, const char *s)
{
	const char *e = NULL;
	return ohash_qlookupi(h, s, &e);
}

unsigned int
ohash_qlookupi(struct ohash *h, const char *s, const char **e)
{
	uint32_t hv;

	hv = ohash_interval(s, e);
	return ohash_lookup_interval(h, s, *e, hv);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt 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			#include "ohash.h"
24
25			struct _ohash_record {
26			uint32_t hv;
27			const char *p;
28			};
29
30			#define DELETED ((const char *)h)
31			#define NONE (h->size)
32
33			/* Don't bother changing the hash table if the change is small enough. */
34			#define MINSIZE (1UL << 4)
35			#define MINDELETED 4
36
37			static void ohash_resize(struct ohash *);
38
39
40			/* This handles the common case of variable length keys, where the
41			* key is stored at the end of the record.
42			*/
43			void *
44			ohash_create_entry(struct ohash_info i, const char start, const char **end)
45			{
46			char *p;
47
48	✓✓	20706718	if (!*end)
49		11120	*end = start + strlen(start);
50		10353359	p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
51	✓✗	10353359	if (p) {
52		10353359	memcpy(p+i->key_offset, start, *end-start);
53		10353359	p[i->key_offset + (*end - start)] = '\0';
54		10353359	}
55		10353359	return (void *)p;
56			}
57
58			/* hash_delete only frees the hash structure. Use hash_first/hash_next
59			* to free entries as well. */
60			void
61			ohash_delete(struct ohash *h)
62			{
63		157046	(h->info.free)(h->t, h->info.data);
64			#ifndef NDEBUG
65		78523	h->t = NULL;
66			#endif
67		78523	}
68
69			static void
70			ohash_resize(struct ohash *h)
71			{
72			struct _ohash_record *n;
73			size_t ns;
74			unsigned int j;
75			unsigned int i, incr;
76
77	✓✓	185940	if (4 * h->deleted < h->total) {
78	✗✓	75094	if (h->size >= (UINT_MAX >> 1U))
79			ns = UINT_MAX;
80			else
81		75094	ns = h->size << 1U;
82	✓✓	17876	} else if (3 * h->deleted > 2 * h->total)
83		6243	ns = h->size >> 1U;
84			else
85		11633	ns = h->size;
86	✓✓	92970	if (ns < MINSIZE)
87		6243	ns = MINSIZE;
88			#ifdef STATS_HASH
89			STAT_HASH_EXPAND++;
90			STAT_HASH_SIZE += ns - h->size;
91			#endif
92
93		92970	n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
94	✗✓	92970	if (!n)
95			return;
96
97	✓✓	21229908	for (j = 0; j < h->size; j++) {
98	✓✓✓✓	18375805	if (h->t[j].p != NULL && h->t[j].p != DELETED) {
99		7781751	i = h->t[j].hv % ns;
100		7781751	incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
101	✓✓	252150361	while (n[i].p != NULL) {
102		236586859	i += incr;
103	✓✓	236586859	if (i >= ns)
104		83087952	i -= ns;
105			}
106		7781751	n[i].hv = h->t[j].hv;
107		7781751	n[i].p = h->t[j].p;
108		7781751	}
109			}
110		92970	(h->info.free)(h->t, h->info.data);
111		92970	h->t = n;
112		92970	h->size = ns;
113		92970	h->total -= h->deleted;
114		92970	h->deleted = 0;
115		185940	}
116
117			void *
118			ohash_remove(struct ohash *h, unsigned int i)
119			{
120		236796	void result = (void )h->t[i].p;
121
122	✓✗✗✓	236796	if (result == NULL \|\| result == DELETED)
123			return NULL;
124
125			#ifdef STATS_HASH
126			STAT_HASH_ENTRIES--;
127			#endif
128		118398	h->t[i].p = DELETED;
129		118398	h->deleted++;
130	✓✓✓✓	137053	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
131		17876	ohash_resize(h);
132		118398	return result;
133		118398	}
134
135			void *
136			ohash_find(struct ohash *h, unsigned int i)
137			{
138	✓✓	99202782	if (h->t[i].p == DELETED)
139		298236	return NULL;
140			else
141		49303155	return (void *)h->t[i].p;
142		49601391	}
143
144			void *
145			ohash_insert(struct ohash h, unsigned int i, void p)
146			{
147			#ifdef STATS_HASH
148			STAT_HASH_ENTRIES++;
149			#endif
150	✓✓	25410270	if (h->t[i].p == DELETED) {
151		42408	h->deleted--;
152		42408	h->t[i].p = p;
153		42408	} else {
154		12662727	h->t[i].p = p;
155			/* Arbitrary resize boundary. Tweak if not efficient enough. */
156	✓✓	12662727	if (++h->total * 4 > h->size * 3)
157		75094	ohash_resize(h);
158			}
159		12705135	return p;
160			}
161
162			unsigned int
163			ohash_entries(struct ohash *h)
164			{
165		2640	return h->total - h->deleted;
166			}
167
168			void *
169			ohash_first(struct ohash h, unsigned int pos)
170			{
171		248466	*pos = 0;
172		124233	return ohash_next(h, pos);
173			}
174
175			void *
176			ohash_next(struct ohash h, unsigned int pos)
177			{
178	✓✓	104002370	for (; pos < h->size; (pos)++)
179	✓✗✓✓	94635486	if (h->t[pos].p != DELETED && h->t[pos].p != NULL)
180		9018845	return (void )h->t[(pos)++].p;
181		116013	return NULL;
182		9134858	}
183
184			void
185			ohash_init(struct ohash h, unsigned int size, struct ohash_info info)
186			{
187		359150	h->size = 1UL << size;
188	✗✓	179575	if (h->size < MINSIZE)
189			h->size = MINSIZE;
190			#ifdef STATS_HASH
191			STAT_HASH_CREATION++;
192			STAT_HASH_SIZE += h->size;
193			#endif
194			/* Copy info so that caller may free it. */
195		179575	h->info.key_offset = info->key_offset;
196		179575	h->info.calloc = info->calloc;
197		179575	h->info.free = info->free;
198		179575	h->info.alloc = info->alloc;
199		179575	h->info.data = info->data;
200		179575	h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
201			h->info.data);
202		179575	h->total = h->deleted = 0;
203		179575	}
204
205			uint32_t
206			ohash_interval(const char s, const char *e)
207			{
208			uint32_t k;
209
210	✓✓	101819524	if (!*e)
211		7966243	*e = s + strlen(s);
212	✓✓	50909762	if (s == *e)
213		250756	k = 0;
214			else
215		50659006	k = *s++;
216	✓✓	931417830	while (s != *e)
217		440254034	k = ((k << 2) \| (k >> 30)) ^ *s++;
218		50909762	return k;
219			}
220
221			unsigned int
222			ohash_lookup_interval(struct ohash h, const char start, const char *end,
223			uint32_t hv)
224			{
225			unsigned int i, incr;
226			unsigned int empty;
227
228			#ifdef STATS_HASH
229			STAT_HASH_LOOKUP++;
230			#endif
231		102528068	empty = NONE;
232		51264034	i = hv % h->size;
233		51264034	incr = ((hv % (h->size-2)) & ~1) + 1;
234	✓✓	644006788	while (h->t[i].p != NULL) {
235			#ifdef STATS_HASH
236			STAT_HASH_LENGTH++;
237			#endif
238	✓✓	563123008	if (h->t[i].p == DELETED) {
239	✓✓	325803	if (empty == NONE)
240		298241	empty = i;
241	✓✓✓✗	584441493	} else if (h->t[i].hv == hv &&
242		313601736	strncmp(h->t[i].p+h->info.key_offset, start,
243	✓✓	313601736	end - start) == 0 &&
244		21644288	(h->t[i].p+h->info.key_offset)[end-start] == '\0') {
245	✓✓	21644288	if (empty != NONE) {
246		5	h->t[empty].hv = hv;
247		5	h->t[empty].p = h->t[i].p;
248		5	h->t[i].p = DELETED;
249		5	return empty;
250			} else {
251			#ifdef STATS_HASH
252			STAT_HASH_POSITIVE++;
253			#endif
254		21644283	return i;
255			}
256			}
257		541478720	i += incr;
258	✓✓	541478720	if (i >= h->size)
259		255556277	i -= h->size;
260			}
261
262			/* Found an empty position. */
263	✓✓	29619746	if (empty != NONE)
264		298236	i = empty;
265		29619746	h->t[i].hv = hv;
266		29619746	return i;
267		51264034	}
268
269			unsigned int
270			ohash_lookup_memory(struct ohash h, const char k, size_t size, uint32_t hv)
271			{
272			unsigned int i, incr;
273			unsigned int empty;
274
275			#ifdef STATS_HASH
276			STAT_HASH_LOOKUP++;
277			#endif
278		11824	empty = NONE;
279		5912	i = hv % h->size;
280		5912	incr = ((hv % (h->size-2)) & ~1) + 1;
281	✓✓	12728	while (h->t[i].p != NULL) {
282			#ifdef STATS_HASH
283			STAT_HASH_LENGTH++;
284			#endif
285	✗✓	982	if (h->t[i].p == DELETED) {
286			if (empty == NONE)
287			empty = i;
288	✓✓✓✗	1060	} else if (h->t[i].hv == hv &&
289		78	memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
290	✗✓	78	if (empty != NONE) {
291			h->t[empty].hv = hv;
292			h->t[empty].p = h->t[i].p;
293			h->t[i].p = DELETED;
294			return empty;
295			} else {
296			#ifdef STATS_HASH
297			STAT_HASH_POSITIVE++;
298			#endif
299		78	} return i;
300			}
301		904	i += incr;
302	✓✓	904	if (i >= h->size)
303		277	i -= h->size;
304			}
305
306			/* Found an empty position. */
307	✗✓	5834	if (empty != NONE)
308			i = empty;
309		5834	h->t[i].hv = hv;
310		5834	return i;
311		5912	}
312
313			unsigned int
314			ohash_qlookup(struct ohash h, const char s)
315			{
316		5196800	const char *e = NULL;
317		5196800	return ohash_qlookupi(h, s, &e);
318		2598400	}
319
320			unsigned int
321			ohash_qlookupi(struct ohash h, const char s, const char **e)
322			{
323			uint32_t hv;
324
325		35043682	hv = ohash_interval(s, e);
326		17521841	return ohash_lookup_interval(h, s, *e, hv);
327			}