src/lib_table.c

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