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,flags)
176 register HE **oentry;
181 if (SvRMAGICAL(hv)) {
182 sv = *hv_fetch(hv, key, klen, TRUE);
184 if (mg_find(sv, 'p')) {
185 sv_unmagic(sv, 'p'); /* No longer an element */
189 xhv = (XPVHV*)SvANY(hv);
196 hash = hash * 33 + *s++;
198 oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
201 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
202 if (entry->hent_hash != hash) /* strings can't be equal */
204 if (entry->hent_klen != klen)
206 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
208 *oentry = entry->hent_next;
211 if (flags & G_DISCARD)
214 sv = sv_mortalcopy(entry->hent_val);
215 if (entry == xhv->xhv_eiter)
216 entry->hent_klen = -1;
226 hv_exists(hv,key,klen)
241 if (SvRMAGICAL(hv)) {
242 if (mg_find((SV*)hv,'P')) {
244 mg_copy((SV*)hv, sv, key, klen);
245 magic_existspack(sv, mg_find(sv, 'p'));
250 xhv = (XPVHV*)SvANY(hv);
258 hash = hash * 33 + *s++;
260 entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
261 for (; entry; entry = entry->hent_next) {
262 if (entry->hent_hash != hash) /* strings can't be equal */
264 if (entry->hent_klen != klen)
266 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
277 register XPVHV* xhv = (XPVHV*)SvANY(hv);
278 I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */
279 register I32 newsize = oldsize * 2;
284 register HE **oentry;
286 a = (HE**)xhv->xhv_array;
288 Renew(a, newsize, HE*);
290 Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/
291 xhv->xhv_max = --newsize;
292 xhv->xhv_array = (char*)a;
294 for (i=0; i<oldsize; i++,a++) {
295 if (!*a) /* non-existent */
298 for (oentry = a, entry = *a; entry; entry = *oentry) {
299 if ((entry->hent_hash & newsize) != i) {
300 *oentry = entry->hent_next;
301 entry->hent_next = *b;
308 oentry = &entry->hent_next;
310 if (!*a) /* everything moved */
321 hv = (HV*)NEWSV(502,0);
322 sv_upgrade((SV *)hv, SVt_PVHV);
323 xhv = (XPVHV*)SvANY(hv);
326 xhv->xhv_max = 7; /* start with 8 buckets */
329 (void)hv_iterinit(hv); /* so each() will start off right */
339 SvREFCNT_dec(hent->hent_val);
340 Safefree(hent->hent_key);
350 sv_2mortal(hent->hent_val); /* free between statements */
351 Safefree(hent->hent_key);
362 xhv = (XPVHV*)SvANY(hv);
367 (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
379 register HE *ohent = Null(HE*);
395 hent = hent->hent_next;
404 (void)hv_iterinit(hv);
414 xhv = (XPVHV*)SvANY(hv);
416 Safefree(xhv->xhv_array);
418 Safefree(HvNAME(hv));
422 xhv->xhv_max = 7; /* it's a normal associative array */
434 register XPVHV* xhv = (XPVHV*)SvANY(hv);
435 HE *entry = xhv->xhv_eiter;
436 if (entry && entry->hent_klen < 0) /* was deleted earlier? */
439 xhv->xhv_eiter = Null(HE*);
440 return xhv->xhv_fill;
453 croak("Bad associative array");
454 xhv = (XPVHV*)SvANY(hv);
455 oldentry = entry = xhv->xhv_eiter;
457 if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
458 SV *key = sv_newmortal();
460 sv_usepvn(key, entry->hent_key, entry->hent_klen);
464 Newz(504,entry, 1, HE);
465 xhv->xhv_eiter = entry;
467 magic_nextpack((SV*) hv,mg,key);
470 entry->hent_key = SvPV_force(key, len);
471 entry->hent_klen = len;
477 SvREFCNT_dec(entry->hent_val);
479 xhv->xhv_eiter = Null(HE*);
484 Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
487 entry = entry->hent_next;
490 if (xhv->xhv_riter > xhv->xhv_max) {
494 entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
498 if (oldentry && oldentry->hent_klen < 0) /* was deleted earlier? */
501 xhv->xhv_eiter = entry;
506 hv_iterkey(entry,retlen)
510 *retlen = entry->hent_klen;
511 return entry->hent_key;
519 if (SvRMAGICAL(hv)) {
520 if (mg_find((SV*)hv,'P')) {
521 SV* sv = sv_newmortal();
522 mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
526 return entry->hent_val;
530 hv_iternextsv(hv, key, retlen)
536 if ( (he = hv_iternext(hv)) == NULL)
538 *key = hv_iterkey(he, retlen);
539 return hv_iterval(hv, he);
543 hv_magic(hv, gv, how)
548 sv_magic((SV*)hv, (SV*)gv, how, Nullch, 0);