op public repos

Blame

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