x2p/hash.c

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