From 351ccd733298e08c41937c1baf22a68e62bfeca9 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Mon, 15 May 2023 17:56:25 -0300 Subject: Towards a new implementation of arrays The array part of a table wastes too much space, due to padding. To avoid that, we need to store values in the array as something different from a TValue. Therefore, the API for table access should not assume that any value in a table lives in a *TValue. This commit is the first step to remove that assumption: functions luaH_get*, instead of returning a *TValue where the value lives, receive a *TValue where to put the value being accessed. (We still have to change the luaH_set* functions.) --- ltable.h | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'ltable.h') diff --git a/ltable.h b/ltable.h index 75dd9e26..c8a8c5e7 100644 --- a/ltable.h +++ b/ltable.h @@ -35,6 +35,27 @@ #define nodefromval(v) cast(Node *, (v)) +/* results from get/set */ +#define HOK 0 +#define HNOTFOUND 1 +#define HNOTATABLE 2 + + +/* 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_) + +#define tagisempty(tag) (novariant(tag) == LUA_TNIL) + +#define arr2val(h,k,tag,res) \ + ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,k)) + + +LUAI_FUNC int luaH_getshortstr1 (Table *t, TString *key, TValue *res); +LUAI_FUNC int luaH_getstr1 (Table *t, TString *key, TValue *res); +LUAI_FUNC int luaH_get1 (Table *t, const TValue *key, TValue *res); +LUAI_FUNC int luaH_getint1 (Table *t, lua_Integer key, TValue *res); + LUAI_FUNC const TValue *luaH_getint (Table *t, lua_Integer key); LUAI_FUNC void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value); -- cgit v1.2.3-55-g6feb From f8d30826dda6ee8e99200de57a1997734b853db2 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Tue, 16 May 2023 14:55:49 -0300 Subject: New table API for 'set' functions --- lapi.c | 31 +++++++++-------- ltable.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++++++++----------- ltable.h | 11 ++++++ lvm.c | 64 +++++++++++++++++----------------- lvm.h | 25 ++++++++++--- 5 files changed, 180 insertions(+), 71 deletions(-) (limited to 'ltable.h') diff --git a/lapi.c b/lapi.c index 2e27bc92..97a9f272 100644 --- a/lapi.c +++ b/lapi.c @@ -823,17 +823,18 @@ LUA_API int lua_getiuservalue (lua_State *L, int idx, int n) { ** t[k] = value at the top of the stack (where 'k' is a string) */ static void auxsetstr (lua_State *L, const TValue *t, const char *k) { - const TValue *slot; + int aux; TString *str = luaS_new(L, k); api_checknelems(L, 1); - if (luaV_fastget(L, t, str, slot, luaH_getstr)) { - luaV_finishfastset(L, t, slot, s2v(L->top.p - 1)); + luaV_fastset1(t, str, s2v(L->top.p - 1), aux, luaH_setstr1); + if (aux == HOK) { + luaV_finishfastset1(L, t, s2v(L->top.p - 1)); L->top.p--; /* pop value */ } else { setsvalue2s(L, L->top.p, str); /* push 'str' (to make it a TValue) */ api_incr_top(L); - luaV_finishset(L, t, s2v(L->top.p - 1), s2v(L->top.p - 2), slot); + luaV_finishset1(L, t, s2v(L->top.p - 1), s2v(L->top.p - 2), aux); L->top.p -= 2; /* pop value and key */ } lua_unlock(L); /* lock done by caller */ @@ -850,15 +851,16 @@ LUA_API void lua_setglobal (lua_State *L, const char *name) { LUA_API void lua_settable (lua_State *L, int idx) { TValue *t; - const TValue *slot; + int aux; lua_lock(L); api_checknelems(L, 2); t = index2value(L, idx); - if (luaV_fastget(L, t, s2v(L->top.p - 2), slot, luaH_get)) { - luaV_finishfastset(L, t, slot, s2v(L->top.p - 1)); + luaV_fastset1(t, s2v(L->top.p - 2), s2v(L->top.p - 1), aux, luaH_set1); + if (aux == HOK) { + luaV_finishfastset1(L, t, s2v(L->top.p - 1)); } else - luaV_finishset(L, t, s2v(L->top.p - 2), s2v(L->top.p - 1), slot); + luaV_finishset1(L, t, s2v(L->top.p - 2), s2v(L->top.p - 1), aux); L->top.p -= 2; /* pop index and value */ lua_unlock(L); } @@ -872,17 +874,18 @@ LUA_API void lua_setfield (lua_State *L, int idx, const char *k) { LUA_API void lua_seti (lua_State *L, int idx, lua_Integer n) { TValue *t; - const TValue *slot; + int aux; lua_lock(L); api_checknelems(L, 1); t = index2value(L, idx); - if (luaV_fastgeti(L, t, n, slot)) { - luaV_finishfastset(L, t, slot, s2v(L->top.p - 1)); + luaV_fastseti1(t, n, s2v(L->top.p - 1), aux); + if (aux == HOK) { + luaV_finishfastset1(L, t, s2v(L->top.p - 1)); } else { - TValue aux; - setivalue(&aux, n); - luaV_finishset(L, t, &aux, s2v(L->top.p - 1), slot); + TValue temp; + setivalue(&temp, n); + luaV_finishset1(L, t, &temp, s2v(L->top.p - 1), aux); } L->top.p--; /* pop value */ lua_unlock(L); diff --git a/ltable.c b/ltable.c index 8fd83fda..902f05a7 100644 --- a/ltable.c +++ b/ltable.c @@ -719,15 +719,7 @@ void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) { } -/* -** Search function for integers. If integer is inside 'alimit', get it -** directly from the array part. Otherwise, if 'alimit' is not equal to -** the real size of the array, key still can be in the array part. In -** this case, try to avoid a call to 'luaH_realasize' when key is just -** one more than the limit (so that it can be incremented without -** changing the real size of the array). -*/ -const TValue *luaH_getint (Table *t, lua_Integer key) { +static const TValue *getintfromarray (Table *t, lua_Integer key) { if (l_castS2U(key) - 1u < t->alimit) /* 'key' in [1, t->alimit]? */ return &t->array[key - 1]; else if (!limitequalsasize(t) && /* key still may be in the array part? */ @@ -736,19 +728,40 @@ const TValue *luaH_getint (Table *t, lua_Integer key) { t->alimit = cast_uint(key); /* probably '#t' is here now */ return &t->array[key - 1]; } - else { - 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; - } + else return NULL; /* key is not in the array part */ +} + + +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; } - return &absentkey; } + return &absentkey; +} + + +/* +** Search function for integers. If integer is inside 'alimit', get it +** directly from the array part. Otherwise, if 'alimit' is not equal to +** the real size of the array, key still can be in the array part. In +** this case, try to avoid a call to 'luaH_realasize' when key is just +** one more than the limit (so that it can be incremented without +** changing the real size of the array). +*/ +const TValue *luaH_getint (Table *t, lua_Integer key) { + const TValue *slot = getintfromarray(t, key); + if (slot != NULL) + return slot; + else + return getintfromhash(t, key); } @@ -832,6 +845,58 @@ int luaH_get1 (Table *t, const TValue *key, TValue *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_setint1 (Table *t, lua_Integer key, TValue *val) { + const TValue *slot = getintfromarray(t, key); + if (slot != NULL) { + if (!ttisnil(slot)) { + setobj(((lua_State*)NULL), cast(TValue*, slot), 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_setshortstr1 (Table *t, TString *key, TValue *val) { + return finishnodeset(t, luaH_getshortstr(t, key), val); +} + + +int luaH_setstr1 (Table *t, TString *key, TValue *val) { + return finishnodeset(t, luaH_getstr(t, key), val); +} + + +int luaH_set1 (Table *t, const TValue *key, TValue *val) { + switch (ttypetag(key)) { + case LUA_VSHRSTR: return luaH_setshortstr1(t, tsvalue(key), val); + case LUA_VNUMINT: return luaH_setint1(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_setint1(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"). @@ -847,6 +912,21 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key, } +void luaH_finishset1 (lua_State *L, Table *t, const TValue *key, + TValue *value, int aux) { + if (aux == HNOTFOUND) { + luaH_newkey(L, t, key, value); + } + else if (aux > 0) { /* regular Node? */ + setobj2t(L, gval(gnode(t, aux - HFIRSTNODE)), value); + } + else { /* array entry */ + aux = ~aux; /* real index */ + val2arr(t, aux, getArrTag(t, aux), value); + } +} + + /* ** beware: when using this function you probably need to check a GC ** barrier and invalidate the TM cache. diff --git a/ltable.h b/ltable.h index c8a8c5e7..b9bb416a 100644 --- a/ltable.h +++ b/ltable.h @@ -39,6 +39,7 @@ #define HOK 0 #define HNOTFOUND 1 #define HNOTATABLE 2 +#define HFIRSTNODE 3 /* fast access to components of array values */ @@ -50,12 +51,20 @@ #define arr2val(h,k,tag,res) \ ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,k)) +#define val2arr(h,k,tag,val) \ + (*tag = (val)->tt_, *getArrVal(h,k) = (val)->value_) + LUAI_FUNC int luaH_getshortstr1 (Table *t, TString *key, TValue *res); LUAI_FUNC int luaH_getstr1 (Table *t, TString *key, TValue *res); LUAI_FUNC int luaH_get1 (Table *t, const TValue *key, TValue *res); LUAI_FUNC int luaH_getint1 (Table *t, lua_Integer key, TValue *res); +LUAI_FUNC int luaH_setint1 (Table *t, lua_Integer key, TValue *val); +LUAI_FUNC int luaH_setshortstr1 (Table *t, TString *key, TValue *val); +LUAI_FUNC int luaH_setstr1 (Table *t, TString *key, TValue *val); +LUAI_FUNC int luaH_set1 (Table *t, const TValue *key, TValue *val); + LUAI_FUNC const TValue *luaH_getint (Table *t, lua_Integer key); LUAI_FUNC void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value); @@ -68,6 +77,8 @@ LUAI_FUNC void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value); LUAI_FUNC void luaH_finishset (lua_State *L, Table *t, const TValue *key, const TValue *slot, TValue *value); +LUAI_FUNC void luaH_finishset1 (lua_State *L, Table *t, const TValue *key, + TValue *value, int aux); LUAI_FUNC Table *luaH_new (lua_State *L); LUAI_FUNC void luaH_resize (lua_State *L, Table *t, unsigned int nasize, unsigned int nhsize); diff --git a/lvm.c b/lvm.c index ee386847..f5934025 100644 --- a/lvm.c +++ b/lvm.c @@ -325,17 +325,16 @@ void luaV_finishget1 (lua_State *L, const TValue *t, TValue *key, StkId val, ** is no such entry. (The value at 'slot' must be empty, otherwise ** 'luaV_fastget' would have done the job.) */ -void luaV_finishset (lua_State *L, const TValue *t, TValue *key, - TValue *val, const TValue *slot) { +void luaV_finishset1 (lua_State *L, const TValue *t, TValue *key, + TValue *val, int aux) { int loop; /* counter to avoid infinite loops */ for (loop = 0; loop < MAXTAGLOOP; loop++) { const TValue *tm; /* '__newindex' metamethod */ - if (slot != NULL) { /* is 't' a table? */ + if (aux != HNOTATABLE) { /* is 't' a table? */ Table *h = hvalue(t); /* save 't' table */ - lua_assert(isempty(slot)); /* slot must be empty */ tm = fasttm(L, h->metatable, TM_NEWINDEX); /* get metamethod */ if (tm == NULL) { /* no metamethod? */ - luaH_finishset(L, h, key, slot, val); /* set new value */ + luaH_finishset1(L, h, key, val, aux); /* set new value */ invalidateTMcache(h); luaC_barrierback(L, obj2gco(h), val); return; @@ -353,10 +352,9 @@ void luaV_finishset (lua_State *L, const TValue *t, TValue *key, return; } t = tm; /* else repeat assignment over 'tm' */ - if (luaV_fastget(L, t, key, slot, luaH_get)) { - luaV_finishfastset(L, t, slot, val); + luaV_fastset1(t, key, val, aux, luaH_set1); + if (aux == HOK) return; /* done */ - } /* else 'return luaV_finishset(L, t, key, val, slot)' (loop) */ } luaG_runerror(L, "'__newindex' chain too long; possible loop"); @@ -1296,59 +1294,61 @@ void luaV_execute (lua_State *L, CallInfo *ci) { vmbreak; } vmcase(OP_SETTABUP) { - const TValue *slot; + int aux; TValue *upval = cl->upvals[GETARG_A(i)]->v.p; TValue *rb = KB(i); TValue *rc = RKC(i); TString *key = tsvalue(rb); /* key must be a string */ - if (luaV_fastget(L, upval, key, slot, luaH_getshortstr)) { - luaV_finishfastset(L, upval, slot, rc); - } + luaV_fastset1(upval, key, rc, aux, luaH_setshortstr1); + if (aux == HOK) + luaV_finishfastset1(L, upval, rc); else - Protect(luaV_finishset(L, upval, rb, rc, slot)); + Protect(luaV_finishset1(L, upval, rb, rc, aux)); vmbreak; } vmcase(OP_SETTABLE) { StkId ra = RA(i); - const TValue *slot; + int aux; TValue *rb = vRB(i); /* key (table is in 'ra') */ TValue *rc = RKC(i); /* value */ - lua_Unsigned n; - if (ttisinteger(rb) /* fast track for integers? */ - ? (cast_void(n = ivalue(rb)), luaV_fastgeti(L, s2v(ra), n, slot)) - : luaV_fastget(L, s2v(ra), rb, slot, luaH_get)) { - luaV_finishfastset(L, s2v(ra), slot, rc); + if (ttisinteger(rb)) { /* fast track for integers? */ + luaV_fastseti1(s2v(ra), ivalue(rb), rc, aux); + } + else { + luaV_fastset1(s2v(ra), rb, rc, aux, luaH_set1); } + if (aux == HOK) + luaV_finishfastset1(L, s2v(ra), rc); else - Protect(luaV_finishset(L, s2v(ra), rb, rc, slot)); + Protect(luaV_finishset1(L, s2v(ra), rb, rc, aux)); vmbreak; } vmcase(OP_SETI) { StkId ra = RA(i); - const TValue *slot; - int c = GETARG_B(i); + int aux; + int b = GETARG_B(i); TValue *rc = RKC(i); - if (luaV_fastgeti(L, s2v(ra), c, slot)) { - luaV_finishfastset(L, s2v(ra), slot, rc); - } + luaV_fastseti1(s2v(ra), b, rc, aux); + if (aux == HOK) + luaV_finishfastset1(L, s2v(ra), rc); else { TValue key; - setivalue(&key, c); - Protect(luaV_finishset(L, s2v(ra), &key, rc, slot)); + setivalue(&key, b); + Protect(luaV_finishset1(L, s2v(ra), &key, rc, aux)); } vmbreak; } vmcase(OP_SETFIELD) { StkId ra = RA(i); - const TValue *slot; + int aux; TValue *rb = KB(i); TValue *rc = RKC(i); TString *key = tsvalue(rb); /* key must be a string */ - if (luaV_fastget(L, s2v(ra), key, slot, luaH_getshortstr)) { - luaV_finishfastset(L, s2v(ra), slot, rc); - } + luaV_fastset1(s2v(ra), key, rc, aux, luaH_setshortstr1); + if (aux == HOK) + luaV_finishfastset1(L, s2v(ra), rc); else - Protect(luaV_finishset(L, s2v(ra), rb, rc, slot)); + Protect(luaV_finishset1(L, s2v(ra), rb, rc, aux)); vmbreak; } vmcase(OP_NEWTABLE) { diff --git a/lvm.h b/lvm.h index 704446c2..750a22b2 100644 --- a/lvm.h +++ b/lvm.h @@ -104,14 +104,27 @@ typedef enum { ? &hvalue(t)->array[k - 1] : luaH_getint(hvalue(t), k), \ !isempty(slot))) /* result not empty? */ -#define luaV_fastgeti1(t,k,val,aux) \ +#define luaV_fastgeti1(t,k,res,aux) \ 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); \ if (tagisempty(tag)) aux = HNOTFOUND; \ - else { arr2val(h, u, tag, val); aux = HOK; }} \ - else { aux = luaH_getint1(h, u, val); }} + else { arr2val(h, u, tag, res); aux = HOK; }} \ + else { aux = luaH_getint1(h, u, res); }} + + +#define luaV_fastset1(t,k,val,aux,f) \ + (aux = (!ttistable(t) ? HNOTATABLE : f(hvalue(t), k, val))) + +#define luaV_fastseti1(t,k,val,aux) \ + 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); \ + if (tagisempty(*tag)) aux = ~cast_int(u); \ + else { val2arr(h, u, tag, val); aux = HOK; }} \ + else { aux = luaH_setint1(h, u, val); }} /* @@ -122,6 +135,8 @@ typedef enum { { setobj2t(L, cast(TValue *,slot), v); \ luaC_barrierback(L, gcvalue(t), v); } +#define luaV_finishfastset1(L,t,v) luaC_barrierback(L, gcvalue(t), v) + /* ** Shift right is the same as shift left with a negative 'y' @@ -140,8 +155,8 @@ LUAI_FUNC int luaV_tointegerns (const TValue *obj, lua_Integer *p, LUAI_FUNC int luaV_flttointeger (lua_Number n, lua_Integer *p, F2Imod mode); LUAI_FUNC void luaV_finishget1 (lua_State *L, const TValue *t, TValue *key, StkId val, int aux); -LUAI_FUNC void luaV_finishset (lua_State *L, const TValue *t, TValue *key, - TValue *val, const TValue *slot); +LUAI_FUNC void luaV_finishset1 (lua_State *L, const TValue *t, TValue *key, + TValue *val, int aux); LUAI_FUNC void luaV_finishOp (lua_State *L); LUAI_FUNC void luaV_execute (lua_State *L, CallInfo *ci); LUAI_FUNC void luaV_concat (lua_State *L, int total); -- cgit v1.2.3-55-g6feb From 819bd51d87b799fdee029754c660dc9a5587ef57 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Tue, 16 May 2023 16:53:29 -0300 Subject: Some cleaning in the new table API --- lapi.c | 70 +++++++++++++++++++-------------------- lcode.c | 8 ++--- llex.c | 10 +++--- ltable.c | 102 +++++++++++++++++++++++++++++---------------------------- ltable.h | 37 ++++++++++++--------- ltm.c | 11 ++++--- lvm.c | 112 ++++++++++++++++++++++++++++++--------------------------------- lvm.h | 49 ++++++++-------------------- 8 files changed, 189 insertions(+), 210 deletions(-) (limited to 'ltable.h') diff --git a/lapi.c b/lapi.c index 97a9f272..4a3ba724 100644 --- a/lapi.c +++ b/lapi.c @@ -637,16 +637,16 @@ LUA_API int lua_pushthread (lua_State *L) { l_sinline int auxgetstr (lua_State *L, const TValue *t, const char *k) { - int aux; + int hres; TString *str = luaS_new(L, k); - luaV_fastget1(t, str, s2v(L->top.p), luaH_getstr1, aux); - if (aux == HOK) { + luaV_fastget(t, str, s2v(L->top.p), luaH_getstr, hres); + if (hres == HOK) { api_incr_top(L); } else { setsvalue2s(L, L->top.p, str); api_incr_top(L); - luaV_finishget1(L, t, s2v(L->top.p - 1), L->top.p - 1, aux); + luaV_finishget(L, t, s2v(L->top.p - 1), L->top.p - 1, hres); } lua_unlock(L); return ttype(s2v(L->top.p - 1)); @@ -672,13 +672,13 @@ LUA_API int lua_getglobal (lua_State *L, const char *name) { LUA_API int lua_gettable (lua_State *L, int idx) { - int aux; + int hres; TValue *t; lua_lock(L); t = index2value(L, idx); - luaV_fastget1(t, s2v(L->top.p - 1), s2v(L->top.p - 1), luaH_get1, aux); - if (aux != HOK) - luaV_finishget1(L, t, s2v(L->top.p - 1), L->top.p - 1, aux); + luaV_fastget(t, s2v(L->top.p - 1), s2v(L->top.p - 1), luaH_get, hres); + if (hres != HOK) + luaV_finishget(L, t, s2v(L->top.p - 1), L->top.p - 1, hres); lua_unlock(L); return ttype(s2v(L->top.p - 1)); } @@ -692,14 +692,14 @@ LUA_API int lua_getfield (lua_State *L, int idx, const char *k) { LUA_API int lua_geti (lua_State *L, int idx, lua_Integer n) { TValue *t; - int aux; + int hres; lua_lock(L); t = index2value(L, idx); - luaV_fastgeti1(t, n, s2v(L->top.p), aux); - if (aux != HOK) { + luaV_fastgeti(t, n, s2v(L->top.p), hres); + if (hres != HOK) { TValue key; setivalue(&key, n); - luaV_finishget1(L, t, &key, L->top.p, aux); + luaV_finishget(L, t, &key, L->top.p, hres); } api_incr_top(L); lua_unlock(L); @@ -707,11 +707,9 @@ LUA_API int lua_geti (lua_State *L, int idx, lua_Integer n) { } -l_sinline int finishrawget (lua_State *L, const TValue *val) { - if (isempty(val)) /* avoid copying empty items to the stack */ +l_sinline int finishrawget (lua_State *L, int hres) { + if (hres != HOK) /* avoid copying empty items to the stack */ setnilvalue(s2v(L->top.p)); - else - setobj2s(L, L->top.p, val); api_incr_top(L); lua_unlock(L); return ttype(s2v(L->top.p - 1)); @@ -727,13 +725,13 @@ static Table *gettable (lua_State *L, int idx) { LUA_API int lua_rawget (lua_State *L, int idx) { Table *t; - const TValue *val; + int hres; lua_lock(L); api_checknelems(L, 1); t = gettable(L, idx); - val = luaH_get(t, s2v(L->top.p - 1)); + hres = luaH_get(t, s2v(L->top.p - 1), s2v(L->top.p - 1)); L->top.p--; /* remove key */ - return finishrawget(L, val); + return finishrawget(L, hres); } @@ -741,7 +739,7 @@ LUA_API int lua_rawgeti (lua_State *L, int idx, lua_Integer n) { Table *t; lua_lock(L); t = gettable(L, idx); - return finishrawget(L, luaH_getint(t, n)); + return finishrawget(L, luaH_getint(t, n, s2v(L->top.p))); } @@ -751,7 +749,7 @@ LUA_API int lua_rawgetp (lua_State *L, int idx, const void *p) { lua_lock(L); t = gettable(L, idx); setpvalue(&k, cast_voidp(p)); - return finishrawget(L, luaH_get(t, &k)); + return finishrawget(L, luaH_get(t, &k, s2v(L->top.p))); } @@ -823,18 +821,18 @@ LUA_API int lua_getiuservalue (lua_State *L, int idx, int n) { ** t[k] = value at the top of the stack (where 'k' is a string) */ static void auxsetstr (lua_State *L, const TValue *t, const char *k) { - int aux; + int hres; TString *str = luaS_new(L, k); api_checknelems(L, 1); - luaV_fastset1(t, str, s2v(L->top.p - 1), aux, luaH_setstr1); - if (aux == HOK) { - luaV_finishfastset1(L, t, s2v(L->top.p - 1)); + luaV_fastset(t, str, s2v(L->top.p - 1), hres, luaH_psetstr); + if (hres == HOK) { + luaV_finishfastset(L, t, s2v(L->top.p - 1)); L->top.p--; /* pop value */ } else { setsvalue2s(L, L->top.p, str); /* push 'str' (to make it a TValue) */ api_incr_top(L); - luaV_finishset1(L, t, s2v(L->top.p - 1), s2v(L->top.p - 2), aux); + luaV_finishset(L, t, s2v(L->top.p - 1), s2v(L->top.p - 2), hres); L->top.p -= 2; /* pop value and key */ } lua_unlock(L); /* lock done by caller */ @@ -851,16 +849,16 @@ LUA_API void lua_setglobal (lua_State *L, const char *name) { LUA_API void lua_settable (lua_State *L, int idx) { TValue *t; - int aux; + int hres; lua_lock(L); api_checknelems(L, 2); t = index2value(L, idx); - luaV_fastset1(t, s2v(L->top.p - 2), s2v(L->top.p - 1), aux, luaH_set1); - if (aux == HOK) { - luaV_finishfastset1(L, t, s2v(L->top.p - 1)); + luaV_fastset(t, s2v(L->top.p - 2), s2v(L->top.p - 1), hres, luaH_pset); + if (hres == HOK) { + luaV_finishfastset(L, t, s2v(L->top.p - 1)); } else - luaV_finishset1(L, t, s2v(L->top.p - 2), s2v(L->top.p - 1), aux); + luaV_finishset(L, t, s2v(L->top.p - 2), s2v(L->top.p - 1), hres); L->top.p -= 2; /* pop index and value */ lua_unlock(L); } @@ -874,18 +872,18 @@ LUA_API void lua_setfield (lua_State *L, int idx, const char *k) { LUA_API void lua_seti (lua_State *L, int idx, lua_Integer n) { TValue *t; - int aux; + int hres; lua_lock(L); api_checknelems(L, 1); t = index2value(L, idx); - luaV_fastseti1(t, n, s2v(L->top.p - 1), aux); - if (aux == HOK) { - luaV_finishfastset1(L, t, s2v(L->top.p - 1)); + luaV_fastseti(t, n, s2v(L->top.p - 1), hres); + if (hres == HOK) { + luaV_finishfastset(L, t, s2v(L->top.p - 1)); } else { TValue temp; setivalue(&temp, n); - luaV_finishset1(L, t, &temp, s2v(L->top.p - 1), aux); + luaV_finishset(L, t, &temp, s2v(L->top.p - 1), hres); } L->top.p--; /* pop value */ lua_unlock(L); diff --git a/lcode.c b/lcode.c index 1a371ca9..25623df7 100644 --- a/lcode.c +++ b/lcode.c @@ -544,10 +544,10 @@ static int addk (FuncState *fs, TValue *key, TValue *v) { TValue val; lua_State *L = fs->ls->L; Proto *f = fs->f; - const TValue *idx = luaH_get(fs->ls->h, key); /* query scanner table */ + int aux = luaH_get(fs->ls->h, key, &val); /* query scanner table */ int k, oldsize; - if (ttisinteger(idx)) { /* is there an index there? */ - k = cast_int(ivalue(idx)); + if (aux == HOK && ttisinteger(&val)) { /* is there an index there? */ + k = cast_int(ivalue(&val)); /* correct value? (warning: must distinguish floats from integers!) */ if (k < fs->nk && ttypetag(&f->k[k]) == ttypetag(v) && luaV_rawequalobj(&f->k[k], v)) @@ -559,7 +559,7 @@ static int addk (FuncState *fs, TValue *key, TValue *v) { /* numerical value does not need GC barrier; table has no metatable, so it does not need to invalidate cache */ setivalue(&val, k); - luaH_finishset(L, fs->ls->h, key, idx, &val); + luaH_set(L, fs->ls->h, key, &val); luaM_growvector(L, f->k, k, f->sizek, TValue, MAXARG_Ax, "constants"); while (oldsize < f->sizek) setnilvalue(&f->k[oldsize++]); setobj(L, &f->k[k], v); diff --git a/llex.c b/llex.c index 5fc39a5c..9f20d3c8 100644 --- a/llex.c +++ b/llex.c @@ -134,13 +134,13 @@ l_noret luaX_syntaxerror (LexState *ls, const char *msg) { TString *luaX_newstring (LexState *ls, const char *str, size_t l) { lua_State *L = ls->L; TString *ts = luaS_newlstr(L, str, l); /* create new string */ - const TValue *o = luaH_getstr(ls->h, ts); - if (!ttisnil(o)) /* string already present? */ - ts = keystrval(nodefromval(o)); /* get saved copy */ - else { /* not in use yet */ + TString *oldts = luaH_getstrkey(ls->h, ts); + if (oldts != NULL) /* string already present? */ + return oldts; /* use it */ + else { /* create a new entry */ TValue *stv = s2v(L->top.p++); /* reserve stack space for string */ setsvalue(L, stv, ts); /* temporarily anchor the string */ - luaH_finishset(L, ls->h, stv, o, stv); /* t[string] = string */ + luaH_set(L, ls->h, stv, stv); /* t[string] = string */ /* table is not a metatable, so it does not need to invalidate cache */ luaC_checkGC(L); L->top.p--; /* remove string from stack */ diff --git a/ltable.c b/ltable.c index 902f05a7..3f95ab0c 100644 --- a/ltable.c +++ b/ltable.c @@ -756,7 +756,7 @@ static const TValue *getintfromhash (Table *t, lua_Integer key) { ** one more than the limit (so that it can be incremented without ** changing the real size of the array). */ -const TValue *luaH_getint (Table *t, lua_Integer key) { +static const TValue *Hgetint (Table *t, lua_Integer key) { const TValue *slot = getintfromarray(t, key); if (slot != NULL) return slot; @@ -775,15 +775,15 @@ static int finishnodeget (const TValue *val, TValue *res) { } -int luaH_getint1 (Table *t, lua_Integer key, TValue *res) { - return finishnodeget(luaH_getint(t, key), res); +int luaH_getint (Table *t, lua_Integer key, TValue *res) { + return finishnodeget(Hgetint(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 */ @@ -799,14 +799,14 @@ const TValue *luaH_getshortstr (Table *t, TString *key) { } -int luaH_getshortstr1 (Table *t, TString *key, TValue *res) { - return finishnodeget(luaH_getshortstr(t, key), res); +int luaH_getshortstr (Table *t, TString *key, TValue *res) { + return finishnodeget(luaH_Hgetshortstr(t, key), res); } -const TValue *luaH_getstr (Table *t, TString *key) { +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); @@ -815,23 +815,32 @@ const TValue *luaH_getstr (Table *t, TString *key) { } -int luaH_getstr1 (Table *t, TString *key, TValue *res) { - return finishnodeget(luaH_getstr(t, key), res); +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) { +static const TValue *Hget (Table *t, const TValue *key) { switch (ttypetag(key)) { - case LUA_VSHRSTR: return luaH_getshortstr(t, tsvalue(key)); - case LUA_VNUMINT: return luaH_getint(t, ivalue(key)); + case LUA_VSHRSTR: return luaH_Hgetshortstr(t, tsvalue(key)); + case LUA_VNUMINT: return Hgetint(t, ivalue(key)); case LUA_VNIL: return &absentkey; case LUA_VNUMFLT: { lua_Integer k; if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */ - return luaH_getint(t, k); /* use specialized version */ + return Hgetint(t, k); /* use specialized version */ /* else... */ } /* FALLTHROUGH */ default: @@ -840,8 +849,8 @@ const TValue *luaH_get (Table *t, const TValue *key) { } -int luaH_get1 (Table *t, const TValue *key, TValue *res) { - return finishnodeget(luaH_get(t, key), res); +int luaH_get (Table *t, const TValue *key, TValue *res) { + return finishnodeget(Hget(t, key), res); } @@ -856,7 +865,7 @@ static int finishnodeset (Table *t, const TValue *slot, TValue *val) { } -int luaH_setint1 (Table *t, lua_Integer key, TValue *val) { +int luaH_psetint (Table *t, lua_Integer key, TValue *val) { const TValue *slot = getintfromarray(t, key); if (slot != NULL) { if (!ttisnil(slot)) { @@ -871,25 +880,25 @@ int luaH_setint1 (Table *t, lua_Integer key, TValue *val) { } -int luaH_setshortstr1 (Table *t, TString *key, TValue *val) { - return finishnodeset(t, luaH_getshortstr(t, key), val); +int luaH_psetshortstr (Table *t, TString *key, TValue *val) { + return finishnodeset(t, luaH_Hgetshortstr(t, key), val); } -int luaH_setstr1 (Table *t, TString *key, TValue *val) { - return finishnodeset(t, luaH_getstr(t, key), val); +int luaH_psetstr (Table *t, TString *key, TValue *val) { + return finishnodeset(t, Hgetstr(t, key), val); } -int luaH_set1 (Table *t, const TValue *key, TValue *val) { +int luaH_pset (Table *t, const TValue *key, TValue *val) { switch (ttypetag(key)) { - case LUA_VSHRSTR: return luaH_setshortstr1(t, tsvalue(key), val); - case LUA_VNUMINT: return luaH_setint1(t, ivalue(key), val); + 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_setint1(t, k, val); /* use specialized version */ + return luaH_psetint(t, k, val); /* use specialized version */ /* else... */ } /* FALLTHROUGH */ default: @@ -903,26 +912,20 @@ int luaH_set1 (Table *t, const TValue *key, TValue *val) { ** 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)) - luaH_newkey(L, t, key, value); - else - setobj2t(L, cast(TValue *, slot), value); -} -void luaH_finishset1 (lua_State *L, Table *t, const TValue *key, - TValue *value, int aux) { - if (aux == HNOTFOUND) { +void luaH_finishset (lua_State *L, Table *t, const TValue *key, + TValue *value, int hres) { + lua_assert(hres != HOK); + if (hres == HNOTFOUND) { luaH_newkey(L, t, key, value); } - else if (aux > 0) { /* regular Node? */ - setobj2t(L, gval(gnode(t, aux - HFIRSTNODE)), value); + else if (hres > 0) { /* regular Node? */ + setobj2t(L, gval(gnode(t, hres - HFIRSTNODE)), value); } else { /* array entry */ - aux = ~aux; /* real index */ - val2arr(t, aux, getArrTag(t, aux), value); + hres = ~hres; /* real index */ + val2arr(t, hres, getArrTag(t, hres), value); } } @@ -932,20 +935,19 @@ void luaH_finishset1 (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); } @@ -971,16 +973,16 @@ 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 (isempty(Hgetint(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 (!isempty(Hgetint(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 (isempty(Hgetint(t, m))) j = m; else i = m; } return i; @@ -1071,7 +1073,7 @@ 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)))) + if (isdummy(t) || isempty(Hgetint(t, cast(lua_Integer, limit + 1)))) return limit; /* 'limit + 1' is absent */ else /* 'limit + 1' is also present */ return hash_search(t, limit); diff --git a/ltable.h b/ltable.h index b9bb416a..5ec7b447 100644 --- a/ltable.h +++ b/ltable.h @@ -35,12 +35,22 @@ #define nodefromval(v) cast(Node *, (v)) -/* results from get/set */ +/* results from get/pset */ #define HOK 0 #define HNOTFOUND 1 #define HNOTATABLE 2 #define HFIRSTNODE 3 +/* +** Besides these values, pset (pre-set) operations may also return an +** encoding of where the value should go (usually called 'hres'). That +** means that there is a slot with that key but with no value. (pset +** cannot set that value because there might be a metamethod.) If the +** slot is in the hash part, the encoding is (HFIRSTNODE + hash index); +** if the slot is in the array part, the encoding is (~array index). +*/ + + /* fast access to components of array values */ #define getArrTag(t,k) (&(t)->array[k - 1].tt_) @@ -55,29 +65,26 @@ (*tag = (val)->tt_, *getArrVal(h,k) = (val)->value_) -LUAI_FUNC int luaH_getshortstr1 (Table *t, TString *key, TValue *res); -LUAI_FUNC int luaH_getstr1 (Table *t, TString *key, TValue *res); -LUAI_FUNC int luaH_get1 (Table *t, const TValue *key, TValue *res); -LUAI_FUNC int luaH_getint1 (Table *t, lua_Integer key, TValue *res); +LUAI_FUNC int luaH_getshortstr (Table *t, TString *key, TValue *res); +LUAI_FUNC int luaH_getstr (Table *t, TString *key, TValue *res); +LUAI_FUNC int luaH_get (Table *t, const TValue *key, TValue *res); +LUAI_FUNC int luaH_getint (Table *t, lua_Integer key, TValue *res); + +LUAI_FUNC TString *luaH_getstrkey (Table *t, TString *key); -LUAI_FUNC int luaH_setint1 (Table *t, lua_Integer key, TValue *val); -LUAI_FUNC int luaH_setshortstr1 (Table *t, TString *key, TValue *val); -LUAI_FUNC int luaH_setstr1 (Table *t, TString *key, TValue *val); -LUAI_FUNC int luaH_set1 (Table *t, const TValue *key, TValue *val); +LUAI_FUNC int luaH_psetint (Table *t, lua_Integer key, TValue *val); +LUAI_FUNC int luaH_psetshortstr (Table *t, TString *key, TValue *val); +LUAI_FUNC int luaH_psetstr (Table *t, TString *key, TValue *val); +LUAI_FUNC int luaH_pset (Table *t, const TValue *key, TValue *val); -LUAI_FUNC const TValue *luaH_getint (Table *t, lua_Integer key); LUAI_FUNC void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value); -LUAI_FUNC const TValue *luaH_getshortstr (Table *t, TString *key); -LUAI_FUNC const TValue *luaH_getstr (Table *t, TString *key); -LUAI_FUNC const TValue *luaH_get (Table *t, const TValue *key); +LUAI_FUNC const TValue *luaH_Hgetshortstr (Table *t, TString *key); LUAI_FUNC void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value); LUAI_FUNC void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value); LUAI_FUNC void luaH_finishset (lua_State *L, Table *t, const TValue *key, - const TValue *slot, TValue *value); -LUAI_FUNC void luaH_finishset1 (lua_State *L, Table *t, const TValue *key, TValue *value, int aux); LUAI_FUNC Table *luaH_new (lua_State *L); LUAI_FUNC void luaH_resize (lua_State *L, Table *t, unsigned int nasize, diff --git a/ltm.c b/ltm.c index 07a06081..fce6245c 100644 --- a/ltm.c +++ b/ltm.c @@ -58,7 +58,7 @@ void luaT_init (lua_State *L) { ** tag methods */ const TValue *luaT_gettm (Table *events, TMS event, TString *ename) { - const TValue *tm = luaH_getshortstr(events, ename); + const TValue *tm = luaH_Hgetshortstr(events, ename); lua_assert(event <= TM_EQ); if (notm(tm)) { /* no tag method? */ events->flags |= cast_byte(1u<mt[ttype(o)]; } - return (mt ? luaH_getshortstr(mt, G(L)->tmname[event]) : &G(L)->nilvalue); + return (mt ? luaH_Hgetshortstr(mt, G(L)->tmname[event]) : &G(L)->nilvalue); } @@ -92,9 +92,10 @@ const char *luaT_objtypename (lua_State *L, const TValue *o) { Table *mt; if ((ttistable(o) && (mt = hvalue(o)->metatable) != NULL) || (ttisfulluserdata(o) && (mt = uvalue(o)->metatable) != NULL)) { - const TValue *name = luaH_getshortstr(mt, luaS_new(L, "__name")); - if (ttisstring(name)) /* is '__name' a string? */ - return getstr(tsvalue(name)); /* use it as type name */ + TValue name; + int hres = luaH_getshortstr(mt, luaS_new(L, "__name"), &name); + if (hres == HOK && ttisstring(&name)) /* is '__name' a string? */ + return getstr(tsvalue(&name)); /* use it as type name */ } return ttypename(ttype(o)); /* else use standard type name */ } diff --git a/lvm.c b/lvm.c index f5934025..96413718 100644 --- a/lvm.c +++ b/lvm.c @@ -281,15 +281,13 @@ static int floatforloop (StkId ra) { /* ** Finish the table access 'val = t[key]'. -** if 'slot' is NULL, 't' is not a table; otherwise, 'slot' points to -** t[k] entry (which must be empty). */ -void luaV_finishget1 (lua_State *L, const TValue *t, TValue *key, StkId val, - int aux) { +void luaV_finishget (lua_State *L, const TValue *t, TValue *key, StkId val, + int hres) { int loop; /* counter to avoid infinite loops */ const TValue *tm; /* metamethod */ for (loop = 0; loop < MAXTAGLOOP; loop++) { - if (aux == HNOTATABLE) { /* 't' is not a table? */ + if (hres == HNOTATABLE) { /* 't' is not a table? */ lua_assert(!ttistable(t)); tm = luaT_gettmbyobj(L, t, TM_INDEX); if (l_unlikely(notm(tm))) @@ -309,8 +307,8 @@ void luaV_finishget1 (lua_State *L, const TValue *t, TValue *key, StkId val, return; } t = tm; /* else try to access 'tm[key]' */ - luaV_fastget1(t, key, s2v(val), luaH_get1, aux); - if (aux == HOK) + luaV_fastget(t, key, s2v(val), luaH_get, hres); + if (hres == HOK) return; /* done */ /* else repeat (tail call 'luaV_finishget') */ } @@ -320,21 +318,17 @@ void luaV_finishget1 (lua_State *L, const TValue *t, TValue *key, StkId val, /* ** Finish a table assignment 't[key] = val'. -** If 'slot' is NULL, 't' is not a table. Otherwise, 'slot' points -** to the entry 't[key]', or to a value with an absent key if there -** is no such entry. (The value at 'slot' must be empty, otherwise -** 'luaV_fastget' would have done the job.) */ -void luaV_finishset1 (lua_State *L, const TValue *t, TValue *key, - TValue *val, int aux) { +void luaV_finishset (lua_State *L, const TValue *t, TValue *key, + TValue *val, int hres) { int loop; /* counter to avoid infinite loops */ for (loop = 0; loop < MAXTAGLOOP; loop++) { const TValue *tm; /* '__newindex' metamethod */ - if (aux != HNOTATABLE) { /* is 't' a table? */ + if (hres != HNOTATABLE) { /* is 't' a table? */ Table *h = hvalue(t); /* save 't' table */ tm = fasttm(L, h->metatable, TM_NEWINDEX); /* get metamethod */ if (tm == NULL) { /* no metamethod? */ - luaH_finishset1(L, h, key, val, aux); /* set new value */ + luaH_finishset(L, h, key, val, hres); /* set new value */ invalidateTMcache(h); luaC_barrierback(L, obj2gco(h), val); return; @@ -352,8 +346,8 @@ void luaV_finishset1 (lua_State *L, const TValue *t, TValue *key, return; } t = tm; /* else repeat assignment over 'tm' */ - luaV_fastset1(t, key, val, aux, luaH_set1); - if (aux == HOK) + luaV_fastset(t, key, val, hres, luaH_pset); + if (hres == HOK) return; /* done */ /* else 'return luaV_finishset(L, t, key, val, slot)' (loop) */ } @@ -1249,36 +1243,36 @@ void luaV_execute (lua_State *L, CallInfo *ci) { TValue *upval = cl->upvals[GETARG_B(i)]->v.p; TValue *rc = KC(i); TString *key = tsvalue(rc); /* key must be a string */ - int aux; - luaV_fastget1(upval, key, s2v(ra), luaH_getshortstr1, aux); - if (aux != HOK) - Protect(luaV_finishget1(L, upval, rc, ra, aux)); + int hres; + luaV_fastget(upval, key, s2v(ra), luaH_getshortstr, hres); + if (hres != HOK) + Protect(luaV_finishget(L, upval, rc, ra, hres)); vmbreak; } vmcase(OP_GETTABLE) { StkId ra = RA(i); TValue *rb = vRB(i); TValue *rc = vRC(i); - int aux; + int hres; if (ttisinteger(rc)) { /* fast track for integers? */ - luaV_fastgeti1(rb, ivalue(rc), s2v(ra), aux); + luaV_fastgeti(rb, ivalue(rc), s2v(ra), hres); } else - luaV_fastget1(rb, rc, s2v(ra), luaH_get1, aux); - if (aux != HOK) /* fast track for integers? */ - Protect(luaV_finishget1(L, rb, rc, ra, aux)); + luaV_fastget(rb, rc, s2v(ra), luaH_get, hres); + if (hres != HOK) /* fast track for integers? */ + Protect(luaV_finishget(L, rb, rc, ra, hres)); vmbreak; } vmcase(OP_GETI) { StkId ra = RA(i); TValue *rb = vRB(i); int c = GETARG_C(i); - int aux; - luaV_fastgeti1(rb, c, s2v(ra), aux); - if (aux != HOK) { + int hres; + luaV_fastgeti(rb, c, s2v(ra), hres); + if (hres != HOK) { TValue key; setivalue(&key, c); - Protect(luaV_finishget1(L, rb, &key, ra, aux)); + Protect(luaV_finishget(L, rb, &key, ra, hres)); } vmbreak; } @@ -1287,68 +1281,68 @@ void luaV_execute (lua_State *L, CallInfo *ci) { TValue *rb = vRB(i); TValue *rc = KC(i); TString *key = tsvalue(rc); /* key must be a string */ - int aux; - luaV_fastget1(rb, key, s2v(ra), luaH_getshortstr1, aux); - if (aux != HOK) - Protect(luaV_finishget1(L, rb, rc, ra, aux)); + int hres; + luaV_fastget(rb, key, s2v(ra), luaH_getshortstr, hres); + if (hres != HOK) + Protect(luaV_finishget(L, rb, rc, ra, hres)); vmbreak; } vmcase(OP_SETTABUP) { - int aux; + int hres; TValue *upval = cl->upvals[GETARG_A(i)]->v.p; TValue *rb = KB(i); TValue *rc = RKC(i); TString *key = tsvalue(rb); /* key must be a string */ - luaV_fastset1(upval, key, rc, aux, luaH_setshortstr1); - if (aux == HOK) - luaV_finishfastset1(L, upval, rc); + luaV_fastset(upval, key, rc, hres, luaH_psetshortstr); + if (hres == HOK) + luaV_finishfastset(L, upval, rc); else - Protect(luaV_finishset1(L, upval, rb, rc, aux)); + Protect(luaV_finishset(L, upval, rb, rc, hres)); vmbreak; } vmcase(OP_SETTABLE) { StkId ra = RA(i); - int aux; + int hres; TValue *rb = vRB(i); /* key (table is in 'ra') */ TValue *rc = RKC(i); /* value */ if (ttisinteger(rb)) { /* fast track for integers? */ - luaV_fastseti1(s2v(ra), ivalue(rb), rc, aux); + luaV_fastseti(s2v(ra), ivalue(rb), rc, hres); } else { - luaV_fastset1(s2v(ra), rb, rc, aux, luaH_set1); + luaV_fastset(s2v(ra), rb, rc, hres, luaH_pset); } - if (aux == HOK) - luaV_finishfastset1(L, s2v(ra), rc); + if (hres == HOK) + luaV_finishfastset(L, s2v(ra), rc); else - Protect(luaV_finishset1(L, s2v(ra), rb, rc, aux)); + Protect(luaV_finishset(L, s2v(ra), rb, rc, hres)); vmbreak; } vmcase(OP_SETI) { StkId ra = RA(i); - int aux; + int hres; int b = GETARG_B(i); TValue *rc = RKC(i); - luaV_fastseti1(s2v(ra), b, rc, aux); - if (aux == HOK) - luaV_finishfastset1(L, s2v(ra), rc); + luaV_fastseti(s2v(ra), b, rc, hres); + if (hres == HOK) + luaV_finishfastset(L, s2v(ra), rc); else { TValue key; setivalue(&key, b); - Protect(luaV_finishset1(L, s2v(ra), &key, rc, aux)); + Protect(luaV_finishset(L, s2v(ra), &key, rc, hres)); } vmbreak; } vmcase(OP_SETFIELD) { StkId ra = RA(i); - int aux; + int hres; TValue *rb = KB(i); TValue *rc = RKC(i); TString *key = tsvalue(rb); /* key must be a string */ - luaV_fastset1(s2v(ra), key, rc, aux, luaH_setshortstr1); - if (aux == HOK) - luaV_finishfastset1(L, s2v(ra), rc); + luaV_fastset(s2v(ra), key, rc, hres, luaH_psetshortstr); + if (hres == HOK) + luaV_finishfastset(L, s2v(ra), rc); else - Protect(luaV_finishset1(L, s2v(ra), rb, rc, aux)); + Protect(luaV_finishset(L, s2v(ra), rb, rc, hres)); vmbreak; } vmcase(OP_NEWTABLE) { @@ -1372,14 +1366,14 @@ void luaV_execute (lua_State *L, CallInfo *ci) { } vmcase(OP_SELF) { StkId ra = RA(i); - int aux; + int hres; TValue *rb = vRB(i); TValue *rc = RKC(i); TString *key = tsvalue(rc); /* key must be a string */ setobj2s(L, ra + 1, rb); - luaV_fastget1(rb, key, s2v(ra), luaH_getstr1, aux); - if (aux != HOK) - Protect(luaV_finishget1(L, rb, rc, ra, aux)); + luaV_fastget(rb, key, s2v(ra), luaH_getstr, hres); + if (hres != HOK) + Protect(luaV_finishget(L, rb, rc, ra, hres)); vmbreak; } vmcase(OP_ADDI) { diff --git a/lvm.h b/lvm.h index 750a22b2..8808c942 100644 --- a/lvm.h +++ b/lvm.h @@ -76,20 +76,9 @@ typedef enum { /* -** fast track for 'gettable': if 't' is a table and 't[k]' is present, -** return 1 with 'slot' pointing to 't[k]' (position of final result). -** Otherwise, return 0 (meaning it will have to check metamethod) -** with 'slot' pointing to an empty 't[k]' (if 't' is a table) or NULL -** (otherwise). 'f' is the raw get function to use. +** fast track for 'gettable' */ -#define luaV_fastget(L,t,k,slot,f) \ - (!ttistable(t) \ - ? (slot = NULL, 0) /* not a table; 'slot' is NULL and result is 0 */ \ - : (slot = f(hvalue(t), k), /* else, do raw access */ \ - !isempty(slot))) /* result not empty? */ - - -#define luaV_fastget1(t,k,res,f, aux) \ +#define luaV_fastget(t,k,res,f, aux) \ (aux = (!ttistable(t) ? HNOTATABLE : f(hvalue(t), k, res))) @@ -97,45 +86,33 @@ typedef enum { ** Special case of 'luaV_fastget' for integers, inlining the fast case ** of 'luaH_getint'. */ -#define luaV_fastgeti(L,t,k,slot) \ - (!ttistable(t) \ - ? (slot = NULL, 0) /* not a table; 'slot' is NULL and result is 0 */ \ - : (slot = (l_castS2U(k) - 1u < hvalue(t)->alimit) \ - ? &hvalue(t)->array[k - 1] : luaH_getint(hvalue(t), k), \ - !isempty(slot))) /* result not empty? */ - -#define luaV_fastgeti1(t,k,res,aux) \ +#define luaV_fastgeti(t,k,res,aux) \ 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); \ if (tagisempty(tag)) aux = HNOTFOUND; \ else { arr2val(h, u, tag, res); aux = HOK; }} \ - else { aux = luaH_getint1(h, u, res); }} + else { aux = luaH_getint(h, u, res); }} -#define luaV_fastset1(t,k,val,aux,f) \ +#define luaV_fastset(t,k,val,aux,f) \ (aux = (!ttistable(t) ? HNOTATABLE : f(hvalue(t), k, val))) -#define luaV_fastseti1(t,k,val,aux) \ +#define luaV_fastseti(t,k,val,aux) \ 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); \ if (tagisempty(*tag)) aux = ~cast_int(u); \ else { val2arr(h, u, tag, val); aux = HOK; }} \ - else { aux = luaH_setint1(h, u, val); }} + else { aux = luaH_psetint(h, u, val); }} /* -** Finish a fast set operation (when fast get succeeds). In that case, -** 'slot' points to the place to put the value. +** Finish a fast set operation (when fast set succeeds). */ -#define luaV_finishfastset(L,t,slot,v) \ - { setobj2t(L, cast(TValue *,slot), v); \ - luaC_barrierback(L, gcvalue(t), v); } - -#define luaV_finishfastset1(L,t,v) luaC_barrierback(L, gcvalue(t), v) +#define luaV_finishfastset(L,t,v) luaC_barrierback(L, gcvalue(t), v) /* @@ -153,10 +130,10 @@ LUAI_FUNC int luaV_tointeger (const TValue *obj, lua_Integer *p, F2Imod mode); LUAI_FUNC int luaV_tointegerns (const TValue *obj, lua_Integer *p, F2Imod mode); LUAI_FUNC int luaV_flttointeger (lua_Number n, lua_Integer *p, F2Imod mode); -LUAI_FUNC void luaV_finishget1 (lua_State *L, const TValue *t, TValue *key, - StkId val, int aux); -LUAI_FUNC void luaV_finishset1 (lua_State *L, const TValue *t, TValue *key, - TValue *val, int aux); +LUAI_FUNC void luaV_finishget (lua_State *L, const TValue *t, TValue *key, + StkId val, int aux); +LUAI_FUNC void luaV_finishset (lua_State *L, const TValue *t, TValue *key, + TValue *val, int aux); LUAI_FUNC void luaV_finishOp (lua_State *L); LUAI_FUNC void luaV_execute (lua_State *L, CallInfo *ci); LUAI_FUNC void luaV_concat (lua_State *L, int total); -- cgit v1.2.3-55-g6feb From 43c8e5bded052801f54a7439d18933b83570eb82 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Mon, 30 Oct 2023 14:25:59 -0300 Subject: Full abstraction for representation of array values --- lapi.c | 31 ++++++++--------- lgc.c | 25 ++++++++++---- lobject.h | 5 ++- lstate.c | 7 ++-- ltable.c | 116 ++++++++++++++++++++++++++++++++------------------------------ ltable.h | 21 +++++++++--- ltests.c | 10 ++++-- lvm.c | 2 +- lvm.h | 4 +-- 9 files changed, 128 insertions(+), 93 deletions(-) (limited to 'ltable.h') diff --git a/lapi.c b/lapi.c index 4a3ba724..99c8473e 100644 --- a/lapi.c +++ b/lapi.c @@ -653,21 +653,17 @@ l_sinline int auxgetstr (lua_State *L, const TValue *t, const char *k) { } -/* -** Get the global table in the registry. Since all predefined -** indices in the registry were inserted right when the registry -** was created and never removed, they must always be in the array -** part of the registry. -*/ -#define getGtable(L) \ - (&hvalue(&G(L)->l_registry)->array[LUA_RIDX_GLOBALS - 1]) +static void getGlobalTable (lua_State *L, TValue *gt) { + Table *registry = hvalue(&G(L)->l_registry); + luaH_getint(registry, LUA_RIDX_GLOBALS, gt); +} LUA_API int lua_getglobal (lua_State *L, const char *name) { - const TValue *G; + TValue gt; lua_lock(L); - G = getGtable(L); - return auxgetstr(L, G, name); + getGlobalTable(L, >); + return auxgetstr(L, >, name); } @@ -840,10 +836,10 @@ static void auxsetstr (lua_State *L, const TValue *t, const char *k) { LUA_API void lua_setglobal (lua_State *L, const char *name) { - const TValue *G; + TValue gt; lua_lock(L); /* unlock done in 'auxsetstr' */ - G = getGtable(L); - auxsetstr(L, G, name); + getGlobalTable(L, >); + auxsetstr(L, >, name); } @@ -1093,10 +1089,11 @@ LUA_API int lua_load (lua_State *L, lua_Reader reader, void *data, LClosure *f = clLvalue(s2v(L->top.p - 1)); /* get new function */ if (f->nupvalues >= 1) { /* does it have an upvalue? */ /* get global table from registry */ - const TValue *gt = getGtable(L); + TValue gt; + getGlobalTable(L, >); /* set global table as 1st upvalue of 'f' (may be LUA_ENV) */ - setobj(L, f->upvals[0]->v.p, gt); - luaC_barrier(L, f->upvals[0], gt); + setobj(L, f->upvals[0]->v.p, >); + luaC_barrier(L, f->upvals[0], >); } } lua_unlock(L); diff --git a/lgc.c b/lgc.c index a3094ff5..813b08d5 100644 --- a/lgc.c +++ b/lgc.c @@ -91,6 +91,13 @@ #define gcvalueN(o) (iscollectable(o) ? gcvalue(o) : NULL) +/* +** Access to collectable objects in array part of tables +*/ +#define gcvalarr(t,i) \ + ((*getArrTag(t,i) & BIT_ISCOLLECTABLE) ? getArrVal(t,i)->gc : NULL) + + #define markvalue(g,o) { checkliveness(g->mainthread,o); \ if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); } @@ -486,9 +493,10 @@ static int traverseephemeron (global_State *g, Table *h, int inv) { unsigned int nsize = sizenode(h); /* traverse array part */ for (i = 0; i < asize; i++) { - if (valiswhite(&h->array[i])) { + GCObject *o = gcvalarr(h, i + 1); + if (o != NULL && iswhite(o)) { marked = 1; - reallymarkobject(g, gcvalue(&h->array[i])); + reallymarkobject(g, o); } } /* traverse hash part; if 'inv', traverse descending @@ -524,8 +532,11 @@ static void traversestrongtable (global_State *g, Table *h) { Node *n, *limit = gnodelast(h); unsigned int i; unsigned int asize = luaH_realasize(h); - for (i = 0; i < asize; i++) /* traverse array part */ - markvalue(g, &h->array[i]); + for (i = 0; i < asize; i++) { /* traverse array part */ + GCObject *o = gcvalarr(h, i + 1); + if (o != NULL && iswhite(o)) + reallymarkobject(g, o); + } for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ if (isempty(gval(n))) /* entry is empty? */ clearkey(n); /* clear its key */ @@ -746,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++) { - TValue *o = &h->array[i]; - if (iscleared(g, gcvalueN(o))) /* value was collected? */ - setempty(o); /* remove entry */ + GCObject *o = gcvalarr(h, i + 1); + if (iscleared(g, o)) /* value was collected? */ + *getArrTag(h, i + 1) = 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 556608e4..e91bb0f8 100644 --- a/lobject.h +++ b/lobject.h @@ -736,12 +736,15 @@ typedef union Node { #define setnorealasize(t) ((t)->flags |= BITRAS) +typedef struct ArrayCell ArrayCell; + + typedef struct Table { CommonHeader; lu_byte flags; /* 1<

