1dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com/* 2dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** $Id: ltablib.c,v 1.65 2013/03/07 18:17:24 roberto Exp $ 3dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** Library for Table Manipulation 4dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** See Copyright Notice in lua.h 5dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com*/ 6dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 7dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 8dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#include <stddef.h> 9dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 10dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#define ltablib_c 11dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#define LUA_LIB 12dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 13dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#include "lua.h" 14dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 15dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#include "lauxlib.h" 16dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#include "lualib.h" 17dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 18dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 19dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#define aux_getn(L,n) (luaL_checktype(L, n, LUA_TTABLE), luaL_len(L, n)) 20dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 21dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 22dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 23dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#if defined(LUA_COMPAT_MAXN) 24dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic int maxn (lua_State *L) { 25dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_Number max = 0; 26dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_checktype(L, 1, LUA_TTABLE); 27dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushnil(L); /* first key */ 28dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com while (lua_next(L, 1)) { 29dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pop(L, 1); /* remove value */ 30dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (lua_type(L, -1) == LUA_TNUMBER) { 31dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_Number v = lua_tonumber(L, -1); 32dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (v > max) max = v; 33dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 34dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 35dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushnumber(L, max); 36dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return 1; 37dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 38dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#endif 39dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 40dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 41dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic int tinsert (lua_State *L) { 42dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int e = aux_getn(L, 1) + 1; /* first empty element */ 43dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int pos; /* where to insert new element */ 44dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com switch (lua_gettop(L)) { 45dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com case 2: { /* called with only 2 arguments */ 46dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com pos = e; /* insert new element at the end */ 47dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com break; 48dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 49dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com case 3: { 50dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int i; 51dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com pos = luaL_checkint(L, 2); /* 2nd argument is the position */ 52dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds"); 53dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com for (i = e; i > pos; i--) { /* move up elements */ 54dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, i-1); 55dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawseti(L, 1, i); /* t[i] = t[i-1] */ 56dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 57dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com break; 58dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 59dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com default: { 60dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return luaL_error(L, "wrong number of arguments to " LUA_QL("insert")); 61dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 62dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 63dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawseti(L, 1, pos); /* t[pos] = v */ 64dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return 0; 65dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 66dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 67dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 68dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic int tremove (lua_State *L) { 69dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int size = aux_getn(L, 1); 70dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int pos = luaL_optint(L, 2, size); 71dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (pos != size) /* validate 'pos' if given */ 72dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds"); 73dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, pos); /* result = t[pos] */ 74dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com for ( ; pos < size; pos++) { 75dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, pos+1); 76dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawseti(L, 1, pos); /* t[pos] = t[pos+1] */ 77dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 78dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushnil(L); 79dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawseti(L, 1, pos); /* t[pos] = nil */ 80dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return 1; 81dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 82dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 83dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 84dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic void addfield (lua_State *L, luaL_Buffer *b, int i) { 85dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, i); 86dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (!lua_isstring(L, -1)) 87dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_error(L, "invalid value (%s) at index %d in table for " 88dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com LUA_QL("concat"), luaL_typename(L, -1), i); 89dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_addvalue(b); 90dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 91dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 92dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 93dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic int tconcat (lua_State *L) { 94dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_Buffer b; 95dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com size_t lsep; 96dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int i, last; 97dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com const char *sep = luaL_optlstring(L, 2, "", &lsep); 98dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_checktype(L, 1, LUA_TTABLE); 99dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com i = luaL_optint(L, 3, 1); 100dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com last = luaL_opt(L, luaL_checkint, 4, luaL_len(L, 1)); 101dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_buffinit(L, &b); 102dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com for (; i < last; i++) { 103dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com addfield(L, &b, i); 104dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_addlstring(&b, sep, lsep); 105dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 106dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (i == last) /* add last value (if interval was not empty) */ 107dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com addfield(L, &b, i); 108dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_pushresult(&b); 109dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return 1; 110dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 111dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 112dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 113dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com/* 114dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** {====================================================== 115dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** Pack/unpack 116dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** ======================================================= 117dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com*/ 118dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 119dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic int pack (lua_State *L) { 120dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int n = lua_gettop(L); /* number of elements to pack */ 121dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_createtable(L, n, 1); /* create result table */ 122dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushinteger(L, n); 123dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_setfield(L, -2, "n"); /* t.n = number of elements */ 124dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (n > 0) { /* at least one element? */ 125dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int i; 126dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushvalue(L, 1); 127dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawseti(L, -2, 1); /* insert first element */ 128dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_replace(L, 1); /* move table into index 1 */ 129dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com for (i = n; i >= 2; i--) /* assign other elements */ 130dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawseti(L, 1, i); 131dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 132dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return 1; /* return table */ 133dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 134dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 135dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 136dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic int unpack (lua_State *L) { 137dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int i, e, n; 138dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_checktype(L, 1, LUA_TTABLE); 139dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com i = luaL_optint(L, 2, 1); 140dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com e = luaL_opt(L, luaL_checkint, 3, luaL_len(L, 1)); 141dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (i > e) return 0; /* empty range */ 142dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com n = e - i + 1; /* number of elements */ 143dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (n <= 0 || !lua_checkstack(L, n)) /* n <= 0 means arith. overflow */ 144dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return luaL_error(L, "too many results to unpack"); 145dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, i); /* push arg[i] (avoiding overflow problems) */ 146dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com while (i++ < e) /* push arg[i + 1...e] */ 147dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, i); 148dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return n; 149dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 150dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 151dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com/* }====================================================== */ 152dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 153dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 154dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 155dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com/* 156dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** {====================================================== 157dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** Quicksort 158dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** (based on `Algorithms in MODULA-3', Robert Sedgewick; 159dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** Addison-Wesley, 1993.) 160dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com** ======================================================= 161dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com*/ 162dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 163dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 164dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic void set2 (lua_State *L, int i, int j) { 165dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawseti(L, 1, i); 166dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawseti(L, 1, j); 167dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 168dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 169dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic int sort_comp (lua_State *L, int a, int b) { 170dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (!lua_isnil(L, 2)) { /* function? */ 171dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int res; 172dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushvalue(L, 2); 173dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushvalue(L, a-1); /* -1 to compensate function */ 174dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushvalue(L, b-2); /* -2 to compensate function and `a' */ 175dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_call(L, 2, 1); 176dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com res = lua_toboolean(L, -1); 177dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pop(L, 1); 178dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return res; 179dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 180dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com else /* a < b? */ 181dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return lua_compare(L, a, b, LUA_OPLT); 182dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 183dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 184dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic void auxsort (lua_State *L, int l, int u) { 185dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com while (l < u) { /* for tail recursion */ 186dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int i, j; 187dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com /* sort elements a[l], a[(l+u)/2] and a[u] */ 188dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, l); 189dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, u); 190dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ 191dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com set2(L, l, u); /* swap a[l] - a[u] */ 192dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com else 193dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pop(L, 2); 194dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (u-l == 1) break; /* only 2 elements */ 195dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com i = (l+u)/2; 196dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, i); 197dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, l); 198dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */ 199dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com set2(L, i, l); 200dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com else { 201dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pop(L, 1); /* remove a[l] */ 202dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, u); 203dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */ 204dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com set2(L, i, u); 205dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com else 206dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pop(L, 2); 207dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 208dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (u-l == 2) break; /* only 3 elements */ 209dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, i); /* Pivot */ 210dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pushvalue(L, -1); 211dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, u-1); 212dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com set2(L, i, u-1); 213dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ 214dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com i = l; j = u-1; 215dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ 216dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com /* repeat ++i until a[i] >= P */ 217dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) { 218dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (i>=u) luaL_error(L, "invalid order function for sorting"); 219dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pop(L, 1); /* remove a[i] */ 220dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 221dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com /* repeat --j until a[j] <= P */ 222dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) { 223dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (j<=l) luaL_error(L, "invalid order function for sorting"); 224dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pop(L, 1); /* remove a[j] */ 225dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 226dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (j<i) { 227dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_pop(L, 3); /* pop pivot, a[i], a[j] */ 228dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com break; 229dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 230dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com set2(L, i, j); 231dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 232dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, u-1); 233dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_rawgeti(L, 1, i); 234dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */ 235dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ 236dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com /* adjust so that smaller half is in [j..i] and larger one in [l..u] */ 237dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (i-l < u-i) { 238dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com j=l; i=i-1; l=i+2; 239dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 240dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com else { 241dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com j=i+1; i=u; u=j-2; 242dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } 243dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com auxsort(L, j, i); /* call recursively the smaller one */ 244dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com } /* repeat the routine for the larger one */ 245dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 246dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 247dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic int sort (lua_State *L) { 248dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com int n = aux_getn(L, 1); 249dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */ 250dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ 251dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_checktype(L, 2, LUA_TFUNCTION); 252dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_settop(L, 2); /* make sure there is two arguments */ 253dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com auxsort(L, 1, n); 254dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return 0; 255dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 256dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 257dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com/* }====================================================== */ 258dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 259dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 260dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comstatic const luaL_Reg tab_funcs[] = { 261dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com {"concat", tconcat}, 262dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#if defined(LUA_COMPAT_MAXN) 263dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com {"maxn", maxn}, 264dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#endif 265dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com {"insert", tinsert}, 266dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com {"pack", pack}, 267dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com {"unpack", unpack}, 268dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com {"remove", tremove}, 269dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com {"sort", sort}, 270dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com {NULL, NULL} 271dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com}; 272dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 273dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 274dff7e11c2000d6745261de046d76b1500a05ece9reed@google.comLUAMOD_API int luaopen_table (lua_State *L) { 275dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com luaL_newlib(L, tab_funcs); 276dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#if defined(LUA_COMPAT_UNPACK) 277dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com /* _G.unpack = table.unpack */ 278dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_getfield(L, -1, "unpack"); 279dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com lua_setglobal(L, "unpack"); 280dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com#endif 281dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com return 1; 282dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com} 283dff7e11c2000d6745261de046d76b1500a05ece9reed@google.com 284