Commit | Line | Data |
---|---|---|
a0d0e21e | 1 | /* hv.c |
79072805 | 2 | * |
a0d0e21e | 3 | * Copyright (c) 1991-1994, Larry Wall |
79072805 LW |
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 | * | |
a0d0e21e LW |
8 | */ |
9 | ||
10 | /* | |
11 | * "I sit beside the fire and think of all that I have seen." --Bilbo | |
79072805 LW |
12 | */ |
13 | ||
14 | #include "EXTERN.h" | |
15 | #include "perl.h" | |
16 | ||
a0d0e21e LW |
17 | static void hsplit _((HV *hv)); |
18 | static void hfreeentries _((HV *hv)); | |
79072805 | 19 | |
4633a7c4 LW |
20 | static HE* more_he(); |
21 | ||
22 | static HE* | |
23 | new_he() | |
24 | { | |
25 | HE* he; | |
26 | if (he_root) { | |
27 | he = he_root; | |
fde52b5c | 28 | he_root = HeNEXT(he); |
4633a7c4 LW |
29 | return he; |
30 | } | |
31 | return more_he(); | |
32 | } | |
33 | ||
34 | static void | |
35 | del_he(p) | |
36 | HE* p; | |
37 | { | |
fde52b5c | 38 | HeNEXT(p) = (HE*)he_root; |
4633a7c4 LW |
39 | he_root = p; |
40 | } | |
41 | ||
42 | static HE* | |
43 | more_he() | |
44 | { | |
45 | register HE* he; | |
46 | register HE* heend; | |
47 | he_root = (HE*)safemalloc(1008); | |
48 | he = he_root; | |
49 | heend = &he[1008 / sizeof(HE) - 1]; | |
50 | while (he < heend) { | |
fde52b5c | 51 | HeNEXT(he) = (HE*)(he + 1); |
4633a7c4 LW |
52 | he++; |
53 | } | |
fde52b5c | 54 | HeNEXT(he) = 0; |
4633a7c4 LW |
55 | return new_he(); |
56 | } | |
57 | ||
bbce6d69 | 58 | static HEK * |
59 | save_hek(str, len, hash) | |
60 | char *str; | |
61 | I32 len; | |
62 | U32 hash; | |
63 | { | |
64 | char *k; | |
65 | register HEK *hek; | |
66 | ||
ff68c719 | 67 | New(54, k, HEK_BASESIZE + len + 1, char); |
bbce6d69 | 68 | hek = (HEK*)k; |
ff68c719 | 69 | Copy(str, HEK_KEY(hek), len, char); |
70 | *(HEK_KEY(hek) + len) = '\0'; | |
71 | HEK_LEN(hek) = len; | |
72 | HEK_HASH(hek) = hash; | |
bbce6d69 | 73 | return hek; |
74 | } | |
75 | ||
76 | void | |
77 | unshare_hek(hek) | |
78 | HEK *hek; | |
79 | { | |
ff68c719 | 80 | unsharepvn(HEK_KEY(hek),HEK_LEN(hek),HEK_HASH(hek)); |
bbce6d69 | 81 | } |
82 | ||
fde52b5c | 83 | /* (klen == HEf_SVKEY) is special for MAGICAL hv entries, meaning key slot |
84 | * contains an SV* */ | |
85 | ||
79072805 LW |
86 | SV** |
87 | hv_fetch(hv,key,klen,lval) | |
88 | HV *hv; | |
89 | char *key; | |
90 | U32 klen; | |
91 | I32 lval; | |
92 | { | |
93 | register XPVHV* xhv; | |
fde52b5c | 94 | register U32 hash; |
79072805 | 95 | register HE *entry; |
79072805 | 96 | SV *sv; |
79072805 LW |
97 | |
98 | if (!hv) | |
99 | return 0; | |
463ee0b2 | 100 | |
8990e307 | 101 | if (SvRMAGICAL(hv)) { |
463ee0b2 | 102 | if (mg_find((SV*)hv,'P')) { |
8990e307 | 103 | sv = sv_newmortal(); |
463ee0b2 | 104 | mg_copy((SV*)hv, sv, key, klen); |
463ee0b2 LW |
105 | Sv = sv; |
106 | return &Sv; | |
107 | } | |
108 | } | |
109 | ||
79072805 LW |
110 | xhv = (XPVHV*)SvANY(hv); |
111 | if (!xhv->xhv_array) { | |
a0d0e21e LW |
112 | if (lval |
113 | #ifdef DYNAMIC_ENV_FETCH /* if it's an %ENV lookup, we may get it on the fly */ | |
114 | || (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) | |
115 | #endif | |
116 | ) | |
463ee0b2 | 117 | Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char); |
79072805 LW |
118 | else |
119 | return 0; | |
120 | } | |
121 | ||
fde52b5c | 122 | PERL_HASH(hash, key, klen); |
79072805 | 123 | |
a0d0e21e | 124 | entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; |
fde52b5c | 125 | for (; entry; entry = HeNEXT(entry)) { |
126 | if (HeHASH(entry) != hash) /* strings can't be equal */ | |
79072805 | 127 | continue; |
fde52b5c | 128 | if (HeKLEN(entry) != klen) |
79072805 | 129 | continue; |
36477c24 | 130 | if (memNE(HeKEY(entry),key,klen)) /* is this it? */ |
79072805 | 131 | continue; |
fde52b5c | 132 | return &HeVAL(entry); |
79072805 | 133 | } |
a0d0e21e LW |
134 | #ifdef DYNAMIC_ENV_FETCH /* %ENV lookup? If so, try to fetch the value now */ |
135 | if (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) { | |
136 | char *gotenv; | |
137 | ||
138 | gotenv = my_getenv(key); | |
139 | if (gotenv != NULL) { | |
140 | sv = newSVpv(gotenv,strlen(gotenv)); | |
141 | return hv_store(hv,key,klen,sv,hash); | |
142 | } | |
143 | } | |
144 | #endif | |
79072805 LW |
145 | if (lval) { /* gonna assign to this, so it better be there */ |
146 | sv = NEWSV(61,0); | |
147 | return hv_store(hv,key,klen,sv,hash); | |
148 | } | |
149 | return 0; | |
150 | } | |
151 | ||
fde52b5c | 152 | /* returns a HE * structure with the all fields set */ |
153 | /* note that hent_val will be a mortal sv for MAGICAL hashes */ | |
154 | HE * | |
155 | hv_fetch_ent(hv,keysv,lval,hash) | |
156 | HV *hv; | |
157 | SV *keysv; | |
158 | I32 lval; | |
159 | register U32 hash; | |
160 | { | |
161 | register XPVHV* xhv; | |
162 | register char *key; | |
163 | STRLEN klen; | |
164 | register HE *entry; | |
165 | SV *sv; | |
166 | ||
167 | if (!hv) | |
168 | return 0; | |
169 | ||
fde52b5c | 170 | if (SvRMAGICAL(hv) && mg_find((SV*)hv,'P')) { |
1cf368ac | 171 | static HE mh; |
ff68c719 | 172 | |
fde52b5c | 173 | sv = sv_newmortal(); |
effa1e2d | 174 | keysv = sv_2mortal(newSVsv(keysv)); |
fde52b5c | 175 | mg_copy((SV*)hv, sv, (char*)keysv, HEf_SVKEY); |
1cf368ac CS |
176 | if (!HeKEY_hek(&mh)) { |
177 | char *k; | |
178 | New(54, k, HEK_BASESIZE + sizeof(SV*), char); | |
179 | HeKEY_hek(&mh) = (HEK*)k; | |
180 | HeKLEN(&mh) = HEf_SVKEY; /* key will always hold an SV* */ | |
181 | } | |
182 | HeSVKEY_set(&mh, keysv); | |
183 | HeVAL(&mh) = sv; | |
184 | return &mh; | |
fde52b5c | 185 | } |
186 | ||
effa1e2d | 187 | xhv = (XPVHV*)SvANY(hv); |
fde52b5c | 188 | if (!xhv->xhv_array) { |
189 | if (lval | |
190 | #ifdef DYNAMIC_ENV_FETCH /* if it's an %ENV lookup, we may get it on the fly */ | |
191 | || (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) | |
192 | #endif | |
193 | ) | |
194 | Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char); | |
195 | else | |
196 | return 0; | |
197 | } | |
198 | ||
effa1e2d | 199 | key = SvPV(keysv, klen); |
200 | ||
201 | if (!hash) | |
202 | PERL_HASH(hash, key, klen); | |
203 | ||
fde52b5c | 204 | entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; |
205 | for (; entry; entry = HeNEXT(entry)) { | |
206 | if (HeHASH(entry) != hash) /* strings can't be equal */ | |
207 | continue; | |
208 | if (HeKLEN(entry) != klen) | |
209 | continue; | |
36477c24 | 210 | if (memNE(HeKEY(entry),key,klen)) /* is this it? */ |
fde52b5c | 211 | continue; |
212 | return entry; | |
213 | } | |
214 | #ifdef DYNAMIC_ENV_FETCH /* %ENV lookup? If so, try to fetch the value now */ | |
215 | if (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) { | |
216 | char *gotenv; | |
217 | ||
218 | gotenv = my_getenv(key); | |
219 | if (gotenv != NULL) { | |
220 | sv = newSVpv(gotenv,strlen(gotenv)); | |
221 | return hv_store_ent(hv,keysv,sv,hash); | |
222 | } | |
223 | } | |
224 | #endif | |
225 | if (lval) { /* gonna assign to this, so it better be there */ | |
226 | sv = NEWSV(61,0); | |
227 | return hv_store_ent(hv,keysv,sv,hash); | |
228 | } | |
229 | return 0; | |
230 | } | |
231 | ||
79072805 LW |
232 | SV** |
233 | hv_store(hv,key,klen,val,hash) | |
234 | HV *hv; | |
235 | char *key; | |
236 | U32 klen; | |
237 | SV *val; | |
93a17b20 | 238 | register U32 hash; |
79072805 LW |
239 | { |
240 | register XPVHV* xhv; | |
79072805 LW |
241 | register I32 i; |
242 | register HE *entry; | |
243 | register HE **oentry; | |
79072805 LW |
244 | |
245 | if (!hv) | |
246 | return 0; | |
247 | ||
248 | xhv = (XPVHV*)SvANY(hv); | |
463ee0b2 | 249 | if (SvMAGICAL(hv)) { |
463ee0b2 | 250 | mg_copy((SV*)hv, val, key, klen); |
1cf368ac CS |
251 | if (!xhv->xhv_array |
252 | && (SvMAGIC(hv)->mg_moremagic | |
253 | || (SvMAGIC(hv)->mg_type != 'E' | |
254 | #ifdef OVERLOAD | |
255 | && SvMAGIC(hv)->mg_type != 'A' | |
a0d0e21e | 256 | #endif /* OVERLOAD */ |
1cf368ac CS |
257 | ))) |
258 | return 0; | |
463ee0b2 | 259 | } |
fde52b5c | 260 | if (!hash) |
261 | PERL_HASH(hash, key, klen); | |
262 | ||
263 | if (!xhv->xhv_array) | |
264 | Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char); | |
265 | ||
266 | oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; | |
267 | i = 1; | |
268 | ||
269 | for (entry = *oentry; entry; i=0, entry = HeNEXT(entry)) { | |
270 | if (HeHASH(entry) != hash) /* strings can't be equal */ | |
271 | continue; | |
272 | if (HeKLEN(entry) != klen) | |
273 | continue; | |
36477c24 | 274 | if (memNE(HeKEY(entry),key,klen)) /* is this it? */ |
fde52b5c | 275 | continue; |
276 | SvREFCNT_dec(HeVAL(entry)); | |
277 | HeVAL(entry) = val; | |
278 | return &HeVAL(entry); | |
279 | } | |
280 | ||
281 | entry = new_he(); | |
fde52b5c | 282 | if (HvSHAREKEYS(hv)) |
ff68c719 | 283 | HeKEY_hek(entry) = share_hek(key, klen, hash); |
fde52b5c | 284 | else /* gotta do the real thing */ |
ff68c719 | 285 | HeKEY_hek(entry) = save_hek(key, klen, hash); |
fde52b5c | 286 | HeVAL(entry) = val; |
fde52b5c | 287 | HeNEXT(entry) = *oentry; |
288 | *oentry = entry; | |
289 | ||
290 | xhv->xhv_keys++; | |
291 | if (i) { /* initial entry? */ | |
292 | ++xhv->xhv_fill; | |
293 | if (xhv->xhv_keys > xhv->xhv_max) | |
294 | hsplit(hv); | |
79072805 LW |
295 | } |
296 | ||
fde52b5c | 297 | return &HeVAL(entry); |
298 | } | |
299 | ||
300 | HE * | |
301 | hv_store_ent(hv,keysv,val,hash) | |
302 | HV *hv; | |
303 | SV *keysv; | |
304 | SV *val; | |
305 | register U32 hash; | |
306 | { | |
307 | register XPVHV* xhv; | |
308 | register char *key; | |
309 | STRLEN klen; | |
310 | register I32 i; | |
311 | register HE *entry; | |
312 | register HE **oentry; | |
313 | ||
314 | if (!hv) | |
315 | return 0; | |
316 | ||
317 | xhv = (XPVHV*)SvANY(hv); | |
318 | if (SvMAGICAL(hv)) { | |
effa1e2d | 319 | keysv = sv_2mortal(newSVsv(keysv)); |
fde52b5c | 320 | mg_copy((SV*)hv, val, (char*)keysv, HEf_SVKEY); |
1cf368ac CS |
321 | if (!xhv->xhv_array |
322 | && (SvMAGIC(hv)->mg_moremagic | |
323 | || (SvMAGIC(hv)->mg_type != 'E' | |
324 | #ifdef OVERLOAD | |
325 | && SvMAGIC(hv)->mg_type != 'A' | |
fde52b5c | 326 | #endif /* OVERLOAD */ |
1cf368ac CS |
327 | ))) |
328 | return Nullhe; | |
fde52b5c | 329 | } |
330 | ||
331 | key = SvPV(keysv, klen); | |
332 | ||
333 | if (!hash) | |
334 | PERL_HASH(hash, key, klen); | |
335 | ||
79072805 | 336 | if (!xhv->xhv_array) |
463ee0b2 | 337 | Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char); |
79072805 | 338 | |
a0d0e21e | 339 | oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; |
79072805 LW |
340 | i = 1; |
341 | ||
fde52b5c | 342 | for (entry = *oentry; entry; i=0, entry = HeNEXT(entry)) { |
343 | if (HeHASH(entry) != hash) /* strings can't be equal */ | |
79072805 | 344 | continue; |
fde52b5c | 345 | if (HeKLEN(entry) != klen) |
79072805 | 346 | continue; |
36477c24 | 347 | if (memNE(HeKEY(entry),key,klen)) /* is this it? */ |
79072805 | 348 | continue; |
fde52b5c | 349 | SvREFCNT_dec(HeVAL(entry)); |
350 | HeVAL(entry) = val; | |
351 | return entry; | |
79072805 | 352 | } |
79072805 | 353 | |
4633a7c4 | 354 | entry = new_he(); |
fde52b5c | 355 | if (HvSHAREKEYS(hv)) |
ff68c719 | 356 | HeKEY_hek(entry) = share_hek(key, klen, hash); |
fde52b5c | 357 | else /* gotta do the real thing */ |
ff68c719 | 358 | HeKEY_hek(entry) = save_hek(key, klen, hash); |
fde52b5c | 359 | HeVAL(entry) = val; |
fde52b5c | 360 | HeNEXT(entry) = *oentry; |
79072805 LW |
361 | *oentry = entry; |
362 | ||
463ee0b2 | 363 | xhv->xhv_keys++; |
79072805 | 364 | if (i) { /* initial entry? */ |
463ee0b2 LW |
365 | ++xhv->xhv_fill; |
366 | if (xhv->xhv_keys > xhv->xhv_max) | |
79072805 LW |
367 | hsplit(hv); |
368 | } | |
79072805 | 369 | |
fde52b5c | 370 | return entry; |
79072805 LW |
371 | } |
372 | ||
373 | SV * | |
748a9306 | 374 | hv_delete(hv,key,klen,flags) |
79072805 LW |
375 | HV *hv; |
376 | char *key; | |
377 | U32 klen; | |
748a9306 | 378 | I32 flags; |
79072805 LW |
379 | { |
380 | register XPVHV* xhv; | |
79072805 | 381 | register I32 i; |
fde52b5c | 382 | register U32 hash; |
79072805 LW |
383 | register HE *entry; |
384 | register HE **oentry; | |
385 | SV *sv; | |
79072805 LW |
386 | |
387 | if (!hv) | |
388 | return Nullsv; | |
8990e307 | 389 | if (SvRMAGICAL(hv)) { |
463ee0b2 LW |
390 | sv = *hv_fetch(hv, key, klen, TRUE); |
391 | mg_clear(sv); | |
fde52b5c | 392 | if (mg_find(sv, 's')) { |
393 | return Nullsv; /* %SIG elements cannot be deleted */ | |
394 | } | |
a0d0e21e LW |
395 | if (mg_find(sv, 'p')) { |
396 | sv_unmagic(sv, 'p'); /* No longer an element */ | |
397 | return sv; | |
398 | } | |
463ee0b2 | 399 | } |
79072805 LW |
400 | xhv = (XPVHV*)SvANY(hv); |
401 | if (!xhv->xhv_array) | |
402 | return Nullsv; | |
fde52b5c | 403 | |
404 | PERL_HASH(hash, key, klen); | |
79072805 | 405 | |
a0d0e21e | 406 | oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; |
79072805 LW |
407 | entry = *oentry; |
408 | i = 1; | |
fde52b5c | 409 | for (; entry; i=0, oentry = &HeNEXT(entry), entry = *oentry) { |
410 | if (HeHASH(entry) != hash) /* strings can't be equal */ | |
79072805 | 411 | continue; |
fde52b5c | 412 | if (HeKLEN(entry) != klen) |
79072805 | 413 | continue; |
36477c24 | 414 | if (memNE(HeKEY(entry),key,klen)) /* is this it? */ |
79072805 | 415 | continue; |
fde52b5c | 416 | *oentry = HeNEXT(entry); |
79072805 LW |
417 | if (i && !*oentry) |
418 | xhv->xhv_fill--; | |
748a9306 LW |
419 | if (flags & G_DISCARD) |
420 | sv = Nullsv; | |
421 | else | |
fde52b5c | 422 | sv = sv_mortalcopy(HeVAL(entry)); |
a0d0e21e | 423 | if (entry == xhv->xhv_eiter) |
72940dca | 424 | HvLAZYDEL_on(hv); |
a0d0e21e | 425 | else |
fde52b5c | 426 | he_free(entry, HvSHAREKEYS(hv)); |
427 | --xhv->xhv_keys; | |
428 | return sv; | |
429 | } | |
430 | return Nullsv; | |
431 | } | |
432 | ||
433 | SV * | |
434 | hv_delete_ent(hv,keysv,flags,hash) | |
435 | HV *hv; | |
436 | SV *keysv; | |
437 | I32 flags; | |
438 | U32 hash; | |
439 | { | |
440 | register XPVHV* xhv; | |
441 | register I32 i; | |
442 | register char *key; | |
443 | STRLEN klen; | |
444 | register HE *entry; | |
445 | register HE **oentry; | |
446 | SV *sv; | |
447 | ||
448 | if (!hv) | |
449 | return Nullsv; | |
450 | if (SvRMAGICAL(hv)) { | |
451 | entry = hv_fetch_ent(hv, keysv, TRUE, hash); | |
452 | sv = HeVAL(entry); | |
453 | mg_clear(sv); | |
454 | if (mg_find(sv, 'p')) { | |
455 | sv_unmagic(sv, 'p'); /* No longer an element */ | |
456 | return sv; | |
457 | } | |
458 | } | |
459 | xhv = (XPVHV*)SvANY(hv); | |
460 | if (!xhv->xhv_array) | |
461 | return Nullsv; | |
462 | ||
463 | key = SvPV(keysv, klen); | |
464 | ||
465 | if (!hash) | |
466 | PERL_HASH(hash, key, klen); | |
467 | ||
468 | oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; | |
469 | entry = *oentry; | |
470 | i = 1; | |
471 | for (; entry; i=0, oentry = &HeNEXT(entry), entry = *oentry) { | |
472 | if (HeHASH(entry) != hash) /* strings can't be equal */ | |
473 | continue; | |
474 | if (HeKLEN(entry) != klen) | |
475 | continue; | |
36477c24 | 476 | if (memNE(HeKEY(entry),key,klen)) /* is this it? */ |
fde52b5c | 477 | continue; |
478 | *oentry = HeNEXT(entry); | |
479 | if (i && !*oentry) | |
480 | xhv->xhv_fill--; | |
481 | if (flags & G_DISCARD) | |
482 | sv = Nullsv; | |
483 | else | |
484 | sv = sv_mortalcopy(HeVAL(entry)); | |
485 | if (entry == xhv->xhv_eiter) | |
72940dca | 486 | HvLAZYDEL_on(hv); |
fde52b5c | 487 | else |
488 | he_free(entry, HvSHAREKEYS(hv)); | |
463ee0b2 | 489 | --xhv->xhv_keys; |
79072805 LW |
490 | return sv; |
491 | } | |
79072805 | 492 | return Nullsv; |
79072805 LW |
493 | } |
494 | ||
a0d0e21e LW |
495 | bool |
496 | hv_exists(hv,key,klen) | |
497 | HV *hv; | |
498 | char *key; | |
499 | U32 klen; | |
500 | { | |
501 | register XPVHV* xhv; | |
fde52b5c | 502 | register U32 hash; |
a0d0e21e LW |
503 | register HE *entry; |
504 | SV *sv; | |
505 | ||
506 | if (!hv) | |
507 | return 0; | |
508 | ||
509 | if (SvRMAGICAL(hv)) { | |
510 | if (mg_find((SV*)hv,'P')) { | |
511 | sv = sv_newmortal(); | |
512 | mg_copy((SV*)hv, sv, key, klen); | |
513 | magic_existspack(sv, mg_find(sv, 'p')); | |
514 | return SvTRUE(sv); | |
515 | } | |
516 | } | |
517 | ||
518 | xhv = (XPVHV*)SvANY(hv); | |
519 | if (!xhv->xhv_array) | |
520 | return 0; | |
521 | ||
fde52b5c | 522 | PERL_HASH(hash, key, klen); |
a0d0e21e LW |
523 | |
524 | entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; | |
fde52b5c | 525 | for (; entry; entry = HeNEXT(entry)) { |
526 | if (HeHASH(entry) != hash) /* strings can't be equal */ | |
a0d0e21e | 527 | continue; |
fde52b5c | 528 | if (HeKLEN(entry) != klen) |
a0d0e21e | 529 | continue; |
36477c24 | 530 | if (memNE(HeKEY(entry),key,klen)) /* is this it? */ |
fde52b5c | 531 | continue; |
532 | return TRUE; | |
533 | } | |
534 | return FALSE; | |
535 | } | |
536 | ||
537 | ||
538 | bool | |
539 | hv_exists_ent(hv,keysv,hash) | |
540 | HV *hv; | |
541 | SV *keysv; | |
542 | U32 hash; | |
543 | { | |
544 | register XPVHV* xhv; | |
545 | register char *key; | |
546 | STRLEN klen; | |
547 | register HE *entry; | |
548 | SV *sv; | |
549 | ||
550 | if (!hv) | |
551 | return 0; | |
552 | ||
553 | if (SvRMAGICAL(hv)) { | |
554 | if (mg_find((SV*)hv,'P')) { | |
555 | sv = sv_newmortal(); | |
effa1e2d | 556 | keysv = sv_2mortal(newSVsv(keysv)); |
fde52b5c | 557 | mg_copy((SV*)hv, sv, (char*)keysv, HEf_SVKEY); |
558 | magic_existspack(sv, mg_find(sv, 'p')); | |
559 | return SvTRUE(sv); | |
560 | } | |
561 | } | |
562 | ||
563 | xhv = (XPVHV*)SvANY(hv); | |
564 | if (!xhv->xhv_array) | |
565 | return 0; | |
566 | ||
567 | key = SvPV(keysv, klen); | |
568 | if (!hash) | |
569 | PERL_HASH(hash, key, klen); | |
570 | ||
571 | entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; | |
572 | for (; entry; entry = HeNEXT(entry)) { | |
573 | if (HeHASH(entry) != hash) /* strings can't be equal */ | |
574 | continue; | |
575 | if (HeKLEN(entry) != klen) | |
576 | continue; | |
36477c24 | 577 | if (memNE(HeKEY(entry),key,klen)) /* is this it? */ |
a0d0e21e LW |
578 | continue; |
579 | return TRUE; | |
580 | } | |
581 | return FALSE; | |
582 | } | |
583 | ||
79072805 LW |
584 | static void |
585 | hsplit(hv) | |
586 | HV *hv; | |
587 | { | |
588 | register XPVHV* xhv = (XPVHV*)SvANY(hv); | |
a0d0e21e | 589 | I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */ |
79072805 LW |
590 | register I32 newsize = oldsize * 2; |
591 | register I32 i; | |
592 | register HE **a; | |
593 | register HE **b; | |
594 | register HE *entry; | |
595 | register HE **oentry; | |
c07a80fd | 596 | #ifndef STRANGE_MALLOC |
4633a7c4 | 597 | I32 tmp; |
c07a80fd | 598 | #endif |
79072805 | 599 | |
463ee0b2 | 600 | a = (HE**)xhv->xhv_array; |
79072805 | 601 | nomemok = TRUE; |
4633a7c4 | 602 | #ifdef STRANGE_MALLOC |
79072805 | 603 | Renew(a, newsize, HE*); |
4633a7c4 LW |
604 | #else |
605 | i = newsize * sizeof(HE*); | |
606 | #define MALLOC_OVERHEAD 16 | |
607 | tmp = MALLOC_OVERHEAD; | |
608 | while (tmp - MALLOC_OVERHEAD < i) | |
609 | tmp += tmp; | |
610 | tmp -= MALLOC_OVERHEAD; | |
611 | tmp /= sizeof(HE*); | |
612 | assert(tmp >= newsize); | |
613 | New(2,a, tmp, HE*); | |
614 | Copy(xhv->xhv_array, a, oldsize, HE*); | |
c07a80fd | 615 | if (oldsize >= 64 && !nice_chunk) { |
616 | nice_chunk = (char*)xhv->xhv_array; | |
617 | nice_chunk_size = oldsize * sizeof(HE*) * 2 - MALLOC_OVERHEAD; | |
4633a7c4 LW |
618 | } |
619 | else | |
620 | Safefree(xhv->xhv_array); | |
621 | #endif | |
622 | ||
79072805 | 623 | nomemok = FALSE; |
79072805 LW |
624 | Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/ |
625 | xhv->xhv_max = --newsize; | |
463ee0b2 | 626 | xhv->xhv_array = (char*)a; |
79072805 LW |
627 | |
628 | for (i=0; i<oldsize; i++,a++) { | |
629 | if (!*a) /* non-existent */ | |
630 | continue; | |
631 | b = a+oldsize; | |
632 | for (oentry = a, entry = *a; entry; entry = *oentry) { | |
fde52b5c | 633 | if ((HeHASH(entry) & newsize) != i) { |
634 | *oentry = HeNEXT(entry); | |
635 | HeNEXT(entry) = *b; | |
79072805 LW |
636 | if (!*b) |
637 | xhv->xhv_fill++; | |
638 | *b = entry; | |
639 | continue; | |
640 | } | |
641 | else | |
fde52b5c | 642 | oentry = &HeNEXT(entry); |
79072805 LW |
643 | } |
644 | if (!*a) /* everything moved */ | |
645 | xhv->xhv_fill--; | |
646 | } | |
647 | } | |
648 | ||
72940dca | 649 | void |
650 | hv_ksplit(hv, newmax) | |
651 | HV *hv; | |
652 | IV newmax; | |
653 | { | |
654 | register XPVHV* xhv = (XPVHV*)SvANY(hv); | |
655 | I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */ | |
656 | register I32 newsize; | |
657 | register I32 i; | |
658 | register I32 j; | |
659 | register HE **a; | |
660 | register HE *entry; | |
661 | register HE **oentry; | |
662 | ||
663 | newsize = (I32) newmax; /* possible truncation here */ | |
664 | if (newsize != newmax || newmax <= oldsize) | |
665 | return; | |
666 | while ((newsize & (1 + ~newsize)) != newsize) { | |
667 | newsize &= ~(newsize & (1 + ~newsize)); /* get proper power of 2 */ | |
668 | } | |
669 | if (newsize < newmax) | |
670 | newsize *= 2; | |
671 | if (newsize < newmax) | |
672 | return; /* overflow detection */ | |
673 | ||
674 | a = (HE**)xhv->xhv_array; | |
675 | if (a) { | |
676 | nomemok = TRUE; | |
677 | #ifdef STRANGE_MALLOC | |
678 | Renew(a, newsize, HE*); | |
679 | #else | |
680 | i = newsize * sizeof(HE*); | |
681 | j = MALLOC_OVERHEAD; | |
682 | while (j - MALLOC_OVERHEAD < i) | |
683 | j += j; | |
684 | j -= MALLOC_OVERHEAD; | |
685 | j /= sizeof(HE*); | |
686 | assert(j >= newsize); | |
687 | New(2, a, j, HE*); | |
688 | Copy(xhv->xhv_array, a, oldsize, HE*); | |
689 | if (oldsize >= 64 && !nice_chunk) { | |
690 | nice_chunk = (char*)xhv->xhv_array; | |
691 | nice_chunk_size = oldsize * sizeof(HE*) * 2 - MALLOC_OVERHEAD; | |
692 | } | |
693 | else | |
694 | Safefree(xhv->xhv_array); | |
695 | #endif | |
696 | nomemok = FALSE; | |
697 | Zero(&a[oldsize], newsize-oldsize, HE*); /* zero 2nd half*/ | |
698 | } | |
699 | else { | |
700 | Newz(0, a, newsize, HE*); | |
701 | } | |
702 | xhv->xhv_max = --newsize; | |
703 | xhv->xhv_array = (char*)a; | |
704 | if (!xhv->xhv_fill) /* skip rest if no entries */ | |
705 | return; | |
706 | ||
707 | for (i=0; i<oldsize; i++,a++) { | |
708 | if (!*a) /* non-existent */ | |
709 | continue; | |
710 | for (oentry = a, entry = *a; entry; entry = *oentry) { | |
711 | if ((j = (HeHASH(entry) & newsize)) != i) { | |
712 | j -= i; | |
713 | *oentry = HeNEXT(entry); | |
714 | if (!(HeNEXT(entry) = a[j])) | |
715 | xhv->xhv_fill++; | |
716 | a[j] = entry; | |
717 | continue; | |
718 | } | |
719 | else | |
720 | oentry = &HeNEXT(entry); | |
721 | } | |
722 | if (!*a) /* everything moved */ | |
723 | xhv->xhv_fill--; | |
724 | } | |
725 | } | |
726 | ||
79072805 | 727 | HV * |
463ee0b2 | 728 | newHV() |
79072805 LW |
729 | { |
730 | register HV *hv; | |
731 | register XPVHV* xhv; | |
732 | ||
a0d0e21e LW |
733 | hv = (HV*)NEWSV(502,0); |
734 | sv_upgrade((SV *)hv, SVt_PVHV); | |
79072805 LW |
735 | xhv = (XPVHV*)SvANY(hv); |
736 | SvPOK_off(hv); | |
737 | SvNOK_off(hv); | |
fde52b5c | 738 | #ifndef NODEFAULT_SHAREKEYS |
739 | HvSHAREKEYS_on(hv); /* key-sharing on by default */ | |
740 | #endif | |
463ee0b2 | 741 | xhv->xhv_max = 7; /* start with 8 buckets */ |
79072805 LW |
742 | xhv->xhv_fill = 0; |
743 | xhv->xhv_pmroot = 0; | |
79072805 LW |
744 | (void)hv_iterinit(hv); /* so each() will start off right */ |
745 | return hv; | |
746 | } | |
747 | ||
748 | void | |
fde52b5c | 749 | he_free(hent, shared) |
79072805 | 750 | register HE *hent; |
fde52b5c | 751 | I32 shared; |
79072805 LW |
752 | { |
753 | if (!hent) | |
754 | return; | |
7a4c00b4 | 755 | if (SvTYPE(HeVAL(hent)) == SVt_PVGV && GvCV(HeVAL(hent))) |
71be2cbc | 756 | sub_generation++; /* May be deletion of method? */ |
fde52b5c | 757 | SvREFCNT_dec(HeVAL(hent)); |
bbce6d69 | 758 | if (HeKLEN(hent) == HEf_SVKEY) { |
759 | SvREFCNT_dec(HeKEY_sv(hent)); | |
ff68c719 | 760 | Safefree(HeKEY_hek(hent)); |
bbce6d69 | 761 | } else if (shared) |
ff68c719 | 762 | unshare_hek(HeKEY_hek(hent)); |
fde52b5c | 763 | else |
ff68c719 | 764 | Safefree(HeKEY_hek(hent)); |
4633a7c4 | 765 | del_he(hent); |
79072805 LW |
766 | } |
767 | ||
768 | void | |
fde52b5c | 769 | he_delayfree(hent, shared) |
79072805 | 770 | register HE *hent; |
fde52b5c | 771 | I32 shared; |
79072805 LW |
772 | { |
773 | if (!hent) | |
774 | return; | |
fde52b5c | 775 | sv_2mortal(HeVAL(hent)); /* free between statements */ |
bbce6d69 | 776 | if (HeKLEN(hent) == HEf_SVKEY) { |
777 | sv_2mortal(HeKEY_sv(hent)); | |
ff68c719 | 778 | Safefree(HeKEY_hek(hent)); |
bbce6d69 | 779 | } else if (shared) |
ff68c719 | 780 | unshare_hek(HeKEY_hek(hent)); |
fde52b5c | 781 | else |
ff68c719 | 782 | Safefree(HeKEY_hek(hent)); |
4633a7c4 | 783 | del_he(hent); |
79072805 LW |
784 | } |
785 | ||
786 | void | |
463ee0b2 | 787 | hv_clear(hv) |
79072805 | 788 | HV *hv; |
79072805 LW |
789 | { |
790 | register XPVHV* xhv; | |
791 | if (!hv) | |
792 | return; | |
793 | xhv = (XPVHV*)SvANY(hv); | |
463ee0b2 | 794 | hfreeentries(hv); |
79072805 | 795 | xhv->xhv_fill = 0; |
a0d0e21e | 796 | xhv->xhv_keys = 0; |
79072805 | 797 | if (xhv->xhv_array) |
463ee0b2 | 798 | (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*)); |
a0d0e21e LW |
799 | |
800 | if (SvRMAGICAL(hv)) | |
801 | mg_clear((SV*)hv); | |
79072805 LW |
802 | } |
803 | ||
804 | static void | |
463ee0b2 | 805 | hfreeentries(hv) |
79072805 | 806 | HV *hv; |
79072805 | 807 | { |
a0d0e21e | 808 | register HE **array; |
79072805 LW |
809 | register HE *hent; |
810 | register HE *ohent = Null(HE*); | |
a0d0e21e LW |
811 | I32 riter; |
812 | I32 max; | |
fde52b5c | 813 | I32 shared; |
79072805 LW |
814 | |
815 | if (!hv) | |
816 | return; | |
a0d0e21e | 817 | if (!HvARRAY(hv)) |
79072805 | 818 | return; |
a0d0e21e LW |
819 | |
820 | riter = 0; | |
821 | max = HvMAX(hv); | |
822 | array = HvARRAY(hv); | |
823 | hent = array[0]; | |
fde52b5c | 824 | shared = HvSHAREKEYS(hv); |
a0d0e21e LW |
825 | for (;;) { |
826 | if (hent) { | |
827 | ohent = hent; | |
fde52b5c | 828 | hent = HeNEXT(hent); |
829 | he_free(ohent, shared); | |
a0d0e21e LW |
830 | } |
831 | if (!hent) { | |
832 | if (++riter > max) | |
833 | break; | |
834 | hent = array[riter]; | |
835 | } | |
79072805 | 836 | } |
a0d0e21e | 837 | (void)hv_iterinit(hv); |
79072805 LW |
838 | } |
839 | ||
840 | void | |
463ee0b2 | 841 | hv_undef(hv) |
79072805 | 842 | HV *hv; |
79072805 LW |
843 | { |
844 | register XPVHV* xhv; | |
845 | if (!hv) | |
846 | return; | |
847 | xhv = (XPVHV*)SvANY(hv); | |
463ee0b2 | 848 | hfreeentries(hv); |
79072805 | 849 | Safefree(xhv->xhv_array); |
85e6fe83 LW |
850 | if (HvNAME(hv)) { |
851 | Safefree(HvNAME(hv)); | |
852 | HvNAME(hv) = 0; | |
853 | } | |
79072805 | 854 | xhv->xhv_array = 0; |
463ee0b2 | 855 | xhv->xhv_max = 7; /* it's a normal associative array */ |
79072805 | 856 | xhv->xhv_fill = 0; |
a0d0e21e LW |
857 | xhv->xhv_keys = 0; |
858 | ||
859 | if (SvRMAGICAL(hv)) | |
860 | mg_clear((SV*)hv); | |
79072805 LW |
861 | } |
862 | ||
79072805 LW |
863 | I32 |
864 | hv_iterinit(hv) | |
865 | HV *hv; | |
866 | { | |
867 | register XPVHV* xhv = (XPVHV*)SvANY(hv); | |
a0d0e21e | 868 | HE *entry = xhv->xhv_eiter; |
effa1e2d | 869 | #ifdef DYNAMIC_ENV_FETCH /* set up %ENV for iteration */ |
870 | if (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) prime_env_iter(); | |
871 | #endif | |
72940dca | 872 | if (entry && HvLAZYDEL(hv)) { /* was deleted earlier? */ |
873 | HvLAZYDEL_off(hv); | |
fde52b5c | 874 | he_free(entry, HvSHAREKEYS(hv)); |
72940dca | 875 | } |
79072805 LW |
876 | xhv->xhv_riter = -1; |
877 | xhv->xhv_eiter = Null(HE*); | |
878 | return xhv->xhv_fill; | |
879 | } | |
880 | ||
881 | HE * | |
882 | hv_iternext(hv) | |
883 | HV *hv; | |
884 | { | |
885 | register XPVHV* xhv; | |
886 | register HE *entry; | |
a0d0e21e | 887 | HE *oldentry; |
463ee0b2 | 888 | MAGIC* mg; |
79072805 LW |
889 | |
890 | if (!hv) | |
463ee0b2 | 891 | croak("Bad associative array"); |
79072805 | 892 | xhv = (XPVHV*)SvANY(hv); |
a0d0e21e | 893 | oldentry = entry = xhv->xhv_eiter; |
463ee0b2 | 894 | |
8990e307 LW |
895 | if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) { |
896 | SV *key = sv_newmortal(); | |
cd1469e6 | 897 | if (entry) { |
fde52b5c | 898 | sv_setsv(key, HeSVKEY_force(entry)); |
cd1469e6 | 899 | SvREFCNT_dec(HeSVKEY(entry)); /* get rid of previous key */ |
900 | } | |
a0d0e21e | 901 | else { |
ff68c719 | 902 | char *k; |
bbce6d69 | 903 | HEK *hek; |
ff68c719 | 904 | |
905 | xhv->xhv_eiter = entry = new_he(); /* one HE per MAGICAL hash */ | |
4633a7c4 | 906 | Zero(entry, 1, HE); |
ff68c719 | 907 | Newz(54, k, HEK_BASESIZE + sizeof(SV*), char); |
908 | hek = (HEK*)k; | |
909 | HeKEY_hek(entry) = hek; | |
fde52b5c | 910 | HeKLEN(entry) = HEf_SVKEY; |
a0d0e21e LW |
911 | } |
912 | magic_nextpack((SV*) hv,mg,key); | |
463ee0b2 | 913 | if (SvOK(key)) { |
cd1469e6 | 914 | /* force key to stay around until next time */ |
bbce6d69 | 915 | HeSVKEY_set(entry, SvREFCNT_inc(key)); |
916 | return entry; /* beware, hent_val is not set */ | |
463ee0b2 | 917 | } |
fde52b5c | 918 | if (HeVAL(entry)) |
919 | SvREFCNT_dec(HeVAL(entry)); | |
ff68c719 | 920 | Safefree(HeKEY_hek(entry)); |
4633a7c4 | 921 | del_he(entry); |
463ee0b2 LW |
922 | xhv->xhv_eiter = Null(HE*); |
923 | return Null(HE*); | |
79072805 | 924 | } |
463ee0b2 | 925 | |
79072805 | 926 | if (!xhv->xhv_array) |
4633a7c4 | 927 | Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char); |
fde52b5c | 928 | if (entry) |
929 | entry = HeNEXT(entry); | |
930 | while (!entry) { | |
931 | ++xhv->xhv_riter; | |
932 | if (xhv->xhv_riter > xhv->xhv_max) { | |
933 | xhv->xhv_riter = -1; | |
934 | break; | |
79072805 | 935 | } |
fde52b5c | 936 | entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter]; |
937 | } | |
79072805 | 938 | |
72940dca | 939 | if (oldentry && HvLAZYDEL(hv)) { /* was deleted earlier? */ |
940 | HvLAZYDEL_off(hv); | |
fde52b5c | 941 | he_free(oldentry, HvSHAREKEYS(hv)); |
72940dca | 942 | } |
a0d0e21e | 943 | |
79072805 LW |
944 | xhv->xhv_eiter = entry; |
945 | return entry; | |
946 | } | |
947 | ||
948 | char * | |
949 | hv_iterkey(entry,retlen) | |
950 | register HE *entry; | |
951 | I32 *retlen; | |
952 | { | |
fde52b5c | 953 | if (HeKLEN(entry) == HEf_SVKEY) { |
bbce6d69 | 954 | return SvPV(HeKEY_sv(entry), *(STRLEN*)retlen); |
fde52b5c | 955 | } |
956 | else { | |
957 | *retlen = HeKLEN(entry); | |
958 | return HeKEY(entry); | |
959 | } | |
960 | } | |
961 | ||
962 | /* unlike hv_iterval(), this always returns a mortal copy of the key */ | |
963 | SV * | |
964 | hv_iterkeysv(entry) | |
965 | register HE *entry; | |
966 | { | |
967 | if (HeKLEN(entry) == HEf_SVKEY) | |
bbce6d69 | 968 | return sv_mortalcopy(HeKEY_sv(entry)); |
fde52b5c | 969 | else |
970 | return sv_2mortal(newSVpv((HeKLEN(entry) ? HeKEY(entry) : ""), | |
971 | HeKLEN(entry))); | |
79072805 LW |
972 | } |
973 | ||
974 | SV * | |
975 | hv_iterval(hv,entry) | |
976 | HV *hv; | |
977 | register HE *entry; | |
978 | { | |
8990e307 | 979 | if (SvRMAGICAL(hv)) { |
463ee0b2 | 980 | if (mg_find((SV*)hv,'P')) { |
8990e307 | 981 | SV* sv = sv_newmortal(); |
bbce6d69 | 982 | if (HeKLEN(entry) == HEf_SVKEY) |
983 | mg_copy((SV*)hv, sv, (char*)HeKEY_sv(entry), HEf_SVKEY); | |
984 | else mg_copy((SV*)hv, sv, HeKEY(entry), HeKLEN(entry)); | |
463ee0b2 LW |
985 | return sv; |
986 | } | |
79072805 | 987 | } |
fde52b5c | 988 | return HeVAL(entry); |
79072805 LW |
989 | } |
990 | ||
a0d0e21e LW |
991 | SV * |
992 | hv_iternextsv(hv, key, retlen) | |
993 | HV *hv; | |
994 | char **key; | |
995 | I32 *retlen; | |
996 | { | |
997 | HE *he; | |
998 | if ( (he = hv_iternext(hv)) == NULL) | |
999 | return NULL; | |
1000 | *key = hv_iterkey(he, retlen); | |
1001 | return hv_iterval(hv, he); | |
1002 | } | |
1003 | ||
79072805 LW |
1004 | void |
1005 | hv_magic(hv, gv, how) | |
1006 | HV* hv; | |
1007 | GV* gv; | |
a0d0e21e | 1008 | int how; |
79072805 | 1009 | { |
a0d0e21e | 1010 | sv_magic((SV*)hv, (SV*)gv, how, Nullch, 0); |
79072805 | 1011 | } |
fde52b5c | 1012 | |
bbce6d69 | 1013 | char* |
1014 | sharepvn(sv, len, hash) | |
1015 | char* sv; | |
1016 | I32 len; | |
1017 | U32 hash; | |
1018 | { | |
ff68c719 | 1019 | return HEK_KEY(share_hek(sv, len, hash)); |
bbce6d69 | 1020 | } |
1021 | ||
1022 | /* possibly free a shared string if no one has access to it | |
fde52b5c | 1023 | * len and hash must both be valid for str. |
1024 | */ | |
bbce6d69 | 1025 | void |
1026 | unsharepvn(str, len, hash) | |
1027 | char* str; | |
fde52b5c | 1028 | I32 len; |
bbce6d69 | 1029 | U32 hash; |
fde52b5c | 1030 | { |
1031 | register XPVHV* xhv; | |
1032 | register HE *entry; | |
1033 | register HE **oentry; | |
1034 | register I32 i = 1; | |
1035 | I32 found = 0; | |
bbce6d69 | 1036 | |
fde52b5c | 1037 | /* what follows is the moral equivalent of: |
bbce6d69 | 1038 | if ((Svp = hv_fetch(strtab, tmpsv, FALSE, hash))) { |
1039 | if (--*Svp == Nullsv) | |
1040 | hv_delete(strtab, str, len, G_DISCARD, hash); | |
1041 | } */ | |
fde52b5c | 1042 | xhv = (XPVHV*)SvANY(strtab); |
1043 | /* assert(xhv_array != 0) */ | |
1044 | oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; | |
bbce6d69 | 1045 | for (entry = *oentry; entry; i=0, oentry = &HeNEXT(entry), entry = *oentry) { |
fde52b5c | 1046 | if (HeHASH(entry) != hash) /* strings can't be equal */ |
1047 | continue; | |
1048 | if (HeKLEN(entry) != len) | |
1049 | continue; | |
36477c24 | 1050 | if (memNE(HeKEY(entry),str,len)) /* is this it? */ |
fde52b5c | 1051 | continue; |
1052 | found = 1; | |
bbce6d69 | 1053 | if (--HeVAL(entry) == Nullsv) { |
1054 | *oentry = HeNEXT(entry); | |
1055 | if (i && !*oentry) | |
1056 | xhv->xhv_fill--; | |
ff68c719 | 1057 | Safefree(HeKEY_hek(entry)); |
bbce6d69 | 1058 | del_he(entry); |
1059 | --xhv->xhv_keys; | |
fde52b5c | 1060 | } |
bbce6d69 | 1061 | break; |
fde52b5c | 1062 | } |
bbce6d69 | 1063 | |
1064 | if (!found) | |
1065 | warn("Attempt to free non-existent shared string"); | |
fde52b5c | 1066 | } |
1067 | ||
bbce6d69 | 1068 | /* get a (constant) string ptr from the global string table |
1069 | * string will get added if it is not already there. | |
fde52b5c | 1070 | * len and hash must both be valid for str. |
1071 | */ | |
bbce6d69 | 1072 | HEK * |
1073 | share_hek(str, len, hash) | |
fde52b5c | 1074 | char *str; |
1075 | I32 len; | |
1076 | register U32 hash; | |
1077 | { | |
1078 | register XPVHV* xhv; | |
1079 | register HE *entry; | |
1080 | register HE **oentry; | |
1081 | register I32 i = 1; | |
1082 | I32 found = 0; | |
bbce6d69 | 1083 | |
fde52b5c | 1084 | /* what follows is the moral equivalent of: |
bbce6d69 | 1085 | |
1086 | if (!(Svp = hv_fetch(strtab, str, len, FALSE))) | |
1087 | hv_store(strtab, str, len, Nullsv, hash); | |
1088 | */ | |
fde52b5c | 1089 | xhv = (XPVHV*)SvANY(strtab); |
1090 | /* assert(xhv_array != 0) */ | |
1091 | oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; | |
bbce6d69 | 1092 | for (entry = *oentry; entry; i=0, entry = HeNEXT(entry)) { |
fde52b5c | 1093 | if (HeHASH(entry) != hash) /* strings can't be equal */ |
1094 | continue; | |
1095 | if (HeKLEN(entry) != len) | |
1096 | continue; | |
36477c24 | 1097 | if (memNE(HeKEY(entry),str,len)) /* is this it? */ |
fde52b5c | 1098 | continue; |
1099 | found = 1; | |
fde52b5c | 1100 | break; |
1101 | } | |
bbce6d69 | 1102 | if (!found) { |
1103 | entry = new_he(); | |
ff68c719 | 1104 | HeKEY_hek(entry) = save_hek(str, len, hash); |
bbce6d69 | 1105 | HeVAL(entry) = Nullsv; |
1106 | HeNEXT(entry) = *oentry; | |
1107 | *oentry = entry; | |
1108 | xhv->xhv_keys++; | |
1109 | if (i) { /* initial entry? */ | |
1110 | ++xhv->xhv_fill; | |
1111 | if (xhv->xhv_keys > xhv->xhv_max) | |
1112 | hsplit(strtab); | |
1113 | } | |
1114 | } | |
1115 | ||
1116 | ++HeVAL(entry); /* use value slot as REFCNT */ | |
ff68c719 | 1117 | return HeKEY_hek(entry); |
fde52b5c | 1118 | } |
1119 | ||
bbce6d69 | 1120 |