1280405Srpaulo/* 2344220Skevans** $Id: ltablib.c,v 1.93.1.1 2017/04/19 17:20:42 roberto Exp $ 3280405Srpaulo** Library for Table Manipulation 4280405Srpaulo** See Copyright Notice in lua.h 5280405Srpaulo*/ 6280405Srpaulo 7280405Srpaulo#define ltablib_c 8280405Srpaulo#define LUA_LIB 9280405Srpaulo 10280405Srpaulo#include "lprefix.h" 11280405Srpaulo 12280405Srpaulo 13280405Srpaulo#include <limits.h> 14280405Srpaulo#include <stddef.h> 15326344Simp#include <string.h> 16280405Srpaulo 17280405Srpaulo#include "lua.h" 18280405Srpaulo 19280405Srpaulo#include "lauxlib.h" 20280405Srpaulo#include "lualib.h" 21280405Srpaulo 22280405Srpaulo 23280405Srpaulo/* 24326344Simp** Operations that an object must define to mimic a table 25326344Simp** (some functions only need some of them) 26280405Srpaulo*/ 27326344Simp#define TAB_R 1 /* read */ 28326344Simp#define TAB_W 2 /* write */ 29326344Simp#define TAB_L 4 /* length */ 30326344Simp#define TAB_RW (TAB_R | TAB_W) /* read/write */ 31280405Srpaulo 32280405Srpaulo 33326344Simp#define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n)) 34326344Simp 35326344Simp 36326344Simpstatic int checkfield (lua_State *L, const char *key, int n) { 37326344Simp lua_pushstring(L, key); 38326344Simp return (lua_rawget(L, -n) != LUA_TNIL); 39326344Simp} 40326344Simp 41326344Simp 42280405Srpaulo/* 43326344Simp** Check that 'arg' either is a table or can behave like one (that is, 44326344Simp** has a metatable with the required metamethods) 45280405Srpaulo*/ 46326344Simpstatic void checktab (lua_State *L, int arg, int what) { 47326344Simp if (lua_type(L, arg) != LUA_TTABLE) { /* is it not a table? */ 48326344Simp int n = 1; /* number of elements to pop */ 49326344Simp if (lua_getmetatable(L, arg) && /* must have metatable */ 50326344Simp (!(what & TAB_R) || checkfield(L, "__index", ++n)) && 51326344Simp (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) && 52326344Simp (!(what & TAB_L) || checkfield(L, "__len", ++n))) { 53326344Simp lua_pop(L, n); /* pop metatable and tested metamethods */ 54326344Simp } 55326344Simp else 56326344Simp luaL_checktype(L, arg, LUA_TTABLE); /* force an error */ 57280405Srpaulo } 58280405Srpaulo} 59280405Srpaulo 60280405Srpaulo 61280405Srpaulo#if defined(LUA_COMPAT_MAXN) 62280405Srpaulostatic int maxn (lua_State *L) { 63280405Srpaulo lua_Number max = 0; 64280405Srpaulo luaL_checktype(L, 1, LUA_TTABLE); 65280405Srpaulo lua_pushnil(L); /* first key */ 66280405Srpaulo while (lua_next(L, 1)) { 67280405Srpaulo lua_pop(L, 1); /* remove value */ 68280405Srpaulo if (lua_type(L, -1) == LUA_TNUMBER) { 69280405Srpaulo lua_Number v = lua_tonumber(L, -1); 70280405Srpaulo if (v > max) max = v; 71280405Srpaulo } 72280405Srpaulo } 73280405Srpaulo lua_pushnumber(L, max); 74280405Srpaulo return 1; 75280405Srpaulo} 76280405Srpaulo#endif 77280405Srpaulo 78280405Srpaulo 79280405Srpaulostatic int tinsert (lua_State *L) { 80326344Simp lua_Integer e = aux_getn(L, 1, TAB_RW) + 1; /* first empty element */ 81280405Srpaulo lua_Integer pos; /* where to insert new element */ 82280405Srpaulo switch (lua_gettop(L)) { 83280405Srpaulo case 2: { /* called with only 2 arguments */ 84280405Srpaulo pos = e; /* insert new element at the end */ 85280405Srpaulo break; 86280405Srpaulo } 87280405Srpaulo case 3: { 88280405Srpaulo lua_Integer i; 89280405Srpaulo pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */ 90280405Srpaulo luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds"); 91280405Srpaulo for (i = e; i > pos; i--) { /* move up elements */ 92326344Simp lua_geti(L, 1, i - 1); 93326344Simp lua_seti(L, 1, i); /* t[i] = t[i - 1] */ 94280405Srpaulo } 95280405Srpaulo break; 96280405Srpaulo } 97280405Srpaulo default: { 98280405Srpaulo return luaL_error(L, "wrong number of arguments to 'insert'"); 99280405Srpaulo } 100280405Srpaulo } 101326344Simp lua_seti(L, 1, pos); /* t[pos] = v */ 102280405Srpaulo return 0; 103280405Srpaulo} 104280405Srpaulo 105280405Srpaulo 106280405Srpaulostatic int tremove (lua_State *L) { 107326344Simp lua_Integer size = aux_getn(L, 1, TAB_RW); 108280405Srpaulo lua_Integer pos = luaL_optinteger(L, 2, size); 109280405Srpaulo if (pos != size) /* validate 'pos' if given */ 110280405Srpaulo luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds"); 111326344Simp lua_geti(L, 1, pos); /* result = t[pos] */ 112280405Srpaulo for ( ; pos < size; pos++) { 113326344Simp lua_geti(L, 1, pos + 1); 114326344Simp lua_seti(L, 1, pos); /* t[pos] = t[pos + 1] */ 115280405Srpaulo } 116280405Srpaulo lua_pushnil(L); 117326344Simp lua_seti(L, 1, pos); /* t[pos] = nil */ 118280405Srpaulo return 1; 119280405Srpaulo} 120280405Srpaulo 121280405Srpaulo 122326344Simp/* 123326344Simp** Copy elements (1[f], ..., 1[e]) into (tt[t], tt[t+1], ...). Whenever 124326344Simp** possible, copy in increasing order, which is better for rehashing. 125326344Simp** "possible" means destination after original range, or smaller 126326344Simp** than origin, or copying to another table. 127326344Simp*/ 128280405Srpaulostatic int tmove (lua_State *L) { 129280405Srpaulo lua_Integer f = luaL_checkinteger(L, 2); 130280405Srpaulo lua_Integer e = luaL_checkinteger(L, 3); 131280405Srpaulo lua_Integer t = luaL_checkinteger(L, 4); 132280405Srpaulo int tt = !lua_isnoneornil(L, 5) ? 5 : 1; /* destination table */ 133326344Simp checktab(L, 1, TAB_R); 134326344Simp checktab(L, tt, TAB_W); 135280405Srpaulo if (e >= f) { /* otherwise, nothing to move */ 136280405Srpaulo lua_Integer n, i; 137326344Simp luaL_argcheck(L, f > 0 || e < LUA_MAXINTEGER + f, 3, 138326344Simp "too many elements to move"); 139280405Srpaulo n = e - f + 1; /* number of elements to move */ 140326344Simp luaL_argcheck(L, t <= LUA_MAXINTEGER - n + 1, 4, 141326344Simp "destination wrap around"); 142326344Simp if (t > e || t <= f || (tt != 1 && !lua_compare(L, 1, tt, LUA_OPEQ))) { 143326344Simp for (i = 0; i < n; i++) { 144326344Simp lua_geti(L, 1, f + i); 145326344Simp lua_seti(L, tt, t + i); 146280405Srpaulo } 147280405Srpaulo } 148280405Srpaulo else { 149326344Simp for (i = n - 1; i >= 0; i--) { 150326344Simp lua_geti(L, 1, f + i); 151326344Simp lua_seti(L, tt, t + i); 152280405Srpaulo } 153280405Srpaulo } 154280405Srpaulo } 155326344Simp lua_pushvalue(L, tt); /* return destination table */ 156280405Srpaulo return 1; 157280405Srpaulo} 158280405Srpaulo 159280405Srpaulo 160326344Simpstatic void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) { 161326344Simp lua_geti(L, 1, i); 162280405Srpaulo if (!lua_isstring(L, -1)) 163280405Srpaulo luaL_error(L, "invalid value (%s) at index %d in table for 'concat'", 164280405Srpaulo luaL_typename(L, -1), i); 165280405Srpaulo luaL_addvalue(b); 166280405Srpaulo} 167280405Srpaulo 168280405Srpaulo 169280405Srpaulostatic int tconcat (lua_State *L) { 170280405Srpaulo luaL_Buffer b; 171326344Simp lua_Integer last = aux_getn(L, 1, TAB_R); 172280405Srpaulo size_t lsep; 173280405Srpaulo const char *sep = luaL_optlstring(L, 2, "", &lsep); 174326344Simp lua_Integer i = luaL_optinteger(L, 3, 1); 175326344Simp last = luaL_optinteger(L, 4, last); 176280405Srpaulo luaL_buffinit(L, &b); 177280405Srpaulo for (; i < last; i++) { 178326344Simp addfield(L, &b, i); 179280405Srpaulo luaL_addlstring(&b, sep, lsep); 180280405Srpaulo } 181280405Srpaulo if (i == last) /* add last value (if interval was not empty) */ 182326344Simp addfield(L, &b, i); 183280405Srpaulo luaL_pushresult(&b); 184280405Srpaulo return 1; 185280405Srpaulo} 186280405Srpaulo 187280405Srpaulo 188280405Srpaulo/* 189280405Srpaulo** {====================================================== 190280405Srpaulo** Pack/unpack 191280405Srpaulo** ======================================================= 192280405Srpaulo*/ 193280405Srpaulo 194280405Srpaulostatic int pack (lua_State *L) { 195280405Srpaulo int i; 196280405Srpaulo int n = lua_gettop(L); /* number of elements to pack */ 197280405Srpaulo lua_createtable(L, n, 1); /* create result table */ 198280405Srpaulo lua_insert(L, 1); /* put it at index 1 */ 199280405Srpaulo for (i = n; i >= 1; i--) /* assign elements */ 200326344Simp lua_seti(L, 1, i); 201280405Srpaulo lua_pushinteger(L, n); 202280405Srpaulo lua_setfield(L, 1, "n"); /* t.n = number of elements */ 203280405Srpaulo return 1; /* return table */ 204280405Srpaulo} 205280405Srpaulo 206280405Srpaulo 207280405Srpaulostatic int unpack (lua_State *L) { 208280405Srpaulo lua_Unsigned n; 209326344Simp lua_Integer i = luaL_optinteger(L, 2, 1); 210326344Simp lua_Integer e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); 211280405Srpaulo if (i > e) return 0; /* empty range */ 212280405Srpaulo n = (lua_Unsigned)e - i; /* number of elements minus 1 (avoid overflows) */ 213280405Srpaulo if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, (int)(++n))) 214280405Srpaulo return luaL_error(L, "too many results to unpack"); 215326344Simp for (; i < e; i++) { /* push arg[i..e - 1] (to avoid overflows) */ 216326344Simp lua_geti(L, 1, i); 217326344Simp } 218326344Simp lua_geti(L, 1, e); /* push last element */ 219280405Srpaulo return (int)n; 220280405Srpaulo} 221280405Srpaulo 222280405Srpaulo/* }====================================================== */ 223280405Srpaulo 224280405Srpaulo 225280405Srpaulo 226280405Srpaulo/* 227280405Srpaulo** {====================================================== 228280405Srpaulo** Quicksort 229280405Srpaulo** (based on 'Algorithms in MODULA-3', Robert Sedgewick; 230280405Srpaulo** Addison-Wesley, 1993.) 231280405Srpaulo** ======================================================= 232280405Srpaulo*/ 233280405Srpaulo 234280405Srpaulo 235326344Simp/* type for array indices */ 236326344Simptypedef unsigned int IdxT; 237326344Simp 238326344Simp 239326344Simp/* 240326344Simp** Produce a "random" 'unsigned int' to randomize pivot choice. This 241326344Simp** macro is used only when 'sort' detects a big imbalance in the result 242326344Simp** of a partition. (If you don't want/need this "randomness", ~0 is a 243326344Simp** good choice.) 244326344Simp*/ 245326344Simp#if !defined(l_randomizePivot) /* { */ 246326344Simp 247326344Simp#include <time.h> 248326344Simp 249326344Simp/* size of 'e' measured in number of 'unsigned int's */ 250326344Simp#define sof(e) (sizeof(e) / sizeof(unsigned int)) 251326344Simp 252326344Simp/* 253326344Simp** Use 'time' and 'clock' as sources of "randomness". Because we don't 254326344Simp** know the types 'clock_t' and 'time_t', we cannot cast them to 255326344Simp** anything without risking overflows. A safe way to use their values 256326344Simp** is to copy them to an array of a known type and use the array values. 257326344Simp*/ 258326344Simpstatic unsigned int l_randomizePivot (void) { 259326344Simp clock_t c = clock(); 260326344Simp time_t t = time(NULL); 261326344Simp unsigned int buff[sof(c) + sof(t)]; 262326344Simp unsigned int i, rnd = 0; 263326344Simp memcpy(buff, &c, sof(c) * sizeof(unsigned int)); 264326344Simp memcpy(buff + sof(c), &t, sof(t) * sizeof(unsigned int)); 265326344Simp for (i = 0; i < sof(buff); i++) 266326344Simp rnd += buff[i]; 267326344Simp return rnd; 268280405Srpaulo} 269280405Srpaulo 270326344Simp#endif /* } */ 271326344Simp 272326344Simp 273326344Simp/* arrays larger than 'RANLIMIT' may use randomized pivots */ 274326344Simp#define RANLIMIT 100u 275326344Simp 276326344Simp 277326344Simpstatic void set2 (lua_State *L, IdxT i, IdxT j) { 278326344Simp lua_seti(L, 1, i); 279326344Simp lua_seti(L, 1, j); 280326344Simp} 281326344Simp 282326344Simp 283326344Simp/* 284326344Simp** Return true iff value at stack index 'a' is less than the value at 285326344Simp** index 'b' (according to the order of the sort). 286326344Simp*/ 287280405Srpaulostatic int sort_comp (lua_State *L, int a, int b) { 288326344Simp if (lua_isnil(L, 2)) /* no function? */ 289326344Simp return lua_compare(L, a, b, LUA_OPLT); /* a < b */ 290326344Simp else { /* function */ 291280405Srpaulo int res; 292326344Simp lua_pushvalue(L, 2); /* push function */ 293280405Srpaulo lua_pushvalue(L, a-1); /* -1 to compensate function */ 294280405Srpaulo lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ 295326344Simp lua_call(L, 2, 1); /* call function */ 296326344Simp res = lua_toboolean(L, -1); /* get result */ 297326344Simp lua_pop(L, 1); /* pop result */ 298280405Srpaulo return res; 299280405Srpaulo } 300280405Srpaulo} 301280405Srpaulo 302326344Simp 303326344Simp/* 304326344Simp** Does the partition: Pivot P is at the top of the stack. 305326344Simp** precondition: a[lo] <= P == a[up-1] <= a[up], 306326344Simp** so it only needs to do the partition from lo + 1 to up - 2. 307326344Simp** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] 308326344Simp** returns 'i'. 309326344Simp*/ 310326344Simpstatic IdxT partition (lua_State *L, IdxT lo, IdxT up) { 311326344Simp IdxT i = lo; /* will be incremented before first use */ 312326344Simp IdxT j = up - 1; /* will be decremented before first use */ 313326344Simp /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ 314326344Simp for (;;) { 315326344Simp /* next loop: repeat ++i while a[i] < P */ 316326344Simp while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { 317326344Simp if (i == up - 1) /* a[i] < P but a[up - 1] == P ?? */ 318326344Simp luaL_error(L, "invalid order function for sorting"); 319326344Simp lua_pop(L, 1); /* remove a[i] */ 320326344Simp } 321326344Simp /* after the loop, a[i] >= P and a[lo .. i - 1] < P */ 322326344Simp /* next loop: repeat --j while P < a[j] */ 323326344Simp while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { 324326344Simp if (j < i) /* j < i but a[j] > P ?? */ 325326344Simp luaL_error(L, "invalid order function for sorting"); 326326344Simp lua_pop(L, 1); /* remove a[j] */ 327326344Simp } 328326344Simp /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ 329326344Simp if (j < i) { /* no elements out of place? */ 330326344Simp /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ 331326344Simp lua_pop(L, 1); /* pop a[j] */ 332326344Simp /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ 333326344Simp set2(L, up - 1, i); 334326344Simp return i; 335326344Simp } 336326344Simp /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ 337326344Simp set2(L, i, j); 338326344Simp } 339326344Simp} 340326344Simp 341326344Simp 342326344Simp/* 343326344Simp** Choose an element in the middle (2nd-3th quarters) of [lo,up] 344326344Simp** "randomized" by 'rnd' 345326344Simp*/ 346326344Simpstatic IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) { 347326344Simp IdxT r4 = (up - lo) / 4; /* range/4 */ 348326344Simp IdxT p = rnd % (r4 * 2) + (lo + r4); 349326344Simp lua_assert(lo + r4 <= p && p <= up - r4); 350326344Simp return p; 351326344Simp} 352326344Simp 353326344Simp 354326344Simp/* 355326344Simp** QuickSort algorithm (recursive function) 356326344Simp*/ 357326344Simpstatic void auxsort (lua_State *L, IdxT lo, IdxT up, 358326344Simp unsigned int rnd) { 359326344Simp while (lo < up) { /* loop for tail recursion */ 360326344Simp IdxT p; /* Pivot index */ 361326344Simp IdxT n; /* to be used later */ 362326344Simp /* sort elements 'lo', 'p', and 'up' */ 363326344Simp lua_geti(L, 1, lo); 364326344Simp lua_geti(L, 1, up); 365326344Simp if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ 366326344Simp set2(L, lo, up); /* swap a[lo] - a[up] */ 367280405Srpaulo else 368326344Simp lua_pop(L, 2); /* remove both values */ 369326344Simp if (up - lo == 1) /* only 2 elements? */ 370326344Simp return; /* already sorted */ 371326344Simp if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */ 372326344Simp p = (lo + up)/2; /* middle element is a good pivot */ 373326344Simp else /* for larger intervals, it is worth a random pivot */ 374326344Simp p = choosePivot(lo, up, rnd); 375326344Simp lua_geti(L, 1, p); 376326344Simp lua_geti(L, 1, lo); 377326344Simp if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ 378326344Simp set2(L, p, lo); /* swap a[p] - a[lo] */ 379280405Srpaulo else { 380326344Simp lua_pop(L, 1); /* remove a[lo] */ 381326344Simp lua_geti(L, 1, up); 382326344Simp if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ 383326344Simp set2(L, p, up); /* swap a[up] - a[p] */ 384280405Srpaulo else 385280405Srpaulo lua_pop(L, 2); 386280405Srpaulo } 387326344Simp if (up - lo == 2) /* only 3 elements? */ 388326344Simp return; /* already sorted */ 389326344Simp lua_geti(L, 1, p); /* get middle element (Pivot) */ 390326344Simp lua_pushvalue(L, -1); /* push Pivot */ 391326344Simp lua_geti(L, 1, up - 1); /* push a[up - 1] */ 392326344Simp set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ 393326344Simp p = partition(L, lo, up); 394326344Simp /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ 395326344Simp if (p - lo < up - p) { /* lower interval is smaller? */ 396326344Simp auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ 397326344Simp n = p - lo; /* size of smaller interval */ 398326344Simp lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ 399280405Srpaulo } 400280405Srpaulo else { 401326344Simp auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ 402326344Simp n = up - p; /* size of smaller interval */ 403326344Simp up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ 404280405Srpaulo } 405326344Simp if ((up - lo) / 128 > n) /* partition too imbalanced? */ 406326344Simp rnd = l_randomizePivot(); /* try a new randomization */ 407326344Simp } /* tail call auxsort(L, lo, up, rnd) */ 408280405Srpaulo} 409280405Srpaulo 410326344Simp 411280405Srpaulostatic int sort (lua_State *L) { 412326344Simp lua_Integer n = aux_getn(L, 1, TAB_RW); 413326344Simp if (n > 1) { /* non-trivial interval? */ 414326344Simp luaL_argcheck(L, n < INT_MAX, 1, "array too big"); 415326344Simp if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ 416326344Simp luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ 417326344Simp lua_settop(L, 2); /* make sure there are two arguments */ 418326344Simp auxsort(L, 1, (IdxT)n, 0); 419326344Simp } 420280405Srpaulo return 0; 421280405Srpaulo} 422280405Srpaulo 423280405Srpaulo/* }====================================================== */ 424280405Srpaulo 425280405Srpaulo 426280405Srpaulostatic const luaL_Reg tab_funcs[] = { 427280405Srpaulo {"concat", tconcat}, 428280405Srpaulo#if defined(LUA_COMPAT_MAXN) 429280405Srpaulo {"maxn", maxn}, 430280405Srpaulo#endif 431280405Srpaulo {"insert", tinsert}, 432280405Srpaulo {"pack", pack}, 433280405Srpaulo {"unpack", unpack}, 434280405Srpaulo {"remove", tremove}, 435280405Srpaulo {"move", tmove}, 436280405Srpaulo {"sort", sort}, 437280405Srpaulo {NULL, NULL} 438280405Srpaulo}; 439280405Srpaulo 440280405Srpaulo 441280405SrpauloLUAMOD_API int luaopen_table (lua_State *L) { 442280405Srpaulo luaL_newlib(L, tab_funcs); 443280405Srpaulo#if defined(LUA_COMPAT_UNPACK) 444280405Srpaulo /* _G.unpack = table.unpack */ 445280405Srpaulo lua_getfield(L, -1, "unpack"); 446280405Srpaulo lua_setglobal(L, "unpack"); 447280405Srpaulo#endif 448280405Srpaulo return 1; 449280405Srpaulo} 450280405Srpaulo 451