x2p/hash.c

   1 /*    hash.c
   2  *
   3  *    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1999, 2000, 2001, 2002,
   4  *    2005 by Larry Wall and others
   5  *
   6  *    You may distribute under the terms of either the GNU General Public
   7  *    License or the Artistic License, as specified in the README file.
   8  */
   9
  10 #include <stdio.h>
  11 #include "EXTERN.h"
  12 #include "a2p.h"
  13 #include "util.h"
  14
  15 #ifdef NETWARE
  16 char *savestr(char *str);
  17 #endif
  18
  19 STR *
  20 hfetch(register HASH *tb, char *key)
  21 {
  22     register char *s;
  23     register int i;
  24     register int hash;
  25     register HENT *entry;
  26
  27     if (!tb)
  28         return NULL;
  29     for (s=key,         i=0,    hash = 0;
  30       /* while */ *s;
  31          s++,           i++,    hash *= 5) {
  32         hash += *s * coeff[i];
  33     }
  34     entry = tb->tbl_array[hash & tb->tbl_max];
  35     for (; entry; entry = entry->hent_next) {
  36         if (entry->hent_hash != hash)           /* strings can't be equal */
  37             continue;
  38         if (strNE(entry->hent_key,key)) /* is this it? */
  39             continue;
  40         return entry->hent_val;
  41     }
  42     return NULL;
  43 }
  44
  45 bool
  46 hstore(register HASH *tb, char *key, STR *val)
  47 {
  48     register char *s;
  49     register int i;
  50     register int hash;
  51     register HENT *entry;
  52     register HENT **oentry;
  53
  54     if (!tb)
  55         return FALSE;
  56     for (s=key,         i=0,    hash = 0;
  57       /* while */ *s;
  58          s++,           i++,    hash *= 5) {
  59         hash += *s * coeff[i];
  60     }
  61
  62     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  63     i = 1;
  64
  65     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  66         if (entry->hent_hash != hash)           /* strings can't be equal */
  67             continue;
  68         if (strNE(entry->hent_key,key)) /* is this it? */
  69             continue;
  70         /*NOSTRICT*/
  71         safefree(entry->hent_val);
  72         entry->hent_val = val;
  73         return TRUE;
  74     }
  75     /*NOSTRICT*/
  76     entry = (HENT*) safemalloc(sizeof(HENT));
  77
  78     entry->hent_key = savestr(key);
  79     entry->hent_val = val;
  80     entry->hent_hash = hash;
  81     entry->hent_next = *oentry;
  82     *oentry = entry;
  83
  84     if (i) {                            /* initial entry? */
  85         tb->tbl_fill++;
  86         if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  87             hsplit(tb);
  88     }
  89
  90     return FALSE;
  91 }
  92
  93 void
  94 hsplit(HASH *tb)
  95 {
  96     const int oldsize = tb->tbl_max + 1;
  97     register int newsize = oldsize * 2;
  98     register int i;
  99     register HENT **a;
 100     register HENT **b;
 101     register HENT *entry;
 102     register HENT **oentry;
 103
 104     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
 105     memset(&a[oldsize], 0, oldsize * sizeof(HENT*)); /* zero second half */
 106     tb->tbl_max = --newsize;
 107     tb->tbl_array = a;
 108
 109     for (i=0; i<oldsize; i++,a++) {
 110         if (!*a)                                /* non-existent */
 111             continue;
 112         b = a+oldsize;
 113         for (oentry = a, entry = *a; entry; entry = *oentry) {
 114             if ((entry->hent_hash & newsize) != i) {
 115                 *oentry = entry->hent_next;
 116                 entry->hent_next = *b;
 117                 if (!*b)
 118                     tb->tbl_fill++;
 119                 *b = entry;
 120                 continue;
 121             }
 122             else
 123                 oentry = &entry->hent_next;
 124         }
 125         if (!*a)                                /* everything moved */
 126             tb->tbl_fill--;
 127     }
 128 }
 129
 130 HASH *
 131 hnew(void)
 132 {
 133     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
 134
 135     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
 136     tb->tbl_fill = 0;
 137     tb->tbl_max = 7;
 138     hiterinit(tb);      /* so each() will start off right */
 139     memset(tb->tbl_array, 0, 8 * sizeof(HENT*));
 140     return tb;
 141 }
 142
 143 int
 144 hiterinit(register HASH *tb)
 145 {
 146     tb->tbl_riter = -1;
 147     tb->tbl_eiter = Null(HENT*);
 148     return tb->tbl_fill;
 149 }