aboutsummaryrefslogtreecommitdiff
path: root/ltable.h
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-04-05 15:35:11 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-04-05 15:35:11 -0300
commit5edacafcfa36a1fa86a7b5316bacf8c6a2c47227 (patch)
tree31538a57a5c724af2cd758938ab06b8674edb7a8 /ltable.h
parent3507c3380f5251a49c63f87c81c027b2664795c7 (diff)
downloadlua-5edacafcfa36a1fa86a7b5316bacf8c6a2c47227.tar.gz
lua-5edacafcfa36a1fa86a7b5316bacf8c6a2c47227.tar.bz2
lua-5edacafcfa36a1fa86a7b5316bacf8c6a2c47227.zip
Yet another representation for arrays
This "linear" representation (see ltable.h for details) has worse locality than cells, but the simpler access code seems to compensate that.
Diffstat (limited to 'ltable.h')
-rw-r--r--ltable.h37
1 files changed, 20 insertions, 17 deletions
diff --git a/ltable.h b/ltable.h
index 4734bd50..6db197ba 100644
--- a/ltable.h
+++ b/ltable.h
@@ -71,7 +71,7 @@
71 71
72/* 72/*
73** 'luaH_get*' operations set 'res', unless the value is absent, and 73** 'luaH_get*' operations set 'res', unless the value is absent, and
74** return the tag of the result, 74** return the tag of the result.
75** The 'luaH_pset*' (pre-set) operations set the given value and return 75** The 'luaH_pset*' (pre-set) operations set the given value and return
76** HOK, unless the original value is absent. In that case, if the key 76** HOK, unless the original value is absent. In that case, if the key
77** is really absent, they return HNOTFOUND. Otherwise, if there is a 77** is really absent, they return HNOTFOUND. Otherwise, if there is a
@@ -86,24 +86,27 @@
86 86
87 87
88/* 88/*
89** The array part of a table is represented by an array of cells. 89** The array part of a table is represented by an inverted array of
90** Each cell is composed of NM tags followed by NM values, so that 90** values followed by an array of tags, to avoid wasting space with
91** no space is wasted in padding. The last cell may be incomplete, 91** padding. The 'array' pointer points to the junction of the two
92** that is, it may have fewer than NM values. 92** arrays, so that values are indexed with negative indices and tags
93** with non-negative indices.
94
95 Values Tags
96 --------------------------------------------------------
97 ... | Value 1 | Value 0 |0|1|...
98 --------------------------------------------------------
99 ^ t->array
100
101** All accesses to 't->array' should be through the macros 'getArrTag'
102** and 'getArrVal'.
93*/ 103*/
94#define NM cast_uint(sizeof(Value))
95
96struct ArrayCell {
97 lu_byte tag[NM];
98 Value value[NM];
99};
100
101 104
102/* Computes the address of the tag for the abstract index 'k' */ 105/* Computes the address of the tag for the abstract index 'k' */
103#define getArrTag(t,k) (&(t)->array[(k)/NM].tag[(k)%NM]) 106#define getArrTag(t,k) (cast(lu_byte*, (t)->array) + (k))
104 107
105/* Computes the address of the value for the abstract index 'k' */ 108/* Computes the address of the value for the abstract index 'k' */
106#define getArrVal(t,k) (&(t)->array[(k)/NM].value[(k)%NM]) 109#define getArrVal(t,k) ((t)->array - 1 - (k))
107 110
108 111
109/* 112/*
@@ -117,9 +120,9 @@ struct ArrayCell {
117 120
118 121
119/* 122/*
120** Often, we need to check the tag of a value before moving it. These 123** Often, we need to check the tag of a value before moving it. The
121** macros also move TValues to/from arrays, but receive the precomputed 124** following macros also move TValues to/from arrays, but receive the
122** tag value or address as an extra argument. 125** precomputed tag value or address as an extra argument.
123*/ 126*/
124#define farr2val(h,k,tag,res) \ 127#define farr2val(h,k,tag,res) \
125 ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,(k)-1u)) 128 ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,(k)-1u))