hash.c

   1 /* $Header: hash.c,v 2.0 88/06/05 00:09:06 root Exp $
   2  *
   3  * $Log:        hash.c,v $
   4  * Revision 2.0  88/06/05  00:09:06  root
   5  * Baseline version 2.0.
   6  *
   7  */
   8
   9 #include "EXTERN.h"
  10 #include "perl.h"
  11
  12 STR *
  13 hfetch(tb,key)
  14 register HASH *tb;
  15 char *key;
  16 {
  17     register char *s;
  18     register int i;
  19     register int hash;
  20     register HENT *entry;
  21
  22     if (!tb)
  23         return Nullstr;
  24     for (s=key,         i=0,    hash = 0;
  25       /* while */ *s && i < COEFFSIZE;
  26          s++,           i++,    hash *= 5) {
  27         hash += *s * coeff[i];
  28     }
  29     entry = tb->tbl_array[hash & tb->tbl_max];
  30     for (; entry; entry = entry->hent_next) {
  31         if (entry->hent_hash != hash)           /* strings can't be equal */
  32             continue;
  33         if (strNE(entry->hent_key,key)) /* is this it? */
  34             continue;
  35         return entry->hent_val;
  36     }
  37     return Nullstr;
  38 }
  39
  40 bool
  41 hstore(tb,key,val)
  42 register HASH *tb;
  43 char *key;
  44 STR *val;
  45 {
  46     register char *s;
  47     register int i;
  48     register int hash;
  49     register HENT *entry;
  50     register HENT **oentry;
  51
  52     if (!tb)
  53         return FALSE;
  54     for (s=key,         i=0,    hash = 0;
  55       /* while */ *s && i < COEFFSIZE;
  56          s++,           i++,    hash *= 5) {
  57         hash += *s * coeff[i];
  58     }
  59
  60     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  61     i = 1;
  62
  63     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  64         if (entry->hent_hash != hash)           /* strings can't be equal */
  65             continue;
  66         if (strNE(entry->hent_key,key)) /* is this it? */
  67             continue;
  68         safefree((char*)entry->hent_val);
  69         entry->hent_val = val;
  70         return TRUE;
  71     }
  72     entry = (HENT*) safemalloc(sizeof(HENT));
  73
  74     entry->hent_key = savestr(key);
  75     entry->hent_val = val;
  76     entry->hent_hash = hash;
  77     entry->hent_next = *oentry;
  78     *oentry = entry;
  79
  80     if (i) {                            /* initial entry? */
  81         tb->tbl_fill++;
  82         if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  83             hsplit(tb);
  84     }
  85
  86     return FALSE;
  87 }
  88
  89 STR *
  90 hdelete(tb,key)
  91 register HASH *tb;
  92 char *key;
  93 {
  94     register char *s;
  95     register int i;
  96     register int hash;
  97     register HENT *entry;
  98     register HENT **oentry;
  99     STR *str;
 100
 101     if (!tb)
 102         return Nullstr;
 103     for (s=key,         i=0,    hash = 0;
 104       /* while */ *s && i < COEFFSIZE;
 105          s++,           i++,    hash *= 5) {
 106         hash += *s * coeff[i];
 107     }
 108
 109     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
 110     entry = *oentry;
 111     i = 1;
 112     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
 113         if (entry->hent_hash != hash)           /* strings can't be equal */
 114             continue;
 115         if (strNE(entry->hent_key,key)) /* is this it? */
 116             continue;
 117         *oentry = entry->hent_next;
 118         str = str_static(entry->hent_val);
 119         hentfree(entry);
 120         if (i)
 121             tb->tbl_fill--;
 122         return str;
 123     }
 124     return Nullstr;
 125 }
 126
 127 hsplit(tb)
 128 HASH *tb;
 129 {
 130     int oldsize = tb->tbl_max + 1;
 131     register int newsize = oldsize * 2;
 132     register int i;
 133     register HENT **a;
 134     register HENT **b;
 135     register HENT *entry;
 136     register HENT **oentry;
 137
 138     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
 139     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
 140     tb->tbl_max = --newsize;
 141     tb->tbl_array = a;
 142
 143     for (i=0; i<oldsize; i++,a++) {
 144         if (!*a)                                /* non-existent */
 145             continue;
 146         b = a+oldsize;
 147         for (oentry = a, entry = *a; entry; entry = *oentry) {
 148             if ((entry->hent_hash & newsize) != i) {
 149                 *oentry = entry->hent_next;
 150                 entry->hent_next = *b;
 151                 if (!*b)
 152                     tb->tbl_fill++;
 153                 *b = entry;
 154                 continue;
 155             }
 156             else
 157                 oentry = &entry->hent_next;
 158         }
 159         if (!*a)                                /* everything moved */
 160             tb->tbl_fill--;
 161     }
 162 }
 163
 164 HASH *
 165 hnew()
 166 {
 167     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
 168
 169     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
 170     tb->tbl_fill = 0;
 171     tb->tbl_max = 7;
 172     hiterinit(tb);      /* so each() will start off right */
 173     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
 174     return tb;
 175 }
 176
 177 void
 178 hentfree(hent)
 179 register HENT *hent;
 180 {
 181     if (!hent)
 182         return;
 183     str_free(hent->hent_val);
 184     safefree(hent->hent_key);
 185     safefree((char*)hent);
 186 }
 187
 188 void
 189 hclear(tb)
 190 register HASH *tb;
 191 {
 192     register HENT *hent;
 193     register HENT *ohent = Null(HENT*);
 194
 195     if (!tb)
 196         return;
 197     hiterinit(tb);
 198     while (hent = hiternext(tb)) {      /* concise but not very efficient */
 199         hentfree(ohent);
 200         ohent = hent;
 201     }
 202     hentfree(ohent);
 203     tb->tbl_fill = 0;
 204     bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
 205 }
 206
 207 #ifdef NOTUSED
 208 void
 209 hfree(tb)
 210 HASH *tb;
 211 {
 212     if (!tb)
 213         return
 214     hiterinit(tb);
 215     while (hent = hiternext(tb)) {
 216         hentfree(ohent);
 217         ohent = hent;
 218     }
 219     hentfree(ohent);
 220     safefree((char*)tb->tbl_array);
 221     safefree((char*)tb);
 222 }
 223 #endif
 224
 225 #ifdef NOTUSED
 226 hshow(tb)
 227 register HASH *tb;
 228 {
 229     fprintf(stderr,"%5d %4d (%2d%%)\n",
 230         tb->tbl_max+1,
 231         tb->tbl_fill,
 232         tb->tbl_fill * 100 / (tb->tbl_max+1));
 233 }
 234 #endif
 235
 236 hiterinit(tb)
 237 register HASH *tb;
 238 {
 239     tb->tbl_riter = -1;
 240     tb->tbl_eiter = Null(HENT*);
 241     return tb->tbl_fill;
 242 }
 243
 244 HENT *
 245 hiternext(tb)
 246 register HASH *tb;
 247 {
 248     register HENT *entry;
 249
 250     entry = tb->tbl_eiter;
 251     do {
 252         if (entry)
 253             entry = entry->hent_next;
 254         if (!entry) {
 255             tb->tbl_riter++;
 256             if (tb->tbl_riter > tb->tbl_max) {
 257                 tb->tbl_riter = -1;
 258                 break;
 259             }
 260             entry = tb->tbl_array[tb->tbl_riter];
 261         }
 262     } while (!entry);
 263
 264     tb->tbl_eiter = entry;
 265     return entry;
 266 }
 267
 268 char *
 269 hiterkey(entry)
 270 register HENT *entry;
 271 {
 272     return entry->hent_key;
 273 }
 274
 275 STR *
 276 hiterval(entry)
 277 register HENT *entry;
 278 {
 279     return entry->hent_val;
 280 }