[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));

static HE* more_he();

static HE*
new_he()
{
    HE* he;
    if (he_root) {
        he = he_root;
        he_root = (HE*)he->hent_next;
        return he;
    }
    return more_he();
}

static void
del_he(p)
HE* p;
{
    p->hent_next = (HE*)he_root;
    he_root = p;
}

static HE*
more_he()
{
    register HE* he;
    register HE* heend;
    he_root = (HE*)safemalloc(1008);
    he = he_root;
    heend = &he[1008 / sizeof(HE) - 1];
    while (he < heend) {
        he->hent_next = (HE*)(he + 1);
        he++;
    }
    he->hent_next = 0;
    return new_he();
}

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')) {
	    dTHR;
	    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;
    }

    entry = new_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')) {
	    dTHR;
	    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;
#ifndef STRANGE_MALLOC
    I32 tmp;
#endif

    a = (HE**)xhv->xhv_array;
    nomemok = TRUE;
#ifdef STRANGE_MALLOC
    Renew(a, newsize, HE*);
#else
    i = newsize * sizeof(HE*);
#define MALLOC_OVERHEAD 16
    tmp = MALLOC_OVERHEAD;
    while (tmp - MALLOC_OVERHEAD < i)
	tmp += tmp;
    tmp -= MALLOC_OVERHEAD;
    tmp /= sizeof(HE*);
    assert(tmp >= newsize);
    New(2,a, tmp, HE*);
    Copy(xhv->xhv_array, a, oldsize, HE*);
    if (oldsize >= 64 && !nice_chunk) {
	nice_chunk = (char*)xhv->xhv_array;
	nice_chunk_size = oldsize * sizeof(HE*) * 2 - MALLOC_OVERHEAD;
    }
    else
	Safefree(xhv->xhv_array);
#endif

    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);
    del_he(hent);
}

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