commit caceeab750ed80e94f8ec763248ae04cd90fefb5
parent 3991312b94c0862577a5998fcf9ea93c81c6933c
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Sun, 18 Aug 2013 13:11:53 -0300
'next' field for tables changed from pointer to integer (for better
alignment on 64-bit machines)
Diffstat:
3 files changed, 49 insertions(+), 29 deletions(-)
diff --git a/lobject.h b/lobject.h
@@ -1,5 +1,5 @@
/*
-** $Id: lobject.h,v 2.78 2013/05/14 15:59:04 roberto Exp roberto $
+** $Id: lobject.h,v 2.79 2013/08/07 12:18:11 roberto Exp roberto $
** Type definitions for Lua objects
** See Copyright Notice in lua.h
*/
@@ -438,7 +438,7 @@ typedef union Closure {
typedef union TKey {
struct {
TValuefields;
- struct Node *next; /* for chaining */
+ int next; /* for chaining (offset for next node) */
} nk;
TValue tvk;
} TKey;
diff --git a/ltable.c b/ltable.c
@@ -1,5 +1,5 @@
/*
-** $Id: ltable.c,v 2.77 2013/05/29 14:05:03 roberto Exp roberto $
+** $Id: ltable.c,v 2.78 2013/06/20 15:02:49 roberto Exp roberto $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/
@@ -79,7 +79,7 @@
static const Node dummynode_ = {
{NILCONSTANT}, /* value */
- {{NILCONSTANT, NULL}} /* key */
+ {{NILCONSTANT, 0}} /* key */
};
@@ -158,6 +158,7 @@ static int findindex (lua_State *L, Table *t, StkId key) {
if (0 < i && i <= t->sizearray) /* is `key' inside array part? */
return i-1; /* yes; that's the index (corrected to C) */
else {
+ int nx;
Node *n = mainposition(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' */
@@ -168,9 +169,10 @@ static int findindex (lua_State *L, Table *t, StkId key) {
/* hash elements are numbered after array ones */
return i + t->sizearray;
}
- else n = gnext(n);
- if (n == NULL)
+ nx = gnext(n);
+ if (nx == 0)
luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */
+ else n += nx;
}
}
}
@@ -301,7 +303,7 @@ static void setnodevector (lua_State *L, Table *t, int size) {
t->node = luaM_newvector(L, size, Node);
for (i=0; i<size; i++) {
Node *n = gnode(t, i);
- gnext(n) = NULL;
+ gnext(n) = 0;
setnilvalue(gkey(n));
setnilvalue(gval(n));
}
@@ -429,27 +431,33 @@ TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */
Node *othern;
- Node *n = getfreepos(t); /* get a free place */
- if (n == NULL) { /* cannot find a free place? */
+ Node *f = getfreepos(t); /* get a free place */
+ if (f == NULL) { /* cannot find a free place? */
rehash(L, t, key); /* grow table */
/* whatever called 'newkey' take care of TM cache and GC barrier */
return luaH_set(L, t, key); /* insert key into grown table */
}
- lua_assert(!isdummy(n));
+ lua_assert(!isdummy(f));
othern = mainposition(t, gkey(mp));
if (othern != mp) { /* is colliding node out of its main position? */
/* yes; move colliding node into free position */
- while (gnext(othern) != mp) othern = gnext(othern); /* find previous */
- gnext(othern) = n; /* redo the chain with `n' in place of `mp' */
- *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */
- gnext(mp) = NULL; /* now `mp' is free */
+ while (othern + gnext(othern) != mp) /* find previous */
+ othern += gnext(othern);
+ gnext(othern) = f - othern; /* re-chain with 'f' in place of 'mp' */
+ *f = *mp; /* copy colliding node into free pos. (mp->next also goes) */
+ if (gnext(mp) != 0) {
+ gnext(f) += mp - f; /* correct 'next' */
+ gnext(mp) = 0; /* now 'mp' is free */
+ }
setnilvalue(gval(mp));
}
else { /* colliding node is in its own main position */
/* new node will go into free position */
- gnext(n) = gnext(mp); /* chain new position */
- gnext(mp) = n;
- mp = n;
+ if (gnext(mp) != 0)
+ gnext(f) = (mp + gnext(mp)) - f; /* chain new position */
+ else lua_assert(gnext(f) == 0);
+ gnext(mp) = f - mp;
+ mp = f;
}
}
setobj2t(L, gkey(mp), key);
@@ -468,11 +476,15 @@ const TValue *luaH_getint (Table *t, lua_Integer key) {
return &t->array[key - 1];
else {
Node *n = hashint(t, key);
- do { /* check whether `key' is somewhere in the chain */
+ for (;;) { /* check whether `key' is somewhere in the chain */
if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
return gval(n); /* that's it */
- else n = gnext(n);
- } while (n);
+ else {
+ int nx = gnext(n);
+ if (nx == 0) break;
+ n += nx;
+ }
+ };
return luaO_nilobject;
}
}
@@ -484,11 +496,15 @@ const TValue *luaH_getint (Table *t, lua_Integer key) {
const TValue *luaH_getstr (Table *t, TString *key) {
Node *n = hashstr(t, key);
lua_assert(key->tsv.tt == LUA_TSHRSTR);
- do { /* check whether `key' is somewhere in the chain */
+ for (;;) { /* check whether `key' is somewhere in the chain */
if (ttisshrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)), key))
return gval(n); /* that's it */
- else n = gnext(n);
- } while (n);
+ else {
+ int nx = gnext(n);
+ if (nx == 0) break;
+ n += nx;
+ }
+ };
return luaO_nilobject;
}
@@ -509,11 +525,15 @@ const TValue *luaH_get (Table *t, const TValue *key) {
}
default: {
Node *n = mainposition(t, key);
- do { /* check whether `key' is somewhere in the chain */
+ for (;;) { /* check whether `key' is somewhere in the chain */
if (luaV_rawequalobj(gkey(n), key))
return gval(n); /* that's it */
- else n = gnext(n);
- } while (n);
+ else {
+ int nx = gnext(n);
+ if (nx == 0) break;
+ n += nx;
+ }
+ };
return luaO_nilobject;
}
}
diff --git a/ltests.c b/ltests.c
@@ -1,5 +1,5 @@
/*
-** $Id: ltests.c,v 2.142 2013/08/16 18:55:49 roberto Exp roberto $
+** $Id: ltests.c,v 2.143 2013/08/16 19:02:31 roberto Exp roberto $
** Internal Module for Debugging of the Lua Implementation
** See Copyright Notice in lua.h
*/
@@ -718,8 +718,8 @@ static int table_query (lua_State *L) {
else
lua_pushliteral(L, "<undef>");
pushobject(L, gval(gnode(t, i)));
- if (gnext(&t->node[i]))
- lua_pushinteger(L, gnext(&t->node[i]) - t->node);
+ if (gnext(&t->node[i]) != 0)
+ lua_pushinteger(L, gnext(&t->node[i]));
else
lua_pushnil(L);
}
