ltablib.c 7.4 KB

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