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));
28 he_root = (HE*)he->hent_next;
38 p->hent_next = (HE*)he_root;
47 he_root = (HE*)safemalloc(1008);
49 heend = &he[1008 / sizeof(HE) - 1];
51 he->hent_next = (HE*)(he + 1);
59 hv_fetch(hv,key,klen,lval)
76 if (mg_find((SV*)hv,'P')) {
79 mg_copy((SV*)hv, sv, key, klen);
85 xhv = (XPVHV*)SvANY(hv);
86 if (!xhv->xhv_array) {
88 #ifdef DYNAMIC_ENV_FETCH /* if it's an %ENV lookup, we may get it on the fly */
89 || (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME))
92 Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
101 hash = hash * 33 + *s++;
103 entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
104 for (; entry; entry = entry->hent_next) {
105 if (entry->hent_hash != hash) /* strings can't be equal */
107 if (entry->hent_klen != klen)
109 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
111 return &entry->hent_val;
113 #ifdef DYNAMIC_ENV_FETCH /* %ENV lookup? If so, try to fetch the value now */
114 if (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) {
117 gotenv = my_getenv(key);
118 if (gotenv != NULL) {
119 sv = newSVpv(gotenv,strlen(gotenv));
120 return hv_store(hv,key,klen,sv,hash);
124 if (lval) { /* gonna assign to this, so it better be there */
126 return hv_store(hv,key,klen,sv,hash);
132 hv_store(hv,key,klen,val,hash)
143 register HE **oentry;
148 xhv = (XPVHV*)SvANY(hv);
150 mg_copy((SV*)hv, val, key, klen);
155 if (!xhv->xhv_array && (SvMAGIC(hv)->mg_type != 'A'
156 || SvMAGIC(hv)->mg_moremagic))
158 #endif /* OVERLOAD */
164 hash = hash * 33 + *s++;
168 Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);
170 oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
173 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
174 if (entry->hent_hash != hash) /* strings can't be equal */
176 if (entry->hent_klen != klen)
178 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
180 SvREFCNT_dec(entry->hent_val);
181 entry->hent_val = val;
182 return &entry->hent_val;
186 entry->hent_klen = klen;
187 entry->hent_key = savepvn(key,klen);
188 entry->hent_val = val;
189 entry->hent_hash = hash;
190 entry->hent_next = *oentry;
194 if (i) { /* initial entry? */
196 if (xhv->xhv_keys > xhv->xhv_max)
200 return &entry->hent_val;
204 hv_delete(hv,key,klen,flags)
215 register HE **oentry;
220 if (SvRMAGICAL(hv)) {
221 sv = *hv_fetch(hv, key, klen, TRUE);
223 if (mg_find(sv, 'p')) {
224 sv_unmagic(sv, 'p'); /* No longer an element */
228 xhv = (XPVHV*)SvANY(hv);
235 hash = hash * 33 + *s++;
237 oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
240 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
241 if (entry->hent_hash != hash) /* strings can't be equal */
243 if (entry->hent_klen != klen)
245 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
247 *oentry = entry->hent_next;
250 if (flags & G_DISCARD)
253 sv = sv_mortalcopy(entry->hent_val);
254 if (entry == xhv->xhv_eiter)
255 entry->hent_klen = -1;
265 hv_exists(hv,key,klen)
280 if (SvRMAGICAL(hv)) {
281 if (mg_find((SV*)hv,'P')) {
284 mg_copy((SV*)hv, sv, key, klen);
285 magic_existspack(sv, mg_find(sv, 'p'));
290 xhv = (XPVHV*)SvANY(hv);
298 hash = hash * 33 + *s++;
300 entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
301 for (; entry; entry = entry->hent_next) {
302 if (entry->hent_hash != hash) /* strings can't be equal */
304 if (entry->hent_klen != klen)
306 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
317 register XPVHV* xhv = (XPVHV*)SvANY(hv);
318 I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */
319 register I32 newsize = oldsize * 2;
324 register HE **oentry;
325 #ifndef STRANGE_MALLOC
329 a = (HE**)xhv->xhv_array;
331 #ifdef STRANGE_MALLOC
332 Renew(a, newsize, HE*);
334 i = newsize * sizeof(HE*);
335 #define MALLOC_OVERHEAD 16
336 tmp = MALLOC_OVERHEAD;
337 while (tmp - MALLOC_OVERHEAD < i)
339 tmp -= MALLOC_OVERHEAD;
341 assert(tmp >= newsize);
343 Copy(xhv->xhv_array, a, oldsize, HE*);
344 if (oldsize >= 64 && !nice_chunk) {
345 nice_chunk = (char*)xhv->xhv_array;
346 nice_chunk_size = oldsize * sizeof(HE*) * 2 - MALLOC_OVERHEAD;
349 Safefree(xhv->xhv_array);
353 Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/
354 xhv->xhv_max = --newsize;
355 xhv->xhv_array = (char*)a;
357 for (i=0; i<oldsize; i++,a++) {
358 if (!*a) /* non-existent */
361 for (oentry = a, entry = *a; entry; entry = *oentry) {
362 if ((entry->hent_hash & newsize) != i) {
363 *oentry = entry->hent_next;
364 entry->hent_next = *b;
371 oentry = &entry->hent_next;
373 if (!*a) /* everything moved */
384 hv = (HV*)NEWSV(502,0);
385 sv_upgrade((SV *)hv, SVt_PVHV);
386 xhv = (XPVHV*)SvANY(hv);
389 xhv->xhv_max = 7; /* start with 8 buckets */
392 (void)hv_iterinit(hv); /* so each() will start off right */
402 SvREFCNT_dec(hent->hent_val);
403 Safefree(hent->hent_key);
413 sv_2mortal(hent->hent_val); /* free between statements */
414 Safefree(hent->hent_key);
425 xhv = (XPVHV*)SvANY(hv);
430 (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
442 register HE *ohent = Null(HE*);
458 hent = hent->hent_next;
467 (void)hv_iterinit(hv);
477 xhv = (XPVHV*)SvANY(hv);
479 Safefree(xhv->xhv_array);
481 Safefree(HvNAME(hv));
485 xhv->xhv_max = 7; /* it's a normal associative array */
497 register XPVHV* xhv = (XPVHV*)SvANY(hv);
498 HE *entry = xhv->xhv_eiter;
499 if (entry && entry->hent_klen < 0) /* was deleted earlier? */
502 xhv->xhv_eiter = Null(HE*);
503 return xhv->xhv_fill;
516 croak("Bad associative array");
517 xhv = (XPVHV*)SvANY(hv);
518 oldentry = entry = xhv->xhv_eiter;
520 if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
521 SV *key = sv_newmortal();
523 sv_usepvn(key, entry->hent_key, entry->hent_klen);
527 xhv->xhv_eiter = entry = new_he();
530 magic_nextpack((SV*) hv,mg,key);
533 entry->hent_key = SvPV_force(key, len);
534 entry->hent_klen = len;
540 SvREFCNT_dec(entry->hent_val);
542 xhv->xhv_eiter = Null(HE*);
547 Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
550 entry = entry->hent_next;
553 if (xhv->xhv_riter > xhv->xhv_max) {
557 entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
561 if (oldentry && oldentry->hent_klen < 0) /* was deleted earlier? */
564 xhv->xhv_eiter = entry;
569 hv_iterkey(entry,retlen)
573 *retlen = entry->hent_klen;
574 return entry->hent_key;
582 if (SvRMAGICAL(hv)) {
583 if (mg_find((SV*)hv,'P')) {
584 SV* sv = sv_newmortal();
585 mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
589 return entry->hent_val;
593 hv_iternextsv(hv, key, retlen)
599 if ( (he = hv_iternext(hv)) == NULL)
601 *key = hv_iterkey(he, retlen);
602 return hv_iterval(hv, he);
606 hv_magic(hv, gv, how)
611 sv_magic((SV*)hv, (SV*)gv, how, Nullch, 0);