1 /* $NetBSD: ltablib.c,v 1.4 2015/10/08 13:21:00 mbalmer Exp $ */
4 ** Id: ltablib.c,v 1.80 2015/01/13 16:27:29 roberto Exp
5 ** Library for Table Manipulation
6 ** See Copyright Notice in lua.h
28 ** Structure with table-access functions
31 int (*geti
) (lua_State
*L
, int idx
, lua_Integer n
);
32 void (*seti
) (lua_State
*L
, int idx
, lua_Integer n
);
37 ** Check that 'arg' has a table and set access functions in 'ta' to raw
38 ** or non-raw according to the presence of corresponding metamethods.
40 static void checktab (lua_State
*L
, int arg
, TabA
*ta
) {
41 ta
->geti
= NULL
; ta
->seti
= NULL
;
42 if (lua_getmetatable(L
, arg
)) {
43 lua_pushliteral(L
, "__index"); /* 'index' metamethod */
44 if (lua_rawget(L
, -2) != LUA_TNIL
)
46 lua_pushliteral(L
, "__newindex"); /* 'newindex' metamethod */
47 if (lua_rawget(L
, -3) != LUA_TNIL
)
49 lua_pop(L
, 3); /* pop metatable plus both metamethods */
51 if (ta
->geti
== NULL
|| ta
->seti
== NULL
) {
52 luaL_checktype(L
, arg
, LUA_TTABLE
); /* must be table for raw methods */
53 if (ta
->geti
== NULL
) ta
->geti
= lua_rawgeti
;
54 if (ta
->seti
== NULL
) ta
->seti
= lua_rawseti
;
59 #define aux_getn(L,n,ta) (checktab(L, n, ta), luaL_len(L, n))
62 #if defined(LUA_COMPAT_MAXN)
63 static int maxn (lua_State
*L
) {
65 luaL_checktype(L
, 1, LUA_TTABLE
);
66 lua_pushnil(L
); /* first key */
67 while (lua_next(L
, 1)) {
68 lua_pop(L
, 1); /* remove value */
69 if (lua_type(L
, -1) == LUA_TNUMBER
) {
70 lua_Number v
= lua_tonumber(L
, -1);
74 lua_pushnumber(L
, max
);
80 static int tinsert (lua_State
*L
) {
82 lua_Integer e
= aux_getn(L
, 1, &ta
) + 1; /* first empty element */
83 lua_Integer pos
; /* where to insert new element */
84 switch (lua_gettop(L
)) {
85 case 2: { /* called with only 2 arguments */
86 pos
= e
; /* insert new element at the end */
91 pos
= luaL_checkinteger(L
, 2); /* 2nd argument is the position */
92 luaL_argcheck(L
, 1 <= pos
&& pos
<= e
, 2, "position out of bounds");
93 for (i
= e
; i
> pos
; i
--) { /* move up elements */
94 (*ta
.geti
)(L
, 1, i
- 1);
95 (*ta
.seti
)(L
, 1, i
); /* t[i] = t[i - 1] */
100 return luaL_error(L
, "wrong number of arguments to 'insert'");
103 (*ta
.seti
)(L
, 1, pos
); /* t[pos] = v */
108 static int tremove (lua_State
*L
) {
110 lua_Integer size
= aux_getn(L
, 1, &ta
);
111 lua_Integer pos
= luaL_optinteger(L
, 2, size
);
112 if (pos
!= size
) /* validate 'pos' if given */
113 luaL_argcheck(L
, 1 <= pos
&& pos
<= size
+ 1, 1, "position out of bounds");
114 (*ta
.geti
)(L
, 1, pos
); /* result = t[pos] */
115 for ( ; pos
< size
; pos
++) {
116 (*ta
.geti
)(L
, 1, pos
+ 1);
117 (*ta
.seti
)(L
, 1, pos
); /* t[pos] = t[pos + 1] */
120 (*ta
.seti
)(L
, 1, pos
); /* t[pos] = nil */
125 static int tmove (lua_State
*L
) {
127 lua_Integer f
= luaL_checkinteger(L
, 2);
128 lua_Integer e
= luaL_checkinteger(L
, 3);
129 lua_Integer t
= luaL_checkinteger(L
, 4);
130 int tt
= !lua_isnoneornil(L
, 5) ? 5 : 1; /* destination table */
131 if (e
>= f
) { /* otherwise, nothing to move */
133 ta
.geti
= (luaL_getmetafield(L
, 1, "__index") == LUA_TNIL
)
134 ? (luaL_checktype(L
, 1, LUA_TTABLE
), lua_rawgeti
)
136 ta
.seti
= (luaL_getmetafield(L
, tt
, "__newindex") == LUA_TNIL
)
137 ? (luaL_checktype(L
, tt
, LUA_TTABLE
), lua_rawseti
)
139 luaL_argcheck(L
, f
> 0 || e
< LUA_MAXINTEGER
+ f
, 3,
140 "too many elements to move");
141 n
= e
- f
+ 1; /* number of elements to move */
142 luaL_argcheck(L
, t
<= LUA_MAXINTEGER
- n
+ 1, 4,
143 "destination wrap around");
145 for (i
= n
- 1; i
>= 0; i
--) {
146 (*ta
.geti
)(L
, 1, f
+ i
);
147 (*ta
.seti
)(L
, tt
, t
+ i
);
151 for (i
= 0; i
< n
; i
++) {
152 (*ta
.geti
)(L
, 1, f
+ i
);
153 (*ta
.seti
)(L
, tt
, t
+ i
);
157 lua_pushvalue(L
, tt
); /* return "to table" */
162 static void addfield (lua_State
*L
, luaL_Buffer
*b
, TabA
*ta
, lua_Integer i
) {
163 (*ta
->geti
)(L
, 1, i
);
164 if (!lua_isstring(L
, -1))
165 luaL_error(L
, "invalid value (%s) at index %d in table for 'concat'",
166 luaL_typename(L
, -1), i
);
171 static int tconcat (lua_State
*L
) {
176 const char *sep
= luaL_optlstring(L
, 2, "", &lsep
);
178 i
= luaL_optinteger(L
, 3, 1);
179 last
= luaL_opt(L
, luaL_checkinteger
, 4, luaL_len(L
, 1));
180 luaL_buffinit(L
, &b
);
181 for (; i
< last
; i
++) {
182 addfield(L
, &b
, &ta
, i
);
183 luaL_addlstring(&b
, sep
, lsep
);
185 if (i
== last
) /* add last value (if interval was not empty) */
186 addfield(L
, &b
, &ta
, i
);
193 ** {======================================================
195 ** =======================================================
198 static int pack (lua_State
*L
) {
200 int n
= lua_gettop(L
); /* number of elements to pack */
201 lua_createtable(L
, n
, 1); /* create result table */
202 lua_insert(L
, 1); /* put it at index 1 */
203 for (i
= n
; i
>= 1; i
--) /* assign elements */
204 lua_rawseti(L
, 1, i
);
205 lua_pushinteger(L
, n
);
206 lua_setfield(L
, 1, "n"); /* t.n = number of elements */
207 return 1; /* return table */
211 static int unpack (lua_State
*L
) {
216 i
= luaL_optinteger(L
, 2, 1);
217 e
= luaL_opt(L
, luaL_checkinteger
, 3, luaL_len(L
, 1));
218 if (i
> e
) return 0; /* empty range */
219 n
= (lua_Unsigned
)e
- i
; /* number of elements minus 1 (avoid overflows) */
220 if (n
>= (unsigned int)INT_MAX
|| !lua_checkstack(L
, (int)(++n
)))
221 return luaL_error(L
, "too many results to unpack");
222 do { /* must have at least one element */
223 (*ta
.geti
)(L
, 1, i
); /* push arg[i..e] */
229 /* }====================================================== */
234 ** {======================================================
236 ** (based on 'Algorithms in MODULA-3', Robert Sedgewick;
237 ** Addison-Wesley, 1993.)
238 ** =======================================================
242 static void set2 (lua_State
*L
, TabA
*ta
, int i
, int j
) {
243 (*ta
->seti
)(L
, 1, i
);
244 (*ta
->seti
)(L
, 1, j
);
247 static int sort_comp (lua_State
*L
, int a
, int b
) {
248 if (!lua_isnil(L
, 2)) { /* function? */
251 lua_pushvalue(L
, a
-1); /* -1 to compensate function */
252 lua_pushvalue(L
, b
-2); /* -2 to compensate function and 'a' */
254 res
= lua_toboolean(L
, -1);
259 return lua_compare(L
, a
, b
, LUA_OPLT
);
262 static void auxsort (lua_State
*L
, TabA
*ta
, int l
, int u
) {
263 while (l
< u
) { /* for tail recursion */
265 /* sort elements a[l], a[(l+u)/2] and a[u] */
266 (*ta
->geti
)(L
, 1, l
);
267 (*ta
->geti
)(L
, 1, u
);
268 if (sort_comp(L
, -1, -2)) /* a[u] < a[l]? */
269 set2(L
, ta
, l
, u
); /* swap a[l] - a[u] */
272 if (u
-l
== 1) break; /* only 2 elements */
274 (*ta
->geti
)(L
, 1, i
);
275 (*ta
->geti
)(L
, 1, l
);
276 if (sort_comp(L
, -2, -1)) /* a[i]<a[l]? */
279 lua_pop(L
, 1); /* remove a[l] */
280 (*ta
->geti
)(L
, 1, u
);
281 if (sort_comp(L
, -1, -2)) /* a[u]<a[i]? */
286 if (u
-l
== 2) break; /* only 3 elements */
287 (*ta
->geti
)(L
, 1, i
); /* Pivot */
288 lua_pushvalue(L
, -1);
289 (*ta
->geti
)(L
, 1, u
-1);
291 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
293 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
294 /* repeat ++i until a[i] >= P */
295 while ((*ta
->geti
)(L
, 1, ++i
), sort_comp(L
, -1, -2)) {
296 if (i
>=u
) luaL_error(L
, "invalid order function for sorting");
297 lua_pop(L
, 1); /* remove a[i] */
299 /* repeat --j until a[j] <= P */
300 while ((*ta
->geti
)(L
, 1, --j
), sort_comp(L
, -3, -1)) {
301 if (j
<=l
) luaL_error(L
, "invalid order function for sorting");
302 lua_pop(L
, 1); /* remove a[j] */
305 lua_pop(L
, 3); /* pop pivot, a[i], a[j] */
310 (*ta
->geti
)(L
, 1, u
-1);
311 (*ta
->geti
)(L
, 1, i
);
312 set2(L
, ta
, u
-1, i
); /* swap pivot (a[u-1]) with a[i] */
313 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
314 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
321 auxsort(L
, ta
, j
, i
); /* call recursively the smaller one */
322 } /* repeat the routine for the larger one */
325 static int sort (lua_State
*L
) {
327 int n
= (int)aux_getn(L
, 1, &ta
);
328 luaL_checkstack(L
, 50, ""); /* assume array is smaller than 2^50 */
329 if (!lua_isnoneornil(L
, 2)) /* is there a 2nd argument? */
330 luaL_checktype(L
, 2, LUA_TFUNCTION
);
331 lua_settop(L
, 2); /* make sure there are two arguments */
332 auxsort(L
, &ta
, 1, n
);
336 /* }====================================================== */
339 static const luaL_Reg tab_funcs
[] = {
341 #if defined(LUA_COMPAT_MAXN)
354 LUAMOD_API
int luaopen_table (lua_State
*L
) {
355 luaL_newlib(L
, tab_funcs
);
356 #if defined(LUA_COMPAT_UNPACK)
357 /* _G.unpack = table.unpack */
358 lua_getfield(L
, -1, "unpack");
359 lua_setglobal(L
, "unpack");