[inseparable changes from match from perl-5.003_91 to perl-5.003_92]
[p5sagit/p5-mst-13.2.git] / x2p / hash.c
1 /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:29:20 $
2  *
3  *    Copyright (c) 1991-1997, Larry Wall
4  *
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.
7  *
8  * $Log:        hash.c,v $
9  */
10
11 #include <stdio.h>
12 #include "EXTERN.h"
13 #include "a2p.h"
14 #include "util.h"
15
16 STR *
17 hfetch(tb,key)
18 register HASH *tb;
19 char *key;
20 {
21     register char *s;
22     register int i;
23     register int hash;
24     register HENT *entry;
25
26     if (!tb)
27         return Nullstr;
28     for (s=key,         i=0,    hash = 0;
29       /* while */ *s;
30          s++,           i++,    hash *= 5) {
31         hash += *s * coeff[i];
32     }
33     entry = tb->tbl_array[hash & tb->tbl_max];
34     for (; entry; entry = entry->hent_next) {
35         if (entry->hent_hash != hash)           /* strings can't be equal */
36             continue;
37         if (strNE(entry->hent_key,key)) /* is this it? */
38             continue;
39         return entry->hent_val;
40     }
41     return Nullstr;
42 }
43
44 bool
45 hstore(tb,key,val)
46 register HASH *tb;
47 char *key;
48 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
96 bool
97 hdelete(tb,key)
98 register HASH *tb;
99 char *key;
100 {
101     register char *s;
102     register int i;
103     register int hash;
104     register HENT *entry;
105     register HENT **oentry;
106
107     if (!tb)
108         return FALSE;
109     for (s=key,         i=0,    hash = 0;
110       /* while */ *s;
111          s++,           i++,    hash *= 5) {
112         hash += *s * coeff[i];
113     }
114
115     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
116     entry = *oentry;
117     i = 1;
118     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
119         if (entry->hent_hash != hash)           /* strings can't be equal */
120             continue;
121         if (strNE(entry->hent_key,key)) /* is this it? */
122             continue;
123         safefree((char*)entry->hent_val);
124         safefree(entry->hent_key);
125         *oentry = entry->hent_next;
126         safefree((char*)entry);
127         if (i)
128             tb->tbl_fill--;
129         return TRUE;
130     }
131     return FALSE;
132 }
133 #endif
134
135 void
136 hsplit(tb)
137 HASH *tb;
138 {
139     int oldsize = tb->tbl_max + 1;
140     register int newsize = oldsize * 2;
141     register int i;
142     register HENT **a;
143     register HENT **b;
144     register HENT *entry;
145     register HENT **oentry;
146
147     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
148     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
149     tb->tbl_max = --newsize;
150     tb->tbl_array = a;
151
152     for (i=0; i<oldsize; i++,a++) {
153         if (!*a)                                /* non-existent */
154             continue;
155         b = a+oldsize;
156         for (oentry = a, entry = *a; entry; entry = *oentry) {
157             if ((entry->hent_hash & newsize) != i) {
158                 *oentry = entry->hent_next;
159                 entry->hent_next = *b;
160                 if (!*b)
161                     tb->tbl_fill++;
162                 *b = entry;
163                 continue;
164             }
165             else
166                 oentry = &entry->hent_next;
167         }
168         if (!*a)                                /* everything moved */
169             tb->tbl_fill--;
170     }
171 }
172
173 HASH *
174 hnew()
175 {
176     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
177
178     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
179     tb->tbl_fill = 0;
180     tb->tbl_max = 7;
181     hiterinit(tb);      /* so each() will start off right */
182     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
183     return tb;
184 }
185
186 #ifdef NOTUSED
187 hshow(tb)
188 register HASH *tb;
189 {
190     fprintf(stderr,"%5d %4d (%2d%%)\n",
191         tb->tbl_max+1,
192         tb->tbl_fill,
193         tb->tbl_fill * 100 / (tb->tbl_max+1));
194 }
195 #endif
196
197 int
198 hiterinit(tb)
199 register HASH *tb;
200 {
201     tb->tbl_riter = -1;
202     tb->tbl_eiter = Null(HENT*);
203     return tb->tbl_fill;
204 }
205
206 HENT *
207 hiternext(tb)
208 register HASH *tb;
209 {
210     register HENT *entry;
211
212     entry = tb->tbl_eiter;
213     do {
214         if (entry)
215             entry = entry->hent_next;
216         if (!entry) {
217             tb->tbl_riter++;
218             if (tb->tbl_riter > tb->tbl_max) {
219                 tb->tbl_riter = -1;
220                 break;
221             }
222             entry = tb->tbl_array[tb->tbl_riter];
223         }
224     } while (!entry);
225
226     tb->tbl_eiter = entry;
227     return entry;
228 }
229
230 char *
231 hiterkey(entry)
232 register HENT *entry;
233 {
234     return entry->hent_key;
235 }
236
237 STR *
238 hiterval(entry)
239 register HENT *entry;
240 {
241     return entry->hent_val;
242 }