1 files changed, 131 insertions, 91 deletions

diff --git a/src/lj_tab.c b/src/lj_tab.c
index c5b6bcbf..c3609b38 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -16,25 +16,10 @@
 
 /* -- Object hashing ------------------------------------------------------ */
 
-/* Hash values are masked with the table hash mask and used as an index. */
-static LJ_AINLINE Node *hashmask(const GCtab *t, uint32_t hash)
-{
-  Node *n = noderef(t->node);
-  return &n[hash & t->hmask];
-}
-
-/* String hashes are precomputed when they are interned. */
-#define hashstr(t, s)           hashmask(t, (s)->hash)
-
-#define hashlohi(t, lo, hi)     hashmask((t), hashrot((lo), (hi)))
-#define hashnum(t, o)           hashlohi((t), (o)->u32.lo, ((o)->u32.hi << 1))
-#define hashptr(t, p)           hashlohi((t), u32ptr(p), u32ptr(p) + HASH_BIAS)
-#define hashgcref(t, r)         hashlohi((t), gcrefu(r), gcrefu(r) + HASH_BIAS)
-
 /* Hash an arbitrary key and return its anchor position in the hash table. */
 static Node *hashkey(const GCtab *t, cTValue *key)
 {
-  lua_assert(!tvisint(key));
+  lj_assertX(!tvisint(key), "attempt to hash integer");
   if (tvisstr(key))
     return hashstr(t, strV(key));
   else if (tvisnum(key))
@@ -53,13 +38,13 @@ static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
 {
   uint32_t hsize;
   Node *node;
-  lua_assert(hbits != 0);
+  lj_assertL(hbits != 0, "zero hash size");
   if (hbits > LJ_MAX_HBITS)
     lj_err_msg(L, LJ_ERR_TABOV);
   hsize = 1u << hbits;
   node = lj_mem_newvec(L, hsize, Node);
-  setmref(node->freetop, &node[hsize]);
   setmref(t->node, node);
+  setfreetop(t, node, &node[hsize]);
   t->hmask = hsize-1;
 }
 
@@ -74,7 +59,7 @@ static LJ_AINLINE void clearhpart(GCtab *t)
 {
   uint32_t i, hmask = t->hmask;
   Node *node = noderef(t->node);
-  lua_assert(t->hmask != 0);
+  lj_assertX(t->hmask != 0, "empty hash part");
   for (i = 0; i <= hmask; i++) {
     Node *n = &node[i];
     setmref(n->next, NULL);
@@ -98,7 +83,8 @@ static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
   GCtab *t;
   /* First try to colocate the array part. */
   if (LJ_MAX_COLOSIZE != 0 && asize > 0 && asize <= LJ_MAX_COLOSIZE) {
-    lua_assert((sizeof(GCtab) & 7) == 0);
+    Node *nilnode;
+    lj_assertL((sizeof(GCtab) & 7) == 0, "bad GCtab size");
     t = (GCtab *)lj_mem_newgco(L, sizetabcolo(asize));
     t->gct = ~LJ_TTAB;
     t->nomm = (uint8_t)~0;
@@ -107,8 +93,13 @@ static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
     setgcrefnull(t->metatable);
     t->asize = asize;
     t->hmask = 0;
-    setmref(t->node, &G(L)->nilnode);
+    nilnode = &G(L)->nilnode;
+    setmref(t->node, nilnode);
+#if LJ_GC64
+    setmref(t->freetop, nilnode);
+#endif
   } else {  /* Otherwise separately allocate the array part. */
+    Node *nilnode;
     t = lj_mem_newobj(L, GCtab);
     t->gct = ~LJ_TTAB;
     t->nomm = (uint8_t)~0;
@@ -117,7 +108,11 @@ static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
     setgcrefnull(t->metatable);
     t->asize = 0;  /* In case the array allocation fails. */
     t->hmask = 0;
-    setmref(t->node, &G(L)->nilnode);
+    nilnode = &G(L)->nilnode;
+    setmref(t->node, nilnode);
+#if LJ_GC64
+    setmref(t->freetop, nilnode);
+#endif
     if (asize > 0) {
       if (asize > LJ_MAX_ASIZE)
         lj_err_msg(L, LJ_ERR_TABOV);
@@ -149,6 +144,12 @@ GCtab *lj_tab_new(lua_State *L, uint32_t asize, uint32_t hbits)
   return t;
 }
 
+/* The API of this function conforms to lua_createtable(). */
+GCtab *lj_tab_new_ah(lua_State *L, int32_t a, int32_t h)
+{
+  return lj_tab_new(L, (uint32_t)(a > 0 ? a+1 : 0), hsize2hbits(h));
+}
+
 #if LJ_HASJIT
 GCtab * LJ_FASTCALL lj_tab_new1(lua_State *L, uint32_t ahsize)
 {
@@ -165,7 +166,8 @@ GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
   GCtab *t;
   uint32_t asize, hmask;
   t = newtab(L, kt->asize, kt->hmask > 0 ? lj_fls(kt->hmask)+1 : 0);
-  lua_assert(kt->asize == t->asize && kt->hmask == t->hmask);
+  lj_assertL(kt->asize == t->asize && kt->hmask == t->hmask,
+             "mismatched size of table and template");
   t->nomm = 0;  /* Keys with metamethod names may be present. */
   asize = kt->asize;
   if (asize > 0) {
@@ -185,7 +187,7 @@ GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
     Node *node = noderef(t->node);
     Node *knode = noderef(kt->node);
     ptrdiff_t d = (char *)node - (char *)knode;
-    setmref(node->freetop, (Node *)((char *)noderef(knode->freetop) + d));
+    setfreetop(t, node, (Node *)((char *)getfreetop(kt, knode) + d));
     for (i = 0; i <= hmask; i++) {
       Node *kn = &knode[i];
       Node *n = &node[i];
@@ -198,6 +200,17 @@ GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
   return t;
 }
 
+/* Clear a table. */
+void LJ_FASTCALL lj_tab_clear(GCtab *t)
+{
+  clearapart(t);
+  if (t->hmask > 0) {
+    Node *node = noderef(t->node);
+    setfreetop(t, node, &node[t->hmask+1]);
+    clearhpart(t);
+  }
+}
+
 /* Free a table. */
 void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
 {
@@ -214,7 +227,7 @@ void LJ_FASTCALL lj_tab_free(global_State *g, GCtab *t)
 /* -- Table resizing ------------------------------------------------------ */
 
 /* Resize a table to fit the new array/hash part sizes. */
-static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
+void lj_tab_resize(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
 {
   Node *oldnode = noderef(t->node);
   uint32_t oldasize = t->asize;
@@ -247,6 +260,9 @@ static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
   } else {
     global_State *g = G(L);
     setmref(t->node, &g->nilnode);
+#if LJ_GC64
+    setmref(t->freetop, &g->nilnode);
+#endif
     t->hmask = 0;
   }
   if (asize < oldasize) {  /* Array part shrinks? */
@@ -276,7 +292,7 @@ static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
 
 static uint32_t countint(cTValue *key, uint32_t *bins)
 {
-  lua_assert(!tvisint(key));
+  lj_assertX(!tvisint(key), "bad integer key");
   if (tvisnum(key)) {
     lua_Number nk = numV(key);
     int32_t k = lj_num2int(nk);
@@ -348,7 +364,7 @@ static void rehashtab(lua_State *L, GCtab *t, cTValue *ek)
   asize += countint(ek, bins);
   na = bestasize(bins, &asize);
   total -= na;
-  resizetab(L, t, asize, hsize2hbits(total));
+  lj_tab_resize(L, t, asize, hsize2hbits(total));
 }
 
 #if LJ_HASFFI
@@ -360,7 +376,7 @@ void lj_tab_rehash(lua_State *L, GCtab *t)
 
 void lj_tab_reasize(lua_State *L, GCtab *t, uint32_t nasize)
 {
-  resizetab(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
+  lj_tab_resize(L, t, nasize+1, t->hmask > 0 ? lj_fls(t->hmask)+1 : 0);
 }
 
 /* -- Table getters ------------------------------------------------------- */
@@ -378,7 +394,7 @@ cTValue * LJ_FASTCALL lj_tab_getinth(GCtab *t, int32_t key)
   return NULL;
 }
 
-cTValue *lj_tab_getstr(GCtab *t, GCstr *key)
+cTValue *lj_tab_getstr(GCtab *t, const GCstr *key)
 {
   Node *n = hashstr(t, key);
   do {
@@ -428,16 +444,17 @@ TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
   Node *n = hashkey(t, key);
   if (!tvisnil(&n->val) || t->hmask == 0) {
     Node *nodebase = noderef(t->node);
-    Node *collide, *freenode = noderef(nodebase->freetop);
-    lua_assert(freenode >= nodebase && freenode <= nodebase+t->hmask+1);
+    Node *collide, *freenode = getfreetop(t, nodebase);
+    lj_assertL(freenode >= nodebase && freenode <= nodebase+t->hmask+1,
+               "bad freenode");
     do {
       if (freenode == nodebase) {  /* No free node found? */
         rehashtab(L, t, key);  /* Rehash table. */
         return lj_tab_set(L, t, key);  /* Retry key insertion. */
       }
     } while (!tvisnil(&(--freenode)->key));
-    setmref(nodebase->freetop, freenode);
-    lua_assert(freenode != &G(L)->nilnode);
+    setfreetop(t, nodebase, freenode);
+    lj_assertL(freenode != &G(L)->nilnode, "store to fallback hash");
     collide = hashkey(t, &n->key);
     if (collide != n) {  /* Colliding node not the main node? */
       while (noderef(collide->next) != n)  /* Find predecessor. */
@@ -493,7 +510,7 @@ TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
   if (LJ_UNLIKELY(tvismzero(&n->key)))
     n->key.u64 = 0;
   lj_gc_anybarriert(L, t);
-  lua_assert(tvisnil(&n->val));
+  lj_assertL(tvisnil(&n->val), "new hash slot is not empty");
   return &n->val;
 }
 
@@ -510,7 +527,7 @@ TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)
   return lj_tab_newkey(L, t, &k);
 }
 
-TValue *lj_tab_setstr(lua_State *L, GCtab *t, GCstr *key)
+TValue *lj_tab_setstr(lua_State *L, GCtab *t, const GCstr *key)
 {
   TValue k;
   Node *n = hashstr(t, key);
@@ -551,103 +568,126 @@ TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key)
 
 /* -- Table traversal ----------------------------------------------------- */
 
-/* Get the traversal index of a key. */
-static uint32_t keyindex(lua_State *L, GCtab *t, cTValue *key)
+/* Table traversal indexes:
+**
+** Array key index: [0 .. t->asize-1]
+** Hash key index:  [t->asize .. t->asize+t->hmask]
+** Invalid key:     ~0
+*/
+
+/* Get the successor traversal index of a key. */
+uint32_t LJ_FASTCALL lj_tab_keyindex(GCtab *t, cTValue *key)
 {
   TValue tmp;
   if (tvisint(key)) {
     int32_t k = intV(key);
     if ((uint32_t)k < t->asize)
-      return (uint32_t)k;  /* Array key indexes: [0..t->asize-1] */
+      return (uint32_t)k + 1;
     setnumV(&tmp, (lua_Number)k);
     key = &tmp;
   } else if (tvisnum(key)) {
     lua_Number nk = numV(key);
     int32_t k = lj_num2int(nk);
     if ((uint32_t)k < t->asize && nk == (lua_Number)k)
-      return (uint32_t)k;  /* Array key indexes: [0..t->asize-1] */
+      return (uint32_t)k + 1;
   }
   if (!tvisnil(key)) {
     Node *n = hashkey(t, key);
     do {
       if (lj_obj_equal(&n->key, key))
-        return t->asize + (uint32_t)(n - noderef(t->node));
-        /* Hash key indexes: [t->asize..t->asize+t->nmask] */
+        return t->asize + (uint32_t)((n+1) - noderef(t->node));
     } while ((n = nextnode(n)));
-    if (key->u32.hi == 0xfffe7fff)  /* ITERN was despecialized while running. */
-      return key->u32.lo - 1;
-    lj_err_msg(L, LJ_ERR_NEXTIDX);
-    return 0;  /* unreachable */
+    if (key->u32.hi == LJ_KEYINDEX)  /* Despecialized ITERN while running. */
+      return key->u32.lo;
+    return ~0u;  /* Invalid key to next. */
   }
-  return ~0u;  /* A nil key starts the traversal. */
+  return 0;  /* A nil key starts the traversal. */
 }
 
-/* Advance to the next step in a table traversal. */
-int lj_tab_next(lua_State *L, GCtab *t, TValue *key)
+/* Get the next key/value pair of a table traversal. */
+int lj_tab_next(GCtab *t, cTValue *key, TValue *o)
 {
-  uint32_t i = keyindex(L, t, key);  /* Find predecessor key index. */
-  for (i++; i < t->asize; i++)  /* First traverse the array keys. */
-    if (!tvisnil(arrayslot(t, i))) {
-      setintV(key, i);
-      copyTV(L, key+1, arrayslot(t, i));
+  uint32_t idx = lj_tab_keyindex(t, key);  /* Find successor index of key. */
+  /* First traverse the array part. */
+  for (; idx < t->asize; idx++) {
+    cTValue *a = arrayslot(t, idx);
+    if (LJ_LIKELY(!tvisnil(a))) {
+      setintV(o, idx);
+      o[1] = *a;
       return 1;
     }
-  for (i -= t->asize; i <= t->hmask; i++) {  /* Then traverse the hash keys. */
-    Node *n = &noderef(t->node)[i];
+  }
+  idx -= t->asize;
+  /* Then traverse the hash part. */
+  for (; idx <= t->hmask; idx++) {
+    Node *n = &noderef(t->node)[idx];
     if (!tvisnil(&n->val)) {
-      copyTV(L, key, &n->key);
-      copyTV(L, key+1, &n->val);
+      o[0] = n->key;
+      o[1] = n->val;
       return 1;
     }
   }
-  return 0;  /* End of traversal. */
+  return (int32_t)idx < 0 ? -1 : 0;  /* Invalid key or end of traversal. */
 }
 
 /* -- Table length calculation -------------------------------------------- */
 
-static MSize unbound_search(GCtab *t, MSize j)
+/* Compute table length. Slow path with mixed array/hash lookups. */
+LJ_NOINLINE static MSize tab_len_slow(GCtab *t, size_t hi)
 {
   cTValue *tv;
-  MSize i = j;  /* i is zero or a present index */
-  j++;
-  /* find `i' and `j' such that i is present and j is not */
-  while ((tv = lj_tab_getint(t, (int32_t)j)) && !tvisnil(tv)) {
-    i = j;
-    j *= 2;
-    if (j > (MSize)(INT_MAX-2)) {  /* overflow? */
-      /* table was built with bad purposes: resort to linear search */
-      i = 1;
-      while ((tv = lj_tab_getint(t, (int32_t)i)) && !tvisnil(tv)) i++;
-      return i - 1;
+  size_t lo = hi;
+  hi++;
+  /* Widening search for an upper bound. */
+  while ((tv = lj_tab_getint(t, (int32_t)hi)) && !tvisnil(tv)) {
+    lo = hi;
+    hi += hi;
+    if (hi > (size_t)(INT_MAX-2)) {  /* Punt and do a linear search. */
+      lo = 1;
+      while ((tv = lj_tab_getint(t, (int32_t)lo)) && !tvisnil(tv)) lo++;
+      return (MSize)(lo - 1);
     }
   }
-  /* now do a binary search between them */
-  while (j - i > 1) {
-    MSize m = (i+j)/2;
-    cTValue *tvb = lj_tab_getint(t, (int32_t)m);
-    if (tvb && !tvisnil(tvb)) i = m; else j = m;
+  /* Binary search to find a non-nil to nil transition. */
+  while (hi - lo > 1) {
+    size_t mid = (lo+hi) >> 1;
+    cTValue *tvb = lj_tab_getint(t, (int32_t)mid);
+    if (tvb && !tvisnil(tvb)) lo = mid; else hi = mid;
   }
-  return i;
+  return (MSize)lo;
 }
 
-/*
-** Try to find a boundary in table `t'. A `boundary' is an integer index
-** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
-*/
+/* Compute table length. Fast path. */
 MSize LJ_FASTCALL lj_tab_len(GCtab *t)
 {
-  MSize j = (MSize)t->asize;
-  if (j > 1 && tvisnil(arrayslot(t, j-1))) {
-    MSize i = 1;
-    while (j - i > 1) {
-      MSize m = (i+j)/2;
-      if (tvisnil(arrayslot(t, m-1))) j = m; else i = m;
+  size_t hi = (size_t)t->asize;
+  if (hi) hi--;
+  /* In a growing array the last array element is very likely nil. */
+  if (hi > 0 && LJ_LIKELY(tvisnil(arrayslot(t, hi)))) {
+    /* Binary search to find a non-nil to nil transition in the array. */
+    size_t lo = 0;
+    while (hi - lo > 1) {
+      size_t mid = (lo+hi) >> 1;
+      if (tvisnil(arrayslot(t, mid))) hi = mid; else lo = mid;
     }
-    return i-1;
+    return (MSize)lo;
   }
-  if (j) j--;
-  if (t->hmask <= 0)
-    return j;
-  return unbound_search(t, j);
+  /* Without a hash part, there's an implicit nil after the last element. */
+  return t->hmask ? tab_len_slow(t, hi) : (MSize)hi;
 }
 
+#if LJ_HASJIT
+/* Verify hinted table length or compute it. */
+MSize LJ_FASTCALL lj_tab_len_hint(GCtab *t, size_t hint)
+{
+  size_t asize = (size_t)t->asize;
+  cTValue *tv = arrayslot(t, hint);
+  if (LJ_LIKELY(hint+1 < asize)) {
+    if (LJ_LIKELY(!tvisnil(tv) && tvisnil(tv+1))) return (MSize)hint;
+  } else if (hint+1 <= asize && LJ_LIKELY(t->hmask == 0) && !tvisnil(tv)) {
+    return (MSize)hint;
+  }
+  return lj_tab_len(t);
+}
+#endif
+