no more 'DEADKEY'. Table traversals do not need to consider dead keys;

if the key is dead, it cannot be given to 'next'. Instead, we now
use a 'table' tag without the collectable bit, which makes it
a unique tag good enough to reserve space.

5 files changed, 49 insertions, 66 deletions

diff --git a/lgc.c b/lgc.c
index 36e34368..18a05142 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 2.230 2017/06/01 19:16:34 roberto Exp roberto $
+** $Id: lgc.c,v 2.231 2017/06/09 16:48:44 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -75,8 +75,6 @@
 
 #define keyiswhite(n)   (keyiscollectable(n) && iswhite(gckey(n)))
 
-#define checkdeadkey(n) lua_assert(!keyisdead(n) || ttisnil(gval(n)))
-
 
 #define checkconsistency(obj)  \
   lua_longassert(!iscollectable(obj) || righttt(obj))
@@ -119,13 +117,11 @@ static lu_mem atomic (lua_State *L);
 
 
 /*
-** If key is not marked, mark its entry as dead. This allows key to be
-** collected, but keeps its entry in the table.  A dead node is needed
-** when Lua looks up for a key (it may be part of a chain) and when
-** traversing a weak table (key might be removed from the table during
-** traversal). Other places never manipulate dead keys, because its
-** associated nil value is enough to signal that the entry is logically
-** empty.
+** If key is not marked, mark its entry as dead. This allows the
+** collection of the key, but keeps its entry in the table (its removal
+** could break a chain). Other places never manipulate dead keys,
+** because its associated nil value is enough to signal that the entry
+** is logically empty.
 */
 static void removeentry (Node *n) {
   lua_assert(ttisnil(gval(n)));
@@ -203,7 +199,7 @@ LUAI_FUNC void luaC_protobarrier_ (lua_State *L, Proto *p) {
   lua_assert(g->gckind != KGC_GEN || isold(p));
   if (getage(p) == G_OLD1)  /* still need to be visited? */
     linkgclist(p, g->grayagain);  /* link it in 'grayagain' */
-  else 
+  else
     linkgclist(p, g->protogray);  /* link it in 'protogray' */
   black2gray(p);  /* make prototype gray (to avoid other barriers) */
 }
@@ -391,7 +387,6 @@ static void traverseweakvalue (global_State *g, Table *h) {
      worth traversing it now just to check) */
   int hasclears = (h->sizearray > 0);
   for (n = gnode(h, 0); n < limit; n++) {  /* traverse hash part */
-    checkdeadkey(n);
     if (ttisnil(gval(n)))  /* entry is empty? */
       removeentry(n);  /* remove it */
     else {
@@ -434,7 +429,6 @@ static int traverseephemeron (global_State *g, Table *h) {
   }
   /* traverse hash part */
   for (n = gnode(h, 0); n < limit; n++) {
-    checkdeadkey(n);
     if (ttisnil(gval(n)))  /* entry is empty? */
       removeentry(n);  /* remove it */
     else if (iscleared(g, gckeyN(n))) {  /* key is not marked (yet)? */
@@ -468,7 +462,6 @@ static void traversestrongtable (global_State *g, Table *h) {
   for (i = 0; i < h->sizearray; i++)  /* traverse array part */
     markvalue(g, &h->array[i]);
   for (n = gnode(h, 0); n < limit; n++) {  /* traverse hash part */
-    checkdeadkey(n);
     if (ttisnil(gval(n)))  /* entry is empty? */
       removeentry(n);  /* remove it */
     else {
diff --git a/lobject.h b/lobject.h
index 97afa143..e245f306 100644
--- a/lobject.h
+++ b/lobject.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lobject.h,v 2.121 2017/06/01 20:24:05 roberto Exp roberto $
+** $Id: lobject.h,v 2.122 2017/06/09 16:48:44 roberto Exp roberto $
 ** Type definitions for Lua objects
 ** See Copyright Notice in lua.h
 */
@@ -21,10 +21,9 @@
 */
 #define LUA_TUPVAL      LUA_NUMTAGS  /* upvalues */
 #define LUA_TPROTO      (LUA_NUMTAGS+1)  /* function prototypes */
-#define LUA_TDEADKEY    (LUA_NUMTAGS+2)  /* removed keys in tables */
 
 /*
-** number of all possible tags (including LUA_TNONE but excluding DEADKEY)
+** number of all possible tags (including LUA_TNONE)
 */
 #define LUA_TOTALTAGS   (LUA_TPROTO + 2)
 
@@ -559,14 +558,7 @@ typedef struct Table {
 #define keyisshrstr(node)       (keytt(node) == ctb(LUA_TSHRSTR))
 #define keystrval(node)         (gco2ts(keyval(node).gc))
 
-#define keyisdead(node)         (keytt(node) == LUA_TDEADKEY)
-
 #define setnilkey(node)         (keytt(node) = LUA_TNIL)
-#define setdeadkey(node)        (keytt(node) = LUA_TDEADKEY)
-
-/* a dead value may get the 'gc' field, but cannot access its contents */
-#define deadkey(n)  \
-  check_exp(keytt(n) == LUA_TDEADKEY, cast(void *, keyval(n).gc))
 
 #define keyiscollectable(n)     (keytt(n) & BIT_ISCOLLECTABLE)
 
@@ -574,6 +566,16 @@ typedef struct Table {
 #define gckeyN(n)       (keyiscollectable(n) ? gckey(n) : NULL)
 
 
+/*
+** Use a "nil table" to mark dead keys in a table. Those keys serve
+** only to keep space for removed entries, which may still be part of
+** chains. Note that the 'keytt' does not have the BIT_ISCOLLECTABLE
+** set, so these values are considered not collectable and are different
+** from any valid value.
+*/
+#define setdeadkey(n)   (keytt(n) = LUA_TTABLE, gckey(n) = NULL)
+
+
 
 /*
 ** 'module' operation for hashing (size is always a power of 2)
diff --git a/lstate.h b/lstate.h
index 9a3e778a..12dddf3b 100644
--- a/lstate.h
+++ b/lstate.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.h,v 2.141 2017/05/13 13:54:47 roberto Exp roberto $
+** $Id: lstate.h,v 2.142 2017/05/26 19:14:29 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -247,8 +247,7 @@ union GCUnion {
 
 
 /* macro to convert a Lua object into a GCObject */
-#define obj2gco(v) \
-        check_exp(novariant((v)->tt) < LUA_TDEADKEY, (&(cast_u(v)->gc)))
+#define obj2gco(v)      (&(cast_u(v)->gc))
 
 
 /* actual number of total bytes allocated */
diff --git a/ltable.c b/ltable.c
index 498eb121..b8244dca 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltable.c,v 2.122 2017/05/19 12:57:10 roberto Exp roberto $
+** $Id: ltable.c,v 2.123 2017/06/09 16:48:44 roberto Exp roberto $
 ** Lua tables (hash)
 ** See Copyright Notice in lua.h
 */
@@ -176,6 +176,25 @@ static int equalkey (const TValue *k1, const Node *n2) {
 
 
 /*
+** "Generic" get version. (Not that generic: not valid for integers,
+** which may be in array part, nor for floats with integral values.)
+*/
+static const TValue *getgeneric (Table *t, const TValue *key) {
+  Node *n = mainpositionTV(t, key);
+  for (;;) {  /* check whether 'key' is somewhere in the chain */
+    if (equalkey(key, n))
+      return gval(n);  /* that's it */
+    else {
+      int nx = gnext(n);
+      if (nx == 0)
+        return luaO_nilobject;  /* not found */
+      n += nx;
+    }
+  }
+}
+
+
+/*
 ** returns the index for 'k' if 'k' is an appropriate key to live in
 ** the array part of a table, 0 otherwise.
 */
@@ -199,22 +218,12 @@ static unsigned int findindex (lua_State *L, Table *t, StkId key) {
   if (i != 0 && i <= t->sizearray)  /* is 'key' inside array part? */
     return i;  /* yes; that's the index */
   else {
-    int nx;
-    Node *n = mainpositionTV(t, key);
-    for (;;) {  /* check whether 'key' is somewhere in the chain */
-      /* key may be dead already, but it is ok to use it in 'next' */
-      if (equalkey(key, n) ||
-             (keyisdead(n) && iscollectable(key) &&
-             deadkey(n) == gcvalue(key))) {
-        i = cast_int(n - gnode(t, 0));  /* key index in hash table */
-        /* hash elements are numbered after array ones */
-        return (i + 1) + t->sizearray;
-      }
-      nx = gnext(n);
-      if (nx == 0)
-        luaG_runerror(L, "invalid key to 'next'");  /* key not found */
-      else n += nx;
-    }
+    const TValue *n = getgeneric(t, key);
+    if (n == luaO_nilobject)
+      luaG_runerror(L, "invalid key to 'next'");  /* key not found */
+    i = cast_int(nodefromval(n) - gnode(t, 0));  /* key index in hash table */
+    /* hash elements are numbered after array ones */
+    return (i + 1) + t->sizearray;
   }
 }
 
@@ -574,25 +583,6 @@ const TValue *luaH_getshortstr (Table *t, TString *key) {
 }
 
 
-/*
-** "Generic" get version. (Not that generic: not valid for integers,
-** which may be in array part, nor for floats with integral values.)
-*/
-static const TValue *getgeneric (Table *t, const TValue *key) {
-  Node *n = mainpositionTV(t, key);
-  for (;;) {  /* check whether 'key' is somewhere in the chain */
-    if (equalkey(key, n))
-      return gval(n);  /* that's it */
-    else {
-      int nx = gnext(n);
-      if (nx == 0)
-        return luaO_nilobject;  /* not found */
-      n += nx;
-    }
-  }
-}
-
-
 const TValue *luaH_getstr (Table *t, TString *key) {
   if (key->tt == LUA_TSHRSTR)
     return luaH_getshortstr(t, key);
@@ -662,7 +652,7 @@ void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
 ** absent while 'i' is present; so 'j > i'.) Otherwise, 'j' is a
 ** boundary. ('j + 1' cannot be a present integer key because it is
 ** not a valid integer in Lua.)
-*/ 
+*/
 static lua_Unsigned hash_search (Table *t, lua_Unsigned j) {
   lua_Unsigned i;
   if (j == 0) j++;  /* the caller ensures 'j + 1' is present */
diff --git a/ltests.c b/ltests.c
index a9c93132..733e47d4 100644
--- a/ltests.c
+++ b/ltests.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.c,v 2.218 2017/05/31 18:54:58 roberto Exp roberto $
+** $Id: ltests.c,v 2.219 2017/06/09 16:48:44 roberto Exp roberto $
 ** Internal Module for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -449,7 +449,6 @@ static void markgrays (global_State *g) {
   checkgraylist(g, g->grayagain);
   checkgraylist(g, g->weak);
   checkgraylist(g, g->ephemeron);
-  checkgraylist(g, g->allweak);
   checkgraylist(g, g->protogray);
 }