duk_heap_stringtable.c File Reference

#include "duk_internal.h"

Go to the source code of this file.

Macros
#define	DUK__HASH_INITIAL(hash, h_size)   DUK_STRTAB_HASH_INITIAL((hash),(h_size))
#define	DUK__HASH_PROBE_STEP(hash)   DUK_STRTAB_HASH_PROBE_STEP((hash))
#define	DUK__DELETED_MARKER(heap)   DUK_STRTAB_DELETED_MARKER((heap))
#define	DUK__PREVENT_MS_SIDE_EFFECTS(heap)

Functions
DUK_LOCAL duk_hstring *	duk__alloc_init_hstring (duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen, duk_uint32_t strhash, const duk_uint8_t *extdata)
DUK_LOCAL duk_int_t	duk__count_used_probe (duk_heap *heap)
DUK_LOCAL void	duk__insert_hstring_probe (duk_heap *heap, duk_hstring **entries, duk_uint32_t size, duk_uint32_t *p_used, duk_hstring *h)
DUK_LOCAL duk_hstring *	duk__find_matching_string_probe (duk_heap *heap, duk_hstring **entries, duk_uint32_t size, const duk_uint8_t *str, duk_uint32_t blen, duk_uint32_t strhash)
DUK_LOCAL void	duk__remove_matching_hstring_probe (duk_heap *heap, duk_hstring **entries, duk_uint32_t size, duk_hstring *h)
DUK_LOCAL duk_bool_t	duk__resize_strtab_raw_probe (duk_heap *heap, duk_uint32_t new_size)
DUK_LOCAL duk_bool_t	duk__resize_strtab_probe (duk_heap *heap)
DUK_LOCAL duk_bool_t	duk__recheck_strtab_size_probe (duk_heap *heap, duk_uint32_t new_used)
DUK_LOCAL duk_hstring *	duk__do_intern (duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen, duk_uint32_t strhash)
DUK_LOCAL duk_hstring *	duk__do_lookup (duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen, duk_uint32_t *out_strhash)
DUK_INTERNAL duk_hstring *	duk_heap_string_intern (duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen)
DUK_INTERNAL duk_hstring *	duk_heap_string_intern_checked (duk_hthread *thr, const duk_uint8_t *str, duk_uint32_t blen)
DUK_INTERNAL duk_hstring *	duk_heap_string_intern_u32 (duk_heap *heap, duk_uint32_t val)
DUK_INTERNAL duk_hstring *	duk_heap_string_intern_u32_checked (duk_hthread *thr, duk_uint32_t val)
DUK_INTERNAL void	duk_heap_string_remove (duk_heap *heap, duk_hstring *h)
DUK_INTERNAL void	duk_heap_force_strtab_resize (duk_heap *heap)
DUK_INTERNAL void	duk_heap_free_strtab (duk_heap *heap)

Macro Definition Documentation

DUK__DELETED_MARKER

#define DUK__DELETED_MARKER

(

heap

)

DUK_STRTAB_DELETED_MARKER((heap))

Definition at line 10 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

Referenced by duk__count_used_probe(), duk__find_matching_string_probe(), duk__insert_hstring_probe(), duk__remove_matching_hstring_probe(), and duk__resize_strtab_raw_probe().

DUK__HASH_INITIAL

#define DUK__HASH_INITIAL	(		hash,
			h_size )   DUK_STRTAB_HASH_INITIAL((hash),(h_size))

Definition at line 8 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

Referenced by duk__find_matching_string_probe(), duk__insert_hstring_probe(), and duk__remove_matching_hstring_probe().

DUK__HASH_PROBE_STEP

#define DUK__HASH_PROBE_STEP

(

hash

)

DUK_STRTAB_HASH_PROBE_STEP((hash))

Definition at line 9 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

Referenced by duk__find_matching_string_probe(), duk__insert_hstring_probe(), and duk__remove_matching_hstring_probe().

DUK__PREVENT_MS_SIDE_EFFECTS

#define DUK__PREVENT_MS_SIDE_EFFECTS

(

heap

)

Value:

        do { \
        (heap)->mark_and_sweep_base_flags |= \
                DUK_MS_FLAG_NO_STRINGTABLE_RESIZE |  /* avoid recursive string table call */ \
                DUK_MS_FLAG_NO_FINALIZERS |          /* avoid pressure to add/remove strings, invalidation of call data argument, etc. */ \
                DUK_MS_FLAG_NO_OBJECT_COMPACTION;    /* avoid array abandoning which interns strings */ \
    } while (0)

Definition at line 14 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

#define DUK__PREVENT_MS_SIDE_EFFECTS(heap) do { \
        (heap)->mark_and_sweep_base_flags |= \
                DUK_MS_FLAG_NO_STRINGTABLE_RESIZE |  /* avoid recursive string table call */ \
                DUK_MS_FLAG_NO_FINALIZERS |          /* avoid pressure to add/remove strings, invalidation of call data argument, etc. */ \
                DUK_MS_FLAG_NO_OBJECT_COMPACTION;    /* avoid array abandoning which interns strings */ \
    } while (0)

Referenced by duk__do_intern(), and duk_heap_force_strtab_resize().

Function Documentation

