Line data Source code
1 : /*
2 : ** $Id: ltablib.c,v 1.93.1.1 2017/04/19 17:20:42 roberto Exp $
3 : ** Library for Table Manipulation
4 : ** See Copyright Notice in lua.h
5 : */
6 :
7 : #define ltablib_c
8 : #define LUA_LIB
9 :
10 : #include "lprefix.h"
11 :
12 :
13 : #include <limits.h>
14 : #include <stddef.h>
15 : #include <string.h>
16 :
17 : #include "lua.h"
18 :
19 : #include "lauxlib.h"
20 : #include "lualib.h"
21 :
22 :
23 : /*
24 : ** Operations that an object must define to mimic a table
25 : ** (some functions only need some of them)
26 : */
27 : #define TAB_R 1 /* read */
28 : #define TAB_W 2 /* write */
29 : #define TAB_L 4 /* length */
30 : #define TAB_RW (TAB_R | TAB_W) /* read/write */
31 :
32 :
33 : #define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n))
34 :
35 :
36 0 : static int checkfield (lua_State *L, const char *key, int n) {
37 0 : lua_pushstring(L, key);
38 0 : return (lua_rawget(L, -n) != LUA_TNIL);
39 : }
40 :
41 :
42 : /*
43 : ** Check that 'arg' either is a table or can behave like one (that is,
44 : ** has a metatable with the required metamethods)
45 : */
46 212 : static void checktab (lua_State *L, int arg, int what) {
47 212 : if (lua_type(L, arg) != LUA_TTABLE) { /* is it not a table? */
48 2 : int n = 1; /* number of elements to pop */
49 2 : if (lua_getmetatable(L, arg) && /* must have metatable */
50 0 : (!(what & TAB_R) || checkfield(L, "__index", ++n)) &&
51 0 : (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) &&
52 0 : (!(what & TAB_L) || checkfield(L, "__len", ++n))) {
53 0 : lua_pop(L, n); /* pop metatable and tested metamethods */
54 : }
55 : else
56 2 : luaL_checktype(L, arg, LUA_TTABLE); /* force an error */
57 : }
58 210 : }
59 :
60 :
61 : #if defined(LUA_COMPAT_MAXN)
62 : static int maxn (lua_State *L) {
63 : lua_Number max = 0;
64 : luaL_checktype(L, 1, LUA_TTABLE);
65 : lua_pushnil(L); /* first key */
66 : while (lua_next(L, 1)) {
67 : lua_pop(L, 1); /* remove value */
68 : if (lua_type(L, -1) == LUA_TNUMBER) {
69 : lua_Number v = lua_tonumber(L, -1);
70 : if (v > max) max = v;
71 : }
72 : }
73 : lua_pushnumber(L, max);
74 : return 1;
75 : }
76 : #endif
77 :
78 :
79 168 : static int tinsert (lua_State *L) {
80 168 : lua_Integer e = aux_getn(L, 1, TAB_RW) + 1; /* first empty element */
81 : lua_Integer pos; /* where to insert new element */
82 168 : switch (lua_gettop(L)) {
83 168 : case 2: { /* called with only 2 arguments */
84 168 : pos = e; /* insert new element at the end */
85 168 : break;
86 : }
87 0 : case 3: {
88 : lua_Integer i;
89 0 : pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */
90 0 : luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds");
91 0 : for (i = e; i > pos; i--) { /* move up elements */
92 0 : lua_geti(L, 1, i - 1);
93 0 : lua_seti(L, 1, i); /* t[i] = t[i - 1] */
94 : }
95 0 : break;
96 : }
97 0 : default: {
98 0 : return luaL_error(L, "wrong number of arguments to 'insert'");
99 : }
100 : }
101 168 : lua_seti(L, 1, pos); /* t[pos] = v */
102 168 : return 0;
103 : }
104 :
105 :
106 2 : static int tremove (lua_State *L) {
107 2 : lua_Integer size = aux_getn(L, 1, TAB_RW);
108 2 : lua_Integer pos = luaL_optinteger(L, 2, size);
109 2 : if (pos != size) /* validate 'pos' if given */
110 0 : luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");
111 2 : lua_geti(L, 1, pos); /* result = t[pos] */
112 2 : for ( ; pos < size; pos++) {
113 0 : lua_geti(L, 1, pos + 1);
114 0 : lua_seti(L, 1, pos); /* t[pos] = t[pos + 1] */
115 : }
116 2 : lua_pushnil(L);
117 2 : lua_seti(L, 1, pos); /* t[pos] = nil */
118 2 : return 1;
119 : }
120 :
121 :
122 : /*
123 : ** Copy elements (1[f], ..., 1[e]) into (tt[t], tt[t+1], ...). Whenever
124 : ** possible, copy in increasing order, which is better for rehashing.
125 : ** "possible" means destination after original range, or smaller
126 : ** than origin, or copying to another table.
127 : */
128 0 : static int tmove (lua_State *L) {
129 0 : lua_Integer f = luaL_checkinteger(L, 2);
130 0 : lua_Integer e = luaL_checkinteger(L, 3);
131 0 : lua_Integer t = luaL_checkinteger(L, 4);
132 0 : int tt = !lua_isnoneornil(L, 5) ? 5 : 1; /* destination table */
133 0 : checktab(L, 1, TAB_R);
134 0 : checktab(L, tt, TAB_W);
135 0 : if (e >= f) { /* otherwise, nothing to move */
136 : lua_Integer n, i;
137 0 : luaL_argcheck(L, f > 0 || e < LUA_MAXINTEGER + f, 3,
138 : "too many elements to move");
139 0 : n = e - f + 1; /* number of elements to move */
140 0 : luaL_argcheck(L, t <= LUA_MAXINTEGER - n + 1, 4,
141 : "destination wrap around");
142 0 : if (t > e || t <= f || (tt != 1 && !lua_compare(L, 1, tt, LUA_OPEQ))) {
143 0 : for (i = 0; i < n; i++) {
144 0 : lua_geti(L, 1, f + i);
145 0 : lua_seti(L, tt, t + i);
146 : }
147 : }
148 : else {
149 0 : for (i = n - 1; i >= 0; i--) {
150 0 : lua_geti(L, 1, f + i);
151 0 : lua_seti(L, tt, t + i);
152 : }
153 : }
154 : }
155 0 : lua_pushvalue(L, tt); /* return destination table */
156 0 : return 1;
157 : }
158 :
159 :
160 640 : static void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) {
161 640 : lua_geti(L, 1, i);
162 640 : if (!lua_isstring(L, -1))
163 2 : luaL_error(L, "invalid value (%s) at index %d in table for 'concat'",
164 : luaL_typename(L, -1), i);
165 638 : luaL_addvalue(b);
166 638 : }
167 :
168 :
169 42 : static int tconcat (lua_State *L) {
170 : luaL_Buffer b;
171 42 : lua_Integer last = aux_getn(L, 1, TAB_R);
172 : size_t lsep;
173 40 : const char *sep = luaL_optlstring(L, 2, "", &lsep);
174 40 : lua_Integer i = luaL_optinteger(L, 3, 1);
175 40 : last = luaL_optinteger(L, 4, last);
176 40 : luaL_buffinit(L, &b);
177 656 : for (; i < last; i++) {
178 616 : addfield(L, &b, i);
179 616 : luaL_addlstring(&b, sep, lsep);
180 : }
181 40 : if (i == last) /* add last value (if interval was not empty) */
182 24 : addfield(L, &b, i);
183 38 : luaL_pushresult(&b);
184 38 : return 1;
185 : }
186 :
187 :
188 : /*
189 : ** {======================================================
190 : ** Pack/unpack
191 : ** =======================================================
192 : */
193 :
194 0 : static int pack (lua_State *L) {
195 : int i;
196 0 : int n = lua_gettop(L); /* number of elements to pack */
197 0 : lua_createtable(L, n, 1); /* create result table */
198 0 : lua_insert(L, 1); /* put it at index 1 */
199 0 : for (i = n; i >= 1; i--) /* assign elements */
200 0 : lua_seti(L, 1, i);
201 0 : lua_pushinteger(L, n);
202 0 : lua_setfield(L, 1, "n"); /* t.n = number of elements */
203 0 : return 1; /* return table */
204 : }
205 :
206 :
207 138 : static int unpack (lua_State *L) {
208 : lua_Unsigned n;
209 138 : lua_Integer i = luaL_optinteger(L, 2, 1);
210 138 : lua_Integer e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1));
211 138 : if (i > e) return 0; /* empty range */
212 138 : n = (lua_Unsigned)e - i; /* number of elements minus 1 (avoid overflows) */
213 138 : if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, (int)(++n)))
214 0 : return luaL_error(L, "too many results to unpack");
215 294 : for (; i < e; i++) { /* push arg[i..e - 1] (to avoid overflows) */
216 156 : lua_geti(L, 1, i);
217 : }
218 138 : lua_geti(L, 1, e); /* push last element */
219 138 : return (int)n;
220 : }
221 :
222 : /* }====================================================== */
223 :
224 :
225 :
226 : /*
227 : ** {======================================================
228 : ** Quicksort
229 : ** (based on 'Algorithms in MODULA-3', Robert Sedgewick;
230 : ** Addison-Wesley, 1993.)
231 : ** =======================================================
232 : */
233 :
234 :
235 : /* type for array indices */
236 : typedef unsigned int IdxT;
237 :
238 :
239 : /*
240 : ** Produce a "random" 'unsigned int' to randomize pivot choice. This
241 : ** macro is used only when 'sort' detects a big imbalance in the result
242 : ** of a partition. (If you don't want/need this "randomness", ~0 is a
243 : ** good choice.)
244 : */
245 : #if !defined(l_randomizePivot) /* { */
246 :
247 : #include <time.h>
248 :
249 : /* size of 'e' measured in number of 'unsigned int's */
250 : #define sof(e) (sizeof(e) / sizeof(unsigned int))
251 :
252 : /*
253 : ** Use 'time' and 'clock' as sources of "randomness". Because we don't
254 : ** know the types 'clock_t' and 'time_t', we cannot cast them to
255 : ** anything without risking overflows. A safe way to use their values
256 : ** is to copy them to an array of a known type and use the array values.
257 : */
258 0 : static unsigned int l_randomizePivot (void) {
259 : #if defined(ARDUPILOT_BUILD)
260 0 : return lua_random32();
261 : #else
262 : clock_t c = clock();
263 : time_t t = time(NULL);
264 : unsigned int buff[sof(c) + sof(t)];
265 : unsigned int i, rnd = 0;
266 : memcpy(buff, &c, sof(c) * sizeof(unsigned int));
267 : memcpy(buff + sof(c), &t, sof(t) * sizeof(unsigned int));
268 : for (i = 0; i < sof(buff); i++)
269 : rnd += buff[i];
270 : return rnd;
271 : #endif
272 : }
273 :
274 : #endif /* } */
275 :
276 :
277 : /* arrays larger than 'RANLIMIT' may use randomized pivots */
278 : #define RANLIMIT 100u
279 :
280 :
281 0 : static void set2 (lua_State *L, IdxT i, IdxT j) {
282 0 : lua_seti(L, 1, i);
283 0 : lua_seti(L, 1, j);
284 0 : }
285 :
286 :
287 : /*
288 : ** Return true iff value at stack index 'a' is less than the value at
289 : ** index 'b' (according to the order of the sort).
290 : */
291 0 : static int sort_comp (lua_State *L, int a, int b) {
292 0 : if (lua_isnil(L, 2)) /* no function? */
293 0 : return lua_compare(L, a, b, LUA_OPLT); /* a < b */
294 : else { /* function */
295 : int res;
296 0 : lua_pushvalue(L, 2); /* push function */
297 0 : lua_pushvalue(L, a-1); /* -1 to compensate function */
298 0 : lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */
299 0 : lua_call(L, 2, 1); /* call function */
300 0 : res = lua_toboolean(L, -1); /* get result */
301 0 : lua_pop(L, 1); /* pop result */
302 0 : return res;
303 : }
304 : }
305 :
306 :
307 : /*
308 : ** Does the partition: Pivot P is at the top of the stack.
309 : ** precondition: a[lo] <= P == a[up-1] <= a[up],
310 : ** so it only needs to do the partition from lo + 1 to up - 2.
311 : ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up]
312 : ** returns 'i'.
313 : */
314 0 : static IdxT partition (lua_State *L, IdxT lo, IdxT up) {
315 0 : IdxT i = lo; /* will be incremented before first use */
316 0 : IdxT j = up - 1; /* will be decremented before first use */
317 : /* loop invariant: a[lo .. i] <= P <= a[j .. up] */
318 : for (;;) {
319 : /* next loop: repeat ++i while a[i] < P */
320 0 : while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) {
321 0 : if (i == up - 1) /* a[i] < P but a[up - 1] == P ?? */
322 0 : luaL_error(L, "invalid order function for sorting");
323 0 : lua_pop(L, 1); /* remove a[i] */
324 : }
325 : /* after the loop, a[i] >= P and a[lo .. i - 1] < P */
326 : /* next loop: repeat --j while P < a[j] */
327 0 : while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) {
328 0 : if (j < i) /* j < i but a[j] > P ?? */
329 0 : luaL_error(L, "invalid order function for sorting");
330 0 : lua_pop(L, 1); /* remove a[j] */
331 : }
332 : /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */
333 0 : if (j < i) { /* no elements out of place? */
334 : /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */
335 0 : lua_pop(L, 1); /* pop a[j] */
336 : /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */
337 0 : set2(L, up - 1, i);
338 0 : return i;
339 : }
340 : /* otherwise, swap a[i] - a[j] to restore invariant and repeat */
341 0 : set2(L, i, j);
342 : }
343 : }
344 :
345 :
346 : /*
347 : ** Choose an element in the middle (2nd-3th quarters) of [lo,up]
348 : ** "randomized" by 'rnd'
349 : */
350 0 : static IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) {
351 0 : IdxT r4 = (up - lo) / 4; /* range/4 */
352 0 : IdxT p = rnd % (r4 * 2) + (lo + r4);
353 : lua_assert(lo + r4 <= p && p <= up - r4);
354 0 : return p;
355 : }
356 :
357 :
358 : /*
359 : ** QuickSort algorithm (recursive function)
360 : */
361 0 : static void auxsort (lua_State *L, IdxT lo, IdxT up,
362 : unsigned int rnd) {
363 0 : while (lo < up) { /* loop for tail recursion */
364 : IdxT p; /* Pivot index */
365 : IdxT n; /* to be used later */
366 : /* sort elements 'lo', 'p', and 'up' */
367 0 : lua_geti(L, 1, lo);
368 0 : lua_geti(L, 1, up);
369 0 : if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */
370 0 : set2(L, lo, up); /* swap a[lo] - a[up] */
371 : else
372 0 : lua_pop(L, 2); /* remove both values */
373 0 : if (up - lo == 1) /* only 2 elements? */
374 0 : return; /* already sorted */
375 0 : if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */
376 0 : p = (lo + up)/2; /* middle element is a good pivot */
377 : else /* for larger intervals, it is worth a random pivot */
378 0 : p = choosePivot(lo, up, rnd);
379 0 : lua_geti(L, 1, p);
380 0 : lua_geti(L, 1, lo);
381 0 : if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */
382 0 : set2(L, p, lo); /* swap a[p] - a[lo] */
383 : else {
384 0 : lua_pop(L, 1); /* remove a[lo] */
385 0 : lua_geti(L, 1, up);
386 0 : if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */
387 0 : set2(L, p, up); /* swap a[up] - a[p] */
388 : else
389 0 : lua_pop(L, 2);
390 : }
391 0 : if (up - lo == 2) /* only 3 elements? */
392 0 : return; /* already sorted */
393 0 : lua_geti(L, 1, p); /* get middle element (Pivot) */
394 0 : lua_pushvalue(L, -1); /* push Pivot */
395 0 : lua_geti(L, 1, up - 1); /* push a[up - 1] */
396 0 : set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */
397 0 : p = partition(L, lo, up);
398 : /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */
399 0 : if (p - lo < up - p) { /* lower interval is smaller? */
400 0 : auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */
401 0 : n = p - lo; /* size of smaller interval */
402 0 : lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */
403 : }
404 : else {
405 0 : auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */
406 0 : n = up - p; /* size of smaller interval */
407 0 : up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */
408 : }
409 0 : if ((up - lo) / 128 > n) /* partition too imbalanced? */
410 0 : rnd = l_randomizePivot(); /* try a new randomization */
411 : } /* tail call auxsort(L, lo, up, rnd) */
412 : }
413 :
414 :
415 0 : static int sort (lua_State *L) {
416 0 : lua_Integer n = aux_getn(L, 1, TAB_RW);
417 0 : if (n > 1) { /* non-trivial interval? */
418 0 : luaL_argcheck(L, n < INT_MAX, 1, "array too big");
419 0 : if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */
420 0 : luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */
421 0 : lua_settop(L, 2); /* make sure there are two arguments */
422 0 : auxsort(L, 1, (IdxT)n, 0);
423 : }
424 0 : return 0;
425 : }
426 :
427 : /* }====================================================== */
428 :
429 :
430 : static const luaL_Reg tab_funcs[] = {
431 : {"concat", tconcat},
432 : #if defined(LUA_COMPAT_MAXN)
433 : {"maxn", maxn},
434 : #endif
435 : {"insert", tinsert},
436 : {"pack", pack},
437 : {"unpack", unpack},
438 : {"remove", tremove},
439 : {"move", tmove},
440 : {"sort", sort},
441 : {NULL, NULL}
442 : };
443 :
444 :
445 92 : LUAMOD_API int luaopen_table (lua_State *L) {
446 92 : luaL_newlib(L, tab_funcs);
447 : #if defined(LUA_COMPAT_UNPACK)
448 : /* _G.unpack = table.unpack */
449 : lua_getfield(L, -1, "unpack");
450 : lua_setglobal(L, "unpack");
451 : #endif
452 92 : return 1;
453 : }
454 :
|
