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