duk__alloc_init_hstring()

DUK_LOCAL duk_hstring * duk__alloc_init_hstring	(	duk_heap *	heap,
		const duk_uint8_t *	str,
		duk_uint32_t	blen,
		duk_uint32_t	strhash,
		const duk_uint8_t *	extdata )

Definition at line 32 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                 {
    duk_hstring *res = NULL;
    duk_uint8_t *data;
    duk_size_t alloc_size;
    duk_uarridx_t dummy;
    duk_uint32_t clen;
 
#if defined(DUK_USE_STRLEN16)
    /* If blen <= 0xffffUL, clen is also guaranteed to be <= 0xffffUL. */
    if (blen > 0xffffUL) {
        DUK_D(DUK_DPRINT("16-bit string blen/clen active and blen over 16 bits, reject intern"));
        return NULL;
    }
#endif
 
    if (extdata) {
        alloc_size = (duk_size_t) sizeof(duk_hstring_external);
        res = (duk_hstring *) DUK_ALLOC(heap, alloc_size);
        if (!res) {
            goto alloc_error;
        }
        DUK_MEMZERO(res, sizeof(duk_hstring_external));
#if defined(DUK_USE_EXPLICIT_NULL_INIT)
        DUK_HEAPHDR_STRING_INIT_NULLS(&res->hdr);
#endif
        DUK_HEAPHDR_SET_TYPE_AND_FLAGS(&res->hdr, DUK_HTYPE_STRING, DUK_HSTRING_FLAG_EXTDATA);
 
        ((duk_hstring_external *) res)->extdata = extdata;
    } else {
        /* NUL terminate for convenient C access */
        alloc_size = (duk_size_t) (sizeof(duk_hstring) + blen + 1);
        res = (duk_hstring *) DUK_ALLOC(heap, alloc_size);
        if (!res) {
            goto alloc_error;
        }
        DUK_MEMZERO(res, sizeof(duk_hstring));
#if defined(DUK_USE_EXPLICIT_NULL_INIT)
        DUK_HEAPHDR_STRING_INIT_NULLS(&res->hdr);
#endif
        DUK_HEAPHDR_SET_TYPE_AND_FLAGS(&res->hdr, DUK_HTYPE_STRING, 0);
 
        data = (duk_uint8_t *) (res + 1);
        DUK_MEMCPY(data, str, blen);
        data[blen] = (duk_uint8_t) 0;
    }
 
    DUK_ASSERT(!DUK_HSTRING_HAS_ARRIDX(res));
    if (duk_js_to_arrayindex_raw_string(str, blen, &dummy)) {
        DUK_HSTRING_SET_ARRIDX(res);
    }
 
    /* All strings beginning with 0xff are treated as "internal",
     * even strings interned by the user.  This allows user code to
     * create internal properties too, and makes behavior consistent
     * in case user code happens to use a string also used by Duktape
     * (such as string has already been interned and has the 'internal'
     * flag set).
     */
    DUK_ASSERT(!DUK_HSTRING_HAS_INTERNAL(res));
    if (blen > 0 && str[0] == (duk_uint8_t) 0xff) {
        DUK_HSTRING_SET_INTERNAL(res);
    }
 
    DUK_HSTRING_SET_HASH(res, strhash);
    DUK_HSTRING_SET_BYTELEN(res, blen);
 
    clen = (duk_uint32_t) duk_unicode_unvalidated_utf8_length(str, (duk_size_t) blen);
    DUK_ASSERT(clen <= blen);
#if defined(DUK_USE_HSTRING_CLEN)
    DUK_HSTRING_SET_CHARLEN(res, clen);
#endif
 
    /* Using an explicit 'ASCII' flag has larger footprint (one call site
     * only) but is quite useful for the case when there's no explicit
     * 'clen' in duk_hstring.
     */
    DUK_ASSERT(!DUK_HSTRING_HAS_ASCII(res));
    if (clen == blen) {
        DUK_HSTRING_SET_ASCII(res);
    }
 
    DUK_DDD(DUK_DDDPRINT("interned string, hash=0x%08lx, blen=%ld, clen=%ld, has_arridx=%ld, has_extdata=%ld",
                         (unsigned long) DUK_HSTRING_GET_HASH(res),
                         (long) DUK_HSTRING_GET_BYTELEN(res),
                         (long) DUK_HSTRING_GET_CHARLEN(res),
                         (long) (DUK_HSTRING_HAS_ARRIDX(res) ? 1 : 0),
                         (long) (DUK_HSTRING_HAS_EXTDATA(res) ? 1 : 0)));
 
    return res;
 
 alloc_error:
    DUK_FREE(heap, res);
    return NULL;
}

