[perl5.git] / hv.c

/*    hv.c
 *
 *    Copyright (c) 1991-1994, Larry Wall
 *
 *    You may distribute under the terms of either the GNU General Public
 *    License or the Artistic License, as specified in the README file.
 *
 */

/*
 * "I sit beside the fire and think of all that I have seen."  --Bilbo
 */

#include "EXTERN.h"
#include "perl.h"

static void hsplit _((HV *hv));
static void hfreeentries _((HV *hv));

SV**
hv_fetch(hv,key,klen,lval)
HV *hv;
char *key;
U32 klen;
I32 lval;
{
    register XPVHV* xhv;
    register char *s;
    register I32 i;
    register I32 hash;
    register HE *entry;
    SV *sv;

    if (!hv)
	return 0;

    if (SvRMAGICAL(hv)) {
	if (mg_find((SV*)hv,'P')) {
	    sv = sv_newmortal();
	    mg_copy((SV*)hv, sv, key, klen);
	    Sv = sv;
	    return &Sv;
	}
    }

    xhv = (XPVHV*)SvANY(hv);
    if (!xhv->xhv_array) {
	if (lval 
#ifdef DYNAMIC_ENV_FETCH  /* if it's an %ENV lookup, we may get it on the fly */
	         || (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME))
#endif
	                                                          )
	    Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
	else
	    return 0;
    }

    i = klen;
    hash = 0;
    s = key;
    while (i--)
	hash = hash * 33 + *s++;

    entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
    for (; entry; entry = entry->hent_next) {
	if (entry->hent_hash != hash)		/* strings can't be equal */
	    continue;
	if (entry->hent_klen != klen)
	    continue;
	if (bcmp(entry->hent_key,key,klen))	/* is this it? */
	    continue;
	return &entry->hent_val;
    }
#ifdef DYNAMIC_ENV_FETCH  /* %ENV lookup?  If so, try to fetch the value now */
    if (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) {
      char *gotenv;

      gotenv = my_getenv(key);
      if (gotenv != NULL) {
        sv = newSVpv(gotenv,strlen(gotenv));
        return hv_store(hv,key,klen,sv,hash);
      }
    }
#endif
    if (lval) {		/* gonna assign to this, so it better be there */
	sv = NEWSV(61,0);
	return hv_store(hv,key,klen,sv,hash);
    }
    return 0;
}

SV**
hv_store(hv,key,klen,val,hash)
HV *hv;
char *key;
U32 klen;
SV *val;
register U32 hash;
{
    register XPVHV* xhv;
    register char *s;
    register I32 i;
    register HE *entry;
    register HE **oentry;

    if (!hv)
	return 0;

    xhv = (XPVHV*)SvANY(hv);
    if (SvMAGICAL(hv)) {
	mg_copy((SV*)hv, val, key, klen);
#ifndef OVERLOAD
	if (!xhv->xhv_array)
	    return 0;
#else
	if (!xhv->xhv_array && (SvMAGIC(hv)->mg_type != 'A'
				|| SvMAGIC(hv)->mg_moremagic))
	  return 0;
#endif /* OVERLOAD */
    }
    if (!hash) {
    i = klen;
    s = key;
    while (i--)
	hash = hash * 33 + *s++;
    }

    if (!xhv->xhv_array)
	Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);

    oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
    i = 1;

    for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
	if (entry->hent_hash != hash)		/* strings can't be equal */
	    continue;
	if (entry->hent_klen != klen)
	    continue;
	if (bcmp(entry->hent_key,key,klen))	/* is this it? */
	    continue;
	SvREFCNT_dec(entry->hent_val);
	entry->hent_val = val;
	return &entry->hent_val;
    }
    New(501,entry, 1, HE);

    entry->hent_klen = klen;
    entry->hent_key = savepvn(key,klen);
    entry->hent_val = val;
    entry->hent_hash = hash;
    entry->hent_next = *oentry;
    *oentry = entry;

    xhv->xhv_keys++;
    if (i) {				/* initial entry? */
	++xhv->xhv_fill;
	if (xhv->xhv_keys > xhv->xhv_max)
	    hsplit(hv);
    }

    return &entry->hent_val;
}

