Commit | Line | Data |
---|---|---|
79072805 LW |
1 | /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:21:48 $ |
2 | * | |
3 | * Copyright (c) 1991, 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 | * Revision 4.1 92/08/07 18:21:48 lwall | |
10 | * | |
11 | * Revision 4.0.1.3 92/06/08 13:26:29 lwall | |
12 | * patch20: removed implicit int declarations on functions | |
13 | * patch20: delete could cause %array to give too low a count of buckets filled | |
14 | * patch20: hash tables now split only if the memory is available to do so | |
15 | * | |
16 | * Revision 4.0.1.2 91/11/05 17:24:13 lwall | |
17 | * patch11: saberized perl | |
18 | * | |
19 | * Revision 4.0.1.1 91/06/07 11:10:11 lwall | |
20 | * patch4: new copyright notice | |
21 | * | |
22 | * Revision 4.0 91/03/20 01:22:26 lwall | |
23 | * 4.0 baseline. | |
24 | * | |
25 | */ | |
26 | ||
27 | #include "EXTERN.h" | |
28 | #include "perl.h" | |
29 | ||
30 | static void hsplit(); | |
31 | ||
32 | static void hfreeentries(); | |
33 | ||
34 | SV** | |
35 | hv_fetch(hv,key,klen,lval) | |
36 | HV *hv; | |
37 | char *key; | |
38 | U32 klen; | |
39 | I32 lval; | |
40 | { | |
41 | register XPVHV* xhv; | |
42 | register char *s; | |
43 | register I32 i; | |
44 | register I32 hash; | |
45 | register HE *entry; | |
79072805 | 46 | SV *sv; |
79072805 LW |
47 | |
48 | if (!hv) | |
49 | return 0; | |
463ee0b2 | 50 | |
8990e307 | 51 | if (SvRMAGICAL(hv)) { |
463ee0b2 | 52 | if (mg_find((SV*)hv,'P')) { |
8990e307 | 53 | sv = sv_newmortal(); |
463ee0b2 LW |
54 | mg_copy((SV*)hv, sv, key, klen); |
55 | if (!lval) { | |
56 | mg_get(sv); | |
57 | sv_unmagic(sv,'p'); | |
58 | } | |
59 | Sv = sv; | |
60 | return &Sv; | |
61 | } | |
62 | } | |
63 | ||
79072805 LW |
64 | xhv = (XPVHV*)SvANY(hv); |
65 | if (!xhv->xhv_array) { | |
66 | if (lval) | |
463ee0b2 | 67 | Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char); |
79072805 LW |
68 | else |
69 | return 0; | |
70 | } | |
71 | ||
463ee0b2 LW |
72 | i = klen; |
73 | hash = 0; | |
74 | s = key; | |
75 | while (i--) | |
76 | hash = hash * 33 + *s++; | |
79072805 | 77 | |
463ee0b2 | 78 | entry = ((HE**)xhv->xhv_array)[hash & xhv->xhv_max]; |
79072805 LW |
79 | for (; entry; entry = entry->hent_next) { |
80 | if (entry->hent_hash != hash) /* strings can't be equal */ | |
81 | continue; | |
82 | if (entry->hent_klen != klen) | |
83 | continue; | |
84 | if (bcmp(entry->hent_key,key,klen)) /* is this it? */ | |
85 | continue; | |
86 | return &entry->hent_val; | |
87 | } | |
79072805 LW |
88 | if (lval) { /* gonna assign to this, so it better be there */ |
89 | sv = NEWSV(61,0); | |
90 | return hv_store(hv,key,klen,sv,hash); | |
91 | } | |
92 | return 0; | |
93 | } | |
94 | ||
95 | SV** | |
96 | hv_store(hv,key,klen,val,hash) | |
97 | HV *hv; | |
98 | char *key; | |
99 | U32 klen; | |
100 | SV *val; | |
93a17b20 | 101 | register U32 hash; |
79072805 LW |
102 | { |
103 | register XPVHV* xhv; | |
104 | register char *s; | |
105 | register I32 i; | |
106 | register HE *entry; | |
107 | register HE **oentry; | |
79072805 LW |
108 | |
109 | if (!hv) | |
110 | return 0; | |
111 | ||
112 | xhv = (XPVHV*)SvANY(hv); | |
463ee0b2 | 113 | if (SvMAGICAL(hv)) { |
463ee0b2 LW |
114 | mg_copy((SV*)hv, val, key, klen); |
115 | if (!xhv->xhv_array) | |
116 | return 0; | |
117 | } | |
118 | if (!hash) { | |
119 | i = klen; | |
120 | s = key; | |
121 | while (i--) | |
122 | hash = hash * 33 + *s++; | |
79072805 LW |
123 | } |
124 | ||
125 | if (!xhv->xhv_array) | |
463ee0b2 | 126 | Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char); |
79072805 | 127 | |
463ee0b2 | 128 | oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max]; |
79072805 LW |
129 | i = 1; |
130 | ||
79072805 LW |
131 | for (entry = *oentry; entry; i=0, entry = entry->hent_next) { |
132 | if (entry->hent_hash != hash) /* strings can't be equal */ | |
133 | continue; | |
134 | if (entry->hent_klen != klen) | |
135 | continue; | |
136 | if (bcmp(entry->hent_key,key,klen)) /* is this it? */ | |
137 | continue; | |
8990e307 | 138 | SvREFCNT_dec(entry->hent_val); |
79072805 LW |
139 | entry->hent_val = val; |
140 | return &entry->hent_val; | |
141 | } | |
142 | New(501,entry, 1, HE); | |
143 | ||
144 | entry->hent_klen = klen; | |
145 | entry->hent_key = nsavestr(key,klen); | |
146 | entry->hent_val = val; | |
147 | entry->hent_hash = hash; | |
148 | entry->hent_next = *oentry; | |
149 | *oentry = entry; | |
150 | ||
463ee0b2 | 151 | xhv->xhv_keys++; |
79072805 | 152 | if (i) { /* initial entry? */ |
463ee0b2 LW |
153 | ++xhv->xhv_fill; |
154 | if (xhv->xhv_keys > xhv->xhv_max) | |
79072805 LW |
155 | hsplit(hv); |
156 | } | |
79072805 LW |
157 | |
158 | return &entry->hent_val; | |
159 | } | |
160 | ||
161 | SV * | |
162 | hv_delete(hv,key,klen) | |
163 | HV *hv; | |
164 | char *key; | |
165 | U32 klen; | |
166 | { | |
167 | register XPVHV* xhv; | |
168 | register char *s; | |
169 | register I32 i; | |
170 | register I32 hash; | |
171 | register HE *entry; | |
172 | register HE **oentry; | |
173 | SV *sv; | |
79072805 LW |
174 | |
175 | if (!hv) | |
176 | return Nullsv; | |
8990e307 | 177 | if (SvRMAGICAL(hv)) { |
463ee0b2 LW |
178 | sv = *hv_fetch(hv, key, klen, TRUE); |
179 | mg_clear(sv); | |
180 | } | |
79072805 LW |
181 | xhv = (XPVHV*)SvANY(hv); |
182 | if (!xhv->xhv_array) | |
183 | return Nullsv; | |
463ee0b2 LW |
184 | i = klen; |
185 | hash = 0; | |
186 | s = key; | |
187 | while (i--) | |
188 | hash = hash * 33 + *s++; | |
79072805 | 189 | |
463ee0b2 | 190 | oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max]; |
79072805 LW |
191 | entry = *oentry; |
192 | i = 1; | |
193 | for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) { | |
194 | if (entry->hent_hash != hash) /* strings can't be equal */ | |
195 | continue; | |
196 | if (entry->hent_klen != klen) | |
197 | continue; | |
198 | if (bcmp(entry->hent_key,key,klen)) /* is this it? */ | |
199 | continue; | |
200 | *oentry = entry->hent_next; | |
201 | if (i && !*oentry) | |
202 | xhv->xhv_fill--; | |
203 | sv = sv_mortalcopy(entry->hent_val); | |
204 | he_free(entry); | |
463ee0b2 | 205 | --xhv->xhv_keys; |
79072805 LW |
206 | return sv; |
207 | } | |
79072805 | 208 | return Nullsv; |
79072805 LW |
209 | } |
210 | ||
211 | static void | |
212 | hsplit(hv) | |
213 | HV *hv; | |
214 | { | |
215 | register XPVHV* xhv = (XPVHV*)SvANY(hv); | |
216 | I32 oldsize = xhv->xhv_max + 1; | |
217 | register I32 newsize = oldsize * 2; | |
218 | register I32 i; | |
219 | register HE **a; | |
220 | register HE **b; | |
221 | register HE *entry; | |
222 | register HE **oentry; | |
223 | ||
463ee0b2 | 224 | a = (HE**)xhv->xhv_array; |
79072805 LW |
225 | nomemok = TRUE; |
226 | Renew(a, newsize, HE*); | |
227 | nomemok = FALSE; | |
79072805 LW |
228 | Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/ |
229 | xhv->xhv_max = --newsize; | |
463ee0b2 | 230 | xhv->xhv_array = (char*)a; |
79072805 LW |
231 | |
232 | for (i=0; i<oldsize; i++,a++) { | |
233 | if (!*a) /* non-existent */ | |
234 | continue; | |
235 | b = a+oldsize; | |
236 | for (oentry = a, entry = *a; entry; entry = *oentry) { | |
237 | if ((entry->hent_hash & newsize) != i) { | |
238 | *oentry = entry->hent_next; | |
239 | entry->hent_next = *b; | |
240 | if (!*b) | |
241 | xhv->xhv_fill++; | |
242 | *b = entry; | |
243 | continue; | |
244 | } | |
245 | else | |
246 | oentry = &entry->hent_next; | |
247 | } | |
248 | if (!*a) /* everything moved */ | |
249 | xhv->xhv_fill--; | |
250 | } | |
251 | } | |
252 | ||
253 | HV * | |
463ee0b2 | 254 | newHV() |
79072805 LW |
255 | { |
256 | register HV *hv; | |
257 | register XPVHV* xhv; | |
258 | ||
259 | Newz(502,hv, 1, HV); | |
260 | SvREFCNT(hv) = 1; | |
261 | sv_upgrade(hv, SVt_PVHV); | |
262 | xhv = (XPVHV*)SvANY(hv); | |
263 | SvPOK_off(hv); | |
264 | SvNOK_off(hv); | |
463ee0b2 | 265 | xhv->xhv_max = 7; /* start with 8 buckets */ |
79072805 LW |
266 | xhv->xhv_fill = 0; |
267 | xhv->xhv_pmroot = 0; | |
79072805 LW |
268 | (void)hv_iterinit(hv); /* so each() will start off right */ |
269 | return hv; | |
270 | } | |
271 | ||
272 | void | |
273 | he_free(hent) | |
274 | register HE *hent; | |
275 | { | |
276 | if (!hent) | |
277 | return; | |
8990e307 | 278 | SvREFCNT_dec(hent->hent_val); |
79072805 LW |
279 | Safefree(hent->hent_key); |
280 | Safefree(hent); | |
281 | } | |
282 | ||
283 | void | |
284 | he_delayfree(hent) | |
285 | register HE *hent; | |
286 | { | |
287 | if (!hent) | |
288 | return; | |
289 | sv_2mortal(hent->hent_val); /* free between statements */ | |
290 | Safefree(hent->hent_key); | |
291 | Safefree(hent); | |
292 | } | |
293 | ||
294 | void | |
463ee0b2 | 295 | hv_clear(hv) |
79072805 | 296 | HV *hv; |
79072805 LW |
297 | { |
298 | register XPVHV* xhv; | |
299 | if (!hv) | |
300 | return; | |
301 | xhv = (XPVHV*)SvANY(hv); | |
463ee0b2 | 302 | hfreeentries(hv); |
79072805 | 303 | xhv->xhv_fill = 0; |
79072805 | 304 | if (xhv->xhv_array) |
463ee0b2 | 305 | (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*)); |
79072805 LW |
306 | } |
307 | ||
308 | static void | |
463ee0b2 | 309 | hfreeentries(hv) |
79072805 | 310 | HV *hv; |
79072805 LW |
311 | { |
312 | register XPVHV* xhv; | |
313 | register HE *hent; | |
314 | register HE *ohent = Null(HE*); | |
79072805 LW |
315 | |
316 | if (!hv) | |
317 | return; | |
318 | xhv = (XPVHV*)SvANY(hv); | |
319 | if (!xhv->xhv_array) | |
320 | return; | |
79072805 LW |
321 | (void)hv_iterinit(hv); |
322 | /*SUPPRESS 560*/ | |
323 | while (hent = hv_iternext(hv)) { /* concise but not very efficient */ | |
324 | he_free(ohent); | |
325 | ohent = hent; | |
326 | } | |
327 | he_free(ohent); | |
79072805 | 328 | if (SvMAGIC(hv)) |
463ee0b2 | 329 | mg_clear((SV*)hv); |
79072805 LW |
330 | } |
331 | ||
332 | void | |
463ee0b2 | 333 | hv_undef(hv) |
79072805 | 334 | HV *hv; |
79072805 LW |
335 | { |
336 | register XPVHV* xhv; | |
337 | if (!hv) | |
338 | return; | |
339 | xhv = (XPVHV*)SvANY(hv); | |
463ee0b2 | 340 | hfreeentries(hv); |
79072805 LW |
341 | Safefree(xhv->xhv_array); |
342 | xhv->xhv_array = 0; | |
463ee0b2 | 343 | xhv->xhv_max = 7; /* it's a normal associative array */ |
79072805 | 344 | xhv->xhv_fill = 0; |
79072805 LW |
345 | (void)hv_iterinit(hv); /* so each() will start off right */ |
346 | } | |
347 | ||
348 | void | |
463ee0b2 | 349 | hv_free(hv) |
79072805 | 350 | register HV *hv; |
79072805 LW |
351 | { |
352 | if (!hv) | |
353 | return; | |
463ee0b2 | 354 | hfreeentries(hv); |
79072805 LW |
355 | Safefree(HvARRAY(hv)); |
356 | Safefree(hv); | |
357 | } | |
358 | ||
359 | I32 | |
360 | hv_iterinit(hv) | |
361 | HV *hv; | |
362 | { | |
363 | register XPVHV* xhv = (XPVHV*)SvANY(hv); | |
364 | xhv->xhv_riter = -1; | |
365 | xhv->xhv_eiter = Null(HE*); | |
366 | return xhv->xhv_fill; | |
367 | } | |
368 | ||
369 | HE * | |
370 | hv_iternext(hv) | |
371 | HV *hv; | |
372 | { | |
373 | register XPVHV* xhv; | |
374 | register HE *entry; | |
463ee0b2 | 375 | MAGIC* mg; |
79072805 LW |
376 | |
377 | if (!hv) | |
463ee0b2 | 378 | croak("Bad associative array"); |
79072805 LW |
379 | xhv = (XPVHV*)SvANY(hv); |
380 | entry = xhv->xhv_eiter; | |
463ee0b2 | 381 | |
8990e307 LW |
382 | if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) { |
383 | SV *key = sv_newmortal(); | |
463ee0b2 LW |
384 | if (entry) |
385 | sv_setpvn(key, entry->hent_key, entry->hent_klen); | |
386 | else { | |
387 | Newz(504,entry, 1, HE); | |
388 | xhv->xhv_eiter = entry; | |
389 | } | |
390 | magic_nextpack(hv,mg,key); | |
391 | if (SvOK(key)) { | |
392 | STRLEN len; | |
393 | entry->hent_key = SvPV(key, len); | |
394 | entry->hent_klen = len; | |
395 | SvPOK_off(key); | |
396 | SvPVX(key) = 0; | |
397 | return entry; | |
398 | } | |
399 | if (entry->hent_val) | |
8990e307 | 400 | SvREFCNT_dec(entry->hent_val); |
463ee0b2 LW |
401 | Safefree(entry); |
402 | xhv->xhv_eiter = Null(HE*); | |
403 | return Null(HE*); | |
79072805 | 404 | } |
463ee0b2 | 405 | |
79072805 | 406 | if (!xhv->xhv_array) |
463ee0b2 | 407 | Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char); |
79072805 LW |
408 | do { |
409 | if (entry) | |
410 | entry = entry->hent_next; | |
411 | if (!entry) { | |
412 | xhv->xhv_riter++; | |
413 | if (xhv->xhv_riter > xhv->xhv_max) { | |
414 | xhv->xhv_riter = -1; | |
415 | break; | |
416 | } | |
463ee0b2 | 417 | entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter]; |
79072805 LW |
418 | } |
419 | } while (!entry); | |
420 | ||
421 | xhv->xhv_eiter = entry; | |
422 | return entry; | |
423 | } | |
424 | ||
425 | char * | |
426 | hv_iterkey(entry,retlen) | |
427 | register HE *entry; | |
428 | I32 *retlen; | |
429 | { | |
430 | *retlen = entry->hent_klen; | |
431 | return entry->hent_key; | |
432 | } | |
433 | ||
434 | SV * | |
435 | hv_iterval(hv,entry) | |
436 | HV *hv; | |
437 | register HE *entry; | |
438 | { | |
8990e307 | 439 | if (SvRMAGICAL(hv)) { |
463ee0b2 | 440 | if (mg_find((SV*)hv,'P')) { |
8990e307 | 441 | SV* sv = sv_newmortal(); |
463ee0b2 LW |
442 | mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen); |
443 | mg_get(sv); | |
444 | sv_unmagic(sv,'p'); | |
445 | return sv; | |
446 | } | |
79072805 | 447 | } |
79072805 LW |
448 | return entry->hent_val; |
449 | } | |
450 | ||
79072805 LW |
451 | void |
452 | hv_magic(hv, gv, how) | |
453 | HV* hv; | |
454 | GV* gv; | |
455 | I32 how; | |
456 | { | |
463ee0b2 | 457 | sv_magic((SV*)hv, (SV*)gv, how, 0, 0); |
79072805 | 458 | } |