src/lib_table.c

   1 /*
   2 ** Table library.
   3 ** Copyright (C) 2005-2023 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_LUA(table_move) /*
 133   function(a1, f, e, t, a2)
 134     CHECK_tab(a1)
 135     CHECK_int(f)
 136     CHECK_int(e)
 137     CHECK_int(t)
 138     if a2 == nil then a2 = a1 end
 139     CHECK_tab(a2)
 140     if e >= f then
 141       local d = t - f
 142       if t > e or t <= f or a2 ~= a1 then
 143         for i=f,e do a2[i+d] = a1[i] end
 144       else
 145         for i=e,f,-1 do a2[i+d] = a1[i] end
 146       end
 147     end
 148     return a2
 149   end
 150 */
 151
 152 LJLIB_CF(table_concat)          LJLIB_REC(.)
 153 {
 154   GCtab *t = lj_lib_checktab(L, 1);
 155   GCstr *sep = lj_lib_optstr(L, 2);
 156   int32_t i = lj_lib_optint(L, 3, 1);
 157   int32_t e = (L->base+3 < L->top && !tvisnil(L->base+3)) ?
 158               lj_lib_checkint(L, 4) : (int32_t)lj_tab_len(t);
 159   SBuf *sb = lj_buf_tmp_(L);
 160   SBuf *sbx = lj_buf_puttab(sb, t, sep, i, e);
 161   if (LJ_UNLIKELY(!sbx)) {  /* Error: bad element type. */
 162     int32_t idx = (int32_t)(intptr_t)sb->w;
 163     cTValue *o = lj_tab_getint(t, idx);
 164     lj_err_callerv(L, LJ_ERR_TABCAT,
 165                    lj_obj_itypename[o ? itypemap(o) : ~LJ_TNIL], idx);
 166   }
 167   setstrV(L, L->top-1, lj_buf_str(L, sbx));
 168   lj_gc_check(L);
 169   return 1;
 170 }
 171
 172 /* ------------------------------------------------------------------------ */
 173
 174 static void set2(lua_State *L, int i, int j)
 175 {
 176   lua_rawseti(L, 1, i);
 177   lua_rawseti(L, 1, j);
 178 }
 179
 180 static int sort_comp(lua_State *L, int a, int b)
 181 {
 182   if (!lua_isnil(L, 2)) {  /* function? */
 183     int res;
 184     lua_pushvalue(L, 2);
 185     lua_pushvalue(L, a-1);  /* -1 to compensate function */
 186     lua_pushvalue(L, b-2);  /* -2 to compensate function and `a' */
 187     lua_call(L, 2, 1);
 188     res = lua_toboolean(L, -1);
 189     lua_pop(L, 1);
 190     return res;
 191   } else {  /* a < b? */
 192     return lua_lessthan(L, a, b);
 193   }
 194 }
 195
 196 static void auxsort(lua_State *L, int l, int u)
 197 {
 198   while (l < u) {  /* for tail recursion */
 199     int i, j;
 200     /* sort elements a[l], a[(l+u)/2] and a[u] */
 201     lua_rawgeti(L, 1, l);
 202     lua_rawgeti(L, 1, u);
 203     if (sort_comp(L, -1, -2))  /* a[u] < a[l]? */
 204       set2(L, l, u);  /* swap a[l] - a[u] */
 205     else
 206       lua_pop(L, 2);
 207     if (u-l == 1) break;  /* only 2 elements */
 208     i = (l+u)/2;
 209     lua_rawgeti(L, 1, i);
 210     lua_rawgeti(L, 1, l);
 211     if (sort_comp(L, -2, -1)) {  /* a[i]<a[l]? */
 212       set2(L, i, l);
 213     } else {
 214       lua_pop(L, 1);  /* remove a[l] */
 215       lua_rawgeti(L, 1, u);
 216       if (sort_comp(L, -1, -2))  /* a[u]<a[i]? */
 217         set2(L, i, u);
 218       else
 219         lua_pop(L, 2);
 220     }
 221     if (u-l == 2) break;  /* only 3 elements */
 222     lua_rawgeti(L, 1, i);  /* Pivot */
 223     lua_pushvalue(L, -1);
 224     lua_rawgeti(L, 1, u-1);
 225     set2(L, i, u-1);
 226     /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
 227     i = l; j = u-1;
 228     for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
 229       /* repeat ++i until a[i] >= P */
 230       while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
 231         if (i>=u) lj_err_caller(L, LJ_ERR_TABSORT);
 232         lua_pop(L, 1);  /* remove a[i] */
 233       }
 234       /* repeat --j until a[j] <= P */
 235       while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
 236         if (j<=l) lj_err_caller(L, LJ_ERR_TABSORT);
 237         lua_pop(L, 1);  /* remove a[j] */
 238       }
 239       if (j<i) {
 240         lua_pop(L, 3);  /* pop pivot, a[i], a[j] */
 241         break;
 242       }
 243       set2(L, i, j);
 244     }
 245     lua_rawgeti(L, 1, u-1);
 246     lua_rawgeti(L, 1, i);
 247     set2(L, u-1, i);  /* swap pivot (a[u-1]) with a[i] */
 248     /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
 249     /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
 250     if (i-l < u-i) {
 251       j=l; i=i-1; l=i+2;
 252     } else {
 253       j=i+1; i=u; u=j-2;
 254     }
 255     auxsort(L, j, i);  /* call recursively the smaller one */
 256   }  /* repeat the routine for the larger one */
 257 }
 258
 259 LJLIB_CF(table_sort)
 260 {
 261   GCtab *t = lj_lib_checktab(L, 1);
 262   int32_t n = (int32_t)lj_tab_len(t);
 263   lua_settop(L, 2);
 264   if (!tvisnil(L->base+1))
 265     lj_lib_checkfunc(L, 2);
 266   auxsort(L, 1, n);
 267   return 0;
 268 }
 269
 270 #if LJ_52
 271 LJLIB_PUSH("n")
 272 LJLIB_CF(table_pack)
 273 {
 274   TValue *array, *base = L->base;
 275   MSize i, n = (uint32_t)(L->top - base);
 276   GCtab *t = lj_tab_new(L, n ? n+1 : 0, 1);
 277   /* NOBARRIER: The table is new (marked white). */
 278   setintV(lj_tab_setstr(L, t, strV(lj_lib_upvalue(L, 1))), (int32_t)n);
 279   for (array = tvref(t->array) + 1, i = 0; i < n; i++)
 280     copyTV(L, &array[i], &base[i]);
 281   settabV(L, base, t);
 282   L->top = base+1;
 283   lj_gc_check(L);
 284   return 1;
 285 }
 286 #endif
 287
 288 LJLIB_NOREG LJLIB_CF(table_new)         LJLIB_REC(.)
 289 {
 290   int32_t a = lj_lib_checkint(L, 1);
 291   int32_t h = lj_lib_checkint(L, 2);
 292   lua_createtable(L, a, h);
 293   return 1;
 294 }
 295
 296 LJLIB_NOREG LJLIB_CF(table_clear)       LJLIB_REC(.)
 297 {
 298   lj_tab_clear(lj_lib_checktab(L, 1));
 299   return 0;
 300 }
 301
 302 static int luaopen_table_new(lua_State *L)
 303 {
 304   return lj_lib_postreg(L, lj_cf_table_new, FF_table_new, "new");
 305 }
 306
 307 static int luaopen_table_clear(lua_State *L)
 308 {
 309   return lj_lib_postreg(L, lj_cf_table_clear, FF_table_clear, "clear");
 310 }
 311
 312 /* ------------------------------------------------------------------------ */
 313
 314 #include "lj_libdef.h"
 315
 316 LUALIB_API int luaopen_table(lua_State *L)
 317 {
 318   LJ_LIB_REG(L, LUA_TABLIBNAME, table);
 319 #if LJ_52
 320   lua_getglobal(L, "unpack");
 321   lua_setfield(L, -2, "unpack");
 322 #endif
 323   lj_lib_prereg(L, LUA_TABLIBNAME ".new", luaopen_table_new, tabV(L->top-1));
 324   lj_lib_prereg(L, LUA_TABLIBNAME ".clear", luaopen_table_clear, tabV(L->top-1));
 325   return 1;
 326 }
 327