SV *
hv_delete(hv,key,klen,flags)
HV *hv;
char *key;
U32 klen;
I32 flags;
{
    register XPVHV* xhv;
    register char *s;
    register I32 i;
    register I32 hash;
    register HE *entry;
    register HE **oentry;
    SV *sv;

    if (!hv)
	return Nullsv;
    if (SvRMAGICAL(hv)) {
	sv = *hv_fetch(hv, key, klen, TRUE);
	mg_clear(sv);
	if (mg_find(sv, 'p')) {
	    sv_unmagic(sv, 'p');	/* No longer an element */
	    return sv;
	}
    }
    xhv = (XPVHV*)SvANY(hv);
    if (!xhv->xhv_array)
	return Nullsv;
    i = klen;
    hash = 0;
    s = key;
    while (i--)
	hash = hash * 33 + *s++;

    oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
    entry = *oentry;
    i = 1;
    for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
	if (entry->hent_hash != hash)		/* strings can't be equal */
	    continue;
	if (entry->hent_klen != klen)
	    continue;
	if (bcmp(entry->hent_key,key,klen))	/* is this it? */
	    continue;
	*oentry = entry->hent_next;
	if (i && !*oentry)
	    xhv->xhv_fill--;
	if (flags & G_DISCARD)
	    sv = Nullsv;
	else
	    sv = sv_mortalcopy(entry->hent_val);
	if (entry == xhv->xhv_eiter)
	    entry->hent_klen = -1;
	else
	    he_free(entry);
	--xhv->xhv_keys;
	return sv;
    }
    return Nullsv;
}

bool
hv_exists(hv,key,klen)
HV *hv;
char *key;
U32 klen;
{
    register XPVHV* xhv;
    register char *s;
    register I32 i;
    register I32 hash;
    register HE *entry;
    SV *sv;

    if (!hv)
	return 0;

    if (SvRMAGICAL(hv)) {
	if (mg_find((SV*)hv,'P')) {
	    sv = sv_newmortal();
	    mg_copy((SV*)hv, sv, key, klen); 
	    magic_existspack(sv, mg_find(sv, 'p'));
	    return SvTRUE(sv);
	}
    }

    xhv = (XPVHV*)SvANY(hv);
    if (!xhv->xhv_array)
	return 0; 

    i = klen;
    hash = 0;
    s = key;
    while (i--)
	hash = hash * 33 + *s++;

    entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
    for (; entry; entry = entry->hent_next) {
	if (entry->hent_hash != hash)		/* strings can't be equal */
	    continue;
	if (entry->hent_klen != klen)
	    continue;
	if (bcmp(entry->hent_key,key,klen))	/* is this it? */
	    continue;
	return TRUE;
    }
    return FALSE;
}

static void
hsplit(hv)
HV *hv;
{
    register XPVHV* xhv = (XPVHV*)SvANY(hv);
    I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */
    register I32 newsize = oldsize * 2;
    register I32 i;
    register HE **a;
    register HE **b;
    register HE *entry;
    register HE **oentry;

    a = (HE**)xhv->xhv_array;
    nomemok = TRUE;
    Renew(a, newsize, HE*);
    nomemok = FALSE;
    Zero(&a[oldsize], oldsize, HE*);		/* zero 2nd half*/
    xhv->xhv_max = --newsize;
    xhv->xhv_array = (char*)a;

    for (i=0; i<oldsize; i++,a++) {
	if (!*a)				/* non-existent */
	    continue;
	b = a+oldsize;
	for (oentry = a, entry = *a; entry; entry = *oentry) {
	    if ((entry->hent_hash & newsize) != i) {
		*oentry = entry->hent_next;
		entry->hent_next = *b;
		if (!*b)
		    xhv->xhv_fill++;
		*b = entry;
		continue;
	    }
	    else
		oentry = &entry->hent_next;
	}
	if (!*a)				/* everything moved */
	    xhv->xhv_fill--;
    }
}

