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