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