Merge branch 'newarray' into nextversion

1 files changed, 244 insertions, 84 deletions

diff --git a/ltable.c b/ltable.c
index 103478fb..c9f66b3c 100644
--- a/ltable.c
+++ b/ltable.c
@@ -371,9 +371,10 @@ int luaH_next (lua_State *L, Table *t, StkId key) {
   unsigned int asize = luaH_realasize(t);
   unsigned int i = findindex(L, t, s2v(key), asize);  /* find original key */
   for (; i < asize; i++) {  /* try first array part */
-    if (!isempty(&t->array[i])) {  /* a non-empty entry? */
+    int tag = *getArrTag(t, i);
+    if (!tagisempty(tag)) {  /* a non-empty entry? */
       setivalue(s2v(key), i + 1);
-      setobj2s(L, key + 1, &t->array[i]);
+      farr2val(t, i + 1, tag, s2v(key + 1));
       return 1;
     }
   }
@@ -403,6 +404,41 @@ static void freehash (lua_State *L, Table *t) {
 
 
 /*
+** Check whether an integer key is in the array part. If 'alimit' is
+** not the real size of the array, the key still can be in the array
+** part.  In this case, do the "Xmilia trick" to check whether 'key-1'
+** is smaller than the real size.
+** The trick works as follow: let 'p' be an integer such that
+** '2^(p+1) >= alimit > 2^p', or  '2^(p+1) > alimit-1 >= 2^p'.
+** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
+** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
+** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
+** have the 'p' bit cleared. If the key is outside the array, that is,
+** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p',
+** therefore it will be larger or equal to 'alimit', and the check
+** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than
+** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
+** than 2^p, therefore smaller than 'alimit', and the check succeeds.
+** As special cases, when 'alimit' is 0 the condition is trivially false,
+** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
+** If key is 0 or negative, 'res' will have its higher bit on, so that
+** if cannot be smaller than alimit.
+*/
+static int keyinarray (Table *t, lua_Integer key) {
+  lua_Unsigned alimit = t->alimit;
+  if (l_castS2U(key) - 1u < alimit)  /* 'key' in [1, t->alimit]? */
+    return 1;
+  else if (!isrealasize(t) &&  /* key still may be in the array part? */
+           (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
+    t->alimit = cast_uint(key);  /* probably '#t' is here now */
+    return 1;
+  }
+  else
+    return 0;
+}
+
+
+/*
 ** {=============================================================
 ** Rehash
 ** ==============================================================
@@ -449,6 +485,12 @@ static int countint (lua_Integer key, unsigned int *nums) {
 }
 
 
+l_sinline int arraykeyisempty (const Table *t, lua_Integer key) {
+  int tag = *getArrTag(t, key - 1);
+  return tagisempty(tag);
+}
+
+
 /*
 ** Count keys in array part of table 't': Fill 'nums[i]' with
 ** number of keys that will go into corresponding slice and return
@@ -471,7 +513,7 @@ static unsigned int numusearray (const Table *t, unsigned int *nums) {
     }
     /* count elements in range (2^(lg - 1), 2^lg] */
     for (; i <= lim; i++) {
-      if (!isempty(&t->array[i-1]))
+      if (!arraykeyisempty(t, i))
         lc++;
     }
     nums[lg] += lc;
@@ -499,6 +541,33 @@ static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
 
 
 /*
+** Convert an "abstract size" (number of values in an array) to
+** "concrete size" (number of cell elements in the array). Cells
+** do not need to be full; we only must make sure it has the values
+** needed and its 'tag' element. So, we compute the concrete tag index
+** and the concrete value index of the last element, get their maximum
+** and adds 1.
+*/
+static unsigned int concretesize (unsigned int size) {
+  if (size == 0) return 0;
+  else {
+    unsigned int ts = TagIndex(size - 1);
+    unsigned int vs = ValueIndex(size - 1);
+    return ((ts >= vs) ? ts : vs) + 1;
+  }
+}
+
+
+static ArrayCell *resizearray (lua_State *L , Table *t,
+                               unsigned int oldasize,
+                               unsigned int newasize) {
+  oldasize = concretesize(oldasize);
+  newasize = concretesize(newasize);
+  return luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell);
+}
+
+
+/*
 ** Creates an array for the hash part of a table with the given
 ** size, or reuses the dummy node if size is zero.
 ** The computation for size overflow is in two steps: the first
@@ -593,7 +662,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
   unsigned int i;
   Table newt;  /* to keep the new hash part */
   unsigned int oldasize = setlimittosize(t);
-  TValue *newarray;
+  ArrayCell *newarray;
   /* create new hash part with appropriate size into 'newt' */
   newt.flags = 0;
   setnodevector(L, &newt, nhsize);
@@ -602,14 +671,18 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
     exchangehashpart(t, &newt);  /* and new hash */
     /* re-insert into the new hash the elements from vanishing slice */
     for (i = newasize; i < oldasize; i++) {
-      if (!isempty(&t->array[i]))
-        luaH_setint(L, t, i + 1, &t->array[i]);
+      int tag = *getArrTag(t, i);
+      if (!tagisempty(tag)) {  /* a non-empty entry? */
+        TValue aux;
+        farr2val(t, i + 1, tag, &aux);
+        luaH_setint(L, t, i + 1, &aux);
+      }
     }
     t->alimit = oldasize;  /* restore current size... */
     exchangehashpart(t, &newt);  /* and hash (in case of errors) */
   }
   /* allocate new array */
-  newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue);
+  newarray = resizearray(L, t, oldasize, newasize);
   if (l_unlikely(newarray == NULL && newasize > 0)) {  /* allocation failed? */
     freehash(L, &newt);  /* release new hash part */
     luaM_error(L);  /* raise error (with array unchanged) */
@@ -619,7 +692,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
   t->array = newarray;  /* set new array part */
   t->alimit = newasize;
   for (i = oldasize; i < newasize; i++)  /* clear new slice of the array */
-     setempty(&t->array[i]);
+    *getArrTag(t, i) = LUA_VEMPTY;
   /* re-insert elements from old hash part into new parts */
   reinsert(L, &newt, t);  /* 'newt' now has the old hash */
   freehash(L, &newt);  /* free old hash part */
@@ -675,8 +748,9 @@ Table *luaH_new (lua_State *L) {
 
 
 void luaH_free (lua_State *L, Table *t) {
+  unsigned ps = concretesize(luaH_realasize(t));
   freehash(L, t);
-  luaM_freearray(L, t->array, luaH_realasize(t));
+  luaM_freearray(L, t->array, ps);
   luaM_free(L, t);
 }
 
@@ -770,57 +844,57 @@ static void luaH_newkey (lua_State *L, Table *t, const TValue *key,
 }
 
 
-/*
-** Search function for integers. If integer is inside 'alimit', get it
-** directly from the array part. Otherwise, if 'alimit' is not
-** the real size of the array, the key still can be in the array part.
-** In this case, do the "Xmilia trick" to check whether 'key-1' is
-** smaller than the real size.
-** The trick works as follow: let 'p' be an integer such that
-**   '2^(p+1) >= alimit > 2^p', or  '2^(p+1) > alimit-1 >= 2^p'.
-** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
-** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
-** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
-** have the 'p' bit cleared. If the key is outside the array, that is,
-** 'key-1 >= 2^(p+1)', then 'res' will have some bit on higher than 'p',
-** therefore it will be larger or equal to 'alimit', and the check
-** will fail. If 'key-1 < 2^(p+1)', then 'res' has no bit on higher than
-** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
-** than 2^p, therefore smaller than 'alimit', and the check succeeds.
-** As special cases, when 'alimit' is 0 the condition is trivially false,
-** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
-** If key is 0 or negative, 'res' will have its higher bit on, so that
-** if cannot be smaller than alimit.
-*/
-const TValue *luaH_getint (Table *t, lua_Integer key) {
-  lua_Unsigned alimit = t->alimit;
-  if (l_castS2U(key) - 1u < alimit)  /* 'key' in [1, t->alimit]? */
-    return &t->array[key - 1];
-  else if (!isrealasize(t) &&  /* key still may be in the array part? */
-           (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
-    t->alimit = cast_uint(key);  /* probably '#t' is here now */
-    return &t->array[key - 1];
+static const TValue *getintfromhash (Table *t, lua_Integer key) {
+  Node *n = hashint(t, key);
+  lua_assert(l_castS2U(key) - 1u >= luaH_realasize(t));
+  for (;;) {  /* check whether 'key' is somewhere in the chain */
+    if (keyisinteger(n) && keyival(n) == key)
+      return gval(n);  /* that's it */
+    else {
+      int nx = gnext(n);
+      if (nx == 0) break;
+      n += nx;
+    }
   }
-  else {  /* key is not in the array part; check the hash */
-    Node *n = hashint(t, key);
-    for (;;) {  /* check whether 'key' is somewhere in the chain */
-      if (keyisinteger(n) && keyival(n) == key)
-        return gval(n);  /* that's it */
-      else {
-        int nx = gnext(n);
-        if (nx == 0) break;
-        n += nx;
-      }
+  return &absentkey;
+}
+
+
+static int hashkeyisempty (Table *t, lua_Integer key) {
+  const TValue *val = getintfromhash(t, key);
+  return isempty(val);
+}
+
+
+static int finishnodeget (const TValue *val, TValue *res) {
+  if (!ttisnil(val)) {
+    setobj(((lua_State*)NULL), res, val);
+    return HOK;  /* success */
+  }
+  else
+    return HNOTFOUND;  /* could not get value */
+}
+
+
+int luaH_getint (Table *t, lua_Integer key, TValue *res) {
+  if (keyinarray(t, key)) {
+    int tag = *getArrTag(t, key - 1);
+    if (!tagisempty(tag)) {
+      farr2val(t, key, tag, res);
+      return HOK;  /* success */
     }
-    return &absentkey;
+    else
+      return ~cast_int(key);  /* empty slot in the array part */
   }
+  else
+    return finishnodeget(getintfromhash(t, key), res);
 }
 
 
 /*
 ** search function for short strings
 */
-const TValue *luaH_getshortstr (Table *t, TString *key) {
+const TValue *luaH_Hgetshortstr (Table *t, TString *key) {
   Node *n = hashstr(t, key);
   lua_assert(key->tt == LUA_VSHRSTR);
   for (;;) {  /* check whether 'key' is somewhere in the chain */
@@ -836,9 +910,14 @@ const TValue *luaH_getshortstr (Table *t, TString *key) {
 }
 
 
-const TValue *luaH_getstr (Table *t, TString *key) {
+int luaH_getshortstr (Table *t, TString *key, TValue *res) {
+  return finishnodeget(luaH_Hgetshortstr(t, key), res);
+}
+
+
+static const TValue *Hgetstr (Table *t, TString *key) {
   if (key->tt == LUA_VSHRSTR)
-    return luaH_getshortstr(t, key);
+    return luaH_Hgetshortstr(t, key);
   else {  /* for long strings, use generic case */
     TValue ko;
     setsvalue(cast(lua_State *, NULL), &ko, key);
@@ -847,38 +926,121 @@ const TValue *luaH_getstr (Table *t, TString *key) {
 }
 
 
+int luaH_getstr (Table *t, TString *key, TValue *res) {
+  return finishnodeget(Hgetstr(t, key), res);
+}
+
+
+TString *luaH_getstrkey (Table *t, TString *key) {
+  const TValue *o = Hgetstr(t, key);
+  if (!isabstkey(o))  /* string already present? */
+    return keystrval(nodefromval(o));  /* get saved copy */
+  else
+    return NULL;
+}
+
+
 /*
 ** main search function
 */
-const TValue *luaH_get (Table *t, const TValue *key) {
+int luaH_get (Table *t, const TValue *key, TValue *res) {
+  const TValue *slot; 
   switch (ttypetag(key)) {
-    case LUA_VSHRSTR: return luaH_getshortstr(t, tsvalue(key));
-    case LUA_VNUMINT: return luaH_getint(t, ivalue(key));
-    case LUA_VNIL: return &absentkey;
+    case LUA_VSHRSTR:
+      slot = luaH_Hgetshortstr(t, tsvalue(key));
+      break;
+    case LUA_VNUMINT:
+      return luaH_getint(t, ivalue(key), res);
+    case LUA_VNIL:
+      slot = &absentkey;
+      break;
     case LUA_VNUMFLT: {
       lua_Integer k;
       if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */
-        return luaH_getint(t, k);  /* use specialized version */
+        return luaH_getint(t, k, res);  /* use specialized version */
       /* else... */
     }  /* FALLTHROUGH */
     default:
-      return getgeneric(t, key, 0);
+      slot = getgeneric(t, key, 0);
+      break;
   }
+  return finishnodeget(slot, res);
 }
 
 
+static int finishnodeset (Table *t, const TValue *slot, TValue *val) {
+  if (!ttisnil(slot)) {
+    setobj(((lua_State*)NULL), cast(TValue*, slot), val);
+    return HOK;  /* success */
+  }
+  else if (isabstkey(slot))
+    return HNOTFOUND;  /* no slot with that key */
+  else return (cast(Node*, slot) - t->node) + HFIRSTNODE;  /* node encoded */
+}
+
+
+int luaH_psetint (Table *t, lua_Integer key, TValue *val) {
+  if (keyinarray(t, key)) {
+    lu_byte *tag = getArrTag(t, key - 1);
+    if (!tagisempty(*tag)) {
+      fval2arr(t, key, tag, val);
+      return HOK;  /* success */
+    }
+    else
+      return ~cast_int(key);  /* empty slot in the array part */
+  }
+  else
+    return finishnodeset(t, getintfromhash(t, key), val);
+}
+
+
+int luaH_psetshortstr (Table *t, TString *key, TValue *val) {
+  return finishnodeset(t, luaH_Hgetshortstr(t, key), val);
+}
+
+
+int luaH_psetstr (Table *t, TString *key, TValue *val) {
+  return finishnodeset(t, Hgetstr(t, key), val);
+}
+
+
+int luaH_pset (Table *t, const TValue *key, TValue *val) {
+  switch (ttypetag(key)) {
+    case LUA_VSHRSTR: return luaH_psetshortstr(t, tsvalue(key), val);
+    case LUA_VNUMINT: return luaH_psetint(t, ivalue(key), val);
+    case LUA_VNIL: return HNOTFOUND;
+    case LUA_VNUMFLT: {
+      lua_Integer k;
+      if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */
+        return luaH_psetint(t, k, val);  /* use specialized version */
+      /* else... */
+    }  /* FALLTHROUGH */
+    default:
+      return finishnodeset(t, getgeneric(t, key, 0), val);
+  }
+}
+
 /*
 ** Finish a raw "set table" operation, where 'slot' is where the value
 ** should have been (the result of a previous "get table").
 ** Beware: when using this function you probably need to check a GC
 ** barrier and invalidate the TM cache.
 */
+
+
 void luaH_finishset (lua_State *L, Table *t, const TValue *key,
-                                   const TValue *slot, TValue *value) {
-  if (isabstkey(slot))
+                                    TValue *value, int hres) {
+  lua_assert(hres != HOK);
+  if (hres == HNOTFOUND) {
     luaH_newkey(L, t, key, value);
-  else
-    setobj2t(L, cast(TValue *, slot), value);
+  }
+  else if (hres > 0) {  /* regular Node? */
+    setobj2t(L, gval(gnode(t, hres - HFIRSTNODE)), value);
+  }
+  else {  /* array entry */
+    hres = ~hres;  /* real index */
+    obj2arr(t, hres, value);
+  }
 }
 
 
@@ -887,20 +1049,19 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key,
 ** barrier and invalidate the TM cache.
 */
 void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) {
-  const TValue *slot = luaH_get(t, key);
-  luaH_finishset(L, t, key, slot, value);
+  int hres = luaH_pset(t, key, value);
+  if (hres != HOK)
+    luaH_finishset(L, t, key, value, hres);
 }
 
 
 void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
-  const TValue *p = luaH_getint(t, key);
-  if (isabstkey(p)) {
+  int hres = luaH_psetint(t, key, value);
+  if (hres != HOK) {
     TValue k;
     setivalue(&k, key);
-    luaH_newkey(L, t, &k, value);
+    luaH_finishset(L, t, &k, value, hres);
   }
-  else
-    setobj2t(L, cast(TValue *, p), value);
 }
 
 
@@ -926,27 +1087,26 @@ static lua_Unsigned hash_search (Table *t, lua_Unsigned j) {
       j *= 2;
     else {
       j = LUA_MAXINTEGER;
-      if (isempty(luaH_getint(t, j)))  /* t[j] not present? */
+      if (hashkeyisempty(t, j))  /* t[j] not present? */
         break;  /* 'j' now is an absent index */
       else  /* weird case */
         return j;  /* well, max integer is a boundary... */
     }
-  } while (!isempty(luaH_getint(t, j)));  /* repeat until an absent t[j] */
+  } while (!hashkeyisempty(t, j));  /* repeat until an absent t[j] */
   /* i < j  &&  t[i] present  &&  t[j] absent */
   while (j - i > 1u) {  /* do a binary search between them */
     lua_Unsigned m = (i + j) / 2;
-    if (isempty(luaH_getint(t, m))) j = m;
+    if (hashkeyisempty(t, m)) j = m;
     else i = m;
   }
   return i;
 }
 
 
-static unsigned int binsearch (const TValue *array, unsigned int i,
-                                                    unsigned int j) {
+static unsigned int binsearch (Table *array, unsigned int i, unsigned int j) {
   while (j - i > 1u) {  /* binary search */
     unsigned int m = (i + j) / 2;
-    if (isempty(&array[m - 1])) j = m;
+    if (arraykeyisempty(array, m)) j = m;
     else i = m;
   }
   return i;
@@ -987,9 +1147,9 @@ static unsigned int binsearch (const TValue *array, unsigned int i,
 */
 lua_Unsigned luaH_getn (Table *t) {
   unsigned int limit = t->alimit;
-  if (limit > 0 && isempty(&t->array[limit - 1])) {  /* (1)? */
+  if (limit > 0 && arraykeyisempty(t, limit)) {  /* (1)? */
     /* there must be a boundary before 'limit' */
-    if (limit >= 2 && !isempty(&t->array[limit - 2])) {
+    if (limit >= 2 && !arraykeyisempty(t, limit - 1)) {
       /* 'limit - 1' is a boundary; can it be a new limit? */
       if (ispow2realasize(t) && !ispow2(limit - 1)) {
         t->alimit = limit - 1;
@@ -998,7 +1158,7 @@ lua_Unsigned luaH_getn (Table *t) {
       return limit - 1;
     }
     else {  /* must search for a boundary in [0, limit] */
-      unsigned int boundary = binsearch(t->array, 0, limit);
+      unsigned int boundary = binsearch(t, 0, limit);
       /* can this boundary represent the real size of the array? */
       if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) {
         t->alimit = boundary;  /* use it as the new limit */
@@ -1010,14 +1170,14 @@ lua_Unsigned luaH_getn (Table *t) {
   /* 'limit' is zero or present in table */
   if (!limitequalsasize(t)) {  /* (2)? */
     /* 'limit' > 0 and array has more elements after 'limit' */
-    if (isempty(&t->array[limit]))  /* 'limit + 1' is empty? */
+    if (arraykeyisempty(t, limit + 1))  /* 'limit + 1' is empty? */
       return limit;  /* this is the boundary */
     /* else, try last element in the array */
     limit = luaH_realasize(t);
-    if (isempty(&t->array[limit - 1])) {  /* empty? */
+    if (arraykeyisempty(t, limit)) {  /* empty? */
       /* there must be a boundary in the array after old limit,
          and it must be a valid new limit */
-      unsigned int boundary = binsearch(t->array, t->alimit, limit);
+      unsigned int boundary = binsearch(t, t->alimit, limit);
       t->alimit = boundary;
       return boundary;
     }
@@ -1025,8 +1185,8 @@ lua_Unsigned luaH_getn (Table *t) {
   }
   /* (3) 'limit' is the last element and either is zero or present in table */
   lua_assert(limit == luaH_realasize(t) &&
-             (limit == 0 || !isempty(&t->array[limit - 1])));
-  if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1))))
+             (limit == 0 || !arraykeyisempty(t, limit)));
+  if (isdummy(t) || hashkeyisempty(t, cast(lua_Integer, limit + 1)))
     return limit;  /* 'limit + 1' is absent */
   else  /* 'limit + 1' is also present */
     return hash_search(t, limit);