src/lib_table.c

   1 /*
   2 ** Table library.
   3 ** Copyright (C) 2005-2014 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
   9 #define lib_table_c
  10 #define LUA_LIB
  11
  12 #include "lua.h"
  13 #include "lauxlib.h"
  14 #include "lualib.h"
  15
  16 #include "lj_obj.h"
  17 #include "lj_gc.h"
  18 #include "lj_err.h"
  19 #include "lj_buf.h"
  20 #include "lj_tab.h"
  21 #include "lj_ff.h"
  22 #include "lj_lib.h"
  23
  24 /* ------------------------------------------------------------------------ */
  25
  26 #define LJLIB_MODULE_table
  27
  28 LJLIB_LUA(table_foreachi) /*
  29   function(t, f)
  30     CHECK_tab(t)
  31     CHECK_func(f)
  32     for i=1,#t do
  33       local r = f(i, t[i])
  34       if r ~= nil then return r end
  35     end
  36   end
  37 */
  38
  39 LJLIB_LUA(table_foreach) /*
  40   function(t, f)
  41     CHECK_tab(t)
  42     CHECK_func(f)
  43     for k, v in PAIRS(t) do
  44       local r = f(k, v)
  45       if r ~= nil then return r end
  46     end
  47   end
  48 */
  49
  50 LJLIB_LUA(table_getn) /*
  51   function(t)
  52     CHECK_tab(t)
  53     return #t
  54   end
  55 */
  56
  57 LJLIB_CF(table_maxn)
  58 {
  59   GCtab *t = lj_lib_checktab(L, 1);
  60   TValue *array = tvref(t->array);
  61   Node *node;
  62   lua_Number m = 0;
  63   ptrdiff_t i;
  64   for (i = (ptrdiff_t)t->asize - 1; i >= 0; i--)
  65     if (!tvisnil(&array[i])) {
  66       m = (lua_Number)(int32_t)i;
  67       break;
  68     }
  69   node = noderef(t->node);
  70   for (i = (ptrdiff_t)t->hmask; i >= 0; i--)
  71     if (!tvisnil(&node[i].val) && tvisnumber(&node[i].key)) {
  72       lua_Number n = numberVnum(&node[i].key);
  73       if (n > m) m = n;
  74     }
  75   setnumV(L->top-1, m);
  76   return 1;
  77 }
  78
  79 LJLIB_CF(table_insert)          LJLIB_REC(.)
  80 {
  81   GCtab *t = lj_lib_checktab(L, 1);
  82   int32_t n, i = (int32_t)lj_tab_len(t) + 1;
  83   int nargs = (int)((char *)L->top - (char *)L->base);
  84   if (nargs != 2*sizeof(TValue)) {
  85     if (nargs != 3*sizeof(TValue))
  86       lj_err_caller(L, LJ_ERR_TABINS);
  87     /* NOBARRIER: This just moves existing elements around. */
  88     for (n = lj_lib_checkint(L, 2); i > n; i--) {
  89       /* The set may invalidate the get pointer, so need to do it first! */
  90       TValue *dst = lj_tab_setint(L, t, i);
  91       cTValue *src = lj_tab_getint(t, i-1);
  92       if (src) {
  93         copyTV(L, dst, src);
  94       } else {
  95         setnilV(dst);
  96       }
  97     }
  98     i = n;
  99   }
 100   {
 101     TValue *dst = lj_tab_setint(L, t, i);
 102     copyTV(L, dst, L->top-1);  /* Set new value. */
 103     lj_gc_barriert(L, t, dst);
 104   }
 105   return 0;
 106 }
 107
 108 LJLIB_LUA(table_remove) /*
 109   function(t, pos)
 110     CHECK_tab(t)
 111     local len = #t
 112     if pos == nil then
 113       if len ~= 0 then
 114         local old = t[len]
 115         t[len] = nil
 116         return old
 117       end
 118     else
 119       CHECK_int(pos)
 120       if pos >= 1 and pos <= len then
 121         local old = t[pos]
 122         for i=pos+1,len do
 123           t[i-1] = t[i]
 124         end
 125         t[len] = nil
 126         return old
 127       end
 128     end
 129   end
 130 */
 131
 132 LJLIB_CF(table_concat)          LJLIB_REC(.)
 133 {
 134   GCtab *t = lj_lib_checktab(L, 1);
 135   GCstr *sep = lj_lib_optstr(L, 2);
 136   int32_t i = lj_lib_optint(L, 3, 1);
 137   int32_t e = (L->base+3 < L->top && !tvisnil(L->base+3)) ?
 138               lj_lib_checkint(L, 4) : (int32_t)lj_tab_len(t);
 139   SBuf *sb = lj_buf_tmp_(L);
 140   SBuf *sbx = lj_buf_puttab(sb, t, sep, i, e);
 141   if (LJ_UNLIKELY(!sbx)) {  /* Error: bad element type. */
 142     int32_t idx = (int32_t)(intptr_t)sbufP(sb);
 143     cTValue *o = lj_tab_getint(t, idx);
 144     lj_err_callerv(L, LJ_ERR_TABCAT,
 145                    lj_obj_itypename[o ? itypemap(o) : ~LJ_TNIL], idx);
 146   }
 147   setstrV(L, L->top-1, lj_buf_str(L, sbx));
 148   lj_gc_check(L);
 149   return 1;
 150 }
 151
 152 /* ------------------------------------------------------------------------ */
 153
 154 static void set2(lua_State *L, int i, int j)
 155 {
 156   lua_rawseti(L, 1, i);
 157   lua_rawseti(L, 1, j);
 158 }
 159
 160 static int sort_comp(lua_State *L, int a, int b)
 161 {
 162   if (!lua_isnil(L, 2)) {  /* function? */
 163     int res;
 164     lua_pushvalue(L, 2);
 165     lua_pushvalue(L, a-1);  /* -1 to compensate function */
 166     lua_pushvalue(L, b-2);  /* -2 to compensate function and `a' */
 167     lua_call(L, 2, 1);
 168     res = lua_toboolean(L, -1);
 169     lua_pop(L, 1);
 170     return res;
 171   } else {  /* a < b? */
 172     return lua_lessthan(L, a, b);
 173   }
 174 }
 175
 176 static void auxsort(lua_State *L, int l, int u)
 177 {
 178   while (l < u) {  /* for tail recursion */
 179     int i, j;
 180     /* sort elements a[l], a[(l+u)/2] and a[u] */
 181     lua_rawgeti(L, 1, l);
 182     lua_rawgeti(L, 1, u);
 183     if (sort_comp(L, -1, -2))  /* a[u] < a[l]? */
 184       set2(L, l, u);  /* swap a[l] - a[u] */
 185     else
 186       lua_pop(L, 2);
 187     if (u-l == 1) break;  /* only 2 elements */
 188     i = (l+u)/2;
 189     lua_rawgeti(L, 1, i);
 190     lua_rawgeti(L, 1, l);
 191     if (sort_comp(L, -2, -1)) {  /* a[i]<a[l]? */
 192       set2(L, i, l);
 193     } else {
 194       lua_pop(L, 1);  /* remove a[l] */
 195       lua_rawgeti(L, 1, u);
 196       if (sort_comp(L, -1, -2))  /* a[u]<a[i]? */
 197         set2(L, i, u);
 198       else
 199         lua_pop(L, 2);
 200     }
 201     if (u-l == 2) break;  /* only 3 elements */
 202     lua_rawgeti(L, 1, i);  /* Pivot */
 203     lua_pushvalue(L, -1);
 204     lua_rawgeti(L, 1, u-1);
 205     set2(L, i, u-1);
 206     /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
 207     i = l; j = u-1;
 208     for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
 209       /* repeat ++i until a[i] >= P */
 210       while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
 211         if (i>=u) lj_err_caller(L, LJ_ERR_TABSORT);
 212         lua_pop(L, 1);  /* remove a[i] */
 213       }
 214       /* repeat --j until a[j] <= P */
 215       while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
 216         if (j<=l) lj_err_caller(L, LJ_ERR_TABSORT);
 217         lua_pop(L, 1);  /* remove a[j] */
 218       }
 219       if (j<i) {
 220         lua_pop(L, 3);  /* pop pivot, a[i], a[j] */
 221         break;
 222       }
 223       set2(L, i, j);
 224     }
 225     lua_rawgeti(L, 1, u-1);
 226     lua_rawgeti(L, 1, i);
 227     set2(L, u-1, i);  /* swap pivot (a[u-1]) with a[i] */
 228     /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
 229     /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
 230     if (i-l < u-i) {
 231       j=l; i=i-1; l=i+2;
 232     } else {
 233       j=i+1; i=u; u=j-2;
 234     }
 235     auxsort(L, j, i);  /* call recursively the smaller one */
 236   }  /* repeat the routine for the larger one */
 237 }
 238
 239 LJLIB_CF(table_sort)
 240 {
 241   GCtab *t = lj_lib_checktab(L, 1);
 242   int32_t n = (int32_t)lj_tab_len(t);
 243   lua_settop(L, 2);
 244   if (!tvisnil(L->base+1))
 245     lj_lib_checkfunc(L, 2);
 246   auxsort(L, 1, n);
 247   return 0;
 248 }
 249
 250 #if LJ_52
 251 LJLIB_PUSH("n")
 252 LJLIB_CF(table_pack)
 253 {
 254   TValue *array, *base = L->base;
 255   MSize i, n = (uint32_t)(L->top - base);
 256   GCtab *t = lj_tab_new(L, n ? n+1 : 0, 1);
 257   /* NOBARRIER: The table is new (marked white). */
 258   setintV(lj_tab_setstr(L, t, strV(lj_lib_upvalue(L, 1))), (int32_t)n);
 259   for (array = tvref(t->array) + 1, i = 0; i < n; i++)
 260     copyTV(L, &array[i], &base[i]);
 261   settabV(L, base, t);
 262   L->top = base+1;
 263   lj_gc_check(L);
 264   return 1;
 265 }
 266 #endif
 267
 268 LJLIB_NOREG LJLIB_CF(table_new)         LJLIB_REC(.)
 269 {
 270   int32_t a = lj_lib_checkint(L, 1);
 271   int32_t h = lj_lib_checkint(L, 2);
 272   lua_createtable(L, a, h);
 273   return 1;
 274 }
 275
 276 LJLIB_NOREG LJLIB_CF(table_clear)       LJLIB_REC(.)
 277 {
 278   lj_tab_clear(lj_lib_checktab(L, 1));
 279   return 0;
 280 }
 281
 282 static int luaopen_table_new(lua_State *L)
 283 {
 284   return lj_lib_postreg(L, lj_cf_table_new, FF_table_new, "new");
 285 }
 286
 287 static int luaopen_table_clear(lua_State *L)
 288 {
 289   return lj_lib_postreg(L, lj_cf_table_clear, FF_table_clear, "clear");
 290 }
 291
 292 /* ------------------------------------------------------------------------ */
 293
 294 #include "lj_libdef.h"
 295
 296 LUALIB_API int luaopen_table(lua_State *L)
 297 {
 298   LJ_LIB_REG(L, LUA_TABLIBNAME, table);
 299 #if LJ_52
 300   lua_getglobal(L, "unpack");
 301   lua_setfield(L, -2, "unpack");
 302 #endif
 303   lj_lib_prereg(L, LUA_TABLIBNAME ".new", luaopen_table_new, tabV(L->top-1));
 304   lj_lib_prereg(L, LUA_TABLIBNAME ".clear", luaopen_table_clear, tabV(L->top-1));
 305   return 1;
 306 }
 307