Mercurial

comparison third_party/luajit/src/lj_tab.c @ 186:8cf4ec5e2191 hg-web

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