commit 73ec04fcf3e3f7017786fbaf0a83291b22bec5c4
parent d13a3fb070fd0ec9ec3b85f88e0fcd914aa666d3
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Mon, 12 Jun 2017 11:21:17 -0300
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.
Diffstat:
5 files changed, 49 insertions(+), 66 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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);
}
