[p5sagit/p5-mst-13.2.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)
HV *hv;
char *key;
U32 klen;
{
    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--;
	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	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	8	*/
	9
	10	/*
	11	* "I sit beside the fire and think of all that I have seen." --Bilbo
79072805	12	*/
	13
	14	#include "EXTERN.h"
	15	#include "perl.h"
	16
a0d0e21e	17	static void hsplit _((HV *hv));
a0d0e21e	18	static void hfreeentries _((HV *hv));
79072805	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	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	41	Sv = sv;
	42	return &Sv;
	43	}
	44	}
	45
79072805	46	xhv = (XPVHV*)SvANY(hv);
79072805	47	if (!xhv->xhv_array) {
a0d0e21e	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	54	else
	55	return 0;
	56	}
	57
463ee0b2	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	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	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	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	99	{
	100	register XPVHV* xhv;
	101	register char *s;
	102	register I32 i;
	103	register HE *entry;
	104	register HE **oentry;
79072805	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	113	if (!xhv->xhv_array)
463ee0b2	114	return 0;
a0d0e21e	115	#else
	116	if (!xhv->xhv_array && (SvMAGIC(hv)->mg_type != 'A'
	117	\|\| SvMAGIC(hv)->mg_moremagic))
	118	return 0;
	119	#endif /* OVERLOAD */
463ee0b2	120	}
	121	if (!hash) {
	122	i = klen;
	123	s = key;
	124	while (i--)
	125	hash = hash * 33 + *s++;
79072805	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	132	i = 1;
79072805	133
79072805	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	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	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	156	++xhv->xhv_fill;
463ee0b2	157	if (xhv->xhv_keys > xhv->xhv_max)
79072805	158	hsplit(hv);
79072805	159	}
79072805	160
	161	return &entry->hent_val;
	162	}
	163
	164	SV *
	165	hv_delete(hv,key,klen)
	166	HV *hv;
	167	char *key;
	168	U32 klen;
	169	{
	170	register XPVHV* xhv;
	171	register char *s;
	172	register I32 i;
	173	register I32 hash;
	174	register HE *entry;
	175	register HE **oentry;
	176	SV *sv;
79072805	177
	178	if (!hv)
	179	return Nullsv;
8990e307	180	if (SvRMAGICAL(hv)) {
463ee0b2	181	sv = *hv_fetch(hv, key, klen, TRUE);
463ee0b2	182	mg_clear(sv);
a0d0e21e	183	if (mg_find(sv, 'p')) {
	184	sv_unmagic(sv, 'p'); /* No longer an element */
	185	return sv;
	186	}
463ee0b2	187	}
79072805	188	xhv = (XPVHV*)SvANY(hv);
	189	if (!xhv->xhv_array)
	190	return Nullsv;
463ee0b2	191	i = klen;
	192	hash = 0;
	193	s = key;
	194	while (i--)
	195	hash = hash * 33 + *s++;
79072805	196
a0d0e21e	197	oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
79072805	198	entry = *oentry;
	199	i = 1;
	200	for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
	201	if (entry->hent_hash != hash) /* strings can't be equal */
	202	continue;
	203	if (entry->hent_klen != klen)
	204	continue;
	205	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
	206	continue;
	207	*oentry = entry->hent_next;
	208	if (i && !*oentry)
	209	xhv->xhv_fill--;
	210	sv = sv_mortalcopy(entry->hent_val);
a0d0e21e	211	if (entry == xhv->xhv_eiter)
	212	entry->hent_klen = -1;
	213	else
	214	he_free(entry);
463ee0b2	215	--xhv->xhv_keys;
79072805	216	return sv;
79072805	217	}
79072805	218	return Nullsv;
79072805	219	}
79072805	220
a0d0e21e	221	bool
	222	hv_exists(hv,key,klen)
	223	HV *hv;
	224	char *key;
	225	U32 klen;
	226	{
	227	register XPVHV* xhv;
	228	register char *s;
	229	register I32 i;
	230	register I32 hash;
	231	register HE *entry;
	232	SV *sv;
	233
	234	if (!hv)
	235	return 0;
	236
	237	if (SvRMAGICAL(hv)) {
	238	if (mg_find((SV*)hv,'P')) {
	239	sv = sv_newmortal();
	240	mg_copy((SV*)hv, sv, key, klen);
	241	magic_existspack(sv, mg_find(sv, 'p'));
	242	return SvTRUE(sv);
	243	}
	244	}
	245
	246	xhv = (XPVHV*)SvANY(hv);
	247	if (!xhv->xhv_array)
	248	return 0;
	249
	250	i = klen;
	251	hash = 0;
	252	s = key;
	253	while (i--)
	254	hash = hash * 33 + *s++;
	255
	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 */
	259	continue;
	260	if (entry->hent_klen != klen)
	261	continue;
	262	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
	263	continue;
	264	return TRUE;
	265	}
	266	return FALSE;
	267	}
	268
