perl 3.0: (no announcement message available)
[p5sagit/p5-mst-13.2.git] / x2p / hash.c
1 /* $Header: hash.c,v 3.0 89/10/18 15:34:50 lwall Locked $
2  *
3  *    Copyright (c) 1989, Larry Wall
4  *
5  *    You may distribute under the terms of the GNU General Public License
6  *    as specified in the README file that comes with the perl 3.0 kit.
7  *
8  * $Log:        hash.c,v $
9  * Revision 3.0  89/10/18  15:34:50  lwall
10  * 3.0 baseline
11  * 
12  */
13
14 #include <stdio.h>
15 #include "EXTERN.h"
16 #include "handy.h"
17 #include "util.h"
18 #include "a2p.h"
19
20 STR *
21 hfetch(tb,key)
22 register HASH *tb;
23 char *key;
24 {
25     register char *s;
26     register int i;
27     register int hash;
28     register HENT *entry;
29
30     if (!tb)
31         return Nullstr;
32     for (s=key,         i=0,    hash = 0;
33       /* while */ *s;
34          s++,           i++,    hash *= 5) {
35         hash += *s * coeff[i];
36     }
37     entry = tb->tbl_array[hash & tb->tbl_max];
38     for (; entry; entry = entry->hent_next) {
39         if (entry->hent_hash != hash)           /* strings can't be equal */
40             continue;
41         if (strNE(entry->hent_key,key)) /* is this it? */
42             continue;
43         return entry->hent_val;
44     }
45     return Nullstr;
46 }
47
48 bool
49 hstore(tb,key,val)
50 register HASH *tb;
51 char *key;
52 STR *val;
53 {
54     register char *s;
55     register int i;
56     register int hash;
57     register HENT *entry;
58     register HENT **oentry;
59
60     if (!tb)
61         return FALSE;
62     for (s=key,         i=0,    hash = 0;
63       /* while */ *s;
64          s++,           i++,    hash *= 5) {
65         hash += *s * coeff[i];
66     }
67
68     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
69     i = 1;
70
71     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
72         if (entry->hent_hash != hash)           /* strings can't be equal */
73             continue;
74         if (strNE(entry->hent_key,key)) /* is this it? */
75             continue;
76         safefree((char*)entry->hent_val);
77         entry->hent_val = val;
78         return TRUE;
79     }
80     entry = (HENT*) safemalloc(sizeof(HENT));
81
82     entry->hent_key = savestr(key);
83     entry->hent_val = val;
84     entry->hent_hash = hash;
85     entry->hent_next = *oentry;
86     *oentry = entry;
87
88     if (i) {                            /* initial entry? */
89         tb->tbl_fill++;
90         if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
91             hsplit(tb);
92     }
93
94     return FALSE;
95 }
96
97 #ifdef NOTUSED
98 bool
99 hdelete(tb,key)
100 register HASH *tb;
101 char *key;
102 {
103     register char *s;
104     register int i;
105     register int hash;
106     register HENT *entry;
107     register HENT **oentry;
108
109     if (!tb)
110         return FALSE;
111     for (s=key,         i=0,    hash = 0;
112       /* while */ *s;
113          s++,           i++,    hash *= 5) {
114         hash += *s * coeff[i];
115     }
116
117     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
118     entry = *oentry;
119     i = 1;
120     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
121         if (entry->hent_hash != hash)           /* strings can't be equal */
122             continue;
123         if (strNE(entry->hent_key,key)) /* is this it? */
124             continue;
125         safefree((char*)entry->hent_val);
126         safefree(entry->hent_key);
127         *oentry = entry->hent_next;
128         safefree((char*)entry);
129         if (i)
130             tb->tbl_fill--;
131         return TRUE;
132     }
133     return FALSE;
134 }
135 #endif
136
137 hsplit(tb)
138 HASH *tb;
139 {
140     int oldsize = tb->tbl_max + 1;
141     register int newsize = oldsize * 2;
142     register int i;
143     register HENT **a;
144     register HENT **b;
145     register HENT *entry;
146     register HENT **oentry;
147
148     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
149     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
150     tb->tbl_max = --newsize;
151     tb->tbl_array = a;
152
153     for (i=0; i<oldsize; i++,a++) {
154         if (!*a)                                /* non-existent */
155             continue;
156         b = a+oldsize;
157         for (oentry = a, entry = *a; entry; entry = *oentry) {
158             if ((entry->hent_hash & newsize) != i) {
159                 *oentry = entry->hent_next;
160                 entry->hent_next = *b;
161                 if (!*b)
162                     tb->tbl_fill++;
163                 *b = entry;
164                 continue;
165             }
166             else
167                 oentry = &entry->hent_next;
168         }
169         if (!*a)                                /* everything moved */
170             tb->tbl_fill--;
171     }
172 }
173
174 HASH *
175 hnew()
176 {
177     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
178
179     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
180     tb->tbl_fill = 0;
181     tb->tbl_max = 7;
182     hiterinit(tb);      /* so each() will start off right */
183     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
184     return tb;
185 }
186
187 #ifdef NOTUSED
188 hshow(tb)
189 register HASH *tb;
190 {
191     fprintf(stderr,"%5d %4d (%2d%%)\n",
192         tb->tbl_max+1,
193         tb->tbl_fill,
194         tb->tbl_fill * 100 / (tb->tbl_max+1));
195 }
196 #endif
197
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 }