lua

A copy of the Lua development repository
Log | Files | Refs | README

commit 43c8e5bded052801f54a7439d18933b83570eb82
parent b8b709b6d40c5c18d9b8ef33bb50afc55f048ab8
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date:   Mon, 30 Oct 2023 14:25:32 -0300

Full abstraction for representation of array values

Diffstat:
Mlapi.c | 31++++++++++++++-----------------
Mlgc.c | 25++++++++++++++++++-------
Mlobject.h | 5++++-
Mlstate.c | 7+++++--
Mltable.c | 116+++++++++++++++++++++++++++++++++++++++++--------------------------------------
Mltable.h | 21+++++++++++++++++----
Mltests.c | 10+++++++---
Mlvm.c | 2+-
Mlvm.h | 4++--
9 files changed, 128 insertions(+), 93 deletions(-)

diff --git 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, &gt); + return auxgetstr(L, &gt, 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, &gt); + auxsetstr(L, &gt, 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, &gt); /* 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, &gt); + luaC_barrier(L, f->upvals[0], &gt); } } lua_unlock(L); diff --git 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 @@ -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<<p means tagmethod(p) is not present */ lu_byte lsizenode; /* log2 of size of 'node' array */ unsigned int alimit; /* "limit" of 'array' array */ - TValue *array; /* array part */ + ArrayCell *array; /* array part */ Node *node; Node *lastfree; /* any free position is before this position */ struct Table *metatable; diff --git a/lstate.c b/lstate.c @@ -215,13 +215,16 @@ static void freestack (lua_State *L) { */ static void init_registry (lua_State *L, global_State *g) { /* create registry */ + TValue aux; Table *registry = luaH_new(L); sethvalue(L, &g->l_registry, registry); luaH_resize(L, registry, LUA_RIDX_LAST, 0); /* registry[LUA_RIDX_MAINTHREAD] = L */ - setthvalue(L, &registry->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, &registry->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 @@ -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; } } @@ -375,6 +376,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 @@ -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 @@ -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 @@ -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 @@ -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); }}