3 * Copyright (c) 1991-1994, Larry Wall
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.
11 * "I sit beside the fire and think of all that I have seen." --Bilbo
17 static void hsplit _((HV *hv));
18 static void hfreeentries _((HV *hv));
21 hv_fetch(hv,key,klen,lval)
38 if (mg_find((SV*)hv,'P')) {
40 mg_copy((SV*)hv, sv, key, klen);
46 xhv = (XPVHV*)SvANY(hv);
47 if (!xhv->xhv_array) {
49 #ifdef DYNAMIC_ENV_FETCH /* if it's an %ENV lookup, we may get it on the fly */
50 || (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME))
53 Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
62 hash = hash * 33 + *s++;
64 entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
65 for (; entry; entry = entry->hent_next) {
66 if (entry->hent_hash != hash) /* strings can't be equal */
68 if (entry->hent_klen != klen)
70 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
72 return &entry->hent_val;
74 #ifdef DYNAMIC_ENV_FETCH /* %ENV lookup? If so, try to fetch the value now */
75 if (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) {
78 gotenv = my_getenv(key);
80 sv = newSVpv(gotenv,strlen(gotenv));
81 return hv_store(hv,key,klen,sv,hash);
85 if (lval) { /* gonna assign to this, so it better be there */
87 return hv_store(hv,key,klen,sv,hash);
93 hv_store(hv,key,klen,val,hash)
104 register HE **oentry;
109 xhv = (XPVHV*)SvANY(hv);
111 mg_copy((SV*)hv, val, key, klen);
116 if (!xhv->xhv_array && (SvMAGIC(hv)->mg_type != 'A'
117 || SvMAGIC(hv)->mg_moremagic))
119 #endif /* OVERLOAD */
125 hash = hash * 33 + *s++;
129 Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);
131 oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
134 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
135 if (entry->hent_hash != hash) /* strings can't be equal */
137 if (entry->hent_klen != klen)
139 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
141 SvREFCNT_dec(entry->hent_val);
142 entry->hent_val = val;
143 return &entry->hent_val;
145 New(501,entry, 1, HE);
147 entry->hent_klen = klen;
148 entry->hent_key = savepvn(key,klen);
149 entry->hent_val = val;
150 entry->hent_hash = hash;
151 entry->hent_next = *oentry;
155 if (i) { /* initial entry? */
157 if (xhv->xhv_keys > xhv->xhv_max)
161 return &entry->hent_val;
165 hv_delete(hv,key,klen)
175 register HE **oentry;
180 if (SvRMAGICAL(hv)) {
181 sv = *hv_fetch(hv, key, klen, TRUE);
183 if (mg_find(sv, 'p')) {
184 sv_unmagic(sv, 'p'); /* No longer an element */
188 xhv = (XPVHV*)SvANY(hv);
195 hash = hash * 33 + *s++;
197 oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
200 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
201 if (entry->hent_hash != hash) /* strings can't be equal */
203 if (entry->hent_klen != klen)
205 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
207 *oentry = entry->hent_next;
210 sv = sv_mortalcopy(entry->hent_val);
211 if (entry == xhv->xhv_eiter)
212 entry->hent_klen = -1;
222 hv_exists(hv,key,klen)
237 if (SvRMAGICAL(hv)) {
238 if (mg_find((SV*)hv,'P')) {
240 mg_copy((SV*)hv, sv, key, klen);
241 magic_existspack(sv, mg_find(sv, 'p'));
246 xhv = (XPVHV*)SvANY(hv);
254 hash = hash * 33 + *s++;
256 entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
257 for (; entry; entry = entry->hent_next) {
258 if (entry->hent_hash != hash) /* strings can't be equal */
260 if (entry->hent_klen != klen)
262 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
273 register XPVHV* xhv = (XPVHV*)SvANY(hv);
274 I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */
275 register I32 newsize = oldsize * 2;
280 register HE **oentry;
282 a = (HE**)xhv->xhv_array;
284 Renew(a, newsize, HE*);
286 Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/
287 xhv->xhv_max = --newsize;
288 xhv->xhv_array = (char*)a;
290 for (i=0; i<oldsize; i++,a++) {
291 if (!*a) /* non-existent */
294 for (oentry = a, entry = *a; entry; entry = *oentry) {
295 if ((entry->hent_hash & newsize) != i) {
296 *oentry = entry->hent_next;
297 entry->hent_next = *b;
304 oentry = &entry->hent_next;
306 if (!*a) /* everything moved */
317 hv = (HV*)NEWSV(502,0);
318 sv_upgrade((SV *)hv, SVt_PVHV);
319 xhv = (XPVHV*)SvANY(hv);
322 xhv->xhv_max = 7; /* start with 8 buckets */
325 (void)hv_iterinit(hv); /* so each() will start off right */
335 SvREFCNT_dec(hent->hent_val);
336 Safefree(hent->hent_key);
346 sv_2mortal(hent->hent_val); /* free between statements */
347 Safefree(hent->hent_key);
358 xhv = (XPVHV*)SvANY(hv);
363 (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
375 register HE *ohent = Null(HE*);
391 hent = hent->hent_next;
400 (void)hv_iterinit(hv);
410 xhv = (XPVHV*)SvANY(hv);
412 Safefree(xhv->xhv_array);
414 Safefree(HvNAME(hv));
418 xhv->xhv_max = 7; /* it's a normal associative array */
430 register XPVHV* xhv = (XPVHV*)SvANY(hv);
431 HE *entry = xhv->xhv_eiter;
432 if (entry && entry->hent_klen < 0) /* was deleted earlier? */
435 xhv->xhv_eiter = Null(HE*);
436 return xhv->xhv_fill;
449 croak("Bad associative array");
450 xhv = (XPVHV*)SvANY(hv);
451 oldentry = entry = xhv->xhv_eiter;
453 if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
454 SV *key = sv_newmortal();
456 sv_usepvn(key, entry->hent_key, entry->hent_klen);
460 Newz(504,entry, 1, HE);
461 xhv->xhv_eiter = entry;
463 magic_nextpack((SV*) hv,mg,key);
466 entry->hent_key = SvPV_force(key, len);
467 entry->hent_klen = len;
473 SvREFCNT_dec(entry->hent_val);
475 xhv->xhv_eiter = Null(HE*);
480 Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
483 entry = entry->hent_next;
486 if (xhv->xhv_riter > xhv->xhv_max) {
490 entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
494 if (oldentry && oldentry->hent_klen < 0) /* was deleted earlier? */
497 xhv->xhv_eiter = entry;
502 hv_iterkey(entry,retlen)
506 *retlen = entry->hent_klen;
507 return entry->hent_key;
515 if (SvRMAGICAL(hv)) {
516 if (mg_find((SV*)hv,'P')) {
517 SV* sv = sv_newmortal();
518 mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
522 return entry->hent_val;
526 hv_iternextsv(hv, key, retlen)
532 if ( (he = hv_iternext(hv)) == NULL)
534 *key = hv_iterkey(he, retlen);
535 return hv_iterval(hv, he);
539 hv_magic(hv, gv, how)
544 sv_magic((SV*)hv, (SV*)gv, how, Nullch, 0);