2 ** $Id: ltablib.c,v 1.38.1.2 2007/12/28 15:32:23 roberto Exp $
3 ** Library for Table Manipulation
4 ** See Copyright Notice in lua.h
19 #define aux_getn(L,n) (luaL_checktype(L, n, LUA_TTABLE), luaL_getn(L, n))
22 static int foreachi (lua_State
*L
) {
24 int n
= aux_getn(L
, 1);
25 luaL_checktype(L
, 2, LUA_TFUNCTION
);
26 for (i
=1; i
<= n
; i
++) {
27 lua_pushvalue(L
, 2); /* function */
28 lua_pushinteger(L
, i
); /* 1st argument */
29 lua_rawgeti(L
, 1, i
); /* 2nd argument */
31 if (!lua_isnil(L
, -1))
33 lua_pop(L
, 1); /* remove nil result */
39 static int foreach (lua_State
*L
) {
40 luaL_checktype(L
, 1, LUA_TTABLE
);
41 luaL_checktype(L
, 2, LUA_TFUNCTION
);
42 lua_pushnil(L
); /* first key */
43 while (lua_next(L
, 1)) {
44 lua_pushvalue(L
, 2); /* function */
45 lua_pushvalue(L
, -3); /* key */
46 lua_pushvalue(L
, -3); /* value */
48 if (!lua_isnil(L
, -1))
50 lua_pop(L
, 2); /* remove value and result */
56 static int maxn (lua_State
*L
) {
58 luaL_checktype(L
, 1, LUA_TTABLE
);
59 lua_pushnil(L
); /* first key */
60 while (lua_next(L
, 1)) {
61 lua_pop(L
, 1); /* remove value */
62 if (lua_type(L
, -1) == LUA_TNUMBER
) {
63 lua_Number v
= lua_tonumber(L
, -1);
67 lua_pushnumber(L
, max
);
72 static int getn (lua_State
*L
) {
73 lua_pushinteger(L
, aux_getn(L
, 1));
78 static int setn (lua_State
*L
) {
79 luaL_checktype(L
, 1, LUA_TTABLE
);
81 luaL_setn(L
, 1, luaL_checkint(L
, 2));
83 luaL_error(L
, LUA_QL("setn") " is obsolete");
90 static int tinsert (lua_State
*L
) {
91 int e
= aux_getn(L
, 1) + 1; /* first empty element */
92 int pos
; /* where to insert new element */
93 switch (lua_gettop(L
)) {
94 case 2: { /* called with only 2 arguments */
95 pos
= e
; /* insert new element at the end */
100 pos
= luaL_checkint(L
, 2); /* 2nd argument is the position */
101 if (pos
> e
) e
= pos
; /* `grow' array if necessary */
102 for (i
= e
; i
> pos
; i
--) { /* move up elements */
103 lua_rawgeti(L
, 1, i
-1);
104 lua_rawseti(L
, 1, i
); /* t[i] = t[i-1] */
109 return luaL_error(L
, "wrong number of arguments to " LUA_QL("insert"));
112 luaL_setn(L
, 1, e
); /* new size */
113 lua_rawseti(L
, 1, pos
); /* t[pos] = v */
118 static int tremove (lua_State
*L
) {
119 int e
= aux_getn(L
, 1);
120 int pos
= luaL_optint(L
, 2, e
);
121 if (!(1 <= pos
&& pos
<= e
)) /* position is outside bounds? */
122 return 0; /* nothing to remove */
123 luaL_setn(L
, 1, e
- 1); /* t.n = n-1 */
124 lua_rawgeti(L
, 1, pos
); /* result = t[pos] */
125 for ( ;pos
<e
; pos
++) {
126 lua_rawgeti(L
, 1, pos
+1);
127 lua_rawseti(L
, 1, pos
); /* t[pos] = t[pos+1] */
130 lua_rawseti(L
, 1, e
); /* t[e] = nil */
135 static int tconcat (lua_State
*L
) {
139 const char *sep
= luaL_optlstring(L
, 2, "", &lsep
);
140 luaL_checktype(L
, 1, LUA_TTABLE
);
141 i
= luaL_optint(L
, 3, 1);
142 last
= luaL_opt(L
, luaL_checkint
, 4, luaL_getn(L
, 1));
143 luaL_buffinit(L
, &b
);
144 for (; i
<= last
; i
++) {
145 lua_rawgeti(L
, 1, i
);
146 luaL_argcheck(L
, lua_isstring(L
, -1), 1, "table contains non-strings");
149 luaL_addlstring(&b
, sep
, lsep
);
158 ** {======================================================
160 ** (based on `Algorithms in MODULA-3', Robert Sedgewick;
161 ** Addison-Wesley, 1993.)
165 static void set2 (lua_State
*L
, int i
, int j
) {
166 lua_rawseti(L
, 1, i
);
167 lua_rawseti(L
, 1, j
);
170 static int sort_comp (lua_State
*L
, int a
, int b
) {
171 if (!lua_isnil(L
, 2)) { /* function? */
174 lua_pushvalue(L
, a
-1); /* -1 to compensate function */
175 lua_pushvalue(L
, b
-2); /* -2 to compensate function and `a' */
177 res
= lua_toboolean(L
, -1);
182 return lua_lessthan(L
, a
, b
);
185 static void auxsort (lua_State
*L
, int l
, int u
) {
186 while (l
< u
) { /* for tail recursion */
188 /* sort elements a[l], a[(l+u)/2] and a[u] */
189 lua_rawgeti(L
, 1, l
);
190 lua_rawgeti(L
, 1, u
);
191 if (sort_comp(L
, -1, -2)) /* a[u] < a[l]? */
192 set2(L
, l
, u
); /* swap a[l] - a[u] */
195 if (u
-l
== 1) break; /* only 2 elements */
197 lua_rawgeti(L
, 1, i
);
198 lua_rawgeti(L
, 1, l
);
199 if (sort_comp(L
, -2, -1)) /* a[i]<a[l]? */
202 lua_pop(L
, 1); /* remove a[l] */
203 lua_rawgeti(L
, 1, u
);
204 if (sort_comp(L
, -1, -2)) /* a[u]<a[i]? */
209 if (u
-l
== 2) break; /* only 3 elements */
210 lua_rawgeti(L
, 1, i
); /* Pivot */
211 lua_pushvalue(L
, -1);
212 lua_rawgeti(L
, 1, u
-1);
214 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
216 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
217 /* repeat ++i until a[i] >= P */
218 while (lua_rawgeti(L
, 1, ++i
), sort_comp(L
, -1, -2)) {
219 if (i
>u
) luaL_error(L
, "invalid order function for sorting");
220 lua_pop(L
, 1); /* remove a[i] */
222 /* repeat --j until a[j] <= P */
223 while (lua_rawgeti(L
, 1, --j
), sort_comp(L
, -3, -1)) {
224 if (j
<l
) luaL_error(L
, "invalid order function for sorting");
225 lua_pop(L
, 1); /* remove a[j] */
228 lua_pop(L
, 3); /* pop pivot, a[i], a[j] */
233 lua_rawgeti(L
, 1, u
-1);
234 lua_rawgeti(L
, 1, i
);
235 set2(L
, u
-1, i
); /* swap pivot (a[u-1]) with a[i] */
236 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
237 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
244 auxsort(L
, j
, i
); /* call recursively the smaller one */
245 } /* repeat the routine for the larger one */
248 static int sort (lua_State
*L
) {
249 int n
= aux_getn(L
, 1);
250 luaL_checkstack(L
, 40, ""); /* assume array is smaller than 2^40 */
251 if (!lua_isnoneornil(L
, 2)) /* is there a 2nd argument? */
252 luaL_checktype(L
, 2, LUA_TFUNCTION
);
253 lua_settop(L
, 2); /* make sure there is two arguments */
258 /* }====================================================== */
261 static const luaL_Reg tab_funcs
[] = {
263 {"foreach", foreach
},
264 {"foreachi", foreachi
},
275 LUALIB_API
int luaopen_table (lua_State
*L
) {
276 luaL_register(L
, LUA_TABLIBNAME
, tab_funcs
);