x2p/hash.c

   1 /* $Header: hash.c,v 1.0 87/12/18 13:07:18 root Exp $
   2  *
   3  * $Log:        hash.c,v $
   4  * Revision 1.0  87/12/18  13:07:18  root
   5  * Initial revision
   6  *
   7  */
   8
   9 #include <stdio.h>
  10 #include "EXTERN.h"
  11 #include "handy.h"
  12 #include "util.h"
  13 #include "a2p.h"
  14
  15 STR *
  16 hfetch(tb,key)
  17 register HASH *tb;
  18 char *key;
  19 {
  20     register char *s;
  21     register int i;
  22     register int hash;
  23     register HENT *entry;
  24
  25     if (!tb)
  26         return Nullstr;
  27     for (s=key,         i=0,    hash = 0;
  28       /* while */ *s;
  29          s++,           i++,    hash *= 5) {
  30         hash += *s * coeff[i];
  31     }
  32     entry = tb->tbl_array[hash & tb->tbl_max];
  33     for (; entry; entry = entry->hent_next) {
  34         if (entry->hent_hash != hash)           /* strings can't be equal */
  35             continue;
  36         if (strNE(entry->hent_key,key)) /* is this it? */
  37             continue;
  38         return entry->hent_val;
  39     }
  40     return Nullstr;
  41 }
  42
  43 bool
  44 hstore(tb,key,val)
  45 register HASH *tb;
  46 char *key;
  47 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         safefree((char*)entry->hent_val);
  72         entry->hent_val = val;
  73         return TRUE;
  74     }
  75     entry = (HENT*) safemalloc(sizeof(HENT));
  76
  77     entry->hent_key = savestr(key);
  78     entry->hent_val = val;
  79     entry->hent_hash = hash;
  80     entry->hent_next = *oentry;
  81     *oentry = entry;
  82
  83     if (i) {                            /* initial entry? */
  84         tb->tbl_fill++;
  85         if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  86             hsplit(tb);
  87     }
  88
  89     return FALSE;
  90 }
  91
  92 #ifdef NOTUSED
  93 bool
  94 hdelete(tb,key)
  95 register HASH *tb;
  96 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 hsplit(tb)
 133 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     bzero((char*)&a[oldsize], 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()
 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     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
 179     return tb;
 180 }
 181
 182 #ifdef NOTUSED
 183 hshow(tb)
 184 register HASH *tb;
 185 {
 186     fprintf(stderr,"%5d %4d (%2d%%)\n",
 187         tb->tbl_max+1,
 188         tb->tbl_fill,
 189         tb->tbl_fill * 100 / (tb->tbl_max+1));
 190 }
 191 #endif
 192
 193 hiterinit(tb)
 194 register HASH *tb;
 195 {
 196     tb->tbl_riter = -1;
 197     tb->tbl_eiter = Null(HENT*);
 198     return tb->tbl_fill;
 199 }
 200
 201 HENT *
 202 hiternext(tb)
 203 register HASH *tb;
 204 {
 205     register HENT *entry;
 206
 207     entry = tb->tbl_eiter;
 208     do {
 209         if (entry)
 210             entry = entry->hent_next;
 211         if (!entry) {
 212             tb->tbl_riter++;
 213             if (tb->tbl_riter > tb->tbl_max) {
 214                 tb->tbl_riter = -1;
 215                 break;
 216             }
 217             entry = tb->tbl_array[tb->tbl_riter];
 218         }
 219     } while (!entry);
 220
 221     tb->tbl_eiter = entry;
 222     return entry;
 223 }
 224
 225 char *
 226 hiterkey(entry)
 227 register HENT *entry;
 228 {
 229     return entry->hent_key;
 230 }
 231
 232 STR *
 233 hiterval(entry)
 234 register HENT *entry;
 235 {
 236     return entry->hent_val;
 237 }