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