l_registry, registry); luaH_resize(L, registry, LUA_RIDX_LAST, 0); /* registry[LUA_RIDX_MAINTHREAD] = L */ - setthvalue(L, ®istry->array[LUA_RIDX_MAINTHREAD - 1], L); + setthvalue(L, &aux, L); + luaH_setint(L, registry, LUA_RIDX_MAINTHREAD, &aux); /* registry[LUA_RIDX_GLOBALS] = new table (table of globals) */ - sethvalue(L, ®istry->array[LUA_RIDX_GLOBALS - 1], luaH_new(L)); + sethvalue(L, &aux, luaH_new(L)); + luaH_setint(L, registry, LUA_RIDX_GLOBALS, &aux); } diff --git a/ltable.c b/ltable.c index d436cf6e..ddda9a44 100644 --- a/ltable.c +++ b/ltable.c @@ -350,9 +350,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 + 1); + 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; } } @@ -374,6 +375,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 @@ -421,6 +457,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); + 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 @@ -443,7 +485,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; @@ -555,7 +597,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' */ setnodevector(L, &newt, nhsize); if (newasize < oldasize) { /* will array shrink? */ @@ -563,14 +605,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 + 1); + 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 = luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell); if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ freehash(L, &newt); /* release new hash part */ luaM_error(L); /* raise error (with array unchanged) */ @@ -580,7 +626,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 + 1) = 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 */ @@ -719,41 +765,6 @@ void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) { } -/* -** Check whether 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; -} - - static const TValue *getintfromhash (Table *t, lua_Integer key) { Node *n = hashint(t, key); lua_assert(l_castS2U(key) - 1u >= luaH_realasize(t)); @@ -770,15 +781,8 @@ static const TValue *getintfromhash (Table *t, lua_Integer key) { } -l_sinline int arraykeyisempty (Table *t, lua_Integer key) { - int tag = *getArrTag(t, key); - return tagisempty(tag); -} - - static int hashkeyisempty (Table *t, lua_Integer key) { const TValue *val = getintfromhash(t, key); - lua_assert(!keyinarray(t, key)); return isempty(val); } @@ -797,7 +801,7 @@ int luaH_getint (Table *t, lua_Integer key, TValue *res) { if (keyinarray(t, key)) { int tag = *getArrTag(t, key); if (!tagisempty(tag)) { - arr2val(t, key, tag, res); + farr2val(t, key, tag, res); return HOK; /* success */ } else @@ -900,7 +904,7 @@ int luaH_psetint (Table *t, lua_Integer key, TValue *val) { if (keyinarray(t, key)) { lu_byte *tag = getArrTag(t, key); if (!tagisempty(*tag)) { - val2arr(t, key, tag, val); + fval2arr(t, key, tag, val); return HOK; /* success */ } else @@ -956,7 +960,7 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key, } else { /* array entry */ hres = ~hres; /* real index */ - val2arr(t, hres, getArrTag(t, hres), value); + fval2arr(t, hres, getArrTag(t, hres), value); } } @@ -1087,11 +1091,11 @@ 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, t->alimit, limit); @@ -1102,7 +1106,7 @@ 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]))); + (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 */ diff --git a/ltable.h b/ltable.h index 5ec7b447..371e721d 100644 --- a/ltable.h +++ b/ltable.h @@ -51,20 +51,33 @@ */ +struct ArrayCell { + lu_byte tt; + 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_) +#define getArrTag(t,k) (&(t)->array[k - 1].tt) +#define getArrVal(t,k) (&(t)->array[k - 1].value) #define tagisempty(tag) (novariant(tag) == LUA_TNIL) -#define arr2val(h,k,tag,res) \ + +#define farr2val(h,k,tag,res) \ ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,k)) -#define val2arr(h,k,tag,val) \ +#define fval2arr(h,k,tag,val) \ (*tag = (val)->tt_, *getArrVal(h,k) = (val)->value_) +#define obj2arr(h,k,val) \ + (*getArrTag(h,k) = (val)->tt_, *getArrVal(h,k) = (val)->value_) + +#define arr2obj(h,k,val) \ + ((val)->tt_ = *getArrTag(h,k), (val)->value_ = *getArrVal(h,k)) + + LUAI_FUNC int luaH_getshortstr (Table *t, TString *key, TValue *res); LUAI_FUNC int luaH_getstr (Table *t, TString *key, TValue *res); LUAI_FUNC int luaH_get (Table *t, const TValue *key, TValue *res); diff --git a/ltests.c b/ltests.c index 7d184c0d..e2bf76bd 100644 --- a/ltests.c +++ b/ltests.c @@ -362,8 +362,11 @@ static void checktable (global_State *g, Table *h) { Node *n, *limit = gnode(h, sizenode(h)); GCObject *hgc = obj2gco(h); checkobjrefN(g, hgc, h->metatable); - for (i = 0; i < asize; i++) - checkvalref(g, hgc, &h->array[i]); + for (i = 0; i < asize; i++) { + TValue aux; + arr2obj(h, i + 1, &aux); + checkvalref(g, hgc, &aux); + } for (n = gnode(h, 0); n < limit; n++) { if (!isempty(gval(n))) { TValue k; @@ -1005,7 +1008,8 @@ static int table_query (lua_State *L) { } else if ((unsigned int)i < asize) { lua_pushinteger(L, i); - pushobject(L, &t->array[i]); + arr2obj(t, i + 1, s2v(L->top.p)); + api_incr_top(L); lua_pushnil(L); } else if ((i -= asize) < sizenode(t)) { diff --git a/lvm.c b/lvm.c index 96413718..927272df 100644 --- a/lvm.c +++ b/lvm.c @@ -1845,7 +1845,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) { luaH_resizearray(L, h, last); /* preallocate it at once */ for (; n > 0; n--) { TValue *val = s2v(ra + n); - setobj2t(L, &h->array[last - 1], val); + obj2arr(h, last, val); last--; luaC_barrierback(L, obj2gco(h), val); } diff --git a/lvm.h b/lvm.h index 8808c942..32455fba 100644 --- a/lvm.h +++ b/lvm.h @@ -92,7 +92,7 @@ typedef enum { if ((u - 1u < h->alimit)) { \ int tag = *getArrTag(h,u); \ if (tagisempty(tag)) aux = HNOTFOUND; \ - else { arr2val(h, u, tag, res); aux = HOK; }} \ + else { farr2val(h, u, tag, res); aux = HOK; }} \ else { aux = luaH_getint(h, u, res); }} @@ -105,7 +105,7 @@ typedef enum { if ((u - 1u < h->alimit)) { \ lu_byte *tag = getArrTag(h,u); \ if (tagisempty(*tag)) aux = ~cast_int(u); \ - else { val2arr(h, u, tag, val); aux = HOK; }} \ + else { fval2arr(h, u, tag, val); aux = HOK; }} \ else { aux = luaH_psetint(h, u, val); }} -- cgit v1.2.3-55-g6feb From 08a077d673b25cf1fbfe21794f240f4ff4999667 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Fri, 3 Nov 2023 15:26:13 -0300 Subject: Full implementation of new representation for arrays --- lgc.c | 8 ++++---- lobject.h | 4 +++- ltable.c | 46 +++++++++++++++++++++++++++++++++++++--------- ltable.h | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++------------- lvm.h | 4 ++-- 5 files changed, 96 insertions(+), 29 deletions(-) (limited to 'ltable.h') 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); } @@ -512,6 +512,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. @@ -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); }} -- cgit v1.2.3-55-g6feb