]> git.proxmox.com Git - ceph.git/blob - ceph/src/civetweb/src/third_party/duktape-1.3.0/src-separate/duk_heap_stringtable.c
projects / ceph.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
add subtree-ish sources for 12.0.3
[ceph.git] / ceph / src / civetweb / src / third_party / duktape-1.3.0 / src-separate / duk_heap_stringtable.c
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 /*
14 * Create a hstring and insert into the heap. The created object
15 * is directly garbage collectable with reference count zero.
16 *
17 * The caller must place the interned string into the stringtable
18 * immediately (without chance of a longjmp); otherwise the string
19 * is lost.
20 */
21
22 DUK_LOCAL
23 duk_hstring *duk__alloc_init_hstring(duk_heap *heap,
24 const duk_uint8_t *str,
25 duk_uint32_t blen,
26 duk_uint32_t strhash,
27 const duk_uint8_t *extdata) {
28 duk_hstring *res = NULL;
29 duk_uint8_t *data;
30 duk_size_t alloc_size;
31 duk_uarridx_t dummy;
32 duk_uint32_t clen;
33
34 #if defined(DUK_USE_STRLEN16)
35 /* If blen <= 0xffffUL, clen is also guaranteed to be <= 0xffffUL. */
36 if (blen > 0xffffUL) {
37 DUK_D(DUK_DPRINT("16-bit string blen/clen active and blen over 16 bits, reject intern"));
38 return NULL;
39 }
40 #endif
41
42 if (extdata) {
43 alloc_size = (duk_size_t) sizeof(duk_hstring_external);
44 res = (duk_hstring *) DUK_ALLOC(heap, alloc_size);
45 if (!res) {
46 goto alloc_error;
47 }
48 DUK_MEMZERO(res, sizeof(duk_hstring_external));
49 #ifdef DUK_USE_EXPLICIT_NULL_INIT
50 DUK_HEAPHDR_STRING_INIT_NULLS(&res->hdr);
51 #endif
52 DUK_HEAPHDR_SET_TYPE_AND_FLAGS(&res->hdr, DUK_HTYPE_STRING, DUK_HSTRING_FLAG_EXTDATA);
53
54 ((duk_hstring_external *) res)->extdata = extdata;
55 } else {
56 /* NUL terminate for convenient C access */
57 alloc_size = (duk_size_t) (sizeof(duk_hstring) + blen + 1);
58 res = (duk_hstring *) DUK_ALLOC(heap, alloc_size);
59 if (!res) {
60 goto alloc_error;
61 }
62 DUK_MEMZERO(res, sizeof(duk_hstring));
63 #ifdef DUK_USE_EXPLICIT_NULL_INIT
64 DUK_HEAPHDR_STRING_INIT_NULLS(&res->hdr);
65 #endif
66 DUK_HEAPHDR_SET_TYPE_AND_FLAGS(&res->hdr, DUK_HTYPE_STRING, 0);
67
68 data = (duk_uint8_t *) (res + 1);
69 DUK_MEMCPY(data, str, blen);
70 data[blen] = (duk_uint8_t) 0;
71 }
72
73 if (duk_js_to_arrayindex_raw_string(str, blen, &dummy)) {
74 DUK_HSTRING_SET_ARRIDX(res);
75 }
76
77 /* All strings beginning with 0xff are treated as "internal",
78 * even strings interned by the user. This allows user code to
79 * create internal properties too, and makes behavior consistent
80 * in case user code happens to use a string also used by Duktape
81 * (such as string has already been interned and has the 'internal'
82 * flag set).
83 */
84 if (blen > 0 && str[0] == (duk_uint8_t) 0xff) {
85 DUK_HSTRING_SET_INTERNAL(res);
86 }
87
88 DUK_HSTRING_SET_HASH(res, strhash);
89 DUK_HSTRING_SET_BYTELEN(res, blen);
90 clen = (duk_uint32_t) duk_unicode_unvalidated_utf8_length(str, (duk_size_t) blen);
91 DUK_ASSERT(clen <= blen);
92 DUK_HSTRING_SET_CHARLEN(res, clen);
93
94 DUK_DDD(DUK_DDDPRINT("interned string, hash=0x%08lx, blen=%ld, clen=%ld, has_arridx=%ld, has_extdata=%ld",
95 (unsigned long) DUK_HSTRING_GET_HASH(res),
96 (long) DUK_HSTRING_GET_BYTELEN(res),
97 (long) DUK_HSTRING_GET_CHARLEN(res),
98 (long) DUK_HSTRING_HAS_ARRIDX(res) ? 1 : 0,
99 (long) DUK_HSTRING_HAS_EXTDATA(res) ? 1 : 0));
100
101 return res;
102
103 alloc_error:
104 DUK_FREE(heap, res);
105 return NULL;
106 }
107
108 /*
109 * String table algorithm: fixed size string table with array chaining
110 *
111 * The top level string table has a fixed size, with each slot holding
112 * either NULL, string pointer, or pointer to a separately allocated
113 * string pointer list.
114 *
115 * This is good for low memory environments using a pool allocator: the
116 * top level allocation has a fixed size and the pointer lists have quite
117 * small allocation size, which further matches the typical pool sizes
118 * needed by objects, strings, property tables, etc.
119 */
120
121 #if defined(DUK_USE_STRTAB_CHAIN)
122
123 #if defined(DUK_USE_HEAPPTR16)
124 DUK_LOCAL duk_bool_t duk__insert_hstring_chain(duk_heap *heap, duk_hstring *h) {
125 duk_small_uint_t slotidx;
126 duk_strtab_entry *e;
127 duk_uint16_t *lst;
128 duk_uint16_t *new_lst;
129 duk_size_t i, n;
130 duk_uint16_t null16 = heap->heapptr_null16;
131 duk_uint16_t h16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
132
133 DUK_ASSERT(heap != NULL);
134 DUK_ASSERT(h != NULL);
135
136 slotidx = DUK_HSTRING_GET_HASH(h) % DUK_STRTAB_CHAIN_SIZE;
137 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
138
139 e = heap->strtable + slotidx;
140 if (e->listlen == 0) {
141 if (e->u.str16 == null16) {
142 e->u.str16 = h16;
143 } else {
144 /* Now two entries in the same slot, alloc list */
145 lst = (duk_uint16_t *) DUK_ALLOC(heap, sizeof(duk_uint16_t) * 2);
146 if (lst == NULL) {
147 return 1; /* fail */
148 }
149 lst[0] = e->u.str16;
150 lst[1] = h16;
151 e->u.strlist16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) lst);
152 e->listlen = 2;
153 }
154 } else {
155 DUK_ASSERT(e->u.strlist16 != null16);
156 lst = (duk_uint16_t *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.strlist16);
157 DUK_ASSERT(lst != NULL);
158 for (i = 0, n = e->listlen; i < n; i++) {
159 if (lst[i] == null16) {
160 lst[i] = h16;
161 return 0;
162 }
163 }
164
165 if (e->listlen + 1 == 0) {
166 /* Overflow, relevant mainly when listlen is 16 bits. */
167 return 1; /* fail */
168 }
169
170 new_lst = (duk_uint16_t *) DUK_REALLOC(heap, lst, sizeof(duk_uint16_t) * (e->listlen + 1));
171 if (new_lst == NULL) {
172 return 1; /* fail */
173 }
174 new_lst[e->listlen++] = h16;
175 e->u.strlist16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) new_lst);
176 }
177 return 0;
178 }
179 #else /* DUK_USE_HEAPPTR16 */
180 DUK_LOCAL duk_bool_t duk__insert_hstring_chain(duk_heap *heap, duk_hstring *h) {
181 duk_small_uint_t slotidx;
182 duk_strtab_entry *e;
183 duk_hstring **lst;
184 duk_hstring **new_lst;
185 duk_size_t i, n;
186
187 DUK_ASSERT(heap != NULL);
188 DUK_ASSERT(h != NULL);
189
190 slotidx = DUK_HSTRING_GET_HASH(h) % DUK_STRTAB_CHAIN_SIZE;
191 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
192
193 e = heap->strtable + slotidx;
194 if (e->listlen == 0) {
195 if (e->u.str == NULL) {
196 e->u.str = h;
197 } else {
198 /* Now two entries in the same slot, alloc list */
199 lst = (duk_hstring **) DUK_ALLOC(heap, sizeof(duk_hstring *) * 2);
200 if (lst == NULL) {
201 return 1; /* fail */
202 }
203 lst[0] = e->u.str;
204 lst[1] = h;
205 e->u.strlist = lst;
206 e->listlen = 2;
207 }
208 } else {
209 DUK_ASSERT(e->u.strlist != NULL);
210 lst = e->u.strlist;
211 for (i = 0, n = e->listlen; i < n; i++) {
212 if (lst[i] == NULL) {
213 lst[i] = h;
214 return 0;
215 }
216 }
217
218 if (e->listlen + 1 == 0) {
219 /* Overflow, relevant mainly when listlen is 16 bits. */
220 return 1; /* fail */
221 }
222
223 new_lst = (duk_hstring **) DUK_REALLOC(heap, e->u.strlist, sizeof(duk_hstring *) * (e->listlen + 1));
224 if (new_lst == NULL) {
225 return 1; /* fail */
226 }
227 new_lst[e->listlen++] = h;
228 e->u.strlist = new_lst;
229 }
230 return 0;
231 }
232 #endif /* DUK_USE_HEAPPTR16 */
233
234 #if defined(DUK_USE_HEAPPTR16)
235 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) {
236 duk_small_uint_t slotidx;
237 duk_strtab_entry *e;
238 duk_uint16_t *lst;
239 duk_size_t i, n;
240 duk_uint16_t null16 = heap->heapptr_null16;
241
242 DUK_ASSERT(heap != NULL);
243
244 slotidx = strhash % DUK_STRTAB_CHAIN_SIZE;
245 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
246
247 e = heap->strtable + slotidx;
248 if (e->listlen == 0) {
249 if (e->u.str16 != null16) {
250 duk_hstring *h = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.str16);
251 DUK_ASSERT(h != NULL);
252 if (DUK_HSTRING_GET_BYTELEN(h) == blen &&
253 DUK_MEMCMP(str, DUK_HSTRING_GET_DATA(h), blen) == 0) {
254 return h;
255 }
256 }
257 } else {
258 DUK_ASSERT(e->u.strlist16 != null16);
259 lst = (duk_uint16_t *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.strlist16);
260 DUK_ASSERT(lst != NULL);
261 for (i = 0, n = e->listlen; i < n; i++) {
262 if (lst[i] != null16) {
263 duk_hstring *h = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, lst[i]);
264 DUK_ASSERT(h != NULL);
265 if (DUK_HSTRING_GET_BYTELEN(h) == blen &&
266 DUK_MEMCMP(str, DUK_HSTRING_GET_DATA(h), blen) == 0) {
267 return h;
268 }
269 }
270 }
271 }
272
273 return NULL;
274 }
275 #else /* DUK_USE_HEAPPTR16 */
276 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) {
277 duk_small_uint_t slotidx;
278 duk_strtab_entry *e;
279 duk_hstring **lst;
280 duk_size_t i, n;
281
282 DUK_ASSERT(heap != NULL);
283
284 slotidx = strhash % DUK_STRTAB_CHAIN_SIZE;
285 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
286
287 e = heap->strtable + slotidx;
288 if (e->listlen == 0) {
289 if (e->u.str != NULL &&
290 DUK_HSTRING_GET_BYTELEN(e->u.str) == blen &&
291 DUK_MEMCMP(str, DUK_HSTRING_GET_DATA(e->u.str), blen) == 0) {
292 return e->u.str;
293 }
294 } else {
295 DUK_ASSERT(e->u.strlist != NULL);
296 lst = e->u.strlist;
297 for (i = 0, n = e->listlen; i < n; i++) {
298 if (lst[i] != NULL &&
299 DUK_HSTRING_GET_BYTELEN(lst[i]) == blen &&
300 DUK_MEMCMP(str, DUK_HSTRING_GET_DATA(lst[i]), blen) == 0) {
301 return lst[i];
302 }
303 }
304 }
305
306 return NULL;
307 }
308 #endif /* DUK_USE_HEAPPTR16 */
309
310 #if defined(DUK_USE_HEAPPTR16)
311 DUK_LOCAL void duk__remove_matching_hstring_chain(duk_heap *heap, duk_hstring *h) {
312 duk_small_uint_t slotidx;
313 duk_strtab_entry *e;
314 duk_uint16_t *lst;
315 duk_size_t i, n;
316 duk_uint16_t h16;
317 duk_uint16_t null16 = heap->heapptr_null16;
318
319 DUK_ASSERT(heap != NULL);
320 DUK_ASSERT(h != NULL);
321
322 slotidx = DUK_HSTRING_GET_HASH(h) % DUK_STRTAB_CHAIN_SIZE;
323 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
324
325 DUK_ASSERT(h != NULL);
326 h16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
327
328 e = heap->strtable + slotidx;
329 if (e->listlen == 0) {
330 if (e->u.str16 == h16) {
331 e->u.str16 = null16;
332 return;
333 }
334 } else {
335 DUK_ASSERT(e->u.strlist16 != null16);
336 lst = (duk_uint16_t *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.strlist16);
337 DUK_ASSERT(lst != NULL);
338 for (i = 0, n = e->listlen; i < n; i++) {
339 if (lst[i] == h16) {
340 lst[i] = null16;
341 return;
342 }
343 }
344 }
345
346 DUK_D(DUK_DPRINT("failed to find string that should be in stringtable"));
347 DUK_UNREACHABLE();
348 return;
349 }
350 #else /* DUK_USE_HEAPPTR16 */
351 DUK_LOCAL void duk__remove_matching_hstring_chain(duk_heap *heap, duk_hstring *h) {
352 duk_small_uint_t slotidx;
353 duk_strtab_entry *e;
354 duk_hstring **lst;
355 duk_size_t i, n;
356
357 DUK_ASSERT(heap != NULL);
358 DUK_ASSERT(h != NULL);
359
360 slotidx = DUK_HSTRING_GET_HASH(h) % DUK_STRTAB_CHAIN_SIZE;
361 DUK_ASSERT(slotidx < DUK_STRTAB_CHAIN_SIZE);
362
363 e = heap->strtable + slotidx;
364 if (e->listlen == 0) {
365 DUK_ASSERT(h != NULL);
366 if (e->u.str == h) {
367 e->u.str = NULL;
368 return;
369 }
370 } else {
371 DUK_ASSERT(e->u.strlist != NULL);
372 lst = e->u.strlist;
373 for (i = 0, n = e->listlen; i < n; i++) {
374 DUK_ASSERT(h != NULL);
375 if (lst[i] == h) {
376 lst[i] = NULL;
377 return;
378 }
379 }
380 }
381
382 DUK_D(DUK_DPRINT("failed to find string that should be in stringtable"));
383 DUK_UNREACHABLE();
384 return;
385 }
386 #endif /* DUK_USE_HEAPPTR16 */
387
388 #if defined(DUK_USE_DEBUG)
389 DUK_INTERNAL void duk_heap_dump_strtab(duk_heap *heap) {
390 duk_strtab_entry *e;
391 duk_small_uint_t i;
392 duk_size_t j, n, used;
393 #if defined(DUK_USE_HEAPPTR16)
394 duk_uint16_t *lst;
395 duk_uint16_t null16 = heap->heapptr_null16;
396 #else
397 duk_hstring **lst;
398 #endif
399
400 DUK_ASSERT(heap != NULL);
401
402 for (i = 0; i < DUK_STRTAB_CHAIN_SIZE; i++) {
403 e = heap->strtable + i;
404
405 if (e->listlen == 0) {
406 #if defined(DUK_USE_HEAPPTR16)
407 DUK_DD(DUK_DDPRINT("[%03d] -> plain %d", (int) i, (int) (e->u.str16 != null16 ? 1 : 0)));
408 #else
409 DUK_DD(DUK_DDPRINT("[%03d] -> plain %d", (int) i, (int) (e->u.str ? 1 : 0)));
410 #endif
411 } else {
412 used = 0;
413 #if defined(DUK_USE_HEAPPTR16)
414 lst = (duk_uint16_t *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.strlist16);
415 #else
416 lst = e->u.strlist;
417 #endif
418 DUK_ASSERT(lst != NULL);
419 for (j = 0, n = e->listlen; j < n; j++) {
420 #if defined(DUK_USE_HEAPPTR16)
421 if (lst[j] != null16) {
422 #else
423 if (lst[j] != NULL) {
424 #endif
425 used++;
426 }
427 }
428 DUK_DD(DUK_DDPRINT("[%03d] -> array %d/%d", (int) i, (int) used, (int) e->listlen));
429 }
430 }
431 }
432 #endif /* DUK_USE_DEBUG */
433
434 #endif /* DUK_USE_STRTAB_CHAIN */
435
436 /*
437 * String table algorithm: closed hashing with a probe sequence
438 *
439 * This is the default algorithm and works fine for environments with
440 * minimal memory constraints.
441 */
442
443 #if defined(DUK_USE_STRTAB_PROBE)
444
445 /* Count actually used (non-NULL, non-DELETED) entries. */
446 DUK_LOCAL duk_int_t duk__count_used_probe(duk_heap *heap) {
447 duk_int_t res = 0;
448 duk_uint_fast32_t i, n;
449 #if defined(DUK_USE_HEAPPTR16)
450 duk_uint16_t null16 = heap->heapptr_null16;
451 duk_uint16_t deleted16 = heap->heapptr_deleted16;
452 #endif
453
454 n = (duk_uint_fast32_t) heap->st_size;
455 for (i = 0; i < n; i++) {
456 #if defined(DUK_USE_HEAPPTR16)
457 if (heap->strtable16[i] != null16 && heap->strtable16[i] != deleted16) {
458 #else
459 if (heap->strtable[i] != NULL && heap->strtable[i] != DUK__DELETED_MARKER(heap)) {
460 #endif
461 res++;
462 }
463 }
464 return res;
465 }
466
467 #if defined(DUK_USE_HEAPPTR16)
468 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) {
469 #else
470 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) {
471 #endif
472 duk_uint32_t i;
473 duk_uint32_t step;
474 #if defined(DUK_USE_HEAPPTR16)
475 duk_uint16_t null16 = heap->heapptr_null16;
476 duk_uint16_t deleted16 = heap->heapptr_deleted16;
477 #endif
478
479 DUK_ASSERT(size > 0);
480
481 i = DUK__HASH_INITIAL(DUK_HSTRING_GET_HASH(h), size);
482 step = DUK__HASH_PROBE_STEP(DUK_HSTRING_GET_HASH(h));
483 for (;;) {
484 #if defined(DUK_USE_HEAPPTR16)
485 duk_uint16_t e16 = entries16[i];
486 #else
487 duk_hstring *e = entries[i];
488 #endif
489
490 #if defined(DUK_USE_HEAPPTR16)
491 /* XXX: could check for e16 == 0 because NULL is guaranteed to
492 * encode to zero.
493 */
494 if (e16 == null16) {
495 #else
496 if (e == NULL) {
497 #endif
498 DUK_DDD(DUK_DDDPRINT("insert hit (null): %ld", (long) i));
499 #if defined(DUK_USE_HEAPPTR16)
500 entries16[i] = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
501 #else
502 entries[i] = h;
503 #endif
504 (*p_used)++;
505 break;
506 #if defined(DUK_USE_HEAPPTR16)
507 } else if (e16 == deleted16) {
508 #else
509 } else if (e == DUK__DELETED_MARKER(heap)) {
510 #endif
511 /* st_used remains the same, DELETED is counted as used */
512 DUK_DDD(DUK_DDDPRINT("insert hit (deleted): %ld", (long) i));
513 #if defined(DUK_USE_HEAPPTR16)
514 entries16[i] = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
515 #else
516 entries[i] = h;
517 #endif
518 break;
519 }
520 DUK_DDD(DUK_DDDPRINT("insert miss: %ld", (long) i));
521 i = (i + step) % size;
522
523 /* looping should never happen */
524 DUK_ASSERT(i != DUK__HASH_INITIAL(DUK_HSTRING_GET_HASH(h), size));
525 }
526 }
527
528 #if defined(DUK_USE_HEAPPTR16)
529 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) {
530 #else
531 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) {
532 #endif
533 duk_uint32_t i;
534 duk_uint32_t step;
535
536 DUK_ASSERT(size > 0);
537
538 i = DUK__HASH_INITIAL(strhash, size);
539 step = DUK__HASH_PROBE_STEP(strhash);
540 for (;;) {
541 duk_hstring *e;
542 #if defined(DUK_USE_HEAPPTR16)
543 e = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, entries16[i]);
544 #else
545 e = entries[i];
546 #endif
547
548 if (!e) {
549 return NULL;
550 }
551 if (e != DUK__DELETED_MARKER(heap) && DUK_HSTRING_GET_BYTELEN(e) == blen) {
552 if (DUK_MEMCMP(str, DUK_HSTRING_GET_DATA(e), blen) == 0) {
553 DUK_DDD(DUK_DDDPRINT("find matching hit: %ld (step %ld, size %ld)",
554 (long) i, (long) step, (long) size));
555 return e;
556 }
557 }
558 DUK_DDD(DUK_DDDPRINT("find matching miss: %ld (step %ld, size %ld)",
559 (long) i, (long) step, (long) size));
560 i = (i + step) % size;
561
562 /* looping should never happen */
563 DUK_ASSERT(i != DUK__HASH_INITIAL(strhash, size));
564 }
565 DUK_UNREACHABLE();
566 }
567
568 #if defined(DUK_USE_HEAPPTR16)
569 DUK_LOCAL void duk__remove_matching_hstring_probe(duk_heap *heap, duk_uint16_t *entries16, duk_uint32_t size, duk_hstring *h) {
570 #else
571 DUK_LOCAL void duk__remove_matching_hstring_probe(duk_heap *heap, duk_hstring **entries, duk_uint32_t size, duk_hstring *h) {
572 #endif
573 duk_uint32_t i;
574 duk_uint32_t step;
575 duk_uint32_t hash;
576 #if defined(DUK_USE_HEAPPTR16)
577 duk_uint16_t null16 = heap->heapptr_null16;
578 duk_uint16_t h16 = DUK_USE_HEAPPTR_ENC16(heap->heap_udata, (void *) h);
579 #endif
580
581 DUK_ASSERT(size > 0);
582
583 hash = DUK_HSTRING_GET_HASH(h);
584 i = DUK__HASH_INITIAL(hash, size);
585 step = DUK__HASH_PROBE_STEP(hash);
586 for (;;) {
587 #if defined(DUK_USE_HEAPPTR16)
588 duk_uint16_t e16 = entries16[i];
589 #else
590 duk_hstring *e = entries[i];
591 #endif
592
593 #if defined(DUK_USE_HEAPPTR16)
594 if (e16 == null16) {
595 #else
596 if (!e) {
597 #endif
598 DUK_UNREACHABLE();
599 break;
600 }
601 #if defined(DUK_USE_HEAPPTR16)
602 if (e16 == h16) {
603 #else
604 if (e == h) {
605 #endif
606 /* st_used remains the same, DELETED is counted as used */
607 DUK_DDD(DUK_DDDPRINT("free matching hit: %ld", (long) i));
608 #if defined(DUK_USE_HEAPPTR16)
609 entries16[i] = heap->heapptr_deleted16;
610 #else
611 entries[i] = DUK__DELETED_MARKER(heap);
612 #endif
613 break;
614 }
615
616 DUK_DDD(DUK_DDDPRINT("free matching miss: %ld", (long) i));
617 i = (i + step) % size;
618
619 /* looping should never happen */
620 DUK_ASSERT(i != DUK__HASH_INITIAL(hash, size));
621 }
622 }
623
624 DUK_LOCAL duk_bool_t duk__resize_strtab_raw_probe(duk_heap *heap, duk_uint32_t new_size) {
625 #ifdef DUK_USE_MARK_AND_SWEEP
626 duk_small_uint_t prev_mark_and_sweep_base_flags;
627 #endif
628 #ifdef DUK_USE_DEBUG
629 duk_uint32_t old_used = heap->st_used;
630 #endif
631 duk_uint32_t old_size = heap->st_size;
632 #if defined(DUK_USE_HEAPPTR16)
633 duk_uint16_t *old_entries = heap->strtable16;
634 duk_uint16_t *new_entries = NULL;
635 #else
636 duk_hstring **old_entries = heap->strtable;
637 duk_hstring **new_entries = NULL;
638 #endif
639 duk_uint32_t new_used = 0;
640 duk_uint32_t i;
641
642 #ifdef DUK_USE_DEBUG
643 DUK_UNREF(old_used); /* unused with some debug level combinations */
644 #endif
645
646 #ifdef DUK_USE_DDDPRINT
647 DUK_DDD(DUK_DDDPRINT("attempt to resize stringtable: %ld entries, %ld bytes, %ld used, %ld%% load -> %ld entries, %ld bytes, %ld used, %ld%% load",
648 (long) old_size, (long) (sizeof(duk_hstring *) * old_size), (long) old_used,
649 (long) (((double) old_used) / ((double) old_size) * 100.0),
650 (long) new_size, (long) (sizeof(duk_hstring *) * new_size), (long) duk__count_used_probe(heap),
651 (long) (((double) duk__count_used_probe(heap)) / ((double) new_size) * 100.0)));
652 #endif
653
654 DUK_ASSERT(new_size > (duk_uint32_t) duk__count_used_probe(heap)); /* required for rehash to succeed, equality not that useful */
655 DUK_ASSERT(old_entries);
656 #ifdef DUK_USE_MARK_AND_SWEEP
657 DUK_ASSERT((heap->mark_and_sweep_base_flags & DUK_MS_FLAG_NO_STRINGTABLE_RESIZE) == 0);
658 #endif
659
660 /*
661 * The attempt to allocate may cause a GC. Such a GC must not attempt to resize
662 * the stringtable (though it can be swept); finalizer execution and object
663 * compaction must also be postponed to avoid the pressure to add strings to the
664 * string table.
665 */
666
667 #ifdef DUK_USE_MARK_AND_SWEEP
668 prev_mark_and_sweep_base_flags = heap->mark_and_sweep_base_flags;
669 heap->mark_and_sweep_base_flags |= \
670 DUK_MS_FLAG_NO_STRINGTABLE_RESIZE | /* avoid recursive call here */
671 DUK_MS_FLAG_NO_FINALIZERS | /* avoid pressure to add/remove strings */
672 DUK_MS_FLAG_NO_OBJECT_COMPACTION; /* avoid array abandoning which interns strings */
673 #endif
674
675 #if defined(DUK_USE_HEAPPTR16)
676 new_entries = (duk_uint16_t *) DUK_ALLOC(heap, sizeof(duk_uint16_t) * new_size);
677 #else
678 new_entries = (duk_hstring **) DUK_ALLOC(heap, sizeof(duk_hstring *) * new_size);
679 #endif
680
681 #ifdef DUK_USE_MARK_AND_SWEEP
682 heap->mark_and_sweep_base_flags = prev_mark_and_sweep_base_flags;
683 #endif
684
685 if (!new_entries) {
686 goto resize_error;
687 }
688
689 #ifdef DUK_USE_EXPLICIT_NULL_INIT
690 for (i = 0; i < new_size; i++) {
691 #if defined(DUK_USE_HEAPPTR16)
692 new_entries[i] = heap->heapptr_null16;
693 #else
694 new_entries[i] = NULL;
695 #endif
696 }
697 #else
698 #if defined(DUK_USE_HEAPPTR16)
699 /* Relies on NULL encoding to zero. */
700 DUK_MEMZERO(new_entries, sizeof(duk_uint16_t) * new_size);
701 #else
702 DUK_MEMZERO(new_entries, sizeof(duk_hstring *) * new_size);
703 #endif
704 #endif
705
706 /* Because new_size > duk__count_used_probe(heap), guaranteed to work */
707 for (i = 0; i < old_size; i++) {
708 duk_hstring *e;
709
710 #if defined(DUK_USE_HEAPPTR16)
711 e = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, old_entries[i]);
712 #else
713 e = old_entries[i];
714 #endif
715 if (e == NULL || e == DUK__DELETED_MARKER(heap)) {
716 continue;
717 }
718 /* checking for DUK__DELETED_MARKER is not necessary here, but helper does it now */
719 duk__insert_hstring_probe(heap, new_entries, new_size, &new_used, e);
720 }
721
722 #ifdef DUK_USE_DDPRINT
723 DUK_DD(DUK_DDPRINT("resized stringtable: %ld entries, %ld bytes, %ld used, %ld%% load -> %ld entries, %ld bytes, %ld used, %ld%% load",
724 (long) old_size, (long) (sizeof(duk_hstring *) * old_size), (long) old_used,
725 (long) (((double) old_used) / ((double) old_size) * 100.0),
726 (long) new_size, (long) (sizeof(duk_hstring *) * new_size), (long) new_used,
727 (long) (((double) new_used) / ((double) new_size) * 100.0)));
728 #endif
729
730 #if defined(DUK_USE_HEAPPTR16)
731 DUK_FREE(heap, heap->strtable16);
732 heap->strtable16 = new_entries;
733 #else
734 DUK_FREE(heap, heap->strtable);
735 heap->strtable = new_entries;
736 #endif
737 heap->st_size = new_size;
738 heap->st_used = new_used; /* may be less, since DELETED entries are NULLed by rehash */
739
740 return 0; /* OK */
741
742 resize_error:
743 DUK_FREE(heap, new_entries);
744 return 1; /* FAIL */
745 }
746
747 DUK_LOCAL duk_bool_t duk__resize_strtab_probe(duk_heap *heap) {
748 duk_uint32_t new_size;
749 duk_bool_t ret;
750
751 new_size = (duk_uint32_t) duk__count_used_probe(heap);
752 if (new_size >= 0x80000000UL) {
753 new_size = DUK_STRTAB_HIGHEST_32BIT_PRIME;
754 } else {
755 new_size = duk_util_get_hash_prime(DUK_STRTAB_GROW_ST_SIZE(new_size));
756 new_size = duk_util_get_hash_prime(new_size);
757 }
758 DUK_ASSERT(new_size > 0);
759
760 /* rehash even if old and new sizes are the same to get rid of
761 * DELETED entries.
762 */
763
764 ret = duk__resize_strtab_raw_probe(heap, new_size);
765
766 return ret;
767 }
768
769 DUK_LOCAL duk_bool_t duk__recheck_strtab_size_probe(duk_heap *heap, duk_uint32_t new_used) {
770 duk_uint32_t new_free;
771 duk_uint32_t tmp1;
772 duk_uint32_t tmp2;
773
774 DUK_ASSERT(new_used <= heap->st_size); /* grow by at most one */
775 new_free = heap->st_size - new_used; /* unsigned intentionally */
776
777 /* new_free / size <= 1 / DIV <=> new_free <= size / DIV */
778 /* new_used / size <= 1 / DIV <=> new_used <= size / DIV */
779
780 tmp1 = heap->st_size / DUK_STRTAB_MIN_FREE_DIVISOR;
781 tmp2 = heap->st_size / DUK_STRTAB_MIN_USED_DIVISOR;
782
783 if (new_free <= tmp1 || new_used <= tmp2) {
784 /* load factor too low or high, count actually used entries and resize */
785 return duk__resize_strtab_probe(heap);
786 } else {
787 return 0; /* OK */
788 }
789 }
790
791 #if defined(DUK_USE_DEBUG)
792 DUK_INTERNAL void duk_heap_dump_strtab(duk_heap *heap) {
793 duk_uint32_t i;
794 duk_hstring *h;
795
796 DUK_ASSERT(heap != NULL);
797 #if defined(DUK_USE_HEAPPTR16)
798 DUK_ASSERT(heap->strtable16 != NULL);
799 #else
800 DUK_ASSERT(heap->strtable != NULL);
801 #endif
802 DUK_UNREF(h);
803
804 for (i = 0; i < heap->st_size; i++) {
805 #if defined(DUK_USE_HEAPPTR16)
806 h = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->strtable16[i]);
807 #else
808 h = heap->strtable[i];
809 #endif
810
811 DUK_DD(DUK_DDPRINT("[%03d] -> %p", (int) i, (void *) h));
812 }
813 }
814 #endif /* DUK_USE_DEBUG */
815
816 #endif /* DUK_USE_STRTAB_PROBE */
817
818 /*
819 * Raw intern and lookup
820 */
821
822 DUK_LOCAL duk_hstring *duk__do_intern(duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen, duk_uint32_t strhash) {
823 duk_hstring *res;
824 const duk_uint8_t *extdata;
825
826 #if defined(DUK_USE_STRTAB_PROBE)
827 if (duk__recheck_strtab_size_probe(heap, heap->st_used + 1)) {
828 return NULL;
829 }
830 #endif
831
832 /* For manual testing only. */
833 #if 0
834 {
835 duk_size_t i;
836 DUK_PRINTF("INTERN: \"");
837 for (i = 0; i < blen; i++) {
838 duk_uint8_t x = str[i];
839 if (x >= 0x20 && x <= 0x7e && x != '"' && x != '\\') {
840 DUK_PRINTF("%c", (int) x); /* char: use int cast */
841 } else {
842 DUK_PRINTF("\\x%02lx", (long) x);
843 }
844 }
845 DUK_PRINTF("\"\n");
846 }
847 #endif
848
849 #if defined(DUK_USE_HSTRING_EXTDATA) && defined(DUK_USE_EXTSTR_INTERN_CHECK)
850 extdata = (const duk_uint8_t *) DUK_USE_EXTSTR_INTERN_CHECK(heap->heap_udata, (void *) str, (duk_size_t) blen);
851 #else
852 extdata = (const duk_uint8_t *) NULL;
853 #endif
854 res = duk__alloc_init_hstring(heap, str, blen, strhash, extdata);
855 if (!res) {
856 return NULL;
857 }
858
859 #if defined(DUK_USE_STRTAB_CHAIN)
860 if (duk__insert_hstring_chain(heap, res)) {
861 /* failed */
862 DUK_FREE(heap, res);
863 return NULL;
864 }
865 #elif defined(DUK_USE_STRTAB_PROBE)
866 /* guaranteed to succeed */
867 duk__insert_hstring_probe(heap,
868 #if defined(DUK_USE_HEAPPTR16)
869 heap->strtable16,
870 #else
871 heap->strtable,
872 #endif
873 heap->st_size,
874 &heap->st_used,
875 res);
876 #else
877 #error internal error, invalid strtab options
878 #endif
879
880 /* Note: hstring is in heap but has refcount zero and is not strongly reachable.
881 * Caller should increase refcount and make the hstring reachable before any
882 * operations which require allocation (and possible gc).
883 */
884
885 return res;
886 }
887
888 DUK_LOCAL duk_hstring *duk__do_lookup(duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen, duk_uint32_t *out_strhash) {
889 duk_hstring *res;
890
891 DUK_ASSERT(out_strhash);
892
893 *out_strhash = duk_heap_hashstring(heap, str, (duk_size_t) blen);
894
895 #if defined(DUK_USE_STRTAB_CHAIN)
896 res = duk__find_matching_string_chain(heap, str, blen, *out_strhash);
897 #elif defined(DUK_USE_STRTAB_PROBE)
898 res = duk__find_matching_string_probe(heap,
899 #if defined(DUK_USE_HEAPPTR16)
900 heap->strtable16,
901 #else
902 heap->strtable,
903 #endif
904 heap->st_size,
905 str,
906 blen,
907 *out_strhash);
908 #else
909 #error internal error, invalid strtab options
910 #endif
911
912 return res;
913 }
914
915 /*
916 * Exposed calls
917 */
918
919 #if 0 /*unused*/
920 DUK_INTERNAL duk_hstring *duk_heap_string_lookup(duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen) {
921 duk_uint32_t strhash; /* dummy */
922 return duk__do_lookup(heap, str, blen, &strhash);
923 }
924 #endif
925
926 DUK_INTERNAL duk_hstring *duk_heap_string_intern(duk_heap *heap, const duk_uint8_t *str, duk_uint32_t blen) {
927 duk_hstring *res;
928 duk_uint32_t strhash;
929
930 /* caller is responsible for ensuring this */
931 DUK_ASSERT(blen <= DUK_HSTRING_MAX_BYTELEN);
932
933 res = duk__do_lookup(heap, str, blen, &strhash);
934 if (res) {
935 return res;
936 }
937
938 res = duk__do_intern(heap, str, blen, strhash);
939 return res; /* may be NULL */
940 }
941
942 DUK_INTERNAL duk_hstring *duk_heap_string_intern_checked(duk_hthread *thr, const duk_uint8_t *str, duk_uint32_t blen) {
943 duk_hstring *res = duk_heap_string_intern(thr->heap, str, blen);
944 if (!res) {
945 DUK_ERROR(thr, DUK_ERR_ALLOC_ERROR, "failed to intern string");
946 }
947 return res;
948 }
949
950 #if 0 /*unused*/
951 DUK_INTERNAL duk_hstring *duk_heap_string_lookup_u32(duk_heap *heap, duk_uint32_t val) {
952 char buf[DUK_STRTAB_U32_MAX_STRLEN+1];
953 DUK_SNPRINTF(buf, sizeof(buf), "%lu", (unsigned long) val);
954 buf[sizeof(buf) - 1] = (char) 0;
955 DUK_ASSERT(DUK_STRLEN(buf) <= DUK_UINT32_MAX); /* formatted result limited */
956 return duk_heap_string_lookup(heap, (const duk_uint8_t *) buf, (duk_uint32_t) DUK_STRLEN(buf));
957 }
958 #endif
959
960 DUK_INTERNAL duk_hstring *duk_heap_string_intern_u32(duk_heap *heap, duk_uint32_t val) {
961 char buf[DUK_STRTAB_U32_MAX_STRLEN+1];
962 DUK_SNPRINTF(buf, sizeof(buf), "%lu", (unsigned long) val);
963 buf[sizeof(buf) - 1] = (char) 0;
964 DUK_ASSERT(DUK_STRLEN(buf) <= DUK_UINT32_MAX); /* formatted result limited */
965 return duk_heap_string_intern(heap, (const duk_uint8_t *) buf, (duk_uint32_t) DUK_STRLEN(buf));
966 }
967
968 DUK_INTERNAL duk_hstring *duk_heap_string_intern_u32_checked(duk_hthread *thr, duk_uint32_t val) {
969 duk_hstring *res = duk_heap_string_intern_u32(thr->heap, val);
970 if (!res) {
971 DUK_ERROR(thr, DUK_ERR_ALLOC_ERROR, "failed to intern string");
972 }
973 return res;
974 }
975
976 /* find and remove string from stringtable; caller must free the string itself */
977 DUK_INTERNAL void duk_heap_string_remove(duk_heap *heap, duk_hstring *h) {
978 DUK_DDD(DUK_DDDPRINT("remove string from stringtable: %!O", (duk_heaphdr *) h));
979
980 #if defined(DUK_USE_STRTAB_CHAIN)
981 duk__remove_matching_hstring_chain(heap, h);
982 #elif defined(DUK_USE_STRTAB_PROBE)
983 duk__remove_matching_hstring_probe(heap,
984 #if defined(DUK_USE_HEAPPTR16)
985 heap->strtable16,
986 #else
987 heap->strtable,
988 #endif
989 heap->st_size,
990 h);
991 #else
992 #error internal error, invalid strtab options
993 #endif
994 }
995
996 #if defined(DUK_USE_MARK_AND_SWEEP) && defined(DUK_USE_MS_STRINGTABLE_RESIZE)
997 DUK_INTERNAL void duk_heap_force_strtab_resize(duk_heap *heap) {
998 /* Force a resize so that DELETED entries are eliminated.
999 * Another option would be duk__recheck_strtab_size_probe();
1000 * but since that happens on every intern anyway, this whole
1001 * check can now be disabled.
1002 */
1003 #if defined(DUK_USE_STRTAB_CHAIN)
1004 DUK_UNREF(heap);
1005 #elif defined(DUK_USE_STRTAB_PROBE)
1006 duk__resize_strtab_probe(heap);
1007 #endif
1008 }
1009 #endif
1010
1011 #if defined(DUK_USE_STRTAB_CHAIN)
1012 DUK_INTERNAL void duk_heap_free_strtab(duk_heap *heap) {
1013 /* Free strings in the stringtable and any allocations needed
1014 * by the stringtable itself.
1015 */
1016 duk_uint_fast32_t i, j;
1017 duk_strtab_entry *e;
1018 #if defined(DUK_USE_HEAPPTR16)
1019 duk_uint16_t *lst;
1020 duk_uint16_t null16 = heap->heapptr_null16;
1021 #else
1022 duk_hstring **lst;
1023 #endif
1024 duk_hstring *h;
1025
1026 for (i = 0; i < DUK_STRTAB_CHAIN_SIZE; i++) {
1027 e = heap->strtable + i;
1028 if (e->listlen > 0) {
1029 #if defined(DUK_USE_HEAPPTR16)
1030 lst = (duk_uint16_t *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.strlist16);
1031 #else
1032 lst = e->u.strlist;
1033 #endif
1034 DUK_ASSERT(lst != NULL);
1035
1036 for (j = 0; j < e->listlen; j++) {
1037 #if defined(DUK_USE_HEAPPTR16)
1038 h = DUK_USE_HEAPPTR_DEC16(heap->heap_udata, lst[j]);
1039 lst[j] = null16;
1040 #else
1041 h = lst[j];
1042 lst[j] = NULL;
1043 #endif
1044 /* strings may have inner refs (extdata) in some cases */
1045 if (h != NULL) {
1046 duk_free_hstring_inner(heap, h);
1047 DUK_FREE(heap, h);
1048 }
1049 }
1050 #if defined(DUK_USE_HEAPPTR16)
1051 e->u.strlist16 = null16;
1052 #else
1053 e->u.strlist = NULL;
1054 #endif
1055 DUK_FREE(heap, lst);
1056 } else {
1057 #if defined(DUK_USE_HEAPPTR16)
1058 h = DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.str16);
1059 e->u.str16 = null16;
1060 #else
1061 h = e->u.str;
1062 e->u.str = NULL;
1063 #endif
1064 if (h != NULL) {
1065 duk_free_hstring_inner(heap, h);
1066 DUK_FREE(heap, h);
1067 }
1068 }
1069 e->listlen = 0;
1070 }
1071 }
1072 #endif /* DUK_USE_STRTAB_CHAIN */
1073
1074 #if defined(DUK_USE_STRTAB_PROBE)
1075 DUK_INTERNAL void duk_heap_free_strtab(duk_heap *heap) {
1076 duk_uint_fast32_t i;
1077 duk_hstring *h;
1078
1079 #if defined(DUK_USE_HEAPPTR16)
1080 if (heap->strtable16) {
1081 #else
1082 if (heap->strtable) {
1083 #endif
1084 for (i = 0; i < (duk_uint_fast32_t) heap->st_size; i++) {
1085 #if defined(DUK_USE_HEAPPTR16)
1086 h = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, heap->strtable16[i]);
1087 #else
1088 h = heap->strtable[i];
1089 #endif
1090 if (h == NULL || h == DUK_STRTAB_DELETED_MARKER(heap)) {
1091 continue;
1092 }
1093 DUK_ASSERT(h != NULL);
1094
1095 /* strings may have inner refs (extdata) in some cases */
1096 duk_free_hstring_inner(heap, h);
1097 DUK_FREE(heap, h);
1098 #if 0 /* not strictly necessary */
1099 heap->strtable[i] = NULL;
1100 #endif
1101 }
1102 #if defined(DUK_USE_HEAPPTR16)
1103 DUK_FREE(heap, heap->strtable16);
1104 #else
1105 DUK_FREE(heap, heap->strtable);
1106 #endif
1107 #if 0 /* not strictly necessary */
1108 heap->strtable = NULL;
1109 #endif
1110 }
1111 }
1112 #endif /* DUK_USE_STRTAB_PROBE */
1113
1114 /* Undefine local defines */
1115 #undef DUK__HASH_INITIAL
1116 #undef DUK__HASH_PROBE_STEP
1117 #undef DUK__DELETED_MARKER
Ceph