79072805	269	static void
	270	hsplit(hv)
	271	HV *hv;
	272	{
	273	register XPVHV* xhv = (XPVHV*)SvANY(hv);
a0d0e21e	274	I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */
79072805	275	register I32 newsize = oldsize * 2;
	276	register I32 i;
	277	register HE **a;
	278	register HE **b;
	279	register HE *entry;
	280	register HE **oentry;
	281
463ee0b2	282	a = (HE**)xhv->xhv_array;
79072805	283	nomemok = TRUE;
	284	Renew(a, newsize, HE*);
	285	nomemok = FALSE;
79072805	286	Zero(&a[oldsize], oldsize, HE); / zero 2nd half*/
79072805	287	xhv->xhv_max = --newsize;
463ee0b2	288	xhv->xhv_array = (char*)a;
79072805	289
	290	for (i=0; i<oldsize; i++,a++) {
	291	if (!a) / non-existent */
	292	continue;
	293	b = a+oldsize;
	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;
	298	if (!*b)
	299	xhv->xhv_fill++;
	300	*b = entry;
	301	continue;
	302	}
	303	else
	304	oentry = &entry->hent_next;
	305	}
	306	if (!a) / everything moved */
	307	xhv->xhv_fill--;
	308	}
	309	}
	310
	311	HV *
463ee0b2	312	newHV()
79072805	313	{
	314	register HV *hv;
	315	register XPVHV* xhv;
	316
a0d0e21e	317	hv = (HV*)NEWSV(502,0);
a0d0e21e	318	sv_upgrade((SV *)hv, SVt_PVHV);
79072805	319	xhv = (XPVHV*)SvANY(hv);
	320	SvPOK_off(hv);
	321	SvNOK_off(hv);
463ee0b2	322	xhv->xhv_max = 7; /* start with 8 buckets */
79072805	323	xhv->xhv_fill = 0;
79072805	324	xhv->xhv_pmroot = 0;
79072805	325	(void)hv_iterinit(hv); /* so each() will start off right */
	326	return hv;
	327	}
	328
	329	void
	330	he_free(hent)
	331	register HE *hent;
	332	{
	333	if (!hent)
	334	return;
8990e307	335	SvREFCNT_dec(hent->hent_val);
79072805	336	Safefree(hent->hent_key);
	337	Safefree(hent);
	338	}
	339
	340	void
	341	he_delayfree(hent)
	342	register HE *hent;
	343	{
	344	if (!hent)
	345	return;
	346	sv_2mortal(hent->hent_val); /* free between statements */
	347	Safefree(hent->hent_key);
	348	Safefree(hent);
	349	}
	350
	351	void
