lib_table.c (8220B)
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_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_int(f) 135 CHECK_int(e) 136 CHECK_int(t) 137 CHECK_tab(a1) 138 a2 = a2 or a1 139 CHECK_tab(a2) 140 if e >= f then 141 local m, n, d = 0, e-f, 1 142 if t > f then m, n, d = n, m, -1 end 143 for i = m, n, d do 144 a2[t+i] = a1[f+i] 145 end 146 end 147 return a2 148 end 149 */ 150 151 LJLIB_CF(table_concat) LJLIB_REC(.) 152 { 153 GCtab *t = lj_lib_checktab(L, 1); 154 GCstr *sep = lj_lib_optstr(L, 2); 155 int32_t i = lj_lib_optint(L, 3, 1); 156 int32_t e = (L->base+3 < L->top && !tvisnil(L->base+3)) ? 157 lj_lib_checkint(L, 4) : (int32_t)lj_tab_len(t); 158 SBuf *sb = lj_buf_tmp_(L); 159 SBuf *sbx = lj_buf_puttab(sb, t, sep, i, e); 160 if (LJ_UNLIKELY(!sbx)) { /* Error: bad element type. */ 161 int32_t idx = (int32_t)(intptr_t)sbufP(sb); 162 cTValue *o = lj_tab_getint(t, idx); 163 lj_err_callerv(L, LJ_ERR_TABCAT, 164 lj_obj_itypename[o ? itypemap(o) : ~LJ_TNIL], idx); 165 } 166 setstrV(L, L->top-1, lj_buf_str(L, sbx)); 167 lj_gc_check(L); 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_51 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 LJLIB_NOREG LJLIB_CF(table_new) LJLIB_REC(.) 288 { 289 int32_t a = lj_lib_checkint(L, 1); 290 int32_t h = lj_lib_checkint(L, 2); 291 lua_createtable(L, a, h); 292 return 1; 293 } 294 295 LJLIB_NOREG LJLIB_CF(table_clear) LJLIB_REC(.) 296 { 297 lj_tab_clear(lj_lib_checktab(L, 1)); 298 return 0; 299 } 300 301 static int luaopen_table_new(lua_State *L) 302 { 303 return lj_lib_postreg(L, lj_cf_table_new, FF_table_new, "new"); 304 } 305 306 static int luaopen_table_clear(lua_State *L) 307 { 308 return lj_lib_postreg(L, lj_cf_table_clear, FF_table_clear, "clear"); 309 } 310 311 /* ------------------------------------------------------------------------ */ 312 313 #include "lj_libdef.h" 314 315 LUALIB_API int luaopen_table(lua_State *L) 316 { 317 LJ_LIB_REG(L, LUA_TABLIBNAME, table); 318 319 /* Ugh, this field juggling is messy. Because they live in different modules 320 * depending on version. LJLIB*LUA does not support conditionals, 321 * so that's another ugly duckling in the pack. 322 */ 323 #if !LJ_51 324 lua_getglobal(L, "unpack"); 325 lua_setfield(L, -2, "unpack"); 326 #endif 327 #if 0 328 lua_pushnil(L); 329 lua_setglobal(L, "unpack"); 330 #endif 331 #if !LJ_53 332 lua_pushnil(L); 333 lua_setfield(L, -2, "move"); 334 #endif 335 lj_lib_prereg(L, LUA_TABLIBNAME ".new", luaopen_table_new, tabV(L->top-1)); 336 lj_lib_prereg(L, LUA_TABLIBNAME ".clear", luaopen_table_clear, tabV(L->top-1)); 337 return 1; 338 } 339