src/lib_table.c - luajit-2.0-src

Functions defined

Macros defined

Source code

  1. /*
  2. ** Table library.
  3. ** Copyright (C) 2005-2015 Mike Pall. See Copyright Notice in luajit.h
  4. **
  5. ** Major portions taken verbatim or adapted from the Lua interpreter.
  6. ** Copyright (C) 1994-2008 Lua.org, PUC-Rio. See Copyright Notice in lua.h
  7. */

  8. #define lib_table_c
  9. #define LUA_LIB

  10. #include "lua.h"
  11. #include "lauxlib.h"
  12. #include "lualib.h"

  13. #include "lj_obj.h"
  14. #include "lj_gc.h"
  15. #include "lj_err.h"
  16. #include "lj_buf.h"
  17. #include "lj_tab.h"
  18. #include "lj_ff.h"
  19. #include "lj_lib.h"

  20. /* ------------------------------------------------------------------------ */

  21. #define LJLIB_MODULE_table

  22. LJLIB_LUA(table_foreachi) /*
  23.   function(t, f)
  24.     CHECK_tab(t)
  25.     CHECK_func(f)
  26.     for i=1,#t do
  27.       local r = f(i, t[i])
  28.       if r ~= nil then return r end
  29.     end
  30.   end
  31. */

  32. LJLIB_LUA(table_foreach) /*
  33.   function(t, f)
  34.     CHECK_tab(t)
  35.     CHECK_func(f)
  36.     for k, v in PAIRS(t) do
  37.       local r = f(k, v)
  38.       if r ~= nil then return r end
  39.     end
  40.   end
  41. */

  42. LJLIB_LUA(table_getn) /*
  43.   function(t)
  44.     CHECK_tab(t)
  45.     return #t
  46.   end
  47. */

  48. LJLIB_CF(table_maxn)
  49. {
  50.   GCtab *t = lj_lib_checktab(L, 1);
  51.   TValue *array = tvref(t->array);
  52.   Node *node;
  53.   lua_Number m = 0;
  54.   ptrdiff_t i;
  55.   for (i = (ptrdiff_t)t->asize - 1; i >= 0; i--)
  56.     if (!tvisnil(&array[i])) {
  57.       m = (lua_Number)(int32_t)i;
  58.       break;
  59.     }
  60.   node = noderef(t->node);
  61.   for (i = (ptrdiff_t)t->hmask; i >= 0; i--)
  62.     if (!tvisnil(&node[i].val) && tvisnumber(&node[i].key)) {
  63.       lua_Number n = numberVnum(&node[i].key);
  64.       if (n > m) m = n;
  65.     }
  66.   setnumV(L->top-1, m);
  67.   return 1;
  68. }

  69. LJLIB_CF(table_insert)                LJLIB_REC(.)
  70. {
  71.   GCtab *t = lj_lib_checktab(L, 1);
  72.   int32_t n, i = (int32_t)lj_tab_len(t) + 1;
  73.   int nargs = (int)((char *)L->top - (char *)L->base);
  74.   if (nargs != 2*sizeof(TValue)) {
  75.     if (nargs != 3*sizeof(TValue))
  76.       lj_err_caller(L, LJ_ERR_TABINS);
  77.     /* NOBARRIER: This just moves existing elements around. */
  78.     for (n = lj_lib_checkint(L, 2); i > n; i--) {
  79.       /* The set may invalidate the get pointer, so need to do it first! */
  80.       TValue *dst = lj_tab_setint(L, t, i);
  81.       cTValue *src = lj_tab_getint(t, i-1);
  82.       if (src) {
  83.         copyTV(L, dst, src);
  84.       } else {
  85.         setnilV(dst);
  86.       }
  87.     }
  88.     i = n;
  89.   }
  90.   {
  91.     TValue *dst = lj_tab_setint(L, t, i);
  92.     copyTV(L, dst, L->top-1);  /* Set new value. */
  93.     lj_gc_barriert(L, t, dst);
  94.   }
  95.   return 0;
  96. }

  97. LJLIB_LUA(table_remove) /*
  98.   function(t, pos)
  99.     CHECK_tab(t)
  100.     local len = #t
  101.     if pos == nil then
  102.       if len ~= 0 then
  103.         local old = t[len]
  104.         t[len] = nil
  105.         return old
  106.       end
  107.     else
  108.       CHECK_int(pos)
  109.       if pos >= 1 and pos <= len then
  110.         local old = t[pos]
  111.         for i=pos+1,len do
  112.           t[i-1] = t[i]
  113.         end
  114.         t[len] = nil
  115.         return old
  116.       end
  117.     end
  118.   end
  119. */

  120. LJLIB_CF(table_concat)                LJLIB_REC(.)
  121. {
  122.   GCtab *t = lj_lib_checktab(L, 1);
  123.   GCstr *sep = lj_lib_optstr(L, 2);
  124.   int32_t i = lj_lib_optint(L, 3, 1);
  125.   int32_t e = (L->base+3 < L->top && !tvisnil(L->base+3)) ?
  126.               lj_lib_checkint(L, 4) : (int32_t)lj_tab_len(t);
  127.   SBuf *sb = lj_buf_tmp_(L);
  128.   SBuf *sbx = lj_buf_puttab(sb, t, sep, i, e);
  129.   if (LJ_UNLIKELY(!sbx)) {  /* Error: bad element type. */
  130.     int32_t idx = (int32_t)(intptr_t)sbufP(sb);
  131.     cTValue *o = lj_tab_getint(t, idx);
  132.     lj_err_callerv(L, LJ_ERR_TABCAT,
  133.                    lj_obj_itypename[o ? itypemap(o) : ~LJ_TNIL], idx);
  134.   }
  135.   setstrV(L, L->top-1, lj_buf_str(L, sbx));
  136.   lj_gc_check(L);
  137.   return 1;
  138. }

  139. /* ------------------------------------------------------------------------ */

  140. static void set2(lua_State *L, int i, int j)
  141. {
  142.   lua_rawseti(L, 1, i);
  143.   lua_rawseti(L, 1, j);
  144. }

  145. static int sort_comp(lua_State *L, int a, int b)
  146. {
  147.   if (!lua_isnil(L, 2)) {  /* function? */
  148.     int res;
  149.     lua_pushvalue(L, 2);
  150.     lua_pushvalue(L, a-1);  /* -1 to compensate function */
  151.     lua_pushvalue(L, b-2);  /* -2 to compensate function and `a' */
  152.     lua_call(L, 2, 1);
  153.     res = lua_toboolean(L, -1);
  154.     lua_pop(L, 1);
  155.     return res;
  156.   } else/* a < b? */
  157.     return lua_lessthan(L, a, b);
  158.   }
  159. }

  160. static void auxsort(lua_State *L, int l, int u)
  161. {
  162.   while (l < u) {  /* for tail recursion */
  163.     int i, j;
  164.     /* sort elements a[l], a[(l+u)/2] and a[u] */
  165.     lua_rawgeti(L, 1, l);
  166.     lua_rawgeti(L, 1, u);
  167.     if (sort_comp(L, -1, -2))  /* a[u] < a[l]? */
  168.       set2(L, l, u);  /* swap a[l] - a[u] */
  169.     else
  170.       lua_pop(L, 2);
  171.     if (u-l == 1) break/* only 2 elements */
  172.     i = (l+u)/2;
  173.     lua_rawgeti(L, 1, i);
  174.     lua_rawgeti(L, 1, l);
  175.     if (sort_comp(L, -2, -1)) {  /* a[i]<a[l]? */
  176.       set2(L, i, l);
  177.     } else {
  178.       lua_pop(L, 1);  /* remove a[l] */
  179.       lua_rawgeti(L, 1, u);
  180.       if (sort_comp(L, -1, -2))  /* a[u]<a[i]? */
  181.         set2(L, i, u);
  182.       else
  183.         lua_pop(L, 2);
  184.     }
  185.     if (u-l == 2) break/* only 3 elements */
  186.     lua_rawgeti(L, 1, i);  /* Pivot */
  187.     lua_pushvalue(L, -1);
  188.     lua_rawgeti(L, 1, u-1);
  189.     set2(L, i, u-1);
  190.     /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
  191.     i = l; j = u-1;
  192.     for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
  193.       /* repeat ++i until a[i] >= P */
  194.       while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
  195.         if (i>=u) lj_err_caller(L, LJ_ERR_TABSORT);
  196.         lua_pop(L, 1);  /* remove a[i] */
  197.       }
  198.       /* repeat --j until a[j] <= P */
  199.       while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
  200.         if (j<=l) lj_err_caller(L, LJ_ERR_TABSORT);
  201.         lua_pop(L, 1);  /* remove a[j] */
  202.       }
  203.       if (j<i) {
  204.         lua_pop(L, 3);  /* pop pivot, a[i], a[j] */
  205.         break;
  206.       }
  207.       set2(L, i, j);
  208.     }
  209.     lua_rawgeti(L, 1, u-1);
  210.     lua_rawgeti(L, 1, i);
  211.     set2(L, u-1, i);  /* swap pivot (a[u-1]) with a[i] */
  212.     /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
  213.     /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
  214.     if (i-l < u-i) {
  215.       j=l; i=i-1; l=i+2;
  216.     } else {
  217.       j=i+1; i=u; u=j-2;
  218.     }
  219.     auxsort(L, j, i);  /* call recursively the smaller one */
  220.   }  /* repeat the routine for the larger one */
  221. }

  222. LJLIB_CF(table_sort)
  223. {
  224.   GCtab *t = lj_lib_checktab(L, 1);
  225.   int32_t n = (int32_t)lj_tab_len(t);
  226.   lua_settop(L, 2);
  227.   if (!tvisnil(L->base+1))
  228.     lj_lib_checkfunc(L, 2);
  229.   auxsort(L, 1, n);
  230.   return 0;
  231. }

  232. #if LJ_52
  233. LJLIB_PUSH("n")
  234. LJLIB_CF(table_pack)
  235. {
  236.   TValue *array, *base = L->base;
  237.   MSize i, n = (uint32_t)(L->top - base);
  238.   GCtab *t = lj_tab_new(L, n ? n+1 : 0, 1);
  239.   /* NOBARRIER: The table is new (marked white). */
  240.   setintV(lj_tab_setstr(L, t, strV(lj_lib_upvalue(L, 1))), (int32_t)n);
  241.   for (array = tvref(t->array) + 1, i = 0; i < n; i++)
  242.     copyTV(L, &array[i], &base[i]);
  243.   settabV(L, base, t);
  244.   L->top = base+1;
  245.   lj_gc_check(L);
  246.   return 1;
  247. }
  248. #endif

  249. LJLIB_NOREG LJLIB_CF(table_new)                LJLIB_REC(.)
  250. {
  251.   int32_t a = lj_lib_checkint(L, 1);
  252.   int32_t h = lj_lib_checkint(L, 2);
  253.   lua_createtable(L, a, h);
  254.   return 1;
  255. }

  256. LJLIB_NOREG LJLIB_CF(table_clear)        LJLIB_REC(.)
  257. {
  258.   lj_tab_clear(lj_lib_checktab(L, 1));
  259.   return 0;
  260. }

  261. static int luaopen_table_new(lua_State *L)
  262. {
  263.   return lj_lib_postreg(L, lj_cf_table_new, FF_table_new, "new");
  264. }

  265. static int luaopen_table_clear(lua_State *L)
  266. {
  267.   return lj_lib_postreg(L, lj_cf_table_clear, FF_table_clear, "clear");
  268. }

  269. /* ------------------------------------------------------------------------ */

  270. #include "lj_libdef.h"

  271. LUALIB_API int luaopen_table(lua_State *L)
  272. {
  273.   LJ_LIB_REG(L, LUA_TABLIBNAME, table);
  274. #if LJ_52
  275.   lua_getglobal(L, "unpack");
  276.   lua_setfield(L, -2, "unpack");
  277. #endif
  278.   lj_lib_prereg(L, LUA_TABLIBNAME ".new", luaopen_table_new, tabV(L->top-1));
  279.   lj_lib_prereg(L, LUA_TABLIBNAME ".clear", luaopen_table_clear, tabV(L->top-1));
  280.   return 1;
  281. }