Home | History | Annotate | Line # | Download | only in lib 
      1 /* $OpenBSD: ohash_do.c,v 1.4 2004/06/22 20:00:16 espie Exp $ */
      2 /* ex:ts=8 sw=4:
      3  */
      4 
      5 /* Copyright (c) 1999, 2004 Marc Espie <espie (at) openbsd.org>
      6  *
      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.
     10  *
     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.
     18  */
     19 
     20 #include "ohash_int.h"
     21 
     22 static void ohash_resize(struct ohash *);
     23 
     24 static void
     25 ohash_resize(struct ohash *h)
     26 {
     27 	struct _ohash_record *n;
     28 	unsigned int 	ns, j;
     29 	unsigned int	i, incr;
     30 
     31 	if (4 * h->deleted < h->total)
     32 		ns = h->size << 1;
     33 	else if (3 * h->deleted > 2 * h->total)
     34 		ns = h->size >> 1;
     35 	else
     36 		ns = h->size;
     37 	if (ns < MINSIZE)
     38 		ns = MINSIZE;
     39 #ifdef STATS_HASH
     40 	STAT_HASH_EXPAND++;
     41 	STAT_HASH_SIZE += ns - h->size;
     42 #endif
     43 	n = (h->info.halloc)(sizeof(struct _ohash_record) * ns, h->info.data);
     44 	if (!n)
     45 		return;
     46 
     47 	for (j = 0; j < h->size; j++) {
     48 		if (h->t[j].p != NULL && h->t[j].p != DELETED) {
     49 			i = h->t[j].hv % ns;
     50 			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
     51 			while (n[i].p != NULL) {
     52 				i += incr;
     53 				if (i >= ns)
     54 					i -= ns;
     55 		    	}
     56 			n[i].hv = h->t[j].hv;
     57 			n[i].p = h->t[j].p;
     58 		}
     59 	}
     60 	(h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size,
     61 		h->info.data);
     62 	h->t = n;
     63 	h->size = ns;
     64 	h->total -= h->deleted;
     65 	h->deleted = 0;
     66 }
     67 
     68 void *
     69 ohash_remove(struct ohash *h, unsigned int i)
     70 {
     71 	void 		*result = __UNCONST(h->t[i].p);
     72 
     73 	if (result == NULL || result == DELETED)
     74 		return NULL;
     75 
     76 #ifdef STATS_HASH
     77 	STAT_HASH_ENTRIES--;
     78 #endif
     79 	h->t[i].p = DELETED;
     80 	h->deleted++;
     81 	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
     82 		ohash_resize(h);
     83 	return result;
     84 }
     85 
     86 void *
     87 ohash_find(struct ohash *h, unsigned int i)
     88 {
     89 	if (h->t[i].p == DELETED)
     90 		return NULL;
     91 	else
     92 		return __UNCONST(h->t[i].p);
     93 }
     94 
     95 void *
     96 ohash_insert(struct ohash *h, unsigned int i, void *p)
     97 {
     98 #ifdef STATS_HASH
     99 	STAT_HASH_ENTRIES++;
    100 #endif
    101 	if (h->t[i].p == DELETED) {
    102 		h->deleted--;
    103 		h->t[i].p = p;
    104 	} else {
    105 		h->t[i].p = p;
    106 	/* Arbitrary resize boundary.  Tweak if not efficient enough.  */
    107 		if (++h->total * 4 > h->size * 3)
    108 			ohash_resize(h);
    109 	}
    110     	return p;
    111 }
    112