[mirror_edk2.git] / AppPkg / Applications / Lua / src / ltablib.c

/*\r
** $Id: ltablib.c,v 1.65.1.1 2013/04/12 18:48:47 roberto Exp $\r
** Library for Table Manipulation\r
** See Copyright Notice in lua.h\r
*/\r
\r
\r
#include <stddef.h>\r
\r
#define ltablib_c\r
#define LUA_LIB\r
\r
#include "lua.h"\r
\r
#include "lauxlib.h"\r
#include "lualib.h"\r
\r
\r
#define aux_getn(L,n) (luaL_checktype(L, n, LUA_TTABLE), luaL_len(L, n))\r
\r
\r
\r
#if defined(LUA_COMPAT_MAXN)\r
static int maxn (lua_State *L) {\r
  lua_Number max = 0;\r
  luaL_checktype(L, 1, LUA_TTABLE);\r
  lua_pushnil(L);  /* first key */\r
  while (lua_next(L, 1)) {\r
    lua_pop(L, 1);  /* remove value */\r
    if (lua_type(L, -1) == LUA_TNUMBER) {\r
      lua_Number v = lua_tonumber(L, -1);\r
      if (v > max) max = v;\r
    }\r
  }\r
  lua_pushnumber(L, max);\r
  return 1;\r
}\r
#endif\r
\r
\r
static int tinsert (lua_State *L) {\r
  int e = aux_getn(L, 1) + 1;  /* first empty element */\r
  int pos;  /* where to insert new element */\r
  switch (lua_gettop(L)) {\r
    case 2: {  /* called with only 2 arguments */\r
      pos = e;  /* insert new element at the end */\r
      break;\r
    }\r
    case 3: {\r
      int i;\r
      pos = luaL_checkint(L, 2);  /* 2nd argument is the position */\r
      luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds");\r
      for (i = e; i > pos; i--) {  /* move up elements */\r
        lua_rawgeti(L, 1, i-1);\r
        lua_rawseti(L, 1, i);  /* t[i] = t[i-1] */\r
      }\r
      break;\r
    }\r
    default: {\r
      return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));\r
    }\r
  }\r
  lua_rawseti(L, 1, pos);  /* t[pos] = v */\r
  return 0;\r
}\r
\r
\r
static int tremove (lua_State *L) {\r
  int size = aux_getn(L, 1);\r
  int pos = luaL_optint(L, 2, size);\r
  if (pos != size)  /* validate 'pos' if given */\r
    luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");\r
  lua_rawgeti(L, 1, pos);  /* result = t[pos] */\r
  for ( ; pos < size; pos++) {\r
    lua_rawgeti(L, 1, pos+1);\r
    lua_rawseti(L, 1, pos);  /* t[pos] = t[pos+1] */\r
  }\r
  lua_pushnil(L);\r
  lua_rawseti(L, 1, pos);  /* t[pos] = nil */\r
  return 1;\r
}\r
\r
\r
static void addfield (lua_State *L, luaL_Buffer *b, int i) {\r
  lua_rawgeti(L, 1, i);\r
  if (!lua_isstring(L, -1))\r
    luaL_error(L, "invalid value (%s) at index %d in table for "\r
                  LUA_QL("concat"), luaL_typename(L, -1), i);\r
  luaL_addvalue(b);\r
}\r
\r
\r
static int tconcat (lua_State *L) {\r
  luaL_Buffer b;\r
  size_t lsep;\r
  int i, last;\r
  const char *sep = luaL_optlstring(L, 2, "", &lsep);\r
  luaL_checktype(L, 1, LUA_TTABLE);\r
  i = luaL_optint(L, 3, 1);\r
  last = luaL_opt(L, luaL_checkint, 4, luaL_len(L, 1));\r
  luaL_buffinit(L, &b);\r
  for (; i < last; i++) {\r
    addfield(L, &b, i);\r
    luaL_addlstring(&b, sep, lsep);\r
  }\r
  if (i == last)  /* add last value (if interval was not empty) */\r
    addfield(L, &b, i);\r
  luaL_pushresult(&b);\r
  return 1;\r
}\r
\r
\r
/*\r
** {======================================================\r
** Pack/unpack\r
** =======================================================\r
*/\r
\r
static int pack (lua_State *L) {\r
  int n = lua_gettop(L);  /* number of elements to pack */\r
  lua_createtable(L, n, 1);  /* create result table */\r
  lua_pushinteger(L, n);\r
  lua_setfield(L, -2, "n");  /* t.n = number of elements */\r
  if (n > 0) {  /* at least one element? */\r
    int i;\r
    lua_pushvalue(L, 1);\r
    lua_rawseti(L, -2, 1);  /* insert first element */\r
    lua_replace(L, 1);  /* move table into index 1 */\r
    for (i = n; i >= 2; i--)  /* assign other elements */\r
      lua_rawseti(L, 1, i);\r
  }\r
  return 1;  /* return table */\r
}\r
\r
\r
static int unpack (lua_State *L) {\r
  int i, e, n;\r
  luaL_checktype(L, 1, LUA_TTABLE);\r
  i = luaL_optint(L, 2, 1);\r
  e = luaL_opt(L, luaL_checkint, 3, luaL_len(L, 1));\r
  if (i > e) return 0;  /* empty range */\r
  n = e - i + 1;  /* number of elements */\r
  if (n <= 0 || !lua_checkstack(L, n))  /* n <= 0 means arith. overflow */\r
    return luaL_error(L, "too many results to unpack");\r
  lua_rawgeti(L, 1, i);  /* push arg[i] (avoiding overflow problems) */\r
  while (i++ < e)  /* push arg[i + 1...e] */\r
    lua_rawgeti(L, 1, i);\r
  return n;\r
}\r
\r
/* }====================================================== */\r
\r
\r
\r
/*\r
** {======================================================\r
** Quicksort\r
** (based on `Algorithms in MODULA-3', Robert Sedgewick;\r
**  Addison-Wesley, 1993.)\r
** =======================================================\r
*/\r
\r
\r
static void set2 (lua_State *L, int i, int j) {\r
  lua_rawseti(L, 1, i);\r
  lua_rawseti(L, 1, j);\r
}\r
\r
static int sort_comp (lua_State *L, int a, int b) {\r
  if (!lua_isnil(L, 2)) {  /* function? */\r
    int res;\r
    lua_pushvalue(L, 2);\r
    lua_pushvalue(L, a-1);  /* -1 to compensate function */\r
    lua_pushvalue(L, b-2);  /* -2 to compensate function and `a' */\r
    lua_call(L, 2, 1);\r
    res = lua_toboolean(L, -1);\r
    lua_pop(L, 1);\r
    return res;\r
  }\r
  else  /* a < b? */\r
    return lua_compare(L, a, b, LUA_OPLT);\r
}\r
\r
static void auxsort (lua_State *L, int l, int u) {\r
  while (l < u) {  /* for tail recursion */\r
    int i, j;\r
    /* sort elements a[l], a[(l+u)/2] and a[u] */\r
    lua_rawgeti(L, 1, l);\r
    lua_rawgeti(L, 1, u);\r
    if (sort_comp(L, -1, -2))  /* a[u] < a[l]? */\r
      set2(L, l, u);  /* swap a[l] - a[u] */\r
    else\r
      lua_pop(L, 2);\r
    if (u-l == 1) break;  /* only 2 elements */\r
    i = (l+u)/2;\r
    lua_rawgeti(L, 1, i);\r
    lua_rawgeti(L, 1, l);\r
    if (sort_comp(L, -2, -1))  /* a[i]<a[l]? */\r
      set2(L, i, l);\r
    else {\r
      lua_pop(L, 1);  /* remove a[l] */\r
      lua_rawgeti(L, 1, u);\r
      if (sort_comp(L, -1, -2))  /* a[u]<a[i]? */\r
        set2(L, i, u);\r
      else\r
        lua_pop(L, 2);\r
    }\r
    if (u-l == 2) break;  /* only 3 elements */\r
    lua_rawgeti(L, 1, i);  /* Pivot */\r
    lua_pushvalue(L, -1);\r
    lua_rawgeti(L, 1, u-1);\r
    set2(L, i, u-1);\r
    /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */\r
    i = l; j = u-1;\r
    for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */\r
      /* repeat ++i until a[i] >= P */\r
      while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {\r
        if (i>=u) luaL_error(L, "invalid order function for sorting");\r
        lua_pop(L, 1);  /* remove a[i] */\r
      }\r
      /* repeat --j until a[j] <= P */\r
      while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {\r
        if (j<=l) luaL_error(L, "invalid order function for sorting");\r
        lua_pop(L, 1);  /* remove a[j] */\r
      }\r
      if (j<i) {\r
        lua_pop(L, 3);  /* pop pivot, a[i], a[j] */\r
        break;\r
      }\r
      set2(L, i, j);\r
    }\r
    lua_rawgeti(L, 1, u-1);\r
    lua_rawgeti(L, 1, i);\r
    set2(L, u-1, i);  /* swap pivot (a[u-1]) with a[i] */\r
    /* a[l..i-1] <= a[i] == P <= a[i+1..u] */\r
    /* adjust so that smaller half is in [j..i] and larger one in [l..u] */\r
    if (i-l < u-i) {\r
      j=l; i=i-1; l=i+2;\r
    }\r
    else {\r
      j=i+1; i=u; u=j-2;\r
    }\r
    auxsort(L, j, i);  /* call recursively the smaller one */\r
  }  /* repeat the routine for the larger one */\r
}\r
\r
static int sort (lua_State *L) {\r
  int n = aux_getn(L, 1);\r
  luaL_checkstack(L, 40, "");  /* assume array is smaller than 2^40 */\r
  if (!lua_isnoneornil(L, 2))  /* is there a 2nd argument? */\r
    luaL_checktype(L, 2, LUA_TFUNCTION);\r
  lua_settop(L, 2);  /* make sure there is two arguments */\r
  auxsort(L, 1, n);\r
  return 0;\r
}\r
\r
/* }====================================================== */\r
\r
\r
static const luaL_Reg tab_funcs[] = {\r
  {"concat", tconcat},\r
#if defined(LUA_COMPAT_MAXN)\r
  {"maxn", maxn},\r
#endif\r
  {"insert", tinsert},\r
  {"pack", pack},\r
  {"unpack", unpack},\r
  {"remove", tremove},\r
  {"sort", sort},\r
  {NULL, NULL}\r
};\r
\r
\r
LUAMOD_API int luaopen_table (lua_State *L) {\r
  luaL_newlib(L, tab_funcs);\r
#if defined(LUA_COMPAT_UNPACK)\r
  /* _G.unpack = table.unpack */\r
  lua_getfield(L, -1, "unpack");\r
  lua_setglobal(L, "unpack");\r
#endif\r
  return 1;\r
}\r
\r
Commit	Line	Data
16a5fed6	1	/*\r
	2	** $Id: ltablib.c,v 1.65.1.1 2013/04/12 18:48:47 roberto Exp $\r
	3	** Library for Table Manipulation\r
	4	** See Copyright Notice in lua.h\r
	5	*/\r
	6	\r
	7	\r
	8	#include <stddef.h>\r
	9	\r
	10	#define ltablib_c\r
	11	#define LUA_LIB\r
	12	\r
	13	#include "lua.h"\r
	14	\r
	15	#include "lauxlib.h"\r
	16	#include "lualib.h"\r
	17	\r
	18	\r
	19	#define aux_getn(L,n) (luaL_checktype(L, n, LUA_TTABLE), luaL_len(L, n))\r
	20	\r
	21	\r
	22	\r
	23	#if defined(LUA_COMPAT_MAXN)\r
	24	static int maxn (lua_State *L) {\r
	25	lua_Number max = 0;\r
	26	luaL_checktype(L, 1, LUA_TTABLE);\r
	27	lua_pushnil(L); /* first key */\r
	28	while (lua_next(L, 1)) {\r
	29	lua_pop(L, 1); /* remove value */\r
	30	if (lua_type(L, -1) == LUA_TNUMBER) {\r
	31	lua_Number v = lua_tonumber(L, -1);\r
	32	if (v > max) max = v;\r
	33	}\r
	34	}\r
	35	lua_pushnumber(L, max);\r
	36	return 1;\r
	37	}\r
	38	#endif\r
	39	\r
	40	\r
	41	static int tinsert (lua_State *L) {\r
	42	int e = aux_getn(L, 1) + 1; /* first empty element */\r
	43	int pos; /* where to insert new element */\r
	44	switch (lua_gettop(L)) {\r
	45	case 2: { /* called with only 2 arguments */\r
	46	pos = e; /* insert new element at the end */\r
	47	break;\r
	48	}\r
	49	case 3: {\r
	50	int i;\r
	51	pos = luaL_checkint(L, 2); /* 2nd argument is the position */\r
	52	luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds");\r
	53	for (i = e; i > pos; i--) { /* move up elements */\r
	54	lua_rawgeti(L, 1, i-1);\r
	55	lua_rawseti(L, 1, i); /* t[i] = t[i-1] */\r
	56	}\r
	57	break;\r
	58	}\r
	59	default: {\r
	60	return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));\r
	61	}\r
	62	}\r
	63	lua_rawseti(L, 1, pos); /* t[pos] = v */\r
	64	return 0;\r