HV *
newHV()
{
    register HV *hv;
    register XPVHV* xhv;

    hv = (HV*)NEWSV(502,0);
    sv_upgrade((SV *)hv, SVt_PVHV);
    xhv = (XPVHV*)SvANY(hv);
    SvPOK_off(hv);
    SvNOK_off(hv);
    xhv->xhv_max = 7;		/* start with 8 buckets */
    xhv->xhv_fill = 0;
    xhv->xhv_pmroot = 0;
    (void)hv_iterinit(hv);	/* so each() will start off right */
    return hv;
}

void
he_free(hent)
register HE *hent;
{
    if (!hent)
	return;
    SvREFCNT_dec(hent->hent_val);
    Safefree(hent->hent_key);
    Safefree(hent);
}

void
he_delayfree(hent)
register HE *hent;
{
    if (!hent)
	return;
    sv_2mortal(hent->hent_val);	/* free between statements */
    Safefree(hent->hent_key);
    Safefree(hent);
}

void
hv_clear(hv)
HV *hv;
{
    register XPVHV* xhv;
    if (!hv)
	return;
    xhv = (XPVHV*)SvANY(hv);
    hfreeentries(hv);
    xhv->xhv_fill = 0;
    xhv->xhv_keys = 0;
    if (xhv->xhv_array)
	(void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));

    if (SvRMAGICAL(hv))
	mg_clear((SV*)hv); 
}

static void
hfreeentries(hv)
HV *hv;
{
    register HE **array;
    register HE *hent;
    register HE *ohent = Null(HE*);
    I32 riter;
    I32 max;

    if (!hv)
	return;
    if (!HvARRAY(hv))
	return;

    riter = 0;
    max = HvMAX(hv);
    array = HvARRAY(hv);
    hent = array[0];
    for (;;) {
	if (hent) {
	    ohent = hent;
	    hent = hent->hent_next;
	    he_free(ohent);
	}
	if (!hent) {
	    if (++riter > max)
		break;
	    hent = array[riter];
	} 
    }
    (void)hv_iterinit(hv);
}

void
hv_undef(hv)
HV *hv;
{
    register XPVHV* xhv;
    if (!hv)
	return;
    xhv = (XPVHV*)SvANY(hv);
    hfreeentries(hv);
    Safefree(xhv->xhv_array);
    if (HvNAME(hv)) {
	Safefree(HvNAME(hv));
	HvNAME(hv) = 0;
    }
    xhv->xhv_array = 0;
    xhv->xhv_max = 7;		/* it's a normal associative array */
    xhv->xhv_fill = 0;
    xhv->xhv_keys = 0;

    if (SvRMAGICAL(hv))
	mg_clear((SV*)hv); 
}

I32
hv_iterinit(hv)
HV *hv;
{
    register XPVHV* xhv = (XPVHV*)SvANY(hv);
    HE *entry = xhv->xhv_eiter;
    if (entry && entry->hent_klen < 0)	/* was deleted earlier? */
	he_free(entry);
    xhv->xhv_riter = -1;
    xhv->xhv_eiter = Null(HE*);
    return xhv->xhv_fill;
}

HE *
hv_iternext(hv)
HV *hv;
{
    register XPVHV* xhv;
    register HE *entry;
    HE *oldentry;
    MAGIC* mg;

    if (!hv)
	croak("Bad associative array");
    xhv = (XPVHV*)SvANY(hv);
    oldentry = entry = xhv->xhv_eiter;

    if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
	SV *key = sv_newmortal();
	if (entry) {
	    sv_usepvn(key, entry->hent_key, entry->hent_klen);
	    entry->hent_key = 0;
	}
	else {
	    Newz(504,entry, 1, HE);
	    xhv->xhv_eiter = entry;
	}
	magic_nextpack((SV*) hv,mg,key);
        if (SvOK(key)) {
	    STRLEN len;
	    entry->hent_key = SvPV_force(key, len);
	    entry->hent_klen = len;
	    SvPOK_off(key);
	    SvPVX(key) = 0;
	    return entry;
        }
	if (entry->hent_val)
	    SvREFCNT_dec(entry->hent_val);
	Safefree(entry);
	xhv->xhv_eiter = Null(HE*);
	return Null(HE*);
    }

    if (!xhv->xhv_array)
	Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
    do {
	if (entry)
	    entry = entry->hent_next;
	if (!entry) {
	    ++xhv->xhv_riter;
	    if (xhv->xhv_riter > xhv->xhv_max) {
		xhv->xhv_riter = -1;
		break;
	    }
	    entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
	}
    } while (!entry);

    if (oldentry && oldentry->hent_klen < 0)	/* was deleted earlier? */
	he_free(oldentry);

    xhv->xhv_eiter = entry;
    return entry;
}

