src/lj_tab.c

   1 /*
   2 ** Table handling.
   3 ** Copyright (C) 2005-2014 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. */
  20 static 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 hashes are precomputed when they are interned. */
  27 #define hashstr(t, s)           hashmask(t, (s)->hash)
  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 #define hashptr(t, p)           hashlohi((t), u32ptr(p), u32ptr(p) + HASH_BIAS)
  32 #define hashgcref(t, r)         hashlohi((t), gcrefu(r), gcrefu(r) + HASH_BIAS)
  33
  34 /* Hash an arbitrary key and return its anchor position in the hash table. */
  35 static Node *hashkey(const GCtab *t, cTValue *key)
  36 {
  37   lua_assert(!tvisint(key));
  38   if (tvisstr(key))
  39     return hashstr(t, strV(key));
  40   else if (tvisnum(key))
  41     return hashnum(t, key);
  42   else if (tvisbool(key))
  43     return hashmask(t, boolV(key));
  44   else
  45     return hashgcref(t, key->gcr);
  46   /* Only hash 32 bits of lightuserdata on a 64 bit CPU. Good enough? */
  47 }
  48
  49 /* -- Table creation and destruction -------------------------------------- */
  50
  51 /* Create new hash part for table. */
  52 static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
  53 {
  54   uint32_t hsize;
  55   Node *node;
  56   lua_assert(hbits != 0);
  57   if (hbits > LJ_MAX_HBITS)
  58     lj_err_msg(L, LJ_ERR_TABOV);
  59   hsize = 1u << hbits;
  60   node = lj_mem_newvec(L, hsize, Node);
  61   setmref(node->freetop, &node[hsize]);
  62   setmref(t->node, node);
  63   t->hmask = hsize-1;
  64 }
  65
  66 /*
  67 ** Q: Why all of these copies of t->hmask, t->node etc. to local variables?
  68 ** A: Because alias analysis for C is _really_ tough.
  69 **    Even state-of-the-art C compilers won't produce good code without this.
  70 */
  71
  72 /* Clear hash part of table. */
  73 static LJ_AINLINE void clearhpart(GCtab *t)
  74 {
  75   uint32_t i, hmask = t->hmask;
  76   Node *node = noderef(t->node);
  77   lua_assert(t->hmask != 0);
  78   for (i = 0; i <= hmask; i++) {
  79     Node *n = &node[i];
  80     setmref(n->next, NULL);
  81     setnilV(&n->key);
  82     setnilV(&n->val);
  83   }
  84 }
  85
  86 /* Clear array part of table. */
  87 static LJ_AINLINE void clearapart(GCtab *t)
  88 {
  89   uint32_t i, asize = t->asize;
  90   TValue *array = tvref(t->array);
  91   for (i = 0; i < asize; i++)
  92     setnilV(&array[i]);
  93 }
  94
  95 /* Create a new table. Note: the slots are not initialized (yet). */
  96 static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
  97 {
  98   GCtab *t;
  99   /* First try to colocate the array part. */
 100   if (LJ_MAX_COLOSIZE != 0 && asize > 0 && asize <= LJ_MAX_COLOSIZE) {
 101     lua_assert((sizeof(GCtab) & 7) == 0);
 102     t = (GCtab *)lj_mem_newgco(L, sizetabcolo(asize));
 103     t->gct = ~LJ_TTAB;
 104     t->nomm = (uint8_t)~0;
 105     t->colo = (int8_t)asize;
 106     setmref(t->array, (TValue *)((char *)t + sizeof(GCtab)));
 107     setgcrefnull(t->metatable);
 108     t->asize = asize;
 109     t->hmask = 0;
 110     setmref(t->node, &G(L)->nilnode);
 111   } else {  /* Otherwise separately allocate the array part. */
 112     t = lj_mem_newobj(L, GCtab);
 113     t->gct = ~LJ_TTAB;
 114     t->nomm = (uint8_t)~0;
 115     t->colo = 0;
 116     setmref(t->array, NULL);
 117     setgcrefnull(t->metatable);
 118     t->asize = 0;  /* In case the array allocation fails. */
 119     t->hmask = 0;
 120     setmref(t->node, &G(L)->nilnode);
 121     if (asize > 0) {
 122       if (asize > LJ_MAX_ASIZE)
 123         lj_err_msg(L, LJ_ERR_TABOV);
 124       setmref(t->array, lj_mem_newvec(L, asize, TValue));
 125       t->asize = asize;
 126     }
 127   }
 128   if (hbits)
 129     newhpart(L, t, hbits);
 130   return t;
 131 }
 132
 133 /* Create a new table.
 134 **
 135 ** IMPORTANT NOTE: The API differs from lua_createtable()!
 136 **
 137 ** The array size is non-inclusive. E.g. asize=128 creates array slots
 138 ** for 0..127, but not for 128. If you need slots 1..128, pass asize=129
 139 ** (slot 0 is wasted in this case).
 140 **
 141 ** The hash size is given in hash bits. hbits=0 means no hash part.
 142 ** hbits=1 creates 2 hash slots, hbits=2 creates 4 hash slots and so on.
 143 */
 144 GCtab *lj_tab_new(lua_State *L, uint32_t asize, uint32_t hbits)
 145 {
 146   GCtab *t = newtab(L, asize, hbits);
 147   clearapart(t);
 148   if (t->hmask > 0) clearhpart(t);
 149   return t;
 150 }
 151
 152 /* The API of this function conforms to lua_createtable(). */
 153 GCtab *lj_tab_new_ah(lua_State *L, int32_t a, int32_t h)
 154 {
 155   return lj_tab_new(L, (uint32_t)(a > 0 ? a+1 : 0), hsize2hbits(h));
 156 }
 157
 158 #if LJ_HASJIT
 159 GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize)
 160 {
 161   GCtab *t = newtab(L, ahsize & 0xffffff, ahsize >> 24);
 162   clearapart(t);
 163   if (t->hmask > 0) clearhpart(t);
 164   return t;
 165 }
 166 #endif
 167
 168 /* Duplicate a table. */
 169 GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
 170 {
 171   GCtab *t;
 172   uint32_t asize, hmask;
 173   t = newtab(L, kt->asize, kt->hmask > 0 ? lj_fls(kt->hmask)+1 : 0);
 174   lua_assert(kt->asize == t->asize && kt->hmask == t->hmask);
 175   t->nomm = 0;  /* Keys with metamethod names may be present. */
 176   asize = kt->asize;
 177   if (asize > 0) {
 178     TValue *array = tvref(t->array);
 179     TValue *karray = tvref(kt->array);
 180     if (asize < 64) {  /* An inlined loop beats memcpy for < 512 bytes. */
 181       uint32_t i;
 182       for (i = 0; i < asize; i++)
 183         copyTV(L, &array[i], &karray[i]);
 184     } else {
 185       memcpy(array, karray, asize*sizeof(TValue));
 186     }
 187   }
 188   hmask = kt->hmask;
 189   if (hmask > 0) {
 190     uint32_t i;
 191     Node *node = noderef(t->node);
 192     Node *knode = noderef(kt->node);
 193     ptrdiff_t d = (char *)node - (char *)knode;
 194     setmref(node->freetop, (Node *)((char *)noderef(knode->freetop) + d));
 195     for (i = 0; i <= hmask; i++) {
 196       Node *kn = &knode[i];
 197       Node *n = &node[i];
 198       Node *next = nextnode(kn);
 199       /* Don't use copyTV here, since it asserts on a copy of a dead key. */
 200       n->val = kn->val; n->key = kn->key;
 201       setmref(n->next, next == NULL? next : (Node *)((char *)next + d));
 202     }
 203   }
 204   return t;
 205 }
 206
 207 /* Clear a table. */
 208 void LJ_FASTCALL lj_tab_clear(GCtab *t)
 209 {
 210   clearapart(t);
 211   if (t->hmask > 0) {
 212     Node *node = noderef(t->node);
 213     setmref(node->freetop, &node[t->hmask+1]);
 214     clearhpart(t);
 215   }
 216 }
 217
 218 /* Free a table. */
 219 void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
 220 {
 221   if (t->hmask > 0)
 222     lj_mem_freevec(g, noderef(t->node), t->hmask+1, Node);
 223   if (t->asize > 0 && LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
 224     lj_mem_freevec(g, tvref(t->array), t->asize, TValue);
 225   if (LJ_MAX_COLOSIZE != 0 && t->colo)
 226     lj_mem_free(g, t, sizetabcolo((uint32_t)t->colo & 0x7f));
 227   else
 228     lj_mem_freet(g, t);
 229 }
 230
 231 /* -- Table resizing ------------------------------------------------------ */
 232
 233 /* Resize a table to fit the new array/hash part sizes. */
 234 static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
 235 {
 236   Node *oldnode = noderef(t->node);
 237   uint32_t oldasize = t->asize;
 238   uint32_t oldhmask = t->hmask;
 239   if (asize > oldasize) {  /* Array part grows? */
 240     TValue *array;
 241     uint32_t i;
 242     if (asize > LJ_MAX_ASIZE)
 243       lj_err_msg(L, LJ_ERR_TABOV);
 244     if (LJ_MAX_COLOSIZE != 0 && t->colo > 0) {
 245       /* A colocated array must be separated and copied. */
 246       TValue *oarray = tvref(t->array);
 247       array = lj_mem_newvec(L, asize, TValue);
 248       t->colo = (int8_t)(t->colo | 0x80);  /* Mark as separated (colo < 0). */
 249       for (i = 0; i < oldasize; i++)
 250         copyTV(L, &array[i], &oarray[i]);
 251     } else {
 252       array = (TValue *)lj_mem_realloc(L, tvref(t->array),
 253                           oldasize*sizeof(TValue), asize*sizeof(TValue));
 254     }
 255     setmref(t->array, array);
 256     t->asize = asize;
 257     for (i = oldasize; i < asize; i++)  /* Clear newly allocated slots. */
 258       setnilV(&array[i]);
 259   }
 260   /* Create new (empty) hash part. */
 261   if (hbits) {
 262     newhpart(L, t, hbits);
 263     clearhpart(t);
 264   } else {
 265     global_State *g = G(L);
 266     setmref(t->node, &g->nilnode);
 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
 294 static uint32_t countint(cTValue *key, uint32_t *bins)
 295 {
 296   lua_assert(!tvisint(key));
 297   if (tvisnum(key)) {
 298     lua_Number nk = numV(key);
 299     int32_t k = lj_num2int(nk);
 300     if ((uint32_t)k < LJ_MAX_ASIZE && nk == (lua_Number)k) {
 301       bins[(k > 2 ? lj_fls((uint32_t)(k-1)) : 0)]++;
 302       return 1;
 303     }
 304   }
 305   return 0;
 306 }
 307
 308 static 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
 330 static 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
 345 static 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
 357 static 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   resizetab(L, t, asize, hsize2hbits(total));
 369 }
 370
 371 #if LJ_HASFFI
 372 void lj_tab_rehash(lua_State *L, GCtab *t)
 373 {
 374   rehashtab(L, t, niltv(L));
 375 }
 376 #endif
 377
 378 void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
 379 {
 380   resizetab(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
 381 }
 382
 383 /* -- Table getters ------------------------------------------------------- */
 384
 385 cTValue * LJ_FASTCALL lj_tab_getinth(GCtab *t, int32_t key)
 386 {
 387   TValue k;
 388   Node *n;
 389   k.n = (lua_Number)key;
 390   n = hashnum(t, &k);
 391   do {
 392     if (tvisnum(&n->key) && n->key.n == k.n)
 393       return &n->val;
 394   } while ((n = nextnode(n)));
 395   return NULL;
 396 }
 397
 398 cTValue *lj_tab_getstr(GCtab *t, GCstr *key)
 399 {
 400   Node *n = hashstr(t, key);
 401   do {
 402     if (tvisstr(&n->key) && strV(&n->key) == key)
 403       return &n->val;
 404   } while ((n = nextnode(n)));
 405   return NULL;
 406 }
 407
 408 cTValue *lj_tab_get(lua_State *L, GCtab *t, cTValue *key)
 409 {
 410   if (tvisstr(key)) {
 411     cTValue *tv = lj_tab_getstr(t, strV(key));
 412     if (tv)
 413       return tv;
 414   } else if (tvisint(key)) {
 415     cTValue *tv = lj_tab_getint(t, intV(key));
 416     if (tv)
 417       return tv;
 418   } else if (tvisnum(key)) {
 419     lua_Number nk = numV(key);
 420     int32_t k = lj_num2int(nk);
 421     if (nk == (lua_Number)k) {
 422       cTValue *tv = lj_tab_getint(t, k);
 423       if (tv)
 424         return tv;
 425     } else {
 426       goto genlookup;  /* Else use the generic lookup. */
 427     }
 428   } else if (!tvisnil(key)) {
 429     Node *n;
 430   genlookup:
 431     n = hashkey(t, key);
 432     do {
 433       if (lj_obj_equal(&n->key, key))
 434         return &n->val;
 435     } while ((n = nextnode(n)));
 436   }
 437   return niltv(L);
 438 }
 439
 440 /* -- Table setters ------------------------------------------------------- */
 441
 442 /* Insert new key. Use Brent's variation to optimize the chain length. */
 443 TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
 444 {
 445   Node *n = hashkey(t, key);
 446   if (!tvisnil(&n->val) || t->hmask == 0) {
 447     Node *nodebase = noderef(t->node);
 448     Node *collide, *freenode = noderef(nodebase->freetop);
 449     lua_assert(freenode >= nodebase && freenode <= nodebase+t->hmask+1);
 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     setmref(nodebase->freetop, freenode);
 457     lua_assert(freenode != &G(L)->nilnode);
 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 (tvisstr(&nn->key) && !tvisnil(&nn->val) &&
 473             hashstr(t, strV(&nn->key)) == n) {
 474           freenode->next = nn->next;
 475           nn->next = n->next;
 476           setmref(n->next, nn);
 477         } else {
 478           freenode = nn;
 479         }
 480       }
 481     } else {  /* Otherwise use free node. */
 482       setmrefr(freenode->next, n->next);  /* Insert into chain. */
 483       setmref(n->next, freenode);
 484       n = freenode;
 485     }
 486   }
 487   n->key.u64 = key->u64;
 488   if (LJ_UNLIKELY(tvismzero(&n->key)))
 489     n->key.u64 = 0;
 490   lj_gc_anybarriert(L, t);
 491   lua_assert(tvisnil(&n->val));
 492   return &n->val;
 493 }
 494
 495 TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)
 496 {
 497   TValue k;
 498   Node *n;
 499   k.n = (lua_Number)key;
 500   n = hashnum(t, &k);
 501   do {
 502     if (tvisnum(&n->key) && n->key.n == k.n)
 503       return &n->val;
 504   } while ((n = nextnode(n)));
 505   return lj_tab_newkey(L, t, &k);
 506 }
 507
 508 TValue *lj_tab_setstr(lua_State *L, GCtab *t, GCstr *key)
 509 {
 510   TValue k;
 511   Node *n = hashstr(t, key);
 512   do {
 513     if (tvisstr(&n->key) && strV(&n->key) == key)
 514       return &n->val;
 515   } while ((n = nextnode(n)));
 516   setstrV(L, &k, key);
 517   return lj_tab_newkey(L, t, &k);
 518 }
 519
 520 TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
 521 {
 522   Node *n;
 523   t->nomm = 0;  /* Invalidate negative metamethod cache. */
 524   if (tvisstr(key)) {
 525     return lj_tab_setstr(L, t, strV(key));
 526   } else if (tvisint(key)) {
 527     return lj_tab_setint(L, t, intV(key));
 528   } else if (tvisnum(key)) {
 529     lua_Number nk = numV(key);
 530     int32_t k = lj_num2int(nk);
 531     if (nk == (lua_Number)k)
 532       return lj_tab_setint(L, t, k);
 533     if (tvisnan(key))
 534       lj_err_msg(L, LJ_ERR_NANIDX);
 535     /* Else use the generic lookup. */
 536   } else if (tvisnil(key)) {
 537     lj_err_msg(L, LJ_ERR_NILIDX);
 538   }
 539   n = hashkey(t, key);
 540   do {
 541     if (lj_obj_equal(&n->key, key))
 542       return &n->val;
 543   } while ((n = nextnode(n)));
 544   return lj_tab_newkey(L, t, key);
 545 }
 546
 547 /* -- Table traversal ----------------------------------------------------- */
 548
 549 /* Get the traversal index of a key. */
 550 static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key)
 551 {
 552   TValue tmp;
 553   if (tvisint(key)) {
 554     int32_t k = intV(key);
 555     if ((uint32_t)k < t->asize)
 556       return (uint32_t)k;  /* Array key indexes: [0..t->asize-1] */
 557     setnumV(&tmp, (lua_Number)k);
 558     key = &tmp;
 559   } else if (tvisnum(key)) {
 560     lua_Number nk = numV(key);
 561     int32_t k = lj_num2int(nk);
 562     if ((uint32_t)k < t->asize && nk == (lua_Number)k)
 563       return (uint32_t)k;  /* Array key indexes: [0..t->asize-1] */
 564   }
 565   if (!tvisnil(key)) {
 566     Node *n = hashkey(t, key);
 567     do {
 568       if (lj_obj_equal(&n->key, key))
 569         return t->asize + (uint32_t)(n - noderef(t->node));
 570         /* Hash key indexes: [t->asize..t->asize+t->nmask] */
 571     } while ((n = nextnode(n)));
 572     if (key->u32.hi == 0xfffe7fff)  /* ITERN was despecialized while running. */
 573       return key->u32.lo - 1;
 574     lj_err_msg(L, LJ_ERR_NEXTIDX);
 575     return 0;  /* unreachable */
 576   }
 577   return ~0u;  /* A nil key starts the traversal. */
 578 }
 579
 580 /* Advance to the next step in a table traversal. */
 581 int lj_tab_next(lua_State *L, GCtab *t, TValue *key)
 582 {
 583   uint32_t i = keyindex(L, t, key);  /* Find predecessor key index. */
 584   for (i++; i < t->asize; i++)  /* First traverse the array keys. */
 585     if (!tvisnil(arrayslot(t, i))) {
 586       setintV(key, i);
 587       copyTV(L, key+1, arrayslot(t, i));
 588       return 1;
 589     }
 590   for (i -= t->asize; i <= t->hmask; i++) {  /* Then traverse the hash keys. */
 591     Node *n = &noderef(t->node)[i];
 592     if (!tvisnil(&n->val)) {
 593       copyTV(L, key, &n->key);
 594       copyTV(L, key+1, &n->val);
 595       return 1;
 596     }
 597   }
 598   return 0;  /* End of traversal. */
 599 }
 600
 601 /* -- Table length calculation -------------------------------------------- */
 602
 603 static MSize unbound_search(GCtab *t, MSize j)
 604 {
 605   cTValue *tv;
 606   MSize i = j;  /* i is zero or a present index */
 607   j++;
 608   /* find `i' and `j' such that i is present and j is not */
 609   while ((tv = lj_tab_getint(t, (int32_t)j)) && !tvisnil(tv)) {
 610     i = j;
 611     j *= 2;
 612     if (j > (MSize)(INT_MAX-2)) {  /* overflow? */
 613       /* table was built with bad purposes: resort to linear search */
 614       i = 1;
 615       while ((tv = lj_tab_getint(t, (int32_t)i)) && !tvisnil(tv)) i++;
 616       return i - 1;
 617     }
 618   }
 619   /* now do a binary search between them */
 620   while (j - i > 1) {
 621     MSize m = (i+j)/2;
 622     cTValue *tvb = lj_tab_getint(t, (int32_t)m);
 623     if (tvb && !tvisnil(tvb)) i = m; else j = m;
 624   }
 625   return i;
 626 }
 627
 628 /*
 629 ** Try to find a boundary in table `t'. A `boundary' is an integer index
 630 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
 631 */
 632 MSize LJ_FASTCALL lj_tab_len(GCtab *t)
 633 {
 634   MSize j = (MSize)t->asize;
 635   if (j > 1 && tvisnil(arrayslot(t, j-1))) {
 636     MSize i = 1;
 637     while (j - i > 1) {
 638       MSize m = (i+j)/2;
 639       if (tvisnil(arrayslot(t, m-1))) j = m; else i = m;
 640     }
 641     return i-1;
 642   }
 643   if (j) j--;
 644   if (t->hmask <= 0)
 645     return j;
 646   return unbound_search(t, j);
 647 }
 648