x2p/hash.c

   1 /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:29:20 $
   2  *
   3  *    Copyright (c) 1991-1997, Larry Wall
   4  *
   5  *    You may distribute under the terms of either the GNU General Public
   6  *    License or the Artistic License, as specified in the README file.
   7  *
   8  * $Log:        hash.c,v $
   9  */
  10
  11 #include <stdio.h>
  12 #include "EXTERN.h"
  13 #include "a2p.h"
  14 #include "util.h"
  15
  16 STR *
  17 hfetch(register HASH *tb, char *key)
  18 {
  19     register char *s;
  20     register int i;
  21     register int hash;
  22     register HENT *entry;
  23
  24     if (!tb)
  25         return Nullstr;
  26     for (s=key,         i=0,    hash = 0;
  27       /* while */ *s;
  28          s++,           i++,    hash *= 5) {
  29         hash += *s * coeff[i];
  30     }
  31     entry = tb->tbl_array[hash & tb->tbl_max];
  32     for (; entry; entry = entry->hent_next) {
  33         if (entry->hent_hash != hash)           /* strings can't be equal */
  34             continue;
  35         if (strNE(entry->hent_key,key)) /* is this it? */
  36             continue;
  37         return entry->hent_val;
  38     }
  39     return Nullstr;
  40 }
  41
  42 bool
  43 hstore(register HASH *tb, char *key, STR *val)
  44 {
  45     register char *s;
  46     register int i;
  47     register int hash;
  48     register HENT *entry;
  49     register HENT **oentry;
  50
  51     if (!tb)
  52         return FALSE;
  53     for (s=key,         i=0,    hash = 0;
  54       /* while */ *s;
  55          s++,           i++,    hash *= 5) {
  56         hash += *s * coeff[i];
  57     }
  58
  59     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  60     i = 1;
  61
  62     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  63         if (entry->hent_hash != hash)           /* strings can't be equal */
  64             continue;
  65         if (strNE(entry->hent_key,key)) /* is this it? */
  66             continue;
  67         /*NOSTRICT*/
  68         Safefree(entry->hent_val);
  69         entry->hent_val = val;
  70         return TRUE;
  71     }
  72     /*NOSTRICT*/
  73     entry = (HENT*) safemalloc(sizeof(HENT));
  74
  75     entry->hent_key = savestr(key);
  76     entry->hent_val = val;
  77     entry->hent_hash = hash;
  78     entry->hent_next = *oentry;
  79     *oentry = entry;
  80
  81     if (i) {                            /* initial entry? */
  82         tb->tbl_fill++;
  83         if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  84             hsplit(tb);
  85     }
  86
  87     return FALSE;
  88 }
  89
  90 #ifdef NOTUSED
  91 bool
  92 hdelete(tb,key)
  93 register HASH *tb;
  94 char *key;
  95 {
  96     register char *s;
  97     register int i;
  98     register int hash;
  99     register HENT *entry;
 100     register HENT **oentry;
 101
 102     if (!tb)
 103         return FALSE;
 104     for (s=key,         i=0,    hash = 0;
 105       /* while */ *s;
 106          s++,           i++,    hash *= 5) {
 107         hash += *s * coeff[i];
 108     }
 109
 110     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
 111     entry = *oentry;
 112     i = 1;
 113     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
 114         if (entry->hent_hash != hash)           /* strings can't be equal */
 115             continue;
 116         if (strNE(entry->hent_key,key)) /* is this it? */
 117             continue;
 118         safefree((char*)entry->hent_val);
 119         safefree(entry->hent_key);
 120         *oentry = entry->hent_next;
 121         safefree((char*)entry);
 122         if (i)
 123             tb->tbl_fill--;
 124         return TRUE;
 125     }
 126     return FALSE;
 127 }
 128 #endif
 129
 130 void
 131 hsplit(HASH *tb)
 132 {
 133     int oldsize = tb->tbl_max + 1;
 134     register int newsize = oldsize * 2;
 135     register int i;
 136     register HENT **a;
 137     register HENT **b;
 138     register HENT *entry;
 139     register HENT **oentry;
 140
 141     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
 142     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
 143     tb->tbl_max = --newsize;
 144     tb->tbl_array = a;
 145
 146     for (i=0; i<oldsize; i++,a++) {
 147         if (!*a)                                /* non-existent */
 148             continue;
 149         b = a+oldsize;
 150         for (oentry = a, entry = *a; entry; entry = *oentry) {
 151             if ((entry->hent_hash & newsize) != i) {
 152                 *oentry = entry->hent_next;
 153                 entry->hent_next = *b;
 154                 if (!*b)
 155                     tb->tbl_fill++;
 156                 *b = entry;
 157                 continue;
 158             }
 159             else
 160                 oentry = &entry->hent_next;
 161         }
 162         if (!*a)                                /* everything moved */
 163             tb->tbl_fill--;
 164     }
 165 }
 166
 167 HASH *
 168 hnew(void)
 169 {
 170     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
 171
 172     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
 173     tb->tbl_fill = 0;
 174     tb->tbl_max = 7;
 175     hiterinit(tb);      /* so each() will start off right */
 176     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
 177     return tb;
 178 }
 179
 180 #ifdef NOTUSED
 181 hshow(tb)
 182 register HASH *tb;
 183 {
 184     fprintf(stderr,"%5d %4d (%2d%%)\n",
 185         tb->tbl_max+1,
 186         tb->tbl_fill,
 187         tb->tbl_fill * 100 / (tb->tbl_max+1));
 188 }
 189 #endif
 190
 191 int
 192 hiterinit(register HASH *tb)
 193 {
 194     tb->tbl_riter = -1;
 195     tb->tbl_eiter = Null(HENT*);
 196     return tb->tbl_fill;
 197 }
 198
 199 HENT *
 200 hiternext(register HASH *tb)
 201 {
 202     register HENT *entry;
 203
 204     entry = tb->tbl_eiter;
 205     do {
 206         if (entry)
 207             entry = entry->hent_next;
 208         if (!entry) {
 209             tb->tbl_riter++;
 210             if (tb->tbl_riter > tb->tbl_max) {
 211                 tb->tbl_riter = -1;
 212                 break;
 213             }
 214             entry = tb->tbl_array[tb->tbl_riter];
 215         }
 216     } while (!entry);
 217
 218     tb->tbl_eiter = entry;
 219     return entry;
 220 }
 221
 222 char *
 223 hiterkey(register HENT *entry)
 224 {
 225     return entry->hent_key;
 226 }
 227
 228 STR *
 229 hiterval(register HENT *entry)
 230 {
 231     return entry->hent_val;
 232 }