char *
hv_iterkey(entry,retlen)
register HE *entry;
I32 *retlen;
{
    *retlen = entry->hent_klen;
    return entry->hent_key;
}

SV *
hv_iterval(hv,entry)
HV *hv;
register HE *entry;
{
    if (SvRMAGICAL(hv)) {
	if (mg_find((SV*)hv,'P')) {
	    SV* sv = sv_newmortal();
	    mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
	    return sv;
	}
    }
    return entry->hent_val;
}

SV *
hv_iternextsv(hv, key, retlen)
    HV *hv;
    char **key;
    I32 *retlen;
{
    HE *he;
    if ( (he = hv_iternext(hv)) == NULL)
	return NULL;
    *key = hv_iterkey(he, retlen);
    return hv_iterval(hv, he);
}

void
hv_magic(hv, gv, how)
HV* hv;
GV* gv;
int how;
{
    sv_magic((SV*)hv, (SV*)gv, how, Nullch, 0);
}
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));
a0d0e21e LW	18	static void hfreeentries _((HV *hv));
79072805 LW	19
	20	SV**
	21	hv_fetch(hv,key,klen,lval)
	22	HV *hv;
	23	char *key;
	24	U32 klen;
	25	I32 lval;
	26	{
	27	register XPVHV* xhv;
	28	register char *s;
	29	register I32 i;
	30	register I32 hash;
	31	register HE *entry;
79072805	32	SV *sv;
79072805 LW	33
	34	if (!hv)
	35	return 0;
463ee0b2	36
8990e307	37	if (SvRMAGICAL(hv)) {
463ee0b2	38	if (mg_find((SV*)hv,'P')) {
8990e307	39	sv = sv_newmortal();
463ee0b2	40	mg_copy((SV*)hv, sv, key, klen);
463ee0b2 LW	41	Sv = sv;
	42	return &Sv;
	43	}
	44	}
	45
79072805 LW	46	xhv = (XPVHV*)SvANY(hv);
79072805 LW	47	if (!xhv->xhv_array) {
a0d0e21e LW	48	if (lval
	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))
	51	#endif
	52	)
463ee0b2	53	Newz(503,xhv->xhv_array, sizeof(HE) (xhv->xhv_max + 1), char);
79072805 LW	54	else
	55	return 0;
	56	}
	57
463ee0b2 LW	58	i = klen;
	59	hash = 0;
	60	s = key;
	61	while (i--)
	62	hash = hash * 33 + *s++;
79072805	63
a0d0e21e	64	entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
79072805 LW	65	for (; entry; entry = entry->hent_next) {
	66	if (entry->hent_hash != hash) /* strings can't be equal */
	67	continue;
	68	if (entry->hent_klen != klen)
	69	continue;
	70	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
	71	continue;
	72	return &entry->hent_val;
	73	}
a0d0e21e LW	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)) {
	76	char *gotenv;
	77
	78	gotenv = my_getenv(key);
	79	if (gotenv != NULL) {
	80	sv = newSVpv(gotenv,strlen(gotenv));
	81	return hv_store(hv,key,klen,sv,hash);
	82	}
	83	}
	84	#endif
