x2p/hash.c

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