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
  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 }