aboutsummaryrefslogtreecommitdiff
path: root/ltablib.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2015-11-06 14:07:14 -0200
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2015-11-06 14:07:14 -0200
commit02340375bee903fe68830cf86c2c207db16ada6b (patch)
tree9218360067aaa664e5e6b73b29ffcc14a9bd92d2 /ltablib.c
parent5100bc8aa1c05b1c967567c09d0c70b7c339cc28 (diff)
downloadlua-02340375bee903fe68830cf86c2c207db16ada6b.tar.gz
lua-02340375bee903fe68830cf86c2c207db16ada6b.tar.bz2
lua-02340375bee903fe68830cf86c2c207db16ada6b.zip
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 (limited to 'ltablib.c')
-rw-r--r--ltablib.c130
1 files changed, 76 insertions, 54 deletions
diff --git a/ltablib.c b/ltablib.c
index 10a4a3d2..7dae7049 100644
--- a/ltablib.c
+++ b/ltablib.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltablib.c,v 1.82 2015/09/09 15:42:30 roberto Exp roberto $ 2** $Id: ltablib.c,v 1.83 2015/09/17 15:53:50 roberto Exp roberto $
3** Library for Table Manipulation 3** Library for Table Manipulation
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -12,6 +12,7 @@
12 12
13#include <limits.h> 13#include <limits.h>
14#include <stddef.h> 14#include <stddef.h>
15#include <time.h>
15 16
16#include "lua.h" 17#include "lua.h"
17 18
@@ -253,67 +254,88 @@ static int sort_comp (lua_State *L, int a, int b) {
253 return lua_compare(L, a, b, LUA_OPLT); 254 return lua_compare(L, a, b, LUA_OPLT);
254} 255}
255 256
256static void auxsort (lua_State *L, int l, int u) { 257
257 while (l < u) { /* for tail recursion */ 258/*
258 int i, j; 259** Does the partition: Pivot P is at the top of the stack.
259 /* sort elements a[l], a[(l+u)/2] and a[u] */ 260** precondition: a[lo] <= P == a[up-1] <= a[up],
260 lua_geti(L, 1, l); 261** so it only needs to do the partition from lo + 1 to up - 2.
261 lua_geti(L, 1, u); 262** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up]
262 if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ 263** returns 'i'.
263 set2(L, l, u); /* swap a[l] - a[u] */ 264*/
265static int partition (lua_State *L, int lo, int up) {
266 int i = lo; /* will be incremented before first use */
267 int j = up - 1; /* will be decremented before first use */
268 /* loop invariant: a[lo .. i] <= P <= a[j .. up] */
269 for (;;) {
270 /* next loop: repeat ++i while a[i] < P */
271 while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) {
272 if (i >= up)
273 luaL_error(L, "invalid order function for sorting");
274 lua_pop(L, 1); /* remove a[i] */
275 }
276 /* after the loop, a[i] >= P and a[lo .. i - 1] < P */
277 /* next loop: repeat --j while P < a[j] */
278 while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) {
279 if (j < lo)
280 luaL_error(L, "invalid order function for sorting");
281 lua_pop(L, 1); /* remove a[j] */
282 }
283 /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */
284 if (j < i) { /* no elements out of place? */
285 /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */
286 lua_pop(L, 1); /* pop a[j] */
287 /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */
288 set2(L, up - 1, i);
289 return i;
290 }
291 /* otherwise, swap a[i] - a[j] to restore invariant and repeat */
292 set2(L, i, j);
293 }
294}
295
296
297static void auxsort (lua_State *L, int lo, int up) {
298 while (lo < up) { /* loop for tail recursion */
299 int p;
300 /* sort elements 'lo', '(lo + up)/2' and 'up' */
301 lua_geti(L, 1, lo);
302 lua_geti(L, 1, up);
303 if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */
304 set2(L, lo, up); /* swap a[lo] - a[up] */
264 else 305 else
265 lua_pop(L, 2); 306 lua_pop(L, 2); /* remove both values */
266 if (u-l == 1) break; /* only 2 elements */ 307 if (up - lo == 1) /* only 2 elements? */
267 i = (l+u)/2; 308 return; /* already sorted */
268 lua_geti(L, 1, i); 309 p = (lo + up)/2;
269 lua_geti(L, 1, l); 310 lua_geti(L, 1, p);
270 if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */ 311 lua_geti(L, 1, lo);
271 set2(L, i, l); 312 if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */
313 set2(L, p, lo); /* swap a[p] - a[lo] */
272 else { 314 else {
273 lua_pop(L, 1); /* remove a[l] */ 315 lua_pop(L, 1); /* remove a[lo] */
274 lua_geti(L, 1, u); 316 lua_geti(L, 1, up);
275 if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */ 317 if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */
276 set2(L, i, u); 318 set2(L, p, up); /* swap a[up] - a[p] */
277 else 319 else
278 lua_pop(L, 2); 320 lua_pop(L, 2);
279 } 321 }
280 if (u-l == 2) break; /* only 3 elements */ 322 if (up - lo == 2) /* only 3 elements? */
281 lua_geti(L, 1, i); /* Pivot */ 323 return; /* already sorted */
282 lua_pushvalue(L, -1); 324 lua_geti(L, 1, p); /* get middle element (Pivot) */
283 lua_geti(L, 1, u-1); 325 lua_pushvalue(L, -1); /* push Pivot */
284 set2(L, i, u-1); 326 lua_geti(L, 1, up - 1); /* push a[up - 1] */
285 /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ 327 set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */
286 i = l; j = u-1; 328 p = partition(L, lo, up);
287 for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ 329 /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */
288 /* repeat ++i until a[i] >= P */ 330 if (p - lo < up - p) { /* lower interval is smaller? */
289 while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { 331 auxsort(L, lo, p - 1); /* call recursively for lower interval */
290 if (i>=u) luaL_error(L, "invalid order function for sorting"); 332 lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */
291 lua_pop(L, 1); /* remove a[i] */
292 }
293 /* repeat --j until a[j] <= P */
294 while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) {
295 if (j<=l) luaL_error(L, "invalid order function for sorting");
296 lua_pop(L, 1); /* remove a[j] */
297 }
298 if (j<i) {
299 lua_pop(L, 3); /* pop pivot, a[i], a[j] */
300 break;
301 }
302 set2(L, i, j);
303 }
304 lua_geti(L, 1, u-1);
305 lua_geti(L, 1, i);
306 set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */
307 /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
308 /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
309 if (i-l < u-i) {
310 j=l; i=i-1; l=i+2;
311 } 333 }
312 else { 334 else {
313 j=i+1; i=u; u=j-2; 335 auxsort(L, p + 1, up); /* call recursively for upper interval */
336 up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */
314 } 337 }
315 auxsort(L, j, i); /* call recursively the smaller one */ 338 } /* tail call auxsort(L, lo, up) */
316 } /* repeat the routine for the larger one */
317} 339}
318 340
319static int sort (lua_State *L) { 341static int sort (lua_State *L) {