[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')) {
	    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')) {
	    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;
    I32 tmp;

    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 && *(char*)&xhv->xnv_nv == 0) {
	sv_add_arena((char*)xhv->xhv_array, oldsize * sizeof(HE*), 0);
	sv_add_arena(((char*)a) + newsize * sizeof(HE*),
		     newsize * sizeof(HE*) - MALLOC_OVERHEAD,
		     SVf_FAKE);
    }
    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;
    *(char*)&xhv->xnv_nv = 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);
#ifdef STRANGE_MALLOC
    Safefree(xhv->xhv_array);
#else
    if (xhv->xhv_max < 127 || *(char*)&xhv->xnv_nv)
	Safefree(xhv->xhv_array);
    else  /* We used last half, so use first half for SV arena too. */
	sv_add_arena((char*)xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*),0);
#endif
    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;
    *(char*)&xhv->xnv_nv = 1;

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