1/*
2** Table library.
3** Copyright (C) 2005-2021 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_buf.h"
20#include "lj_tab.h"
21#include "lj_ff.h"
22#include "lj_lib.h"
23
24/* ------------------------------------------------------------------------ */
25
26#define LJLIB_MODULE_table
27
28LJLIB_LUA(table_foreachi) /*
29 function(t, f)
30 CHECK_tab(t)
31 CHECK_func(f)
32 for i=1,#t do
33 local r = f(i, t[i])
34 if r ~= nil then return r end
35 end
36 end
37*/
38
39LJLIB_LUA(table_foreach) /*
40 function(t, f)
41 CHECK_tab(t)
42 CHECK_func(f)
43 for k, v in PAIRS(t) do
44 local r = f(k, v)
45 if r ~= nil then return r end
46 end
47 end
48*/
49
50LJLIB_LUA(table_getn) /*
51 function(t)
52 CHECK_tab(t)
53 return #t
54 end
55*/
56
57LJLIB_CF(table_maxn)
58{
59 GCtab *t = lj_lib_checktab(L, 1);
60 TValue *array = tvref(t->array);
61 Node *node;
62 lua_Number m = 0;
63 ptrdiff_t i;
64 for (i = (ptrdiff_t)t->asize - 1; i >= 0; i--)
65 if (!tvisnil(&array[i])) {
66 m = (lua_Number)(int32_t)i;
67 break;
68 }
69 node = noderef(t->node);
70 for (i = (ptrdiff_t)t->hmask; i >= 0; i--)
71 if (!tvisnil(&node[i].val) && tvisnumber(&node[i].key)) {
72 lua_Number n = numberVnum(&node[i].key);
73 if (n > m) m = n;
74 }
75 setnumV(L->top-1, m);
76 return 1;
77}
78
79LJLIB_CF(table_insert) LJLIB_REC(.)
80{
81 GCtab *t = lj_lib_checktab(L, 1);
82 int32_t n, i = (int32_t)lj_tab_len(t) + 1;
83 int nargs = (int)((char *)L->top - (char *)L->base);
84 if (nargs != 2*sizeof(TValue)) {
85 if (nargs != 3*sizeof(TValue))
86 lj_err_caller(L, LJ_ERR_TABINS);
87 /* NOBARRIER: This just moves existing elements around. */
88 for (n = lj_lib_checkint(L, 2); i > n; i--) {
89 /* The set may invalidate the get pointer, so need to do it first! */
90 TValue *dst = lj_tab_setint(L, t, i);
91 cTValue *src = lj_tab_getint(t, i-1);
92 if (src) {
93 copyTV(L, dst, src);
94 } else {
95 setnilV(dst);
96 }
97 }
98 i = n;
99 }
100 {
101 TValue *dst = lj_tab_setint(L, t, i);
102 copyTV(L, dst, L->top-1); /* Set new value. */
103 lj_gc_barriert(L, t, dst);
104 }
105 return 0;
106}
107
108LJLIB_LUA(table_remove) /*
109 function(t, pos)
110 CHECK_tab(t)
111 local len = #t
112 if pos == nil then
113 if len ~= 0 then
114 local old = t[len]
115 t[len] = nil
116 return old
117 end
118 else
119 CHECK_int(pos)
120 if pos >= 1 and pos <= len then
121 local old = t[pos]
122 for i=pos+1,len do
123 t[i-1] = t[i]
124 end
125 t[len] = nil
126 return old
127 end
128 end
129 end
130*/
131
132LJLIB_LUA(table_move) /*
133 function(a1, f, e, t, a2)
134 CHECK_tab(a1)
135 CHECK_int(f)
136 CHECK_int(e)
137 CHECK_int(t)
138 if a2 == nil then a2 = a1 end
139 CHECK_tab(a2)
140 if e >= f then
141 local d = t - f
142 if t > e or t <= f or a2 ~= a1 then
143 for i=f,e do a2[i+d] = a1[i] end
144 else
145 for i=e,f,-1 do a2[i+d] = a1[i] end
146 end
147 end
148 return a2
149 end
150*/
151
152LJLIB_CF(table_concat) LJLIB_REC(.)
153{
154 GCtab *t = lj_lib_checktab(L, 1);
155 GCstr *sep = lj_lib_optstr(L, 2);
156 int32_t i = lj_lib_optint(L, 3, 1);
157 int32_t e = (L->base+3 < L->top && !tvisnil(L->base+3)) ?
158 lj_lib_checkint(L, 4) : (int32_t)lj_tab_len(t);
159 SBuf *sb = lj_buf_tmp_(L);
160 SBuf *sbx = lj_buf_puttab(sb, t, sep, i, e);
161 if (LJ_UNLIKELY(!sbx)) { /* Error: bad element type. */
162 int32_t idx = (int32_t)(intptr_t)sbufP(sb);
163 cTValue *o = lj_tab_getint(t, idx);
164 lj_err_callerv(L, LJ_ERR_TABCAT,
165 lj_obj_itypename[o ? itypemap(o) : ~LJ_TNIL], idx);
166 }
167 setstrV(L, L->top-1, lj_buf_str(L, sbx));
168 lj_gc_check(L);
169 return 1;
170}
171
172/* ------------------------------------------------------------------------ */
173
174static void set2(lua_State *L, int i, int j)
175{
176 lua_rawseti(L, 1, i);
177 lua_rawseti(L, 1, j);
178}
179
180static int sort_comp(lua_State *L, int a, int b)
181{
182 if (!lua_isnil(L, 2)) { /* function? */
183 int res;
184 lua_pushvalue(L, 2);
185 lua_pushvalue(L, a-1); /* -1 to compensate function */
186 lua_pushvalue(L, b-2); /* -2 to compensate function and `a' */
187 lua_call(L, 2, 1);
188 res = lua_toboolean(L, -1);
189 lua_pop(L, 1);
190 return res;
191 } else { /* a < b? */
192 return lua_lessthan(L, a, b);
193 }
194}
195
196static void auxsort(lua_State *L, int l, int u)
197{
198 while (l < u) { /* for tail recursion */
199 int i, j;
200 /* sort elements a[l], a[(l+u)/2] and a[u] */
201 lua_rawgeti(L, 1, l);
202 lua_rawgeti(L, 1, u);
203 if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */
204 set2(L, l, u); /* swap a[l] - a[u] */
205 else
206 lua_pop(L, 2);
207 if (u-l == 1) break; /* only 2 elements */
208 i = (l+u)/2;
209 lua_rawgeti(L, 1, i);
210 lua_rawgeti(L, 1, l);
211 if (sort_comp(L, -2, -1)) { /* a[i]<a[l]? */
212 set2(L, i, l);
213 } else {
214 lua_pop(L, 1); /* remove a[l] */
215 lua_rawgeti(L, 1, u);
216 if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */
217 set2(L, i, u);
218 else
219 lua_pop(L, 2);
220 }
221 if (u-l == 2) break; /* only 3 elements */
222 lua_rawgeti(L, 1, i); /* Pivot */
223 lua_pushvalue(L, -1);
224 lua_rawgeti(L, 1, u-1);
225 set2(L, i, u-1);
226 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
227 i = l; j = u-1;
228 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
229 /* repeat ++i until a[i] >= P */
230 while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
231 if (i>=u) lj_err_caller(L, LJ_ERR_TABSORT);
232 lua_pop(L, 1); /* remove a[i] */
233 }
234 /* repeat --j until a[j] <= P */
235 while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
236 if (j<=l) lj_err_caller(L, LJ_ERR_TABSORT);
237 lua_pop(L, 1); /* remove a[j] */
238 }
239 if (j<i) {
240 lua_pop(L, 3); /* pop pivot, a[i], a[j] */
241 break;
242 }
243 set2(L, i, j);
244 }
245 lua_rawgeti(L, 1, u-1);
246 lua_rawgeti(L, 1, i);
247 set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */
248 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
249 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
250 if (i-l < u-i) {
251 j=l; i=i-1; l=i+2;
252 } else {
253 j=i+1; i=u; u=j-2;
254 }
255 auxsort(L, j, i); /* call recursively the smaller one */
256 } /* repeat the routine for the larger one */
257}
258
259LJLIB_CF(table_sort)
260{
261 GCtab *t = lj_lib_checktab(L, 1);
262 int32_t n = (int32_t)lj_tab_len(t);
263 lua_settop(L, 2);
264 if (!tvisnil(L->base+1))
265 lj_lib_checkfunc(L, 2);
266 auxsort(L, 1, n);
267 return 0;
268}
269
270#if LJ_52
271LJLIB_PUSH("n")
272LJLIB_CF(table_pack)
273{
274 TValue *array, *base = L->base;
275 MSize i, n = (uint32_t)(L->top - base);
276 GCtab *t = lj_tab_new(L, n ? n+1 : 0, 1);
277 /* NOBARRIER: The table is new (marked white). */
278 setintV(lj_tab_setstr(L, t, strV(lj_lib_upvalue(L, 1))), (int32_t)n);
279 for (array = tvref(t->array) + 1, i = 0; i < n; i++)
280 copyTV(L, &array[i], &base[i]);
281 settabV(L, base, t);
282 L->top = base+1;
283 lj_gc_check(L);
284 return 1;
285}
286#endif
287
288LJLIB_NOREG LJLIB_CF(table_new) LJLIB_REC(.)
289{
290 int32_t a = lj_lib_checkint(L, 1);
291 int32_t h = lj_lib_checkint(L, 2);
292 lua_createtable(L, a, h);
293 return 1;
294}
295
296LJLIB_NOREG LJLIB_CF(table_clear) LJLIB_REC(.)
297{
298 lj_tab_clear(lj_lib_checktab(L, 1));
299 return 0;
300}
301
302static int luaopen_table_new(lua_State *L)
303{
304 return lj_lib_postreg(L, lj_cf_table_new, FF_table_new, "new");
305}
306
307static int luaopen_table_clear(lua_State *L)
308{
309 return lj_lib_postreg(L, lj_cf_table_clear, FF_table_clear, "clear");
310}
311
312/* ------------------------------------------------------------------------ */
313
314#include "lj_libdef.h"
315
316LUALIB_API int luaopen_table(lua_State *L)
317{
318 LJ_LIB_REG(L, LUA_TABLIBNAME, table);
319#if LJ_52
320 lua_getglobal(L, "unpack");
321 lua_setfield(L, -2, "unpack");
322#endif
323 lj_lib_prereg(L, LUA_TABLIBNAME ".new", luaopen_table_new, tabV(L->top-1));
324 lj_lib_prereg(L, LUA_TABLIBNAME ".clear", luaopen_table_clear, tabV(L->top-1));
325 return 1;
326}
327
328