#define PERL_HASH_INTERNAL_ACCESS
#include "perl.h"
-#define DO_HSPLIT(xhv) ((xhv)->xhv_keys > (xhv)->xhv_max) /* HvTOTALKEYS(hv) > HvMAX(hv) */
+/* we split when we collide and we have a load factor over 0.667.
+ * NOTE if you change this formula so we split earlier than previously
+ * you MUST change the logic in hv_ksplit()
+ */
+#define DO_HSPLIT(xhv) ( ((xhv)->xhv_keys + ((xhv)->xhv_keys >> 1)) > (xhv)->xhv_max )
#define HV_FILL_THRESHOLD 31
static const char S_strtab_error[]
HE **oentry;
SV *sv;
bool is_utf8;
+ bool in_collision;
int masked_flags;
const int return_svp = action & HV_FETCH_JUST_SV;
HEK *keysv_hek = NULL;
flags = is_utf8 ? HVhek_UTF8 : 0;
}
} else {
- is_utf8 = ((flags & HVhek_UTF8) ? TRUE : FALSE);
+ is_utf8 = cBOOL(flags & HVhek_UTF8);
}
if (action & HV_DELETE) {
/* This cast somewhat evil, but I'm merely using NULL/
not NULL to return the boolean exists.
And I know hv is not NULL. */
- return SvTRUE(svret) ? (void *)hv : NULL;
+ return SvTRUE_NN(svret) ? (void *)hv : NULL;
}
#ifdef ENV_IS_CASELESS
else if (mg_find((const SV *)hv, PERL_MAGIC_env)) {
* making it harder to see if there is a collision. We also
* reset the iterator randomizer if there is one.
*/
+ in_collision = *oentry != NULL;
if ( *oentry && PL_HASH_RAND_BITS_ENABLED) {
PL_hash_rand_bits++;
PL_hash_rand_bits= ROTL_UV(PL_hash_rand_bits,1);
HvHASKFLAGS_on(hv);
xhv->xhv_keys++; /* HvTOTALKEYS(hv)++ */
- if ( DO_HSPLIT(xhv) ) {
+ if ( in_collision && DO_HSPLIT(xhv) ) {
const STRLEN oldsize = xhv->xhv_max + 1;
const U32 items = (U32)HvPLACEHOLDERS_get(hv);
return sv;
}
+
+/*
+hv_pushkv(): push all the keys and/or values of a hash onto the stack.
+The rough Perl equivalents:
+ () = %hash;
+ () = keys %hash;
+ () = values %hash;
+
+Resets the hash's iterator.
+
+flags : 1 = push keys
+ 2 = push values
+ 1|2 = push keys and values
+ XXX use symbolic flag constants at some point?
+I might unroll the non-tied hv_iternext() in here at some point - DAPM
+*/
+
+void
+Perl_hv_pushkv(pTHX_ HV *hv, U32 flags)
+{
+ HE *entry;
+ bool tied = SvRMAGICAL(hv) && (mg_find(MUTABLE_SV(hv), PERL_MAGIC_tied)
+#ifdef DYNAMIC_ENV_FETCH /* might not know number of keys yet */
+ || mg_find(MUTABLE_SV(hv), PERL_MAGIC_env)
+#endif
+ );
+ dSP;
+
+ PERL_ARGS_ASSERT_HV_PUSHKV;
+ assert(flags); /* must be pushing at least one of keys and values */
+
+ (void)hv_iterinit(hv);
+
+ if (tied) {
+ SSize_t ext = (flags == 3) ? 2 : 1;
+ while ((entry = hv_iternext(hv))) {
+ EXTEND(SP, ext);
+ if (flags & 1)
+ PUSHs(hv_iterkeysv(entry));
+ if (flags & 2)
+ PUSHs(hv_iterval(hv, entry));
+ }
+ }
+ else {
+ Size_t nkeys = HvUSEDKEYS(hv);
+ SSize_t ext;
+
+ if (!nkeys)
+ return;
+
+ /* 2*nkeys() should never be big enough to truncate or wrap */
+ assert(nkeys <= (SSize_t_MAX >> 1));
+ ext = nkeys * ((flags == 3) ? 2 : 1);
+
+ EXTEND_MORTAL(nkeys);
+ EXTEND(SP, ext);
+
+ while ((entry = hv_iternext(hv))) {
+ if (flags & 1) {
+ SV *keysv = newSVhek(HeKEY_hek(entry));
+ SvTEMP_on(keysv);
+ PL_tmps_stack[++PL_tmps_ix] = keysv;
+ PUSHs(keysv);
+ }
+ if (flags & 2)
+ PUSHs(HeVAL(entry));
+ }
+ }
+
+ PUTBACK;
+}
+
+
/*
=for apidoc hv_bucket_ratio
return magic_scalarpack(hv, mg);
}
- sv = sv_newmortal();
- if (HvUSEDKEYS((const HV *)hv))
+ if (HvUSEDKEYS((HV *)hv)) {
+ sv = sv_newmortal();
Perl_sv_setpvf(aTHX_ sv, "%ld/%ld",
(long)HvFILL(hv), (long)HvMAX(hv) + 1);
+ }
else
- sv_setiv(sv, 0);
+ sv = &PL_sv_zero;
return sv;
}
HE *entry;
HE **oentry;
HE **first_entry;
- bool is_utf8 = (k_flags & HVhek_UTF8) ? TRUE : FALSE;
+ bool is_utf8 = cBOOL(k_flags & HVhek_UTF8);
int masked_flags;
HEK *keysv_hek = NULL;
U8 mro_changes = 0; /* 1 = isa; 2 = package moved */
sv_2mortal((SV *)gv)
);
}
- else if (klen == 3 && strEQs(key, "ISA") && GvAV(gv)) {
+ else if (memEQs(key, klen, "ISA") && GvAV(gv)) {
AV *isa = GvAV(gv);
MAGIC *mg = mg_find((SV*)isa, PERL_MAGIC_isa);
SV **svp, **end;
strip_magic:
svp = AvARRAY(isa);
- end = svp + AvFILLp(isa)+1;
+ end = svp + (AvFILLp(isa)+1);
while (svp < end) {
if (*svp)
mg_free_type(*svp, PERL_MAGIC_isaelem);
Perl_hv_ksplit(pTHX_ HV *hv, IV newmax)
{
XPVHV* xhv = (XPVHV*)SvANY(hv);
- const I32 oldsize = (I32) xhv->xhv_max+1; /* HvMAX(hv)+1 (sick) */
+ const I32 oldsize = (I32) xhv->xhv_max+1; /* HvMAX(hv)+1 */
I32 newsize;
+ I32 wantsize;
+ I32 trysize;
char *a;
PERL_ARGS_ASSERT_HV_KSPLIT;
- newsize = (I32) newmax; /* possible truncation here */
- if (newsize != newmax || newmax <= oldsize)
+ wantsize = (I32) newmax; /* possible truncation here */
+ if (wantsize != newmax)
return;
- while ((newsize & (1 + ~newsize)) != newsize) {
- newsize &= ~(newsize & (1 + ~newsize)); /* get proper power of 2 */
+
+ wantsize= wantsize + (wantsize >> 1); /* wantsize *= 1.5 */
+ if (wantsize < newmax) /* overflow detection */
+ return;
+
+ newsize = oldsize;
+ while (wantsize > newsize) {
+ trysize = newsize << 1;
+ if (trysize > newsize) {
+ newsize = trysize;
+ } else {
+ /* we overflowed */
+ return;
+ }
}
- if (newsize < newmax)
- newsize *= 2;
- if (newsize < newmax)
- return; /* overflow detection */
+
+ if (newsize <= oldsize)
+ return; /* overflow detection */
a = (char *) HvARRAY(hv);
if (a) {
hsplit(hv, oldsize, newsize);
} else {
Newxz(a, PERL_HV_ARRAY_ALLOC_BYTES(newsize), char);
- xhv->xhv_max = --newsize;
+ xhv->xhv_max = newsize - 1;
HvARRAY(hv) = (HE **) a;
}
}
}
}
else {
- hfreeentries(hv);
+ hv_free_entries(hv);
HvPLACEHOLDERS_set(hv, 0);
if (SvRMAGICAL(hv))
}
STATIC void
-S_hfreeentries(pTHX_ HV *hv)
+S_hv_free_entries(pTHX_ HV *hv)
{
STRLEN index = 0;
XPVHV * const xhv = (XPVHV*)SvANY(hv);
SV *sv;
- PERL_ARGS_ASSERT_HFREEENTRIES;
+ PERL_ARGS_ASSERT_HV_FREE_ENTRIES;
while ((sv = Perl_hfree_next_entry(aTHX_ hv, &index))||xhv->xhv_keys) {
SvREFCNT_dec(sv);
/* hfree_next_entry()
- * For use only by S_hfreeentries() and sv_clear().
+ * For use only by S_hv_free_entries() and sv_clear().
* Delete the next available HE from hv and return the associated SV.
* Returns null on empty hash. Nevertheless null is not a reliable
* indicator that the hash is empty, as the deleted entry may have a
{
XPVHV* xhv;
bool save;
- SSize_t orig_ix;
+ SSize_t orig_ix = PL_tmps_ix; /* silence compiler warning about unitialized vars */
if (!hv)
return;
DEBUG_A(Perl_hv_assert(aTHX_ hv));
xhv = (XPVHV*)SvANY(hv);
- /* The name must be deleted before the call to hfreeeeentries so that
+ /* The name must be deleted before the call to hv_free_entries so that
CVs are anonymised properly. But the effective name must be pre-
served until after that call (and only deleted afterwards if the
call originated from sv_clear). For stashes with one name that is
allocate an array for storing the effective name. We can skip that
during global destruction, as it does not matter where the CVs point
if they will be freed anyway. */
- /* note that the code following prior to hfreeentries is duplicated
+ /* note that the code following prior to hv_free_entries is duplicated
* in sv_clear(), and changes here should be done there too */
if (PL_phase != PERL_PHASE_DESTRUCT && HvNAME(hv)) {
if (PL_stashcache) {
PL_tmps_stack[++PL_tmps_ix] = SvREFCNT_inc_simple_NN(hv);
orig_ix = PL_tmps_ix;
}
- hfreeentries(hv);
+ hv_free_entries(hv);
if (SvOOK(hv)) {
struct mro_meta *meta;
const char *name;
=for apidoc hv_iterinit
Prepares a starting point to traverse a hash table. Returns the number of
-keys in the hash (i.e. the same as C<HvUSEDKEYS(hv)>). The return value is
-currently only meaningful for hashes without tie magic.
+keys in the hash, including placeholders (i.e. the same as C<HvTOTALKEYS(hv)>).
+The return value is currently only meaningful for hashes without tie magic.
NOTE: Before version 5.004_65, C<hv_iterinit> used to return the number of
hash buckets that happen to be in use. If you still need that esoteric
* len and hash must both be valid for str.
*/
HEK *
-Perl_share_hek(pTHX_ const char *str, I32 len, U32 hash)
+Perl_share_hek(pTHX_ const char *str, SSize_t len, U32 hash)
{
bool is_utf8 = FALSE;
int flags = 0;
}
STATIC HEK *
-S_share_hek_flags(pTHX_ const char *str, I32 len, U32 hash, int flags)
+S_share_hek_flags(pTHX_ const char *str, STRLEN len, U32 hash, int flags)
{
HE *entry;
const int flags_masked = flags & HVhek_MASK;
PERL_ARGS_ASSERT_SHARE_HEK_FLAGS;
+ if (UNLIKELY(len > (STRLEN) I32_MAX)) {
+ Perl_croak_nocontext("Sorry, hash keys must be smaller than 2**31 bytes");
+ }
+
/* what follows is the moral equivalent of:
if (!(Svp = hv_fetch(PL_strtab, str, len, FALSE)))
for (;entry; entry = HeNEXT(entry)) {
if (HeHASH(entry) != hash) /* strings can't be equal */
continue;
- if (HeKLEN(entry) != len)
+ if (HeKLEN(entry) != (SSize_t) len)
continue;
if (HeKEY(entry) != str && memNE(HeKEY(entry),str,len)) /* is this it? */
continue;