79072805 LW	85	if (lval) { /* gonna assign to this, so it better be there */
	86	sv = NEWSV(61,0);
	87	return hv_store(hv,key,klen,sv,hash);
	88	}
	89	return 0;
	90	}
	91
	92	SV**
	93	hv_store(hv,key,klen,val,hash)
	94	HV *hv;
	95	char *key;
	96	U32 klen;
	97	SV *val;
93a17b20	98	register U32 hash;
79072805 LW	99	{
	100	register XPVHV* xhv;
	101	register char *s;
	102	register I32 i;
	103	register HE *entry;
	104	register HE **oentry;
79072805 LW	105
	106	if (!hv)
	107	return 0;
	108
	109	xhv = (XPVHV*)SvANY(hv);
463ee0b2	110	if (SvMAGICAL(hv)) {
463ee0b2	111	mg_copy((SV*)hv, val, key, klen);
a0d0e21e	112	#ifndef OVERLOAD
463ee0b2 LW	113	if (!xhv->xhv_array)
463ee0b2 LW	114	return 0;
a0d0e21e LW	115	#else
	116	if (!xhv->xhv_array && (SvMAGIC(hv)->mg_type != 'A'
	117	\|\| SvMAGIC(hv)->mg_moremagic))
	118	return 0;
	119	#endif /* OVERLOAD */
463ee0b2 LW	120	}
	121	if (!hash) {
	122	i = klen;
	123	s = key;
	124	while (i--)
	125	hash = hash * 33 + *s++;
79072805 LW	126	}
	127
	128	if (!xhv->xhv_array)
463ee0b2	129	Newz(505, xhv->xhv_array, sizeof(HE*) (xhv->xhv_max + 1), char);
79072805	130
a0d0e21e	131	oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
79072805 LW	132	i = 1;
79072805 LW	133
79072805 LW	134	for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
	135	if (entry->hent_hash != hash) /* strings can't be equal */
	136	continue;
	137	if (entry->hent_klen != klen)
	138	continue;
	139	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
	140	continue;
8990e307	141	SvREFCNT_dec(entry->hent_val);
79072805 LW	142	entry->hent_val = val;
	143	return &entry->hent_val;
	144	}
	145	New(501,entry, 1, HE);
	146
	147	entry->hent_klen = klen;
a0d0e21e	148	entry->hent_key = savepvn(key,klen);
79072805 LW	149	entry->hent_val = val;
	150	entry->hent_hash = hash;
	151	entry->hent_next = *oentry;
	152	*oentry = entry;
	153
463ee0b2	154	xhv->xhv_keys++;
79072805	155	if (i) { /* initial entry? */
463ee0b2 LW	156	++xhv->xhv_fill;
463ee0b2 LW	157	if (xhv->xhv_keys > xhv->xhv_max)
79072805 LW	158	hsplit(hv);
79072805 LW	159	}
79072805 LW	160
	161	return &entry->hent_val;
	162	}
	163
	164	SV *
748a9306	165	hv_delete(hv,key,klen,flags)
79072805 LW	166	HV *hv;
	167	char *key;
	168	U32 klen;
