aboutsummaryrefslogtreecommitdiff
path: root/ltable.h
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-29 17:26:20 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-29 17:26:20 -0300
commit002beeebe79065e03dd9f531bee367e8459e3f64 (patch)
tree5b066d30e08950c923c253ce85f702b39fbe9c31 /ltable.h
parent9329eeac3b7035c223d7a8b63dbde1f6db371bf5 (diff)
downloadlua-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.h36
1 files changed, 22 insertions, 14 deletions
diff --git a/ltable.h b/ltable.h
index 17e4fb4a..9c4eb937 100644
--- a/ltable.h
+++ b/ltable.h
@@ -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);
167LUAI_FUNC void luaH_free (lua_State *L, Table *t); 176LUAI_FUNC void luaH_free (lua_State *L, Table *t);
168LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); 177LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key);
169LUAI_FUNC lua_Unsigned luaH_getn (Table *t); 178LUAI_FUNC lua_Unsigned luaH_getn (Table *t);
170LUAI_FUNC unsigned luaH_realasize (const Table *t);
171 179
172 180
173#if defined(LUA_DEBUG) 181#if defined(LUA_DEBUG)