31 #define DELETED		((const char *)h)
32 #define NONE		(h->size)
62 ohash_delete(struct ohash *h)  in ohash_delete()  argument
64 	(h->info.free)(h->t, h->info.data);  in ohash_delete()
66 	h->t = NULL;  in ohash_delete()
71 ohash_resize(struct ohash *h)  in ohash_resize()  argument
78 	if (4 * h->deleted < h->total) {  in ohash_resize()
79 		if (h->size >= (UINT_MAX >> 1U))  in ohash_resize()
82 			ns = h->size << 1U;  in ohash_resize()
83 	} else if (3 * h->deleted > 2 * h->total)  in ohash_resize()
84 		ns = h->size >> 1U;  in ohash_resize()
86 		ns = h->size;  in ohash_resize()
91 	STAT_HASH_SIZE += ns - h->size;  in ohash_resize()
94 	n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);  in ohash_resize()
98 	for (j = 0; j < h->size; j++) {  in ohash_resize()
99 		if (h->t[j].p != NULL && h->t[j].p != DELETED) {  in ohash_resize()
100 			i = h->t[j].hv % ns;  in ohash_resize()
101 			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;  in ohash_resize()
107 			n[i].hv = h->t[j].hv;  in ohash_resize()
108 			n[i].p = h->t[j].p;  in ohash_resize()
111 	(h->info.free)(h->t, h->info.data);  in ohash_resize()
112 	h->t = n;  in ohash_resize()
113 	h->size = ns;  in ohash_resize()
114 	h->total -= h->deleted;  in ohash_resize()
115 	h->deleted = 0;  in ohash_resize()
119 ohash_remove(struct ohash *h, unsigned int i)  in ohash_remove()  argument
121 	void		*result = (void *)h->t[i].p;  in ohash_remove()
129 	h->t[i].p = DELETED;  in ohash_remove()
130 	h->deleted++;  in ohash_remove()
131 	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)  in ohash_remove()
132 		ohash_resize(h);  in ohash_remove()
137 ohash_find(struct ohash *h, unsigned int i)  in ohash_find()  argument
139 	if (h->t[i].p == DELETED)  in ohash_find()
142 		return (void *)h->t[i].p;  in ohash_find()
146 ohash_insert(struct ohash *h, unsigned int i, void *p)  in ohash_insert()  argument
151 	if (h->t[i].p == DELETED) {  in ohash_insert()
152 		h->deleted--;  in ohash_insert()
153 		h->t[i].p = p;  in ohash_insert()
155 		h->t[i].p = p;  in ohash_insert()
157 		if (++h->total * 4 > h->size * 3)  in ohash_insert()
158 			ohash_resize(h);  in ohash_insert()
164 ohash_entries(struct ohash *h)  in ohash_entries()  argument
166 	return h->total - h->deleted;  in ohash_entries()
170 ohash_first(struct ohash *h, unsigned int *pos)  in ohash_first()  argument
173 	return ohash_next(h, pos);  in ohash_first()
177 ohash_next(struct ohash *h, unsigned int *pos)  in ohash_next()  argument
179 	for (; *pos < h->size; (*pos)++)  in ohash_next()
180 		if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)  in ohash_next()
181 			return (void *)h->t[(*pos)++].p;  in ohash_next()
186 ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)  in ohash_init()  argument
188 	h->size = 1UL << size;  in ohash_init()
189 	if (h->size < MINSIZE)  in ohash_init()
190 		h->size = MINSIZE;  in ohash_init()
193 	STAT_HASH_SIZE += h->size;  in ohash_init()
196 	h->info.key_offset = info->key_offset;  in ohash_init()
197 	h->info.calloc = info->calloc;  in ohash_init()
198 	h->info.free = info->free;  in ohash_init()
199 	h->info.alloc = info->alloc;  in ohash_init()
200 	h->info.data = info->data;  in ohash_init()
201 	h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),  in ohash_init()
202 		    h->info.data);  in ohash_init()
203 	h->total = h->deleted = 0;  in ohash_init()
223 ohash_lookup_interval(struct ohash *h, const char *start, const char *end,  in ohash_lookup_interval()  argument
233 	i = hv % h->size;  in ohash_lookup_interval()
234 	incr = ((hv % (h->size-2)) & ~1) + 1;  in ohash_lookup_interval()
235 	while (h->t[i].p != NULL) {  in ohash_lookup_interval()
239 		if (h->t[i].p == DELETED) {  in ohash_lookup_interval()
242 		} else if (h->t[i].hv == hv &&  in ohash_lookup_interval()
243 		    strncmp(h->t[i].p+h->info.key_offset, start,  in ohash_lookup_interval()
245 		    (h->t[i].p+h->info.key_offset)[end-start] == '\0') {  in ohash_lookup_interval()
247 				h->t[empty].hv = hv;  in ohash_lookup_interval()
248 				h->t[empty].p = h->t[i].p;  in ohash_lookup_interval()
249 				h->t[i].p = DELETED;  in ohash_lookup_interval()
259 		if (i >= h->size)  in ohash_lookup_interval()
260 			i -= h->size;  in ohash_lookup_interval()
266 	h->t[i].hv = hv;  in ohash_lookup_interval()
271 ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)  in ohash_lookup_memory()  argument
280 	i = hv % h->size;  in ohash_lookup_memory()
281 	incr = ((hv % (h->size-2)) & ~1) + 1;  in ohash_lookup_memory()
282 	while (h->t[i].p != NULL) {  in ohash_lookup_memory()
286 		if (h->t[i].p == DELETED) {  in ohash_lookup_memory()
289 		} else if (h->t[i].hv == hv &&  in ohash_lookup_memory()
290 		    memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {  in ohash_lookup_memory()
292 				h->t[empty].hv = hv;  in ohash_lookup_memory()
293 				h->t[empty].p = h->t[i].p;  in ohash_lookup_memory()
294 				h->t[i].p = DELETED;  in ohash_lookup_memory()
303 		if (i >= h->size)  in ohash_lookup_memory()
304 			i -= h->size;  in ohash_lookup_memory()
310 	h->t[i].hv = hv;  in ohash_lookup_memory()
315 ohash_qlookup(struct ohash *h, const char *s)  in ohash_qlookup()  argument
318 	return ohash_qlookupi(h, s, &e);  in ohash_qlookup()
322 ohash_qlookupi(struct ohash *h, const char *s, const char **e)  in ohash_qlookupi()  argument
327 	return ohash_lookup_interval(h, s, *e, hv);  in ohash_qlookupi()