748a9306	169	I32 flags;
79072805 LW	170	{
	171	register XPVHV* xhv;
	172	register char *s;
	173	register I32 i;
	174	register I32 hash;
	175	register HE *entry;
	176	register HE **oentry;
	177	SV *sv;
79072805 LW	178
	179	if (!hv)
	180	return Nullsv;
8990e307	181	if (SvRMAGICAL(hv)) {
463ee0b2 LW	182	sv = *hv_fetch(hv, key, klen, TRUE);
463ee0b2 LW	183	mg_clear(sv);
a0d0e21e LW	184	if (mg_find(sv, 'p')) {
	185	sv_unmagic(sv, 'p'); /* No longer an element */
	186	return sv;
	187	}
463ee0b2	188	}
79072805 LW	189	xhv = (XPVHV*)SvANY(hv);
	190	if (!xhv->xhv_array)
	191	return Nullsv;
463ee0b2 LW	192	i = klen;
	193	hash = 0;
	194	s = key;
	195	while (i--)
	196	hash = hash * 33 + *s++;
79072805	197
a0d0e21e	198	oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
79072805 LW	199	entry = *oentry;
	200	i = 1;
	201	for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
	202	if (entry->hent_hash != hash) /* strings can't be equal */
	203	continue;
	204	if (entry->hent_klen != klen)
	205	continue;
	206	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
	207	continue;
	208	*oentry = entry->hent_next;
	209	if (i && !*oentry)
	210	xhv->xhv_fill--;
748a9306 LW	211	if (flags & G_DISCARD)
	212	sv = Nullsv;
	213	else
	214	sv = sv_mortalcopy(entry->hent_val);
a0d0e21e LW	215	if (entry == xhv->xhv_eiter)
	216	entry->hent_klen = -1;
	217	else
	218	he_free(entry);
463ee0b2	219	--xhv->xhv_keys;
79072805 LW	220	return sv;
79072805 LW	221	}
79072805	222	return Nullsv;
79072805 LW	223	}
79072805 LW	224
a0d0e21e LW	225	bool
	226	hv_exists(hv,key,klen)
	227	HV *hv;
	228	char *key;
	229	U32 klen;
	230	{
	231	register XPVHV* xhv;
	232	register char *s;
	233	register I32 i;
	234	register I32 hash;
	235	register HE *entry;
	236	SV *sv;
	237
	238	if (!hv)
	239	return 0;
	240
	241	if (SvRMAGICAL(hv)) {
	242	if (mg_find((SV*)hv,'P')) {
	243	sv = sv_newmortal();
	244	mg_copy((SV*)hv, sv, key, klen);
	245	magic_existspack(sv, mg_find(sv, 'p'));
	246	return SvTRUE(sv);
	247	}
	248	}
	249
	250	xhv = (XPVHV*)SvANY(hv);
	251	if (!xhv->xhv_array)
	252	return 0;
	253
	254	i = klen;
	255	hash = 0;
	256	s = key;
	257	while (i--)
	258	hash = hash * 33 + *s++;
	259
	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 */
	263	continue;
	264	if (entry->hent_klen != klen)
	265	continue;
	266	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
	267	continue;
	268	return TRUE;
	269	}
	270	return FALSE;
	271	}
	272
79072805 LW	273	static void
	274	hsplit(hv)
	275	HV *hv;
	276	{
	277	register XPVHV* xhv = (XPVHV*)SvANY(hv);
a0d0e21e	278	I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */
79072805 LW	279	register I32 newsize = oldsize * 2;
	280	register I32 i;
	281	register HE **a;
	282	register HE **b;
	283	register HE *entry;
	284	register HE **oentry;
	285
463ee0b2	286	a = (HE**)xhv->xhv_array;
79072805 LW	287	nomemok = TRUE;
	288	Renew(a, newsize, HE*);
	289	nomemok = FALSE;
79072805 LW	290	Zero(&a[oldsize], oldsize, HE); / zero 2nd half*/
79072805 LW	291	xhv->xhv_max = --newsize;
463ee0b2	292	xhv->xhv_array = (char*)a;
79072805 LW	293
	294	for (i=0; i<oldsize; i++,a++) {
	295	if (!a) / non-existent */
	296	continue;
	297	b = a+oldsize;
	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;
	302	if (!*b)
	303	xhv->xhv_fill++;
	304	*b = entry;
	305	continue;
	306	}
	307	else
	308	oentry = &entry->hent_next;
	309	}
	310	if (!a) / everything moved */
	311	xhv->xhv_fill--;
	312	}
	313	}
	314
	315	HV *