References DUK_ALLOC, DUK_ASSERT, DUK_D, DUK_DDD, DUK_DDDPRINT, DUK_DPRINT, DUK_FREE, DUK_HEAPHDR_SET_TYPE_AND_FLAGS, DUK_HEAPHDR_STRING_INIT_NULLS, DUK_HSTRING_FLAG_EXTDATA, DUK_HSTRING_GET_BYTELEN, DUK_HSTRING_GET_CHARLEN, DUK_HSTRING_GET_HASH, DUK_HSTRING_HAS_ARRIDX, DUK_HSTRING_HAS_ASCII, DUK_HSTRING_HAS_EXTDATA, DUK_HSTRING_HAS_INTERNAL, DUK_HSTRING_SET_ARRIDX, DUK_HSTRING_SET_ASCII, DUK_HSTRING_SET_BYTELEN, DUK_HSTRING_SET_CHARLEN, DUK_HSTRING_SET_HASH, DUK_HSTRING_SET_INTERNAL, DUK_HTYPE_STRING, duk_js_to_arrayindex_raw_string(), DUK_MEMCPY, DUK_MEMZERO, duk_unicode_unvalidated_utf8_length(), dummy, duk_hstring::hdr, and NULL.

Referenced by duk__do_intern().

duk__count_used_probe()

DUK_LOCAL duk_int_t duk__count_used_probe

(

duk_heap *

heap

)

