]>
git.proxmox.com Git - ceph.git/blob - ceph/src/civetweb/src/third_party/lua-5.3.1/src/ltablib.c
2 ** $Id: ltablib.c,v 1.80 2015/01/13 16:27:29 roberto Exp $
3 ** Library for Table Manipulation
4 ** See Copyright Notice in lua.h
24 ** Structure with table-access functions
27 int (*geti
) (lua_State
*L
, int idx
, lua_Integer n
);
28 void (*seti
) (lua_State
*L
, int idx
, lua_Integer n
);
33 ** Check that 'arg' has a table and set access functions in 'ta' to raw
34 ** or non-raw according to the presence of corresponding metamethods.
36 static void checktab (lua_State
*L
, int arg
, TabA
*ta
) {
37 ta
->geti
= NULL
; ta
->seti
= NULL
;
38 if (lua_getmetatable(L
, arg
)) {
39 lua_pushliteral(L
, "__index"); /* 'index' metamethod */
40 if (lua_rawget(L
, -2) != LUA_TNIL
)
42 lua_pushliteral(L
, "__newindex"); /* 'newindex' metamethod */
43 if (lua_rawget(L
, -3) != LUA_TNIL
)
45 lua_pop(L
, 3); /* pop metatable plus both metamethods */
47 if (ta
->geti
== NULL
|| ta
->seti
== NULL
) {
48 luaL_checktype(L
, arg
, LUA_TTABLE
); /* must be table for raw methods */
49 if (ta
->geti
== NULL
) ta
->geti
= lua_rawgeti
;
50 if (ta
->seti
== NULL
) ta
->seti
= lua_rawseti
;
55 #define aux_getn(L,n,ta) (checktab(L, n, ta), luaL_len(L, n))
58 #if defined(LUA_COMPAT_MAXN)
59 static int maxn (lua_State
*L
) {
61 luaL_checktype(L
, 1, LUA_TTABLE
);
62 lua_pushnil(L
); /* first key */
63 while (lua_next(L
, 1)) {
64 lua_pop(L
, 1); /* remove value */
65 if (lua_type(L
, -1) == LUA_TNUMBER
) {
66 lua_Number v
= lua_tonumber(L
, -1);
70 lua_pushnumber(L
, max
);
76 static int tinsert (lua_State
*L
) {
78 lua_Integer e
= aux_getn(L
, 1, &ta
) + 1; /* first empty element */
79 lua_Integer pos
; /* where to insert new element */
80 switch (lua_gettop(L
)) {
81 case 2: { /* called with only 2 arguments */
82 pos
= e
; /* insert new element at the end */
87 pos
= luaL_checkinteger(L
, 2); /* 2nd argument is the position */
88 luaL_argcheck(L
, 1 <= pos
&& pos
<= e
, 2, "position out of bounds");
89 for (i
= e
; i
> pos
; i
--) { /* move up elements */
90 (*ta
.geti
)(L
, 1, i
- 1);
91 (*ta
.seti
)(L
, 1, i
); /* t[i] = t[i - 1] */
96 return luaL_error(L
, "wrong number of arguments to 'insert'");
99 (*ta
.seti
)(L
, 1, pos
); /* t[pos] = v */
104 static int tremove (lua_State
*L
) {
106 lua_Integer size
= aux_getn(L
, 1, &ta
);
107 lua_Integer pos
= luaL_optinteger(L
, 2, size
);
108 if (pos
!= size
) /* validate 'pos' if given */
109 luaL_argcheck(L
, 1 <= pos
&& pos
<= size
+ 1, 1, "position out of bounds");
110 (*ta
.geti
)(L
, 1, pos
); /* result = t[pos] */
111 for ( ; pos
< size
; pos
++) {
112 (*ta
.geti
)(L
, 1, pos
+ 1);
113 (*ta
.seti
)(L
, 1, pos
); /* t[pos] = t[pos + 1] */
116 (*ta
.seti
)(L
, 1, pos
); /* t[pos] = nil */
121 static int tmove (lua_State
*L
) {
123 lua_Integer f
= luaL_checkinteger(L
, 2);
124 lua_Integer e
= luaL_checkinteger(L
, 3);
125 lua_Integer t
= luaL_checkinteger(L
, 4);
126 int tt
= !lua_isnoneornil(L
, 5) ? 5 : 1; /* destination table */
127 if (e
>= f
) { /* otherwise, nothing to move */
129 ta
.geti
= (luaL_getmetafield(L
, 1, "__index") == LUA_TNIL
)
130 ? (luaL_checktype(L
, 1, LUA_TTABLE
), lua_rawgeti
)
132 ta
.seti
= (luaL_getmetafield(L
, tt
, "__newindex") == LUA_TNIL
)
133 ? (luaL_checktype(L
, tt
, LUA_TTABLE
), lua_rawseti
)
135 luaL_argcheck(L
, f
> 0 || e
< LUA_MAXINTEGER
+ f
, 3,
136 "too many elements to move");
137 n
= e
- f
+ 1; /* number of elements to move */
138 luaL_argcheck(L
, t
<= LUA_MAXINTEGER
- n
+ 1, 4,
139 "destination wrap around");
141 for (i
= n
- 1; i
>= 0; i
--) {
142 (*ta
.geti
)(L
, 1, f
+ i
);
143 (*ta
.seti
)(L
, tt
, t
+ i
);
147 for (i
= 0; i
< n
; i
++) {
148 (*ta
.geti
)(L
, 1, f
+ i
);
149 (*ta
.seti
)(L
, tt
, t
+ i
);
153 lua_pushvalue(L
, tt
); /* return "to table" */
158 static void addfield (lua_State
*L
, luaL_Buffer
*b
, TabA
*ta
, lua_Integer i
) {
159 (*ta
->geti
)(L
, 1, i
);
160 if (!lua_isstring(L
, -1))
161 luaL_error(L
, "invalid value (%s) at index %d in table for 'concat'",
162 luaL_typename(L
, -1), i
);
167 static int tconcat (lua_State
*L
) {
172 const char *sep
= luaL_optlstring(L
, 2, "", &lsep
);
174 i
= luaL_optinteger(L
, 3, 1);
175 last
= luaL_opt(L
, luaL_checkinteger
, 4, luaL_len(L
, 1));
176 luaL_buffinit(L
, &b
);
177 for (; i
< last
; i
++) {
178 addfield(L
, &b
, &ta
, i
);
179 luaL_addlstring(&b
, sep
, lsep
);
181 if (i
== last
) /* add last value (if interval was not empty) */
182 addfield(L
, &b
, &ta
, i
);
189 ** {======================================================
191 ** =======================================================
194 static int pack (lua_State
*L
) {
196 int n
= lua_gettop(L
); /* number of elements to pack */
197 lua_createtable(L
, n
, 1); /* create result table */
198 lua_insert(L
, 1); /* put it at index 1 */
199 for (i
= n
; i
>= 1; i
--) /* assign elements */
200 lua_rawseti(L
, 1, i
);
201 lua_pushinteger(L
, n
);
202 lua_setfield(L
, 1, "n"); /* t.n = number of elements */
203 return 1; /* return table */
207 static int unpack (lua_State
*L
) {
212 i
= luaL_optinteger(L
, 2, 1);
213 e
= luaL_opt(L
, luaL_checkinteger
, 3, luaL_len(L
, 1));
214 if (i
> e
) return 0; /* empty range */
215 n
= (lua_Unsigned
)e
- i
; /* number of elements minus 1 (avoid overflows) */
216 if (n
>= (unsigned int)INT_MAX
|| !lua_checkstack(L
, (int)(++n
)))
217 return luaL_error(L
, "too many results to unpack");
218 do { /* must have at least one element */
219 (*ta
.geti
)(L
, 1, i
); /* push arg[i..e] */
225 /* }====================================================== */
230 ** {======================================================
232 ** (based on 'Algorithms in MODULA-3', Robert Sedgewick;
233 ** Addison-Wesley, 1993.)
234 ** =======================================================
238 static void set2 (lua_State
*L
, TabA
*ta
, int i
, int j
) {
239 (*ta
->seti
)(L
, 1, i
);
240 (*ta
->seti
)(L
, 1, j
);
243 static int sort_comp (lua_State
*L
, int a
, int b
) {
244 if (!lua_isnil(L
, 2)) { /* function? */
247 lua_pushvalue(L
, a
-1); /* -1 to compensate function */
248 lua_pushvalue(L
, b
-2); /* -2 to compensate function and 'a' */
250 res
= lua_toboolean(L
, -1);
255 return lua_compare(L
, a
, b
, LUA_OPLT
);
258 static void auxsort (lua_State
*L
, TabA
*ta
, int l
, int u
) {
259 while (l
< u
) { /* for tail recursion */
261 /* sort elements a[l], a[(l+u)/2] and a[u] */
262 (*ta
->geti
)(L
, 1, l
);
263 (*ta
->geti
)(L
, 1, u
);
264 if (sort_comp(L
, -1, -2)) /* a[u] < a[l]? */
265 set2(L
, ta
, l
, u
); /* swap a[l] - a[u] */
268 if (u
-l
== 1) break; /* only 2 elements */
270 (*ta
->geti
)(L
, 1, i
);
271 (*ta
->geti
)(L
, 1, l
);
272 if (sort_comp(L
, -2, -1)) /* a[i]<a[l]? */
275 lua_pop(L
, 1); /* remove a[l] */
276 (*ta
->geti
)(L
, 1, u
);
277 if (sort_comp(L
, -1, -2)) /* a[u]<a[i]? */
282 if (u
-l
== 2) break; /* only 3 elements */
283 (*ta
->geti
)(L
, 1, i
); /* Pivot */
284 lua_pushvalue(L
, -1);
285 (*ta
->geti
)(L
, 1, u
-1);
287 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
289 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
290 /* repeat ++i until a[i] >= P */
291 while ((*ta
->geti
)(L
, 1, ++i
), sort_comp(L
, -1, -2)) {
292 if (i
>=u
) luaL_error(L
, "invalid order function for sorting");
293 lua_pop(L
, 1); /* remove a[i] */
295 /* repeat --j until a[j] <= P */
296 while ((*ta
->geti
)(L
, 1, --j
), sort_comp(L
, -3, -1)) {
297 if (j
<=l
) luaL_error(L
, "invalid order function for sorting");
298 lua_pop(L
, 1); /* remove a[j] */
301 lua_pop(L
, 3); /* pop pivot, a[i], a[j] */
306 (*ta
->geti
)(L
, 1, u
-1);
307 (*ta
->geti
)(L
, 1, i
);
308 set2(L
, ta
, u
-1, i
); /* swap pivot (a[u-1]) with a[i] */
309 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
310 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
317 auxsort(L
, ta
, j
, i
); /* call recursively the smaller one */
318 } /* repeat the routine for the larger one */
321 static int sort (lua_State
*L
) {
323 int n
= (int)aux_getn(L
, 1, &ta
);
324 luaL_checkstack(L
, 50, ""); /* assume array is smaller than 2^50 */
325 if (!lua_isnoneornil(L
, 2)) /* is there a 2nd argument? */
326 luaL_checktype(L
, 2, LUA_TFUNCTION
);
327 lua_settop(L
, 2); /* make sure there are two arguments */
328 auxsort(L
, &ta
, 1, n
);
332 /* }====================================================== */
335 static const luaL_Reg tab_funcs
[] = {
337 #if defined(LUA_COMPAT_MAXN)
350 LUAMOD_API
int luaopen_table (lua_State
*L
) {
351 luaL_newlib(L
, tab_funcs
);
352 #if defined(LUA_COMPAT_UNPACK)
353 /* _G.unpack = table.unpack */
354 lua_getfield(L
, -1, "unpack");
355 lua_setglobal(L
, "unpack");