463ee0b2	316	newHV()
79072805 LW	317	{
	318	register HV *hv;
	319	register XPVHV* xhv;
	320
a0d0e21e LW	321	hv = (HV*)NEWSV(502,0);
a0d0e21e LW	322	sv_upgrade((SV *)hv, SVt_PVHV);
79072805 LW	323	xhv = (XPVHV*)SvANY(hv);
	324	SvPOK_off(hv);
	325	SvNOK_off(hv);
463ee0b2	326	xhv->xhv_max = 7; /* start with 8 buckets */
79072805 LW	327	xhv->xhv_fill = 0;
79072805 LW	328	xhv->xhv_pmroot = 0;
79072805 LW	329	(void)hv_iterinit(hv); /* so each() will start off right */
	330	return hv;
	331	}
	332
	333	void
	334	he_free(hent)
	335	register HE *hent;
	336	{
	337	if (!hent)
	338	return;
8990e307	339	SvREFCNT_dec(hent->hent_val);
79072805 LW	340	Safefree(hent->hent_key);
	341	Safefree(hent);
	342	}
	343
	344	void
	345	he_delayfree(hent)
	346	register HE *hent;
	347	{
	348	if (!hent)
	349	return;
	350	sv_2mortal(hent->hent_val); /* free between statements */
	351	Safefree(hent->hent_key);
	352	Safefree(hent);
	353	}
	354
	355	void
