1 /* $OpenBSD: ohash_do.c,v 1.4 2004/06/22 20:00:16 espie Exp $ */
5 /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 #include <sys/cdefs.h>
20 __FBSDID("$FreeBSD$");
22 #include "ohash_int.h"
24 static void ohash_resize(struct ohash *);
27 ohash_resize(struct ohash *h)
29 struct _ohash_record *n;
33 if (4 * h->deleted < h->total)
35 else if (3 * h->deleted > 2 * h->total)
43 STAT_HASH_SIZE += ns - h->size;
45 n = (h->info.halloc)(sizeof(struct _ohash_record) * ns, h->info.data);
49 for (j = 0; j < h->size; j++) {
50 if (h->t[j].p != NULL && h->t[j].p != DELETED) {
52 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
53 while (n[i].p != NULL) {
62 (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size,
66 h->total -= h->deleted;
71 ohash_remove(struct ohash *h, unsigned int i)
73 void *result = __DECONST(void *, h->t[i].p);
75 if (result == NULL || result == DELETED)
83 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
89 ohash_find(struct ohash *h, unsigned int i)
91 if (h->t[i].p == DELETED)
94 return __DECONST(void *, h->t[i].p);
98 ohash_insert(struct ohash *h, unsigned int i, void *p)
103 if (h->t[i].p == DELETED) {
108 /* Arbitrary resize boundary. Tweak if not efficient enough. */
109 if (++h->total * 4 > h->size * 3)