lua

A copy of the Lua development repository
Log | Files | Refs | README

commit 02340375bee903fe68830cf86c2c207db16ada6b
parent 5100bc8aa1c05b1c967567c09d0c70b7c339cc28
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date:   Fri,  6 Nov 2015 14:06:48 -0200

janitor work on 'table.sort': added comments, partition code moved
to a separated function, code conventions updated, etc. No changes
at all in the logic/algorithm

Diffstat:
Mltablib.c | 130++++++++++++++++++++++++++++++++++++++++++++++---------------------------------
1 file changed, 76 insertions(+), 54 deletions(-)

diff --git a/ltablib.c b/ltablib.c @@ -1,5 +1,5 @@ /* -** $Id: ltablib.c,v 1.82 2015/09/09 15:42:30 roberto Exp roberto $ +** $Id: ltablib.c,v 1.83 2015/09/17 15:53:50 roberto Exp roberto $ ** Library for Table Manipulation ** See Copyright Notice in lua.h */ @@ -12,6 +12,7 @@ #include <limits.h> #include <stddef.h> +#include <time.h> #include "lua.h" @@ -253,67 +254,88 @@ 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, int l, int u) { - while (l < u) { /* for tail recursion */ - int i, j; - /* sort elements a[l], a[(l+u)/2] and a[u] */ - lua_geti(L, 1, l); - lua_geti(L, 1, u); - if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ - set2(L, l, u); /* swap a[l] - a[u] */ + +/* +** Does the partition: Pivot P is at the top of the stack. +** precondition: a[lo] <= P == a[up-1] <= a[up], +** so it only needs to do the partition from lo + 1 to up - 2. +** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] +** returns 'i'. +*/ +static int partition (lua_State *L, int lo, int up) { + int i = lo; /* will be incremented before first use */ + int j = up - 1; /* will be decremented before first use */ + /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ + for (;;) { + /* next loop: repeat ++i while a[i] < P */ + while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { + if (i >= up) + luaL_error(L, "invalid order function for sorting"); + lua_pop(L, 1); /* remove a[i] */ + } + /* after the loop, a[i] >= P and a[lo .. i - 1] < P */ + /* next loop: repeat --j while P < a[j] */ + while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { + if (j < lo) + luaL_error(L, "invalid order function for sorting"); + lua_pop(L, 1); /* remove a[j] */ + } + /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ + if (j < i) { /* no elements out of place? */ + /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ + lua_pop(L, 1); /* pop a[j] */ + /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ + set2(L, up - 1, i); + return i; + } + /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ + set2(L, i, j); + } +} + + +static void auxsort (lua_State *L, int lo, int up) { + while (lo < up) { /* loop for tail recursion */ + int p; + /* sort elements 'lo', '(lo + up)/2' and 'up' */ + lua_geti(L, 1, lo); + lua_geti(L, 1, up); + if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ + set2(L, lo, up); /* swap a[lo] - a[up] */ else - lua_pop(L, 2); - if (u-l == 1) break; /* only 2 elements */ - i = (l+u)/2; - lua_geti(L, 1, i); - lua_geti(L, 1, l); - if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */ - set2(L, i, l); + lua_pop(L, 2); /* remove both values */ + if (up - lo == 1) /* only 2 elements? */ + return; /* already sorted */ + p = (lo + up)/2; + lua_geti(L, 1, p); + lua_geti(L, 1, lo); + if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ + set2(L, p, lo); /* swap a[p] - a[lo] */ else { - lua_pop(L, 1); /* remove a[l] */ - lua_geti(L, 1, u); - if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */ - set2(L, i, u); + lua_pop(L, 1); /* remove a[lo] */ + lua_geti(L, 1, up); + if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ + set2(L, p, up); /* swap a[up] - a[p] */ else lua_pop(L, 2); } - if (u-l == 2) break; /* only 3 elements */ - lua_geti(L, 1, i); /* Pivot */ - lua_pushvalue(L, -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 (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 (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] */ - } - if (j<i) { - lua_pop(L, 3); /* pop pivot, a[i], a[j] */ - break; - } - set2(L, i, j); - } - 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) { - j=l; i=i-1; l=i+2; + if (up - lo == 2) /* only 3 elements? */ + return; /* already sorted */ + lua_geti(L, 1, p); /* get middle element (Pivot) */ + lua_pushvalue(L, -1); /* push Pivot */ + lua_geti(L, 1, up - 1); /* push a[up - 1] */ + set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ + p = partition(L, lo, up); + /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ + if (p - lo < up - p) { /* lower interval is smaller? */ + auxsort(L, lo, p - 1); /* call recursively for lower interval */ + lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ } else { - j=i+1; i=u; u=j-2; + auxsort(L, p + 1, up); /* call recursively for upper interval */ + up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ } - auxsort(L, j, i); /* call recursively the smaller one */ - } /* repeat the routine for the larger one */ + } /* tail call auxsort(L, lo, up) */ } static int sort (lua_State *L) {