1/*
2** Table handling.
3** Copyright (C) 2005-2021 Mike Pall. See Copyright Notice in luajit.h
4**
5** Major portions taken verbatim or adapted from the Lua interpreter.
6** Copyright (C) 1994-2008 Lua.org, PUC-Rio. See Copyright Notice in lua.h
7*/
8
9#define lj_tab_c
10#define LUA_CORE
11
12#include "lj_obj.h"
13#include "lj_gc.h"
14#include "lj_err.h"
15#include "lj_tab.h"
16
17/* -- Object hashing ------------------------------------------------------ */
18
19/* Hash values are masked with the table hash mask and used as an index. */
20static LJ_AINLINE Node *hashmask(const GCtab *t, uint32_t hash)
21{
22 Node *n = noderef(t->node);
23 return &n[hash & t->hmask];
24}
25
26/* String IDs are generated when a string is interned. */
27#define hashstr(t, s) hashmask(t, (s)->sid)
28
29#define hashlohi(t, lo, hi) hashmask((t), hashrot((lo), (hi)))
30#define hashnum(t, o) hashlohi((t), (o)->u32.lo, ((o)->u32.hi << 1))
31#if LJ_GC64
32#define hashgcref(t, r) \
33 hashlohi((t), (uint32_t)gcrefu(r), (uint32_t)(gcrefu(r) >> 32))
34#else
35#define hashgcref(t, r) hashlohi((t), gcrefu(r), gcrefu(r) + HASH_BIAS)
36#endif
37
38/* Hash an arbitrary key and return its anchor position in the hash table. */
39static Node *hashkey(const GCtab *t, cTValue *key)
40{
41 lj_assertX(!tvisint(key), "attempt to hash integer");
42 if (tvisstr(key))
43 return hashstr(t, strV(key));
44 else if (tvisnum(key))
45 return hashnum(t, key);
46 else if (tvisbool(key))
47 return hashmask(t, boolV(key));
48 else
49 return hashgcref(t, key->gcr);
50 /* Only hash 32 bits of lightuserdata on a 64 bit CPU. Good enough? */
51}
52
53/* -- Table creation and destruction -------------------------------------- */
54
55/* Create new hash part for table. */
56static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
57{
58 uint32_t hsize;
59 Node *node;
60 lj_assertL(hbits != 0, "zero hash size");
61 if (hbits > LJ_MAX_HBITS)
62 lj_err_msg(L, LJ_ERR_TABOV);
63 hsize = 1u << hbits;
64 node = lj_mem_newvec(L, hsize, Node);
65 setmref(t->node, node);
66 setfreetop(t, node, &node[hsize]);
67 t->hmask = hsize-1;
68}
69
70/*
71** Q: Why all of these copies of t->hmask, t->node etc. to local variables?
72** A: Because alias analysis for C is _really_ tough.
73** Even state-of-the-art C compilers won't produce good code without this.
74*/
75
76/* Clear hash part of table. */
77static LJ_AINLINE void clearhpart(GCtab *t)
78{
79 uint32_t i, hmask = t->hmask;
80 Node *node = noderef(t->node);
81 lj_assertX(t->hmask != 0, "empty hash part");
82 for (i = 0; i <= hmask; i++) {
83 Node *n = &node[i];
84 setmref(n->next, NULL);
85 setnilV(&n->key);
86 setnilV(&n->val);
87 }
88}
89
90/* Clear array part of table. */
91static LJ_AINLINE void clearapart(GCtab *t)
92{
93 uint32_t i, asize = t->asize;
94 TValue *array = tvref(t->array);
95 for (i = 0; i < asize; i++)
96 setnilV(&array[i]);
97}
98
99/* Create a new table. Note: the slots are not initialized (yet). */
100static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
101{
102 GCtab *t;
103 /* First try to colocate the array part. */
104 if (LJ_MAX_COLOSIZE != 0 && asize > 0 && asize <= LJ_MAX_COLOSIZE) {
105 Node *nilnode;
106 lj_assertL((sizeof(GCtab) & 7) == 0, "bad GCtab size");
107 t = (GCtab *)lj_mem_newgco(L, sizetabcolo(asize));
108 t->gct = ~LJ_TTAB;
109 t->nomm = (uint8_t)~0;
110 t->colo = (int8_t)asize;
111 setmref(t->array, (TValue *)((char *)t + sizeof(GCtab)));
112 setgcrefnull(t->metatable);
113 t->asize = asize;
114 t->hmask = 0;
115 nilnode = &G(L)->nilnode;
116 setmref(t->node, nilnode);
117#if LJ_GC64
118 setmref(t->freetop, nilnode);
119#endif
120 } else { /* Otherwise separately allocate the array part. */
121 Node *nilnode;
122 t = lj_mem_newobj(L, GCtab);
123 t->gct = ~LJ_TTAB;
124 t->nomm = (uint8_t)~0;
125 t->colo = 0;
126 setmref(t->array, NULL);
127 setgcrefnull(t->metatable);
128 t->asize = 0; /* In case the array allocation fails. */
129 t->hmask = 0;
130 nilnode = &G(L)->nilnode;
131 setmref(t->node, nilnode);
132#if LJ_GC64
133 setmref(t->freetop, nilnode);
134#endif
135 if (asize > 0) {
136 if (asize > LJ_MAX_ASIZE)
137 lj_err_msg(L, LJ_ERR_TABOV);
138 setmref(t->array, lj_mem_newvec(L, asize, TValue));
139 t->asize = asize;
140 }
141 }
142 if (hbits)
143 newhpart(L, t, hbits);
144 return t;
145}
146
147/* Create a new table.
148**
149** IMPORTANT NOTE: The API differs from lua_createtable()!
150**
151** The array size is non-inclusive. E.g. asize=128 creates array slots
152** for 0..127, but not for 128. If you need slots 1..128, pass asize=129
153** (slot 0 is wasted in this case).
154**
155** The hash size is given in hash bits. hbits=0 means no hash part.
156** hbits=1 creates 2 hash slots, hbits=2 creates 4 hash slots and so on.
157*/
158GCtab *lj_tab_new(lua_State *L, uint32_t asize, uint32_t hbits)
159{
160 GCtab *t = newtab(L, asize, hbits);
161 clearapart(t);
162 if (t->hmask > 0) clearhpart(t);
163 return t;
164}
165
166/* The API of this function conforms to lua_createtable(). */
167GCtab *lj_tab_new_ah(lua_State *L, int32_t a, int32_t h)
168{
169 return lj_tab_new(L, (uint32_t)(a > 0 ? a+1 : 0), hsize2hbits(h));
170}
171
172#if LJ_HASJIT
173GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize)
174{
175 GCtab *t = newtab(L, ahsize & 0xffffff, ahsize >> 24);
176 clearapart(t);
177 if (t->hmask > 0) clearhpart(t);
178 return t;
179}
180#endif
181
182/* Duplicate a table. */
183GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
184{
185 GCtab *t;
186 uint32_t asize, hmask;
187 t = newtab(L, kt->asize, kt->hmask > 0 ? lj_fls(kt->hmask)+1 : 0);
188 lj_assertL(kt->asize == t->asize && kt->hmask == t->hmask,
189 "mismatched size of table and template");
190 t->nomm = 0; /* Keys with metamethod names may be present. */
191 asize = kt->asize;
192 if (asize > 0) {
193 TValue *array = tvref(t->array);
194 TValue *karray = tvref(kt->array);
195 if (asize < 64) { /* An inlined loop beats memcpy for < 512 bytes. */
196 uint32_t i;
197 for (i = 0; i < asize; i++)
198 copyTV(L, &array[i], &karray[i]);
199 } else {
200 memcpy(array, karray, asize*sizeof(TValue));
201 }
202 }
203 hmask = kt->hmask;
204 if (hmask > 0) {
205 uint32_t i;
206 Node *node = noderef(t->node);
207 Node *knode = noderef(kt->node);
208 ptrdiff_t d = (char *)node - (char *)knode;
209 setfreetop(t, node, (Node *)((char *)getfreetop(kt, knode) + d));
210 for (i = 0; i <= hmask; i++) {
211 Node *kn = &knode[i];
212 Node *n = &node[i];
213 Node *next = nextnode(kn);
214 /* Don't use copyTV here, since it asserts on a copy of a dead key. */
215 n->val = kn->val; n->key = kn->key;
216 setmref(n->next, next == NULL? next : (Node *)((char *)next + d));
217 }
218 }
219 return t;
220}
221
222/* Clear a table. */
223void LJ_FASTCALL lj_tab_clear(GCtab *t)
224{
225 clearapart(t);
226 if (t->hmask > 0) {
227 Node *node = noderef(t->node);
228 setfreetop(t, node, &node[t->hmask+1]);
229 clearhpart(t);
230 }
231}
232
233/* Free a table. */
234void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
235{
236 if (t->hmask > 0)
237 lj_mem_freevec(g, noderef(t->node), t->hmask+1, Node);
238 if (t->asize > 0 && LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
239 lj_mem_freevec(g, tvref(t->array), t->asize, TValue);
240 if (LJ_MAX_COLOSIZE != 0 && t->colo)
241 lj_mem_free(g, t, sizetabcolo((uint32_t)t->colo & 0x7f));
242 else
243 lj_mem_freet(g, t);
244}
245
246/* -- Table resizing ------------------------------------------------------ */
247
248/* Resize a table to fit the new array/hash part sizes. */
249void lj_tab_resize(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
250{
251 Node *oldnode = noderef(t->node);
252 uint32_t oldasize = t->asize;
253 uint32_t oldhmask = t->hmask;
254 if (asize > oldasize) { /* Array part grows? */
255 TValue *array;
256 uint32_t i;
257 if (asize > LJ_MAX_ASIZE)
258 lj_err_msg(L, LJ_ERR_TABOV);
259 if (LJ_MAX_COLOSIZE != 0 && t->colo > 0) {
260 /* A colocated array must be separated and copied. */
261 TValue *oarray = tvref(t->array);
262 array = lj_mem_newvec(L, asize, TValue);
263 t->colo = (int8_t)(t->colo | 0x80); /* Mark as separated (colo < 0). */
264 for (i = 0; i < oldasize; i++)
265 copyTV(L, &array[i], &oarray[i]);
266 } else {
267 array = (TValue *)lj_mem_realloc(L, tvref(t->array),
268 oldasize*sizeof(TValue), asize*sizeof(TValue));
269 }
270 setmref(t->array, array);
271 t->asize = asize;
272 for (i = oldasize; i < asize; i++) /* Clear newly allocated slots. */
273 setnilV(&array[i]);
274 }
275 /* Create new (empty) hash part. */
276 if (hbits) {
277 newhpart(L, t, hbits);
278 clearhpart(t);
279 } else {
280 global_State *g = G(L);
281 setmref(t->node, &g->nilnode);
282#if LJ_GC64
283 setmref(t->freetop, &g->nilnode);
284#endif
285 t->hmask = 0;
286 }
287 if (asize < oldasize) { /* Array part shrinks? */
288 TValue *array = tvref(t->array);
289 uint32_t i;
290 t->asize = asize; /* Note: This 'shrinks' even colocated arrays. */
291 for (i = asize; i < oldasize; i++) /* Reinsert old array values. */
292 if (!tvisnil(&array[i]))
293 copyTV(L, lj_tab_setinth(L, t, (int32_t)i), &array[i]);
294 /* Physically shrink only separated arrays. */
295 if (LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
296 setmref(t->array, lj_mem_realloc(L, array,
297 oldasize*sizeof(TValue), asize*sizeof(TValue)));
298 }
299 if (oldhmask > 0) { /* Reinsert pairs from old hash part. */
300 global_State *g;
301 uint32_t i;
302 for (i = 0; i <= oldhmask; i++) {
303 Node *n = &oldnode[i];
304 if (!tvisnil(&n->val))
305 copyTV(L, lj_tab_set(L, t, &n->key), &n->val);
306 }
307 g = G(L);
308 lj_mem_freevec(g, oldnode, oldhmask+1, Node);
309 }
310}
311
312static uint32_t countint(cTValue *key, uint32_t *bins)
313{
314 lj_assertX(!tvisint(key), "bad integer key");
315 if (tvisnum(key)) {
316 lua_Number nk = numV(key);
317 int32_t k = lj_num2int(nk);
318 if ((uint32_t)k < LJ_MAX_ASIZE && nk == (lua_Number)k) {
319 bins[(k > 2 ? lj_fls((uint32_t)(k-1)) : 0)]++;
320 return 1;
321 }
322 }
323 return 0;
324}
325
326static uint32_t countarray(const GCtab *t, uint32_t *bins)
327{
328 uint32_t na, b, i;
329 if (t->asize == 0) return 0;
330 for (na = i = b = 0; b < LJ_MAX_ABITS; b++) {
331 uint32_t n, top = 2u << b;
332 TValue *array;
333 if (top >= t->asize) {
334 top = t->asize-1;
335 if (i > top)
336 break;
337 }
338 array = tvref(t->array);
339 for (n = 0; i <= top; i++)
340 if (!tvisnil(&array[i]))
341 n++;
342 bins[b] += n;
343 na += n;
344 }
345 return na;
346}
347
348static uint32_t counthash(const GCtab *t, uint32_t *bins, uint32_t *narray)
349{
350 uint32_t total, na, i, hmask = t->hmask;
351 Node *node = noderef(t->node);
352 for (total = na = 0, i = 0; i <= hmask; i++) {
353 Node *n = &node[i];
354 if (!tvisnil(&n->val)) {
355 na += countint(&n->key, bins);
356 total++;
357 }
358 }
359 *narray += na;
360 return total;
361}
362
363static uint32_t bestasize(uint32_t bins[], uint32_t *narray)
364{
365 uint32_t b, sum, na = 0, sz = 0, nn = *narray;
366 for (b = 0, sum = 0; 2*nn > (1u<<b) && sum != nn; b++)
367 if (bins[b] > 0 && 2*(sum += bins[b]) > (1u<<b)) {
368 sz = (2u<<b)+1;
369 na = sum;
370 }
371 *narray = sz;
372 return na;
373}
374
375static void rehashtab(lua_State *L, GCtab *t, cTValue *ek)
376{
377 uint32_t bins[LJ_MAX_ABITS];
378 uint32_t total, asize, na, i;
379 for (i = 0; i < LJ_MAX_ABITS; i++) bins[i] = 0;
380 asize = countarray(t, bins);
381 total = 1 + asize;
382 total += counthash(t, bins, &asize);
383 asize += countint(ek, bins);
384 na = bestasize(bins, &asize);
385 total -= na;
386 lj_tab_resize(L, t, asize, hsize2hbits(total));
387}
388
389#if LJ_HASFFI
390void lj_tab_rehash(lua_State *L, GCtab *t)
391{
392 rehashtab(L, t, niltv(L));
393}
394#endif
395
396void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
397{
398 lj_tab_resize(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
399}
400
401/* -- Table getters ------------------------------------------------------- */
402
403cTValue * LJ_FASTCALL lj_tab_getinth(GCtab *t, int32_t key)
404{
405 TValue k;
406 Node *n;
407 k.n = (lua_Number)key;
408 n = hashnum(t, &k);
409 do {
410 if (tvisnum(&n->key) && n->key.n == k.n)
411 return &n->val;
412 } while ((n = nextnode(n)));
413 return NULL;
414}
415
416cTValue *lj_tab_getstr(GCtab *t, GCstr *key)
417{
418 Node *n = hashstr(t, key);
419 do {
420 if (tvisstr(&n->key) && strV(&n->key) == key)
421 return &n->val;
422 } while ((n = nextnode(n)));
423 return NULL;
424}
425
426cTValue *lj_tab_get(lua_State *L, GCtab *t, cTValue *key)
427{
428 if (tvisstr(key)) {
429 cTValue *tv = lj_tab_getstr(t, strV(key));
430 if (tv)
431 return tv;
432 } else if (tvisint(key)) {
433 cTValue *tv = lj_tab_getint(t, intV(key));
434 if (tv)
435 return tv;
436 } else if (tvisnum(key)) {
437 lua_Number nk = numV(key);
438 int32_t k = lj_num2int(nk);
439 if (nk == (lua_Number)k) {
440 cTValue *tv = lj_tab_getint(t, k);
441 if (tv)
442 return tv;
443 } else {
444 goto genlookup; /* Else use the generic lookup. */
445 }
446 } else if (!tvisnil(key)) {
447 Node *n;
448 genlookup:
449 n = hashkey(t, key);
450 do {
451 if (lj_obj_equal(&n->key, key))
452 return &n->val;
453 } while ((n = nextnode(n)));
454 }
455 return niltv(L);
456}
457
458/* -- Table setters ------------------------------------------------------- */
459
460/* Insert new key. Use Brent's variation to optimize the chain length. */
461TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
462{
463 Node *n = hashkey(t, key);
464 if (!tvisnil(&n->val) || t->hmask == 0) {
465 Node *nodebase = noderef(t->node);
466 Node *collide, *freenode = getfreetop(t, nodebase);
467 lj_assertL(freenode >= nodebase && freenode <= nodebase+t->hmask+1,
468 "bad freenode");
469 do {
470 if (freenode == nodebase) { /* No free node found? */
471 rehashtab(L, t, key); /* Rehash table. */
472 return lj_tab_set(L, t, key); /* Retry key insertion. */
473 }
474 } while (!tvisnil(&(--freenode)->key));
475 setfreetop(t, nodebase, freenode);
476 lj_assertL(freenode != &G(L)->nilnode, "store to fallback hash");
477 collide = hashkey(t, &n->key);
478 if (collide != n) { /* Colliding node not the main node? */
479 while (noderef(collide->next) != n) /* Find predecessor. */
480 collide = nextnode(collide);
481 setmref(collide->next, freenode); /* Relink chain. */
482 /* Copy colliding node into free node and free main node. */
483 freenode->val = n->val;
484 freenode->key = n->key;
485 freenode->next = n->next;
486 setmref(n->next, NULL);
487 setnilV(&n->val);
488 /* Rechain pseudo-resurrected string keys with colliding hashes. */
489 while (nextnode(freenode)) {
490 Node *nn = nextnode(freenode);
491 if (!tvisnil(&nn->val) && hashkey(t, &nn->key) == n) {
492 freenode->next = nn->next;
493 nn->next = n->next;
494 setmref(n->next, nn);
495 /*
496 ** Rechaining a resurrected string key creates a new dilemma:
497 ** Another string key may have originally been resurrected via
498 ** _any_ of the previous nodes as a chain anchor. Including
499 ** a node that had to be moved, which makes them unreachable.
500 ** It's not feasible to check for all previous nodes, so rechain
501 ** any string key that's currently in a non-main positions.
502 */
503 while ((nn = nextnode(freenode))) {
504 if (!tvisnil(&nn->val)) {
505 Node *mn = hashkey(t, &nn->key);
506 if (mn != freenode && mn != nn) {
507 freenode->next = nn->next;
508 nn->next = mn->next;
509 setmref(mn->next, nn);
510 } else {
511 freenode = nn;
512 }
513 } else {
514 freenode = nn;
515 }
516 }
517 break;
518 } else {
519 freenode = nn;
520 }
521 }
522 } else { /* Otherwise use free node. */
523 setmrefr(freenode->next, n->next); /* Insert into chain. */
524 setmref(n->next, freenode);
525 n = freenode;
526 }
527 }
528 n->key.u64 = key->u64;
529 if (LJ_UNLIKELY(tvismzero(&n->key)))
530 n->key.u64 = 0;
531 lj_gc_anybarriert(L, t);
532 lj_assertL(tvisnil(&n->val), "new hash slot is not empty");
533 return &n->val;
534}
535
536TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)
537{
538 TValue k;
539 Node *n;
540 k.n = (lua_Number)key;
541 n = hashnum(t, &k);
542 do {
543 if (tvisnum(&n->key) && n->key.n == k.n)
544 return &n->val;
545 } while ((n = nextnode(n)));
546 return lj_tab_newkey(L, t, &k);
547}
548
549TValue *lj_tab_setstr(lua_State *L, GCtab *t, GCstr *key)
550{
551 TValue k;
552 Node *n = hashstr(t, key);
553 do {
554 if (tvisstr(&n->key) && strV(&n->key) == key)
555 return &n->val;
556 } while ((n = nextnode(n)));
557 setstrV(L, &k, key);
558 return lj_tab_newkey(L, t, &k);
559}
560
561TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
562{
563 Node *n;
564 t->nomm = 0; /* Invalidate negative metamethod cache. */
565 if (tvisstr(key)) {
566 return lj_tab_setstr(L, t, strV(key));
567 } else if (tvisint(key)) {
568 return lj_tab_setint(L, t, intV(key));
569 } else if (tvisnum(key)) {
570 lua_Number nk = numV(key);
571 int32_t k = lj_num2int(nk);
572 if (nk == (lua_Number)k)
573 return lj_tab_setint(L, t, k);
574 if (tvisnan(key))
575 lj_err_msg(L, LJ_ERR_NANIDX);
576 /* Else use the generic lookup. */
577 } else if (tvisnil(key)) {
578 lj_err_msg(L, LJ_ERR_NILIDX);
579 }
580 n = hashkey(t, key);
581 do {
582 if (lj_obj_equal(&n->key, key))
583 return &n->val;
584 } while ((n = nextnode(n)));
585 return lj_tab_newkey(L, t, key);
586}
587
588/* -- Table traversal ----------------------------------------------------- */
589
590/* Get the traversal index of a key. */
591static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key)
592{
593 TValue tmp;
594 if (tvisint(key)) {
595 int32_t k = intV(key);
596 if ((uint32_t)k < t->asize)
597 return (uint32_t)k; /* Array key indexes: [0..t->asize-1] */
598 setnumV(&tmp, (lua_Number)k);
599 key = &tmp;
600 } else if (tvisnum(key)) {
601 lua_Number nk = numV(key);
602 int32_t k = lj_num2int(nk);
603 if ((uint32_t)k < t->asize && nk == (lua_Number)k)
604 return (uint32_t)k; /* Array key indexes: [0..t->asize-1] */
605 }
606 if (!tvisnil(key)) {
607 Node *n = hashkey(t, key);
608 do {
609 if (lj_obj_equal(&n->key, key))
610 return t->asize + (uint32_t)(n - noderef(t->node));
611 /* Hash key indexes: [t->asize..t->asize+t->nmask] */
612 } while ((n = nextnode(n)));
613 if (key->u32.hi == 0xfffe7fff) /* ITERN was despecialized while running. */
614 return key->u32.lo - 1;
615 lj_err_msg(L, LJ_ERR_NEXTIDX);
616 return 0; /* unreachable */
617 }
618 return ~0u; /* A nil key starts the traversal. */
619}
620
621/* Advance to the next step in a table traversal. */
622int lj_tab_next(lua_State *L, GCtab *t, TValue *key)
623{
624 uint32_t i = keyindex(L, t, key); /* Find predecessor key index. */
625 for (i++; i < t->asize; i++) /* First traverse the array keys. */
626 if (!tvisnil(arrayslot(t, i))) {
627 setintV(key, i);
628 copyTV(L, key+1, arrayslot(t, i));
629 return 1;
630 }
631 for (i -= t->asize; i <= t->hmask; i++) { /* Then traverse the hash keys. */
632 Node *n = &noderef(t->node)[i];
633 if (!tvisnil(&n->val)) {
634 copyTV(L, key, &n->key);
635 copyTV(L, key+1, &n->val);
636 return 1;
637 }
638 }
639 return 0; /* End of traversal. */
640}
641
642/* -- Table length calculation -------------------------------------------- */
643
644/* Compute table length. Slow path with mixed array/hash lookups. */
645LJ_NOINLINE static MSize tab_len_slow(GCtab *t, size_t hi)
646{
647 cTValue *tv;
648 size_t lo = hi;
649 hi++;
650 /* Widening search for an upper bound. */
651 while ((tv = lj_tab_getint(t, (int32_t)hi)) && !tvisnil(tv)) {
652 lo = hi;
653 hi += hi;
654 if (hi > (size_t)(INT_MAX-2)) { /* Punt and do a linear search. */
655 lo = 1;
656 while ((tv = lj_tab_getint(t, (int32_t)lo)) && !tvisnil(tv)) lo++;
657 return (MSize)(lo - 1);
658 }
659 }
660 /* Binary search to find a non-nil to nil transition. */
661 while (hi - lo > 1) {
662 size_t mid = (lo+hi) >> 1;
663 cTValue *tvb = lj_tab_getint(t, (int32_t)mid);
664 if (tvb && !tvisnil(tvb)) lo = mid; else hi = mid;
665 }
666 return (MSize)lo;
667}
668
669/* Compute table length. Fast path. */
670MSize LJ_FASTCALL lj_tab_len(GCtab *t)
671{
672 size_t hi = (size_t)t->asize;
673 if (hi) hi--;
674 /* In a growing array the last array element is very likely nil. */
675 if (hi > 0 && LJ_LIKELY(tvisnil(arrayslot(t, hi)))) {
676 /* Binary search to find a non-nil to nil transition in the array. */
677 size_t lo = 0;
678 while (hi - lo > 1) {
679 size_t mid = (lo+hi) >> 1;
680 if (tvisnil(arrayslot(t, mid))) hi = mid; else lo = mid;
681 }
682 return (MSize)lo;
683 }
684 /* Without a hash part, there's an implicit nil after the last element. */
685 return t->hmask ? tab_len_slow(t, hi) : (MSize)hi;
686}
687
688#if LJ_HASJIT
689/* Verify hinted table length or compute it. */
690MSize LJ_FASTCALL lj_tab_len_hint(GCtab *t, size_t hint)
691{
692 size_t asize = (size_t)t->asize;
693 cTValue *tv = arrayslot(t, hint);
694 if (LJ_LIKELY(hint+1 < asize)) {
695 if (LJ_LIKELY(!tvisnil(tv) && tvisnil(tv+1))) return (MSize)hint;
696 } else if (hint+1 <= asize && LJ_LIKELY(t->hmask == 0) && !tvisnil(tv)) {
697 return (MSize)hint;
698 }
699 return lj_tab_len(t);
700}
701#endif
702
703