463ee0b2	352	hv_clear(hv)
79072805	353	HV *hv;
79072805	354	{
	355	register XPVHV* xhv;
	356	if (!hv)
	357	return;
	358	xhv = (XPVHV*)SvANY(hv);
463ee0b2	359	hfreeentries(hv);
79072805	360	xhv->xhv_fill = 0;
a0d0e21e	361	xhv->xhv_keys = 0;
79072805	362	if (xhv->xhv_array)
463ee0b2	363	(void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
a0d0e21e	364
	365	if (SvRMAGICAL(hv))
	366	mg_clear((SV*)hv);
79072805	367	}
	368
	369	static void
463ee0b2	370	hfreeentries(hv)
79072805	371	HV *hv;
79072805	372	{
a0d0e21e	373	register HE **array;
79072805	374	register HE *hent;
79072805	375	register HE ohent = Null(HE);
a0d0e21e	376	I32 riter;
a0d0e21e	377	I32 max;
79072805	378
	379	if (!hv)
	380	return;
a0d0e21e	381	if (!HvARRAY(hv))
79072805	382	return;
a0d0e21e	383
	384	riter = 0;
	385	max = HvMAX(hv);
	386	array = HvARRAY(hv);
	387	hent = array[0];
	388	for (;;) {
	389	if (hent) {
	390	ohent = hent;
	391	hent = hent->hent_next;
	392	he_free(ohent);
	393	}
	394	if (!hent) {
	395	if (++riter > max)
	396	break;
	397	hent = array[riter];
	398	}
79072805	399	}
a0d0e21e	400	(void)hv_iterinit(hv);
79072805	401	}
	402
	403	void
463ee0b2	404	hv_undef(hv)
79072805	405	HV *hv;
79072805	406	{
	407	register XPVHV* xhv;
	408	if (!hv)
	409	return;
	410	xhv = (XPVHV*)SvANY(hv);
463ee0b2	411	hfreeentries(hv);
79072805	412	Safefree(xhv->xhv_array);
85e6fe83	413	if (HvNAME(hv)) {
	414	Safefree(HvNAME(hv));
	415	HvNAME(hv) = 0;
	416	}
79072805	417	xhv->xhv_array = 0;
463ee0b2	418	xhv->xhv_max = 7; /* it's a normal associative array */
79072805	419	xhv->xhv_fill = 0;
a0d0e21e	420	xhv->xhv_keys = 0;
	421
	422	if (SvRMAGICAL(hv))
	423	mg_clear((SV*)hv);
79072805	424	}
79072805	425
79072805	426	I32
	427	hv_iterinit(hv)
	428	HV *hv;
	429	{
	430	register XPVHV* xhv = (XPVHV*)SvANY(hv);
a0d0e21e	431	HE *entry = xhv->xhv_eiter;
	432	if (entry && entry->hent_klen < 0) /* was deleted earlier? */
	433	he_free(entry);
79072805	434	xhv->xhv_riter = -1;
	435	xhv->xhv_eiter = Null(HE*);
	436	return xhv->xhv_fill;
	437	}
	438
	439	HE *
	440	hv_iternext(hv)
	441	HV *hv;
	442	{
	443	register XPVHV* xhv;
	444	register HE *entry;
a0d0e21e	445	HE *oldentry;
463ee0b2	446	MAGIC* mg;
79072805	447
79072805	448	if (!hv)
463ee0b2	449	croak("Bad associative array");
79072805	450	xhv = (XPVHV*)SvANY(hv);
a0d0e21e	451	oldentry = entry = xhv->xhv_eiter;
463ee0b2	452
8990e307	453	if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
8990e307	454	SV *key = sv_newmortal();
a0d0e21e	455	if (entry) {
	456	sv_usepvn(key, entry->hent_key, entry->hent_klen);
	457	entry->hent_key = 0;
	458	}
	459	else {
	460	Newz(504,entry, 1, HE);
	461	xhv->xhv_eiter = entry;
	462	}
	463	magic_nextpack((SV*) hv,mg,key);
463ee0b2	464	if (SvOK(key)) {
463ee0b2	465	STRLEN len;
a0d0e21e	466	entry->hent_key = SvPV_force(key, len);
463ee0b2	467	entry->hent_klen = len;
	468	SvPOK_off(key);
	469	SvPVX(key) = 0;
	470	return entry;
	471	}
	472	if (entry->hent_val)
8990e307	473	SvREFCNT_dec(entry->hent_val);
463ee0b2	474	Safefree(entry);
	475	xhv->xhv_eiter = Null(HE*);
	476	return Null(HE*);
79072805	477	}
463ee0b2	478
79072805	479	if (!xhv->xhv_array)
463ee0b2	480	Newz(506,xhv->xhv_array, sizeof(HE) (xhv->xhv_max + 1), char);
79072805	481	do {
	482	if (entry)
	483	entry = entry->hent_next;
	484	if (!entry) {
a0d0e21e	485	++xhv->xhv_riter;
79072805	486	if (xhv->xhv_riter > xhv->xhv_max) {
	487	xhv->xhv_riter = -1;
	488	break;
	489	}
463ee0b2	490	entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
79072805	491	}
	492	} while (!entry);
	493
a0d0e21e	494	if (oldentry && oldentry->hent_klen < 0) /* was deleted earlier? */
	495	he_free(oldentry);
	496
79072805	497	xhv->xhv_eiter = entry;
	498	return entry;
	499	}
	500
	501	char *
	502	hv_iterkey(entry,retlen)
	503	register HE *entry;
	504	I32 *retlen;
	505	{
	506	*retlen = entry->hent_klen;
	507	return entry->hent_key;
	508	}
	509
	510	SV *
	511	hv_iterval(hv,entry)
	512	HV *hv;
	513	register HE *entry;
	514	{
8990e307	515	if (SvRMAGICAL(hv)) {
463ee0b2	516	if (mg_find((SV*)hv,'P')) {
8990e307	517	SV* sv = sv_newmortal();
463ee0b2	518	mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
463ee0b2	519	return sv;
463ee0b2	520	}
79072805	521	}
79072805	522	return entry->hent_val;
	523	}
	524
a0d0e21e	525	SV *
	526	hv_iternextsv(hv, key, retlen)
	527	HV *hv;
	528	char **key;
	529	I32 *retlen;
	530	{
	531	HE *he;
	532	if ( (he = hv_iternext(hv)) == NULL)
	533	return NULL;
	534	*key = hv_iterkey(he, retlen);
	535	return hv_iterval(hv, he);
	536	}
	537
79072805	538	void
	539	hv_magic(hv, gv, how)
	540	HV* hv;
	541	GV* gv;
a0d0e21e	542	int how;
79072805	543	{
a0d0e21e	544	sv_magic((SV)hv, (SV)gv, how, Nullch, 0);
79072805	545	}