1 /*
2 ** $Id: ltablib.c,v 1.38.1.3 2008/02/14 16:46:58 roberto Exp $
3 ** Library for Table Manipulation
4 ** See Copyright Notice in lua.h
5 */
6
7
8 #include <stddef.h>
9
10 #define ltablib_c
11 #define LUA_LIB
12
13 #include "lua.h"
14
15 #include "lauxlib.h"
16 #include "lualib.h"
17
18
19 #define aux_getn(L,n) (luaL_checktype(L, n, LUA_TTABLE), luaL_getn(L, n))
20
21
foreachi(lua_State * L)22 static int foreachi (lua_State *L) {
23 int i;
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 */
30 lua_call(L, 2, 1);
31 if (!lua_isnil(L, -1))
32 return 1;
33 lua_pop(L, 1); /* remove nil result */
34 }
35 return 0;
36 }
37
38
foreach(lua_State * L)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 */
47 lua_call(L, 2, 1);
48 if (!lua_isnil(L, -1))
49 return 1;
50 lua_pop(L, 2); /* remove value and result */
51 }
52 return 0;
53 }
54
55
maxn(lua_State * L)56 static int maxn (lua_State *L) {
57 lua_Number max = 0;
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);
64 if (v > max) max = v;
65 }
66 }
67 lua_pushnumber(L, max);
68 return 1;
69 }
70
71
getn(lua_State * L)72 static int getn (lua_State *L) {
73 lua_pushinteger(L, aux_getn(L, 1));
74 return 1;
75 }
76
77
setn(lua_State * L)78 static int setn (lua_State *L) {
79 luaL_checktype(L, 1, LUA_TTABLE);
80 #ifndef luaL_setn
81 luaL_setn(L, 1, luaL_checkint(L, 2));
82 #else
83 luaL_error(L, LUA_QL("setn") " is obsolete");
84 #endif
85 lua_pushvalue(L, 1);
86 return 1;
87 }
88
89
tinsert(lua_State * L)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 */
96 break;
97 }
98 case 3: {
99 int i;
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] */
105 }
106 break;
107 }
108 default: {
109 return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));
110 }
111 }
112 luaL_setn(L, 1, e); /* new size */
113 lua_rawseti(L, 1, pos); /* t[pos] = v */
114 return 0;
115 }
116
117
tremove(lua_State * L)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] */
128 }
129 lua_pushnil(L);
130 lua_rawseti(L, 1, e); /* t[e] = nil */
131 return 1;
132 }
133
134
addfield(lua_State * L,luaL_Buffer * b,int i)135 static void addfield (lua_State *L, luaL_Buffer *b, int i) {
136 lua_rawgeti(L, 1, i);
137 if (!lua_isstring(L, -1))
138 luaL_error(L, "invalid value (%s) at index %d in table for "
139 LUA_QL("concat"), luaL_typename(L, -1), i);
140 luaL_addvalue(b);
141 }
142
143
tconcat(lua_State * L)144 static int tconcat (lua_State *L) {
145 luaL_Buffer b;
146 size_t lsep;
147 int i, last;
148 const char *sep = luaL_optlstring(L, 2, "", &lsep);
149 luaL_checktype(L, 1, LUA_TTABLE);
150 i = luaL_optint(L, 3, 1);
151 last = luaL_opt(L, luaL_checkint, 4, luaL_getn(L, 1));
152 luaL_buffinit(L, &b);
153 for (; i < last; i++) {
154 addfield(L, &b, i);
155 luaL_addlstring(&b, sep, lsep);
156 }
157 if (i == last) /* add last value (if interval was not empty) */
158 addfield(L, &b, i);
159 luaL_pushresult(&b);
160 return 1;
161 }
162
163
164
165 /*
166 ** {======================================================
167 ** Quicksort
168 ** (based on `Algorithms in MODULA-3', Robert Sedgewick;
169 ** Addison-Wesley, 1993.)
170 */
171
172
set2(lua_State * L,int i,int j)173 static void set2 (lua_State *L, int i, int j) {
174 lua_rawseti(L, 1, i);
175 lua_rawseti(L, 1, j);
176 }
177
sort_comp(lua_State * L,int a,int b)178 static int sort_comp (lua_State *L, int a, int b) {
179 if (!lua_isnil(L, 2)) { /* function? */
180 int res;
181 lua_pushvalue(L, 2);
182 lua_pushvalue(L, a-1); /* -1 to compensate function */
183 lua_pushvalue(L, b-2); /* -2 to compensate function and `a' */
184 lua_call(L, 2, 1);
185 res = lua_toboolean(L, -1);
186 lua_pop(L, 1);
187 return res;
188 }
189 else /* a < b? */
190 return lua_lessthan(L, a, b);
191 }
192
auxsort(lua_State * L,int l,int u)193 static void auxsort (lua_State *L, int l, int u) {
194 while (l < u) { /* for tail recursion */
195 int i, j;
196 /* sort elements a[l], a[(l+u)/2] and a[u] */
197 lua_rawgeti(L, 1, l);
198 lua_rawgeti(L, 1, u);
199 if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */
200 set2(L, l, u); /* swap a[l] - a[u] */
201 else
202 lua_pop(L, 2);
203 if (u-l == 1) break; /* only 2 elements */
204 i = (l+u)/2;
205 lua_rawgeti(L, 1, i);
206 lua_rawgeti(L, 1, l);
207 if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */
208 set2(L, i, l);
209 else {
210 lua_pop(L, 1); /* remove a[l] */
211 lua_rawgeti(L, 1, u);
212 if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */
213 set2(L, i, u);
214 else
215 lua_pop(L, 2);
216 }
217 if (u-l == 2) break; /* only 3 elements */
218 lua_rawgeti(L, 1, i); /* Pivot */
219 lua_pushvalue(L, -1);
220 lua_rawgeti(L, 1, u-1);
221 set2(L, i, u-1);
222 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
223 i = l; j = u-1;
224 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
225 /* repeat ++i until a[i] >= P */
226 while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
227 if (i>u) luaL_error(L, "invalid order function for sorting");
228 lua_pop(L, 1); /* remove a[i] */
229 }
230 /* repeat --j until a[j] <= P */
231 while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
232 if (j<l) luaL_error(L, "invalid order function for sorting");
233 lua_pop(L, 1); /* remove a[j] */
234 }
235 if (j<i) {
236 lua_pop(L, 3); /* pop pivot, a[i], a[j] */
237 break;
238 }
239 set2(L, i, j);
240 }
241 lua_rawgeti(L, 1, u-1);
242 lua_rawgeti(L, 1, i);
243 set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */
244 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
245 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
246 if (i-l < u-i) {
247 j=l; i=i-1; l=i+2;
248 }
249 else {
250 j=i+1; i=u; u=j-2;
251 }
252 auxsort(L, j, i); /* call recursively the smaller one */
253 } /* repeat the routine for the larger one */
254 }
255
sort(lua_State * L)256 static int sort (lua_State *L) {
257 int n = aux_getn(L, 1);
258 luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */
259 if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */
260 luaL_checktype(L, 2, LUA_TFUNCTION);
261 lua_settop(L, 2); /* make sure there is two arguments */
262 auxsort(L, 1, n);
263 return 0;
264 }
265
266 /* }====================================================== */
267
268
269 static const luaL_Reg tab_funcs[] = {
270 {"concat", tconcat},
271 {"foreach", foreach},
272 {"foreachi", foreachi},
273 {"getn", getn},
274 {"maxn", maxn},
275 {"insert", tinsert},
276 {"remove", tremove},
277 {"setn", setn},
278 {"sort", sort},
279 {NULL, NULL}
280 };
281
282
luaopen_table(lua_State * L)283 LUALIB_API int luaopen_table (lua_State *L) {
284 luaL_register(L, LUA_TABLIBNAME, tab_funcs);
285 return 1;
286 }
287
288