diff options
Diffstat (limited to 'src/lib_table.c')
-rw-r--r-- | src/lib_table.c | 276 |
1 files changed, 276 insertions, 0 deletions
diff --git a/src/lib_table.c b/src/lib_table.c new file mode 100644 index 00000000..68dc825b --- /dev/null +++ b/src/lib_table.c | |||
@@ -0,0 +1,276 @@ | |||
1 | /* | ||
2 | ** Table library. | ||
3 | ** Copyright (C) 2005-2009 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 | |||
26 | LJLIB_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 | |||
46 | LJLIB_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 | |||
65 | LJLIB_ASM(table_getn) LJLIB_REC(.) | ||
66 | { | ||
67 | lj_lib_checktab(L, 1); | ||
68 | return FFH_UNREACHABLE; | ||
69 | } | ||
70 | |||
71 | LJLIB_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 | uint32_t i; | ||
78 | for (i = 0; i < t->asize; i++) | ||
79 | if (!tvisnil(&array[i])) { | ||
80 | m = (lua_Number)i; | ||
81 | break; | ||
82 | } | ||
83 | node = noderef(t->node); | ||
84 | for (i = 0; i <= t->hmask; i++) | ||
85 | if (tvisnum(&node[i].key) && numV(&node[i].key) > m) | ||
86 | m = numV(&node[i].key); | ||
87 | setnumV(L->top-1, m); | ||
88 | return 1; | ||
89 | } | ||
90 | |||
91 | LJLIB_CF(table_insert) | ||
92 | { | ||
93 | GCtab *t = lj_lib_checktab(L, 1); | ||
94 | int32_t n, i = (int32_t)lj_tab_len(t) + 1; | ||
95 | int nargs = (int)((char *)L->top - (char *)L->base); | ||
96 | if (nargs != 2*sizeof(TValue)) { | ||
97 | if (nargs != 3*sizeof(TValue)) | ||
98 | lj_err_caller(L, LJ_ERR_TABINS); | ||
99 | /* NOBARRIER: This just moves existing elements around. */ | ||
100 | for (n = lj_lib_checkint(L, 2); i > n; i--) { | ||
101 | /* The set may invalidate the get pointer, so need to do it first! */ | ||
102 | TValue *dst = lj_tab_setint(L, t, i); | ||
103 | cTValue *src = lj_tab_getint(t, i-1); | ||
104 | if (src) { | ||
105 | copyTV(L, dst, src); | ||
106 | } else { | ||
107 | setnilV(dst); | ||
108 | } | ||
109 | } | ||
110 | i = n; | ||
111 | } | ||
112 | { | ||
113 | TValue *dst = lj_tab_setint(L, t, i); | ||
114 | copyTV(L, dst, L->top-1); | ||
115 | lj_gc_barriert(L, t, dst); | ||
116 | } | ||
117 | return 0; | ||
118 | } | ||
119 | |||
120 | LJLIB_CF(table_remove) | ||
121 | { | ||
122 | GCtab *t = lj_lib_checktab(L, 1); | ||
123 | int32_t e = (int32_t)lj_tab_len(t); | ||
124 | int32_t pos = lj_lib_optint(L, 2, e); | ||
125 | if (!(1 <= pos && pos <= e)) /* position is outside bounds? */ | ||
126 | return 0; /* nothing to remove */ | ||
127 | lua_rawgeti(L, 1, pos); | ||
128 | /* NOBARRIER: This just moves existing elements around. */ | ||
129 | for (; pos < e; pos++) { | ||
130 | cTValue *src = lj_tab_getint(t, pos+1); | ||
131 | TValue *dst = lj_tab_setint(L, t, pos); | ||
132 | if (src) { | ||
133 | copyTV(L, dst, src); | ||
134 | } else { | ||
135 | setnilV(dst); | ||
136 | } | ||
137 | } | ||
138 | setnilV(lj_tab_setint(L, t, e)); | ||
139 | return 1; | ||
140 | } | ||
141 | |||
142 | LJLIB_CF(table_concat) | ||
143 | { | ||
144 | luaL_Buffer b; | ||
145 | GCtab *t = lj_lib_checktab(L, 1); | ||
146 | GCstr *sep = lj_lib_optstr(L, 2); | ||
147 | MSize seplen = sep ? sep->len : 0; | ||
148 | int32_t i = lj_lib_optint(L, 3, 1); | ||
149 | int32_t e = L->base+3 < L->top ? lj_lib_checkint(L, 4) : | ||
150 | (int32_t)lj_tab_len(t); | ||
151 | luaL_buffinit(L, &b); | ||
152 | if (i <= e) { | ||
153 | for (;;) { | ||
154 | cTValue *o; | ||
155 | lua_rawgeti(L, 1, i); | ||
156 | o = L->top-1; | ||
157 | if (!(tvisstr(o) || tvisnum(o))) | ||
158 | lj_err_callerv(L, LJ_ERR_TABCAT, typename(o), i); | ||
159 | luaL_addvalue(&b); | ||
160 | if (i++ == e) break; | ||
161 | if (seplen) | ||
162 | luaL_addlstring(&b, strdata(sep), seplen); | ||
163 | } | ||
164 | } | ||
165 | luaL_pushresult(&b); | ||
166 | return 1; | ||
167 | } | ||
168 | |||
169 | /* ------------------------------------------------------------------------ */ | ||
170 | |||
171 | static void set2(lua_State *L, int i, int j) | ||
172 | { | ||
173 | lua_rawseti(L, 1, i); | ||
174 | lua_rawseti(L, 1, j); | ||
175 | } | ||
176 | |||
177 | static int sort_comp(lua_State *L, int a, int b) | ||
178 | { | ||
179 | if (!lua_isnil(L, 2)) { /* function? */ | ||
180 | int res; | ||
181 | lua_pushvalue(L, 2); | ||
182 | lua_pushvalue(L, a-1); /* -1 to compensate function */ | ||
183 | lua_pushvalue(L, b-2); /* -2 to compensate function and `a' */ | ||
184 | lua_call(L, 2, 1); | ||
185 | res = lua_toboolean(L, -1); | ||
186 | lua_pop(L, 1); | ||
187 | return res; | ||
188 | } else { /* a < b? */ | ||
189 | return lua_lessthan(L, a, b); | ||
190 | } | ||
191 | } | ||
192 | |||
193 | static void auxsort(lua_State *L, int l, int u) | ||
194 | { | ||
195 | while (l < u) { /* for tail recursion */ | ||
196 | int i, j; | ||
197 | /* sort elements a[l], a[(l+u)/2] and a[u] */ | ||
198 | lua_rawgeti(L, 1, l); | ||
199 | lua_rawgeti(L, 1, u); | ||
200 | if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ | ||
201 | set2(L, l, u); /* swap a[l] - a[u] */ | ||
202 | else | ||
203 | lua_pop(L, 2); | ||
204 | if (u-l == 1) break; /* only 2 elements */ | ||
205 | i = (l+u)/2; | ||
206 | lua_rawgeti(L, 1, i); | ||
207 | lua_rawgeti(L, 1, l); | ||
208 | if (sort_comp(L, -2, -1)) { /* a[i]<a[l]? */ | ||
209 | set2(L, i, l); | ||
210 | } else { | ||
211 | lua_pop(L, 1); /* remove a[l] */ | ||
212 | lua_rawgeti(L, 1, u); | ||
213 | if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */ | ||
214 | set2(L, i, u); | ||
215 | else | ||
216 | lua_pop(L, 2); | ||
217 | } | ||
218 | if (u-l == 2) break; /* only 3 elements */ | ||
219 | lua_rawgeti(L, 1, i); /* Pivot */ | ||
220 | lua_pushvalue(L, -1); | ||
221 | lua_rawgeti(L, 1, u-1); | ||
222 | set2(L, i, u-1); | ||
223 | /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ | ||
224 | i = l; j = u-1; | ||
225 | for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ | ||
226 | /* repeat ++i until a[i] >= P */ | ||
227 | while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) { | ||
228 | if (i>u) lj_err_caller(L, LJ_ERR_TABSORT); | ||
229 | lua_pop(L, 1); /* remove a[i] */ | ||
230 | } | ||
231 | /* repeat --j until a[j] <= P */ | ||
232 | while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) { | ||
233 | if (j<l) lj_err_caller(L, LJ_ERR_TABSORT); | ||
234 | lua_pop(L, 1); /* remove a[j] */ | ||
235 | } | ||
236 | if (j<i) { | ||
237 | lua_pop(L, 3); /* pop pivot, a[i], a[j] */ | ||
238 | break; | ||
239 | } | ||
240 | set2(L, i, j); | ||
241 | } | ||
242 | lua_rawgeti(L, 1, u-1); | ||
243 | lua_rawgeti(L, 1, i); | ||
244 | set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */ | ||
245 | /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ | ||
246 | /* adjust so that smaller half is in [j..i] and larger one in [l..u] */ | ||
247 | if (i-l < u-i) { | ||
248 | j=l; i=i-1; l=i+2; | ||
249 | } else { | ||
250 | j=i+1; i=u; u=j-2; | ||
251 | } | ||
252 | auxsort(L, j, i); /* call recursively the smaller one */ | ||
253 | } /* repeat the routine for the larger one */ | ||
254 | } | ||
255 | |||
256 | LJLIB_CF(table_sort) | ||
257 | { | ||
258 | GCtab *t = lj_lib_checktab(L, 1); | ||
259 | int32_t n = (int32_t)lj_tab_len(t); | ||
260 | lua_settop(L, 2); | ||
261 | if (!tvisnil(L->base+1)) | ||
262 | lj_lib_checkfunc(L, 2); | ||
263 | auxsort(L, 1, n); | ||
264 | return 0; | ||
265 | } | ||
266 | |||
267 | /* ------------------------------------------------------------------------ */ | ||
268 | |||
269 | #include "lj_libdef.h" | ||
270 | |||
271 | LUALIB_API int luaopen_table(lua_State *L) | ||
272 | { | ||
273 | LJ_LIB_REG(L, table); | ||
274 | return 1; | ||
275 | } | ||
276 | |||