One Level Up Top Level

src/lj_tab.c - luajit-2.0-src

Functions defined

Macros defined

Source code

  1. /*
  2. ** Table handling.
  3. ** Copyright (C) 2005-2015 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. */

  9. ‌#define lj_tab_c
  10. ‌#define LUA_CORE

  12. #include "lj_obj.h"
  13. #include "lj_gc.h"
  14. #include "lj_err.h"
  15. #include "lj_tab.h"

  17. /* -- Object hashing ------------------------------------------------------ */

  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. }

  26. /* String hashes are precomputed when they are interned. */
  27. ‌#define hashstr(t, s)                hashmask(t, (s)->hash)

  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. #if LJ_GC64
  33. ‌#define hashgcref(t, r) \
  34.   hashlohi((t), (uint32_t)gcrefu(r), (uint32_t)(gcrefu(r) >> 32))
  35. #else
  36. ‌#define hashgcref(t, r)                hashlohi((t), gcrefu(r), gcrefu(r) + HASH_BIAS)
  37. #endif

  39. /* Hash an arbitrary key and return its anchor position in the hash table. */
  40. ‌static Node *hashkey(const GCtab *t, cTValue *key)
  41. {
  42.   lua_assert(!tvisint(key));
  43.   if (tvisstr(key))
  44.     return hashstr(t, strV(key));
  45.   else if (tvisnum(key))
  46.     return hashnum(t, key);
  47.   else if (tvisbool(key))
  48.     return hashmask(t, boolV(key));
  49.   else
  50.     return hashgcref(t, key->gcr);
  51.   /* Only hash 32 bits of lightuserdata on a 64 bit CPU. Good enough? */
  52. }

  54. /* -- Table creation and destruction -------------------------------------- */

  56. /* Create new hash part for table. */
  57. ‌static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
  58. {
  59.   uint32_t hsize;
  60.   Node *node;
  61.   lua_assert(hbits != 0);
  62.   if (hbits > LJ_MAX_HBITS)
  63.     lj_err_msg(L, LJ_ERR_TABOV);
  64.   hsize = 1u << hbits;
  65.   node = lj_mem_newvec(L, hsize, Node);
  66.   setmref(t->node, node);
  67.   setfreetop(t, node, &node[hsize]);
  68.   t->hmask = hsize-1;
  69. }

  71. /*
  72. ** Q: Why all of these copies of t->hmask, t->node etc. to local variables?
  73. ** A: Because alias analysis for C is _really_ tough.
  74. **    Even state-of-the-art C compilers won't produce good code without this.
  75. */

  77. /* Clear hash part of table. */
  78. ‌static LJ_AINLINE void clearhpart(GCtab *t)
  79. {
  80.   uint32_t i, hmask = t->hmask;
  81.   Node *node = noderef(t->node);
  82.   lua_assert(t->hmask != 0);
  83.   for (i = 0; i <= hmask; i++) {
  84.     Node *n = &node[i];
  85.     setmref(n->next, NULL);
  86.     setnilV(&n->key);
  87.     setnilV(&n->val);
  88.   }
  89. }

  91. /* Clear array part of table. */
  92. ‌static LJ_AINLINE void clearapart(GCtab *t)
  93. {
  94.   uint32_t i, asize = t->asize;
  95.   TValue *array = tvref(t->array);
  96.   for (i = 0; i < asize; i++)
  97.     setnilV(&array[i]);
  98. }

  100. /* Create a new table. Note: the slots are not initialized (yet). */
  101. ‌static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
  102. {
  103.   GCtab *t;
  104.   /* First try to colocate the array part. */
  105.   if (LJ_MAX_COLOSIZE != 0 && asize > 0 && asize <= LJ_MAX_COLOSIZE) {
  106.     Node *nilnode;
  107.     lua_assert((sizeof(GCtab) & 7) == 0);
  108.     t = (GCtab *)lj_mem_newgco(L, sizetabcolo(asize));
  109.     t->gct = ~LJ_TTAB;
  110.     t->nomm = (uint8_t)~0;
  111.     t->colo = (int8_t)asize;
  112.     setmref(t->array, (TValue *)((char *)t + sizeof(GCtab)));
  113.     setgcrefnull(t->metatable);
  114.     t->asize = asize;
  115.     t->hmask = 0;
  116.     nilnode = &G(L)->nilnode;
  117.     setmref(t->node, nilnode);
  118. #if LJ_GC64
  119.     setmref(t->freetop, nilnode);
  120. #endif
  121.   } else {  /* Otherwise separately allocate the array part. */
  122.     Node *nilnode;
  123.     t = lj_mem_newobj(L, GCtab);
  124.     t->gct = ~LJ_TTAB;
  125.     t->nomm = (uint8_t)~0;
  126.     t->colo = 0;
  127.     setmref(t->array, NULL);
  128.     setgcrefnull(t->metatable);
  129.     t->asize = 0;  /* In case the array allocation fails. */
  130.     t->hmask = 0;
  131.     nilnode = &G(L)->nilnode;
  132.     setmref(t->node, nilnode);
  133. #if LJ_GC64
  134.     setmref(t->freetop, nilnode);
  135. #endif
  136.     if (asize > 0) {
  137.       if (asize > LJ_MAX_ASIZE)
  138.         lj_err_msg(L, LJ_ERR_TABOV);
  139.       setmref(t->array, lj_mem_newvec(L, asize, TValue));
  140.       t->asize = asize;
  141.     }
  142.   }
  143.   if (hbits)
  144.     newhpart(L, t, hbits);
  145.   return t;
  146. }

  148. /* Create a new table.
  149. **
  150. ** IMPORTANT NOTE: The API differs from lua_createtable()!
  151. **
  152. ** The array size is non-inclusive. E.g. asize=128 creates array slots
  153. ** for 0..127, but not for 128. If you need slots 1..128, pass asize=129
  154. ** (slot 0 is wasted in this case).
  155. **
  156. ** The hash size is given in hash bits. hbits=0 means no hash part.
  157. ** hbits=1 creates 2 hash slots, hbits=2 creates 4 hash slots and so on.
  158. */
  159. ‌GCtab *lj_tab_new(lua_State *L, uint32_t asize, uint32_t hbits)
  160. {
  161.   GCtab *t = newtab(L, asize, hbits);
  162.   clearapart(t);
  163.   if (t->hmask > 0) clearhpart(t);
  164.   return t;
  165. }

  167. /* The API of this function conforms to lua_createtable(). */
  168. ‌GCtab *lj_tab_new_ah(lua_State *L, int32_t a, int32_t h)
  169. {
  170.   return lj_tab_new(L, (uint32_t)(a > 0 ? a+1 : 0), hsize2hbits(h));
  171. }

  173. #if LJ_HASJIT
  174. ‌GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize)
  175. {
  176.   GCtab *t = newtab(L, ahsize & 0xffffff, ahsize >> 24);
  177.   clearapart(t);
  178.   if (t->hmask > 0) clearhpart(t);
  179.   return t;
  180. }
  181. #endif

  183. /* Duplicate a table. */
  184. ‌GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
  185. {
  186.   GCtab *t;
  187.   uint32_t asize, hmask;
  188.   t = newtab(L, kt->asize, kt->hmask > 0 ? lj_fls(kt->hmask)+1 : 0);
  189.   lua_assert(kt->asize == t->asize && kt->hmask == t->hmask);
  190.   t->nomm = 0;  /* Keys with metamethod names may be present. */
  191.   asize = kt->asize;
  192.   if (asize > 0) {
  193.     TValue *array = tvref(t->array);
  194.     TValue *karray = tvref(kt->array);
  195.     if (asize < 64) {  /* An inlined loop beats memcpy for < 512 bytes. */
  196.       uint32_t i;
  197.       for (i = 0; i < asize; i++)
  198.         copyTV(L, &array[i], &karray[i]);
  199.     } else {
  200.       memcpy(array, karray, asize*sizeof(TValue));
  201.     }
  202.   }
  203.   hmask = kt->hmask;
  204.   if (hmask > 0) {
  205.     uint32_t i;
  206.     Node *node = noderef(t->node);
  207.     Node *knode = noderef(kt->node);
  208.     ptrdiff_t d = (char *)node - (char *)knode;
  209.     setfreetop(t, node, (Node *)((char *)getfreetop(kt, knode) + d));
  210.     for (i = 0; i <= hmask; i++) {
  211.       Node *kn = &knode[i];
  212.       Node *n = &node[i];
  213.       Node *next = nextnode(kn);
  214.       /* Don't use copyTV here, since it asserts on a copy of a dead key. */
  215.       n->val = kn->val; n->key = kn->key;
  216.       setmref(n->next, next == NULL? next : (Node *)((char *)next + d));
  217.     }
  218.   }
  219.   return t;
  220. }

  222. /* Clear a table. */
  223. ‌void LJ_FASTCALL lj_tab_clear(GCtab *t)
  224. {
  225.   clearapart(t);
  226.   if (t->hmask > 0) {
  227.     Node *node = noderef(t->node);
  228.     setfreetop(t, node, &node[t->hmask+1]);
  229.     clearhpart(t);
  230.   }
  231. }

  233. /* Free a table. */
  234. ‌void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
  235. {
  236.   if (t->hmask > 0)
  237.     lj_mem_freevec(g, noderef(t->node), t->hmask+1, Node);
  238.   if (t->asize > 0 && LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
  239.     lj_mem_freevec(g, tvref(t->array), t->asize, TValue);
  240.   if (LJ_MAX_COLOSIZE != 0 && t->colo)
  241.     lj_mem_free(g, t, sizetabcolo((uint32_t)t->colo & 0x7f));
  242.   else
  243.     lj_mem_freet(g, t);
  244. }

  246. /* -- Table resizing ------------------------------------------------------ */

  248. /* Resize a table to fit the new array/hash part sizes. */
  249. ‌static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
  250. {
  251.   Node *oldnode = noderef(t->node);
  252.   uint32_t oldasize = t->asize;
  253.   uint32_t oldhmask = t->hmask;
  254.   if (asize > oldasize) {  /* Array part grows? */
  255.     TValue *array;
  256.     uint32_t i;
  257.     if (asize > LJ_MAX_ASIZE)
  258.       lj_err_msg(L, LJ_ERR_TABOV);
  259.     if (LJ_MAX_COLOSIZE != 0 && t->colo > 0) {
  260.       /* A colocated array must be separated and copied. */
  261.       TValue *oarray = tvref(t->array);
  262.       array = lj_mem_newvec(L, asize, TValue);
  263.       t->colo = (int8_t)(t->colo | 0x80);  /* Mark as separated (colo < 0). */
  264.       for (i = 0; i < oldasize; i++)
  265.         copyTV(L, &array[i], &oarray[i]);
  266.     } else {
  267.       array = (TValue *)lj_mem_realloc(L, tvref(t->array),
  268.                           oldasize*sizeof(TValue), asize*sizeof(TValue));
  269.     }
  270.     setmref(t->array, array);
  271.     t->asize = asize;
  272.     for (i = oldasize; i < asize; i++)  /* Clear newly allocated slots. */
  273.       setnilV(&array[i]);
  274.   }
  275.   /* Create new (empty) hash part. */
  276.   if (hbits) {
  277.     newhpart(L, t, hbits);
  278.     clearhpart(t);
  279.   } else {
  280.     global_State *g = G(L);
  281.     setmref(t->node, &g->nilnode);
  282. #if LJ_GC64
  283.     setmref(t->freetop, &g->nilnode);
  284. #endif
  285.     t->hmask = 0;
  286.   }
  287.   if (asize < oldasize) {  /* Array part shrinks? */
  288.     TValue *array = tvref(t->array);
  289.     uint32_t i;
  290.     t->asize = asize;  /* Note: This 'shrinks' even colocated arrays. */
  291.     for (i = asize; i < oldasize; i++)  /* Reinsert old array values. */
  292.       if (!tvisnil(&array[i]))
  293.         copyTV(L, lj_tab_setinth(L, t, (int32_t)i), &array[i]);
  294.     /* Physically shrink only separated arrays. */
  295.     if (LJ_MAX_COLOSIZE != 0 && t->colo <= 0)
  296.       setmref(t->array, lj_mem_realloc(L, array,
  297.               oldasize*sizeof(TValue), asize*sizeof(TValue)));
  298.   }
  299.   if (oldhmask > 0) {  /* Reinsert pairs from old hash part. */
  300.     global_State *g;
  301.     uint32_t i;
  302.     for (i = 0; i <= oldhmask; i++) {
  303.       Node *n = &oldnode[i];
  304.       if (!tvisnil(&n->val))
  305.         copyTV(L, lj_tab_set(L, t, &n->key), &n->val);
  306.     }
  307.     g = G(L);
  308.     lj_mem_freevec(g, oldnode, oldhmask+1, Node);
  309.   }
  310. }

  312. ‌static uint32_t countint(cTValue *key, uint32_t *bins)
  313. {
  314.   lua_assert(!tvisint(key));
  315.   if (tvisnum(key)) {
  316.     lua_Number nk = numV(key);
  317.     int32_t k = lj_num2int(nk);
  318.     if ((uint32_t)k < LJ_MAX_ASIZE && nk == (lua_Number)k) {
  319.       bins[(k > 2 ? lj_fls((uint32_t)(k-1)) : 0)]++;
  320.       return 1;
  321.     }
  322.   }
  323.   return 0;
  324. }

  326. ‌static uint32_t countarray(const GCtab *t, uint32_t *bins)
  327. {
  328.   uint32_t na, b, i;
  329.   if (t->asize == 0) return 0;
  330.   for (na = i = b = 0; b < LJ_MAX_ABITS; b++) {
  331.     uint32_t n, top = 2u << b;
  332.     TValue *array;
  333.     if (top >= t->asize) {
  334.       top = t->asize-1;
  335.       if (i > top)
  336.         break;
  337.     }
  338.     array = tvref(t->array);
  339.     for (n = 0; i <= top; i++)
  340.       if (!tvisnil(&array[i]))
  341.         n++;
  342.     bins[b] += n;
  343.     na += n;
  344.   }
  345.   return na;
  346. }

  348. ‌static uint32_t counthash(const GCtab *t, uint32_t *bins, uint32_t *narray)
  349. {
  350.   uint32_t total, na, i, hmask = t->hmask;
  351.   Node *node = noderef(t->node);
  352.   for (total = na = 0, i = 0; i <= hmask; i++) {
  353.     Node *n = &node[i];
  354.     if (!tvisnil(&n->val)) {
  355.       na += countint(&n->key, bins);
  356.       total++;
  357.     }
  358.   }
  359.   *narray += na;
  360.   return total;
  361. }

  363. ‌static uint32_t bestasize(uint32_t bins[], uint32_t *narray)
  364. {
  365.   uint32_t b, sum, na = 0, sz = 0, nn = *narray;
  366.   for (b = 0, sum = 0; 2*nn > (1u<<b) && sum != nn; b++)
  367.     if (bins[b] > 0 && 2*(sum += bins[b]) > (1u<<b)) {
  368.       sz = (2u<<b)+1;
  369.       na = sum;
  370.     }
  371.   *narray = sz;
  372.   return na;
  373. }

  375. ‌static void rehashtab(lua_State *L, GCtab *t, cTValue *ek)
  376. {
  377.   uint32_t bins[LJ_MAX_ABITS];
  378.   uint32_t total, asize, na, i;
  379.   for (i = 0; i < LJ_MAX_ABITS; i++) bins[i] = 0;
  380.   asize = countarray(t, bins);
  381.   total = 1 + asize;
  382.   total += counthash(t, bins, &asize);
  383.   asize += countint(ek, bins);
  384.   na = bestasize(bins, &asize);
  385.   total -= na;
  386.   resizetab(L, t, asize, hsize2hbits(total));
  387. }

  389. #if LJ_HASFFI
  390. ‌void lj_tab_rehash(lua_State *L, GCtab *t)
  391. {
  392.   rehashtab(L, t, niltv(L));
  393. }
  394. #endif

  396. ‌void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
  397. {
  398.   resizetab(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
  399. }

  401. /* -- Table getters ------------------------------------------------------- */

  403. ‌cTValue * LJ_FASTCALL lj_tab_getinth(GCtab *t, int32_t key)
  404. {
  405.   TValue k;
  406.   Node *n;
  407.   k.n = (lua_Number)key;
  408.   n = hashnum(t, &k);
  409.   do {
  410.     if (tvisnum(&n->key) && n->key.n == k.n)
  411.       return &n->val;
  412.   } while ((n = nextnode(n)));
  413.   return NULL;
  414. }

  416. ‌cTValue *lj_tab_getstr(GCtab *t, GCstr *key)
  417. {
  418.   Node *n = hashstr(t, key);
  419.   do {
  420.     if (tvisstr(&n->key) && strV(&n->key) == key)
  421.       return &n->val;
  422.   } while ((n = nextnode(n)));
  423.   return NULL;
  424. }

  426. ‌cTValue *lj_tab_get(lua_State *L, GCtab *t, cTValue *key)
  427. {
  428.   if (tvisstr(key)) {
  429.     cTValue *tv = lj_tab_getstr(t, strV(key));
  430.     if (tv)
  431.       return tv;
  432.   } else if (tvisint(key)) {
  433.     cTValue *tv = lj_tab_getint(t, intV(key));
  434.     if (tv)
  435.       return tv;
  436.   } else if (tvisnum(key)) {
  437.     lua_Number nk = numV(key);
  438.     int32_t k = lj_num2int(nk);
  439.     if (nk == (lua_Number)k) {
  440.       cTValue *tv = lj_tab_getint(t, k);
  441.       if (tv)
  442.         return tv;
  443.     } else {
  444.       goto genlookup;  /* Else use the generic lookup. */
  445.     }
  446.   } else if (!tvisnil(key)) {
  447.     Node *n;
  448.   genlookup:
  449.     n = hashkey(t, key);
  450.     do {
  451.       if (lj_obj_equal(&n->key, key))
  452.         return &n->val;
  453.     } while ((n = nextnode(n)));
  454.   }
  455.   return niltv(L);
  456. }

  458. /* -- Table setters ------------------------------------------------------- */

  460. /* Insert new key. Use Brent's variation to optimize the chain length. */
  461. ‌TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
  462. {
  463.   Node *n = hashkey(t, key);
  464.   if (!tvisnil(&n->val) || t->hmask == 0) {
  465.     Node *nodebase = noderef(t->node);
  466.     Node *collide, *freenode = getfreetop(t, nodebase);
  467.     lua_assert(freenode >= nodebase && freenode <= nodebase+t->hmask+1);
  468.     do {
  469.       if (freenode == nodebase) {  /* No free node found? */
  470.         rehashtab(L, t, key);  /* Rehash table. */
  471.         return lj_tab_set(L, t, key);  /* Retry key insertion. */
  472.       }
  473.     } while (!tvisnil(&(--freenode)->key));
  474.     setfreetop(t, nodebase, freenode);
  475.     lua_assert(freenode != &G(L)->nilnode);
  476.     collide = hashkey(t, &n->key);
  477.     if (collide != n) {  /* Colliding node not the main node? */
  478.       while (noderef(collide->next) != n)  /* Find predecessor. */
  479.         collide = nextnode(collide);
  480.       setmref(collide->next, freenode);  /* Relink chain. */
  481.       /* Copy colliding node into free node and free main node. */
  482.       freenode->val = n->val;
  483.       freenode->key = n->key;
  484.       freenode->next = n->next;
  485.       setmref(n->next, NULL);
  486.       setnilV(&n->val);
  487.       /* Rechain pseudo-resurrected string keys with colliding hashes. */
  488.       while (nextnode(freenode)) {
  489.         Node *nn = nextnode(freenode);
  490.         if (tvisstr(&nn->key) && !tvisnil(&nn->val) &&
  491.             hashstr(t, strV(&nn->key)) == n) {
  492.           freenode->next = nn->next;
  493.           nn->next = n->next;
  494.           setmref(n->next, nn);
  495.         } else {
  496.           freenode = nn;
  497.         }
  498.       }
  499.     } else {  /* Otherwise use free node. */
  500.       setmrefr(freenode->next, n->next);  /* Insert into chain. */
  501.       setmref(n->next, freenode);
  502.       n = freenode;
  503.     }
  504.   }
  505.   n->key.u64 = key->u64;
  506.   if (LJ_UNLIKELY(tvismzero(&n->key)))
  507.     n->key.u64 = 0;
  508.   lj_gc_anybarriert(L, t);
  509.   lua_assert(tvisnil(&n->val));
  510.   return &n->val;
  511. }

  513. ‌TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)
  514. {
  515.   TValue k;
  516.   Node *n;
  517.   k.n = (lua_Number)key;
  518.   n = hashnum(t, &k);
  519.   do {
  520.     if (tvisnum(&n->key) && n->key.n == k.n)
  521.       return &n->val;
  522.   } while ((n = nextnode(n)));
  523.   return lj_tab_newkey(L, t, &k);
  524. }

  526. ‌TValue *lj_tab_setstr(lua_State *L, GCtab *t, GCstr *key)
  527. {
  528.   TValue k;
  529.   Node *n = hashstr(t, key);
  530.   do {
  531.     if (tvisstr(&n->key) && strV(&n->key) == key)
  532.       return &n->val;
  533.   } while ((n = nextnode(n)));
  534.   setstrV(L, &k, key);
  535.   return lj_tab_newkey(L, t, &k);
  536. }

  538. ‌TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
  539. {
  540.   Node *n;
  541.   t->nomm = 0;  /* Invalidate negative metamethod cache. */
  542.   if (tvisstr(key)) {
  543.     return lj_tab_setstr(L, t, strV(key));
  544.   } else if (tvisint(key)) {
  545.     return lj_tab_setint(L, t, intV(key));
  546.   } else if (tvisnum(key)) {
  547.     lua_Number nk = numV(key);
  548.     int32_t k = lj_num2int(nk);
  549.     if (nk == (lua_Number)k)
  550.       return lj_tab_setint(L, t, k);
  551.     if (tvisnan(key))
  552.       lj_err_msg(L, LJ_ERR_NANIDX);
  553.     /* Else use the generic lookup. */
  554.   } else if (tvisnil(key)) {
  555.     lj_err_msg(L, LJ_ERR_NILIDX);
  556.   }
  557.   n = hashkey(t, key);
  558.   do {
  559.     if (lj_obj_equal(&n->key, key))
  560.       return &n->val;
  561.   } while ((n = nextnode(n)));
  562.   return lj_tab_newkey(L, t, key);
  563. }

  565. /* -- Table traversal ----------------------------------------------------- */

  567. /* Get the traversal index of a key. */
  568. ‌static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key)
  569. {
  570.   TValue tmp;
  571.   if (tvisint(key)) {
  572.     int32_t k = intV(key);
  573.     if ((uint32_t)k < t->asize)
  574.       return (uint32_t)k;  /* Array key indexes: [0..t->asize-1] */
  575.     setnumV(&tmp, (lua_Number)k);
  576.     key = &tmp;
  577.   } else if (tvisnum(key)) {
  578.     lua_Number nk = numV(key);
  579.     int32_t k = lj_num2int(nk);
  580.     if ((uint32_t)k < t->asize && nk == (lua_Number)k)
  581.       return (uint32_t)k;  /* Array key indexes: [0..t->asize-1] */
  582.   }
  583.   if (!tvisnil(key)) {
  584.     Node *n = hashkey(t, key);
  585.     do {
  586.       if (lj_obj_equal(&n->key, key))
  587.         return t->asize + (uint32_t)(n - noderef(t->node));
  588.         /* Hash key indexes: [t->asize..t->asize+t->nmask] */
  589.     } while ((n = nextnode(n)));
  590.     if (key->u32.hi == 0xfffe7fff)  /* ITERN was despecialized while running. */
  591.       return key->u32.lo - 1;
  592.     lj_err_msg(L, LJ_ERR_NEXTIDX);
  593.     return 0;  /* unreachable */
  594.   }
  595.   return ~0u;  /* A nil key starts the traversal. */
  596. }

  598. /* Advance to the next step in a table traversal. */
  599. ‌int lj_tab_next(lua_State *L, GCtab *t, TValue *key)
  600. {
  601.   uint32_t i = keyindex(L, t, key);  /* Find predecessor key index. */
  602.   for (i++; i < t->asize; i++)  /* First traverse the array keys. */
  603.     if (!tvisnil(arrayslot(t, i))) {
  604.       setintV(key, i);
  605.       copyTV(L, key+1, arrayslot(t, i));
  606.       return 1;
  607.     }
  608.   for (i -= t->asize; i <= t->hmask; i++) {  /* Then traverse the hash keys. */
  609.     Node *n = &noderef(t->node)[i];
  610.     if (!tvisnil(&n->val)) {
  611.       copyTV(L, key, &n->key);
  612.       copyTV(L, key+1, &n->val);
  613.       return 1;
  614.     }
  615.   }
  616.   return 0;  /* End of traversal. */
  617. }

  619. /* -- Table length calculation -------------------------------------------- */

  621. ‌static MSize unbound_search(GCtab *t, MSize j)
  622. {
  623.   cTValue *tv;
  624.   MSize i = j;  /* i is zero or a present index */
  625.   j++;
  626.   /* find `i' and `j' such that i is present and j is not */
  627.   while ((tv = lj_tab_getint(t, (int32_t)j)) && !tvisnil(tv)) {
  628.     i = j;
  629.     j *= 2;
  630.     if (j > (MSize)(INT_MAX-2)) {  /* overflow? */
  631.       /* table was built with bad purposes: resort to linear search */
  632.       i = 1;
  633.       while ((tv = lj_tab_getint(t, (int32_t)i)) && !tvisnil(tv)) i++;
  634.       return i - 1;
  635.     }
  636.   }
  637.   /* now do a binary search between them */
  638.   while (j - i > 1) {
  639.     MSize m = (i+j)/2;
  640.     cTValue *tvb = lj_tab_getint(t, (int32_t)m);
  641.     if (tvb && !tvisnil(tvb)) i = m; else j = m;
  642.   }
  643.   return i;
  644. }

  646. /*
  647. ** Try to find a boundary in table `t'. A `boundary' is an integer index
  648. ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
  649. */
  650. ‌MSize LJ_FASTCALL lj_tab_len(GCtab *t)
  651. {
  652.   MSize j = (MSize)t->asize;
  653.   if (j > 1 && tvisnil(arrayslot(t, j-1))) {
  654.     MSize i = 1;
  655.     while (j - i > 1) {
  656.       MSize m = (i+j)/2;
  657.       if (tvisnil(arrayslot(t, m-1))) j = m; else i = m;
  658.     }
  659.     return i-1;
  660.   }
  661.   if (j) j--;
  662.   if (t->hmask <= 0)
  663.     return j;
  664.   return unbound_search(t, j);
  665. }

One Level Up Top Level