463ee0b2	356	hv_clear(hv)
79072805	357	HV *hv;
79072805 LW	358	{
	359	register XPVHV* xhv;
	360	if (!hv)
	361	return;
	362	xhv = (XPVHV*)SvANY(hv);
463ee0b2	363	hfreeentries(hv);
79072805	364	xhv->xhv_fill = 0;
a0d0e21e	365	xhv->xhv_keys = 0;
79072805	366	if (xhv->xhv_array)
463ee0b2	367	(void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
a0d0e21e LW	368
	369	if (SvRMAGICAL(hv))
	370	mg_clear((SV*)hv);
79072805 LW	371	}
	372
	373	static void
463ee0b2	374	hfreeentries(hv)
79072805	375	HV *hv;
79072805	376	{
a0d0e21e	377	register HE **array;
79072805 LW	378	register HE *hent;
79072805 LW	379	register HE ohent = Null(HE);
a0d0e21e LW	380	I32 riter;
a0d0e21e LW	381	I32 max;
79072805 LW	382
	383	if (!hv)
	384	return;
a0d0e21e	385	if (!HvARRAY(hv))
79072805	386	return;
a0d0e21e LW	387
	388	riter = 0;
	389	max = HvMAX(hv);
	390	array = HvARRAY(hv);
	391	hent = array[0];
	392	for (;;) {
	393	if (hent) {
	394	ohent = hent;
	395	hent = hent->hent_next;
	396	he_free(ohent);
	397	}
	398	if (!hent) {
	399	if (++riter > max)
	400	break;
	401	hent = array[riter];
	402	}
79072805	403	}
a0d0e21e	404	(void)hv_iterinit(hv);
79072805 LW	405	}
	406
	407	void
463ee0b2	408	hv_undef(hv)
79072805	409	HV *hv;
79072805 LW	410	{
	411	register XPVHV* xhv;
	412	if (!hv)
	413	return;
	414	xhv = (XPVHV*)SvANY(hv);
463ee0b2	415	hfreeentries(hv);
79072805	416	Safefree(xhv->xhv_array);
85e6fe83 LW	417	if (HvNAME(hv)) {
	418	Safefree(HvNAME(hv));
	419	HvNAME(hv) = 0;
	420	}
79072805	421	xhv->xhv_array = 0;
463ee0b2	422	xhv->xhv_max = 7; /* it's a normal associative array */
79072805	423	xhv->xhv_fill = 0;
a0d0e21e LW	424	xhv->xhv_keys = 0;
	425
	426	if (SvRMAGICAL(hv))
	427	mg_clear((SV*)hv);
79072805 LW	428	}
79072805 LW	429
79072805 LW	430	I32
	431	hv_iterinit(hv)
	432	HV *hv;
	433	{
	434	register XPVHV* xhv = (XPVHV*)SvANY(hv);
a0d0e21e LW	435	HE *entry = xhv->xhv_eiter;
	436	if (entry && entry->hent_klen < 0) /* was deleted earlier? */
	437	he_free(entry);
79072805 LW	438	xhv->xhv_riter = -1;
	439	xhv->xhv_eiter = Null(HE*);
	440	return xhv->xhv_fill;
	441	}
	442
	443	HE *
	444	hv_iternext(hv)
	445	HV *hv;
	446	{
	447	register XPVHV* xhv;
	448	register HE *entry;
a0d0e21e	449	HE *oldentry;
463ee0b2	450	MAGIC* mg;
79072805 LW	451
79072805 LW	452	if (!hv)
463ee0b2	453	croak("Bad associative array");
79072805	454	xhv = (XPVHV*)SvANY(hv);
a0d0e21e	455	oldentry = entry = xhv->xhv_eiter;
463ee0b2	456
8990e307 LW	457	if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
8990e307 LW	458	SV *key = sv_newmortal();
a0d0e21e LW	459	if (entry) {
	460	sv_usepvn(key, entry->hent_key, entry->hent_klen);
	461	entry->hent_key = 0;
	462	}
	463	else {
	464	Newz(504,entry, 1, HE);
	465	xhv->xhv_eiter = entry;
	466	}
	467	magic_nextpack((SV*) hv,mg,key);
463ee0b2 LW	468	if (SvOK(key)) {
463ee0b2 LW	469	STRLEN len;
a0d0e21e	470	entry->hent_key = SvPV_force(key, len);
463ee0b2 LW	471	entry->hent_klen = len;
	472	SvPOK_off(key);
	473	SvPVX(key) = 0;
	474	return entry;
	475	}
	476	if (entry->hent_val)
8990e307	477	SvREFCNT_dec(entry->hent_val);
463ee0b2 LW	478	Safefree(entry);
	479	xhv->xhv_eiter = Null(HE*);
	480	return Null(HE*);
79072805	481	}
463ee0b2	482
79072805	483	if (!xhv->xhv_array)
463ee0b2	484	Newz(506,xhv->xhv_array, sizeof(HE) (xhv->xhv_max + 1), char);
79072805 LW	485	do {
	486	if (entry)
	487	entry = entry->hent_next;
	488	if (!entry) {
a0d0e21e	489	++xhv->xhv_riter;
79072805 LW	490	if (xhv->xhv_riter > xhv->xhv_max) {
	491	xhv->xhv_riter = -1;
	492	break;
	493	}
463ee0b2	494	entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
79072805 LW	495	}
	496	} while (!entry);
	497
a0d0e21e LW	498	if (oldentry && oldentry->hent_klen < 0) /* was deleted earlier? */
	499	he_free(oldentry);
	500
79072805 LW	501	xhv->xhv_eiter = entry;
	502	return entry;
	503	}
	504
	505	char *
	506	hv_iterkey(entry,retlen)
	507	register HE *entry;
	508	I32 *retlen;
	509	{
	510	*retlen = entry->hent_klen;
	511	return entry->hent_key;
	512	}
	513
	514	SV *
	515	hv_iterval(hv,entry)
	516	HV *hv;
	517	register HE *entry;
	518	{
8990e307	519	if (SvRMAGICAL(hv)) {
463ee0b2	520	if (mg_find((SV*)hv,'P')) {
8990e307	521	SV* sv = sv_newmortal();
463ee0b2	522	mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
463ee0b2 LW	523	return sv;
463ee0b2 LW	524	}
79072805	525	}
79072805 LW	526	return entry->hent_val;
	527	}
	528
a0d0e21e LW	529	SV *
	530	hv_iternextsv(hv, key, retlen)
	531	HV *hv;
	532	char **key;
	533	I32 *retlen;
	534	{
	535	HE *he;
	536	if ( (he = hv_iternext(hv)) == NULL)
	537	return NULL;
	538	*key = hv_iterkey(he, retlen);
	539	return hv_iterval(hv, he);
	540	}
	541
79072805 LW	542	void
	543	hv_magic(hv, gv, how)
	544	HV* hv;
	545	GV* gv;
a0d0e21e	546	int how;
79072805	547	{
a0d0e21e	548	sv_magic((SV)hv, (SV)gv, how, Nullch, 0);
79072805	549	}