Definition at line 469 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                          {
    duk_int_t res = 0;
    duk_uint_fast32_t i, n;
#if defined(DUK_USE_HEAPPTR16)
    duk_uint16_t null16 = heap->heapptr_null16;
    duk_uint16_t deleted16 = heap->heapptr_deleted16;
#endif
 
    n = (duk_uint_fast32_t) heap->st_size;
    for (i = 0; i < n; i++) {
#if defined(DUK_USE_HEAPPTR16)
        if (heap->strtable16[i] != null16 && heap->strtable16[i] != deleted16) {
#else
        if (heap->strtable[i] != NULL && heap->strtable[i] != DUK__DELETED_MARKER(heap)) {
#endif
            res++;
        }
    }
    return res;
}

References DUK__DELETED_MARKER, duk__insert_hstring_probe(), DUK_LOCAL, NULL, duk_heap::st_size, and duk_heap::strtable.

Referenced by duk__resize_strtab_probe(), and duk__resize_strtab_raw_probe().

duk__do_intern()

DUK_LOCAL duk_hstring * duk__do_intern	(	duk_heap *	heap,
		const duk_uint8_t *	str,
		duk_uint32_t	blen,
		duk_uint32_t	strhash )

Definition at line 833 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                                                       {
    duk_hstring *res;
    const duk_uint8_t *extdata;
#if defined(DUK_USE_MARK_AND_SWEEP)
    duk_small_uint_t prev_mark_and_sweep_base_flags;
#endif
 
    /* Prevent any side effects on the string table and the caller provided
     * str/blen arguments while interning is in progress.  For example, if
     * the caller provided str/blen from a dynamic buffer, a finalizer might
     * resize that dynamic buffer, invalidating the call arguments.
     */
#if defined(DUK_USE_MARK_AND_SWEEP)
    DUK_ASSERT((heap->mark_and_sweep_base_flags & DUK_MS_FLAG_NO_STRINGTABLE_RESIZE) == 0);
    prev_mark_and_sweep_base_flags = heap->mark_and_sweep_base_flags;
    DUK__PREVENT_MS_SIDE_EFFECTS(heap);
#endif
 
#if defined(DUK_USE_STRTAB_PROBE)
    if (duk__recheck_strtab_size_probe(heap, heap->st_used + 1)) {
        goto failed;
    }
#endif
 
    /* For manual testing only. */
#if 0
    {
        duk_size_t i;
        DUK_PRINTF("INTERN: \"");
        for (i = 0; i < blen; i++) {
            duk_uint8_t x = str[i];
            if (x >= 0x20 && x <= 0x7e && x != '"' && x != '\\') {
                DUK_PRINTF("%c", (int) x);  /* char: use int cast */
            } else {
                DUK_PRINTF("\\x%02lx", (long) x);
            }
        }
        DUK_PRINTF("\"\n");
    }
#endif
 
#if defined(DUK_USE_HSTRING_EXTDATA) && defined(DUK_USE_EXTSTR_INTERN_CHECK)
    extdata = (const duk_uint8_t *) DUK_USE_EXTSTR_INTERN_CHECK(heap->heap_udata, (void *) DUK_LOSE_CONST(str), (duk_size_t) blen);
#else
    extdata = (const duk_uint8_t *) NULL;
#endif
    res = duk__alloc_init_hstring(heap, str, blen, strhash, extdata);
    if (!res) {
        goto failed;
    }
 
#if defined(DUK_USE_STRTAB_CHAIN)
    if (duk__insert_hstring_chain(heap, res)) {
        /* failed */
        DUK_FREE(heap, res);
        goto failed;
    }
#elif defined(DUK_USE_STRTAB_PROBE)
    /* guaranteed to succeed */
    duk__insert_hstring_probe(heap,
#if defined(DUK_USE_HEAPPTR16)
                              heap->strtable16,
#else
                              heap->strtable,
#endif
                              heap->st_size,
                              &heap->st_used,
                              res);
#else
#error internal error, invalid strtab options
#endif
 
    /* Note: hstring is in heap but has refcount zero and is not strongly reachable.
     * Caller should increase refcount and make the hstring reachable before any
     * operations which require allocation (and possible gc).
     */
 
 done:
#if defined(DUK_USE_MARK_AND_SWEEP)
    heap->mark_and_sweep_base_flags = prev_mark_and_sweep_base_flags;
#endif
    return res;
 
 failed:
    res = NULL;
    goto done;
}

References duk__alloc_init_hstring(), duk__insert_hstring_probe(), DUK__PREVENT_MS_SIDE_EFFECTS, duk__recheck_strtab_size_probe(), DUK_ASSERT, DUK_FREE, DUK_LOSE_CONST, DUK_MS_FLAG_NO_STRINGTABLE_RESIZE, DUK_PRINTF, duk_heap::heap_udata, duk_heap::mark_and_sweep_base_flags, NULL, duk_heap::st_size, duk_heap::st_used, and duk_heap::strtable.

Referenced by duk_heap_string_intern().

duk__do_lookup()

DUK_LOCAL duk_hstring * duk__do_lookup	(	duk_heap *	heap,
		const duk_uint8_t *	str,
		duk_uint32_t	blen,
		duk_uint32_t *	out_strhash )

Definition at line 921 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                                                            {
    duk_hstring *res;
 
    DUK_ASSERT(out_strhash);
 
    *out_strhash = duk_heap_hashstring(heap, str, (duk_size_t) blen);
 
#if defined(DUK_USE_ROM_STRINGS)
    {
        duk_small_uint_t i;
        /* XXX: This is VERY inefficient now, and should be e.g. a
         * binary search or perfect hash, to be fixed.
         */
        for (i = 0; i < (duk_small_uint_t) (sizeof(duk_rom_strings) / sizeof(duk_hstring *)); i++) {
            duk_hstring *romstr;
            romstr = (duk_hstring *) DUK_LOSE_CONST(duk_rom_strings[i]);
            if (blen == DUK_HSTRING_GET_BYTELEN(romstr) &&
                DUK_MEMCMP((const void *) str, (const void *) DUK_HSTRING_GET_DATA(romstr), blen) == 0) {
                DUK_DD(DUK_DDPRINT("intern check: rom string: %!O, computed hash 0x%08lx, rom hash 0x%08lx",
                                   romstr, (unsigned long) *out_strhash, (unsigned long) DUK_HSTRING_GET_HASH(romstr)));
                DUK_ASSERT(*out_strhash == DUK_HSTRING_GET_HASH(romstr));
                *out_strhash = DUK_HSTRING_GET_HASH(romstr);
                return romstr;
            }
        }
    }
#endif  /* DUK_USE_ROM_STRINGS */
 
#if defined(DUK_USE_STRTAB_CHAIN)
    res = duk__find_matching_string_chain(heap, str, blen, *out_strhash);
#elif defined(DUK_USE_STRTAB_PROBE)
    res = duk__find_matching_string_probe(heap,
#if defined(DUK_USE_HEAPPTR16)
                                          heap->strtable16,
#else
                                          heap->strtable,
#endif
                                          heap->st_size,
                                          str,
                                          blen,
                                          *out_strhash);
#else
#error internal error, invalid strtab options
#endif
 
    return res;
}

References duk__find_matching_string_probe(), DUK_ASSERT, DUK_DD, DUK_DDPRINT, duk_heap_hashstring(), DUK_HSTRING_GET_BYTELEN, DUK_HSTRING_GET_DATA, DUK_HSTRING_GET_HASH, DUK_LOSE_CONST, DUK_MEMCMP, duk_heap::st_size, and duk_heap::strtable.

Referenced by duk_heap_string_intern().

duk__find_matching_string_probe()

DUK_LOCAL duk_hstring * duk__find_matching_string_probe	(	duk_heap *	heap,
		duk_hstring **	entries,
		duk_uint32_t	size,
		const duk_uint8_t *	str,
		duk_uint32_t	blen,
		duk_uint32_t	strhash )

Definition at line 554 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                                                                                                                  {
#endif
    duk_uint32_t i;
    duk_uint32_t step;
 
    DUK_ASSERT(size > 0);
 
    i = DUK__HASH_INITIAL(strhash, size);
    step = DUK__HASH_PROBE_STEP(strhash);
    for (;;) {
        duk_hstring *e;
#if defined(DUK_USE_HEAPPTR16)
        e = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, entries16[i]);
#else
        e = entries[i];
#endif
 
        if (!e) {
            return NULL;
        }
        if (e != DUK__DELETED_MARKER(heap) && DUK_HSTRING_GET_BYTELEN(e) == blen) {
            if (DUK_MEMCMP((const void *) str, (const void *) DUK_HSTRING_GET_DATA(e), (size_t) blen) == 0) {
                DUK_DDD(DUK_DDDPRINT("find matching hit: %ld (step %ld, size %ld)",
                                     (long) i, (long) step, (long) size));
                return e;
            }
        }
        DUK_DDD(DUK_DDDPRINT("find matching miss: %ld (step %ld, size %ld)",
                             (long) i, (long) step, (long) size));
        i = (i + step) % size;
 
        /* looping should never happen */
        DUK_ASSERT(i != DUK__HASH_INITIAL(strhash, size));
    }
    DUK_UNREACHABLE();
}

