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 |
44a8e56a | 426 | he_free(hv, entry); |
fde52b5c | 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 |
44a8e56a | 488 | he_free(hv, entry); |
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 | |
44a8e56a | 749 | he_free(hv, hent) |
750 | HV *hv; | |
79072805 LW |
751 | register HE *hent; |
752 | { | |
753 | if (!hent) | |
754 | return; | |
44a8e56a | 755 | if (isGV(HeVAL(hent)) && GvCVu(HeVAL(hent)) && HvNAME(hv)) |
756 | sub_generation++; /* may be deletion of method from stash */ | |
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)); |
44a8e56a | 761 | } |
762 | else if (HvSHAREKEYS(hv)) | |
ff68c719 | 763 | unshare_hek(HeKEY_hek(hent)); |
fde52b5c | 764 | else |
ff68c719 | 765 | Safefree(HeKEY_hek(hent)); |
4633a7c4 | 766 | del_he(hent); |
79072805 LW |
767 | } |
768 | ||
769 | void | |
44a8e56a | 770 | he_delayfree(hv, hent) |
771 | HV *hv; | |
79072805 LW |
772 | register HE *hent; |
773 | { | |
774 | if (!hent) | |
775 | return; | |
44a8e56a | 776 | if (isGV(HeVAL(hent)) && GvCVu(HeVAL(hent)) && HvNAME(hv)) |
777 | sub_generation++; /* may be deletion of method from stash */ | |
fde52b5c | 778 | sv_2mortal(HeVAL(hent)); /* free between statements */ |
bbce6d69 | 779 | if (HeKLEN(hent) == HEf_SVKEY) { |
780 | sv_2mortal(HeKEY_sv(hent)); | |
ff68c719 | 781 | Safefree(HeKEY_hek(hent)); |
44a8e56a | 782 | } |
783 | else if (HvSHAREKEYS(hv)) | |
ff68c719 | 784 | unshare_hek(HeKEY_hek(hent)); |
fde52b5c | 785 | else |
ff68c719 | 786 | Safefree(HeKEY_hek(hent)); |
4633a7c4 | 787 | del_he(hent); |
79072805 LW |
788 | } |
789 | ||
790 | void | |
463ee0b2 | 791 | hv_clear(hv) |
79072805 | 792 | HV *hv; |
79072805 LW |
793 | { |
794 | register XPVHV* xhv; | |
795 | if (!hv) | |
796 | return; | |
797 | xhv = (XPVHV*)SvANY(hv); | |
463ee0b2 | 798 | hfreeentries(hv); |
79072805 | 799 | xhv->xhv_fill = 0; |
a0d0e21e | 800 | xhv->xhv_keys = 0; |
79072805 | 801 | if (xhv->xhv_array) |
463ee0b2 | 802 | (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*)); |
a0d0e21e LW |
803 | |
804 | if (SvRMAGICAL(hv)) | |
805 | mg_clear((SV*)hv); | |
79072805 LW |
806 | } |
807 | ||
808 | static void | |
463ee0b2 | 809 | hfreeentries(hv) |
79072805 | 810 | HV *hv; |
79072805 | 811 | { |
a0d0e21e | 812 | register HE **array; |
79072805 LW |
813 | register HE *hent; |
814 | register HE *ohent = Null(HE*); | |
a0d0e21e LW |
815 | I32 riter; |
816 | I32 max; | |
79072805 LW |
817 | |
818 | if (!hv) | |
819 | return; | |
a0d0e21e | 820 | if (!HvARRAY(hv)) |
79072805 | 821 | return; |
a0d0e21e LW |
822 | |
823 | riter = 0; | |
824 | max = HvMAX(hv); | |
825 | array = HvARRAY(hv); | |
826 | hent = array[0]; | |
827 | for (;;) { | |
828 | if (hent) { | |
829 | ohent = hent; | |
fde52b5c | 830 | hent = HeNEXT(hent); |
44a8e56a | 831 | he_free(hv, ohent); |
a0d0e21e LW |
832 | } |
833 | if (!hent) { | |
834 | if (++riter > max) | |
835 | break; | |
836 | hent = array[riter]; | |
837 | } | |
79072805 | 838 | } |
a0d0e21e | 839 | (void)hv_iterinit(hv); |
79072805 LW |
840 | } |
841 | ||
842 | void | |
463ee0b2 | 843 | hv_undef(hv) |
79072805 | 844 | HV *hv; |
79072805 LW |
845 | { |
846 | register XPVHV* xhv; | |
847 | if (!hv) | |
848 | return; | |
849 | xhv = (XPVHV*)SvANY(hv); | |
463ee0b2 | 850 | hfreeentries(hv); |
79072805 | 851 | Safefree(xhv->xhv_array); |
85e6fe83 LW |
852 | if (HvNAME(hv)) { |
853 | Safefree(HvNAME(hv)); | |
854 | HvNAME(hv) = 0; | |
855 | } | |
79072805 | 856 | xhv->xhv_array = 0; |
463ee0b2 | 857 | xhv->xhv_max = 7; /* it's a normal associative array */ |
79072805 | 858 | xhv->xhv_fill = 0; |
a0d0e21e LW |
859 | xhv->xhv_keys = 0; |
860 | ||
861 | if (SvRMAGICAL(hv)) | |
862 | mg_clear((SV*)hv); | |
79072805 LW |
863 | } |
864 | ||
79072805 LW |
865 | I32 |
866 | hv_iterinit(hv) | |
867 | HV *hv; | |
868 | { | |
869 | register XPVHV* xhv = (XPVHV*)SvANY(hv); | |
a0d0e21e | 870 | HE *entry = xhv->xhv_eiter; |
effa1e2d | 871 | #ifdef DYNAMIC_ENV_FETCH /* set up %ENV for iteration */ |
872 | if (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) prime_env_iter(); | |
873 | #endif | |
72940dca | 874 | if (entry && HvLAZYDEL(hv)) { /* was deleted earlier? */ |
875 | HvLAZYDEL_off(hv); | |
44a8e56a | 876 | he_free(hv, entry); |
72940dca | 877 | } |
79072805 LW |
878 | xhv->xhv_riter = -1; |
879 | xhv->xhv_eiter = Null(HE*); | |
880 | return xhv->xhv_fill; | |
881 | } | |
882 | ||
883 | HE * | |
884 | hv_iternext(hv) | |
885 | HV *hv; | |
886 | { | |
887 | register XPVHV* xhv; | |
888 | register HE *entry; | |
a0d0e21e | 889 | HE *oldentry; |
463ee0b2 | 890 | MAGIC* mg; |
79072805 LW |
891 | |
892 | if (!hv) | |
463ee0b2 | 893 | croak("Bad associative array"); |
79072805 | 894 | xhv = (XPVHV*)SvANY(hv); |
a0d0e21e | 895 | oldentry = entry = xhv->xhv_eiter; |
463ee0b2 | 896 | |
8990e307 LW |
897 | if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) { |
898 | SV *key = sv_newmortal(); | |
cd1469e6 | 899 | if (entry) { |
fde52b5c | 900 | sv_setsv(key, HeSVKEY_force(entry)); |
cd1469e6 | 901 | SvREFCNT_dec(HeSVKEY(entry)); /* get rid of previous key */ |
902 | } | |
a0d0e21e | 903 | else { |
ff68c719 | 904 | char *k; |
bbce6d69 | 905 | HEK *hek; |
ff68c719 | 906 | |
907 | xhv->xhv_eiter = entry = new_he(); /* one HE per MAGICAL hash */ | |
4633a7c4 | 908 | Zero(entry, 1, HE); |
ff68c719 | 909 | Newz(54, k, HEK_BASESIZE + sizeof(SV*), char); |
910 | hek = (HEK*)k; | |
911 | HeKEY_hek(entry) = hek; | |
fde52b5c | 912 | HeKLEN(entry) = HEf_SVKEY; |
a0d0e21e LW |
913 | } |
914 | magic_nextpack((SV*) hv,mg,key); | |
463ee0b2 | 915 | if (SvOK(key)) { |
cd1469e6 | 916 | /* force key to stay around until next time */ |
bbce6d69 | 917 | HeSVKEY_set(entry, SvREFCNT_inc(key)); |
918 | return entry; /* beware, hent_val is not set */ | |
463ee0b2 | 919 | } |
fde52b5c | 920 | if (HeVAL(entry)) |
921 | SvREFCNT_dec(HeVAL(entry)); | |
ff68c719 | 922 | Safefree(HeKEY_hek(entry)); |
4633a7c4 | 923 | del_he(entry); |
463ee0b2 LW |
924 | xhv->xhv_eiter = Null(HE*); |
925 | return Null(HE*); | |
79072805 | 926 | } |
463ee0b2 | 927 | |
79072805 | 928 | if (!xhv->xhv_array) |
4633a7c4 | 929 | Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char); |
fde52b5c | 930 | if (entry) |
931 | entry = HeNEXT(entry); | |
932 | while (!entry) { | |
933 | ++xhv->xhv_riter; | |
934 | if (xhv->xhv_riter > xhv->xhv_max) { | |
935 | xhv->xhv_riter = -1; | |
936 | break; | |
79072805 | 937 | } |
fde52b5c | 938 | entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter]; |
939 | } | |
79072805 | 940 | |
72940dca | 941 | if (oldentry && HvLAZYDEL(hv)) { /* was deleted earlier? */ |
942 | HvLAZYDEL_off(hv); | |
44a8e56a | 943 | he_free(hv, oldentry); |
72940dca | 944 | } |
a0d0e21e | 945 | |
79072805 LW |
946 | xhv->xhv_eiter = entry; |
947 | return entry; | |
948 | } | |
949 | ||
950 | char * | |
951 | hv_iterkey(entry,retlen) | |
952 | register HE *entry; | |
953 | I32 *retlen; | |
954 | { | |
fde52b5c | 955 | if (HeKLEN(entry) == HEf_SVKEY) { |
bbce6d69 | 956 | return SvPV(HeKEY_sv(entry), *(STRLEN*)retlen); |
fde52b5c | 957 | } |
958 | else { | |
959 | *retlen = HeKLEN(entry); | |
960 | return HeKEY(entry); | |
961 | } | |
962 | } | |
963 | ||
964 | /* unlike hv_iterval(), this always returns a mortal copy of the key */ | |
965 | SV * | |
966 | hv_iterkeysv(entry) | |
967 | register HE *entry; | |
968 | { | |
969 | if (HeKLEN(entry) == HEf_SVKEY) | |
bbce6d69 | 970 | return sv_mortalcopy(HeKEY_sv(entry)); |
fde52b5c | 971 | else |
972 | return sv_2mortal(newSVpv((HeKLEN(entry) ? HeKEY(entry) : ""), | |
973 | HeKLEN(entry))); | |
79072805 LW |
974 | } |
975 | ||
976 | SV * | |
977 | hv_iterval(hv,entry) | |
978 | HV *hv; | |
979 | register HE *entry; | |
980 | { | |
8990e307 | 981 | if (SvRMAGICAL(hv)) { |
463ee0b2 | 982 | if (mg_find((SV*)hv,'P')) { |
8990e307 | 983 | SV* sv = sv_newmortal(); |
bbce6d69 | 984 | if (HeKLEN(entry) == HEf_SVKEY) |
985 | mg_copy((SV*)hv, sv, (char*)HeKEY_sv(entry), HEf_SVKEY); | |
986 | else mg_copy((SV*)hv, sv, HeKEY(entry), HeKLEN(entry)); | |
463ee0b2 LW |
987 | return sv; |
988 | } | |
79072805 | 989 | } |
fde52b5c | 990 | return HeVAL(entry); |
79072805 LW |
991 | } |
992 | ||
a0d0e21e LW |
993 | SV * |
994 | hv_iternextsv(hv, key, retlen) | |
995 | HV *hv; | |
996 | char **key; | |
997 | I32 *retlen; | |
998 | { | |
999 | HE *he; | |
1000 | if ( (he = hv_iternext(hv)) == NULL) | |
1001 | return NULL; | |
1002 | *key = hv_iterkey(he, retlen); | |
1003 | return hv_iterval(hv, he); | |
1004 | } | |
1005 | ||
79072805 LW |
1006 | void |
1007 | hv_magic(hv, gv, how) | |
1008 | HV* hv; | |
1009 | GV* gv; | |
a0d0e21e | 1010 | int how; |
79072805 | 1011 | { |
a0d0e21e | 1012 | sv_magic((SV*)hv, (SV*)gv, how, Nullch, 0); |
79072805 | 1013 | } |
fde52b5c | 1014 | |
bbce6d69 | 1015 | char* |
1016 | sharepvn(sv, len, hash) | |
1017 | char* sv; | |
1018 | I32 len; | |
1019 | U32 hash; | |
1020 | { | |
ff68c719 | 1021 | return HEK_KEY(share_hek(sv, len, hash)); |
bbce6d69 | 1022 | } |
1023 | ||
1024 | /* possibly free a shared string if no one has access to it | |
fde52b5c | 1025 | * len and hash must both be valid for str. |
1026 | */ | |
bbce6d69 | 1027 | void |
1028 | unsharepvn(str, len, hash) | |
1029 | char* str; | |
fde52b5c | 1030 | I32 len; |
bbce6d69 | 1031 | U32 hash; |
fde52b5c | 1032 | { |
1033 | register XPVHV* xhv; | |
1034 | register HE *entry; | |
1035 | register HE **oentry; | |
1036 | register I32 i = 1; | |
1037 | I32 found = 0; | |
bbce6d69 | 1038 | |
fde52b5c | 1039 | /* what follows is the moral equivalent of: |
bbce6d69 | 1040 | if ((Svp = hv_fetch(strtab, tmpsv, FALSE, hash))) { |
1041 | if (--*Svp == Nullsv) | |
1042 | hv_delete(strtab, str, len, G_DISCARD, hash); | |
1043 | } */ | |
fde52b5c | 1044 | xhv = (XPVHV*)SvANY(strtab); |
1045 | /* assert(xhv_array != 0) */ | |
1046 | oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; | |
bbce6d69 | 1047 | for (entry = *oentry; entry; i=0, oentry = &HeNEXT(entry), entry = *oentry) { |
fde52b5c | 1048 | if (HeHASH(entry) != hash) /* strings can't be equal */ |
1049 | continue; | |
1050 | if (HeKLEN(entry) != len) | |
1051 | continue; | |
36477c24 | 1052 | if (memNE(HeKEY(entry),str,len)) /* is this it? */ |
fde52b5c | 1053 | continue; |
1054 | found = 1; | |
bbce6d69 | 1055 | if (--HeVAL(entry) == Nullsv) { |
1056 | *oentry = HeNEXT(entry); | |
1057 | if (i && !*oentry) | |
1058 | xhv->xhv_fill--; | |
ff68c719 | 1059 | Safefree(HeKEY_hek(entry)); |
bbce6d69 | 1060 | del_he(entry); |
1061 | --xhv->xhv_keys; | |
fde52b5c | 1062 | } |
bbce6d69 | 1063 | break; |
fde52b5c | 1064 | } |
bbce6d69 | 1065 | |
1066 | if (!found) | |
1067 | warn("Attempt to free non-existent shared string"); | |
fde52b5c | 1068 | } |
1069 | ||
bbce6d69 | 1070 | /* get a (constant) string ptr from the global string table |
1071 | * string will get added if it is not already there. | |
fde52b5c | 1072 | * len and hash must both be valid for str. |
1073 | */ | |
bbce6d69 | 1074 | HEK * |
1075 | share_hek(str, len, hash) | |
fde52b5c | 1076 | char *str; |
1077 | I32 len; | |
1078 | register U32 hash; | |
1079 | { | |
1080 | register XPVHV* xhv; | |
1081 | register HE *entry; | |
1082 | register HE **oentry; | |
1083 | register I32 i = 1; | |
1084 | I32 found = 0; | |
bbce6d69 | 1085 | |
fde52b5c | 1086 | /* what follows is the moral equivalent of: |
bbce6d69 | 1087 | |
1088 | if (!(Svp = hv_fetch(strtab, str, len, FALSE))) | |
1089 | hv_store(strtab, str, len, Nullsv, hash); | |
1090 | */ | |
fde52b5c | 1091 | xhv = (XPVHV*)SvANY(strtab); |
1092 | /* assert(xhv_array != 0) */ | |
1093 | oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max]; | |
bbce6d69 | 1094 | for (entry = *oentry; entry; i=0, entry = HeNEXT(entry)) { |
fde52b5c | 1095 | if (HeHASH(entry) != hash) /* strings can't be equal */ |
1096 | continue; | |
1097 | if (HeKLEN(entry) != len) | |
1098 | continue; | |
36477c24 | 1099 | if (memNE(HeKEY(entry),str,len)) /* is this it? */ |
fde52b5c | 1100 | continue; |
1101 | found = 1; | |
fde52b5c | 1102 | break; |
1103 | } | |
bbce6d69 | 1104 | if (!found) { |
1105 | entry = new_he(); | |
ff68c719 | 1106 | HeKEY_hek(entry) = save_hek(str, len, hash); |
bbce6d69 | 1107 | HeVAL(entry) = Nullsv; |
1108 | HeNEXT(entry) = *oentry; | |
1109 | *oentry = entry; | |
1110 | xhv->xhv_keys++; | |
1111 | if (i) { /* initial entry? */ | |
1112 | ++xhv->xhv_fill; | |
1113 | if (xhv->xhv_keys > xhv->xhv_max) | |
1114 | hsplit(strtab); | |
1115 | } | |
1116 | } | |
1117 | ||
1118 | ++HeVAL(entry); /* use value slot as REFCNT */ | |
ff68c719 | 1119 | return HeKEY_hek(entry); |
fde52b5c | 1120 | } |
1121 | ||
bbce6d69 | 1122 |