usr.bin/m4/lib/ohash_do.c

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