2.11BSD#431 - /usr/src/new/PORT/perl.1.0.0/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: }

Defined functions