1 /* 2 ** $Id: ltablib.c $ 3 ** Library for Table Manipulation 4 ** See Copyright Notice in lua.h 5 */ 6 7 #define ltablib_c 8 #define LUA_LIB 9 10 #include "lprefix.h" 11 12 13 #include <limits.h> 14 #include <stddef.h> 15 #include <string.h> 16 17 #include "lua.h" 18 19 #include "lauxlib.h" 20 #include "lualib.h" 21 22 23 /* 24 ** Operations that an object must define to mimic a table 25 ** (some functions only need some of them) 26 */ 27 #define TAB_R 1 /* read */ 28 #define TAB_W 2 /* write */ 29 #define TAB_L 4 /* length */ 30 #define TAB_RW (TAB_R | TAB_W) /* read/write */ 31 32 33 #define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n)) 34 35 36 static int checkfield (lua_State *L, const char *key, int n) { 37 lua_pushstring(L, key); 38 return (lua_rawget(L, -n) != LUA_TNIL); 39 } 40 41 42 /* 43 ** Check that 'arg' either is a table or can behave like one (that is, 44 ** has a metatable with the required metamethods) 45 */ 46 static void checktab (lua_State *L, int arg, int what) { 47 if (lua_type(L, arg) != LUA_TTABLE) { /* is it not a table? */ 48 int n = 1; /* number of elements to pop */ 49 if (lua_getmetatable(L, arg) && /* must have metatable */ 50 (!(what & TAB_R) || checkfield(L, "__index", ++n)) && 51 (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) && 52 (!(what & TAB_L) || checkfield(L, "__len", ++n))) { 53 lua_pop(L, n); /* pop metatable and tested metamethods */ 54 } 55 else 56 luaL_checktype(L, arg, LUA_TTABLE); /* force an error */ 57 } 58 } 59 60 61 static int tinsert (lua_State *L) { 62 lua_Integer pos; /* where to insert new element */ 63 lua_Integer e = aux_getn(L, 1, TAB_RW); 64 e = luaL_intop(+, e, 1); /* first empty element */ 65 switch (lua_gettop(L)) { 66 case 2: { /* called with only 2 arguments */ 67 pos = e; /* insert new element at the end */ 68 break; 69 } 70 case 3: { 71 lua_Integer i; 72 pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */ 73 /* check whether 'pos' is in [1, e] */ 74 luaL_argcheck(L, (lua_Unsigned)pos - 1u < (lua_Unsigned)e, 2, 75 "position out of bounds"); 76 for (i = e; i > pos; i--) { /* move up elements */ 77 lua_geti(L, 1, i - 1); 78 lua_seti(L, 1, i); /* t[i] = t[i - 1] */ 79 } 80 break; 81 } 82 default: { 83 return luaL_error(L, "wrong number of arguments to 'insert'"); 84 } 85 } 86 lua_seti(L, 1, pos); /* t[pos] = v */ 87 return 0; 88 } 89 90 91 static int tremove (lua_State *L) { 92 lua_Integer size = aux_getn(L, 1, TAB_RW); 93 lua_Integer pos = luaL_optinteger(L, 2, size); 94 if (pos != size) /* validate 'pos' if given */ 95 /* check whether 'pos' is in [1, size + 1] */ 96 luaL_argcheck(L, (lua_Unsigned)pos - 1u <= (lua_Unsigned)size, 2, 97 "position out of bounds"); 98 lua_geti(L, 1, pos); /* result = t[pos] */ 99 for ( ; pos < size; pos++) { 100 lua_geti(L, 1, pos + 1); 101 lua_seti(L, 1, pos); /* t[pos] = t[pos + 1] */ 102 } 103 lua_pushnil(L); 104 lua_seti(L, 1, pos); /* remove entry t[pos] */ 105 return 1; 106 } 107 108 109 /* 110 ** Copy elements (1[f], ..., 1[e]) into (tt[t], tt[t+1], ...). Whenever 111 ** possible, copy in increasing order, which is better for rehashing. 112 ** "possible" means destination after original range, or smaller 113 ** than origin, or copying to another table. 114 */ 115 static int tmove (lua_State *L) { 116 lua_Integer f = luaL_checkinteger(L, 2); 117 lua_Integer e = luaL_checkinteger(L, 3); 118 lua_Integer t = luaL_checkinteger(L, 4); 119 int tt = !lua_isnoneornil(L, 5) ? 5 : 1; /* destination table */ 120 checktab(L, 1, TAB_R); 121 checktab(L, tt, TAB_W); 122 if (e >= f) { /* otherwise, nothing to move */ 123 lua_Integer n, i; 124 luaL_argcheck(L, f > 0 || e < LUA_MAXINTEGER + f, 3, 125 "too many elements to move"); 126 n = e - f + 1; /* number of elements to move */ 127 luaL_argcheck(L, t <= LUA_MAXINTEGER - n + 1, 4, 128 "destination wrap around"); 129 if (t > e || t <= f || (tt != 1 && !lua_compare(L, 1, tt, LUA_OPEQ))) { 130 for (i = 0; i < n; i++) { 131 lua_geti(L, 1, f + i); 132 lua_seti(L, tt, t + i); 133 } 134 } 135 else { 136 for (i = n - 1; i >= 0; i--) { 137 lua_geti(L, 1, f + i); 138 lua_seti(L, tt, t + i); 139 } 140 } 141 } 142 lua_pushvalue(L, tt); /* return destination table */ 143 return 1; 144 } 145 146 147 static void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) { 148 lua_geti(L, 1, i); 149 if (l_unlikely(!lua_isstring(L, -1))) 150 luaL_error(L, "invalid value (%s) at index %I in table for 'concat'", 151 luaL_typename(L, -1), (LUAI_UACINT)i); 152 luaL_addvalue(b); 153 } 154 155 156 static int tconcat (lua_State *L) { 157 luaL_Buffer b; 158 lua_Integer last = aux_getn(L, 1, TAB_R); 159 size_t lsep; 160 const char *sep = luaL_optlstring(L, 2, "", &lsep); 161 lua_Integer i = luaL_optinteger(L, 3, 1); 162 last = luaL_optinteger(L, 4, last); 163 luaL_buffinit(L, &b); 164 for (; i < last; i++) { 165 addfield(L, &b, i); 166 luaL_addlstring(&b, sep, lsep); 167 } 168 if (i == last) /* add last value (if interval was not empty) */ 169 addfield(L, &b, i); 170 luaL_pushresult(&b); 171 return 1; 172 } 173 174 175 /* 176 ** {====================================================== 177 ** Pack/unpack 178 ** ======================================================= 179 */ 180 181 static int tpack (lua_State *L) { 182 int i; 183 int n = lua_gettop(L); /* number of elements to pack */ 184 lua_createtable(L, n, 1); /* create result table */ 185 lua_insert(L, 1); /* put it at index 1 */ 186 for (i = n; i >= 1; i--) /* assign elements */ 187 lua_seti(L, 1, i); 188 lua_pushinteger(L, n); 189 lua_setfield(L, 1, "n"); /* t.n = number of elements */ 190 return 1; /* return table */ 191 } 192 193 194 static int tunpack (lua_State *L) { 195 lua_Unsigned n; 196 lua_Integer i = luaL_optinteger(L, 2, 1); 197 lua_Integer e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); 198 if (i > e) return 0; /* empty range */ 199 n = (lua_Unsigned)e - i; /* number of elements minus 1 (avoid overflows) */ 200 if (l_unlikely(n >= (unsigned int)INT_MAX || 201 !lua_checkstack(L, (int)(++n)))) 202 return luaL_error(L, "too many results to unpack"); 203 for (; i < e; i++) { /* push arg[i..e - 1] (to avoid overflows) */ 204 lua_geti(L, 1, i); 205 } 206 lua_geti(L, 1, e); /* push last element */ 207 return (int)n; 208 } 209 210 /* }====================================================== */ 211 212 213 214 /* 215 ** {====================================================== 216 ** Quicksort 217 ** (based on 'Algorithms in MODULA-3', Robert Sedgewick; 218 ** Addison-Wesley, 1993.) 219 ** ======================================================= 220 */ 221 222 223 /* type for array indices */ 224 typedef unsigned int IdxT; 225 226 227 /* 228 ** Produce a "random" 'unsigned int' to randomize pivot choice. This 229 ** macro is used only when 'sort' detects a big imbalance in the result 230 ** of a partition. (If you don't want/need this "randomness", ~0 is a 231 ** good choice.) 232 */ 233 #if !defined(l_randomizePivot) /* { */ 234 235 #include <time.h> 236 237 /* size of 'e' measured in number of 'unsigned int's */ 238 #define sof(e) (sizeof(e) / sizeof(unsigned int)) 239 240 /* 241 ** Use 'time' and 'clock' as sources of "randomness". Because we don't 242 ** know the types 'clock_t' and 'time_t', we cannot cast them to 243 ** anything without risking overflows. A safe way to use their values 244 ** is to copy them to an array of a known type and use the array values. 245 */ 246 static unsigned int l_randomizePivot (void) { 247 clock_t c = clock(); 248 time_t t = time(NULL); 249 unsigned int buff[sof(c) + sof(t)]; 250 unsigned int i, rnd = 0; 251 memcpy(buff, &c, sof(c) * sizeof(unsigned int)); 252 memcpy(buff + sof(c), &t, sof(t) * sizeof(unsigned int)); 253 for (i = 0; i < sof(buff); i++) 254 rnd += buff[i]; 255 return rnd; 256 } 257 258 #endif /* } */ 259 260 261 /* arrays larger than 'RANLIMIT' may use randomized pivots */ 262 #define RANLIMIT 100u 263 264 265 static void set2 (lua_State *L, IdxT i, IdxT j) { 266 lua_seti(L, 1, i); 267 lua_seti(L, 1, j); 268 } 269 270 271 /* 272 ** Return true iff value at stack index 'a' is less than the value at 273 ** index 'b' (according to the order of the sort). 274 */ 275 static int sort_comp (lua_State *L, int a, int b) { 276 if (lua_isnil(L, 2)) /* no function? */ 277 return lua_compare(L, a, b, LUA_OPLT); /* a < b */ 278 else { /* function */ 279 int res; 280 lua_pushvalue(L, 2); /* push function */ 281 lua_pushvalue(L, a-1); /* -1 to compensate function */ 282 lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ 283 lua_call(L, 2, 1); /* call function */ 284 res = lua_toboolean(L, -1); /* get result */ 285 lua_pop(L, 1); /* pop result */ 286 return res; 287 } 288 } 289 290 291 /* 292 ** Does the partition: Pivot P is at the top of the stack. 293 ** precondition: a[lo] <= P == a[up-1] <= a[up], 294 ** so it only needs to do the partition from lo + 1 to up - 2. 295 ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] 296 ** returns 'i'. 297 */ 298 static IdxT partition (lua_State *L, IdxT lo, IdxT up) { 299 IdxT i = lo; /* will be incremented before first use */ 300 IdxT j = up - 1; /* will be decremented before first use */ 301 /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ 302 for (;;) { 303 /* next loop: repeat ++i while a[i] < P */ 304 while ((void)lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { 305 if (l_unlikely(i == up - 1)) /* a[i] < P but a[up - 1] == P ?? */ 306 luaL_error(L, "invalid order function for sorting"); 307 lua_pop(L, 1); /* remove a[i] */ 308 } 309 /* after the loop, a[i] >= P and a[lo .. i - 1] < P */ 310 /* next loop: repeat --j while P < a[j] */ 311 while ((void)lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { 312 if (l_unlikely(j < i)) /* j < i but a[j] > P ?? */ 313 luaL_error(L, "invalid order function for sorting"); 314 lua_pop(L, 1); /* remove a[j] */ 315 } 316 /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ 317 if (j < i) { /* no elements out of place? */ 318 /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ 319 lua_pop(L, 1); /* pop a[j] */ 320 /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ 321 set2(L, up - 1, i); 322 return i; 323 } 324 /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ 325 set2(L, i, j); 326 } 327 } 328 329 330 /* 331 ** Choose an element in the middle (2nd-3th quarters) of [lo,up] 332 ** "randomized" by 'rnd' 333 */ 334 static IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) { 335 IdxT r4 = (up - lo) / 4; /* range/4 */ 336 IdxT p = rnd % (r4 * 2) + (lo + r4); 337 lua_assert(lo + r4 <= p && p <= up - r4); 338 return p; 339 } 340 341 342 /* 343 ** Quicksort algorithm (recursive function) 344 */ 345 static void auxsort (lua_State *L, IdxT lo, IdxT up, 346 unsigned int rnd) { 347 while (lo < up) { /* loop for tail recursion */ 348 IdxT p; /* Pivot index */ 349 IdxT n; /* to be used later */ 350 /* sort elements 'lo', 'p', and 'up' */ 351 lua_geti(L, 1, lo); 352 lua_geti(L, 1, up); 353 if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ 354 set2(L, lo, up); /* swap a[lo] - a[up] */ 355 else 356 lua_pop(L, 2); /* remove both values */ 357 if (up - lo == 1) /* only 2 elements? */ 358 return; /* already sorted */ 359 if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */ 360 p = (lo + up)/2; /* middle element is a good pivot */ 361 else /* for larger intervals, it is worth a random pivot */ 362 p = choosePivot(lo, up, rnd); 363 lua_geti(L, 1, p); 364 lua_geti(L, 1, lo); 365 if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ 366 set2(L, p, lo); /* swap a[p] - a[lo] */ 367 else { 368 lua_pop(L, 1); /* remove a[lo] */ 369 lua_geti(L, 1, up); 370 if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ 371 set2(L, p, up); /* swap a[up] - a[p] */ 372 else 373 lua_pop(L, 2); 374 } 375 if (up - lo == 2) /* only 3 elements? */ 376 return; /* already sorted */ 377 lua_geti(L, 1, p); /* get middle element (Pivot) */ 378 lua_pushvalue(L, -1); /* push Pivot */ 379 lua_geti(L, 1, up - 1); /* push a[up - 1] */ 380 set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ 381 p = partition(L, lo, up); 382 /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ 383 if (p - lo < up - p) { /* lower interval is smaller? */ 384 auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ 385 n = p - lo; /* size of smaller interval */ 386 lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ 387 } 388 else { 389 auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ 390 n = up - p; /* size of smaller interval */ 391 up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ 392 } 393 if ((up - lo) / 128 > n) /* partition too imbalanced? */ 394 rnd = l_randomizePivot(); /* try a new randomization */ 395 } /* tail call auxsort(L, lo, up, rnd) */ 396 } 397 398 399 static int sort (lua_State *L) { 400 lua_Integer n = aux_getn(L, 1, TAB_RW); 401 if (n > 1) { /* non-trivial interval? */ 402 luaL_argcheck(L, n < INT_MAX, 1, "array too big"); 403 if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ 404 luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ 405 lua_settop(L, 2); /* make sure there are two arguments */ 406 auxsort(L, 1, (IdxT)n, 0); 407 } 408 return 0; 409 } 410 411 /* }====================================================== */ 412 413 414 static const luaL_Reg tab_funcs[] = { 415 {"concat", tconcat}, 416 {"insert", tinsert}, 417 {"pack", tpack}, 418 {"unpack", tunpack}, 419 {"remove", tremove}, 420 {"move", tmove}, 421 {"sort", sort}, 422 {NULL, NULL} 423 }; 424 425 426 LUAMOD_API int luaopen_table (lua_State *L) { 427 luaL_newlib(L, tab_funcs); 428 return 1; 429 } 430 431