]>
git.zerfleddert.de Git - proxmark3-svn/blob - liblua/ltablib.c
2 ** $Id: ltablib.c,v 1.65 2013/03/07 18:17:24 roberto Exp $
3 ** Library for Table Manipulation
4 ** See Copyright Notice in lua.h
19 #define aux_getn(L,n) (luaL_checktype(L, n, LUA_TTABLE), luaL_len(L, n))
23 #if defined(LUA_COMPAT_MAXN)
24 static int maxn (lua_State
*L
) {
26 luaL_checktype(L
, 1, LUA_TTABLE
);
27 lua_pushnil(L
); /* first key */
28 while (lua_next(L
, 1)) {
29 lua_pop(L
, 1); /* remove value */
30 if (lua_type(L
, -1) == LUA_TNUMBER
) {
31 lua_Number v
= lua_tonumber(L
, -1);
35 lua_pushnumber(L
, max
);
41 static int tinsert (lua_State
*L
) {
42 int e
= aux_getn(L
, 1) + 1; /* first empty element */
43 int pos
; /* where to insert new element */
44 switch (lua_gettop(L
)) {
45 case 2: { /* called with only 2 arguments */
46 pos
= e
; /* insert new element at the end */
51 pos
= luaL_checkint(L
, 2); /* 2nd argument is the position */
52 luaL_argcheck(L
, 1 <= pos
&& pos
<= e
, 2, "position out of bounds");
53 for (i
= e
; i
> pos
; i
--) { /* move up elements */
54 lua_rawgeti(L
, 1, i
-1);
55 lua_rawseti(L
, 1, i
); /* t[i] = t[i-1] */
60 return luaL_error(L
, "wrong number of arguments to " LUA_QL("insert"));
63 lua_rawseti(L
, 1, pos
); /* t[pos] = v */
68 static int tremove (lua_State
*L
) {
69 int size
= aux_getn(L
, 1);
70 int pos
= luaL_optint(L
, 2, size
);
71 if (pos
!= size
) /* validate 'pos' if given */
72 luaL_argcheck(L
, 1 <= pos
&& pos
<= size
+ 1, 1, "position out of bounds");
73 lua_rawgeti(L
, 1, pos
); /* result = t[pos] */
74 for ( ; pos
< size
; pos
++) {
75 lua_rawgeti(L
, 1, pos
+1);
76 lua_rawseti(L
, 1, pos
); /* t[pos] = t[pos+1] */
79 lua_rawseti(L
, 1, pos
); /* t[pos] = nil */
84 static void addfield (lua_State
*L
, luaL_Buffer
*b
, int i
) {
86 if (!lua_isstring(L
, -1))
87 luaL_error(L
, "invalid value (%s) at index %d in table for "
88 LUA_QL("concat"), luaL_typename(L
, -1), i
);
93 static int tconcat (lua_State
*L
) {
97 const char *sep
= luaL_optlstring(L
, 2, "", &lsep
);
98 luaL_checktype(L
, 1, LUA_TTABLE
);
99 i
= luaL_optint(L
, 3, 1);
100 last
= luaL_opt(L
, luaL_checkint
, 4, luaL_len(L
, 1));
101 luaL_buffinit(L
, &b
);
102 for (; i
< last
; i
++) {
104 luaL_addlstring(&b
, sep
, lsep
);
106 if (i
== last
) /* add last value (if interval was not empty) */
114 ** {======================================================
116 ** =======================================================
119 static int pack (lua_State
*L
) {
120 int n
= lua_gettop(L
); /* number of elements to pack */
121 lua_createtable(L
, n
, 1); /* create result table */
122 lua_pushinteger(L
, n
);
123 lua_setfield(L
, -2, "n"); /* t.n = number of elements */
124 if (n
> 0) { /* at least one element? */
127 lua_rawseti(L
, -2, 1); /* insert first element */
128 lua_replace(L
, 1); /* move table into index 1 */
129 for (i
= n
; i
>= 2; i
--) /* assign other elements */
130 lua_rawseti(L
, 1, i
);
132 return 1; /* return table */
136 static int unpack (lua_State
*L
) {
138 luaL_checktype(L
, 1, LUA_TTABLE
);
139 i
= luaL_optint(L
, 2, 1);
140 e
= luaL_opt(L
, luaL_checkint
, 3, luaL_len(L
, 1));
141 if (i
> e
) return 0; /* empty range */
142 n
= e
- i
+ 1; /* number of elements */
143 if (n
<= 0 || !lua_checkstack(L
, n
)) /* n <= 0 means arith. overflow */
144 return luaL_error(L
, "too many results to unpack");
145 lua_rawgeti(L
, 1, i
); /* push arg[i] (avoiding overflow problems) */
146 while (i
++ < e
) /* push arg[i + 1...e] */
147 lua_rawgeti(L
, 1, i
);
151 /* }====================================================== */
156 ** {======================================================
158 ** (based on `Algorithms in MODULA-3', Robert Sedgewick;
159 ** Addison-Wesley, 1993.)
160 ** =======================================================
164 static void set2 (lua_State
*L
, int i
, int j
) {
165 lua_rawseti(L
, 1, i
);
166 lua_rawseti(L
, 1, j
);
169 static int sort_comp (lua_State
*L
, int a
, int b
) {
170 if (!lua_isnil(L
, 2)) { /* function? */
173 lua_pushvalue(L
, a
-1); /* -1 to compensate function */
174 lua_pushvalue(L
, b
-2); /* -2 to compensate function and `a' */
176 res
= lua_toboolean(L
, -1);
181 return lua_compare(L
, a
, b
, LUA_OPLT
);
184 static void auxsort (lua_State
*L
, int l
, int u
) {
185 while (l
< u
) { /* for tail recursion */
187 /* sort elements a[l], a[(l+u)/2] and a[u] */
188 lua_rawgeti(L
, 1, l
);
189 lua_rawgeti(L
, 1, u
);
190 if (sort_comp(L
, -1, -2)) /* a[u] < a[l]? */
191 set2(L
, l
, u
); /* swap a[l] - a[u] */
194 if (u
-l
== 1) break; /* only 2 elements */
196 lua_rawgeti(L
, 1, i
);
197 lua_rawgeti(L
, 1, l
);
198 if (sort_comp(L
, -2, -1)) /* a[i]<a[l]? */
201 lua_pop(L
, 1); /* remove a[l] */
202 lua_rawgeti(L
, 1, u
);
203 if (sort_comp(L
, -1, -2)) /* a[u]<a[i]? */
208 if (u
-l
== 2) break; /* only 3 elements */
209 lua_rawgeti(L
, 1, i
); /* Pivot */
210 lua_pushvalue(L
, -1);
211 lua_rawgeti(L
, 1, u
-1);
213 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
215 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
216 /* repeat ++i until a[i] >= P */
217 while (lua_rawgeti(L
, 1, ++i
), sort_comp(L
, -1, -2)) {
218 if (i
>=u
) luaL_error(L
, "invalid order function for sorting");
219 lua_pop(L
, 1); /* remove a[i] */
221 /* repeat --j until a[j] <= P */
222 while (lua_rawgeti(L
, 1, --j
), sort_comp(L
, -3, -1)) {
223 if (j
<=l
) luaL_error(L
, "invalid order function for sorting");
224 lua_pop(L
, 1); /* remove a[j] */
227 lua_pop(L
, 3); /* pop pivot, a[i], a[j] */
232 lua_rawgeti(L
, 1, u
-1);
233 lua_rawgeti(L
, 1, i
);
234 set2(L
, u
-1, i
); /* swap pivot (a[u-1]) with a[i] */
235 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
236 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
243 auxsort(L
, j
, i
); /* call recursively the smaller one */
244 } /* repeat the routine for the larger one */
247 static int sort (lua_State
*L
) {
248 int n
= aux_getn(L
, 1);
249 luaL_checkstack(L
, 40, ""); /* assume array is smaller than 2^40 */
250 if (!lua_isnoneornil(L
, 2)) /* is there a 2nd argument? */
251 luaL_checktype(L
, 2, LUA_TFUNCTION
);
252 lua_settop(L
, 2); /* make sure there is two arguments */
257 /* }====================================================== */
260 static const luaL_Reg tab_funcs
[] = {
262 #if defined(LUA_COMPAT_MAXN)
274 LUAMOD_API
int luaopen_table (lua_State
*L
) {
275 luaL_newlib(L
, tab_funcs
);
276 #if defined(LUA_COMPAT_UNPACK)
277 /* _G.unpack = table.unpack */
278 lua_getfield(L
, -1, "unpack");
279 lua_setglobal(L
, "unpack");