]>
git.proxmox.com Git - ceph.git/blob - ceph/src/jaegertracing/opentelemetry-cpp/third_party/prometheus-cpp/3rdparty/civetweb/src/third_party/lua-5.4.3/src/ltablib.c
3 ** Library for Table Manipulation
4 ** See Copyright Notice in lua.h
24 ** Operations that an object must define to mimic a table
25 ** (some functions only need some of them)
27 #define TAB_R 1 /* read */
28 #define TAB_W 2 /* write */
29 #define TAB_L 4 /* length */
30 #define TAB_RW (TAB_R | TAB_W) /* read/write */
33 #define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n))
36 static int checkfield (lua_State
*L
, const char *key
, int n
) {
37 lua_pushstring(L
, key
);
38 return (lua_rawget(L
, -n
) != LUA_TNIL
);
43 ** Check that 'arg' either is a table or can behave like one (that is,
44 ** has a metatable with the required metamethods)
46 static void checktab (lua_State
*L
, int arg
, int what
) {
47 if (lua_type(L
, arg
) != LUA_TTABLE
) { /* is it not a table? */
48 int n
= 1; /* number of elements to pop */
49 if (lua_getmetatable(L
, arg
) && /* must have metatable */
50 (!(what
& TAB_R
) || checkfield(L
, "__index", ++n
)) &&
51 (!(what
& TAB_W
) || checkfield(L
, "__newindex", ++n
)) &&
52 (!(what
& TAB_L
) || checkfield(L
, "__len", ++n
))) {
53 lua_pop(L
, n
); /* pop metatable and tested metamethods */
56 luaL_checktype(L
, arg
, LUA_TTABLE
); /* force an error */
61 static int tinsert (lua_State
*L
) {
62 lua_Integer e
= aux_getn(L
, 1, TAB_RW
) + 1; /* first empty element */
63 lua_Integer pos
; /* where to insert new element */
64 switch (lua_gettop(L
)) {
65 case 2: { /* called with only 2 arguments */
66 pos
= e
; /* insert new element at the end */
71 pos
= luaL_checkinteger(L
, 2); /* 2nd argument is the position */
72 /* check whether 'pos' is in [1, e] */
73 luaL_argcheck(L
, (lua_Unsigned
)pos
- 1u < (lua_Unsigned
)e
, 2,
74 "position out of bounds");
75 for (i
= e
; i
> pos
; i
--) { /* move up elements */
76 lua_geti(L
, 1, i
- 1);
77 lua_seti(L
, 1, i
); /* t[i] = t[i - 1] */
82 return luaL_error(L
, "wrong number of arguments to 'insert'");
85 lua_seti(L
, 1, pos
); /* t[pos] = v */
90 static int tremove (lua_State
*L
) {
91 lua_Integer size
= aux_getn(L
, 1, TAB_RW
);
92 lua_Integer pos
= luaL_optinteger(L
, 2, size
);
93 if (pos
!= size
) /* validate 'pos' if given */
94 /* check whether 'pos' is in [1, size + 1] */
95 luaL_argcheck(L
, (lua_Unsigned
)pos
- 1u <= (lua_Unsigned
)size
, 1,
96 "position out of bounds");
97 lua_geti(L
, 1, pos
); /* result = t[pos] */
98 for ( ; pos
< size
; pos
++) {
99 lua_geti(L
, 1, pos
+ 1);
100 lua_seti(L
, 1, pos
); /* t[pos] = t[pos + 1] */
103 lua_seti(L
, 1, pos
); /* remove entry t[pos] */
109 ** Copy elements (1[f], ..., 1[e]) into (tt[t], tt[t+1], ...). Whenever
110 ** possible, copy in increasing order, which is better for rehashing.
111 ** "possible" means destination after original range, or smaller
112 ** than origin, or copying to another table.
114 static int tmove (lua_State
*L
) {
115 lua_Integer f
= luaL_checkinteger(L
, 2);
116 lua_Integer e
= luaL_checkinteger(L
, 3);
117 lua_Integer t
= luaL_checkinteger(L
, 4);
118 int tt
= !lua_isnoneornil(L
, 5) ? 5 : 1; /* destination table */
119 checktab(L
, 1, TAB_R
);
120 checktab(L
, tt
, TAB_W
);
121 if (e
>= f
) { /* otherwise, nothing to move */
123 luaL_argcheck(L
, f
> 0 || e
< LUA_MAXINTEGER
+ f
, 3,
124 "too many elements to move");
125 n
= e
- f
+ 1; /* number of elements to move */
126 luaL_argcheck(L
, t
<= LUA_MAXINTEGER
- n
+ 1, 4,
127 "destination wrap around");
128 if (t
> e
|| t
<= f
|| (tt
!= 1 && !lua_compare(L
, 1, tt
, LUA_OPEQ
))) {
129 for (i
= 0; i
< n
; i
++) {
130 lua_geti(L
, 1, f
+ i
);
131 lua_seti(L
, tt
, t
+ i
);
135 for (i
= n
- 1; i
>= 0; i
--) {
136 lua_geti(L
, 1, f
+ i
);
137 lua_seti(L
, tt
, t
+ i
);
141 lua_pushvalue(L
, tt
); /* return destination table */
146 static void addfield (lua_State
*L
, luaL_Buffer
*b
, lua_Integer i
) {
148 if (l_unlikely(!lua_isstring(L
, -1)))
149 luaL_error(L
, "invalid value (%s) at index %I in table for 'concat'",
150 luaL_typename(L
, -1), i
);
155 static int tconcat (lua_State
*L
) {
157 lua_Integer last
= aux_getn(L
, 1, TAB_R
);
159 const char *sep
= luaL_optlstring(L
, 2, "", &lsep
);
160 lua_Integer i
= luaL_optinteger(L
, 3, 1);
161 last
= luaL_optinteger(L
, 4, last
);
162 luaL_buffinit(L
, &b
);
163 for (; i
< last
; i
++) {
165 luaL_addlstring(&b
, sep
, lsep
);
167 if (i
== last
) /* add last value (if interval was not empty) */
175 ** {======================================================
177 ** =======================================================
180 static int tpack (lua_State
*L
) {
182 int n
= lua_gettop(L
); /* number of elements to pack */
183 lua_createtable(L
, n
, 1); /* create result table */
184 lua_insert(L
, 1); /* put it at index 1 */
185 for (i
= n
; i
>= 1; i
--) /* assign elements */
187 lua_pushinteger(L
, n
);
188 lua_setfield(L
, 1, "n"); /* t.n = number of elements */
189 return 1; /* return table */
193 static int tunpack (lua_State
*L
) {
195 lua_Integer i
= luaL_optinteger(L
, 2, 1);
196 lua_Integer e
= luaL_opt(L
, luaL_checkinteger
, 3, luaL_len(L
, 1));
197 if (i
> e
) return 0; /* empty range */
198 n
= (lua_Unsigned
)e
- i
; /* number of elements minus 1 (avoid overflows) */
199 if (l_unlikely(n
>= (unsigned int)INT_MAX
||
200 !lua_checkstack(L
, (int)(++n
))))
201 return luaL_error(L
, "too many results to unpack");
202 for (; i
< e
; i
++) { /* push arg[i..e - 1] (to avoid overflows) */
205 lua_geti(L
, 1, e
); /* push last element */
209 /* }====================================================== */
214 ** {======================================================
216 ** (based on 'Algorithms in MODULA-3', Robert Sedgewick;
217 ** Addison-Wesley, 1993.)
218 ** =======================================================
222 /* type for array indices */
223 typedef unsigned int IdxT
;
227 ** Produce a "random" 'unsigned int' to randomize pivot choice. This
228 ** macro is used only when 'sort' detects a big imbalance in the result
229 ** of a partition. (If you don't want/need this "randomness", ~0 is a
232 #if !defined(l_randomizePivot) /* { */
236 /* size of 'e' measured in number of 'unsigned int's */
237 #define sof(e) (sizeof(e) / sizeof(unsigned int))
240 ** Use 'time' and 'clock' as sources of "randomness". Because we don't
241 ** know the types 'clock_t' and 'time_t', we cannot cast them to
242 ** anything without risking overflows. A safe way to use their values
243 ** is to copy them to an array of a known type and use the array values.
245 static unsigned int l_randomizePivot (void) {
247 time_t t
= time(NULL
);
248 unsigned int buff
[sof(c
) + sof(t
)];
249 unsigned int i
, rnd
= 0;
250 memcpy(buff
, &c
, sof(c
) * sizeof(unsigned int));
251 memcpy(buff
+ sof(c
), &t
, sof(t
) * sizeof(unsigned int));
252 for (i
= 0; i
< sof(buff
); i
++)
260 /* arrays larger than 'RANLIMIT' may use randomized pivots */
261 #define RANLIMIT 100u
264 static void set2 (lua_State
*L
, IdxT i
, IdxT j
) {
271 ** Return true iff value at stack index 'a' is less than the value at
272 ** index 'b' (according to the order of the sort).
274 static int sort_comp (lua_State
*L
, int a
, int b
) {
275 if (lua_isnil(L
, 2)) /* no function? */
276 return lua_compare(L
, a
, b
, LUA_OPLT
); /* a < b */
277 else { /* function */
279 lua_pushvalue(L
, 2); /* push function */
280 lua_pushvalue(L
, a
-1); /* -1 to compensate function */
281 lua_pushvalue(L
, b
-2); /* -2 to compensate function and 'a' */
282 lua_call(L
, 2, 1); /* call function */
283 res
= lua_toboolean(L
, -1); /* get result */
284 lua_pop(L
, 1); /* pop result */
291 ** Does the partition: Pivot P is at the top of the stack.
292 ** precondition: a[lo] <= P == a[up-1] <= a[up],
293 ** so it only needs to do the partition from lo + 1 to up - 2.
294 ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up]
297 static IdxT
partition (lua_State
*L
, IdxT lo
, IdxT up
) {
298 IdxT i
= lo
; /* will be incremented before first use */
299 IdxT j
= up
- 1; /* will be decremented before first use */
300 /* loop invariant: a[lo .. i] <= P <= a[j .. up] */
302 /* next loop: repeat ++i while a[i] < P */
303 while ((void)lua_geti(L
, 1, ++i
), sort_comp(L
, -1, -2)) {
304 if (l_unlikely(i
== up
- 1)) /* a[i] < P but a[up - 1] == P ?? */
305 luaL_error(L
, "invalid order function for sorting");
306 lua_pop(L
, 1); /* remove a[i] */
308 /* after the loop, a[i] >= P and a[lo .. i - 1] < P */
309 /* next loop: repeat --j while P < a[j] */
310 while ((void)lua_geti(L
, 1, --j
), sort_comp(L
, -3, -1)) {
311 if (l_unlikely(j
< i
)) /* j < i but a[j] > P ?? */
312 luaL_error(L
, "invalid order function for sorting");
313 lua_pop(L
, 1); /* remove a[j] */
315 /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */
316 if (j
< i
) { /* no elements out of place? */
317 /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */
318 lua_pop(L
, 1); /* pop a[j] */
319 /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */
323 /* otherwise, swap a[i] - a[j] to restore invariant and repeat */
330 ** Choose an element in the middle (2nd-3th quarters) of [lo,up]
331 ** "randomized" by 'rnd'
333 static IdxT
choosePivot (IdxT lo
, IdxT up
, unsigned int rnd
) {
334 IdxT r4
= (up
- lo
) / 4; /* range/4 */
335 IdxT p
= rnd
% (r4
* 2) + (lo
+ r4
);
336 lua_assert(lo
+ r4
<= p
&& p
<= up
- r4
);
342 ** Quicksort algorithm (recursive function)
344 static void auxsort (lua_State
*L
, IdxT lo
, IdxT up
,
346 while (lo
< up
) { /* loop for tail recursion */
347 IdxT p
; /* Pivot index */
348 IdxT n
; /* to be used later */
349 /* sort elements 'lo', 'p', and 'up' */
352 if (sort_comp(L
, -1, -2)) /* a[up] < a[lo]? */
353 set2(L
, lo
, up
); /* swap a[lo] - a[up] */
355 lua_pop(L
, 2); /* remove both values */
356 if (up
- lo
== 1) /* only 2 elements? */
357 return; /* already sorted */
358 if (up
- lo
< RANLIMIT
|| rnd
== 0) /* small interval or no randomize? */
359 p
= (lo
+ up
)/2; /* middle element is a good pivot */
360 else /* for larger intervals, it is worth a random pivot */
361 p
= choosePivot(lo
, up
, rnd
);
364 if (sort_comp(L
, -2, -1)) /* a[p] < a[lo]? */
365 set2(L
, p
, lo
); /* swap a[p] - a[lo] */
367 lua_pop(L
, 1); /* remove a[lo] */
369 if (sort_comp(L
, -1, -2)) /* a[up] < a[p]? */
370 set2(L
, p
, up
); /* swap a[up] - a[p] */
374 if (up
- lo
== 2) /* only 3 elements? */
375 return; /* already sorted */
376 lua_geti(L
, 1, p
); /* get middle element (Pivot) */
377 lua_pushvalue(L
, -1); /* push Pivot */
378 lua_geti(L
, 1, up
- 1); /* push a[up - 1] */
379 set2(L
, p
, up
- 1); /* swap Pivot (a[p]) with a[up - 1] */
380 p
= partition(L
, lo
, up
);
381 /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */
382 if (p
- lo
< up
- p
) { /* lower interval is smaller? */
383 auxsort(L
, lo
, p
- 1, rnd
); /* call recursively for lower interval */
384 n
= p
- lo
; /* size of smaller interval */
385 lo
= p
+ 1; /* tail call for [p + 1 .. up] (upper interval) */
388 auxsort(L
, p
+ 1, up
, rnd
); /* call recursively for upper interval */
389 n
= up
- p
; /* size of smaller interval */
390 up
= p
- 1; /* tail call for [lo .. p - 1] (lower interval) */
392 if ((up
- lo
) / 128 > n
) /* partition too imbalanced? */
393 rnd
= l_randomizePivot(); /* try a new randomization */
394 } /* tail call auxsort(L, lo, up, rnd) */
398 static int sort (lua_State
*L
) {
399 lua_Integer n
= aux_getn(L
, 1, TAB_RW
);
400 if (n
> 1) { /* non-trivial interval? */
401 luaL_argcheck(L
, n
< INT_MAX
, 1, "array too big");
402 if (!lua_isnoneornil(L
, 2)) /* is there a 2nd argument? */
403 luaL_checktype(L
, 2, LUA_TFUNCTION
); /* must be a function */
404 lua_settop(L
, 2); /* make sure there are two arguments */
405 auxsort(L
, 1, (IdxT
)n
, 0);
410 /* }====================================================== */
413 static const luaL_Reg tab_funcs
[] = {
425 LUAMOD_API
int luaopen_table (lua_State
*L
) {
426 luaL_newlib(L
, tab_funcs
);