diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-11-29 17:26:20 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-11-29 17:26:20 -0300 |
commit | 002beeebe79065e03dd9f531bee367e8459e3f64 (patch) | |
tree | 5b066d30e08950c923c253ce85f702b39fbe9c31 /ltable.h | |
parent | 9329eeac3b7035c223d7a8b63dbde1f6db371bf5 (diff) | |
download | lua-002beeebe79065e03dd9f531bee367e8459e3f64.tar.gz lua-002beeebe79065e03dd9f531bee367e8459e3f64.tar.bz2 lua-002beeebe79065e03dd9f531bee367e8459e3f64.zip |
New way to keep hints for table length
Instead of using 'alimit' for keeping the size of the array and at
the same time being a hint for '#t', a table now keeps these two
values separate. The Table structure has a field 'asize' with the
size of the array, while the length hint is kept in the array itself.
That way, tables with no array part waste no space with that field.
Moreover, the space for the hint may have zero cost for small arrays,
if the array of tags plus the hint still fits in a single word.
Diffstat (limited to 'ltable.h')
-rw-r--r-- | ltable.h | 36 |
1 files changed, 22 insertions, 14 deletions
@@ -48,7 +48,7 @@ | |||
48 | 48 | ||
49 | #define luaH_fastgeti(t,k,res,tag) \ | 49 | #define luaH_fastgeti(t,k,res,tag) \ |
50 | { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \ | 50 | { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \ |
51 | if ((u < h->alimit)) { \ | 51 | if ((u < h->asize)) { \ |
52 | tag = *getArrTag(h, u); \ | 52 | tag = *getArrTag(h, u); \ |
53 | if (!tagisempty(tag)) { farr2val(h, u, tag, res); }} \ | 53 | if (!tagisempty(tag)) { farr2val(h, u, tag, res); }} \ |
54 | else { tag = luaH_getint(h, (k), res); }} | 54 | else { tag = luaH_getint(h, (k), res); }} |
@@ -56,10 +56,11 @@ | |||
56 | 56 | ||
57 | #define luaH_fastseti(t,k,val,hres) \ | 57 | #define luaH_fastseti(t,k,val,hres) \ |
58 | { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \ | 58 | { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \ |
59 | if ((u < h->alimit)) { \ | 59 | if ((u < h->asize)) { \ |
60 | lu_byte *tag = getArrTag(h, u); \ | 60 | lu_byte *tag = getArrTag(h, u); \ |
61 | if (tagisempty(*tag)) hres = ~cast_int(u); \ | 61 | if (h->metatable == NULL || !tagisempty(*tag)) \ |
62 | else { fval2arr(h, u, tag, val); hres = HOK; }} \ | 62 | { fval2arr(h, u, tag, val); hres = HOK; } \ |
63 | else hres = ~cast_int(u); } \ | ||
63 | else { hres = luaH_psetint(h, k, val); }} | 64 | else { hres = luaH_psetint(h, k, val); }} |
64 | 65 | ||
65 | 66 | ||
@@ -94,28 +95,36 @@ | |||
94 | /* | 95 | /* |
95 | ** The array part of a table is represented by an inverted array of | 96 | ** The array part of a table is represented by an inverted array of |
96 | ** values followed by an array of tags, to avoid wasting space with | 97 | ** values followed by an array of tags, to avoid wasting space with |
97 | ** padding. The 'array' pointer points to the junction of the two | 98 | ** padding. In between them there is an unsigned int, explained later. |
98 | ** arrays, so that values are indexed with negative indices and tags | 99 | ** The 'array' pointer points between the two arrays, so that values are |
99 | ** with non-negative indices. | 100 | ** indexed with negative indices and tags with non-negative indices. |
100 | 101 | ||
101 | Values Tags | 102 | Values Tags |
102 | -------------------------------------------------------- | 103 | -------------------------------------------------------- |
103 | ... | Value 1 | Value 0 |0|1|... | 104 | ... | Value 1 | Value 0 |unsigned|0|1|... |
104 | -------------------------------------------------------- | 105 | -------------------------------------------------------- |
105 | ^ t->array | 106 | ^ t->array |
106 | 107 | ||
107 | ** All accesses to 't->array' should be through the macros 'getArrTag' | 108 | ** All accesses to 't->array' should be through the macros 'getArrTag' |
108 | ** and 'getArrVal'. | 109 | ** and 'getArrVal'. |
109 | */ | 110 | */ |
110 | 111 | ||
111 | /* Computes the address of the tag for the abstract C-index 'k' */ | 112 | /* Computes the address of the tag for the abstract C-index 'k' */ |
112 | #define getArrTag(t,k) (cast(lu_byte*, (t)->array) + (k)) | 113 | #define getArrTag(t,k) (cast(lu_byte*, (t)->array) + sizeof(unsigned) + (k)) |
113 | 114 | ||
114 | /* Computes the address of the value for the abstract C-index 'k' */ | 115 | /* Computes the address of the value for the abstract C-index 'k' */ |
115 | #define getArrVal(t,k) ((t)->array - 1 - (k)) | 116 | #define getArrVal(t,k) ((t)->array - 1 - (k)) |
116 | 117 | ||
117 | 118 | ||
118 | /* | 119 | /* |
120 | ** The unsigned between the two arrays is used as a hint for #t; | ||
121 | ** see luaH_getn. It is stored there to avoid wasting space in | ||
122 | ** the structure Table for tables with no array part. | ||
123 | */ | ||
124 | #define lenhint(t) cast(unsigned*, (t)->array) | ||
125 | |||
126 | |||
127 | /* | ||
119 | ** Move TValues to/from arrays, using C indices | 128 | ** Move TValues to/from arrays, using C indices |
120 | */ | 129 | */ |
121 | #define arr2obj(h,k,val) \ | 130 | #define arr2obj(h,k,val) \ |
@@ -167,7 +176,6 @@ LUAI_FUNC lu_mem luaH_size (Table *t); | |||
167 | LUAI_FUNC void luaH_free (lua_State *L, Table *t); | 176 | LUAI_FUNC void luaH_free (lua_State *L, Table *t); |
168 | LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); | 177 | LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); |
169 | LUAI_FUNC lua_Unsigned luaH_getn (Table *t); | 178 | LUAI_FUNC lua_Unsigned luaH_getn (Table *t); |
170 | LUAI_FUNC unsigned luaH_realasize (const Table *t); | ||
171 | 179 | ||
172 | 180 | ||
173 | #if defined(LUA_DEBUG) | 181 | #if defined(LUA_DEBUG) |