root/lj_tab.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. hashmask
  2. hashkey
  3. newhpart
  4. clearhpart
  5. clearapart
  6. newtab
  7. lj_tab_new
  8. lj_tab_new_ah
  9. lj_tab_new1
  10. lj_tab_dup
  11. lj_tab_clear
  12. lj_tab_free
  13. lj_tab_resize
  14. countint
  15. countarray
  16. counthash
  17. bestasize
  18. rehashtab
  19. lj_tab_rehash
  20. lj_tab_reasize
  21. lj_tab_getinth
  22. lj_tab_getstr
  23. lj_tab_get
  24. lj_tab_newkey
  25. lj_tab_setinth
  26. lj_tab_setstr
  27. lj_tab_set
  28. keyindex
  29. lj_tab_next
  30. unbound_search
  31. lj_tab_len

   1 /*
   2 ** Table handling.
   3 ** Copyright (C) 2005-2017 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 #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. */
  39 static Node *hashkey(const GCtab *t, cTValue *key)
  40 {
  41   lua_assert(!tvisint(key));
  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. */
  56 static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
  57 {
  58   uint32_t hsize;
  59   Node *node;
  60   lua_assert(hbits != 0);
  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. */
  77 static LJ_AINLINE void clearhpart(GCtab *t)
  78 {
  79   uint32_t i, hmask = t->hmask;
  80   Node *node = noderef(t->node);
  81   lua_assert(t->hmask != 0);
  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. */
  91 static 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). */
 100 static 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     lua_assert((sizeof(GCtab) & 7) == 0);
 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 */
 158 GCtab *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(). */
 167 GCtab *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
 173 GCtab * 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. */
 183 GCtab * 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   lua_assert(kt->asize == t->asize && kt->hmask == t->hmask);
 189   t->nomm = 0;  /* Keys with metamethod names may be present. */
 190   asize = kt->asize;
 191   if (asize > 0) {
 192     TValue *array = tvref(t->array);
 193     TValue *karray = tvref(kt->array);
 194     if (asize < 64) {  /* An inlined loop beats memcpy for < 512 bytes. */
 195       uint32_t i;
 196       for (i = 0; i < asize; i++)
 197         copyTV(L, &array[i], &karray[i]);
 198     } else {
 199       memcpy(array, karray, asize*sizeof(TValue));
 200     }
 201   }
 202   hmask = kt->hmask;
 203   if (hmask > 0) {
 204     uint32_t i;
 205     Node *node = noderef(t->node);
 206     Node *knode = noderef(kt->node);
 207     ptrdiff_t d = (char *)node - (char *)knode;
 208     setfreetop(t, node, (Node *)((char *)getfreetop(kt, knode) + d));
 209     for (i = 0; i <= hmask; i++) {
 210       Node *kn = &knode[i];
 211       Node *n = &node[i];
 212       Node *next = nextnode(kn);
 213       /* Don't use copyTV here, since it asserts on a copy of a dead key. */
 214       n->val = kn->val; n->key = kn->key;
 215       setmref(n->next, next == NULL? next : (Node *)((char *)next + d));
 216     }
 217   }
 218   return t;
 219 }
 220 
 221 /* Clear a table. */
 222 void LJ_FASTCALL lj_tab_clear(GCtab *t)
 223 {
 224   clearapart(t);
 225   if (t->hmask > 0) {
 226     Node *node = noderef(t->node);
 227     setfreetop(t, node, &node[t->hmask+1]);
 228     clearhpart(t);
 229   }
 230 }
 231 
 232 /* Free a table. */
 233 void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
 234 {
 235   if (t->hmask > 0)
 236     lj_mem_freevec(g, noderef(t->node), t->hmask+1, Node);
 237   if (t->asize > 0 && LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
 238     lj_mem_freevec(g, tvref(t->array), t->asize, TValue);
 239   if (LJ_MAX_COLOSIZE != 0 && t->colo)
 240     lj_mem_free(g, t, sizetabcolo((uint32_t)t->colo & 0x7f));
 241   else
 242     lj_mem_freet(g, t);
 243 }
 244 
 245 /* -- Table resizing ------------------------------------------------------ */
 246 
 247 /* Resize a table to fit the new array/hash part sizes. */
 248 void lj_tab_resize(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
 249 {
 250   Node *oldnode = noderef(t->node);
 251   uint32_t oldasize = t->asize;
 252   uint32_t oldhmask = t->hmask;
 253   if (asize > oldasize) {  /* Array part grows? */
 254     TValue *array;
 255     uint32_t i;
 256     if (asize > LJ_MAX_ASIZE)
 257       lj_err_msg(L, LJ_ERR_TABOV);
 258     if (LJ_MAX_COLOSIZE != 0 && t->colo > 0) {
 259       /* A colocated array must be separated and copied. */
 260       TValue *oarray = tvref(t->array);
 261       array = lj_mem_newvec(L, asize, TValue);
 262       t->colo = (int8_t)(t->colo | 0x80);  /* Mark as separated (colo < 0). */
 263       for (i = 0; i < oldasize; i++)
 264         copyTV(L, &array[i], &oarray[i]);
 265     } else {
 266       array = (TValue *)lj_mem_realloc(L, tvref(t->array),
 267                           oldasize*sizeof(TValue), asize*sizeof(TValue));
 268     }
 269     setmref(t->array, array);
 270     t->asize = asize;
 271     for (i = oldasize; i < asize; i++)  /* Clear newly allocated slots. */
 272       setnilV(&array[i]);
 273   }
 274   /* Create new (empty) hash part. */
 275   if (hbits) {
 276     newhpart(L, t, hbits);
 277     clearhpart(t);
 278   } else {
 279     global_State *g = G(L);
 280     setmref(t->node, &g->nilnode);
 281 #if LJ_GC64
 282     setmref(t->freetop, &g->nilnode);
 283 #endif
 284     t->hmask = 0;
 285   }
 286   if (asize < oldasize) {  /* Array part shrinks? */
 287     TValue *array = tvref(t->array);
 288     uint32_t i;
 289     t->asize = asize;  /* Note: This 'shrinks' even colocated arrays. */
 290     for (i = asize; i < oldasize; i++)  /* Reinsert old array values. */
 291       if (!tvisnil(&array[i]))
 292         copyTV(L, lj_tab_setinth(L, t, (int32_t)i), &array[i]);
 293     /* Physically shrink only separated arrays. */
 294     if (LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
 295       setmref(t->array, lj_mem_realloc(L, array,
 296               oldasize*sizeof(TValue), asize*sizeof(TValue)));
 297   }
 298   if (oldhmask > 0) {  /* Reinsert pairs from old hash part. */
 299     global_State *g;
 300     uint32_t i;
 301     for (i = 0; i <= oldhmask; i++) {
 302       Node *n = &oldnode[i];
 303       if (!tvisnil(&n->val))
 304         copyTV(L, lj_tab_set(L, t, &n->key), &n->val);
 305     }
 306     g = G(L);
 307     lj_mem_freevec(g, oldnode, oldhmask+1, Node);
 308   }
 309 }
 310 
 311 static uint32_t countint(cTValue *key, uint32_t *bins)
 312 {
 313   lua_assert(!tvisint(key));
 314   if (tvisnum(key)) {
 315     lua_Number nk = numV(key);
 316     int32_t k = lj_num2int(nk);
 317     if ((uint32_t)k < LJ_MAX_ASIZE && nk == (lua_Number)k) {
 318       bins[(k > 2 ? lj_fls((uint32_t)(k-1)) : 0)]++;
 319       return 1;
 320     }
 321   }
 322   return 0;
 323 }
 324 
 325 static uint32_t countarray(const GCtab *t, uint32_t *bins)
 326 {
 327   uint32_t na, b, i;
 328   if (t->asize == 0) return 0;
 329   for (na = i = b = 0; b < LJ_MAX_ABITS; b++) {
 330     uint32_t n, top = 2u << b;
 331     TValue *array;
 332     if (top >= t->asize) {
 333       top = t->asize-1;
 334       if (i > top)
 335         break;
 336     }
 337     array = tvref(t->array);
 338     for (n = 0; i <= top; i++)
 339       if (!tvisnil(&array[i]))
 340         n++;
 341     bins[b] += n;
 342     na += n;
 343   }
 344   return na;
 345 }
 346 
 347 static uint32_t counthash(const GCtab *t, uint32_t *bins, uint32_t *narray)
 348 {
 349   uint32_t total, na, i, hmask = t->hmask;
 350   Node *node = noderef(t->node);
 351   for (total = na = 0, i = 0; i <= hmask; i++) {
 352     Node *n = &node[i];
 353     if (!tvisnil(&n->val)) {
 354       na += countint(&n->key, bins);
 355       total++;
 356     }
 357   }
 358   *narray += na;
 359   return total;
 360 }
 361 
 362 static uint32_t bestasize(uint32_t bins[], uint32_t *narray)
 363 {
 364   uint32_t b, sum, na = 0, sz = 0, nn = *narray;
 365   for (b = 0, sum = 0; 2*nn > (1u<<b) && sum != nn; b++)
 366     if (bins[b] > 0 && 2*(sum += bins[b]) > (1u<<b)) {
 367       sz = (2u<<b)+1;
 368       na = sum;
 369     }
 370   *narray = sz;
 371   return na;
 372 }
 373 
 374 static void rehashtab(lua_State *L, GCtab *t, cTValue *ek)
 375 {
 376   uint32_t bins[LJ_MAX_ABITS];
 377   uint32_t total, asize, na, i;
 378   for (i = 0; i < LJ_MAX_ABITS; i++) bins[i] = 0;
 379   asize = countarray(t, bins);
 380   total = 1 + asize;
 381   total += counthash(t, bins, &asize);
 382   asize += countint(ek, bins);
 383   na = bestasize(bins, &asize);
 384   total -= na;
 385   lj_tab_resize(L, t, asize, hsize2hbits(total));
 386 }
 387 
 388 #if LJ_HASFFI
 389 void lj_tab_rehash(lua_State *L, GCtab *t)
 390 {
 391   rehashtab(L, t, niltv(L));
 392 }
 393 #endif
 394 
 395 void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
 396 {
 397   lj_tab_resize(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
 398 }
 399 
 400 /* -- Table getters ------------------------------------------------------- */
 401 
 402 cTValue * LJ_FASTCALL lj_tab_getinth(GCtab *t, int32_t key)
 403 {
 404   TValue k;
 405   Node *n;
 406   k.n = (lua_Number)key;
 407   n = hashnum(t, &k);
 408   do {
 409     if (tvisnum(&n->key) && n->key.n == k.n)
 410       return &n->val;
 411   } while ((n = nextnode(n)));
 412   return NULL;
 413 }
 414 
 415 cTValue *lj_tab_getstr(GCtab *t, GCstr *key)
 416 {
 417   Node *n = hashstr(t, key);
 418   do {
 419     if (tvisstr(&n->key) && strV(&n->key) == key)
 420       return &n->val;
 421   } while ((n = nextnode(n)));
 422   return NULL;
 423 }
 424 
 425 cTValue *lj_tab_get(lua_State *L, GCtab *t, cTValue *key)
 426 {
 427   if (tvisstr(key)) {
 428     cTValue *tv = lj_tab_getstr(t, strV(key));
 429     if (tv)
 430       return tv;
 431   } else if (tvisint(key)) {
 432     cTValue *tv = lj_tab_getint(t, intV(key));
 433     if (tv)
 434       return tv;
 435   } else if (tvisnum(key)) {
 436     lua_Number nk = numV(key);
 437     int32_t k = lj_num2int(nk);
 438     if (nk == (lua_Number)k) {
 439       cTValue *tv = lj_tab_getint(t, k);
 440       if (tv)
 441         return tv;
 442     } else {
 443       goto genlookup;  /* Else use the generic lookup. */
 444     }
 445   } else if (!tvisnil(key)) {
 446     Node *n;
 447   genlookup:
 448     n = hashkey(t, key);
 449     do {
 450       if (lj_obj_equal(&n->key, key))
 451         return &n->val;
 452     } while ((n = nextnode(n)));
 453   }
 454   return niltv(L);
 455 }
 456 
 457 /* -- Table setters ------------------------------------------------------- */
 458 
 459 /* Insert new key. Use Brent's variation to optimize the chain length. */
 460 TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
 461 {
 462   Node *n = hashkey(t, key);
 463   if (!tvisnil(&n->val) || t->hmask == 0) {
 464     Node *nodebase = noderef(t->node);
 465     Node *collide, *freenode = getfreetop(t, nodebase);
 466     lua_assert(freenode >= nodebase && freenode <= nodebase+t->hmask+1);
 467     do {
 468       if (freenode == nodebase) {  /* No free node found? */
 469         rehashtab(L, t, key);  /* Rehash table. */
 470         return lj_tab_set(L, t, key);  /* Retry key insertion. */
 471       }
 472     } while (!tvisnil(&(--freenode)->key));
 473     setfreetop(t, nodebase, freenode);
 474     lua_assert(freenode != &G(L)->nilnode);
 475     collide = hashkey(t, &n->key);
 476     if (collide != n) {  /* Colliding node not the main node? */
 477       while (noderef(collide->next) != n)  /* Find predecessor. */
 478         collide = nextnode(collide);
 479       setmref(collide->next, freenode);  /* Relink chain. */
 480       /* Copy colliding node into free node and free main node. */
 481       freenode->val = n->val;
 482       freenode->key = n->key;
 483       freenode->next = n->next;
 484       setmref(n->next, NULL);
 485       setnilV(&n->val);
 486       /* Rechain pseudo-resurrected string keys with colliding hashes. */
 487       while (nextnode(freenode)) {
 488         Node *nn = nextnode(freenode);
 489         if (tvisstr(&nn->key) && !tvisnil(&nn->val) &&
 490             hashstr(t, strV(&nn->key)) == n) {
 491           freenode->next = nn->next;
 492           nn->next = n->next;
 493           setmref(n->next, nn);
 494         } else {
 495           freenode = nn;
 496         }
 497       }
 498     } else {  /* Otherwise use free node. */
 499       setmrefr(freenode->next, n->next);  /* Insert into chain. */
 500       setmref(n->next, freenode);
 501       n = freenode;
 502     }
 503   }
 504   n->key.u64 = key->u64;
 505   if (LJ_UNLIKELY(tvismzero(&n->key)))
 506     n->key.u64 = 0;
 507   lj_gc_anybarriert(L, t);
 508   lua_assert(tvisnil(&n->val));
 509   return &n->val;
 510 }
 511 
 512 TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)
 513 {
 514   TValue k;
 515   Node *n;
 516   k.n = (lua_Number)key;
 517   n = hashnum(t, &k);
 518   do {
 519     if (tvisnum(&n->key) && n->key.n == k.n)
 520       return &n->val;
 521   } while ((n = nextnode(n)));
 522   return lj_tab_newkey(L, t, &k);
 523 }
 524 
 525 TValue *lj_tab_setstr(lua_State *L, GCtab *t, GCstr *key)
 526 {
 527   TValue k;
 528   Node *n = hashstr(t, key);
 529   do {
 530     if (tvisstr(&n->key) && strV(&n->key) == key)
 531       return &n->val;
 532   } while ((n = nextnode(n)));
 533   setstrV(L, &k, key);
 534   return lj_tab_newkey(L, t, &k);
 535 }
 536 
 537 TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
 538 {
 539   Node *n;
 540   t->nomm = 0;  /* Invalidate negative metamethod cache. */
 541   if (tvisstr(key)) {
 542     return lj_tab_setstr(L, t, strV(key));
 543   } else if (tvisint(key)) {
 544     return lj_tab_setint(L, t, intV(key));
 545   } else if (tvisnum(key)) {
 546     lua_Number nk = numV(key);
 547     int32_t k = lj_num2int(nk);
 548     if (nk == (lua_Number)k)
 549       return lj_tab_setint(L, t, k);
 550     if (tvisnan(key))
 551       lj_err_msg(L, LJ_ERR_NANIDX);
 552     /* Else use the generic lookup. */
 553   } else if (tvisnil(key)) {
 554     lj_err_msg(L, LJ_ERR_NILIDX);
 555   }
 556   n = hashkey(t, key);
 557   do {
 558     if (lj_obj_equal(&n->key, key))
 559       return &n->val;
 560   } while ((n = nextnode(n)));
 561   return lj_tab_newkey(L, t, key);
 562 }
 563 
 564 /* -- Table traversal ----------------------------------------------------- */
 565 
 566 /* Get the traversal index of a key. */
 567 static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key)
 568 {
 569   TValue tmp;
 570   if (tvisint(key)) {
 571     int32_t k = intV(key);
 572     if ((uint32_t)k < t->asize)
 573       return (uint32_t)k;  /* Array key indexes: [0..t->asize-1] */
 574     setnumV(&tmp, (lua_Number)k);
 575     key = &tmp;
 576   } else if (tvisnum(key)) {
 577     lua_Number nk = numV(key);
 578     int32_t k = lj_num2int(nk);
 579     if ((uint32_t)k < t->asize && nk == (lua_Number)k)
 580       return (uint32_t)k;  /* Array key indexes: [0..t->asize-1] */
 581   }
 582   if (!tvisnil(key)) {
 583     Node *n = hashkey(t, key);
 584     do {
 585       if (lj_obj_equal(&n->key, key))
 586         return t->asize + (uint32_t)(n - noderef(t->node));
 587         /* Hash key indexes: [t->asize..t->asize+t->nmask] */
 588     } while ((n = nextnode(n)));
 589     if (key->u32.hi == 0xfffe7fff)  /* ITERN was despecialized while running. */
 590       return key->u32.lo - 1;
 591     lj_err_msg(L, LJ_ERR_NEXTIDX);
 592     return 0;  /* unreachable */
 593   }
 594   return ~0u;  /* A nil key starts the traversal. */
 595 }
 596 
 597 /* Advance to the next step in a table traversal. */
 598 int lj_tab_next(lua_State *L, GCtab *t, TValue *key)
 599 {
 600   uint32_t i = keyindex(L, t, key);  /* Find predecessor key index. */
 601   for (i++; i < t->asize; i++)  /* First traverse the array keys. */
 602     if (!tvisnil(arrayslot(t, i))) {
 603       setintV(key, i);
 604       copyTV(L, key+1, arrayslot(t, i));
 605       return 1;
 606     }
 607   for (i -= t->asize; i <= t->hmask; i++) {  /* Then traverse the hash keys. */
 608     Node *n = &noderef(t->node)[i];
 609     if (!tvisnil(&n->val)) {
 610       copyTV(L, key, &n->key);
 611       copyTV(L, key+1, &n->val);
 612       return 1;
 613     }
 614   }
 615   return 0;  /* End of traversal. */
 616 }
 617 
 618 /* -- Table length calculation -------------------------------------------- */
 619 
 620 static MSize unbound_search(GCtab *t, MSize j)
 621 {
 622   cTValue *tv;
 623   MSize i = j;  /* i is zero or a present index */
 624   j++;
 625   /* find `i' and `j' such that i is present and j is not */
 626   while ((tv = lj_tab_getint(t, (int32_t)j)) && !tvisnil(tv)) {
 627     i = j;
 628     j *= 2;
 629     if (j > (MSize)(INT_MAX-2)) {  /* overflow? */
 630       /* table was built with bad purposes: resort to linear search */
 631       i = 1;
 632       while ((tv = lj_tab_getint(t, (int32_t)i)) && !tvisnil(tv)) i++;
 633       return i - 1;
 634     }
 635   }
 636   /* now do a binary search between them */
 637   while (j - i > 1) {
 638     MSize m = (i+j)/2;
 639     cTValue *tvb = lj_tab_getint(t, (int32_t)m);
 640     if (tvb && !tvisnil(tvb)) i = m; else j = m;
 641   }
 642   return i;
 643 }
 644 
 645 /*
 646 ** Try to find a boundary in table `t'. A `boundary' is an integer index
 647 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
 648 */
 649 MSize LJ_FASTCALL lj_tab_len(GCtab *t)
 650 {
 651   MSize j = (MSize)t->asize;
 652   if (j > 1 && tvisnil(arrayslot(t, j-1))) {
 653     MSize i = 1;
 654     while (j - i > 1) {
 655       MSize m = (i+j)/2;
 656       if (tvisnil(arrayslot(t, m-1))) j = m; else i = m;
 657     }
 658     return i-1;
 659   }
 660   if (j) j--;
 661   if (t->hmask <= 0)
 662     return j;
 663   return unbound_search(t, j);
 664 }
 665 

/* [<][>][^][v][top][bottom][index][help] */