luna - luajit/src/lj

  1/*
  2** Table handling.
  3** Copyright (C) 2005-2026 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. */
 20static 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. */
 37static 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. */
 58static 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. */
 72static 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). */
 81static 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*/
139GCtab *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(). */
148GCtab *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
154GCtab * 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. */
164GCtab * 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      if (tvistab(&n->val)) setnilV(&n->val); /* Replace nil value marker. */
198      setmref(n->next, next == NULL? next : (Node *)((char *)next + d));
199    }
200  }
201  return t;
202}
203
204/* Clear a table. */
205void LJ_FASTCALL lj_tab_clear(GCtab *t)
206{
207  clearapart(t);
208  if (t->hmask > 0) {
209    Node *node = noderef(t->node);
210    setfreetop(t, node, &node[t->hmask+1]);
211    clearhpart(t);
212  }
213}
214
215/* Free a table. */
216void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
217{
218  if (t->hmask > 0)
219    lj_mem_freevec(g, noderef(t->node), t->hmask+1, Node);
220  if (t->asize > 0 && LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
221    lj_mem_freevec(g, tvref(t->array), t->asize, TValue);
222  if (LJ_MAX_COLOSIZE != 0 && t->colo)
223    lj_mem_free(g, t, sizetabcolo((uint32_t)t->colo & 0x7f));
224  else
225    lj_mem_freet(g, t);
226}
227
228/* -- Table resizing ------------------------------------------------------ */
229
230/* Resize a table to fit the new array/hash part sizes. */
231void lj_tab_resize(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
232{
233  Node *oldnode = noderef(t->node);
234  uint32_t oldasize = t->asize;
235  uint32_t oldhmask = t->hmask;
236  if (asize > oldasize) {  /* Array part grows? */
237    TValue *array;
238    uint32_t i;
239    if (asize > LJ_MAX_ASIZE)
240      lj_err_msg(L, LJ_ERR_TABOV);
241    if (LJ_MAX_COLOSIZE != 0 && t->colo > 0) {
242      /* A colocated array must be separated and copied. */
243      TValue *oarray = tvref(t->array);
244      array = lj_mem_newvec(L, asize, TValue);
245      t->colo = (int8_t)(t->colo | 0x80);  /* Mark as separated (colo < 0). */
246      for (i = 0; i < oldasize; i++)
247	copyTV(L, &array[i], &oarray[i]);
248    } else {
249      array = (TValue *)lj_mem_realloc(L, tvref(t->array),
250			  oldasize*sizeof(TValue), asize*sizeof(TValue));
251    }
252    setmref(t->array, array);
253    t->asize = asize;
254    for (i = oldasize; i < asize; i++)  /* Clear newly allocated slots. */
255      setnilV(&array[i]);
256  }
257  /* Create new (empty) hash part. */
258  if (hbits) {
259    newhpart(L, t, hbits);
260    clearhpart(t);
261  } else {
262    global_State *g = G(L);
263    setmref(t->node, &g->nilnode);
264#if LJ_GC64
265    setmref(t->freetop, &g->nilnode);
266#endif
267    t->hmask = 0;
268  }
269  if (asize < oldasize) {  /* Array part shrinks? */
270    TValue *array = tvref(t->array);
271    uint32_t i;
272    t->asize = asize;  /* Note: This 'shrinks' even colocated arrays. */
273    for (i = asize; i < oldasize; i++)  /* Reinsert old array values. */
274      if (!tvisnil(&array[i]))
275	copyTV(L, lj_tab_setinth(L, t, (int32_t)i), &array[i]);
276    /* Physically shrink only separated arrays. */
277    if (LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
278      setmref(t->array, lj_mem_realloc(L, array,
279	      oldasize*sizeof(TValue), asize*sizeof(TValue)));
280  }
281  if (oldhmask > 0) {  /* Reinsert pairs from old hash part. */
282    global_State *g;
283    uint32_t i;
284    for (i = 0; i <= oldhmask; i++) {
285      Node *n = &oldnode[i];
286      if (!tvisnil(&n->val))
287	copyTV(L, lj_tab_set(L, t, &n->key), &n->val);
288    }
289    g = G(L);
290    lj_mem_freevec(g, oldnode, oldhmask+1, Node);
291  }
292}
293
294static uint32_t countint(cTValue *key, uint32_t *bins)
295{
296  lj_assertX(!tvisint(key), "bad integer key");
297  if (tvisnum(key)) {
298    int64_t i64;
299    int32_t k;
300    if (lj_num2int_cond(numV(key), i64, k, (uint32_t)i64 < LJ_MAX_ASIZE)) {
301      bins[(k > 2 ? lj_fls((uint32_t)(k-1)) : 0)]++;
302      return 1;
303    }
304  }
305  return 0;
306}
307
308static uint32_t countarray(const GCtab *t, uint32_t *bins)
309{
310  uint32_t na, b, i;
311  if (t->asize == 0) return 0;
312  for (na = i = b = 0; b < LJ_MAX_ABITS; b++) {
313    uint32_t n, top = 2u << b;
314    TValue *array;
315    if (top >= t->asize) {
316      top = t->asize-1;
317      if (i > top)
318	break;
319    }
320    array = tvref(t->array);
321    for (n = 0; i <= top; i++)
322      if (!tvisnil(&array[i]))
323	n++;
324    bins[b] += n;
325    na += n;
326  }
327  return na;
328}
329
330static uint32_t counthash(const GCtab *t, uint32_t *bins, uint32_t *narray)
331{
332  uint32_t total, na, i, hmask = t->hmask;
333  Node *node = noderef(t->node);
334  for (total = na = 0, i = 0; i <= hmask; i++) {
335    Node *n = &node[i];
336    if (!tvisnil(&n->val)) {
337      na += countint(&n->key, bins);
338      total++;
339    }
340  }
341  *narray += na;
342  return total;
343}
344
345static uint32_t bestasize(uint32_t bins[], uint32_t *narray)
346{
347  uint32_t b, sum, na = 0, sz = 0, nn = *narray;
348  for (b = 0, sum = 0; 2*nn > (1u<<b) && sum != nn; b++)
349    if (bins[b] > 0 && 2*(sum += bins[b]) > (1u<<b)) {
350      sz = (2u<<b)+1;
351      na = sum;
352    }
353  *narray = sz;
354  return na;
355}
356
357static void rehashtab(lua_State *L, GCtab *t, cTValue *ek)
358{
359  uint32_t bins[LJ_MAX_ABITS];
360  uint32_t total, asize, na, i;
361  for (i = 0; i < LJ_MAX_ABITS; i++) bins[i] = 0;
362  asize = countarray(t, bins);
363  total = 1 + asize;
364  total += counthash(t, bins, &asize);
365  asize += countint(ek, bins);
366  na = bestasize(bins, &asize);
367  total -= na;
368  lj_tab_resize(L, t, asize, hsize2hbits(total));
369}
370
371void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
372{
373  lj_tab_resize(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
374}
375
376/* -- Table getters ------------------------------------------------------- */
377
378cTValue * LJ_FASTCALL lj_tab_getinth(GCtab *t, int32_t key)
379{
380  TValue k;
381  Node *n;
382  k.n = (lua_Number)key;
383  n = hashnum(t, &k);
384  do {
385    if (tvisnum(&n->key) && n->key.n == k.n)
386      return &n->val;
387  } while ((n = nextnode(n)));
388  return NULL;
389}
390
391cTValue *lj_tab_getstr(GCtab *t, const GCstr *key)
392{
393  Node *n = hashstr(t, key);
394  do {
395    if (tvisstr(&n->key) && strV(&n->key) == key)
396      return &n->val;
397  } while ((n = nextnode(n)));
398  return NULL;
399}
400
401cTValue *lj_tab_get(lua_State *L, GCtab *t, cTValue *key)
402{
403  if (tvisstr(key)) {
404    cTValue *tv = lj_tab_getstr(t, strV(key));
405    if (tv)
406      return tv;
407  } else if (tvisint(key)) {
408    cTValue *tv = lj_tab_getint(t, intV(key));
409    if (tv)
410      return tv;
411  } else if (tvisnum(key)) {
412    int64_t i64;
413    int32_t k;
414    if (lj_num2int_check(numV(key), i64, k)) {
415      cTValue *tv = lj_tab_getint(t, k);
416      if (tv)
417	return tv;
418    } else {
419      goto genlookup;  /* Else use the generic lookup. */
420    }
421  } else if (!tvisnil(key)) {
422    Node *n;
423  genlookup:
424    n = hashkey(t, key);
425    do {
426      if (lj_obj_equal(&n->key, key))
427	return &n->val;
428    } while ((n = nextnode(n)));
429  }
430  return niltv(L);
431}
432
433/* -- Table setters ------------------------------------------------------- */
434
435/* Insert new key. Use Brent's variation to optimize the chain length. */
436TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
437{
438  Node *n = hashkey(t, key);
439  if (!tvisnil(&n->val) || t->hmask == 0) {
440    Node *nodebase = noderef(t->node);
441    Node *collide, *freenode = getfreetop(t, nodebase);
442    lj_assertL(freenode >= nodebase && freenode <= nodebase+t->hmask+1,
443	       "bad freenode");
444    do {
445      if (freenode == nodebase) {  /* No free node found? */
446	rehashtab(L, t, key);  /* Rehash table. */
447	return lj_tab_set(L, t, key);  /* Retry key insertion. */
448      }
449    } while (!tvisnil(&(--freenode)->key));
450    setfreetop(t, nodebase, freenode);
451    lj_assertL(freenode != &G(L)->nilnode, "store to fallback hash");
452    collide = hashkey(t, &n->key);
453    if (collide != n) {  /* Colliding node not the main node? */
454      while (noderef(collide->next) != n)  /* Find predecessor. */
455	collide = nextnode(collide);
456      setmref(collide->next, freenode);  /* Relink chain. */
457      /* Copy colliding node into free node and free main node. */
458      freenode->val = n->val;
459      freenode->key = n->key;
460      freenode->next = n->next;
461      setmref(n->next, NULL);
462      setnilV(&n->val);
463      /* Rechain pseudo-resurrected string keys with colliding hashes. */
464      while (nextnode(freenode)) {
465	Node *nn = nextnode(freenode);
466	if (!tvisnil(&nn->val) && hashkey(t, &nn->key) == n) {
467	  freenode->next = nn->next;
468	  nn->next = n->next;
469	  setmref(n->next, nn);
470	  /*
471	  ** Rechaining a resurrected string key creates a new dilemma:
472	  ** Another string key may have originally been resurrected via
473	  ** _any_ of the previous nodes as a chain anchor. Including
474	  ** a node that had to be moved, which makes them unreachable.
475	  ** It's not feasible to check for all previous nodes, so rechain
476	  ** any string key that's currently in a non-main positions.
477	  */
478	  while ((nn = nextnode(freenode))) {
479	    if (!tvisnil(&nn->val)) {
480	      Node *mn = hashkey(t, &nn->key);
481	      if (mn != freenode && mn != nn) {
482		freenode->next = nn->next;
483		nn->next = mn->next;
484		setmref(mn->next, nn);
485	      } else {
486		freenode = nn;
487	      }
488	    } else {
489	      freenode = nn;
490	    }
491	  }
492	  break;
493	} else {
494	  freenode = nn;
495	}
496      }
497    } else {  /* Otherwise use free node. */
498      setmrefr(freenode->next, n->next);  /* Insert into chain. */
499      setmref(n->next, freenode);
500      n = freenode;
501    }
502  }
503  n->key.u64 = key->u64;
504  if (LJ_UNLIKELY(tvismzero(&n->key)))
505    n->key.u64 = 0;
506  lj_gc_anybarriert(L, t);
507  lj_assertL(tvisnil(&n->val), "new hash slot is not empty");
508  return &n->val;
509}
510
511TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)
512{
513  TValue k;
514  Node *n;
515  k.n = (lua_Number)key;
516  n = hashnum(t, &k);
517  do {
518    if (tvisnum(&n->key) && n->key.n == k.n)
519      return &n->val;
520  } while ((n = nextnode(n)));
521  return lj_tab_newkey(L, t, &k);
522}
523
524TValue *lj_tab_setstr(lua_State *L, GCtab *t, const GCstr *key)
525{
526  TValue k;
527  Node *n = hashstr(t, key);
528  do {
529    if (tvisstr(&n->key) && strV(&n->key) == key)
530      return &n->val;
531  } while ((n = nextnode(n)));
532  setstrV(L, &k, key);
533  return lj_tab_newkey(L, t, &k);
534}
535
536TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
537{
538  Node *n;
539  t->nomm = 0;  /* Invalidate negative metamethod cache. */
540  if (tvisstr(key)) {
541    return lj_tab_setstr(L, t, strV(key));
542  } else if (tvisint(key)) {
543    return lj_tab_setint(L, t, intV(key));
544  } else if (tvisnum(key)) {
545    int64_t i64;
546    int32_t k;
547    if (lj_num2int_check(numV(key), i64, k))
548      return lj_tab_setint(L, t, k);
549    if (tvisnan(key))
550      lj_err_msg(L, LJ_ERR_NANIDX);
551    /* Else use the generic lookup. */
552  } else if (tvisnil(key)) {
553    lj_err_msg(L, LJ_ERR_NILIDX);
554  }
555  n = hashkey(t, key);
556  do {
557    if (lj_obj_equal(&n->key, key))
558      return &n->val;
559  } while ((n = nextnode(n)));
560  return lj_tab_newkey(L, t, key);
561}
562
563/* -- Table traversal ----------------------------------------------------- */
564
565/* Table traversal indexes:
566**
567** Array key index: [0 .. t->asize-1]
568** Hash key index:  [t->asize .. t->asize+t->hmask]
569** Invalid key:     ~0
570*/
571
572/* Get the successor traversal index of a key. */
573uint32_t LJ_FASTCALL lj_tab_keyindex(GCtab *t, cTValue *key)
574{
575  TValue tmp;
576  if (tvisint(key)) {
577    int32_t k = intV(key);
578    if ((uint32_t)k < t->asize)
579      return (uint32_t)k + 1;
580    setnumV(&tmp, (lua_Number)k);
581    key = &tmp;
582  } else if (tvisnum(key)) {
583    int64_t i64;
584    int32_t k;
585    if (lj_num2int_cond(numV(key), i64, k, (uint32_t)i64 < t->asize))
586      return (uint32_t)k + 1;
587  }
588  if (!tvisnil(key)) {
589    Node *n = hashkey(t, key);
590    do {
591      if (lj_obj_equal(&n->key, key))
592	return t->asize + (uint32_t)((n+1) - noderef(t->node));
593    } while ((n = nextnode(n)));
594    if (key->u32.hi == LJ_KEYINDEX)  /* Despecialized ITERN while running. */
595      return key->u32.lo;
596    return ~0u;  /* Invalid key to next. */
597  }
598  return 0;  /* A nil key starts the traversal. */
599}
600
601/* Get the next key/value pair of a table traversal. */
602int lj_tab_next(GCtab *t, cTValue *key, TValue *o)
603{
604  uint32_t idx = lj_tab_keyindex(t, key);  /* Find successor index of key. */
605  /* First traverse the array part. */
606  for (; idx < t->asize; idx++) {
607    cTValue *a = arrayslot(t, idx);
608    if (LJ_LIKELY(!tvisnil(a))) {
609      setintV(o, idx);
610      o[1] = *a;
611      return 1;
612    }
613  }
614  idx -= t->asize;
615  /* Then traverse the hash part. */
616  for (; idx <= t->hmask; idx++) {
617    Node *n = &noderef(t->node)[idx];
618    if (!tvisnil(&n->val)) {
619      o[0] = n->key;
620      o[1] = n->val;
621      return 1;
622    }
623  }
624  return (int32_t)idx < 0 ? -1 : 0;  /* Invalid key or end of traversal. */
625}
626
627/* -- Table length calculation -------------------------------------------- */
628
629/* Compute table length. Slow path with mixed array/hash lookups. */
630LJ_NOINLINE static MSize tab_len_slow(GCtab *t, size_t hi)
631{
632  cTValue *tv;
633  size_t lo = hi;
634  hi++;
635  /* Widening search for an upper bound. */
636  while ((tv = lj_tab_getint(t, (int32_t)hi)) && !tvisnil(tv)) {
637    lo = hi;
638    hi += hi;
639    if (hi > (size_t)(0x7fffffff - 2)) {  /* Punt and do a linear search. */
640      lo = 1;
641      while ((tv = lj_tab_getint(t, (int32_t)lo)) && !tvisnil(tv)) lo++;
642      return (MSize)(lo - 1);
643    }
644  }
645  /* Binary search to find a non-nil to nil transition. */
646  while (hi - lo > 1) {
647    size_t mid = (lo+hi) >> 1;
648    cTValue *tvb = lj_tab_getint(t, (int32_t)mid);
649    if (tvb && !tvisnil(tvb)) lo = mid; else hi = mid;
650  }
651  return (MSize)lo;
652}
653
654/* Compute table length. Fast path. */
655MSize LJ_FASTCALL lj_tab_len(GCtab *t)
656{
657  size_t hi = (size_t)t->asize;
658  if (hi) hi--;
659  /* In a growing array the last array element is very likely nil. */
660  if (hi > 0 && LJ_LIKELY(tvisnil(arrayslot(t, hi)))) {
661    /* Binary search to find a non-nil to nil transition in the array. */
662    size_t lo = 0;
663    while (hi - lo > 1) {
664      size_t mid = (lo+hi) >> 1;
665      if (tvisnil(arrayslot(t, mid))) hi = mid; else lo = mid;
666    }
667    return (MSize)lo;
668  }
669  /* Without a hash part, there's an implicit nil after the last element. */
670  return t->hmask ? tab_len_slow(t, hi) : (MSize)hi;
671}
672
673#if LJ_HASJIT
674/* Verify hinted table length or compute it. */
675MSize LJ_FASTCALL lj_tab_len_hint(GCtab *t, size_t hint)
676{
677  size_t asize = (size_t)t->asize;
678  cTValue *tv = arrayslot(t, hint);
679  if (LJ_LIKELY(hint+1 < asize)) {
680    if (LJ_LIKELY(!tvisnil(tv) && tvisnil(tv+1))) return (MSize)hint;
681  } else if (hint+1 <= asize && LJ_LIKELY(t->hmask == 0) && !tvisnil(tv)) {
682    return (MSize)hint;
683  }
684  return lj_tab_len(t);
685}
686#endif
687