65	}\r
66	\r
67	\r
68	static int tremove (lua_State *L) {\r
69	int size = aux_getn(L, 1);\r
70	int pos = luaL_optint(L, 2, size);\r
71	if (pos != size) /* validate 'pos' if given */\r
72	luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds");\r
73	lua_rawgeti(L, 1, pos); /* result = t[pos] */\r
74	for ( ; pos < size; pos++) {\r
75	lua_rawgeti(L, 1, pos+1);\r
76	lua_rawseti(L, 1, pos); /* t[pos] = t[pos+1] */\r
77	}\r
78	lua_pushnil(L);\r
79	lua_rawseti(L, 1, pos); /* t[pos] = nil */\r
80	return 1;\r
81	}\r
82	\r
83	\r
84	static void addfield (lua_State L, luaL_Buffer b, int i) {\r
85	lua_rawgeti(L, 1, i);\r
86	if (!lua_isstring(L, -1))\r
87	luaL_error(L, "invalid value (%s) at index %d in table for "\r
88	LUA_QL("concat"), luaL_typename(L, -1), i);\r
89	luaL_addvalue(b);\r
90	}\r
91	\r
92	\r
93	static int tconcat (lua_State *L) {\r
94	luaL_Buffer b;\r
95	size_t lsep;\r
96	int i, last;\r
97	const char *sep = luaL_optlstring(L, 2, "", &lsep);\r
98	luaL_checktype(L, 1, LUA_TTABLE);\r
99	i = luaL_optint(L, 3, 1);\r
100	last = luaL_opt(L, luaL_checkint, 4, luaL_len(L, 1));\r
101	luaL_buffinit(L, &b);\r
102	for (; i < last; i++) {\r
103	addfield(L, &b, i);\r
104	luaL_addlstring(&b, sep, lsep);\r
105	}\r
106	if (i == last) /* add last value (if interval was not empty) */\r
107	addfield(L, &b, i);\r
108	luaL_pushresult(&b);\r
109	return 1;\r
110	}\r
111	\r
112	\r
113	/*\r
114	** {======================================================\r
115	** Pack/unpack\r
116	** =======================================================\r
117	*/\r
118	\r
119	static int pack (lua_State *L) {\r
120	int n = lua_gettop(L); /* number of elements to pack */\r
121	lua_createtable(L, n, 1); /* create result table */\r
122	lua_pushinteger(L, n);\r
123	lua_setfield(L, -2, "n"); /* t.n = number of elements */\r
124	if (n > 0) { /* at least one element? */\r
125	int i;\r
126	lua_pushvalue(L, 1);\r
127	lua_rawseti(L, -2, 1); /* insert first element */\r
128	lua_replace(L, 1); /* move table into index 1 */\r
129	for (i = n; i >= 2; i--) /* assign other elements */\r
130	lua_rawseti(L, 1, i);\r
131	}\r
132	return 1; /* return table */\r
133	}\r
134	\r
135	\r
136	static int unpack (lua_State *L) {\r
137	int i, e, n;\r
138	luaL_checktype(L, 1, LUA_TTABLE);\r
139	i = luaL_optint(L, 2, 1);\r
140	e = luaL_opt(L, luaL_checkint, 3, luaL_len(L, 1));\r
141	if (i > e) return 0; /* empty range */\r
142	n = e - i + 1; /* number of elements */\r
143	if (n <= 0 \|\| !lua_checkstack(L, n)) /* n <= 0 means arith. overflow */\r
144	return luaL_error(L, "too many results to unpack");\r
145	lua_rawgeti(L, 1, i); /* push arg[i] (avoiding overflow problems) */\r
146	while (i++ < e) /* push arg[i + 1...e] */\r
147	lua_rawgeti(L, 1, i);\r
148	return n;\r
149	}\r
150	\r
151	/* }====================================================== */\r
152	\r
153	\r
154	\r
155	/*\r
156	** {======================================================\r
157	** Quicksort\r
158	** (based on `Algorithms in MODULA-3', Robert Sedgewick;\r
159	** Addison-Wesley, 1993.)\r
160	** =======================================================\r
161	*/\r
162	\r
163	\r
164	static void set2 (lua_State *L, int i, int j) {\r
165	lua_rawseti(L, 1, i);\r
166	lua_rawseti(L, 1, j);\r
167	}\r
168	\r
169	static int sort_comp (lua_State *L, int a, int b) {\r
170	if (!lua_isnil(L, 2)) { /* function? */\r
171	int res;\r
172	lua_pushvalue(L, 2);\r
173	lua_pushvalue(L, a-1); /* -1 to compensate function */\r
174	lua_pushvalue(L, b-2); /* -2 to compensate function and `a' */\r
175	lua_call(L, 2, 1);\r
176	res = lua_toboolean(L, -1);\r
177	lua_pop(L, 1);\r
178	return res;\r
179	}\r
180	else /* a < b? */\r
181	return lua_compare(L, a, b, LUA_OPLT);\r
182	}\r
183	\r
184	static void auxsort (lua_State *L, int l, int u) {\r
185	while (l < u) { /* for tail recursion */\r
186	int i, j;\r
187	/* sort elements a[l], a[(l+u)/2] and a[u] */\r
188	lua_rawgeti(L, 1, l);\r
189	lua_rawgeti(L, 1, u);\r
190	if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */\r
191	set2(L, l, u); /* swap a[l] - a[u] */\r
192	else\r
193	lua_pop(L, 2);\r
194	if (u-l == 1) break; /* only 2 elements */\r
195	i = (l+u)/2;\r
196	lua_rawgeti(L, 1, i);\r
197	lua_rawgeti(L, 1, l);\r
198	if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */\r
199	set2(L, i, l);\r
200	else {\r
201	lua_pop(L, 1); /* remove a[l] */\r
202	lua_rawgeti(L, 1, u);\r
203	if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */\r
204	set2(L, i, u);\r
205	else\r
206	lua_pop(L, 2);\r
207	}\r
208	if (u-l == 2) break; /* only 3 elements */\r
209	lua_rawgeti(L, 1, i); /* Pivot */\r
210	lua_pushvalue(L, -1);\r
211	lua_rawgeti(L, 1, u-1);\r
212	set2(L, i, u-1);\r
213	/* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */\r
214	i = l; j = u-1;\r
215	for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */\r
216	/* repeat ++i until a[i] >= P */\r
217	while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {\r
218	if (i>=u) luaL_error(L, "invalid order function for sorting");\r
219	lua_pop(L, 1); /* remove a[i] */\r
220	}\r
221	/* repeat --j until a[j] <= P */\r
222	while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {\r
223	if (j<=l) luaL_error(L, "invalid order function for sorting");\r
224	lua_pop(L, 1); /* remove a[j] */\r
225	}\r
226	if (j<i) {\r
227	lua_pop(L, 3); /* pop pivot, a[i], a[j] */\r
228	break;\r
229	}\r
230	set2(L, i, j);\r
231	}\r
232	lua_rawgeti(L, 1, u-1);\r
233	lua_rawgeti(L, 1, i);\r
234	set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */\r
235	/* a[l..i-1] <= a[i] == P <= a[i+1..u] */\r
236	/* adjust so that smaller half is in [j..i] and larger one in [l..u] */\r
237	if (i-l < u-i) {\r
238	j=l; i=i-1; l=i+2;\r
239	}\r
240	else {\r
241	j=i+1; i=u; u=j-2;\r
242	}\r
243	auxsort(L, j, i); /* call recursively the smaller one */\r
244	} /* repeat the routine for the larger one */\r
245	}\r
246	\r
247	static int sort (lua_State *L) {\r
248	int n = aux_getn(L, 1);\r
249	luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */\r
250	if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */\r
251	luaL_checktype(L, 2, LUA_TFUNCTION);\r
252	lua_settop(L, 2); /* make sure there is two arguments */\r
253	auxsort(L, 1, n);\r
254	return 0;\r
255	}\r
256	\r
257	/* }====================================================== */\r
258	\r
259	\r
260	static const luaL_Reg tab_funcs[] = {\r
261	{"concat", tconcat},\r
262	#if defined(LUA_COMPAT_MAXN)\r
263	{"maxn", maxn},\r
264	#endif\r
265	{"insert", tinsert},\r
266	{"pack", pack},\r
267	{"unpack", unpack},\r
268	{"remove", tremove},\r
269	{"sort", sort},\r
270	{NULL, NULL}\r
271	};\r
272	\r
273	\r
274	LUAMOD_API int luaopen_table (lua_State *L) {\r
275	luaL_newlib(L, tab_funcs);\r
276	#if defined(LUA_COMPAT_UNPACK)\r
277	/* _G.unpack = table.unpack */\r
278	lua_getfield(L, -1, "unpack");\r
279	lua_setglobal(L, "unpack");\r
280	#endif\r
281	return 1;\r
282	}\r
283	\r