1/*
2** Table library.
3** Copyright (C) 2005-2014 Mike Pall. See Copyright Notice in luajit.h
4**
5** Major portions taken verbatim or adapted from the Lua interpreter.
6** Copyright (C) 1994-2008 Lua.org, PUC-Rio. See Copyright Notice in lua.h
7*/
8
9#define lib_table_c
10#define LUA_LIB
11
12#include "lua.h"
13#include "lauxlib.h"
14#include "lualib.h"
15
16#include "lj_obj.h"
17#include "lj_gc.h"
18#include "lj_err.h"
19#include "lj_tab.h"
20#include "lj_lib.h"
21
22/* ------------------------------------------------------------------------ */
23
24#define LJLIB_MODULE_table
25
26LJLIB_CF(table_foreachi)
27{
28 GCtab *t = lj_lib_checktab(L, 1);
29 GCfunc *func = lj_lib_checkfunc(L, 2);
30 MSize i, n = lj_tab_len(t);
31 for (i = 1; i <= n; i++) {
32 cTValue *val;
33 setfuncV(L, L->top, func);
34 setintV(L->top+1, i);
35 val = lj_tab_getint(t, (int32_t)i);
36 if (val) { copyTV(L, L->top+2, val); } else { setnilV(L->top+2); }
37 L->top += 3;
38 lua_call(L, 2, 1);
39 if (!tvisnil(L->top-1))
40 return 1;
41 L->top--;
42 }
43 return 0;
44}
45
46LJLIB_CF(table_foreach)
47{
48 GCtab *t = lj_lib_checktab(L, 1);
49 GCfunc *func = lj_lib_checkfunc(L, 2);
50 L->top = L->base+3;
51 setnilV(L->top-1);
52 while (lj_tab_next(L, t, L->top-1)) {
53 copyTV(L, L->top+2, L->top);
54 copyTV(L, L->top+1, L->top-1);
55 setfuncV(L, L->top, func);
56 L->top += 3;
57 lua_call(L, 2, 1);
58 if (!tvisnil(L->top-1))
59 return 1;
60 L->top--;
61 }
62 return 0;
63}
64
65LJLIB_ASM(table_getn) LJLIB_REC(.)
66{
67 lj_lib_checktab(L, 1);
68 return FFH_UNREACHABLE;
69}
70
71LJLIB_CF(table_maxn)
72{
73 GCtab *t = lj_lib_checktab(L, 1);
74 TValue *array = tvref(t->array);
75 Node *node;
76 lua_Number m = 0;
77 ptrdiff_t i;
78 for (i = (ptrdiff_t)t->asize - 1; i >= 0; i--)
79 if (!tvisnil(&array[i])) {
80 m = (lua_Number)(int32_t)i;
81 break;
82 }
83 node = noderef(t->node);
84 for (i = (ptrdiff_t)t->hmask; i >= 0; i--)
85 if (!tvisnil(&node[i].val) && tvisnumber(&node[i].key)) {
86 lua_Number n = numberVnum(&node[i].key);
87 if (n > m) m = n;
88 }
89 setnumV(L->top-1, m);
90 return 1;
91}
92
93LJLIB_CF(table_insert) LJLIB_REC(.)
94{
95 GCtab *t = lj_lib_checktab(L, 1);
96 int32_t n, i = (int32_t)lj_tab_len(t) + 1;
97 int nargs = (int)((char *)L->top - (char *)L->base);
98 if (nargs != 2*sizeof(TValue)) {
99 if (nargs != 3*sizeof(TValue))
100 lj_err_caller(L, LJ_ERR_TABINS);
101 /* NOBARRIER: This just moves existing elements around. */
102 for (n = lj_lib_checkint(L, 2); i > n; i--) {
103 /* The set may invalidate the get pointer, so need to do it first! */
104 TValue *dst = lj_tab_setint(L, t, i);
105 cTValue *src = lj_tab_getint(t, i-1);
106 if (src) {
107 copyTV(L, dst, src);
108 } else {
109 setnilV(dst);
110 }
111 }
112 i = n;
113 }
114 {
115 TValue *dst = lj_tab_setint(L, t, i);
116 copyTV(L, dst, L->top-1); /* Set new value. */
117 lj_gc_barriert(L, t, dst);
118 }
119 return 0;
120}
121
122LJLIB_CF(table_remove) LJLIB_REC(.)
123{
124 GCtab *t = lj_lib_checktab(L, 1);
125 int32_t e = (int32_t)lj_tab_len(t);
126 int32_t pos = lj_lib_optint(L, 2, e);
127 if (!(1 <= pos && pos <= e)) /* Nothing to remove? */
128 return 0;
129 lua_rawgeti(L, 1, pos); /* Get previous value. */
130 /* NOBARRIER: This just moves existing elements around. */
131 for (; pos < e; pos++) {
132 cTValue *src = lj_tab_getint(t, pos+1);
133 TValue *dst = lj_tab_setint(L, t, pos);
134 if (src) {
135 copyTV(L, dst, src);
136 } else {
137 setnilV(dst);
138 }
139 }
140 setnilV(lj_tab_setint(L, t, e)); /* Remove (last) value. */
141 return 1; /* Return previous value. */
142}
143
144LJLIB_CF(table_concat)
145{
146 luaL_Buffer b;
147 GCtab *t = lj_lib_checktab(L, 1);
148 GCstr *sep = lj_lib_optstr(L, 2);
149 MSize seplen = sep ? sep->len : 0;
150 int32_t i = lj_lib_optint(L, 3, 1);
151 int32_t e = (L->base+3 < L->top && !tvisnil(L->base+3)) ?
152 lj_lib_checkint(L, 4) : (int32_t)lj_tab_len(t);
153 luaL_buffinit(L, &b);
154 if (i <= e) {
155 for (;;) {
156 cTValue *o;
157 lua_rawgeti(L, 1, i);
158 o = L->top-1;
159 if (!(tvisstr(o) || tvisnumber(o)))
160 lj_err_callerv(L, LJ_ERR_TABCAT, lj_typename(o), i);
161 luaL_addvalue(&b);
162 if (i++ == e) break;
163 if (seplen)
164 luaL_addlstring(&b, strdata(sep), seplen);
165 }
166 }
167 luaL_pushresult(&b);
168 return 1;
169}
170
171/* ------------------------------------------------------------------------ */
172
173static void set2(lua_State *L, int i, int j)
174{
175 lua_rawseti(L, 1, i);
176 lua_rawseti(L, 1, j);
177}
178
179static int sort_comp(lua_State *L, int a, int b)
180{
181 if (!lua_isnil(L, 2)) { /* function? */
182 int res;
183 lua_pushvalue(L, 2);
184 lua_pushvalue(L, a-1); /* -1 to compensate function */
185 lua_pushvalue(L, b-2); /* -2 to compensate function and `a' */
186 lua_call(L, 2, 1);
187 res = lua_toboolean(L, -1);
188 lua_pop(L, 1);
189 return res;
190 } else { /* a < b? */
191 return lua_lessthan(L, a, b);
192 }
193}
194
195static void auxsort(lua_State *L, int l, int u)
196{
197 while (l < u) { /* for tail recursion */
198 int i, j;
199 /* sort elements a[l], a[(l+u)/2] and a[u] */
200 lua_rawgeti(L, 1, l);
201 lua_rawgeti(L, 1, u);
202 if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */
203 set2(L, l, u); /* swap a[l] - a[u] */
204 else
205 lua_pop(L, 2);
206 if (u-l == 1) break; /* only 2 elements */
207 i = (l+u)/2;
208 lua_rawgeti(L, 1, i);
209 lua_rawgeti(L, 1, l);
210 if (sort_comp(L, -2, -1)) { /* a[i]<a[l]? */
211 set2(L, i, l);
212 } else {
213 lua_pop(L, 1); /* remove a[l] */
214 lua_rawgeti(L, 1, u);
215 if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */
216 set2(L, i, u);
217 else
218 lua_pop(L, 2);
219 }
220 if (u-l == 2) break; /* only 3 elements */
221 lua_rawgeti(L, 1, i); /* Pivot */
222 lua_pushvalue(L, -1);
223 lua_rawgeti(L, 1, u-1);
224 set2(L, i, u-1);
225 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
226 i = l; j = u-1;
227 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
228 /* repeat ++i until a[i] >= P */
229 while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
230 if (i>=u) lj_err_caller(L, LJ_ERR_TABSORT);
231 lua_pop(L, 1); /* remove a[i] */
232 }
233 /* repeat --j until a[j] <= P */
234 while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
235 if (j<=l) lj_err_caller(L, LJ_ERR_TABSORT);
236 lua_pop(L, 1); /* remove a[j] */
237 }
238 if (j<i) {
239 lua_pop(L, 3); /* pop pivot, a[i], a[j] */
240 break;
241 }
242 set2(L, i, j);
243 }
244 lua_rawgeti(L, 1, u-1);
245 lua_rawgeti(L, 1, i);
246 set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */
247 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
248 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
249 if (i-l < u-i) {
250 j=l; i=i-1; l=i+2;
251 } else {
252 j=i+1; i=u; u=j-2;
253 }
254 auxsort(L, j, i); /* call recursively the smaller one */
255 } /* repeat the routine for the larger one */
256}
257
258LJLIB_CF(table_sort)
259{
260 GCtab *t = lj_lib_checktab(L, 1);
261 int32_t n = (int32_t)lj_tab_len(t);
262 lua_settop(L, 2);
263 if (!tvisnil(L->base+1))
264 lj_lib_checkfunc(L, 2);
265 auxsort(L, 1, n);
266 return 0;
267}
268
269#if LJ_52
270LJLIB_PUSH("n")
271LJLIB_CF(table_pack)
272{
273 TValue *array, *base = L->base;
274 MSize i, n = (uint32_t)(L->top - base);
275 GCtab *t = lj_tab_new(L, n ? n+1 : 0, 1);
276 /* NOBARRIER: The table is new (marked white). */
277 setintV(lj_tab_setstr(L, t, strV(lj_lib_upvalue(L, 1))), (int32_t)n);
278 for (array = tvref(t->array) + 1, i = 0; i < n; i++)
279 copyTV(L, &array[i], &base[i]);
280 settabV(L, base, t);
281 L->top = base+1;
282 lj_gc_check(L);
283 return 1;
284}
285#endif
286
287/* ------------------------------------------------------------------------ */
288
289#include "lj_libdef.h"
290
291LUALIB_API int luaopen_table(lua_State *L)
292{
293 LJ_LIB_REG(L, LUA_TABLIBNAME, table);
294#if LJ_52
295 lua_getglobal(L, "unpack");
296 lua_setfield(L, -2, "unpack");
297#endif
298 return 1;
299}
300
301