contrib/mdocml/compat_ohash.c

3 #if HAVE_OHASH
9 /* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */
13  * Permission to use, copy, modify, and distribute this software for any
14  * purpose with or without fee is hereby granted, provided that the above
15  * copyright notice and this permission notice appear in all copies.
17  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
18  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
19  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
20  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
21  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
22  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
23  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
36 	uint32_t	hv;
43 /* Don't bother changing the hash table if the change is small enough.  */
44 #define MINSIZE		(1UL << 4)
50 /* This handles the common case of variable length keys, where the
51  * key is stored at the end of the record.
58 	if (!*end)
61 	if (p) {
69  * to free entries as well.  */
83 	size_t ns;
87 	if (4 * h->deleted < h->total) {
88 		if (h->size >= (UINT_MAX >> 1U))
89 			ns = UINT_MAX;
91 			ns = h->size << 1U;
92 	} else if (3 * h->deleted > 2 * h->total)
93 		ns = h->size >> 1U;
95 		ns = h->size;
96 	if (ns < MINSIZE)
97 		ns = MINSIZE;
100 	STAT_HASH_SIZE += ns - h->size;
103 	n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
104 	if (!n)
108 		if (h->t[j].p != NULL && h->t[j].p != DELETED) {
109 			i = h->t[j].hv % ns;
110 			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
113 				if (i >= ns)
114 					i -= ns;
116 			n[i].hv = h->t[j].hv;
122 	h->size = ns;
132 	if (result == NULL || result == DELETED)
140 	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
148 	if (h->t[i].p == DELETED)
160 	if (h->t[i].p == DELETED) {
165 		/* Arbitrary resize boundary.  Tweak if not efficient enough.  */
166 		if (++h->total * 4 > h->size * 3)
189 		if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
197 	h->size = 1UL << size;
198 	if (h->size < MINSIZE)
204 	/* Copy info so that caller may free it.  */
220 	if (!*e)
222 	if (s == *e)
227 		k =  ((k << 2) | (k >> 30)) ^ *s++;
233     uint32_t hv)
242 	i = hv % h->size;
243 	incr = ((hv % (h->size-2)) & ~1) + 1;
248 		if (h->t[i].p == DELETED) {
249 			if (empty == NONE)
251 		} else if (h->t[i].hv == hv &&
255 			if (empty != NONE) {
256 				h->t[empty].hv = hv;
268 		if (i >= h->size)
272 	/* Found an empty position.  */
273 	if (empty != NONE)
275 	h->t[i].hv = hv;
280 ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
289 	i = hv % h->size;
290 	incr = ((hv % (h->size-2)) & ~1) + 1;
295 		if (h->t[i].p == DELETED) {
296 			if (empty == NONE)
298 		} else if (h->t[i].hv == hv &&
300 			if (empty != NONE) {
301 				h->t[empty].hv = hv;
312 		if (i >= h->size)
316 	/* Found an empty position.  */
317 	if (empty != NONE)
319 	h->t[i].hv = hv;
333 	uint32_t hv;
335 	hv = ohash_interval(s, e);
336 	return ohash_lookup_interval(h, s, *e, hv);