ltablib.c revision 344220
1178354Ssam/* 2178354Ssam** $Id: ltablib.c,v 1.93.1.1 2017/04/19 17:20:42 roberto Exp $ 3178354Ssam** Library for Table Manipulation 4178354Ssam** See Copyright Notice in lua.h 5178354Ssam*/ 6178354Ssam 7178354Ssam#define ltablib_c 8178354Ssam#define LUA_LIB 9178354Ssam 10178354Ssam#include "lprefix.h" 11178354Ssam 12178354Ssam 13178354Ssam#include <limits.h> 14178354Ssam#include <stddef.h> 15178354Ssam#include <string.h> 16178354Ssam 17178354Ssam#include "lua.h" 18178354Ssam 19178354Ssam#include "lauxlib.h" 20178354Ssam#include "lualib.h" 21178354Ssam 22178354Ssam 23178354Ssam/* 24178354Ssam** Operations that an object must define to mimic a table 25178354Ssam** (some functions only need some of them) 26178354Ssam*/ 27178354Ssam#define TAB_R 1 /* read */ 28178354Ssam#define TAB_W 2 /* write */ 29178354Ssam#define TAB_L 4 /* length */ 30178354Ssam#define TAB_RW (TAB_R | TAB_W) /* read/write */ 31178354Ssam 32178354Ssam 33178354Ssam#define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n)) 34178354Ssam 35178354Ssam 36178354Ssamstatic int checkfield (lua_State *L, const char *key, int n) { 37178354Ssam lua_pushstring(L, key); 38178354Ssam return (lua_rawget(L, -n) != LUA_TNIL); 39178354Ssam} 40178354Ssam 41178354Ssam 42178354Ssam/* 43178354Ssam** Check that 'arg' either is a table or can behave like one (that is, 44178354Ssam** has a metatable with the required metamethods) 45178354Ssam*/ 46178354Ssamstatic void checktab (lua_State *L, int arg, int what) { 47178354Ssam if (lua_type(L, arg) != LUA_TTABLE) { /* is it not a table? */ 48178354Ssam int n = 1; /* number of elements to pop */ 49178354Ssam if (lua_getmetatable(L, arg) && /* must have metatable */ 50178354Ssam (!(what & TAB_R) || checkfield(L, "__index", ++n)) && 51178354Ssam (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) && 52178354Ssam (!(what & TAB_L) || checkfield(L, "__len", ++n))) { 53178354Ssam lua_pop(L, n); /* pop metatable and tested metamethods */ 54178354Ssam } 55178354Ssam else 56178354Ssam luaL_checktype(L, arg, LUA_TTABLE); /* force an error */ 57178354Ssam } 58178354Ssam} 59178354Ssam 60190391Ssam 61190391Ssam#if defined(LUA_COMPAT_MAXN) 62190391Ssamstatic int maxn (lua_State *L) { 63178354Ssam lua_Number max = 0; 64178354Ssam luaL_checktype(L, 1, LUA_TTABLE); 65178354Ssam lua_pushnil(L); /* first key */ 66178354Ssam while (lua_next(L, 1)) { 67178354Ssam lua_pop(L, 1); /* remove value */ 68178354Ssam if (lua_type(L, -1) == LUA_TNUMBER) { 69178354Ssam lua_Number v = lua_tonumber(L, -1); 70178354Ssam if (v > max) max = v; 71178354Ssam } 72178354Ssam } 73191546Ssam lua_pushnumber(L, max); 74178354Ssam return 1; 75178354Ssam} 76178354Ssam#endif 77178354Ssam 78178354Ssam 79178354Ssamstatic int tinsert (lua_State *L) { 80178354Ssam lua_Integer e = aux_getn(L, 1, TAB_RW) + 1; /* first empty element */ 81178354Ssam lua_Integer pos; /* where to insert new element */ 82178354Ssam switch (lua_gettop(L)) { 83178354Ssam case 2: { /* called with only 2 arguments */ 84178354Ssam pos = e; /* insert new element at the end */ 85178354Ssam break; 86178354Ssam } 87178354Ssam case 3: { 88178354Ssam lua_Integer i; 89178354Ssam pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */ 90178354Ssam luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds"); 91178354Ssam for (i = e; i > pos; i--) { /* move up elements */ 92178354Ssam lua_geti(L, 1, i - 1); 93178354Ssam lua_seti(L, 1, i); /* t[i] = t[i - 1] */ 94178354Ssam } 95178354Ssam break; 96178354Ssam } 97191546Ssam default: { 98178354Ssam return luaL_error(L, "wrong number of arguments to 'insert'"); 99178354Ssam } 100178354Ssam } 101178354Ssam lua_seti(L, 1, pos); /* t[pos] = v */ 102178354Ssam return 0; 103178354Ssam} 104178354Ssam 105178354Ssam 106178354Ssamstatic int tremove (lua_State *L) { 107178354Ssam lua_Integer size = aux_getn(L, 1, TAB_RW); 108178354Ssam lua_Integer pos = luaL_optinteger(L, 2, size); 109178354Ssam if (pos != size) /* validate 'pos' if given */ 110190402Ssam luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds"); 111178354Ssam lua_geti(L, 1, pos); /* result = t[pos] */ 112178354Ssam for ( ; pos < size; pos++) { 113178354Ssam lua_geti(L, 1, pos + 1); 114178354Ssam lua_seti(L, 1, pos); /* t[pos] = t[pos + 1] */ 115178354Ssam } 116178354Ssam lua_pushnil(L); 117178354Ssam lua_seti(L, 1, pos); /* t[pos] = nil */ 118178354Ssam return 1; 119178354Ssam} 120178354Ssam 121178354Ssam 122178354Ssam/* 123178354Ssam** Copy elements (1[f], ..., 1[e]) into (tt[t], tt[t+1], ...). Whenever 124178354Ssam** possible, copy in increasing order, which is better for rehashing. 125178354Ssam** "possible" means destination after original range, or smaller 126178354Ssam** than origin, or copying to another table. 127178354Ssam*/ 128178354Ssamstatic int tmove (lua_State *L) { 129178354Ssam lua_Integer f = luaL_checkinteger(L, 2); 130178354Ssam lua_Integer e = luaL_checkinteger(L, 3); 131178354Ssam lua_Integer t = luaL_checkinteger(L, 4); 132178354Ssam int tt = !lua_isnoneornil(L, 5) ? 5 : 1; /* destination table */ 133178354Ssam checktab(L, 1, TAB_R); 134178354Ssam checktab(L, tt, TAB_W); 135190391Ssam if (e >= f) { /* otherwise, nothing to move */ 136190402Ssam lua_Integer n, i; 137190402Ssam luaL_argcheck(L, f > 0 || e < LUA_MAXINTEGER + f, 3, 138178354Ssam "too many elements to move"); 139178354Ssam n = e - f + 1; /* number of elements to move */ 140178354Ssam luaL_argcheck(L, t <= LUA_MAXINTEGER - n + 1, 4, 141178354Ssam "destination wrap around"); 142178354Ssam if (t > e || t <= f || (tt != 1 && !lua_compare(L, 1, tt, LUA_OPEQ))) { 143178354Ssam for (i = 0; i < n; i++) { 144178354Ssam lua_geti(L, 1, f + i); 145178354Ssam lua_seti(L, tt, t + i); 146190391Ssam } 147178354Ssam } 148178354Ssam else { 149178354Ssam for (i = n - 1; i >= 0; i--) { 150178354Ssam lua_geti(L, 1, f + i); 151178354Ssam lua_seti(L, tt, t + i); 152178354Ssam } 153178354Ssam } 154178354Ssam } 155178354Ssam lua_pushvalue(L, tt); /* return destination table */ 156178354Ssam return 1; 157178354Ssam} 158178354Ssam 159178354Ssam 160178354Ssamstatic void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) { 161178354Ssam lua_geti(L, 1, i); 162178354Ssam if (!lua_isstring(L, -1)) 163178354Ssam luaL_error(L, "invalid value (%s) at index %d in table for 'concat'", 164178354Ssam luaL_typename(L, -1), i); 165178354Ssam luaL_addvalue(b); 166178354Ssam} 167178354Ssam 168178354Ssam 169178354Ssamstatic int tconcat (lua_State *L) { 170178354Ssam luaL_Buffer b; 171178354Ssam lua_Integer last = aux_getn(L, 1, TAB_R); 172178354Ssam size_t lsep; 173178354Ssam const char *sep = luaL_optlstring(L, 2, "", &lsep); 174178354Ssam lua_Integer i = luaL_optinteger(L, 3, 1); 175178354Ssam last = luaL_optinteger(L, 4, last); 176178354Ssam luaL_buffinit(L, &b); 177178354Ssam for (; i < last; i++) { 178178354Ssam addfield(L, &b, i); 179178354Ssam luaL_addlstring(&b, sep, lsep); 180178354Ssam } 181178354Ssam if (i == last) /* add last value (if interval was not empty) */ 182178354Ssam addfield(L, &b, i); 183178354Ssam luaL_pushresult(&b); 184178354Ssam return 1; 185178354Ssam} 186178354Ssam 187178354Ssam 188178354Ssam/* 189178354Ssam** {====================================================== 190178354Ssam** Pack/unpack 191178354Ssam** ======================================================= 192178354Ssam*/ 193178354Ssam 194178354Ssamstatic int pack (lua_State *L) { 195178354Ssam int i; 196178354Ssam int n = lua_gettop(L); /* number of elements to pack */ 197178354Ssam lua_createtable(L, n, 1); /* create result table */ 198178354Ssam lua_insert(L, 1); /* put it at index 1 */ 199178354Ssam for (i = n; i >= 1; i--) /* assign elements */ 200178354Ssam lua_seti(L, 1, i); 201178354Ssam lua_pushinteger(L, n); 202178354Ssam lua_setfield(L, 1, "n"); /* t.n = number of elements */ 203178354Ssam return 1; /* return table */ 204178354Ssam} 205178354Ssam 206178354Ssam 207178354Ssamstatic int unpack (lua_State *L) { 208178354Ssam lua_Unsigned n; 209178354Ssam lua_Integer i = luaL_optinteger(L, 2, 1); 210178354Ssam lua_Integer e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); 211178354Ssam if (i > e) return 0; /* empty range */ 212178354Ssam n = (lua_Unsigned)e - i; /* number of elements minus 1 (avoid overflows) */ 213178354Ssam if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, (int)(++n))) 214178354Ssam return luaL_error(L, "too many results to unpack"); 215178354Ssam for (; i < e; i++) { /* push arg[i..e - 1] (to avoid overflows) */ 216178354Ssam lua_geti(L, 1, i); 217178354Ssam } 218178354Ssam lua_geti(L, 1, e); /* push last element */ 219178354Ssam return (int)n; 220178354Ssam} 221178354Ssam 222178354Ssam/* }====================================================== */ 223178354Ssam 224178354Ssam 225178354Ssam 226178354Ssam/* 227178354Ssam** {====================================================== 228178354Ssam** Quicksort 229178354Ssam** (based on 'Algorithms in MODULA-3', Robert Sedgewick; 230178354Ssam** Addison-Wesley, 1993.) 231178354Ssam** ======================================================= 232178354Ssam*/ 233178354Ssam 234178354Ssam 235178354Ssam/* type for array indices */ 236178354Ssamtypedef unsigned int IdxT; 237178354Ssam 238178354Ssam 239178354Ssam/* 240178354Ssam** Produce a "random" 'unsigned int' to randomize pivot choice. This 241178354Ssam** macro is used only when 'sort' detects a big imbalance in the result 242178354Ssam** of a partition. (If you don't want/need this "randomness", ~0 is a 243178354Ssam** good choice.) 244178354Ssam*/ 245178354Ssam#if !defined(l_randomizePivot) /* { */ 246178354Ssam 247178354Ssam#include <time.h> 248178354Ssam 249178354Ssam/* size of 'e' measured in number of 'unsigned int's */ 250178354Ssam#define sof(e) (sizeof(e) / sizeof(unsigned int)) 251178354Ssam 252178354Ssam/* 253178354Ssam** Use 'time' and 'clock' as sources of "randomness". Because we don't 254178354Ssam** know the types 'clock_t' and 'time_t', we cannot cast them to 255178354Ssam** anything without risking overflows. A safe way to use their values 256178354Ssam** is to copy them to an array of a known type and use the array values. 257178354Ssam*/ 258178354Ssamstatic unsigned int l_randomizePivot (void) { 259178354Ssam clock_t c = clock(); 260178354Ssam time_t t = time(NULL); 261178354Ssam unsigned int buff[sof(c) + sof(t)]; 262178354Ssam unsigned int i, rnd = 0; 263178354Ssam memcpy(buff, &c, sof(c) * sizeof(unsigned int)); 264178354Ssam memcpy(buff + sof(c), &t, sof(t) * sizeof(unsigned int)); 265178354Ssam for (i = 0; i < sof(buff); i++) 266178354Ssam rnd += buff[i]; 267178354Ssam return rnd; 268178354Ssam} 269178354Ssam 270178354Ssam#endif /* } */ 271178354Ssam 272178354Ssam 273178354Ssam/* arrays larger than 'RANLIMIT' may use randomized pivots */ 274178354Ssam#define RANLIMIT 100u 275178354Ssam 276178354Ssam 277178354Ssamstatic void set2 (lua_State *L, IdxT i, IdxT j) { 278178354Ssam lua_seti(L, 1, i); 279178354Ssam lua_seti(L, 1, j); 280178354Ssam} 281178354Ssam 282178354Ssam 283178354Ssam/* 284178354Ssam** Return true iff value at stack index 'a' is less than the value at 285178354Ssam** index 'b' (according to the order of the sort). 286178354Ssam*/ 287178354Ssamstatic int sort_comp (lua_State *L, int a, int b) { 288178354Ssam if (lua_isnil(L, 2)) /* no function? */ 289178354Ssam return lua_compare(L, a, b, LUA_OPLT); /* a < b */ 290178354Ssam else { /* function */ 291178354Ssam int res; 292178354Ssam lua_pushvalue(L, 2); /* push function */ 293178354Ssam lua_pushvalue(L, a-1); /* -1 to compensate function */ 294178354Ssam lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ 295178354Ssam lua_call(L, 2, 1); /* call function */ 296178354Ssam res = lua_toboolean(L, -1); /* get result */ 297178354Ssam lua_pop(L, 1); /* pop result */ 298178354Ssam return res; 299178354Ssam } 300178354Ssam} 301178354Ssam 302178354Ssam 303178354Ssam/* 304178354Ssam** Does the partition: Pivot P is at the top of the stack. 305178354Ssam** precondition: a[lo] <= P == a[up-1] <= a[up], 306178354Ssam** so it only needs to do the partition from lo + 1 to up - 2. 307178354Ssam** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] 308178354Ssam** returns 'i'. 309178354Ssam*/ 310178354Ssamstatic IdxT partition (lua_State *L, IdxT lo, IdxT up) { 311178354Ssam IdxT i = lo; /* will be incremented before first use */ 312178354Ssam IdxT j = up - 1; /* will be decremented before first use */ 313178354Ssam /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ 314178354Ssam for (;;) { 315178354Ssam /* next loop: repeat ++i while a[i] < P */ 316178354Ssam while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { 317178354Ssam if (i == up - 1) /* a[i] < P but a[up - 1] == P ?? */ 318178354Ssam luaL_error(L, "invalid order function for sorting"); 319178354Ssam lua_pop(L, 1); /* remove a[i] */ 320178354Ssam } 321178354Ssam /* after the loop, a[i] >= P and a[lo .. i - 1] < P */ 322178354Ssam /* next loop: repeat --j while P < a[j] */ 323178354Ssam while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { 324178354Ssam if (j < i) /* j < i but a[j] > P ?? */ 325178354Ssam luaL_error(L, "invalid order function for sorting"); 326178354Ssam lua_pop(L, 1); /* remove a[j] */ 327178354Ssam } 328178354Ssam /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ 329178354Ssam if (j < i) { /* no elements out of place? */ 330178354Ssam /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ 331178354Ssam lua_pop(L, 1); /* pop a[j] */ 332178354Ssam /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ 333178354Ssam set2(L, up - 1, i); 334178354Ssam return i; 335178354Ssam } 336178354Ssam /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ 337178354Ssam set2(L, i, j); 338178354Ssam } 339178354Ssam} 340178354Ssam 341178354Ssam 342178354Ssam/* 343178354Ssam** Choose an element in the middle (2nd-3th quarters) of [lo,up] 344178354Ssam** "randomized" by 'rnd' 345178354Ssam*/ 346178354Ssamstatic IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) { 347178354Ssam IdxT r4 = (up - lo) / 4; /* range/4 */ 348178354Ssam IdxT p = rnd % (r4 * 2) + (lo + r4); 349178354Ssam lua_assert(lo + r4 <= p && p <= up - r4); 350178354Ssam return p; 351178354Ssam} 352178354Ssam 353178354Ssam 354178354Ssam/* 355178354Ssam** QuickSort algorithm (recursive function) 356178354Ssam*/ 357178354Ssamstatic void auxsort (lua_State *L, IdxT lo, IdxT up, 358178354Ssam unsigned int rnd) { 359178354Ssam while (lo < up) { /* loop for tail recursion */ 360178354Ssam IdxT p; /* Pivot index */ 361178354Ssam IdxT n; /* to be used later */ 362178354Ssam /* sort elements 'lo', 'p', and 'up' */ 363178354Ssam lua_geti(L, 1, lo); 364178354Ssam lua_geti(L, 1, up); 365178354Ssam if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ 366178354Ssam set2(L, lo, up); /* swap a[lo] - a[up] */ 367178354Ssam else 368178354Ssam lua_pop(L, 2); /* remove both values */ 369178354Ssam if (up - lo == 1) /* only 2 elements? */ 370178354Ssam return; /* already sorted */ 371178354Ssam if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */ 372178354Ssam p = (lo + up)/2; /* middle element is a good pivot */ 373178354Ssam else /* for larger intervals, it is worth a random pivot */ 374178354Ssam p = choosePivot(lo, up, rnd); 375178354Ssam lua_geti(L, 1, p); 376178354Ssam lua_geti(L, 1, lo); 377178354Ssam if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ 378178354Ssam set2(L, p, lo); /* swap a[p] - a[lo] */ 379178354Ssam else { 380178354Ssam lua_pop(L, 1); /* remove a[lo] */ 381178354Ssam lua_geti(L, 1, up); 382178354Ssam if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ 383178354Ssam set2(L, p, up); /* swap a[up] - a[p] */ 384178354Ssam else 385178354Ssam lua_pop(L, 2); 386178354Ssam } 387178354Ssam if (up - lo == 2) /* only 3 elements? */ 388178354Ssam return; /* already sorted */ 389178354Ssam lua_geti(L, 1, p); /* get middle element (Pivot) */ 390178354Ssam lua_pushvalue(L, -1); /* push Pivot */ 391178354Ssam lua_geti(L, 1, up - 1); /* push a[up - 1] */ 392178354Ssam set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ 393178354Ssam p = partition(L, lo, up); 394178354Ssam /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ 395178354Ssam if (p - lo < up - p) { /* lower interval is smaller? */ 396178354Ssam auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ 397178354Ssam n = p - lo; /* size of smaller interval */ 398178354Ssam lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ 399178354Ssam } 400178354Ssam else { 401178354Ssam auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ 402178354Ssam n = up - p; /* size of smaller interval */ 403178354Ssam up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ 404178354Ssam } 405178354Ssam if ((up - lo) / 128 > n) /* partition too imbalanced? */ 406178354Ssam rnd = l_randomizePivot(); /* try a new randomization */ 407178354Ssam } /* tail call auxsort(L, lo, up, rnd) */ 408178354Ssam} 409178354Ssam 410184345Ssam 411184345Ssamstatic int sort (lua_State *L) { 412184345Ssam lua_Integer n = aux_getn(L, 1, TAB_RW); 413184345Ssam if (n > 1) { /* non-trivial interval? */ 414184345Ssam luaL_argcheck(L, n < INT_MAX, 1, "array too big"); 415178354Ssam if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ 416178354Ssam luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ 417178354Ssam lua_settop(L, 2); /* make sure there are two arguments */ 418178354Ssam auxsort(L, 1, (IdxT)n, 0); 419178354Ssam } 420178354Ssam return 0; 421184268Ssam} 422184268Ssam 423178354Ssam/* }====================================================== */ 424178354Ssam 425178354Ssam 426178354Ssamstatic const luaL_Reg tab_funcs[] = { 427178354Ssam {"concat", tconcat}, 428178354Ssam#if defined(LUA_COMPAT_MAXN) 429178354Ssam {"maxn", maxn}, 430178354Ssam#endif 431178354Ssam {"insert", tinsert}, 432178354Ssam {"pack", pack}, 433178354Ssam {"unpack", unpack}, 434178354Ssam {"remove", tremove}, 435178354Ssam {"move", tmove}, 436178354Ssam {"sort", sort}, 437178354Ssam {NULL, NULL} 438178354Ssam}; 439178354Ssam 440178354Ssam 441178354SsamLUAMOD_API int luaopen_table (lua_State *L) { 442178354Ssam luaL_newlib(L, tab_funcs); 443178354Ssam#if defined(LUA_COMPAT_UNPACK) 444178354Ssam /* _G.unpack = table.unpack */ 445178354Ssam lua_getfield(L, -1, "unpack"); 446178354Ssam lua_setglobal(L, "unpack"); 447178354Ssam#endif 448178354Ssam return 1; 449178354Ssam} 450178354Ssam 451178354Ssam