src/lj_tab.c

   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