aboutsummaryrefslogtreecommitdiff
path: root/ltablib.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2014-07-16 09:44:52 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2014-07-16 09:44:52 -0300
commita9af12bbe765dd2c60fa3d9d43013042fd3361a8 (patch)
tree1ddd2f4fbd370ae8724b81378f66a69f7d89d5e2 /ltablib.c
parent5bbb4a06a692ec2c9773274f0f99c7573838e86b (diff)
downloadlua-a9af12bbe765dd2c60fa3d9d43013042fd3361a8.tar.gz
lua-a9af12bbe765dd2c60fa3d9d43013042fd3361a8.tar.bz2
lua-a9af12bbe765dd2c60fa3d9d43013042fd3361a8.zip
Table library now respects '__index'/'__newindex' metamethods
Diffstat (limited to 'ltablib.c')
-rw-r--r--ltablib.c139
1 files changed, 96 insertions, 43 deletions
diff --git a/ltablib.c b/ltablib.c
index e61f3323..dca2bc8e 100644
--- a/ltablib.c
+++ b/ltablib.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltablib.c,v 1.69 2014/04/12 14:43:50 roberto Exp roberto $ 2** $Id: ltablib.c,v 1.70 2014/05/16 18:53:25 roberto Exp roberto $
3** Library for Table Manipulation 3** Library for Table Manipulation
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -17,8 +17,56 @@
17#include "lualib.h" 17#include "lualib.h"
18 18
19 19
20#define aux_getn(L,n) (luaL_checktype(L, n, LUA_TTABLE), luaL_len(L, n))
21 20
21/*
22** Structure with table-access functions
23*/
24typedef struct {
25 int (*geti) (lua_State *L, int idx, lua_Integer n);
26 void (*seti) (lua_State *L, int idx, lua_Integer n);
27} TabA;
28
29
30/*
31** equivalent to 'lua_rawgeti', but not raw
32*/
33static int geti (lua_State *L, int idx, lua_Integer n) {
34 lua_pushinteger(L, n);
35 return lua_gettable(L, idx); /* assume 'idx' is not negative */
36}
37
38
39/*
40** equivalent to 'lua_rawseti', but not raw
41*/
42static void seti (lua_State *L, int idx, lua_Integer n) {
43 lua_pushinteger(L, n);
44 lua_rotate(L, -2, 1); /* exchange key and value */
45 lua_settable(L, idx); /* assume 'idx' is not negative */
46}
47
48
49/*
50** Check that 'arg' has a table and set access functions in 'ta' to raw
51** or non-raw according to the presence of corresponding metamethods.
52*/
53static void checktab (lua_State *L, int arg, TabA *ta) {
54 luaL_checktype(L, arg, LUA_TTABLE);
55 if (!lua_getmetatable(L, arg)) { /* fast track */
56 ta->geti = lua_rawgeti; /* with no metatable, all is raw */
57 ta->seti = lua_rawseti;
58 }
59 else {
60 lua_pushliteral(L, "__index"); /* 'index' metamethod */
61 ta->geti = (lua_rawget(L, -2) == LUA_TNIL) ? lua_rawgeti : geti;
62 lua_pushliteral(L, "__newindex"); /* 'newindex' metamethod */
63 ta->seti = (lua_rawget(L, -3) == LUA_TNIL) ? lua_rawseti : seti;
64 lua_pop(L, 3); /* pop metatable plus both metamethods */
65 }
66}
67
68
69#define aux_getn(L,n,ta) (checktab(L, n, ta), luaL_len(L, n))
22 70
23 71
24#if defined(LUA_COMPAT_MAXN) 72#if defined(LUA_COMPAT_MAXN)
@@ -40,7 +88,8 @@ static int maxn (lua_State *L) {
40 88
41 89
42static int tinsert (lua_State *L) { 90static int tinsert (lua_State *L) {
43 lua_Integer e = aux_getn(L, 1) + 1; /* first empty element */ 91 TabA ta;
92 lua_Integer e = aux_getn(L, 1, &ta) + 1; /* first empty element */
44 lua_Integer pos; /* where to insert new element */ 93 lua_Integer pos; /* where to insert new element */
45 switch (lua_gettop(L)) { 94 switch (lua_gettop(L)) {
46 case 2: { /* called with only 2 arguments */ 95 case 2: { /* called with only 2 arguments */
@@ -52,8 +101,8 @@ static int tinsert (lua_State *L) {
52 pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */ 101 pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */
53 luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds"); 102 luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds");
54 for (i = e; i > pos; i--) { /* move up elements */ 103 for (i = e; i > pos; i--) { /* move up elements */
55 lua_rawgeti(L, 1, i-1); 104 (*ta.geti)(L, 1, i - 1);
56 lua_rawseti(L, 1, i); /* t[i] = t[i-1] */ 105 (*ta.seti)(L, 1, i); /* t[i] = t[i - 1] */
57 } 106 }
58 break; 107 break;
59 } 108 }
@@ -61,29 +110,30 @@ static int tinsert (lua_State *L) {
61 return luaL_error(L, "wrong number of arguments to " LUA_QL("insert")); 110 return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));
62 } 111 }
63 } 112 }
64 lua_rawseti(L, 1, pos); /* t[pos] = v */ 113 (*ta.seti)(L, 1, pos); /* t[pos] = v */
65 return 0; 114 return 0;
66} 115}
67 116
68 117
69static int tremove (lua_State *L) { 118static int tremove (lua_State *L) {
70 lua_Integer size = aux_getn(L, 1); 119 TabA ta;
120 lua_Integer size = aux_getn(L, 1, &ta);
71 lua_Integer pos = luaL_optinteger(L, 2, size); 121 lua_Integer pos = luaL_optinteger(L, 2, size);
72 if (pos != size) /* validate 'pos' if given */ 122 if (pos != size) /* validate 'pos' if given */
73 luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds"); 123 luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");
74 lua_rawgeti(L, 1, pos); /* result = t[pos] */ 124 (*ta.geti)(L, 1, pos); /* result = t[pos] */
75 for ( ; pos < size; pos++) { 125 for ( ; pos < size; pos++) {
76 lua_rawgeti(L, 1, pos+1); 126 (*ta.geti)(L, 1, pos + 1);
77 lua_rawseti(L, 1, pos); /* t[pos] = t[pos+1] */ 127 (*ta.seti)(L, 1, pos); /* t[pos] = t[pos + 1] */
78 } 128 }
79 lua_pushnil(L); 129 lua_pushnil(L);
80 lua_rawseti(L, 1, pos); /* t[pos] = nil */ 130 (*ta.seti)(L, 1, pos); /* t[pos] = nil */
81 return 1; 131 return 1;
82} 132}
83 133
84 134
85static void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) { 135static void addfield (lua_State *L, luaL_Buffer *b, TabA *ta, lua_Integer i) {
86 lua_rawgeti(L, 1, i); 136 (*ta->geti)(L, 1, i);
87 if (!lua_isstring(L, -1)) 137 if (!lua_isstring(L, -1))
88 luaL_error(L, "invalid value (%s) at index %d in table for " 138 luaL_error(L, "invalid value (%s) at index %d in table for "
89 LUA_QL("concat"), luaL_typename(L, -1), i); 139 LUA_QL("concat"), luaL_typename(L, -1), i);
@@ -92,20 +142,21 @@ static void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) {
92 142
93 143
94static int tconcat (lua_State *L) { 144static int tconcat (lua_State *L) {
145 TabA ta;
95 luaL_Buffer b; 146 luaL_Buffer b;
96 size_t lsep; 147 size_t lsep;
97 lua_Integer i, last; 148 lua_Integer i, last;
98 const char *sep = luaL_optlstring(L, 2, "", &lsep); 149 const char *sep = luaL_optlstring(L, 2, "", &lsep);
99 luaL_checktype(L, 1, LUA_TTABLE); 150 checktab(L, 1, &ta);
100 i = luaL_optinteger(L, 3, 1); 151 i = luaL_optinteger(L, 3, 1);
101 last = luaL_opt(L, luaL_checkinteger, 4, luaL_len(L, 1)); 152 last = luaL_opt(L, luaL_checkinteger, 4, luaL_len(L, 1));
102 luaL_buffinit(L, &b); 153 luaL_buffinit(L, &b);
103 for (; i < last; i++) { 154 for (; i < last; i++) {
104 addfield(L, &b, i); 155 addfield(L, &b, &ta, i);
105 luaL_addlstring(&b, sep, lsep); 156 luaL_addlstring(&b, sep, lsep);
106 } 157 }
107 if (i == last) /* add last value (if interval was not empty) */ 158 if (i == last) /* add last value (if interval was not empty) */
108 addfield(L, &b, i); 159 addfield(L, &b, &ta, i);
109 luaL_pushresult(&b); 160 luaL_pushresult(&b);
110 return 1; 161 return 1;
111} 162}
@@ -131,9 +182,10 @@ static int pack (lua_State *L) {
131 182
132 183
133static int unpack (lua_State *L) { 184static int unpack (lua_State *L) {
185 TabA ta;
134 lua_Integer i, e; 186 lua_Integer i, e;
135 lua_Unsigned n; 187 lua_Unsigned n;
136 luaL_checktype(L, 1, LUA_TTABLE); 188 checktab(L, 1, &ta);
137 i = luaL_optinteger(L, 2, 1); 189 i = luaL_optinteger(L, 2, 1);
138 e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); 190 e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1));
139 if (i > e) return 0; /* empty range */ 191 if (i > e) return 0; /* empty range */
@@ -141,7 +193,7 @@ static int unpack (lua_State *L) {
141 if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, ++n)) 193 if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, ++n))
142 return luaL_error(L, "too many results to unpack"); 194 return luaL_error(L, "too many results to unpack");
143 do { /* must have at least one element */ 195 do { /* must have at least one element */
144 lua_rawgeti(L, 1, i); /* push arg[i..e] */ 196 (*ta.geti)(L, 1, i); /* push arg[i..e] */
145 } while (i++ < e); 197 } while (i++ < e);
146 198
147 return n; 199 return n;
@@ -160,9 +212,9 @@ static int unpack (lua_State *L) {
160*/ 212*/
161 213
162 214
163static void set2 (lua_State *L, int i, int j) { 215static void set2 (lua_State *L, TabA *ta, int i, int j) {
164 lua_rawseti(L, 1, i); 216 (*ta->seti)(L, 1, i);
165 lua_rawseti(L, 1, j); 217 (*ta->seti)(L, 1, j);
166} 218}
167 219
168static int sort_comp (lua_State *L, int a, int b) { 220static int sort_comp (lua_State *L, int a, int b) {
@@ -180,45 +232,45 @@ static int sort_comp (lua_State *L, int a, int b) {
180 return lua_compare(L, a, b, LUA_OPLT); 232 return lua_compare(L, a, b, LUA_OPLT);
181} 233}
182 234
183static void auxsort (lua_State *L, int l, int u) { 235static void auxsort (lua_State *L, TabA *ta, int l, int u) {
184 while (l < u) { /* for tail recursion */ 236 while (l < u) { /* for tail recursion */
185 int i, j; 237 int i, j;
186 /* sort elements a[l], a[(l+u)/2] and a[u] */ 238 /* sort elements a[l], a[(l+u)/2] and a[u] */
187 lua_rawgeti(L, 1, l); 239 (*ta->geti)(L, 1, l);
188 lua_rawgeti(L, 1, u); 240 (*ta->geti)(L, 1, u);
189 if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ 241 if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */
190 set2(L, l, u); /* swap a[l] - a[u] */ 242 set2(L, ta, l, u); /* swap a[l] - a[u] */
191 else 243 else
192 lua_pop(L, 2); 244 lua_pop(L, 2);
193 if (u-l == 1) break; /* only 2 elements */ 245 if (u-l == 1) break; /* only 2 elements */
194 i = (l+u)/2; 246 i = (l+u)/2;
195 lua_rawgeti(L, 1, i); 247 (*ta->geti)(L, 1, i);
196 lua_rawgeti(L, 1, l); 248 (*ta->geti)(L, 1, l);
197 if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */ 249 if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */
198 set2(L, i, l); 250 set2(L, ta, i, l);
199 else { 251 else {
200 lua_pop(L, 1); /* remove a[l] */ 252 lua_pop(L, 1); /* remove a[l] */
201 lua_rawgeti(L, 1, u); 253 (*ta->geti)(L, 1, u);
202 if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */ 254 if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */
203 set2(L, i, u); 255 set2(L, ta, i, u);
204 else 256 else
205 lua_pop(L, 2); 257 lua_pop(L, 2);
206 } 258 }
207 if (u-l == 2) break; /* only 3 elements */ 259 if (u-l == 2) break; /* only 3 elements */
208 lua_rawgeti(L, 1, i); /* Pivot */ 260 (*ta->geti)(L, 1, i); /* Pivot */
209 lua_pushvalue(L, -1); 261 lua_pushvalue(L, -1);
210 lua_rawgeti(L, 1, u-1); 262 (*ta->geti)(L, 1, u-1);
211 set2(L, i, u-1); 263 set2(L, ta, i, u-1);
212 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ 264 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
213 i = l; j = u-1; 265 i = l; j = u-1;
214 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ 266 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
215 /* repeat ++i until a[i] >= P */ 267 /* repeat ++i until a[i] >= P */
216 while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) { 268 while ((*ta->geti)(L, 1, ++i), sort_comp(L, -1, -2)) {
217 if (i>=u) luaL_error(L, "invalid order function for sorting"); 269 if (i>=u) luaL_error(L, "invalid order function for sorting");
218 lua_pop(L, 1); /* remove a[i] */ 270 lua_pop(L, 1); /* remove a[i] */
219 } 271 }
220 /* repeat --j until a[j] <= P */ 272 /* repeat --j until a[j] <= P */
221 while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) { 273 while ((*ta->geti)(L, 1, --j), sort_comp(L, -3, -1)) {
222 if (j<=l) luaL_error(L, "invalid order function for sorting"); 274 if (j<=l) luaL_error(L, "invalid order function for sorting");
223 lua_pop(L, 1); /* remove a[j] */ 275 lua_pop(L, 1); /* remove a[j] */
224 } 276 }
@@ -226,11 +278,11 @@ static void auxsort (lua_State *L, int l, int u) {
226 lua_pop(L, 3); /* pop pivot, a[i], a[j] */ 278 lua_pop(L, 3); /* pop pivot, a[i], a[j] */
227 break; 279 break;
228 } 280 }
229 set2(L, i, j); 281 set2(L, ta, i, j);
230 } 282 }
231 lua_rawgeti(L, 1, u-1); 283 (*ta->geti)(L, 1, u-1);
232 lua_rawgeti(L, 1, i); 284 (*ta->geti)(L, 1, i);
233 set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */ 285 set2(L, ta, u-1, i); /* swap pivot (a[u-1]) with a[i] */
234 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ 286 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
235 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */ 287 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
236 if (i-l < u-i) { 288 if (i-l < u-i) {
@@ -239,17 +291,18 @@ static void auxsort (lua_State *L, int l, int u) {
239 else { 291 else {
240 j=i+1; i=u; u=j-2; 292 j=i+1; i=u; u=j-2;
241 } 293 }
242 auxsort(L, j, i); /* call recursively the smaller one */ 294 auxsort(L, ta, j, i); /* call recursively the smaller one */
243 } /* repeat the routine for the larger one */ 295 } /* repeat the routine for the larger one */
244} 296}
245 297
246static int sort (lua_State *L) { 298static int sort (lua_State *L) {
247 int n = aux_getn(L, 1); 299 TabA ta;
248 luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */ 300 int n = aux_getn(L, 1, &ta);
301 luaL_checkstack(L, 50, ""); /* assume array is smaller than 2^50 */
249 if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ 302 if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */
250 luaL_checktype(L, 2, LUA_TFUNCTION); 303 luaL_checktype(L, 2, LUA_TFUNCTION);
251 lua_settop(L, 2); /* make sure there is two arguments */ 304 lua_settop(L, 2); /* make sure there is two arguments */
252 auxsort(L, 1, n); 305 auxsort(L, &ta, 1, n);
253 return 0; 306 return 0;
254} 307}
255 308