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