1228063Sbapt/* $OpenBSD: ohash_do.c,v 1.4 2004/06/22 20:00:16 espie Exp $ */ 2228063Sbapt/* ex:ts=8 sw=4: 3228063Sbapt */ 4228063Sbapt 5228063Sbapt/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org> 6228063Sbapt * 7228063Sbapt * Permission to use, copy, modify, and distribute this software for any 8228063Sbapt * purpose with or without fee is hereby granted, provided that the above 9228063Sbapt * copyright notice and this permission notice appear in all copies. 10228063Sbapt * 11228063Sbapt * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12228063Sbapt * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13228063Sbapt * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14228063Sbapt * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15228063Sbapt * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16228063Sbapt * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17228063Sbapt * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18228063Sbapt */ 19228063Sbapt#include <sys/cdefs.h> 20228063Sbapt__FBSDID("$FreeBSD$"); 21228063Sbapt 22228063Sbapt#include "ohash_int.h" 23228063Sbapt 24228063Sbaptstatic void ohash_resize(struct ohash *); 25228063Sbapt 26228063Sbaptstatic void 27228063Sbaptohash_resize(struct ohash *h) 28228063Sbapt{ 29228063Sbapt struct _ohash_record *n; 30228063Sbapt unsigned int ns, j; 31228063Sbapt unsigned int i, incr; 32228063Sbapt 33228063Sbapt if (4 * h->deleted < h->total) 34228063Sbapt ns = h->size << 1; 35228063Sbapt else if (3 * h->deleted > 2 * h->total) 36228063Sbapt ns = h->size >> 1; 37228063Sbapt else 38228063Sbapt ns = h->size; 39228063Sbapt if (ns < MINSIZE) 40228063Sbapt ns = MINSIZE; 41228063Sbapt#ifdef STATS_HASH 42228063Sbapt STAT_HASH_EXPAND++; 43228063Sbapt STAT_HASH_SIZE += ns - h->size; 44228063Sbapt#endif 45228063Sbapt n = (h->info.halloc)(sizeof(struct _ohash_record) * ns, h->info.data); 46228063Sbapt if (!n) 47228063Sbapt return; 48228063Sbapt 49228063Sbapt for (j = 0; j < h->size; j++) { 50228063Sbapt if (h->t[j].p != NULL && h->t[j].p != DELETED) { 51228063Sbapt i = h->t[j].hv % ns; 52228063Sbapt incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; 53228063Sbapt while (n[i].p != NULL) { 54228063Sbapt i += incr; 55228063Sbapt if (i >= ns) 56228063Sbapt i -= ns; 57228063Sbapt } 58228063Sbapt n[i].hv = h->t[j].hv; 59228063Sbapt n[i].p = h->t[j].p; 60228063Sbapt } 61228063Sbapt } 62228063Sbapt (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size, 63228063Sbapt h->info.data); 64228063Sbapt h->t = n; 65228063Sbapt h->size = ns; 66228063Sbapt h->total -= h->deleted; 67228063Sbapt h->deleted = 0; 68228063Sbapt} 69228063Sbapt 70228063Sbaptvoid * 71228063Sbaptohash_remove(struct ohash *h, unsigned int i) 72228063Sbapt{ 73228063Sbapt void *result = __DECONST(void *, h->t[i].p); 74228063Sbapt 75228063Sbapt if (result == NULL || result == DELETED) 76228063Sbapt return NULL; 77228063Sbapt 78228063Sbapt#ifdef STATS_HASH 79228063Sbapt STAT_HASH_ENTRIES--; 80228063Sbapt#endif 81228063Sbapt h->t[i].p = DELETED; 82228063Sbapt h->deleted++; 83228063Sbapt if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) 84228063Sbapt ohash_resize(h); 85228063Sbapt return result; 86228063Sbapt} 87228063Sbapt 88228063Sbaptvoid * 89228063Sbaptohash_find(struct ohash *h, unsigned int i) 90228063Sbapt{ 91228063Sbapt if (h->t[i].p == DELETED) 92228063Sbapt return NULL; 93228063Sbapt else 94228063Sbapt return __DECONST(void *, h->t[i].p); 95228063Sbapt} 96228063Sbapt 97228063Sbaptvoid * 98228063Sbaptohash_insert(struct ohash *h, unsigned int i, void *p) 99228063Sbapt{ 100228063Sbapt#ifdef STATS_HASH 101228063Sbapt STAT_HASH_ENTRIES++; 102228063Sbapt#endif 103228063Sbapt if (h->t[i].p == DELETED) { 104228063Sbapt h->deleted--; 105228063Sbapt h->t[i].p = p; 106228063Sbapt } else { 107228063Sbapt h->t[i].p = p; 108228063Sbapt /* Arbitrary resize boundary. Tweak if not efficient enough. */ 109228063Sbapt if (++h->total * 4 > h->size * 3) 110228063Sbapt ohash_resize(h); 111228063Sbapt } 112228063Sbapt return p; 113228063Sbapt} 114