Line data Source code
1 : /*
2 : ** $Id: ltablib.c,v 1.65.1.2 2014/05/07 16:32:55 roberto Exp $
3 : ** Library for Table Manipulation
4 : ** See Copyright Notice in lua.h
5 : */
6 :
7 :
8 : #include <limits.h>
9 : #include <stddef.h>
10 :
11 : #define ltablib_c
12 : #define LUA_LIB
13 :
14 : #include "lua.h"
15 :
16 : #include "lauxlib.h"
17 : #include "lualib.h"
18 :
19 :
20 : #define aux_getn(L,n) (luaL_checktype(L, n, LUA_TTABLE), luaL_len(L, n))
21 :
22 :
23 :
24 : #if defined(LUA_COMPAT_MAXN)
25 4 : static int maxn (lua_State *L) {
26 4 : lua_Number max = 0;
27 4 : luaL_checktype(L, 1, LUA_TTABLE);
28 4 : lua_pushnil(L); /* first key */
29 14 : while (lua_next(L, 1)) {
30 6 : lua_pop(L, 1); /* remove value */
31 6 : if (lua_type(L, -1) == LUA_TNUMBER) {
32 6 : lua_Number v = lua_tonumber(L, -1);
33 6 : if (v > max) max = v;
34 : }
35 : }
36 4 : lua_pushnumber(L, max);
37 4 : return 1;
38 : }
39 : #endif
40 :
41 :
42 59 : static int tinsert (lua_State *L) {
43 59 : int e = aux_getn(L, 1) + 1; /* first empty element */
44 : int pos; /* where to insert new element */
45 59 : switch (lua_gettop(L)) {
46 52 : case 2: { /* called with only 2 arguments */
47 52 : pos = e; /* insert new element at the end */
48 52 : break;
49 : }
50 6 : case 3: {
51 : int i;
52 6 : pos = luaL_checkint(L, 2); /* 2nd argument is the position */
53 6 : luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds");
54 11 : for (i = e; i > pos; i--) { /* move up elements */
55 7 : lua_rawgeti(L, 1, i-1);
56 7 : lua_rawseti(L, 1, i); /* t[i] = t[i-1] */
57 : }
58 4 : break;
59 : }
60 1 : default: {
61 1 : return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));
62 : }
63 : }
64 56 : lua_rawseti(L, 1, pos); /* t[pos] = v */
65 56 : return 0;
66 : }
67 :
68 :
69 5 : static int tremove (lua_State *L) {
70 5 : int size = aux_getn(L, 1);
71 5 : int pos = luaL_optint(L, 2, size);
72 5 : if (pos != size) /* validate 'pos' if given */
73 3 : luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");
74 4 : lua_rawgeti(L, 1, pos); /* result = t[pos] */
75 7 : for ( ; pos < size; pos++) {
76 3 : lua_rawgeti(L, 1, pos+1);
77 3 : lua_rawseti(L, 1, pos); /* t[pos] = t[pos+1] */
78 : }
79 4 : lua_pushnil(L);
80 4 : lua_rawseti(L, 1, pos); /* t[pos] = nil */
81 4 : return 1;
82 : }
83 :
84 :
85 80901 : static void addfield (lua_State *L, luaL_Buffer *b, int i) {
86 80901 : lua_rawgeti(L, 1, i);
87 80901 : if (!lua_isstring(L, -1))
88 2 : luaL_error(L, "invalid value (%s) at index %d in table for "
89 : LUA_QL("concat"), luaL_typename(L, -1), i);
90 80899 : luaL_addvalue(b);
91 80899 : }
92 :
93 :
94 11979 : static int tconcat (lua_State *L) {
95 : luaL_Buffer b;
96 : size_t lsep;
97 : int i, last;
98 11979 : const char *sep = luaL_optlstring(L, 2, "", &lsep);
99 11979 : luaL_checktype(L, 1, LUA_TTABLE);
100 11979 : i = luaL_optint(L, 3, 1);
101 11979 : last = luaL_opt(L, luaL_checkint, 4, luaL_len(L, 1));
102 11978 : luaL_buffinit(L, &b);
103 80903 : for (; i < last; i++) {
104 68927 : addfield(L, &b, i);
105 68925 : luaL_addlstring(&b, sep, lsep);
106 : }
107 11976 : if (i == last) /* add last value (if interval was not empty) */
108 11974 : addfield(L, &b, i);
109 11976 : luaL_pushresult(&b);
110 11976 : return 1;
111 : }
112 :
113 :
114 : /*
115 : ** {======================================================
116 : ** Pack/unpack
117 : ** =======================================================
118 : */
119 :
120 2 : static int pack (lua_State *L) {
121 2 : int n = lua_gettop(L); /* number of elements to pack */
122 2 : lua_createtable(L, n, 1); /* create result table */
123 2 : lua_pushinteger(L, n);
124 2 : lua_setfield(L, -2, "n"); /* t.n = number of elements */
125 2 : if (n > 0) { /* at least one element? */
126 : int i;
127 1 : lua_pushvalue(L, 1);
128 1 : lua_rawseti(L, -2, 1); /* insert first element */
129 1 : lua_replace(L, 1); /* move table into index 1 */
130 3 : for (i = n; i >= 2; i--) /* assign other elements */
131 2 : lua_rawseti(L, 1, i);
132 : }
133 2 : return 1; /* return table */
134 : }
135 :
136 :
137 6 : static int unpack (lua_State *L) {
138 : int i, e;
139 : unsigned int n;
140 6 : luaL_checktype(L, 1, LUA_TTABLE);
141 6 : i = luaL_optint(L, 2, 1);
142 6 : e = luaL_opt(L, luaL_checkint, 3, luaL_len(L, 1));
143 6 : if (i > e) return 0; /* empty range */
144 5 : n = (unsigned int)e - (unsigned int)i; /* number of elements minus 1 */
145 5 : if (n > (INT_MAX - 10) || !lua_checkstack(L, ++n))
146 0 : return luaL_error(L, "too many results to unpack");
147 5 : lua_rawgeti(L, 1, i); /* push arg[i] (avoiding overflow problems) */
148 13 : while (i++ < e) /* push arg[i + 1...e] */
149 8 : lua_rawgeti(L, 1, i);
150 5 : return n;
151 : }
152 :
153 : /* }====================================================== */
154 :
155 :
156 :
157 : /*
158 : ** {======================================================
159 : ** Quicksort
160 : ** (based on `Algorithms in MODULA-3', Robert Sedgewick;
161 : ** Addison-Wesley, 1993.)
162 : ** =======================================================
163 : */
164 :
165 :
166 43021 : static void set2 (lua_State *L, int i, int j) {
167 43021 : lua_rawseti(L, 1, i);
168 43021 : lua_rawseti(L, 1, j);
169 43021 : }
170 :
171 91619 : static int sort_comp (lua_State *L, int a, int b) {
172 91619 : if (!lua_isnil(L, 2)) { /* function? */
173 : int res;
174 8 : lua_pushvalue(L, 2);
175 8 : lua_pushvalue(L, a-1); /* -1 to compensate function */
176 8 : lua_pushvalue(L, b-2); /* -2 to compensate function and `a' */
177 8 : lua_call(L, 2, 1);
178 8 : res = lua_toboolean(L, -1);
179 8 : lua_pop(L, 1);
180 8 : return res;
181 : }
182 : else /* a < b? */
183 91611 : return lua_compare(L, a, b, LUA_OPLT);
184 : }
185 :
186 15854 : static void auxsort (lua_State *L, int l, int u) {
187 25790 : while (l < u) { /* for tail recursion */
188 : int i, j;
189 : /* sort elements a[l], a[(l+u)/2] and a[u] */
190 20509 : lua_rawgeti(L, 1, l);
191 20509 : lua_rawgeti(L, 1, u);
192 20509 : if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */
193 10254 : set2(L, l, u); /* swap a[l] - a[u] */
194 : else
195 10255 : lua_pop(L, 2);
196 20509 : if (u-l == 1) break; /* only 2 elements */
197 13907 : i = (l+u)/2;
198 13907 : lua_rawgeti(L, 1, i);
199 13907 : lua_rawgeti(L, 1, l);
200 13907 : if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */
201 4635 : set2(L, i, l);
202 : else {
203 9272 : lua_pop(L, 1); /* remove a[l] */
204 9272 : lua_rawgeti(L, 1, u);
205 9272 : if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */
206 4635 : set2(L, i, u);
207 : else
208 4637 : lua_pop(L, 2);
209 : }
210 13907 : if (u-l == 2) break; /* only 3 elements */
211 9937 : lua_rawgeti(L, 1, i); /* Pivot */
212 9937 : lua_pushvalue(L, -1);
213 9937 : lua_rawgeti(L, 1, u-1);
214 9937 : set2(L, i, u-1);
215 : /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
216 9937 : i = l; j = u-1;
217 : for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
218 : /* repeat ++i until a[i] >= P */
219 23967 : while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
220 10407 : if (i>=u) luaL_error(L, "invalid order function for sorting");
221 10406 : lua_pop(L, 1); /* remove a[i] */
222 : }
223 : /* repeat --j until a[j] <= P */
224 23964 : while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
225 10404 : if (j<=l) luaL_error(L, "invalid order function for sorting");
226 10404 : lua_pop(L, 1); /* remove a[j] */
227 : }
228 13560 : if (j<i) {
229 9936 : lua_pop(L, 3); /* pop pivot, a[i], a[j] */
230 9936 : break;
231 : }
232 3624 : set2(L, i, j);
233 : }
234 9936 : lua_rawgeti(L, 1, u-1);
235 9936 : lua_rawgeti(L, 1, i);
236 9936 : set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */
237 : /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
238 : /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
239 9936 : if (i-l < u-i) {
240 4008 : j=l; i=i-1; l=i+2;
241 : }
242 : else {
243 5928 : j=i+1; i=u; u=j-2;
244 : }
245 9936 : auxsort(L, j, i); /* call recursively the smaller one */
246 : } /* repeat the routine for the larger one */
247 15853 : }
248 :
249 5918 : static int sort (lua_State *L) {
250 5918 : int n = aux_getn(L, 1);
251 5918 : luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */
252 5918 : if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */
253 2 : luaL_checktype(L, 2, LUA_TFUNCTION);
254 5918 : lua_settop(L, 2); /* make sure there is two arguments */
255 5918 : auxsort(L, 1, n);
256 5917 : return 0;
257 : }
258 :
259 : /* }====================================================== */
260 :
261 :
262 : static const luaL_Reg tab_funcs[] = {
263 : {"concat", tconcat},
264 : #if defined(LUA_COMPAT_MAXN)
265 : {"maxn", maxn},
266 : #endif
267 : {"insert", tinsert},
268 : {"pack", pack},
269 : {"unpack", unpack},
270 : {"remove", tremove},
271 : {"sort", sort},
272 : {NULL, NULL}
273 : };
274 :
275 :
276 86 : LUAMOD_API int luaopen_table (lua_State *L) {
277 86 : luaL_newlib(L, tab_funcs);
278 : #if defined(LUA_COMPAT_UNPACK)
279 : /* _G.unpack = table.unpack */
280 86 : lua_getfield(L, -1, "unpack");
281 86 : lua_setglobal(L, "unpack");
282 : #endif
283 86 : return 1;
284 : }
285 :
|
