2 * Heap stringtable handling, string interning.
5 #include "duk_internal.h"
7 #if defined(DUK_USE_STRTAB_PROBE)
8 #define DUK__HASH_INITIAL(hash,h_size) DUK_STRTAB_HASH_INITIAL((hash),(h_size))
9 #define DUK__HASH_PROBE_STEP(hash) DUK_STRTAB_HASH_PROBE_STEP((hash))
10 #define DUK__DELETED_MARKER(heap) DUK_STRTAB_DELETED_MARKER((heap))
13 #if defined(DUK_USE_MARK_AND_SWEEP)
14 #define DUK__PREVENT_MS_SIDE_EFFECTS(heap) do { \
15 (heap)->mark_and_sweep_base_flags |= \
16 DUK_MS_FLAG_NO_STRINGTABLE_RESIZE | /* avoid recursive string table call */ \
17 DUK_MS_FLAG_NO_FINALIZERS | /* avoid pressure to add/remove strings, invalidation of call data argument, etc. */ \
18 DUK_MS_FLAG_NO_OBJECT_COMPACTION; /* avoid array abandoning which interns strings */ \
23 * Create a hstring and insert into the heap. The created object
24 * is directly garbage collectable with reference count zero.
26 * The caller must place the interned string into the stringtable
27 * immediately (without chance of a longjmp); otherwise the string
32 duk_hstring
*duk__alloc_init_hstring(duk_heap
*heap
,
33 const duk_uint8_t
*str
,
36 const duk_uint8_t
*extdata
) {
37 duk_hstring
*res
= NULL
;
39 duk_size_t alloc_size
;
43 #if defined(DUK_USE_STRLEN16)
44 /* If blen <= 0xffffUL, clen is also guaranteed to be <= 0xffffUL. */
45 if (blen
> 0xffffUL
) {
46 DUK_D(DUK_DPRINT("16-bit string blen/clen active and blen over 16 bits, reject intern"));
52 alloc_size
= (duk_size_t
) sizeof(duk_hstring_external
);
53 res
= (duk_hstring
*) DUK_ALLOC(heap
, alloc_size
);
57 DUK_MEMZERO(res
, sizeof(duk_hstring_external
));
58 #if defined(DUK_USE_EXPLICIT_NULL_INIT)
59 DUK_HEAPHDR_STRING_INIT_NULLS(&res
->hdr
);
61 DUK_HEAPHDR_SET_TYPE_AND_FLAGS(&res
->hdr
, DUK_HTYPE_STRING
, DUK_HSTRING_FLAG_EXTDATA
);
63 ((duk_hstring_external
*) res
)->extdata
= extdata
;
65 /* NUL terminate for convenient C access */
66 alloc_size
= (duk_size_t
) (sizeof(duk_hstring
) + blen
+ 1);
67 res
= (duk_hstring
*) DUK_ALLOC(heap
, alloc_size
);
71 DUK_MEMZERO(res
, sizeof(duk_hstring
));
72 #if defined(DUK_USE_EXPLICIT_NULL_INIT)
73 DUK_HEAPHDR_STRING_INIT_NULLS(&res
->hdr
);
75 DUK_HEAPHDR_SET_TYPE_AND_FLAGS(&res
->hdr
, DUK_HTYPE_STRING
, 0);
77 data
= (duk_uint8_t
*) (res
+ 1);
78 DUK_MEMCPY(data
, str
, blen
);
79 data
[blen
] = (duk_uint8_t
) 0;
82 DUK_ASSERT(!DUK_HSTRING_HAS_ARRIDX(res
));
83 if (duk_js_to_arrayindex_raw_string(str
, blen
, &dummy
)) {
84 DUK_HSTRING_SET_ARRIDX(res
);
87 /* All strings beginning with 0xff are treated as "internal",
88 * even strings interned by the user. This allows user code to
89 * create internal properties too, and makes behavior consistent
90 * in case user code happens to use a string also used by Duktape
91 * (such as string has already been interned and has the 'internal'
94 DUK_ASSERT(!DUK_HSTRING_HAS_INTERNAL(res
));
95 if (blen
> 0 && str
[0] == (duk_uint8_t
) 0xff) {
96 DUK_HSTRING_SET_INTERNAL(res
);
99 DUK_HSTRING_SET_HASH(res
, strhash
);
100 DUK_HSTRING_SET_BYTELEN(res
, blen
);
102 clen
= (duk_uint32_t
) duk_unicode_unvalidated_utf8_length(str
, (duk_size_t
) blen
);
103 DUK_ASSERT(clen
<= blen
);
104 #if defined(DUK_USE_HSTRING_CLEN)
105 DUK_HSTRING_SET_CHARLEN(res
, clen
);
108 /* Using an explicit 'ASCII' flag has larger footprint (one call site
109 * only) but is quite useful for the case when there's no explicit
110 * 'clen' in duk_hstring.
112 DUK_ASSERT(!DUK_HSTRING_HAS_ASCII(res
));
114 DUK_HSTRING_SET_ASCII(res
);
117 DUK_DDD(DUK_DDDPRINT("interned string, hash=0x%08lx, blen=%ld, clen=%ld, has_arridx=%ld, has_extdata=%ld",
118 (unsigned long) DUK_HSTRING_GET_HASH(res
),
119 (long) DUK_HSTRING_GET_BYTELEN(res
),
120 (long) DUK_HSTRING_GET_CHARLEN(res
),
121 (long) (DUK_HSTRING_HAS_ARRIDX(res
) ? 1 : 0),
122 (long) (DUK_HSTRING_HAS_EXTDATA(res
) ? 1 : 0)));
132 * String table algorithm: fixed size string table with array chaining
134 * The top level string table has a fixed size, with each slot holding
135 * either NULL, string pointer, or pointer to a separately allocated
136 * string pointer list.
138 * This is good for low memory environments using a pool allocator: the
139 * top level allocation has a fixed size and the pointer lists have quite
140 * small allocation size, which further matches the typical pool sizes
141 * needed by objects, strings, property tables, etc.
144 #if defined(DUK_USE_STRTAB_CHAIN)
146 #if defined(DUK_USE_HEAPPTR16)
147 DUK_LOCAL duk_bool_t
duk__insert_hstring_chain(duk_heap
*heap
, duk_hstring
*h
) {
148 duk_small_uint_t slotidx
;
151 duk_uint16_t
*new_lst
;
153 duk_uint16_t null16
= heap
->heapptr_null16
;
154 duk_uint16_t h16
= DUK_USE_HEAPPTR_ENC16(heap
->heap_udata
, (void *) h
);
156 DUK_ASSERT(heap
!= NULL
);
157 DUK_ASSERT(h
!= NULL
);
159 slotidx
= DUK_HSTRING_GET_HASH(h
) % DUK_STRTAB_CHAIN_SIZE
;
160 DUK_ASSERT(slotidx
< DUK_STRTAB_CHAIN_SIZE
);
162 e
= heap
->strtable
+ slotidx
;
163 if (e
->listlen
== 0) {
164 if (e
->u
.str16
== null16
) {
167 /* Now two entries in the same slot, alloc list */
168 lst
= (duk_uint16_t
*) DUK_ALLOC(heap
, sizeof(duk_uint16_t
) * 2);
174 e
->u
.strlist16
= DUK_USE_HEAPPTR_ENC16(heap
->heap_udata
, (void *) lst
);
178 DUK_ASSERT(e
->u
.strlist16
!= null16
);
179 lst
= (duk_uint16_t
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, e
->u
.strlist16
);
180 DUK_ASSERT(lst
!= NULL
);
181 for (i
= 0, n
= e
->listlen
; i
< n
; i
++) {
182 if (lst
[i
] == null16
) {
188 if (e
->listlen
+ 1 == 0) {
189 /* Overflow, relevant mainly when listlen is 16 bits. */
193 new_lst
= (duk_uint16_t
*) DUK_REALLOC(heap
, lst
, sizeof(duk_uint16_t
) * (e
->listlen
+ 1));
194 if (new_lst
== NULL
) {
197 new_lst
[e
->listlen
++] = h16
;
198 e
->u
.strlist16
= DUK_USE_HEAPPTR_ENC16(heap
->heap_udata
, (void *) new_lst
);
202 #else /* DUK_USE_HEAPPTR16 */
203 DUK_LOCAL duk_bool_t
duk__insert_hstring_chain(duk_heap
*heap
, duk_hstring
*h
) {
204 duk_small_uint_t slotidx
;
207 duk_hstring
**new_lst
;
210 DUK_ASSERT(heap
!= NULL
);
211 DUK_ASSERT(h
!= NULL
);
213 slotidx
= DUK_HSTRING_GET_HASH(h
) % DUK_STRTAB_CHAIN_SIZE
;
214 DUK_ASSERT(slotidx
< DUK_STRTAB_CHAIN_SIZE
);
216 e
= heap
->strtable
+ slotidx
;
217 if (e
->listlen
== 0) {
218 if (e
->u
.str
== NULL
) {
221 /* Now two entries in the same slot, alloc list */
222 lst
= (duk_hstring
**) DUK_ALLOC(heap
, sizeof(duk_hstring
*) * 2);
232 DUK_ASSERT(e
->u
.strlist
!= NULL
);
234 for (i
= 0, n
= e
->listlen
; i
< n
; i
++) {
235 if (lst
[i
] == NULL
) {
241 if (e
->listlen
+ 1 == 0) {
242 /* Overflow, relevant mainly when listlen is 16 bits. */
246 new_lst
= (duk_hstring
**) DUK_REALLOC(heap
, e
->u
.strlist
, sizeof(duk_hstring
*) * (e
->listlen
+ 1));
247 if (new_lst
== NULL
) {
250 new_lst
[e
->listlen
++] = h
;
251 e
->u
.strlist
= new_lst
;
255 #endif /* DUK_USE_HEAPPTR16 */
257 #if defined(DUK_USE_HEAPPTR16)
258 DUK_LOCAL duk_hstring
*duk__find_matching_string_chain(duk_heap
*heap
, const duk_uint8_t
*str
, duk_uint32_t blen
, duk_uint32_t strhash
) {
259 duk_small_uint_t slotidx
;
263 duk_uint16_t null16
= heap
->heapptr_null16
;
265 DUK_ASSERT(heap
!= NULL
);
267 slotidx
= strhash
% DUK_STRTAB_CHAIN_SIZE
;
268 DUK_ASSERT(slotidx
< DUK_STRTAB_CHAIN_SIZE
);
270 e
= heap
->strtable
+ slotidx
;
271 if (e
->listlen
== 0) {
272 if (e
->u
.str16
!= null16
) {
273 duk_hstring
*h
= (duk_hstring
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, e
->u
.str16
);
274 DUK_ASSERT(h
!= NULL
);
275 if (DUK_HSTRING_GET_BYTELEN(h
) == blen
&&
276 DUK_MEMCMP((const void *) str
, (const void *) DUK_HSTRING_GET_DATA(h
), (size_t) blen
) == 0) {
281 DUK_ASSERT(e
->u
.strlist16
!= null16
);
282 lst
= (duk_uint16_t
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, e
->u
.strlist16
);
283 DUK_ASSERT(lst
!= NULL
);
284 for (i
= 0, n
= e
->listlen
; i
< n
; i
++) {
285 if (lst
[i
] != null16
) {
286 duk_hstring
*h
= (duk_hstring
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, lst
[i
]);
287 DUK_ASSERT(h
!= NULL
);
288 if (DUK_HSTRING_GET_BYTELEN(h
) == blen
&&
289 DUK_MEMCMP((const void *) str
, (const void *) DUK_HSTRING_GET_DATA(h
), (size_t) blen
) == 0) {
298 #else /* DUK_USE_HEAPPTR16 */
299 DUK_LOCAL duk_hstring
*duk__find_matching_string_chain(duk_heap
*heap
, const duk_uint8_t
*str
, duk_uint32_t blen
, duk_uint32_t strhash
) {
300 duk_small_uint_t slotidx
;
305 DUK_ASSERT(heap
!= NULL
);
307 slotidx
= strhash
% DUK_STRTAB_CHAIN_SIZE
;
308 DUK_ASSERT(slotidx
< DUK_STRTAB_CHAIN_SIZE
);
310 e
= heap
->strtable
+ slotidx
;
311 if (e
->listlen
== 0) {
312 if (e
->u
.str
!= NULL
&&
313 DUK_HSTRING_GET_BYTELEN(e
->u
.str
) == blen
&&
314 DUK_MEMCMP((const void *) str
, (const void *) DUK_HSTRING_GET_DATA(e
->u
.str
), (size_t) blen
) == 0) {
318 DUK_ASSERT(e
->u
.strlist
!= NULL
);
320 for (i
= 0, n
= e
->listlen
; i
< n
; i
++) {
321 if (lst
[i
] != NULL
&&
322 DUK_HSTRING_GET_BYTELEN(lst
[i
]) == blen
&&
323 DUK_MEMCMP((const void *) str
, (const void *) DUK_HSTRING_GET_DATA(lst
[i
]), (size_t) blen
) == 0) {
331 #endif /* DUK_USE_HEAPPTR16 */
333 #if defined(DUK_USE_HEAPPTR16)
334 DUK_LOCAL
void duk__remove_matching_hstring_chain(duk_heap
*heap
, duk_hstring
*h
) {
335 duk_small_uint_t slotidx
;
340 duk_uint16_t null16
= heap
->heapptr_null16
;
342 DUK_ASSERT(heap
!= NULL
);
343 DUK_ASSERT(h
!= NULL
);
345 slotidx
= DUK_HSTRING_GET_HASH(h
) % DUK_STRTAB_CHAIN_SIZE
;
346 DUK_ASSERT(slotidx
< DUK_STRTAB_CHAIN_SIZE
);
348 DUK_ASSERT(h
!= NULL
);
349 h16
= DUK_USE_HEAPPTR_ENC16(heap
->heap_udata
, (void *) h
);
351 e
= heap
->strtable
+ slotidx
;
352 if (e
->listlen
== 0) {
353 if (e
->u
.str16
== h16
) {
358 DUK_ASSERT(e
->u
.strlist16
!= null16
);
359 lst
= (duk_uint16_t
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, e
->u
.strlist16
);
360 DUK_ASSERT(lst
!= NULL
);
361 for (i
= 0, n
= e
->listlen
; i
< n
; i
++) {
369 DUK_D(DUK_DPRINT("failed to find string that should be in stringtable"));
373 #else /* DUK_USE_HEAPPTR16 */
374 DUK_LOCAL
void duk__remove_matching_hstring_chain(duk_heap
*heap
, duk_hstring
*h
) {
375 duk_small_uint_t slotidx
;
380 DUK_ASSERT(heap
!= NULL
);
381 DUK_ASSERT(h
!= NULL
);
383 slotidx
= DUK_HSTRING_GET_HASH(h
) % DUK_STRTAB_CHAIN_SIZE
;
384 DUK_ASSERT(slotidx
< DUK_STRTAB_CHAIN_SIZE
);
386 e
= heap
->strtable
+ slotidx
;
387 if (e
->listlen
== 0) {
388 DUK_ASSERT(h
!= NULL
);
394 DUK_ASSERT(e
->u
.strlist
!= NULL
);
396 for (i
= 0, n
= e
->listlen
; i
< n
; i
++) {
397 DUK_ASSERT(h
!= NULL
);
405 DUK_D(DUK_DPRINT("failed to find string that should be in stringtable"));
409 #endif /* DUK_USE_HEAPPTR16 */
411 #if defined(DUK_USE_DEBUG)
412 DUK_INTERNAL
void duk_heap_dump_strtab(duk_heap
*heap
) {
415 duk_size_t j
, n
, used
;
416 #if defined(DUK_USE_HEAPPTR16)
418 duk_uint16_t null16
= heap
->heapptr_null16
;
423 DUK_ASSERT(heap
!= NULL
);
425 for (i
= 0; i
< DUK_STRTAB_CHAIN_SIZE
; i
++) {
426 e
= heap
->strtable
+ i
;
428 if (e
->listlen
== 0) {
429 #if defined(DUK_USE_HEAPPTR16)
430 DUK_DD(DUK_DDPRINT("[%03d] -> plain %d", (int) i
, (int) (e
->u
.str16
!= null16
? 1 : 0)));
432 DUK_DD(DUK_DDPRINT("[%03d] -> plain %d", (int) i
, (int) (e
->u
.str
? 1 : 0)));
436 #if defined(DUK_USE_HEAPPTR16)
437 lst
= (duk_uint16_t
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, e
->u
.strlist16
);
441 DUK_ASSERT(lst
!= NULL
);
442 for (j
= 0, n
= e
->listlen
; j
< n
; j
++) {
443 #if defined(DUK_USE_HEAPPTR16)
444 if (lst
[j
] != null16
) {
446 if (lst
[j
] != NULL
) {
451 DUK_DD(DUK_DDPRINT("[%03d] -> array %d/%d", (int) i
, (int) used
, (int) e
->listlen
));
455 #endif /* DUK_USE_DEBUG */
457 #endif /* DUK_USE_STRTAB_CHAIN */
460 * String table algorithm: closed hashing with a probe sequence
462 * This is the default algorithm and works fine for environments with
463 * minimal memory constraints.
466 #if defined(DUK_USE_STRTAB_PROBE)
468 /* Count actually used (non-NULL, non-DELETED) entries. */
469 DUK_LOCAL duk_int_t
duk__count_used_probe(duk_heap
*heap
) {
471 duk_uint_fast32_t i
, n
;
472 #if defined(DUK_USE_HEAPPTR16)
473 duk_uint16_t null16
= heap
->heapptr_null16
;
474 duk_uint16_t deleted16
= heap
->heapptr_deleted16
;
477 n
= (duk_uint_fast32_t
) heap
->st_size
;
478 for (i
= 0; i
< n
; i
++) {
479 #if defined(DUK_USE_HEAPPTR16)
480 if (heap
->strtable16
[i
] != null16
&& heap
->strtable16
[i
] != deleted16
) {
482 if (heap
->strtable
[i
] != NULL
&& heap
->strtable
[i
] != DUK__DELETED_MARKER(heap
)) {
490 #if defined(DUK_USE_HEAPPTR16)
491 DUK_LOCAL
void duk__insert_hstring_probe(duk_heap
*heap
, duk_uint16_t
*entries16
, duk_uint32_t size
, duk_uint32_t
*p_used
, duk_hstring
*h
) {
493 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
) {
497 #if defined(DUK_USE_HEAPPTR16)
498 duk_uint16_t null16
= heap
->heapptr_null16
;
499 duk_uint16_t deleted16
= heap
->heapptr_deleted16
;
502 DUK_ASSERT(size
> 0);
504 i
= DUK__HASH_INITIAL(DUK_HSTRING_GET_HASH(h
), size
);
505 step
= DUK__HASH_PROBE_STEP(DUK_HSTRING_GET_HASH(h
));
507 #if defined(DUK_USE_HEAPPTR16)
508 duk_uint16_t e16
= entries16
[i
];
510 duk_hstring
*e
= entries
[i
];
513 #if defined(DUK_USE_HEAPPTR16)
514 /* XXX: could check for e16 == 0 because NULL is guaranteed to
521 DUK_DDD(DUK_DDDPRINT("insert hit (null): %ld", (long) i
));
522 #if defined(DUK_USE_HEAPPTR16)
523 entries16
[i
] = DUK_USE_HEAPPTR_ENC16(heap
->heap_udata
, (void *) h
);
529 #if defined(DUK_USE_HEAPPTR16)
530 } else if (e16
== deleted16
) {
532 } else if (e
== DUK__DELETED_MARKER(heap
)) {
534 /* st_used remains the same, DELETED is counted as used */
535 DUK_DDD(DUK_DDDPRINT("insert hit (deleted): %ld", (long) i
));
536 #if defined(DUK_USE_HEAPPTR16)
537 entries16
[i
] = DUK_USE_HEAPPTR_ENC16(heap
->heap_udata
, (void *) h
);
543 DUK_DDD(DUK_DDDPRINT("insert miss: %ld", (long) i
));
544 i
= (i
+ step
) % size
;
546 /* looping should never happen */
547 DUK_ASSERT(i
!= DUK__HASH_INITIAL(DUK_HSTRING_GET_HASH(h
), size
));
551 #if defined(DUK_USE_HEAPPTR16)
552 DUK_LOCAL duk_hstring
*duk__find_matching_string_probe(duk_heap
*heap
, duk_uint16_t
*entries16
, duk_uint32_t size
, const duk_uint8_t
*str
, duk_uint32_t blen
, duk_uint32_t strhash
) {
554 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
) {
559 DUK_ASSERT(size
> 0);
561 i
= DUK__HASH_INITIAL(strhash
, size
);
562 step
= DUK__HASH_PROBE_STEP(strhash
);
565 #if defined(DUK_USE_HEAPPTR16)
566 e
= (duk_hstring
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, entries16
[i
]);
574 if (e
!= DUK__DELETED_MARKER(heap
) && DUK_HSTRING_GET_BYTELEN(e
) == blen
) {
575 if (DUK_MEMCMP((const void *) str
, (const void *) DUK_HSTRING_GET_DATA(e
), (size_t) blen
) == 0) {
576 DUK_DDD(DUK_DDDPRINT("find matching hit: %ld (step %ld, size %ld)",
577 (long) i
, (long) step
, (long) size
));
581 DUK_DDD(DUK_DDDPRINT("find matching miss: %ld (step %ld, size %ld)",
582 (long) i
, (long) step
, (long) size
));
583 i
= (i
+ step
) % size
;
585 /* looping should never happen */
586 DUK_ASSERT(i
!= DUK__HASH_INITIAL(strhash
, size
));
591 #if defined(DUK_USE_HEAPPTR16)
592 DUK_LOCAL
void duk__remove_matching_hstring_probe(duk_heap
*heap
, duk_uint16_t
*entries16
, duk_uint32_t size
, duk_hstring
*h
) {
594 DUK_LOCAL
void duk__remove_matching_hstring_probe(duk_heap
*heap
, duk_hstring
**entries
, duk_uint32_t size
, duk_hstring
*h
) {
599 #if defined(DUK_USE_HEAPPTR16)
600 duk_uint16_t null16
= heap
->heapptr_null16
;
601 duk_uint16_t h16
= DUK_USE_HEAPPTR_ENC16(heap
->heap_udata
, (void *) h
);
604 DUK_ASSERT(size
> 0);
606 hash
= DUK_HSTRING_GET_HASH(h
);
607 i
= DUK__HASH_INITIAL(hash
, size
);
608 step
= DUK__HASH_PROBE_STEP(hash
);
610 #if defined(DUK_USE_HEAPPTR16)
611 duk_uint16_t e16
= entries16
[i
];
613 duk_hstring
*e
= entries
[i
];
616 #if defined(DUK_USE_HEAPPTR16)
624 #if defined(DUK_USE_HEAPPTR16)
629 /* st_used remains the same, DELETED is counted as used */
630 DUK_DDD(DUK_DDDPRINT("free matching hit: %ld", (long) i
));
631 #if defined(DUK_USE_HEAPPTR16)
632 entries16
[i
] = heap
->heapptr_deleted16
;
634 entries
[i
] = DUK__DELETED_MARKER(heap
);
639 DUK_DDD(DUK_DDDPRINT("free matching miss: %ld", (long) i
));
640 i
= (i
+ step
) % size
;
642 /* looping should never happen */
643 DUK_ASSERT(i
!= DUK__HASH_INITIAL(hash
, size
));
647 DUK_LOCAL duk_bool_t
duk__resize_strtab_raw_probe(duk_heap
*heap
, duk_uint32_t new_size
) {
648 #if defined(DUK_USE_DEBUG)
649 duk_uint32_t old_used
= heap
->st_used
;
651 duk_uint32_t old_size
= heap
->st_size
;
652 #if defined(DUK_USE_HEAPPTR16)
653 duk_uint16_t
*old_entries
= heap
->strtable16
;
654 duk_uint16_t
*new_entries
= NULL
;
656 duk_hstring
**old_entries
= heap
->strtable
;
657 duk_hstring
**new_entries
= NULL
;
659 duk_uint32_t new_used
= 0;
662 #if defined(DUK_USE_DEBUG)
663 DUK_UNREF(old_used
); /* unused with some debug level combinations */
666 #ifdef DUK_USE_DDDPRINT
667 DUK_DDD(DUK_DDDPRINT("attempt to resize stringtable: %ld entries, %ld bytes, %ld used, %ld%% load -> %ld entries, %ld bytes, %ld used, %ld%% load",
668 (long) old_size
, (long) (sizeof(duk_hstring
*) * old_size
), (long) old_used
,
669 (long) (((double) old_used
) / ((double) old_size
) * 100.0),
670 (long) new_size
, (long) (sizeof(duk_hstring
*) * new_size
), (long) duk__count_used_probe(heap
),
671 (long) (((double) duk__count_used_probe(heap
)) / ((double) new_size
) * 100.0)));
674 DUK_ASSERT(new_size
> (duk_uint32_t
) duk__count_used_probe(heap
)); /* required for rehash to succeed, equality not that useful */
675 DUK_ASSERT(old_entries
);
678 * The attempt to allocate may cause a GC. Such a GC must not attempt to resize
679 * the stringtable (though it can be swept); finalizer execution and object
680 * compaction must also be postponed to avoid the pressure to add strings to the
681 * string table. Call site must prevent these.
684 #if defined(DUK_USE_MARK_AND_SWEEP)
685 DUK_ASSERT(heap
->mark_and_sweep_base_flags
& DUK_MS_FLAG_NO_STRINGTABLE_RESIZE
);
686 DUK_ASSERT(heap
->mark_and_sweep_base_flags
& DUK_MS_FLAG_NO_FINALIZERS
);
687 DUK_ASSERT(heap
->mark_and_sweep_base_flags
& DUK_MS_FLAG_NO_OBJECT_COMPACTION
);
690 #if defined(DUK_USE_HEAPPTR16)
691 new_entries
= (duk_uint16_t
*) DUK_ALLOC(heap
, sizeof(duk_uint16_t
) * new_size
);
693 new_entries
= (duk_hstring
**) DUK_ALLOC(heap
, sizeof(duk_hstring
*) * new_size
);
700 #if defined(DUK_USE_EXPLICIT_NULL_INIT)
701 for (i
= 0; i
< new_size
; i
++) {
702 #if defined(DUK_USE_HEAPPTR16)
703 new_entries
[i
] = heap
->heapptr_null16
;
705 new_entries
[i
] = NULL
;
709 #if defined(DUK_USE_HEAPPTR16)
710 /* Relies on NULL encoding to zero. */
711 DUK_MEMZERO(new_entries
, sizeof(duk_uint16_t
) * new_size
);
713 DUK_MEMZERO(new_entries
, sizeof(duk_hstring
*) * new_size
);
717 /* Because new_size > duk__count_used_probe(heap), guaranteed to work */
718 for (i
= 0; i
< old_size
; i
++) {
721 #if defined(DUK_USE_HEAPPTR16)
722 e
= (duk_hstring
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, old_entries
[i
]);
726 if (e
== NULL
|| e
== DUK__DELETED_MARKER(heap
)) {
729 /* checking for DUK__DELETED_MARKER is not necessary here, but helper does it now */
730 duk__insert_hstring_probe(heap
, new_entries
, new_size
, &new_used
, e
);
733 #ifdef DUK_USE_DDPRINT
734 DUK_DD(DUK_DDPRINT("resized stringtable: %ld entries, %ld bytes, %ld used, %ld%% load -> %ld entries, %ld bytes, %ld used, %ld%% load",
735 (long) old_size
, (long) (sizeof(duk_hstring
*) * old_size
), (long) old_used
,
736 (long) (((double) old_used
) / ((double) old_size
) * 100.0),
737 (long) new_size
, (long) (sizeof(duk_hstring
*) * new_size
), (long) new_used
,
738 (long) (((double) new_used
) / ((double) new_size
) * 100.0)));
741 #if defined(DUK_USE_HEAPPTR16)
742 DUK_FREE(heap
, heap
->strtable16
);
743 heap
->strtable16
= new_entries
;
745 DUK_FREE(heap
, heap
->strtable
);
746 heap
->strtable
= new_entries
;
748 heap
->st_size
= new_size
;
749 heap
->st_used
= new_used
; /* may be less, since DELETED entries are NULLed by rehash */
754 DUK_FREE(heap
, new_entries
);
758 DUK_LOCAL duk_bool_t
duk__resize_strtab_probe(duk_heap
*heap
) {
759 duk_uint32_t new_size
;
762 new_size
= (duk_uint32_t
) duk__count_used_probe(heap
);
763 if (new_size
>= 0x80000000UL
) {
764 new_size
= DUK_STRTAB_HIGHEST_32BIT_PRIME
;
766 new_size
= duk_util_get_hash_prime(DUK_STRTAB_GROW_ST_SIZE(new_size
));
767 new_size
= duk_util_get_hash_prime(new_size
);
769 DUK_ASSERT(new_size
> 0);
771 /* rehash even if old and new sizes are the same to get rid of
775 ret
= duk__resize_strtab_raw_probe(heap
, new_size
);
780 DUK_LOCAL duk_bool_t
duk__recheck_strtab_size_probe(duk_heap
*heap
, duk_uint32_t new_used
) {
781 duk_uint32_t new_free
;
785 DUK_ASSERT(new_used
<= heap
->st_size
); /* grow by at most one */
786 new_free
= heap
->st_size
- new_used
; /* unsigned intentionally */
788 /* new_free / size <= 1 / DIV <=> new_free <= size / DIV */
789 /* new_used / size <= 1 / DIV <=> new_used <= size / DIV */
791 tmp1
= heap
->st_size
/ DUK_STRTAB_MIN_FREE_DIVISOR
;
792 tmp2
= heap
->st_size
/ DUK_STRTAB_MIN_USED_DIVISOR
;
794 if (new_free
<= tmp1
|| new_used
<= tmp2
) {
795 /* load factor too low or high, count actually used entries and resize */
796 return duk__resize_strtab_probe(heap
);
802 #if defined(DUK_USE_DEBUG)
803 DUK_INTERNAL
void duk_heap_dump_strtab(duk_heap
*heap
) {
807 DUK_ASSERT(heap
!= NULL
);
808 #if defined(DUK_USE_HEAPPTR16)
809 DUK_ASSERT(heap
->strtable16
!= NULL
);
811 DUK_ASSERT(heap
->strtable
!= NULL
);
815 for (i
= 0; i
< heap
->st_size
; i
++) {
816 #if defined(DUK_USE_HEAPPTR16)
817 h
= (duk_hstring
*) DUK_USE_HEAPPTR_DEC16(heap
->strtable16
[i
]);
819 h
= heap
->strtable
[i
];
822 DUK_DD(DUK_DDPRINT("[%03d] -> %p", (int) i
, (void *) h
));
825 #endif /* DUK_USE_DEBUG */
827 #endif /* DUK_USE_STRTAB_PROBE */
830 * Raw intern and lookup
833 DUK_LOCAL duk_hstring
*duk__do_intern(duk_heap
*heap
, const duk_uint8_t
*str
, duk_uint32_t blen
, duk_uint32_t strhash
) {
835 const duk_uint8_t
*extdata
;
836 #if defined(DUK_USE_MARK_AND_SWEEP)
837 duk_small_uint_t prev_mark_and_sweep_base_flags
;
840 /* Prevent any side effects on the string table and the caller provided
841 * str/blen arguments while interning is in progress. For example, if
842 * the caller provided str/blen from a dynamic buffer, a finalizer might
843 * resize that dynamic buffer, invalidating the call arguments.
845 #if defined(DUK_USE_MARK_AND_SWEEP)
846 DUK_ASSERT((heap
->mark_and_sweep_base_flags
& DUK_MS_FLAG_NO_STRINGTABLE_RESIZE
) == 0);
847 prev_mark_and_sweep_base_flags
= heap
->mark_and_sweep_base_flags
;
848 DUK__PREVENT_MS_SIDE_EFFECTS(heap
);
851 #if defined(DUK_USE_STRTAB_PROBE)
852 if (duk__recheck_strtab_size_probe(heap
, heap
->st_used
+ 1)) {
857 /* For manual testing only. */
861 DUK_PRINTF("INTERN: \"");
862 for (i
= 0; i
< blen
; i
++) {
863 duk_uint8_t x
= str
[i
];
864 if (x
>= 0x20 && x
<= 0x7e && x
!= '"' && x
!= '\\') {
865 DUK_PRINTF("%c", (int) x
); /* char: use int cast */
867 DUK_PRINTF("\\x%02lx", (long) x
);
874 #if defined(DUK_USE_HSTRING_EXTDATA) && defined(DUK_USE_EXTSTR_INTERN_CHECK)
875 extdata
= (const duk_uint8_t
*) DUK_USE_EXTSTR_INTERN_CHECK(heap
->heap_udata
, (void *) DUK_LOSE_CONST(str
), (duk_size_t
) blen
);
877 extdata
= (const duk_uint8_t
*) NULL
;
879 res
= duk__alloc_init_hstring(heap
, str
, blen
, strhash
, extdata
);
884 #if defined(DUK_USE_STRTAB_CHAIN)
885 if (duk__insert_hstring_chain(heap
, res
)) {
890 #elif defined(DUK_USE_STRTAB_PROBE)
891 /* guaranteed to succeed */
892 duk__insert_hstring_probe(heap
,
893 #if defined(DUK_USE_HEAPPTR16)
902 #error internal error, invalid strtab options
905 /* Note: hstring is in heap but has refcount zero and is not strongly reachable.
906 * Caller should increase refcount and make the hstring reachable before any
907 * operations which require allocation (and possible gc).
911 #if defined(DUK_USE_MARK_AND_SWEEP)
912 heap
->mark_and_sweep_base_flags
= prev_mark_and_sweep_base_flags
;
921 DUK_LOCAL duk_hstring
*duk__do_lookup(duk_heap
*heap
, const duk_uint8_t
*str
, duk_uint32_t blen
, duk_uint32_t
*out_strhash
) {
924 DUK_ASSERT(out_strhash
);
926 *out_strhash
= duk_heap_hashstring(heap
, str
, (duk_size_t
) blen
);
928 #if defined(DUK_USE_ROM_STRINGS)
931 /* XXX: This is VERY inefficient now, and should be e.g. a
932 * binary search or perfect hash, to be fixed.
934 for (i
= 0; i
< (duk_small_uint_t
) (sizeof(duk_rom_strings
) / sizeof(duk_hstring
*)); i
++) {
936 romstr
= (duk_hstring
*) DUK_LOSE_CONST(duk_rom_strings
[i
]);
937 if (blen
== DUK_HSTRING_GET_BYTELEN(romstr
) &&
938 DUK_MEMCMP((const void *) str
, (const void *) DUK_HSTRING_GET_DATA(romstr
), blen
) == 0) {
939 DUK_DD(DUK_DDPRINT("intern check: rom string: %!O, computed hash 0x%08lx, rom hash 0x%08lx",
940 romstr
, (unsigned long) *out_strhash
, (unsigned long) DUK_HSTRING_GET_HASH(romstr
)));
941 DUK_ASSERT(*out_strhash
== DUK_HSTRING_GET_HASH(romstr
));
942 *out_strhash
= DUK_HSTRING_GET_HASH(romstr
);
947 #endif /* DUK_USE_ROM_STRINGS */
949 #if defined(DUK_USE_STRTAB_CHAIN)
950 res
= duk__find_matching_string_chain(heap
, str
, blen
, *out_strhash
);
951 #elif defined(DUK_USE_STRTAB_PROBE)
952 res
= duk__find_matching_string_probe(heap
,
953 #if defined(DUK_USE_HEAPPTR16)
963 #error internal error, invalid strtab options
974 DUK_INTERNAL duk_hstring
*duk_heap_string_lookup(duk_heap
*heap
, const duk_uint8_t
*str
, duk_uint32_t blen
) {
975 duk_uint32_t strhash
; /* dummy */
976 return duk__do_lookup(heap
, str
, blen
, &strhash
);
980 DUK_INTERNAL duk_hstring
*duk_heap_string_intern(duk_heap
*heap
, const duk_uint8_t
*str
, duk_uint32_t blen
) {
982 duk_uint32_t strhash
;
984 /* caller is responsible for ensuring this */
985 DUK_ASSERT(blen
<= DUK_HSTRING_MAX_BYTELEN
);
987 res
= duk__do_lookup(heap
, str
, blen
, &strhash
);
992 res
= duk__do_intern(heap
, str
, blen
, strhash
);
993 return res
; /* may be NULL */
996 DUK_INTERNAL duk_hstring
*duk_heap_string_intern_checked(duk_hthread
*thr
, const duk_uint8_t
*str
, duk_uint32_t blen
) {
997 duk_hstring
*res
= duk_heap_string_intern(thr
->heap
, str
, blen
);
999 DUK_ERROR_ALLOC_DEFMSG(thr
);
1005 DUK_INTERNAL duk_hstring
*duk_heap_string_lookup_u32(duk_heap
*heap
, duk_uint32_t val
) {
1006 char buf
[DUK_STRTAB_U32_MAX_STRLEN
+1];
1007 DUK_SNPRINTF(buf
, sizeof(buf
), "%lu", (unsigned long) val
);
1008 buf
[sizeof(buf
) - 1] = (char) 0;
1009 DUK_ASSERT(DUK_STRLEN(buf
) <= DUK_UINT32_MAX
); /* formatted result limited */
1010 return duk_heap_string_lookup(heap
, (const duk_uint8_t
*) buf
, (duk_uint32_t
) DUK_STRLEN(buf
));
1014 DUK_INTERNAL duk_hstring
*duk_heap_string_intern_u32(duk_heap
*heap
, duk_uint32_t val
) {
1015 char buf
[DUK_STRTAB_U32_MAX_STRLEN
+1];
1016 DUK_SNPRINTF(buf
, sizeof(buf
), "%lu", (unsigned long) val
);
1017 buf
[sizeof(buf
) - 1] = (char) 0;
1018 DUK_ASSERT(DUK_STRLEN(buf
) <= DUK_UINT32_MAX
); /* formatted result limited */
1019 return duk_heap_string_intern(heap
, (const duk_uint8_t
*) buf
, (duk_uint32_t
) DUK_STRLEN(buf
));
1022 DUK_INTERNAL duk_hstring
*duk_heap_string_intern_u32_checked(duk_hthread
*thr
, duk_uint32_t val
) {
1023 duk_hstring
*res
= duk_heap_string_intern_u32(thr
->heap
, val
);
1025 DUK_ERROR_ALLOC_DEFMSG(thr
);
1030 /* find and remove string from stringtable; caller must free the string itself */
1031 #if defined(DUK_USE_REFERENCE_COUNTING)
1032 DUK_INTERNAL
void duk_heap_string_remove(duk_heap
*heap
, duk_hstring
*h
) {
1033 DUK_DDD(DUK_DDDPRINT("remove string from stringtable: %!O", (duk_heaphdr
*) h
));
1035 #if defined(DUK_USE_STRTAB_CHAIN)
1036 duk__remove_matching_hstring_chain(heap
, h
);
1037 #elif defined(DUK_USE_STRTAB_PROBE)
1038 duk__remove_matching_hstring_probe(heap
,
1039 #if defined(DUK_USE_HEAPPTR16)
1047 #error internal error, invalid strtab options
1052 #if defined(DUK_USE_MARK_AND_SWEEP) && defined(DUK_USE_MS_STRINGTABLE_RESIZE)
1053 DUK_INTERNAL
void duk_heap_force_strtab_resize(duk_heap
*heap
) {
1054 duk_small_uint_t prev_mark_and_sweep_base_flags
;
1055 /* Force a resize so that DELETED entries are eliminated.
1056 * Another option would be duk__recheck_strtab_size_probe();
1057 * but since that happens on every intern anyway, this whole
1058 * check can now be disabled.
1061 DUK_ASSERT((heap
->mark_and_sweep_base_flags
& DUK_MS_FLAG_NO_STRINGTABLE_RESIZE
) == 0);
1062 prev_mark_and_sweep_base_flags
= heap
->mark_and_sweep_base_flags
;
1063 DUK__PREVENT_MS_SIDE_EFFECTS(heap
);
1065 #if defined(DUK_USE_STRTAB_CHAIN)
1067 #elif defined(DUK_USE_STRTAB_PROBE)
1068 (void) duk__resize_strtab_probe(heap
);
1071 heap
->mark_and_sweep_base_flags
= prev_mark_and_sweep_base_flags
;
1075 #if defined(DUK_USE_STRTAB_CHAIN)
1076 DUK_INTERNAL
void duk_heap_free_strtab(duk_heap
*heap
) {
1077 /* Free strings in the stringtable and any allocations needed
1078 * by the stringtable itself.
1080 duk_uint_fast32_t i
, j
;
1081 duk_strtab_entry
*e
;
1082 #if defined(DUK_USE_HEAPPTR16)
1084 duk_uint16_t null16
= heap
->heapptr_null16
;
1090 for (i
= 0; i
< DUK_STRTAB_CHAIN_SIZE
; i
++) {
1091 e
= heap
->strtable
+ i
;
1092 if (e
->listlen
> 0) {
1093 #if defined(DUK_USE_HEAPPTR16)
1094 lst
= (duk_uint16_t
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, e
->u
.strlist16
);
1098 DUK_ASSERT(lst
!= NULL
);
1100 for (j
= 0; j
< e
->listlen
; j
++) {
1101 #if defined(DUK_USE_HEAPPTR16)
1102 h
= DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, lst
[j
]);
1108 /* strings may have inner refs (extdata) in some cases */
1110 duk_free_hstring_inner(heap
, h
);
1114 #if defined(DUK_USE_HEAPPTR16)
1115 e
->u
.strlist16
= null16
;
1117 e
->u
.strlist
= NULL
;
1119 DUK_FREE(heap
, lst
);
1121 #if defined(DUK_USE_HEAPPTR16)
1122 h
= DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, e
->u
.str16
);
1123 e
->u
.str16
= null16
;
1129 duk_free_hstring_inner(heap
, h
);
1136 #endif /* DUK_USE_STRTAB_CHAIN */
1138 #if defined(DUK_USE_STRTAB_PROBE)
1139 DUK_INTERNAL
void duk_heap_free_strtab(duk_heap
*heap
) {
1140 duk_uint_fast32_t i
;
1143 #if defined(DUK_USE_HEAPPTR16)
1144 if (heap
->strtable16
) {
1146 if (heap
->strtable
) {
1148 for (i
= 0; i
< (duk_uint_fast32_t
) heap
->st_size
; i
++) {
1149 #if defined(DUK_USE_HEAPPTR16)
1150 h
= (duk_hstring
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, heap
->strtable16
[i
]);
1152 h
= heap
->strtable
[i
];
1154 if (h
== NULL
|| h
== DUK_STRTAB_DELETED_MARKER(heap
)) {
1157 DUK_ASSERT(h
!= NULL
);
1159 /* strings may have inner refs (extdata) in some cases */
1160 duk_free_hstring_inner(heap
, h
);
1162 #if 0 /* not strictly necessary */
1163 heap
->strtable
[i
] = NULL
;
1166 #if defined(DUK_USE_HEAPPTR16)
1167 DUK_FREE(heap
, heap
->strtable16
);
1169 DUK_FREE(heap
, heap
->strtable
);
1171 #if 0 /* not strictly necessary */
1172 heap
->strtable
= NULL
;
1176 #endif /* DUK_USE_STRTAB_PROBE */
1178 /* Undefine local defines */
1179 #undef DUK__HASH_INITIAL
1180 #undef DUK__HASH_PROBE_STEP
1181 #undef DUK__DELETED_MARKER