1 /*
2 * Heap stringtable handling, string interning.
3 */
4
5 #include "duk_internal.h"
6
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))
11 #endif
12
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 */ \
19 } while (0)
20 #endif
21
22 /*
23 * Create a hstring and insert into the heap. The created object
24 * is directly garbage collectable with reference count zero.
25 *
26 * The caller must place the interned string into the stringtable
27 * immediately (without chance of a longjmp); otherwise the string
28 * is lost.
29 */
30
31 DUK_LOCAL
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)32 duk_hstring *duk__alloc_init_hstring(duk_heap *heap,
33 const duk_uint8_t *str,
34 duk_uint32_t blen,
35 duk_uint32_t strhash,
36 const duk_uint8_t *extdata) {
37 duk_hstring *res = NULL;
38 duk_uint8_t *data;
39 duk_size_t alloc_size;
40 duk_uarridx_t dummy;
41 duk_uint32_t clen;
42
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"));
47 return NULL;
48 }
49 #endif
50
51 if (extdata) {
52 alloc_size = (duk_size_t) sizeof(duk_hstring_external);
53 res = (duk_hstring *) DUK_ALLOC(heap, alloc_size);
54 if (!res) {
55 goto alloc_error;
56 }
57 DUK_MEMZERO(res, sizeof(duk_hstring_external));
58 #if defined(DUK_USE_EXPLICIT_NULL_INIT)
59 DUK_HEAPHDR_STRING_INIT_NULLS(&res->hdr);
60 #endif
61 DUK_HEAPHDR_SET_TYPE_AND_FLAGS(&res->hdr, DUK_HTYPE_STRING, DUK_HSTRING_FLAG_EXTDATA);
62
63 ((duk_hstring_external *) res)->extdata = extdata;
64 } else {
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);
68 if (!res) {
69 goto alloc_error;
70 }
71 DUK_MEMZERO(res, sizeof(duk_hstring));
72 #if defined(DUK_USE_EXPLICIT_NULL_INIT)
73 DUK_HEAPHDR_STRING_INIT_NULLS(&res->hdr);
74 #endif
75 DUK_HEAPHDR_SET_TYPE_AND_FLAGS(&res->hdr, DUK_HTYPE_STRING, 0);
76
77 data = (duk_uint8_t *) (res + 1);
78 DUK_MEMCPY(data, str, blen);
79 data[blen] = (duk_uint8_t) 0;
80 }
81
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);
85 }
86
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'
92 * flag set).
93 */
94 DUK_ASSERT(!DUK_HSTRING_HAS_INTERNAL(res));
95 if (blen > 0 && str[0] == (duk_uint8_t) 0xff) {
96 DUK_HSTRING_SET_INTERNAL(res);
97 }
98
99 DUK_HSTRING_SET_HASH(res, strhash);
100 DUK_HSTRING_SET_BYTELEN(res, blen);
101
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);
106 #endif
107
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.
111 */
112 DUK_ASSERT(!DUK_HSTRING_HAS_ASCII(res));
113 if (clen == blen) {
114 DUK_HSTRING_SET_ASCII(res);
115 }
116
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)));
123
124 return res;
125
126 alloc_error:
127 DUK_FREE(heap, res);
128 return NULL;
129 }
130
131 /*
132 * String table algorithm: fixed size string table with array chaining
133 *
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.
137 *
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.
142 */
143
144 #if defined(DUK_USE_STRTAB_CHAIN)
145
146 #if defined(DUK_USE_HEAPPTR16)
duk__insert_hstring_chain(duk_heap * heap,duk_hstring * h)147 DUK_LOCAL duk_bool_t duk__insert_hstring_chain(duk_heap *heap, duk_hstring *h) {
148 duk_small_uint_t slotidx;
149 duk_strtab_entry *e;
150 duk_uint16_t *lst;
151 duk_uint16_t *new_lst;
152 duk_size_t i, n;
153 duk_uint16_t null16 = heap->heapptr_null16;
154 duk_uint16_t h16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
155
156 DUK_ASSERT(heap != NULL);
157 DUK_ASSERT(h != NULL);
158
159 slotidx = DUK_HSTRING_GET_HASH(h) % DUK_STRTAB_CHAIN_SIZE;
160 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
161
162 e = heap->strtable + slotidx;
163 if (e->listlen == 0) {
164 if (e->u.str16 == null16) {
165 e->u.str16 = h16;
166 } else {
167 /* Now two entries in the same slot, alloc list */
168 lst = (duk_uint16_t *) DUK_ALLOC(heap, sizeof(duk_uint16_t) * 2);
169 if (lst == NULL) {
170 return 1; /* fail */
171 }
172 lst[0] = e->u.str16;
173 lst[1] = h16;
174 e->u.strlist16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) lst);
175 e->listlen = 2;
176 }
177 } else {
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) {
183 lst[i] = h16;
184 return 0;
185 }
186 }
187
188 if (e->listlen + 1 == 0) {
189 /* Overflow, relevant mainly when listlen is 16 bits. */
190 return 1; /* fail */
191 }
192
193 new_lst = (duk_uint16_t *) DUK_REALLOC(heap, lst, sizeof(duk_uint16_t) * (e->listlen + 1));
194 if (new_lst == NULL) {
195 return 1; /* fail */
196 }
197 new_lst[e->listlen++] = h16;
198 e->u.strlist16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) new_lst);
199 }
200 return 0;
201 }
202 #else /* DUK_USE_HEAPPTR16 */
duk__insert_hstring_chain(duk_heap * heap,duk_hstring * h)203 DUK_LOCAL duk_bool_t duk__insert_hstring_chain(duk_heap *heap, duk_hstring *h) {
204 duk_small_uint_t slotidx;
205 duk_strtab_entry *e;
206 duk_hstring **lst;
207 duk_hstring **new_lst;
208 duk_size_t i, n;
209
210 DUK_ASSERT(heap != NULL);
211 DUK_ASSERT(h != NULL);
212
213 slotidx = DUK_HSTRING_GET_HASH(h) % DUK_STRTAB_CHAIN_SIZE;
214 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
215
216 e = heap->strtable + slotidx;
217 if (e->listlen == 0) {
218 if (e->u.str == NULL) {
219 e->u.str = h;
220 } else {
221 /* Now two entries in the same slot, alloc list */
222 lst = (duk_hstring **) DUK_ALLOC(heap, sizeof(duk_hstring *) * 2);
223 if (lst == NULL) {
224 return 1; /* fail */
225 }
226 lst[0] = e->u.str;
227 lst[1] = h;
228 e->u.strlist = lst;
229 e->listlen = 2;
230 }
231 } else {
232 DUK_ASSERT(e->u.strlist != NULL);
233 lst = e->u.strlist;
234 for (i = 0, n = e->listlen; i < n; i++) {
235 if (lst[i] == NULL) {
236 lst[i] = h;
237 return 0;
238 }
239 }
240
241 if (e->listlen + 1 == 0) {
242 /* Overflow, relevant mainly when listlen is 16 bits. */
243 return 1; /* fail */
244 }
245
246 new_lst = (duk_hstring **) DUK_REALLOC(heap, e->u.strlist, sizeof(duk_hstring *) * (e->listlen + 1));
247 if (new_lst == NULL) {
248 return 1; /* fail */
249 }
250 new_lst[e->listlen++] = h;
251 e->u.strlist = new_lst;
252 }
253 return 0;
254 }
255 #endif /* DUK_USE_HEAPPTR16 */
256
257 #if defined(DUK_USE_HEAPPTR16)
duk__find_matching_string_chain(duk_heap * heap,const duk_uint8_t * str,duk_uint32_t blen,duk_uint32_t strhash)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;
260 duk_strtab_entry *e;
261 duk_uint16_t *lst;
262 duk_size_t i, n;
263 duk_uint16_t null16 = heap->heapptr_null16;
264
265 DUK_ASSERT(heap != NULL);
266
267 slotidx = strhash % DUK_STRTAB_CHAIN_SIZE;
268 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
269
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) {
277 return h;
278 }
279 }
280 } else {
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) {
290 return h;
291 }
292 }
293 }
294 }
295
296 return NULL;
297 }
298 #else /* DUK_USE_HEAPPTR16 */
duk__find_matching_string_chain(duk_heap * heap,const duk_uint8_t * str,duk_uint32_t blen,duk_uint32_t strhash)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;
301 duk_strtab_entry *e;
302 duk_hstring **lst;
303 duk_size_t i, n;
304
305 DUK_ASSERT(heap != NULL);
306
307 slotidx = strhash % DUK_STRTAB_CHAIN_SIZE;
308 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
309
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) {
315 return e->u.str;
316 }
317 } else {
318 DUK_ASSERT(e->u.strlist != NULL);
319 lst = e->u.strlist;
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) {
324 return lst[i];
325 }
326 }
327 }
328
329 return NULL;
330 }
331 #endif /* DUK_USE_HEAPPTR16 */
332
333 #if defined(DUK_USE_HEAPPTR16)
duk__remove_matching_hstring_chain(duk_heap * heap,duk_hstring * h)334 DUK_LOCAL void duk__remove_matching_hstring_chain(duk_heap *heap, duk_hstring *h) {
335 duk_small_uint_t slotidx;
336 duk_strtab_entry *e;
337 duk_uint16_t *lst;
338 duk_size_t i, n;
339 duk_uint16_t h16;
340 duk_uint16_t null16 = heap->heapptr_null16;
341
342 DUK_ASSERT(heap != NULL);
343 DUK_ASSERT(h != NULL);
344
345 slotidx = DUK_HSTRING_GET_HASH(h) % DUK_STRTAB_CHAIN_SIZE;
346 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
347
348 DUK_ASSERT(h != NULL);
349 h16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
350
351 e = heap->strtable + slotidx;
352 if (e->listlen == 0) {
353 if (e->u.str16 == h16) {
354 e->u.str16 = null16;
355 return;
356 }
357 } else {
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++) {
362 if (lst[i] == h16) {
363 lst[i] = null16;
364 return;
365 }
366 }
367 }
368
369 DUK_D(DUK_DPRINT("failed to find string that should be in stringtable"));
370 DUK_UNREACHABLE();
371 return;
372 }
373 #else /* DUK_USE_HEAPPTR16 */
duk__remove_matching_hstring_chain(duk_heap * heap,duk_hstring * h)374 DUK_LOCAL void duk__remove_matching_hstring_chain(duk_heap *heap, duk_hstring *h) {
375 duk_small_uint_t slotidx;
376 duk_strtab_entry *e;
377 duk_hstring **lst;
378 duk_size_t i, n;
379
380 DUK_ASSERT(heap != NULL);
381 DUK_ASSERT(h != NULL);
382
383 slotidx = DUK_HSTRING_GET_HASH(h) % DUK_STRTAB_CHAIN_SIZE;
384 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
385
386 e = heap->strtable + slotidx;
387 if (e->listlen == 0) {
388 DUK_ASSERT(h != NULL);
389 if (e->u.str == h) {
390 e->u.str = NULL;
391 return;
392 }
393 } else {
394 DUK_ASSERT(e->u.strlist != NULL);
395 lst = e->u.strlist;
396 for (i = 0, n = e->listlen; i < n; i++) {
397 DUK_ASSERT(h != NULL);
398 if (lst[i] == h) {
399 lst[i] = NULL;
400 return;
401 }
402 }
403 }
404
405 DUK_D(DUK_DPRINT("failed to find string that should be in stringtable"));
406 DUK_UNREACHABLE();
407 return;
408 }
409 #endif /* DUK_USE_HEAPPTR16 */
410
411 #if defined(DUK_USE_DEBUG)
duk_heap_dump_strtab(duk_heap * heap)412 DUK_INTERNAL void duk_heap_dump_strtab(duk_heap *heap) {
413 duk_strtab_entry *e;
414 duk_small_uint_t i;
415 duk_size_t j, n, used;
416 #if defined(DUK_USE_HEAPPTR16)
417 duk_uint16_t *lst;
418 duk_uint16_t null16 = heap->heapptr_null16;
419 #else
420 duk_hstring **lst;
421 #endif
422
423 DUK_ASSERT(heap != NULL);
424
425 for (i = 0; i < DUK_STRTAB_CHAIN_SIZE; i++) {
426 e = heap->strtable + i;
427
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)));
431 #else
432 DUK_DD(DUK_DDPRINT("[%03d] -> plain %d", (int) i, (int) (e->u.str ? 1 : 0)));
433 #endif
434 } else {
435 used = 0;
436 #if defined(DUK_USE_HEAPPTR16)
437 lst = (duk_uint16_t *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.strlist16);
438 #else
439 lst = e->u.strlist;
440 #endif
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) {
445 #else
446 if (lst[j] != NULL) {
447 #endif
448 used++;
449 }
450 }
451 DUK_DD(DUK_DDPRINT("[%03d] -> array %d/%d", (int) i, (int) used, (int) e->listlen));
452 }
453 }
454 }
455 #endif /* DUK_USE_DEBUG */
456
457 #endif /* DUK_USE_STRTAB_CHAIN */
458
459 /*
460 * String table algorithm: closed hashing with a probe sequence
461 *
462 * This is the default algorithm and works fine for environments with
463 * minimal memory constraints.
464 */
465
466 #if defined(DUK_USE_STRTAB_PROBE)
467
468 /* Count actually used (non-NULL, non-DELETED) entries. */
469 DUK_LOCAL duk_int_t duk__count_used_probe(duk_heap *heap) {
470 duk_int_t res = 0;
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;
475 #endif
476
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) {
481 #else
482 if (heap->strtable[i] != NULL && heap->strtable[i] != DUK__DELETED_MARKER(heap)) {
483 #endif
484 res++;
485 }
486 }
487 return res;
488 }
489
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) {
492 #else
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) {
494 #endif
495 duk_uint32_t i;
496 duk_uint32_t step;
497 #if defined(DUK_USE_HEAPPTR16)
498 duk_uint16_t null16 = heap->heapptr_null16;
499 duk_uint16_t deleted16 = heap->heapptr_deleted16;
500 #endif
501
502 DUK_ASSERT(size > 0);
503
504 i = DUK__HASH_INITIAL(DUK_HSTRING_GET_HASH(h), size);
505 step = DUK__HASH_PROBE_STEP(DUK_HSTRING_GET_HASH(h));
506 for (;;) {
507 #if defined(DUK_USE_HEAPPTR16)
508 duk_uint16_t e16 = entries16[i];
509 #else
510 duk_hstring *e = entries[i];
511 #endif
512
513 #if defined(DUK_USE_HEAPPTR16)
514 /* XXX: could check for e16 == 0 because NULL is guaranteed to
515 * encode to zero.
516 */
517 if (e16 == null16) {
518 #else
519 if (e == NULL) {
520 #endif
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);
524 #else
525 entries[i] = h;
526 #endif
527 (*p_used)++;
528 break;
529 #if defined(DUK_USE_HEAPPTR16)
530 } else if (e16 == deleted16) {
531 #else
532 } else if (e == DUK__DELETED_MARKER(heap)) {
533 #endif
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);
538 #else
539 entries[i] = h;
540 #endif
541 break;
542 }
543 DUK_DDD(DUK_DDDPRINT("insert miss: %ld", (long) i));
544 i = (i + step) % size;
545
546 /* looping should never happen */
547 DUK_ASSERT(i != DUK__HASH_INITIAL(DUK_HSTRING_GET_HASH(h), size));
548 }
549 }
550
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) {
553 #else
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) {
555 #endif
556 duk_uint32_t i;
557 duk_uint32_t step;
558
559 DUK_ASSERT(size > 0);
560
561 i = DUK__HASH_INITIAL(strhash, size);
562 step = DUK__HASH_PROBE_STEP(strhash);
563 for (;;) {
564 duk_hstring *e;
565 #if defined(DUK_USE_HEAPPTR16)
566 e = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, entries16[i]);
567 #else
568 e = entries[i];
569 #endif
570
571 if (!e) {
572 return NULL;
573 }
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));
578 return e;
579 }
580 }
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;
584
585 /* looping should never happen */
586 DUK_ASSERT(i != DUK__HASH_INITIAL(strhash, size));
587 }
588 DUK_UNREACHABLE();
589 }
590
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) {
593 #else
594 DUK_LOCAL void duk__remove_matching_hstring_probe(duk_heap *heap, duk_hstring **entries, duk_uint32_t size, duk_hstring *h) {
595 #endif
596 duk_uint32_t i;
597 duk_uint32_t step;
598 duk_uint32_t hash;
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);
602 #endif
603
604 DUK_ASSERT(size > 0);
605
606 hash = DUK_HSTRING_GET_HASH(h);
607 i = DUK__HASH_INITIAL(hash, size);
608 step = DUK__HASH_PROBE_STEP(hash);
609 for (;;) {
610 #if defined(DUK_USE_HEAPPTR16)
611 duk_uint16_t e16 = entries16[i];
612 #else
613 duk_hstring *e = entries[i];
614 #endif
615
616 #if defined(DUK_USE_HEAPPTR16)
617 if (e16 == null16) {
618 #else
619 if (!e) {
620 #endif
621 DUK_UNREACHABLE();
622 break;
623 }
624 #if defined(DUK_USE_HEAPPTR16)
625 if (e16 == h16) {
626 #else
627 if (e == h) {
628 #endif
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;
633 #else
634 entries[i] = DUK__DELETED_MARKER(heap);
635 #endif
636 break;
637 }
638
639 DUK_DDD(DUK_DDDPRINT("free matching miss: %ld", (long) i));
640 i = (i + step) % size;
641
642 /* looping should never happen */
643 DUK_ASSERT(i != DUK__HASH_INITIAL(hash, size));
644 }
645 }
646
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;
650 #endif
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;
655 #else
656 duk_hstring **old_entries = heap->strtable;
657 duk_hstring **new_entries = NULL;
658 #endif
659 duk_uint32_t new_used = 0;
660 duk_uint32_t i;
661
662 #if defined(DUK_USE_DEBUG)
663 DUK_UNREF(old_used); /* unused with some debug level combinations */
664 #endif
665
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)));
672 #endif
673
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);
676
677 /*
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.
682 */
683
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);
688 #endif
689
690 #if defined(DUK_USE_HEAPPTR16)
691 new_entries = (duk_uint16_t *) DUK_ALLOC(heap, sizeof(duk_uint16_t) * new_size);
692 #else
693 new_entries = (duk_hstring **) DUK_ALLOC(heap, sizeof(duk_hstring *) * new_size);
694 #endif
695
696 if (!new_entries) {
697 goto resize_error;
698 }
699
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;
704 #else
705 new_entries[i] = NULL;
706 #endif
707 }
708 #else
709 #if defined(DUK_USE_HEAPPTR16)
710 /* Relies on NULL encoding to zero. */
711 DUK_MEMZERO(new_entries, sizeof(duk_uint16_t) * new_size);
712 #else
713 DUK_MEMZERO(new_entries, sizeof(duk_hstring *) * new_size);
714 #endif
715 #endif
716
717 /* Because new_size > duk__count_used_probe(heap), guaranteed to work */
718 for (i = 0; i < old_size; i++) {
719 duk_hstring *e;
720
721 #if defined(DUK_USE_HEAPPTR16)
722 e = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, old_entries[i]);
723 #else
724 e = old_entries[i];
725 #endif
726 if (e == NULL || e == DUK__DELETED_MARKER(heap)) {
727 continue;
728 }
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);
731 }
732
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)));
739 #endif
740
741 #if defined(DUK_USE_HEAPPTR16)
742 DUK_FREE(heap, heap->strtable16);
743 heap->strtable16 = new_entries;
744 #else
745 DUK_FREE(heap, heap->strtable);
746 heap->strtable = new_entries;
747 #endif
748 heap->st_size = new_size;
749 heap->st_used = new_used; /* may be less, since DELETED entries are NULLed by rehash */
750
751 return 0; /* OK */
752
753 resize_error:
754 DUK_FREE(heap, new_entries);
755 return 1; /* FAIL */
756 }
757
758 DUK_LOCAL duk_bool_t duk__resize_strtab_probe(duk_heap *heap) {
759 duk_uint32_t new_size;
760 duk_bool_t ret;
761
762 new_size = (duk_uint32_t) duk__count_used_probe(heap);
763 if (new_size >= 0x80000000UL) {
764 new_size = DUK_STRTAB_HIGHEST_32BIT_PRIME;
765 } else {
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);
768 }
769 DUK_ASSERT(new_size > 0);
770
771 /* rehash even if old and new sizes are the same to get rid of
772 * DELETED entries.
773 */
774
775 ret = duk__resize_strtab_raw_probe(heap, new_size);
776
777 return ret;
778 }
779
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;
782 duk_uint32_t tmp1;
783 duk_uint32_t tmp2;
784
785 DUK_ASSERT(new_used <= heap->st_size); /* grow by at most one */
786 new_free = heap->st_size - new_used; /* unsigned intentionally */
787
788 /* new_free / size <= 1 / DIV <=> new_free <= size / DIV */
789 /* new_used / size <= 1 / DIV <=> new_used <= size / DIV */
790
791 tmp1 = heap->st_size / DUK_STRTAB_MIN_FREE_DIVISOR;
792 tmp2 = heap->st_size / DUK_STRTAB_MIN_USED_DIVISOR;
793
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);
797 } else {
798 return 0; /* OK */
799 }
800 }
801
802 #if defined(DUK_USE_DEBUG)
803 DUK_INTERNAL void duk_heap_dump_strtab(duk_heap *heap) {
804 duk_uint32_t i;
805 duk_hstring *h;
806
807 DUK_ASSERT(heap != NULL);
808 #if defined(DUK_USE_HEAPPTR16)
809 DUK_ASSERT(heap->strtable16 != NULL);
810 #else
811 DUK_ASSERT(heap->strtable != NULL);
812 #endif
813 DUK_UNREF(h);
814
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]);
818 #else
819 h = heap->strtable[i];
820 #endif
821
822 DUK_DD(DUK_DDPRINT("[%03d] -> %p", (int) i, (void *) h));
823 }
824 }
825 #endif /* DUK_USE_DEBUG */
826
827 #endif /* DUK_USE_STRTAB_PROBE */
828
829 /*
830 * Raw intern and lookup
831 */
832
833 DUK_LOCAL duk_hstring *duk__do_intern(duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen, duk_uint32_t strhash) {
834 duk_hstring *res;
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;
838 #endif
839
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.
844 */
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);
849 #endif
850
851 #if defined(DUK_USE_STRTAB_PROBE)
852 if (duk__recheck_strtab_size_probe(heap, heap->st_used + 1)) {
853 goto failed;
854 }
855 #endif
856
857 /* For manual testing only. */
858 #if 0
859 {
860 duk_size_t i;
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 */
866 } else {
867 DUK_PRINTF("\\x%02lx", (long) x);
868 }
869 }
870 DUK_PRINTF("\"\n");
871 }
872 #endif
873
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);
876 #else
877 extdata = (const duk_uint8_t *) NULL;
878 #endif
879 res = duk__alloc_init_hstring(heap, str, blen, strhash, extdata);
880 if (!res) {
881 goto failed;
882 }
883
884 #if defined(DUK_USE_STRTAB_CHAIN)
885 if (duk__insert_hstring_chain(heap, res)) {
886 /* failed */
887 DUK_FREE(heap, res);
888 goto failed;
889 }
890 #elif defined(DUK_USE_STRTAB_PROBE)
891 /* guaranteed to succeed */
892 duk__insert_hstring_probe(heap,
893 #if defined(DUK_USE_HEAPPTR16)
894 heap->strtable16,
895 #else
896 heap->strtable,
897 #endif
898 heap->st_size,
899 &heap->st_used,
900 res);
901 #else
902 #error internal error, invalid strtab options
903 #endif
904
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).
908 */
909
910 done:
911 #if defined(DUK_USE_MARK_AND_SWEEP)
912 heap->mark_and_sweep_base_flags = prev_mark_and_sweep_base_flags;
913 #endif
914 return res;
915
916 failed:
917 res = NULL;
918 goto done;
919 }
920
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) {
922 duk_hstring *res;
923
924 DUK_ASSERT(out_strhash);
925
926 *out_strhash = duk_heap_hashstring(heap, str, (duk_size_t) blen);
927
928 #if defined(DUK_USE_ROM_STRINGS)
929 {
930 duk_small_uint_t i;
931 /* XXX: This is VERY inefficient now, and should be e.g. a
932 * binary search or perfect hash, to be fixed.
933 */
934 for (i = 0; i < (duk_small_uint_t) (sizeof(duk_rom_strings) / sizeof(duk_hstring *)); i++) {
935 duk_hstring *romstr;
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);
943 return romstr;
944 }
945 }
946 }
947 #endif /* DUK_USE_ROM_STRINGS */
948
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)
954 heap->strtable16,
955 #else
956 heap->strtable,
957 #endif
958 heap->st_size,
959 str,
960 blen,
961 *out_strhash);
962 #else
963 #error internal error, invalid strtab options
964 #endif
965
966 return res;
967 }
968
969 /*
970 * Exposed calls
971 */
972
973 #if 0 /*unused*/
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);
977 }
978 #endif
979
980 DUK_INTERNAL duk_hstring *duk_heap_string_intern(duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen) {
981 duk_hstring *res;
982 duk_uint32_t strhash;
983
984 /* caller is responsible for ensuring this */
985 DUK_ASSERT(blen <= DUK_HSTRING_MAX_BYTELEN);
986
987 res = duk__do_lookup(heap, str, blen, &strhash);
988 if (res) {
989 return res;
990 }
991
992 res = duk__do_intern(heap, str, blen, strhash);
993 return res; /* may be NULL */
994 }
995
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);
998 if (!res) {
999 DUK_ERROR_ALLOC_DEFMSG(thr);
1000 }
1001 return res;
1002 }
1003
1004 #if 0 /*unused*/
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));
1011 }
1012 #endif
1013
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));
1020 }
1021
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);
1024 if (!res) {
1025 DUK_ERROR_ALLOC_DEFMSG(thr);
1026 }
1027 return res;
1028 }
1029
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));
1034
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)
1040 heap->strtable16,
1041 #else
1042 heap->strtable,
1043 #endif
1044 heap->st_size,
1045 h);
1046 #else
1047 #error internal error, invalid strtab options
1048 #endif
1049 }
1050 #endif
1051
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.
1059 */
1060
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);
1064
1065 #if defined(DUK_USE_STRTAB_CHAIN)
1066 DUK_UNREF(heap);
1067 #elif defined(DUK_USE_STRTAB_PROBE)
1068 (void) duk__resize_strtab_probe(heap);
1069 #endif
1070
1071 heap->mark_and_sweep_base_flags = prev_mark_and_sweep_base_flags;
1072 }
1073 #endif
1074
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.
1079 */
1080 duk_uint_fast32_t i, j;
1081 duk_strtab_entry *e;
1082 #if defined(DUK_USE_HEAPPTR16)
1083 duk_uint16_t *lst;
1084 duk_uint16_t null16 = heap->heapptr_null16;
1085 #else
1086 duk_hstring **lst;
1087 #endif
1088 duk_hstring *h;
1089
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);
1095 #else
1096 lst = e->u.strlist;
1097 #endif
1098 DUK_ASSERT(lst != NULL);
1099
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]);
1103 lst[j] = null16;
1104 #else
1105 h = lst[j];
1106 lst[j] = NULL;
1107 #endif
1108 /* strings may have inner refs (extdata) in some cases */
1109 if (h != NULL) {
1110 duk_free_hstring_inner(heap, h);
1111 DUK_FREE(heap, h);
1112 }
1113 }
1114 #if defined(DUK_USE_HEAPPTR16)
1115 e->u.strlist16 = null16;
1116 #else
1117 e->u.strlist = NULL;
1118 #endif
1119 DUK_FREE(heap, lst);
1120 } else {
1121 #if defined(DUK_USE_HEAPPTR16)
1122 h = DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.str16);
1123 e->u.str16 = null16;
1124 #else
1125 h = e->u.str;
1126 e->u.str = NULL;
1127 #endif
1128 if (h != NULL) {
1129 duk_free_hstring_inner(heap, h);
1130 DUK_FREE(heap, h);
1131 }
1132 }
1133 e->listlen = 0;
1134 }
1135 }
1136 #endif /* DUK_USE_STRTAB_CHAIN */
1137
1138 #if defined(DUK_USE_STRTAB_PROBE)
1139 DUK_INTERNAL void duk_heap_free_strtab(duk_heap *heap) {
1140 duk_uint_fast32_t i;
1141 duk_hstring *h;
1142
1143 #if defined(DUK_USE_HEAPPTR16)
1144 if (heap->strtable16) {
1145 #else
1146 if (heap->strtable) {
1147 #endif
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]);
1151 #else
1152 h = heap->strtable[i];
1153 #endif
1154 if (h == NULL || h == DUK_STRTAB_DELETED_MARKER(heap)) {
1155 continue;
1156 }
1157 DUK_ASSERT(h != NULL);
1158
1159 /* strings may have inner refs (extdata) in some cases */
1160 duk_free_hstring_inner(heap, h);
1161 DUK_FREE(heap, h);
1162 #if 0 /* not strictly necessary */
1163 heap->strtable[i] = NULL;
1164 #endif
1165 }
1166 #if defined(DUK_USE_HEAPPTR16)
1167 DUK_FREE(heap, heap->strtable16);
1168 #else
1169 DUK_FREE(heap, heap->strtable);
1170 #endif
1171 #if 0 /* not strictly necessary */
1172 heap->strtable = NULL;
1173 #endif
1174 }
1175 }
1176 #endif /* DUK_USE_STRTAB_PROBE */
1177
1178 /* Undefine local defines */
1179 #undef DUK__HASH_INITIAL
1180 #undef DUK__HASH_PROBE_STEP
1181 #undef DUK__DELETED_MARKER
1182