Full implementation of new representation for arrays

5 files changed, 96 insertions, 29 deletions

diff --git a/lgc.c b/lgc.c
index 813b08d5..0f423282 100644
--- a/lgc.c
+++ b/lgc.c
@@ -493,7 +493,7 @@ static int traverseephemeron (global_State *g, Table *h, int inv) {
   unsigned int nsize = sizenode(h);
   /* traverse array part */
   for (i = 0; i < asize; i++) {
-    GCObject *o = gcvalarr(h, i + 1);
+    GCObject *o = gcvalarr(h, i);
     if (o != NULL && iswhite(o)) {
       marked = 1;
       reallymarkobject(g, o);
@@ -533,7 +533,7 @@ static void traversestrongtable (global_State *g, Table *h) {
   unsigned int i;
   unsigned int asize = luaH_realasize(h);
   for (i = 0; i < asize; i++) {  /* traverse array part */
-    GCObject *o = gcvalarr(h, i + 1);
+    GCObject *o = gcvalarr(h, i);
     if (o != NULL && iswhite(o))
       reallymarkobject(g, o);
   }
@@ -757,9 +757,9 @@ static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) {
     unsigned int i;
     unsigned int asize = luaH_realasize(h);
     for (i = 0; i < asize; i++) {
-      GCObject *o = gcvalarr(h, i + 1);
+      GCObject *o = gcvalarr(h, i);
       if (iscleared(g, o))  /* value was collected? */
-        *getArrTag(h, i + 1) = LUA_VEMPTY;  /* remove entry */
+        *getArrTag(h, i) = LUA_VEMPTY;  /* remove entry */
     }
     for (n = gnode(h, 0); n < limit; n++) {
       if (iscleared(g, gcvalueN(gval(n))))  /* unmarked value? */
diff --git a/lobject.h b/lobject.h
index e91bb0f8..25e268be 100644
--- a/lobject.h
+++ b/lobject.h
@@ -192,6 +192,8 @@ typedef union {
 /* macro to test for (any kind of) nil */
 #define ttisnil(v)              checktype((v), LUA_TNIL)
 
+#define tagisempty(tag)         (novariant(tag) == LUA_TNIL)
+
 
 /* macro to test for a standard nil */
 #define ttisstrictnil(o)        checktag((o), LUA_VNIL)
@@ -736,7 +738,7 @@ typedef union Node {
 #define setnorealasize(t)       ((t)->flags |= BITRAS)
 
 
-typedef struct ArrayCell ArrayCell;
+typedef union ArrayCell ArrayCell;
 
 
 typedef struct Table {
diff --git a/ltable.c b/ltable.c
index ddda9a44..b7362a36 100644
--- a/ltable.c
+++ b/ltable.c
@@ -350,7 +350,7 @@ 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 */
-    int tag = *getArrTag(t, i + 1);
+    int tag = *getArrTag(t, i);
     if (!tagisempty(tag)) {  /* a non-empty entry? */
       setivalue(s2v(key), i + 1);
       farr2val(t, i + 1, tag, s2v(key + 1));
@@ -458,7 +458,7 @@ static int countint (lua_Integer key, unsigned int *nums) {
 
 
 l_sinline int arraykeyisempty (const Table *t, lua_Integer key) {
-  int tag = *getArrTag(t, key);
+  int tag = *getArrTag(t, key - 1);
   return tagisempty(tag);
 }
 
@@ -513,6 +513,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
@@ -605,7 +632,7 @@ 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++) {
-      int tag = *getArrTag(t, i + 1);
+      int tag = *getArrTag(t, i);
       if (!tagisempty(tag)) {  /* a non-empty entry? */
         TValue aux;
         farr2val(t, i + 1, tag, &aux);
@@ -616,7 +643,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
     exchangehashpart(t, &newt);  /* and hash (in case of errors) */
   }
   /* allocate new array */
-  newarray = luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell);
+  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) */
@@ -626,7 +653,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 */
-    *getArrTag(t, i + 1) = LUA_VEMPTY;
+    *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 */
@@ -682,8 +709,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);
 }
 
@@ -799,7 +827,7 @@ static int finishnodeget (const TValue *val, TValue *res) {
 
 int luaH_getint (Table *t, lua_Integer key, TValue *res) {
   if (keyinarray(t, key)) {
-    int tag = *getArrTag(t, key);
+    int tag = *getArrTag(t, key - 1);
     if (!tagisempty(tag)) {
       farr2val(t, key, tag, res);
       return HOK;  /* success */
@@ -902,7 +930,7 @@ static int finishnodeset (Table *t, const TValue *slot, TValue *val) {
 
 int luaH_psetint (Table *t, lua_Integer key, TValue *val) {
   if (keyinarray(t, key)) {
-    lu_byte *tag = getArrTag(t, key);
+    lu_byte *tag = getArrTag(t, key - 1);
     if (!tagisempty(*tag)) {
       fval2arr(t, key, tag, val);
       return HOK;  /* success */
@@ -960,7 +988,7 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key,
   }
   else {  /* array entry */
     hres = ~hres;  /* real index */
-    fval2arr(t, hres, getArrTag(t, hres), value);
+    obj2arr(t, hres, value);
   }
 }
 
diff --git a/ltable.h b/ltable.h
index 371e721d..b401aba1 100644
--- a/ltable.h
+++ b/ltable.h
@@ -51,31 +51,68 @@
 */
 
 
-struct ArrayCell {
-  lu_byte tt;
+/*
+** The array part of a table is represented by an array of cells.
+** Each cell is composed of (NM + 1) elements, and each element has the
+** type 'ArrayCell'.  In each cell, only one element has the variant
+** 'tag', while the other NM elements have the variant 'value'. The
+** array in the 'tag' element holds the tags of the other elements in
+** that cell.
+*/
+#define NM      ((unsigned int)sizeof(Value))
+
+union ArrayCell {
+  unsigned char tag[NM];
   Value value;
 };
 
 
-/* fast access to components of array values */
-#define getArrTag(t,k)  (&(t)->array[k - 1].tt)
-#define getArrVal(t,k)  (&(t)->array[k - 1].value)
+/*
+** 'NMTag' defines which cell element has the tags; that could be any
+** value between 0 (tags come before all values) and NM (tags come after
+** all values).
+*/
+#define NMTag     0
 
-#define tagisempty(tag)  (novariant(tag) == LUA_TNIL)
 
+/*
+** Computes the concrete index that holds the tag of abstract index 'i'
+*/
+#define TagIndex(i)     (((i)/NM * (NM + 1u)) + NMTag)
 
-#define farr2val(h,k,tag,res)  \
-  ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,k))
+/*
+** Computes the concrete index that holds the value of abstract index 'i'
+*/
+#define ValueIndex(i)   ((i) + (((i) + (NM - NMTag))/NM))
 
-#define fval2arr(h,k,tag,val)  \
-  (*tag = (val)->tt_, *getArrVal(h,k) = (val)->value_)
 
+/* Computes the address of the tag for the abstract index 'k' */
+#define getArrTag(t,k)  (&(t)->array[TagIndex(k)].tag[(k)%NM])
 
-#define obj2arr(h,k,val)  \
-  (*getArrTag(h,k) = (val)->tt_, *getArrVal(h,k) = (val)->value_)
+/* Computes the address of the value for the abstract index 'k' */
+#define getArrVal(t,k)  (&(t)->array[ValueIndex(k)].value)
 
+
+/*
+** Move TValues to/from arrays, using Lua indices
+*/
 #define arr2obj(h,k,val)  \
-  ((val)->tt_ = *getArrTag(h,k), (val)->value_ = *getArrVal(h,k))
+  ((val)->tt_ = *getArrTag(h,(k)-1u), (val)->value_ = *getArrVal(h,(k)-1u))
+
+#define obj2arr(h,k,val)  \
+  (*getArrTag(h,(k)-1u) = (val)->tt_, *getArrVal(h,(k)-1u) = (val)->value_)
+
+
+/*
+** Often, we need to check the tag of a value before moving it. These
+** macros also move TValues to/from arrays, but receive the precomputed
+** tag value or address as an extra argument.
+*/
+#define farr2val(h,k,tag,res)  \
+  ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,(k)-1u))
+
+#define fval2arr(h,k,tag,val)  \
+  (*tag = (val)->tt_, *getArrVal(h,(k)-1u) = (val)->value_)
 
 
 LUAI_FUNC int luaH_getshortstr (Table *t, TString *key, TValue *res);
diff --git a/lvm.h b/lvm.h
index 32455fba..c74c81f8 100644
--- a/lvm.h
+++ b/lvm.h
@@ -90,7 +90,7 @@ typedef enum {
   if (!ttistable(t)) aux = HNOTATABLE; \
   else { Table *h = hvalue(t); lua_Unsigned u = l_castS2U(k); \
     if ((u - 1u < h->alimit)) { \
-      int tag = *getArrTag(h,u); \
+      int tag = *getArrTag(h,(u)-1u); \
       if (tagisempty(tag)) aux = HNOTFOUND; \
       else { farr2val(h, u, tag, res); aux = HOK; }} \
     else { aux = luaH_getint(h, u, res); }}
@@ -103,7 +103,7 @@ typedef enum {
   if (!ttistable(t)) aux = HNOTATABLE; \
   else { Table *h = hvalue(t); lua_Unsigned u = l_castS2U(k); \
     if ((u - 1u < h->alimit)) { \
-      lu_byte *tag = getArrTag(h,u); \
+      lu_byte *tag = getArrTag(h,(u)-1u); \
       if (tagisempty(*tag)) aux = ~cast_int(u); \
       else { fval2arr(h, u, tag, val); aux = HOK; }} \
     else { aux = luaH_psetint(h, u, val); }}