1 0d6fb46a 2022-01-09 op /* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */
  2 0d6fb46a 2022-01-09 op 
  3 0d6fb46a 2022-01-09 op /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
  4 0d6fb46a 2022-01-09 op  *
  5 0d6fb46a 2022-01-09 op  * Permission to use, copy, modify, and distribute this software for any
  6 0d6fb46a 2022-01-09 op  * purpose with or without fee is hereby granted, provided that the above
  7 0d6fb46a 2022-01-09 op  * copyright notice and this permission notice appear in all copies.
  8 0d6fb46a 2022-01-09 op  *
  9 0d6fb46a 2022-01-09 op  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 10 0d6fb46a 2022-01-09 op  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 11 0d6fb46a 2022-01-09 op  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 12 0d6fb46a 2022-01-09 op  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 13 0d6fb46a 2022-01-09 op  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 14 0d6fb46a 2022-01-09 op  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 15 0d6fb46a 2022-01-09 op  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 16 0d6fb46a 2022-01-09 op  */
 17 0d6fb46a 2022-01-09 op 
 18 0d6fb46a 2022-01-09 op #include "compat.h"
 19 0d6fb46a 2022-01-09 op 
 20 0d6fb46a 2022-01-09 op #include <stddef.h>
 21 0d6fb46a 2022-01-09 op #include <stdint.h>
 22 0d6fb46a 2022-01-09 op #include <stdlib.h>
 23 0d6fb46a 2022-01-09 op #include <string.h>
 24 0d6fb46a 2022-01-09 op #include <limits.h>
 25 0d6fb46a 2022-01-09 op #include "ohash.h"
 26 0d6fb46a 2022-01-09 op 
 27 0d6fb46a 2022-01-09 op struct _ohash_record {
 28 0d6fb46a 2022-01-09 op 	uint32_t	hv;
 29 0d6fb46a 2022-01-09 op 	const char	*p;
 30 0d6fb46a 2022-01-09 op };
 31 0d6fb46a 2022-01-09 op 
 32 0d6fb46a 2022-01-09 op #define DELETED		((const char *)h)
 33 0d6fb46a 2022-01-09 op #define NONE		(h->size)
 34 0d6fb46a 2022-01-09 op 
 35 0d6fb46a 2022-01-09 op /* Don't bother changing the hash table if the change is small enough.  */
 36 0d6fb46a 2022-01-09 op #define MINSIZE		(1UL << 4)
 37 0d6fb46a 2022-01-09 op #define MINDELETED	4
 38 0d6fb46a 2022-01-09 op 
 39 0d6fb46a 2022-01-09 op static void ohash_resize(struct ohash *);
 40 0d6fb46a 2022-01-09 op 
 41 0d6fb46a 2022-01-09 op 
 42 0d6fb46a 2022-01-09 op /* This handles the common case of variable length keys, where the
 43 0d6fb46a 2022-01-09 op  * key is stored at the end of the record.
 44 0d6fb46a 2022-01-09 op  */
 45 0d6fb46a 2022-01-09 op void *
 46 0d6fb46a 2022-01-09 op ohash_create_entry(struct ohash_info *i, const char *start, const char **end)
 47 0d6fb46a 2022-01-09 op {
 48 0d6fb46a 2022-01-09 op 	char *p;
 49 0d6fb46a 2022-01-09 op 
 50 0d6fb46a 2022-01-09 op 	if (!*end)
 51 0d6fb46a 2022-01-09 op 		*end = start + strlen(start);
 52 0d6fb46a 2022-01-09 op 	p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
 53 0d6fb46a 2022-01-09 op 	if (p) {
 54 0d6fb46a 2022-01-09 op 		memcpy(p+i->key_offset, start, *end-start);
 55 0d6fb46a 2022-01-09 op 		p[i->key_offset + (*end - start)] = '\0';
 56 0d6fb46a 2022-01-09 op 	}
 57 0d6fb46a 2022-01-09 op 	return (void *)p;
 58 0d6fb46a 2022-01-09 op }
 59 0d6fb46a 2022-01-09 op 
 60 0d6fb46a 2022-01-09 op /* hash_delete only frees the hash structure. Use hash_first/hash_next
 61 0d6fb46a 2022-01-09 op  * to free entries as well.  */
 62 0d6fb46a 2022-01-09 op void
 63 0d6fb46a 2022-01-09 op ohash_delete(struct ohash *h)
 64 0d6fb46a 2022-01-09 op {
 65 0d6fb46a 2022-01-09 op 	(h->info.free)(h->t, h->info.data);
 66 0d6fb46a 2022-01-09 op #ifndef NDEBUG
 67 0d6fb46a 2022-01-09 op 	h->t = NULL;
 68 0d6fb46a 2022-01-09 op #endif
 69 0d6fb46a 2022-01-09 op }
 70 0d6fb46a 2022-01-09 op 
 71 0d6fb46a 2022-01-09 op static void
 72 0d6fb46a 2022-01-09 op ohash_resize(struct ohash *h)
 73 0d6fb46a 2022-01-09 op {
 74 0d6fb46a 2022-01-09 op 	struct _ohash_record *n;
 75 0d6fb46a 2022-01-09 op 	size_t ns;
 76 0d6fb46a 2022-01-09 op 	unsigned int	j;
 77 0d6fb46a 2022-01-09 op 	unsigned int	i, incr;
 78 0d6fb46a 2022-01-09 op 
 79 0d6fb46a 2022-01-09 op 	if (4 * h->deleted < h->total) {
 80 0d6fb46a 2022-01-09 op 		if (h->size >= (UINT_MAX >> 1U))
 81 0d6fb46a 2022-01-09 op 			ns = UINT_MAX;
 82 0d6fb46a 2022-01-09 op 		else
 83 0d6fb46a 2022-01-09 op 			ns = h->size << 1U;
 84 0d6fb46a 2022-01-09 op 	} else if (3 * h->deleted > 2 * h->total)
 85 0d6fb46a 2022-01-09 op 		ns = h->size >> 1U;
 86 0d6fb46a 2022-01-09 op 	else
 87 0d6fb46a 2022-01-09 op 		ns = h->size;
 88 0d6fb46a 2022-01-09 op 	if (ns < MINSIZE)
 89 0d6fb46a 2022-01-09 op 		ns = MINSIZE;
 90 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
 91 0d6fb46a 2022-01-09 op 	STAT_HASH_EXPAND++;
 92 0d6fb46a 2022-01-09 op 	STAT_HASH_SIZE += ns - h->size;
 93 0d6fb46a 2022-01-09 op #endif
 94 0d6fb46a 2022-01-09 op 
 95 0d6fb46a 2022-01-09 op 	n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
 96 0d6fb46a 2022-01-09 op 	if (!n)
 97 0d6fb46a 2022-01-09 op 		return;
 98 0d6fb46a 2022-01-09 op 
 99 0d6fb46a 2022-01-09 op 	for (j = 0; j < h->size; j++) {
100 0d6fb46a 2022-01-09 op 		if (h->t[j].p != NULL && h->t[j].p != DELETED) {
101 0d6fb46a 2022-01-09 op 			i = h->t[j].hv % ns;
102 0d6fb46a 2022-01-09 op 			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
103 0d6fb46a 2022-01-09 op 			while (n[i].p != NULL) {
104 0d6fb46a 2022-01-09 op 				i += incr;
105 0d6fb46a 2022-01-09 op 				if (i >= ns)
106 0d6fb46a 2022-01-09 op 					i -= ns;
107 0d6fb46a 2022-01-09 op 			}
108 0d6fb46a 2022-01-09 op 			n[i].hv = h->t[j].hv;
109 0d6fb46a 2022-01-09 op 			n[i].p = h->t[j].p;
110 0d6fb46a 2022-01-09 op 		}
111 0d6fb46a 2022-01-09 op 	}
112 0d6fb46a 2022-01-09 op 	(h->info.free)(h->t, h->info.data);
113 0d6fb46a 2022-01-09 op 	h->t = n;
114 0d6fb46a 2022-01-09 op 	h->size = ns;
115 0d6fb46a 2022-01-09 op 	h->total -= h->deleted;
116 0d6fb46a 2022-01-09 op 	h->deleted = 0;
117 0d6fb46a 2022-01-09 op }
118 0d6fb46a 2022-01-09 op 
119 0d6fb46a 2022-01-09 op void *
120 0d6fb46a 2022-01-09 op ohash_remove(struct ohash *h, unsigned int i)
121 0d6fb46a 2022-01-09 op {
122 0d6fb46a 2022-01-09 op 	void		*result = (void *)h->t[i].p;
123 0d6fb46a 2022-01-09 op 
124 0d6fb46a 2022-01-09 op 	if (result == NULL || result == DELETED)
125 0d6fb46a 2022-01-09 op 		return NULL;
126 0d6fb46a 2022-01-09 op 
127 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
128 0d6fb46a 2022-01-09 op 	STAT_HASH_ENTRIES--;
129 0d6fb46a 2022-01-09 op #endif
130 0d6fb46a 2022-01-09 op 	h->t[i].p = DELETED;
131 0d6fb46a 2022-01-09 op 	h->deleted++;
132 0d6fb46a 2022-01-09 op 	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
133 0d6fb46a 2022-01-09 op 		ohash_resize(h);
134 0d6fb46a 2022-01-09 op 	return result;
135 0d6fb46a 2022-01-09 op }
136 0d6fb46a 2022-01-09 op 
137 0d6fb46a 2022-01-09 op void *
138 0d6fb46a 2022-01-09 op ohash_find(struct ohash *h, unsigned int i)
139 0d6fb46a 2022-01-09 op {
140 0d6fb46a 2022-01-09 op 	if (h->t[i].p == DELETED)
141 0d6fb46a 2022-01-09 op 		return NULL;
142 0d6fb46a 2022-01-09 op 	else
143 0d6fb46a 2022-01-09 op 		return (void *)h->t[i].p;
144 0d6fb46a 2022-01-09 op }
145 0d6fb46a 2022-01-09 op 
146 0d6fb46a 2022-01-09 op void *
147 0d6fb46a 2022-01-09 op ohash_insert(struct ohash *h, unsigned int i, void *p)
148 0d6fb46a 2022-01-09 op {
149 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
150 0d6fb46a 2022-01-09 op 	STAT_HASH_ENTRIES++;
151 0d6fb46a 2022-01-09 op #endif
152 0d6fb46a 2022-01-09 op 	if (h->t[i].p == DELETED) {
153 0d6fb46a 2022-01-09 op 		h->deleted--;
154 0d6fb46a 2022-01-09 op 		h->t[i].p = p;
155 0d6fb46a 2022-01-09 op 	} else {
156 0d6fb46a 2022-01-09 op 		h->t[i].p = p;
157 0d6fb46a 2022-01-09 op 		/* Arbitrary resize boundary.  Tweak if not efficient enough.  */
158 0d6fb46a 2022-01-09 op 		if (++h->total * 4 > h->size * 3)
159 0d6fb46a 2022-01-09 op 			ohash_resize(h);
160 0d6fb46a 2022-01-09 op 	}
161 0d6fb46a 2022-01-09 op 	return p;
162 0d6fb46a 2022-01-09 op }
163 0d6fb46a 2022-01-09 op 
164 0d6fb46a 2022-01-09 op unsigned int
165 0d6fb46a 2022-01-09 op ohash_entries(struct ohash *h)
166 0d6fb46a 2022-01-09 op {
167 0d6fb46a 2022-01-09 op 	return h->total - h->deleted;
168 0d6fb46a 2022-01-09 op }
169 0d6fb46a 2022-01-09 op 
170 0d6fb46a 2022-01-09 op void *
171 0d6fb46a 2022-01-09 op ohash_first(struct ohash *h, unsigned int *pos)
172 0d6fb46a 2022-01-09 op {
173 0d6fb46a 2022-01-09 op 	*pos = 0;
174 0d6fb46a 2022-01-09 op 	return ohash_next(h, pos);
175 0d6fb46a 2022-01-09 op }
176 0d6fb46a 2022-01-09 op 
177 0d6fb46a 2022-01-09 op void *
178 0d6fb46a 2022-01-09 op ohash_next(struct ohash *h, unsigned int *pos)
179 0d6fb46a 2022-01-09 op {
180 0d6fb46a 2022-01-09 op 	for (; *pos < h->size; (*pos)++)
181 0d6fb46a 2022-01-09 op 		if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
182 0d6fb46a 2022-01-09 op 			return (void *)h->t[(*pos)++].p;
183 0d6fb46a 2022-01-09 op 	return NULL;
184 0d6fb46a 2022-01-09 op }
185 0d6fb46a 2022-01-09 op 
186 0d6fb46a 2022-01-09 op void
187 0d6fb46a 2022-01-09 op ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)
188 0d6fb46a 2022-01-09 op {
189 0d6fb46a 2022-01-09 op 	h->size = 1UL << size;
190 0d6fb46a 2022-01-09 op 	if (h->size < MINSIZE)
191 0d6fb46a 2022-01-09 op 		h->size = MINSIZE;
192 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
193 0d6fb46a 2022-01-09 op 	STAT_HASH_CREATION++;
194 0d6fb46a 2022-01-09 op 	STAT_HASH_SIZE += h->size;
195 0d6fb46a 2022-01-09 op #endif
196 0d6fb46a 2022-01-09 op 	/* Copy info so that caller may free it.  */
197 0d6fb46a 2022-01-09 op 	h->info.key_offset = info->key_offset;
198 0d6fb46a 2022-01-09 op 	h->info.calloc = info->calloc;
199 0d6fb46a 2022-01-09 op 	h->info.free = info->free;
200 0d6fb46a 2022-01-09 op 	h->info.alloc = info->alloc;
201 0d6fb46a 2022-01-09 op 	h->info.data = info->data;
202 0d6fb46a 2022-01-09 op 	h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
203 0d6fb46a 2022-01-09 op 		    h->info.data);
204 0d6fb46a 2022-01-09 op 	h->total = h->deleted = 0;
205 0d6fb46a 2022-01-09 op }
206 0d6fb46a 2022-01-09 op 
207 0d6fb46a 2022-01-09 op uint32_t
208 0d6fb46a 2022-01-09 op ohash_interval(const char *s, const char **e)
209 0d6fb46a 2022-01-09 op {
210 0d6fb46a 2022-01-09 op 	uint32_t k;
211 0d6fb46a 2022-01-09 op 
212 0d6fb46a 2022-01-09 op 	if (!*e)
213 0d6fb46a 2022-01-09 op 		*e = s + strlen(s);
214 0d6fb46a 2022-01-09 op 	if (s == *e)
215 0d6fb46a 2022-01-09 op 		k = 0;
216 0d6fb46a 2022-01-09 op 	else
217 0d6fb46a 2022-01-09 op 		k = *s++;
218 0d6fb46a 2022-01-09 op 	while (s != *e)
219 0d6fb46a 2022-01-09 op 		k =  ((k << 2) | (k >> 30)) ^ *s++;
220 0d6fb46a 2022-01-09 op 	return k;
221 0d6fb46a 2022-01-09 op }
222 0d6fb46a 2022-01-09 op 
223 0d6fb46a 2022-01-09 op unsigned int
224 0d6fb46a 2022-01-09 op ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
225 0d6fb46a 2022-01-09 op     uint32_t hv)
226 0d6fb46a 2022-01-09 op {
227 0d6fb46a 2022-01-09 op 	unsigned int	i, incr;
228 0d6fb46a 2022-01-09 op 	unsigned int	empty;
229 0d6fb46a 2022-01-09 op 
230 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
231 0d6fb46a 2022-01-09 op 	STAT_HASH_LOOKUP++;
232 0d6fb46a 2022-01-09 op #endif
233 0d6fb46a 2022-01-09 op 	empty = NONE;
234 0d6fb46a 2022-01-09 op 	i = hv % h->size;
235 0d6fb46a 2022-01-09 op 	incr = ((hv % (h->size-2)) & ~1) + 1;
236 0d6fb46a 2022-01-09 op 	while (h->t[i].p != NULL) {
237 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
238 0d6fb46a 2022-01-09 op 		STAT_HASH_LENGTH++;
239 0d6fb46a 2022-01-09 op #endif
240 0d6fb46a 2022-01-09 op 		if (h->t[i].p == DELETED) {
241 0d6fb46a 2022-01-09 op 			if (empty == NONE)
242 0d6fb46a 2022-01-09 op 				empty = i;
243 0d6fb46a 2022-01-09 op 		} else if (h->t[i].hv == hv &&
244 0d6fb46a 2022-01-09 op 		    strncmp(h->t[i].p+h->info.key_offset, start,
245 0d6fb46a 2022-01-09 op 			end - start) == 0 &&
246 0d6fb46a 2022-01-09 op 		    (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
247 0d6fb46a 2022-01-09 op 			if (empty != NONE) {
248 0d6fb46a 2022-01-09 op 				h->t[empty].hv = hv;
249 0d6fb46a 2022-01-09 op 				h->t[empty].p = h->t[i].p;
250 0d6fb46a 2022-01-09 op 				h->t[i].p = DELETED;
251 0d6fb46a 2022-01-09 op 				return empty;
252 0d6fb46a 2022-01-09 op 			} else {
253 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
254 0d6fb46a 2022-01-09 op 				STAT_HASH_POSITIVE++;
255 0d6fb46a 2022-01-09 op #endif
256 0d6fb46a 2022-01-09 op 				return i;
257 0d6fb46a 2022-01-09 op 			}
258 0d6fb46a 2022-01-09 op 		}
259 0d6fb46a 2022-01-09 op 		i += incr;
260 0d6fb46a 2022-01-09 op 		if (i >= h->size)
261 0d6fb46a 2022-01-09 op 			i -= h->size;
262 0d6fb46a 2022-01-09 op 	}
263 0d6fb46a 2022-01-09 op 
264 0d6fb46a 2022-01-09 op 	/* Found an empty position.  */
265 0d6fb46a 2022-01-09 op 	if (empty != NONE)
266 0d6fb46a 2022-01-09 op 		i = empty;
267 0d6fb46a 2022-01-09 op 	h->t[i].hv = hv;
268 0d6fb46a 2022-01-09 op 	return i;
269 0d6fb46a 2022-01-09 op }
270 0d6fb46a 2022-01-09 op 
271 0d6fb46a 2022-01-09 op unsigned int
272 0d6fb46a 2022-01-09 op ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
273 0d6fb46a 2022-01-09 op {
274 0d6fb46a 2022-01-09 op 	unsigned int	i, incr;
275 0d6fb46a 2022-01-09 op 	unsigned int	empty;
276 0d6fb46a 2022-01-09 op 
277 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
278 0d6fb46a 2022-01-09 op 	STAT_HASH_LOOKUP++;
279 0d6fb46a 2022-01-09 op #endif
280 0d6fb46a 2022-01-09 op 	empty = NONE;
281 0d6fb46a 2022-01-09 op 	i = hv % h->size;
282 0d6fb46a 2022-01-09 op 	incr = ((hv % (h->size-2)) & ~1) + 1;
283 0d6fb46a 2022-01-09 op 	while (h->t[i].p != NULL) {
284 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
285 0d6fb46a 2022-01-09 op 		STAT_HASH_LENGTH++;
286 0d6fb46a 2022-01-09 op #endif
287 0d6fb46a 2022-01-09 op 		if (h->t[i].p == DELETED) {
288 0d6fb46a 2022-01-09 op 			if (empty == NONE)
289 0d6fb46a 2022-01-09 op 				empty = i;
290 0d6fb46a 2022-01-09 op 		} else if (h->t[i].hv == hv &&
291 0d6fb46a 2022-01-09 op 		    memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
292 0d6fb46a 2022-01-09 op 			if (empty != NONE) {
293 0d6fb46a 2022-01-09 op 				h->t[empty].hv = hv;
294 0d6fb46a 2022-01-09 op 				h->t[empty].p = h->t[i].p;
295 0d6fb46a 2022-01-09 op 				h->t[i].p = DELETED;
296 0d6fb46a 2022-01-09 op 				return empty;
297 0d6fb46a 2022-01-09 op 			} else {
298 0d6fb46a 2022-01-09 op #ifdef STATS_HASH
299 0d6fb46a 2022-01-09 op 				STAT_HASH_POSITIVE++;
300 0d6fb46a 2022-01-09 op #endif
301 0d6fb46a 2022-01-09 op 			}	return i;
302 0d6fb46a 2022-01-09 op 		}
303 0d6fb46a 2022-01-09 op 		i += incr;
304 0d6fb46a 2022-01-09 op 		if (i >= h->size)
305 0d6fb46a 2022-01-09 op 			i -= h->size;
306 0d6fb46a 2022-01-09 op 	}
307 0d6fb46a 2022-01-09 op 
308 0d6fb46a 2022-01-09 op 	/* Found an empty position.  */
309 0d6fb46a 2022-01-09 op 	if (empty != NONE)
310 0d6fb46a 2022-01-09 op 		i = empty;
311 0d6fb46a 2022-01-09 op 	h->t[i].hv = hv;
312 0d6fb46a 2022-01-09 op 	return i;
313 0d6fb46a 2022-01-09 op }
314 0d6fb46a 2022-01-09 op 
315 0d6fb46a 2022-01-09 op unsigned int
316 0d6fb46a 2022-01-09 op ohash_qlookup(struct ohash *h, const char *s)
317 0d6fb46a 2022-01-09 op {
318 0d6fb46a 2022-01-09 op 	const char *e = NULL;
319 0d6fb46a 2022-01-09 op 	return ohash_qlookupi(h, s, &e);
320 0d6fb46a 2022-01-09 op }
321 0d6fb46a 2022-01-09 op 
322 0d6fb46a 2022-01-09 op unsigned int
323 0d6fb46a 2022-01-09 op ohash_qlookupi(struct ohash *h, const char *s, const char **e)
324 0d6fb46a 2022-01-09 op {
325 0d6fb46a 2022-01-09 op 	uint32_t hv;
326 0d6fb46a 2022-01-09 op 
327 0d6fb46a 2022-01-09 op 	hv = ohash_interval(s, e);
328 0d6fb46a 2022-01-09 op 	return ohash_lookup_interval(h, s, *e, hv);
329 0d6fb46a 2022-01-09 op }