33 #define DELETED		((const char *)h)
34 #define NONE		(h->size)
64 ohash_delete(struct ohash *h)  in ohash_delete()  argument
66 	(h->info.free)(h->t, h->info.data);  in ohash_delete()
68 	h->t = NULL;  in ohash_delete()
73 ohash_resize(struct ohash *h)  in ohash_resize()  argument
80 	if (4 * h->deleted < h->total) {  in ohash_resize()
81 		if (h->size >= (UINT_MAX >> 1U))  in ohash_resize()
84 			ns = h->size << 1U;  in ohash_resize()
85 	} else if (3 * h->deleted > 2 * h->total)  in ohash_resize()
86 		ns = h->size >> 1U;  in ohash_resize()
88 		ns = h->size;  in ohash_resize()
93 	STAT_HASH_SIZE += ns - h->size;  in ohash_resize()
96 	n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);  in ohash_resize()
100 	for (j = 0; j < h->size; j++) {  in ohash_resize()
101 		if (h->t[j].p != NULL && h->t[j].p != DELETED) {  in ohash_resize()
102 			i = h->t[j].hv % ns;  in ohash_resize()
103 			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;  in ohash_resize()
109 			n[i].hv = h->t[j].hv;  in ohash_resize()
110 			n[i].p = h->t[j].p;  in ohash_resize()
113 	(h->info.free)(h->t, h->info.data);  in ohash_resize()
114 	h->t = n;  in ohash_resize()
115 	h->size = ns;  in ohash_resize()
116 	h->total -= h->deleted;  in ohash_resize()
117 	h->deleted = 0;  in ohash_resize()
121 ohash_remove(struct ohash *h, unsigned int i)  in ohash_remove()  argument
123 	void		*result = (void *)h->t[i].p;  in ohash_remove()
131 	h->t[i].p = DELETED;  in ohash_remove()
132 	h->deleted++;  in ohash_remove()
133 	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)  in ohash_remove()
134 		ohash_resize(h);  in ohash_remove()
139 ohash_find(struct ohash *h, unsigned int i)  in ohash_find()  argument
141 	if (h->t[i].p == DELETED)  in ohash_find()
144 		return (void *)h->t[i].p;  in ohash_find()
148 ohash_insert(struct ohash *h, unsigned int i, void *p)  in ohash_insert()  argument
153 	if (h->t[i].p == DELETED) {  in ohash_insert()
154 		h->deleted--;  in ohash_insert()
155 		h->t[i].p = p;  in ohash_insert()
157 		h->t[i].p = p;  in ohash_insert()
159 		if (++h->total * 4 > h->size * 3)  in ohash_insert()
160 			ohash_resize(h);  in ohash_insert()
166 ohash_entries(struct ohash *h)  in ohash_entries()  argument
168 	return h->total - h->deleted;  in ohash_entries()
172 ohash_first(struct ohash *h, unsigned int *pos)  in ohash_first()  argument
175 	return ohash_next(h, pos);  in ohash_first()
179 ohash_next(struct ohash *h, unsigned int *pos)  in ohash_next()  argument
181 	for (; *pos < h->size; (*pos)++)  in ohash_next()
182 		if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)  in ohash_next()
183 			return (void *)h->t[(*pos)++].p;  in ohash_next()
188 ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)  in ohash_init()  argument
190 	h->size = 1UL << size;  in ohash_init()
191 	if (h->size < MINSIZE)  in ohash_init()
192 		h->size = MINSIZE;  in ohash_init()
195 	STAT_HASH_SIZE += h->size;  in ohash_init()
198 	h->info.key_offset = info->key_offset;  in ohash_init()
199 	h->info.calloc = info->calloc;  in ohash_init()
200 	h->info.free = info->free;  in ohash_init()
201 	h->info.alloc = info->alloc;  in ohash_init()
202 	h->info.data = info->data;  in ohash_init()
203 	h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),  in ohash_init()
204 		    h->info.data);  in ohash_init()
205 	h->total = h->deleted = 0;  in ohash_init()
225 ohash_lookup_interval(struct ohash *h, const char *start, const char *end,  in ohash_lookup_interval()  argument
235 	i = hv % h->size;  in ohash_lookup_interval()
236 	incr = ((hv % (h->size-2)) & ~1) + 1;  in ohash_lookup_interval()
237 	while (h->t[i].p != NULL) {  in ohash_lookup_interval()
241 		if (h->t[i].p == DELETED) {  in ohash_lookup_interval()
244 		} else if (h->t[i].hv == hv &&  in ohash_lookup_interval()
245 		    strncmp(h->t[i].p+h->info.key_offset, start,  in ohash_lookup_interval()
247 		    (h->t[i].p+h->info.key_offset)[end-start] == '\0') {  in ohash_lookup_interval()
249 				h->t[empty].hv = hv;  in ohash_lookup_interval()
250 				h->t[empty].p = h->t[i].p;  in ohash_lookup_interval()
251 				h->t[i].p = DELETED;  in ohash_lookup_interval()
261 		if (i >= h->size)  in ohash_lookup_interval()
262 			i -= h->size;  in ohash_lookup_interval()
268 	h->t[i].hv = hv;  in ohash_lookup_interval()
273 ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)  in ohash_lookup_memory()  argument
282 	i = hv % h->size;  in ohash_lookup_memory()
283 	incr = ((hv % (h->size-2)) & ~1) + 1;  in ohash_lookup_memory()
284 	while (h->t[i].p != NULL) {  in ohash_lookup_memory()
288 		if (h->t[i].p == DELETED) {  in ohash_lookup_memory()
291 		} else if (h->t[i].hv == hv &&  in ohash_lookup_memory()
292 		    memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {  in ohash_lookup_memory()
294 				h->t[empty].hv = hv;  in ohash_lookup_memory()
295 				h->t[empty].p = h->t[i].p;  in ohash_lookup_memory()
296 				h->t[i].p = DELETED;  in ohash_lookup_memory()
305 		if (i >= h->size)  in ohash_lookup_memory()
306 			i -= h->size;  in ohash_lookup_memory()
312 	h->t[i].hv = hv;  in ohash_lookup_memory()
317 ohash_qlookup(struct ohash *h, const char *s)  in ohash_qlookup()  argument
320 	return ohash_qlookupi(h, s, &e);  in ohash_qlookup()
324 ohash_qlookupi(struct ohash *h, const char *s, const char **e)  in ohash_qlookupi()  argument
329 	return ohash_lookup_interval(h, s, *e, hv);  in ohash_qlookupi()