From bda83e22c0ab3e6fffbf0a71e5e4a5869da8f6ab Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Wed, 9 Sep 2015 12:42:30 -0300 Subject: 'tablib' does not try to use raw operations when possible: fast track should make standard operations fast enough to forgo raw accesses --- ltablib.c | 165 +++++++++++++++++++++++++++++--------------------------------- 1 file changed, 78 insertions(+), 87 deletions(-) (limited to 'ltablib.c') diff --git a/ltablib.c b/ltablib.c index af9bd9c6..a63b5351 100644 --- a/ltablib.c +++ b/ltablib.c @@ -1,5 +1,5 @@ /* -** $Id: ltablib.c,v 1.80 2015/01/13 16:27:29 roberto Exp roberto $ +** $Id: ltablib.c,v 1.81 2015/07/04 16:31:42 roberto Exp roberto $ ** Library for Table Manipulation ** See Copyright Notice in lua.h */ @@ -19,42 +19,44 @@ #include "lualib.h" - /* -** Structure with table-access functions +** Operations that an object must define to mimic a table +** (some functions only need some of them) */ -typedef struct { - int (*geti) (lua_State *L, int idx, lua_Integer n); - void (*seti) (lua_State *L, int idx, lua_Integer n); -} TabA; +#define TAB_R 1 +#define TAB_W 2 +#define TAB_L 4 +#define TAB_RW (TAB_R | TAB_W) + + +#define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n)) + + +static int checkfield (lua_State *L, const char *key, int n) { + lua_pushstring(L, key); + return (lua_rawget(L, -n) != LUA_TNIL); +} /* -** Check that 'arg' has a table and set access functions in 'ta' to raw -** or non-raw according to the presence of corresponding metamethods. +** Check that 'arg' either is a table or can behave like one (that is, +** has a metatable with the required metamethods) */ -static void checktab (lua_State *L, int arg, TabA *ta) { - ta->geti = NULL; ta->seti = NULL; - if (lua_getmetatable(L, arg)) { - lua_pushliteral(L, "__index"); /* 'index' metamethod */ - if (lua_rawget(L, -2) != LUA_TNIL) - ta->geti = lua_geti; - lua_pushliteral(L, "__newindex"); /* 'newindex' metamethod */ - if (lua_rawget(L, -3) != LUA_TNIL) - ta->seti = lua_seti; - lua_pop(L, 3); /* pop metatable plus both metamethods */ - } - if (ta->geti == NULL || ta->seti == NULL) { - luaL_checktype(L, arg, LUA_TTABLE); /* must be table for raw methods */ - if (ta->geti == NULL) ta->geti = lua_rawgeti; - if (ta->seti == NULL) ta->seti = lua_rawseti; +static void checktab (lua_State *L, int arg, int what) { + if (lua_type(L, arg) != LUA_TTABLE) { /* is it not a table? */ + int n = 1; /* number of elements to pop */ + if (lua_getmetatable(L, arg) && /* must have metatable */ + (!(what & TAB_R) || checkfield(L, "__index", ++n)) && + (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) && + (!(what & TAB_L) || checkfield(L, "__len", ++n))) { + lua_pop(L, n); /* pop metatable and tested metamethods */ +} + else + luaL_argerror(L, arg, "table expected"); /* force an error */ } } -#define aux_getn(L,n,ta) (checktab(L, n, ta), luaL_len(L, n)) - - #if defined(LUA_COMPAT_MAXN) static int maxn (lua_State *L) { lua_Number max = 0; @@ -74,8 +76,7 @@ static int maxn (lua_State *L) { static int tinsert (lua_State *L) { - TabA ta; - lua_Integer e = aux_getn(L, 1, &ta) + 1; /* first empty element */ + lua_Integer e = aux_getn(L, 1, TAB_RW) + 1; /* first empty element */ lua_Integer pos; /* where to insert new element */ switch (lua_gettop(L)) { case 2: { /* called with only 2 arguments */ @@ -87,8 +88,8 @@ static int tinsert (lua_State *L) { pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */ luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds"); for (i = e; i > pos; i--) { /* move up elements */ - (*ta.geti)(L, 1, i - 1); - (*ta.seti)(L, 1, i); /* t[i] = t[i - 1] */ + lua_geti(L, 1, i - 1); + lua_seti(L, 1, i); /* t[i] = t[i - 1] */ } break; } @@ -96,42 +97,36 @@ static int tinsert (lua_State *L) { return luaL_error(L, "wrong number of arguments to 'insert'"); } } - (*ta.seti)(L, 1, pos); /* t[pos] = v */ + lua_seti(L, 1, pos); /* t[pos] = v */ return 0; } static int tremove (lua_State *L) { - TabA ta; - lua_Integer size = aux_getn(L, 1, &ta); + lua_Integer size = aux_getn(L, 1, TAB_RW); lua_Integer pos = luaL_optinteger(L, 2, size); if (pos != size) /* validate 'pos' if given */ luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds"); - (*ta.geti)(L, 1, pos); /* result = t[pos] */ + lua_geti(L, 1, pos); /* result = t[pos] */ for ( ; pos < size; pos++) { - (*ta.geti)(L, 1, pos + 1); - (*ta.seti)(L, 1, pos); /* t[pos] = t[pos + 1] */ + lua_geti(L, 1, pos + 1); + lua_seti(L, 1, pos); /* t[pos] = t[pos + 1] */ } lua_pushnil(L); - (*ta.seti)(L, 1, pos); /* t[pos] = nil */ + lua_seti(L, 1, pos); /* t[pos] = nil */ return 1; } static int tmove (lua_State *L) { - TabA ta; lua_Integer f = luaL_checkinteger(L, 2); lua_Integer e = luaL_checkinteger(L, 3); lua_Integer t = luaL_checkinteger(L, 4); int tt = !lua_isnoneornil(L, 5) ? 5 : 1; /* destination table */ + checktab(L, 1, TAB_R); + checktab(L, tt, TAB_W); if (e >= f) { /* otherwise, nothing to move */ lua_Integer n, i; - ta.geti = (luaL_getmetafield(L, 1, "__index") == LUA_TNIL) - ? (luaL_checktype(L, 1, LUA_TTABLE), lua_rawgeti) - : lua_geti; - ta.seti = (luaL_getmetafield(L, tt, "__newindex") == LUA_TNIL) - ? (luaL_checktype(L, tt, LUA_TTABLE), lua_rawseti) - : lua_seti; luaL_argcheck(L, f > 0 || e < LUA_MAXINTEGER + f, 3, "too many elements to move"); n = e - f + 1; /* number of elements to move */ @@ -139,14 +134,14 @@ static int tmove (lua_State *L) { "destination wrap around"); if (t > f) { for (i = n - 1; i >= 0; i--) { - (*ta.geti)(L, 1, f + i); - (*ta.seti)(L, tt, t + i); + lua_geti(L, 1, f + i); + lua_seti(L, tt, t + i); } } else { for (i = 0; i < n; i++) { - (*ta.geti)(L, 1, f + i); - (*ta.seti)(L, tt, t + i); + lua_geti(L, 1, f + i); + lua_seti(L, tt, t + i); } } } @@ -155,8 +150,8 @@ static int tmove (lua_State *L) { } -static void addfield (lua_State *L, luaL_Buffer *b, TabA *ta, lua_Integer i) { - (*ta->geti)(L, 1, i); +static void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) { + lua_geti(L, 1, i); if (!lua_isstring(L, -1)) luaL_error(L, "invalid value (%s) at index %d in table for 'concat'", luaL_typename(L, -1), i); @@ -165,21 +160,20 @@ static void addfield (lua_State *L, luaL_Buffer *b, TabA *ta, lua_Integer i) { static int tconcat (lua_State *L) { - TabA ta; luaL_Buffer b; size_t lsep; - lua_Integer i, last; + lua_Integer i; + lua_Integer last = aux_getn(L, 1, TAB_R); const char *sep = luaL_optlstring(L, 2, "", &lsep); - checktab(L, 1, &ta); i = luaL_optinteger(L, 3, 1); - last = luaL_opt(L, luaL_checkinteger, 4, luaL_len(L, 1)); + last = luaL_opt(L, luaL_checkinteger, 4, last); luaL_buffinit(L, &b); for (; i < last; i++) { - addfield(L, &b, &ta, i); + addfield(L, &b, i); luaL_addlstring(&b, sep, lsep); } if (i == last) /* add last value (if interval was not empty) */ - addfield(L, &b, &ta, i); + addfield(L, &b, i); luaL_pushresult(&b); return 1; } @@ -197,7 +191,7 @@ static int pack (lua_State *L) { lua_createtable(L, n, 1); /* create result table */ lua_insert(L, 1); /* put it at index 1 */ for (i = n; i >= 1; i--) /* assign elements */ - lua_rawseti(L, 1, i); + lua_seti(L, 1, i); lua_pushinteger(L, n); lua_setfield(L, 1, "n"); /* t.n = number of elements */ return 1; /* return table */ @@ -205,10 +199,8 @@ static int pack (lua_State *L) { static int unpack (lua_State *L) { - TabA ta; lua_Integer i, e; lua_Unsigned n; - checktab(L, 1, &ta); i = luaL_optinteger(L, 2, 1); e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); if (i > e) return 0; /* empty range */ @@ -216,9 +208,9 @@ static int unpack (lua_State *L) { if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, (int)(++n))) return luaL_error(L, "too many results to unpack"); for (; i < e; i++) { /* push arg[i..e - 1] (to avoid overflows) */ - (*ta.geti)(L, 1, i); + lua_geti(L, 1, i); } - (*ta.geti)(L, 1, e); /* push last element */ + lua_geti(L, 1, e); /* push last element */ return (int)n; } @@ -235,9 +227,9 @@ static int unpack (lua_State *L) { */ -static void set2 (lua_State *L, TabA *ta, int i, int j) { - (*ta->seti)(L, 1, i); - (*ta->seti)(L, 1, j); +static void set2 (lua_State *L, int i, int j) { + lua_seti(L, 1, i); + lua_seti(L, 1, j); } static int sort_comp (lua_State *L, int a, int b) { @@ -255,45 +247,45 @@ static int sort_comp (lua_State *L, int a, int b) { return lua_compare(L, a, b, LUA_OPLT); } -static void auxsort (lua_State *L, TabA *ta, int l, int u) { +static void auxsort (lua_State *L, int l, int u) { while (l < u) { /* for tail recursion */ int i, j; /* sort elements a[l], a[(l+u)/2] and a[u] */ - (*ta->geti)(L, 1, l); - (*ta->geti)(L, 1, u); + lua_geti(L, 1, l); + lua_geti(L, 1, u); if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ - set2(L, ta, l, u); /* swap a[l] - a[u] */ + set2(L, l, u); /* swap a[l] - a[u] */ else lua_pop(L, 2); if (u-l == 1) break; /* only 2 elements */ i = (l+u)/2; - (*ta->geti)(L, 1, i); - (*ta->geti)(L, 1, l); + lua_geti(L, 1, i); + lua_geti(L, 1, l); if (sort_comp(L, -2, -1)) /* a[i]geti)(L, 1, u); + lua_geti(L, 1, u); if (sort_comp(L, -1, -2)) /* a[u]geti)(L, 1, i); /* Pivot */ + lua_geti(L, 1, i); /* Pivot */ lua_pushvalue(L, -1); - (*ta->geti)(L, 1, u-1); - set2(L, ta, i, u-1); + lua_geti(L, 1, u-1); + set2(L, i, u-1); /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ i = l; j = u-1; for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ /* repeat ++i until a[i] >= P */ - while ((*ta->geti)(L, 1, ++i), sort_comp(L, -1, -2)) { + while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { if (i>=u) luaL_error(L, "invalid order function for sorting"); lua_pop(L, 1); /* remove a[i] */ } /* repeat --j until a[j] <= P */ - while ((*ta->geti)(L, 1, --j), sort_comp(L, -3, -1)) { + while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { if (j<=l) luaL_error(L, "invalid order function for sorting"); lua_pop(L, 1); /* remove a[j] */ } @@ -301,11 +293,11 @@ static void auxsort (lua_State *L, TabA *ta, int l, int u) { lua_pop(L, 3); /* pop pivot, a[i], a[j] */ break; } - set2(L, ta, i, j); + set2(L, i, j); } - (*ta->geti)(L, 1, u-1); - (*ta->geti)(L, 1, i); - set2(L, ta, u-1, i); /* swap pivot (a[u-1]) with a[i] */ + lua_geti(L, 1, u-1); + lua_geti(L, 1, i); + set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */ /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ /* adjust so that smaller half is in [j..i] and larger one in [l..u] */ if (i-l < u-i) { @@ -314,18 +306,17 @@ static void auxsort (lua_State *L, TabA *ta, int l, int u) { else { j=i+1; i=u; u=j-2; } - auxsort(L, ta, j, i); /* call recursively the smaller one */ + auxsort(L, j, i); /* call recursively the smaller one */ } /* repeat the routine for the larger one */ } static int sort (lua_State *L) { - TabA ta; - int n = (int)aux_getn(L, 1, &ta); + int n = (int)aux_getn(L, 1, TAB_RW); luaL_checkstack(L, 50, ""); /* assume array is smaller than 2^50 */ if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ luaL_checktype(L, 2, LUA_TFUNCTION); lua_settop(L, 2); /* make sure there are two arguments */ - auxsort(L, &ta, 1, n); + auxsort(L, 1, n); return 0; } -- cgit v1.2.3-55-g6feb