References DUK__DELETED_MARKER, DUK__HASH_INITIAL, DUK__HASH_PROBE_STEP, DUK_ASSERT, DUK_DDD, DUK_DDDPRINT, DUK_HSTRING_GET_BYTELEN, DUK_HSTRING_GET_DATA, DUK_MEMCMP, DUK_UNREACHABLE, duk_heap::heap_udata, and NULL.

Referenced by duk__do_lookup(), and duk__insert_hstring_probe().

duk__insert_hstring_probe()

DUK_LOCAL void duk__insert_hstring_probe	(	duk_heap *	heap,
		duk_hstring **	entries,
		duk_uint32_t	size,
		duk_uint32_t *	p_used,
		duk_hstring *	h )

Definition at line 493 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                                                                         {
#endif
    duk_uint32_t i;
    duk_uint32_t step;
#if defined(DUK_USE_HEAPPTR16)
    duk_uint16_t null16 = heap->heapptr_null16;
    duk_uint16_t deleted16 = heap->heapptr_deleted16;
#endif
 
    DUK_ASSERT(size > 0);
 
    i = DUK__HASH_INITIAL(DUK_HSTRING_GET_HASH(h), size);
    step = DUK__HASH_PROBE_STEP(DUK_HSTRING_GET_HASH(h));
    for (;;) {
#if defined(DUK_USE_HEAPPTR16)
        duk_uint16_t e16 = entries16[i];
#else
        duk_hstring *e = entries[i];
#endif
 
#if defined(DUK_USE_HEAPPTR16)
        /* XXX: could check for e16 == 0 because NULL is guaranteed to
         * encode to zero.
         */
        if (e16 == null16) {
#else
        if (e == NULL) {
#endif
            DUK_DDD(DUK_DDDPRINT("insert hit (null): %ld", (long) i));
#if defined(DUK_USE_HEAPPTR16)
            entries16[i] = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
#else
            entries[i] = h;
#endif
            (*p_used)++;
            break;
#if defined(DUK_USE_HEAPPTR16)
        } else if (e16 == deleted16) {
#else
        } else if (e == DUK__DELETED_MARKER(heap)) {
#endif
            /* st_used remains the same, DELETED is counted as used */
            DUK_DDD(DUK_DDDPRINT("insert hit (deleted): %ld", (long) i));
#if defined(DUK_USE_HEAPPTR16)
            entries16[i] = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
#else
            entries[i] = h;
#endif
            break;
        }
        DUK_DDD(DUK_DDDPRINT("insert miss: %ld", (long) i));
        i = (i + step) % size;
 
        /* looping should never happen */
        DUK_ASSERT(i != DUK__HASH_INITIAL(DUK_HSTRING_GET_HASH(h), size));
    }
}

References DUK__DELETED_MARKER, duk__find_matching_string_probe(), DUK__HASH_INITIAL, DUK__HASH_PROBE_STEP, DUK_ASSERT, DUK_DDD, DUK_DDDPRINT, DUK_HSTRING_GET_HASH, DUK_LOCAL, duk_heap::heap_udata, and NULL.

Referenced by duk__count_used_probe(), duk__do_intern(), and duk__resize_strtab_raw_probe().

duk__recheck_strtab_size_probe()

DUK_LOCAL duk_bool_t duk__recheck_strtab_size_probe	(	duk_heap *	heap,
		duk_uint32_t	new_used )

Definition at line 780 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                           {
    duk_uint32_t new_free;
    duk_uint32_t tmp1;
    duk_uint32_t tmp2;
 
    DUK_ASSERT(new_used <= heap->st_size);  /* grow by at most one */
    new_free = heap->st_size - new_used;    /* unsigned intentionally */
 
    /* new_free / size <= 1 / DIV  <=>  new_free <= size / DIV */
    /* new_used / size <= 1 / DIV  <=>  new_used <= size / DIV */
 
    tmp1 = heap->st_size / DUK_STRTAB_MIN_FREE_DIVISOR;
    tmp2 = heap->st_size / DUK_STRTAB_MIN_USED_DIVISOR;
 
    if (new_free <= tmp1 || new_used <= tmp2) {
        /* load factor too low or high, count actually used entries and resize */
        return duk__resize_strtab_probe(heap);
    } else {
        return 0;  /* OK */
    }
}

References duk__resize_strtab_probe(), DUK_ASSERT, DUK_STRTAB_MIN_FREE_DIVISOR, DUK_STRTAB_MIN_USED_DIVISOR, and duk_heap::st_size.

Referenced by duk__do_intern().

duk__remove_matching_hstring_probe()

DUK_LOCAL void duk__remove_matching_hstring_probe	(	duk_heap *	heap,
		duk_hstring **	entries,
		duk_uint32_t	size,
		duk_hstring *	h )

Definition at line 594 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                                                            {
#endif
    duk_uint32_t i;
    duk_uint32_t step;
    duk_uint32_t hash;
#if defined(DUK_USE_HEAPPTR16)
    duk_uint16_t null16 = heap->heapptr_null16;
    duk_uint16_t h16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
#endif
 
    DUK_ASSERT(size > 0);
 
    hash = DUK_HSTRING_GET_HASH(h);
    i = DUK__HASH_INITIAL(hash, size);
    step = DUK__HASH_PROBE_STEP(hash);
    for (;;) {
#if defined(DUK_USE_HEAPPTR16)
        duk_uint16_t e16 = entries16[i];
#else
        duk_hstring *e = entries[i];
#endif
 
#if defined(DUK_USE_HEAPPTR16)
        if (e16 == null16) {
#else
        if (!e) {
#endif
            DUK_UNREACHABLE();
            break;
        }
#if defined(DUK_USE_HEAPPTR16)
        if (e16 == h16) {
#else
        if (e == h) {
#endif
            /* st_used remains the same, DELETED is counted as used */
            DUK_DDD(DUK_DDDPRINT("free matching hit: %ld", (long) i));
#if defined(DUK_USE_HEAPPTR16)
            entries16[i] = heap->heapptr_deleted16;
#else
            entries[i] = DUK__DELETED_MARKER(heap);
#endif
            break;
        }
 
        DUK_DDD(DUK_DDDPRINT("free matching miss: %ld", (long) i));
        i = (i + step) % size;
 
        /* looping should never happen */
        DUK_ASSERT(i != DUK__HASH_INITIAL(hash, size));
    }
}

References DUK__DELETED_MARKER, DUK__HASH_INITIAL, DUK__HASH_PROBE_STEP, DUK_ASSERT, DUK_DDD, DUK_DDDPRINT, DUK_HSTRING_GET_HASH, DUK_UNREACHABLE, and duk_heap::heap_udata.

Referenced by duk_heap_string_remove().

duk__resize_strtab_probe()

DUK_LOCAL duk_bool_t duk__resize_strtab_probe

(

duk_heap *

heap

)

Definition at line 758 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                              {
    duk_uint32_t new_size;
    duk_bool_t ret;
 
    new_size = (duk_uint32_t) duk__count_used_probe(heap);
    if (new_size >= 0x80000000UL) {
        new_size = DUK_STRTAB_HIGHEST_32BIT_PRIME;
    } else {
        new_size = duk_util_get_hash_prime(DUK_STRTAB_GROW_ST_SIZE(new_size));
        new_size = duk_util_get_hash_prime(new_size);
    }
    DUK_ASSERT(new_size > 0);
 
    /* rehash even if old and new sizes are the same to get rid of
     * DELETED entries.
    */
 
    ret = duk__resize_strtab_raw_probe(heap, new_size);
 
    return ret;
}

References duk__count_used_probe(), duk__resize_strtab_raw_probe(), DUK_ASSERT, DUK_STRTAB_GROW_ST_SIZE, DUK_STRTAB_HIGHEST_32BIT_PRIME, and duk_util_get_hash_prime().

Referenced by duk__recheck_strtab_size_probe(), and duk_heap_force_strtab_resize().

duk__resize_strtab_raw_probe()

DUK_LOCAL duk_bool_t duk__resize_strtab_raw_probe	(	duk_heap *	heap,
		duk_uint32_t	new_size )

Definition at line 647 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                         {
#if defined(DUK_USE_DEBUG)
    duk_uint32_t old_used = heap->st_used;
#endif
    duk_uint32_t old_size = heap->st_size;
#if defined(DUK_USE_HEAPPTR16)
    duk_uint16_t *old_entries = heap->strtable16;
    duk_uint16_t *new_entries = NULL;
#else
    duk_hstring **old_entries = heap->strtable;
    duk_hstring **new_entries = NULL;
#endif
    duk_uint32_t new_used = 0;
    duk_uint32_t i;
 
#if defined(DUK_USE_DEBUG)
    DUK_UNREF(old_used);  /* unused with some debug level combinations */
#endif
 
#ifdef DUK_USE_DDDPRINT
    DUK_DDD(DUK_DDDPRINT("attempt to resize stringtable: %ld entries, %ld bytes, %ld used, %ld%% load -> %ld entries, %ld bytes, %ld used, %ld%% load",
                         (long) old_size, (long) (sizeof(duk_hstring *) * old_size), (long) old_used,
                         (long) (((double) old_used) / ((double) old_size) * 100.0),
                         (long) new_size, (long) (sizeof(duk_hstring *) * new_size), (long) duk__count_used_probe(heap),
                         (long) (((double) duk__count_used_probe(heap)) / ((double) new_size) * 100.0)));
#endif
 
    DUK_ASSERT(new_size > (duk_uint32_t) duk__count_used_probe(heap));  /* required for rehash to succeed, equality not that useful */
    DUK_ASSERT(old_entries);
 
    /*
     *  The attempt to allocate may cause a GC.  Such a GC must not attempt to resize
     *  the stringtable (though it can be swept); finalizer execution and object
     *  compaction must also be postponed to avoid the pressure to add strings to the
     *  string table.  Call site must prevent these.
     */
 
#if defined(DUK_USE_MARK_AND_SWEEP)
    DUK_ASSERT(heap->mark_and_sweep_base_flags & DUK_MS_FLAG_NO_STRINGTABLE_RESIZE);
    DUK_ASSERT(heap->mark_and_sweep_base_flags & DUK_MS_FLAG_NO_FINALIZERS);
    DUK_ASSERT(heap->mark_and_sweep_base_flags & DUK_MS_FLAG_NO_OBJECT_COMPACTION);
#endif
 
#if defined(DUK_USE_HEAPPTR16)
    new_entries = (duk_uint16_t *) DUK_ALLOC(heap, sizeof(duk_uint16_t) * new_size);
#else
    new_entries = (duk_hstring **) DUK_ALLOC(heap, sizeof(duk_hstring *) * new_size);
#endif
 
    if (!new_entries) {
        goto resize_error;
    }
 
#if defined(DUK_USE_EXPLICIT_NULL_INIT)
    for (i = 0; i < new_size; i++) {
#if defined(DUK_USE_HEAPPTR16)
        new_entries[i] = heap->heapptr_null16;
#else
        new_entries[i] = NULL;
#endif
    }
#else
#if defined(DUK_USE_HEAPPTR16)
    /* Relies on NULL encoding to zero. */
    DUK_MEMZERO(new_entries, sizeof(duk_uint16_t) * new_size);
#else
    DUK_MEMZERO(new_entries, sizeof(duk_hstring *) * new_size);
#endif
#endif
 
    /* Because new_size > duk__count_used_probe(heap), guaranteed to work */
    for (i = 0; i < old_size; i++) {
        duk_hstring *e;
 
#if defined(DUK_USE_HEAPPTR16)
        e = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, old_entries[i]);
#else
        e = old_entries[i];
#endif
        if (e == NULL || e == DUK__DELETED_MARKER(heap)) {
            continue;
        }
        /* checking for DUK__DELETED_MARKER is not necessary here, but helper does it now */
        duk__insert_hstring_probe(heap, new_entries, new_size, &new_used, e);
    }
 
#ifdef DUK_USE_DDPRINT
    DUK_DD(DUK_DDPRINT("resized stringtable: %ld entries, %ld bytes, %ld used, %ld%% load -> %ld entries, %ld bytes, %ld used, %ld%% load",
                       (long) old_size, (long) (sizeof(duk_hstring *) * old_size), (long) old_used,
                       (long) (((double) old_used) / ((double) old_size) * 100.0),
                       (long) new_size, (long) (sizeof(duk_hstring *) * new_size), (long) new_used,
                       (long) (((double) new_used) / ((double) new_size) * 100.0)));
#endif
 
#if defined(DUK_USE_HEAPPTR16)
    DUK_FREE(heap, heap->strtable16);
    heap->strtable16 = new_entries;
#else
    DUK_FREE(heap, heap->strtable);
    heap->strtable = new_entries;
#endif
    heap->st_size = new_size;
    heap->st_used = new_used;  /* may be less, since DELETED entries are NULLed by rehash */
 
    return 0;  /* OK */
 
 resize_error:
    DUK_FREE(heap, new_entries);
    return 1;  /* FAIL */
}

References duk__count_used_probe(), DUK__DELETED_MARKER, duk__insert_hstring_probe(), DUK_ALLOC, DUK_ASSERT, DUK_DD, DUK_DDD, DUK_DDDPRINT, DUK_DDPRINT, DUK_FREE, DUK_MEMZERO, DUK_MS_FLAG_NO_FINALIZERS, DUK_MS_FLAG_NO_OBJECT_COMPACTION, DUK_MS_FLAG_NO_STRINGTABLE_RESIZE, DUK_UNREF, duk_heap::heap_udata, duk_heap::mark_and_sweep_base_flags, NULL, duk_heap::st_size, duk_heap::st_used, and duk_heap::strtable.

Referenced by duk__resize_strtab_probe().

duk_heap_force_strtab_resize()

DUK_INTERNAL void duk_heap_force_strtab_resize

(

duk_heap *

heap

)

Definition at line 1053 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                               {
    duk_small_uint_t prev_mark_and_sweep_base_flags;
    /* Force a resize so that DELETED entries are eliminated.
     * Another option would be duk__recheck_strtab_size_probe();
     * but since that happens on every intern anyway, this whole
     * check can now be disabled.
     */
 
    DUK_ASSERT((heap->mark_and_sweep_base_flags & DUK_MS_FLAG_NO_STRINGTABLE_RESIZE) == 0);
    prev_mark_and_sweep_base_flags = heap->mark_and_sweep_base_flags;
    DUK__PREVENT_MS_SIDE_EFFECTS(heap);
 
#if defined(DUK_USE_STRTAB_CHAIN)
    DUK_UNREF(heap);
#elif defined(DUK_USE_STRTAB_PROBE)
    (void) duk__resize_strtab_probe(heap);
#endif
 
    heap->mark_and_sweep_base_flags = prev_mark_and_sweep_base_flags;
}

References DUK__PREVENT_MS_SIDE_EFFECTS, duk__resize_strtab_probe(), DUK_ASSERT, DUK_MS_FLAG_NO_STRINGTABLE_RESIZE, DUK_UNREF, and duk_heap::mark_and_sweep_base_flags.

duk_heap_free_strtab()

DUK_INTERNAL void duk_heap_free_strtab

(

duk_heap *

heap

)

Definition at line 1139 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                       {
    duk_uint_fast32_t i;
    duk_hstring *h;
 
#if defined(DUK_USE_HEAPPTR16)
    if (heap->strtable16) {
#else
    if (heap->strtable) {
#endif
        for (i = 0; i < (duk_uint_fast32_t) heap->st_size; i++) {
#if defined(DUK_USE_HEAPPTR16)
            h = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, heap->strtable16[i]);
#else
            h = heap->strtable[i];
#endif
            if (h == NULL || h == DUK_STRTAB_DELETED_MARKER(heap)) {
                continue;
            }
            DUK_ASSERT(h != NULL);
 
            /* strings may have inner refs (extdata) in some cases */
            duk_free_hstring_inner(heap, h);
            DUK_FREE(heap, h);
#if 0  /* not strictly necessary */
            heap->strtable[i] = NULL;
#endif
        }
#if defined(DUK_USE_HEAPPTR16)
        DUK_FREE(heap, heap->strtable16);
#else
        DUK_FREE(heap, heap->strtable);
#endif
#if 0  /* not strictly necessary */
        heap->strtable = NULL;
#endif
    }
}

References DUK_ASSERT, DUK_FREE, duk_free_hstring_inner(), DUK_STRTAB_DELETED_MARKER, duk_heap::heap_udata, NULL, duk_heap::st_size, and duk_heap::strtable.

duk_heap_string_intern()

DUK_INTERNAL duk_hstring * duk_heap_string_intern	(	duk_heap *	heap,
		const duk_uint8_t *	str,
		duk_uint32_t	blen )

Definition at line 980 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                                            {
    duk_hstring *res;
    duk_uint32_t strhash;
 
    /* caller is responsible for ensuring this */
    DUK_ASSERT(blen <= DUK_HSTRING_MAX_BYTELEN);
 
    res = duk__do_lookup(heap, str, blen, &strhash);
    if (res) {
        return res;
    }
 
    res = duk__do_intern(heap, str, blen, strhash);
    return res;  /* may be NULL */
}

References duk__do_intern(), duk__do_lookup(), DUK_ASSERT, and DUK_HSTRING_MAX_BYTELEN.

Referenced by duk_heap_string_intern_checked(), and duk_heap_string_intern_u32().

duk_heap_string_intern_checked()

DUK_INTERNAL duk_hstring * duk_heap_string_intern_checked	(	duk_hthread *	thr,
		const duk_uint8_t *	str,
		duk_uint32_t	blen )

Definition at line 996 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                                                      {
    duk_hstring *res = duk_heap_string_intern(thr->heap, str, blen);
    if (!res) {
        DUK_ERROR_ALLOC_DEFMSG(thr);
    }
    return res;
}

References DUK_ERROR_ALLOC_DEFMSG, duk_heap_string_intern(), and duk_hthread::heap.

duk_heap_string_intern_u32()

DUK_INTERNAL duk_hstring * duk_heap_string_intern_u32	(	duk_heap *	heap,
		duk_uint32_t	val )

Definition at line 1014 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                       {
    char buf[DUK_STRTAB_U32_MAX_STRLEN+1];
    DUK_SNPRINTF(buf, sizeof(buf), "%lu", (unsigned long) val);
    buf[sizeof(buf) - 1] = (char) 0;
    DUK_ASSERT(DUK_STRLEN(buf) <= DUK_UINT32_MAX);  /* formatted result limited */
    return duk_heap_string_intern(heap, (const duk_uint8_t *) buf, (duk_uint32_t) DUK_STRLEN(buf));
}

References DUK_ASSERT, duk_heap_string_intern(), DUK_SNPRINTF, DUK_STRLEN, DUK_STRTAB_U32_MAX_STRLEN, and DUK_UINT32_MAX.

Referenced by duk_heap_string_intern_u32_checked().

duk_heap_string_intern_u32_checked()

DUK_INTERNAL duk_hstring * duk_heap_string_intern_u32_checked	(	duk_hthread *	thr,
		duk_uint32_t	val )

Definition at line 1022 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                                                 {
    duk_hstring *res = duk_heap_string_intern_u32(thr->heap, val);
    if (!res) {
        DUK_ERROR_ALLOC_DEFMSG(thr);
    }
    return res;
}

References DUK_ERROR_ALLOC_DEFMSG, duk_heap_string_intern_u32(), and duk_hthread::heap.

duk_heap_string_remove()

DUK_INTERNAL void duk_heap_string_remove	(	duk_heap *	heap,
		duk_hstring *	h )

Definition at line 1032 of file duktape-1.5.2/src-separate/duk_heap_stringtable.c.

                                                                         {
    DUK_DDD(DUK_DDDPRINT("remove string from stringtable: %!O", (duk_heaphdr *) h));
 
#if defined(DUK_USE_STRTAB_CHAIN)
    duk__remove_matching_hstring_chain(heap, h);
#elif defined(DUK_USE_STRTAB_PROBE)
    duk__remove_matching_hstring_probe(heap,
#if defined(DUK_USE_HEAPPTR16)
                                       heap->strtable16,
#else
                                       heap->strtable,
#endif
                                       heap->st_size,
                                       h);
#else
#error internal error, invalid strtab options
#endif
}

References duk__remove_matching_hstring_probe(), DUK_DDD, DUK_DDDPRINT, duk_heap::st_size, and duk_heap::strtable.