diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-12-14 09:57:38 -0200 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-12-14 09:57:38 -0200 |
commit | e3839416526b41c1d3f859a79760f8ff22794293 (patch) | |
tree | 75b72484646fc7babd041db529331c7a61591af8 /ltablib.c | |
parent | 656b3cea1b6071f30099cef27788a8616a162b7a (diff) | |
download | lua-e3839416526b41c1d3f859a79760f8ff22794293.tar.gz lua-e3839416526b41c1d3f859a79760f8ff22794293.tar.bz2 lua-e3839416526b41c1d3f859a79760f8ff22794293.zip |
in 'table.sort': 'typedef' for type of indices + removed stack check
(recursion is in the C stack, not in the Lua stack!)
Diffstat (limited to 'ltablib.c')
-rw-r--r-- | ltablib.c | 33 |
1 files changed, 17 insertions, 16 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: ltablib.c,v 1.89 2015/11/24 16:54:32 roberto Exp roberto $ | 2 | ** $Id: ltablib.c,v 1.90 2015/11/25 12:48:57 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 | */ |
@@ -232,6 +232,10 @@ static int unpack (lua_State *L) { | |||
232 | */ | 232 | */ |
233 | 233 | ||
234 | 234 | ||
235 | /* type for array indices */ | ||
236 | typedef unsigned int IdxT; | ||
237 | |||
238 | |||
235 | /* | 239 | /* |
236 | ** Produce a "random" 'unsigned int' to randomize pivot choice. This | 240 | ** Produce a "random" 'unsigned int' to randomize pivot choice. This |
237 | ** macro is used only when 'sort' detects a big imbalance in the result | 241 | ** macro is used only when 'sort' detects a big imbalance in the result |
@@ -270,7 +274,7 @@ static unsigned int l_randomizePivot (void) { | |||
270 | #define RANLIMIT 100u | 274 | #define RANLIMIT 100u |
271 | 275 | ||
272 | 276 | ||
273 | static void set2 (lua_State *L, unsigned int i, unsigned int j) { | 277 | static void set2 (lua_State *L, IdxT i, IdxT j) { |
274 | lua_seti(L, 1, i); | 278 | lua_seti(L, 1, i); |
275 | lua_seti(L, 1, j); | 279 | lua_seti(L, 1, j); |
276 | } | 280 | } |
@@ -303,10 +307,9 @@ static int sort_comp (lua_State *L, int a, int b) { | |||
303 | ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] | 307 | ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] |
304 | ** returns 'i'. | 308 | ** returns 'i'. |
305 | */ | 309 | */ |
306 | static unsigned int partition (lua_State *L, unsigned int lo, | 310 | static IdxT partition (lua_State *L, IdxT lo, IdxT up) { |
307 | unsigned int up) { | 311 | IdxT i = lo; /* will be incremented before first use */ |
308 | unsigned int i = lo; /* will be incremented before first use */ | 312 | IdxT j = up - 1; /* will be decremented before first use */ |
309 | unsigned int j = up - 1; /* will be decremented before first use */ | ||
310 | /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ | 313 | /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ |
311 | for (;;) { | 314 | for (;;) { |
312 | /* next loop: repeat ++i while a[i] < P */ | 315 | /* next loop: repeat ++i while a[i] < P */ |
@@ -340,10 +343,9 @@ static unsigned int partition (lua_State *L, unsigned int lo, | |||
340 | ** Choose an element in the middle (2nd-3th quarters) of [lo,up] | 343 | ** Choose an element in the middle (2nd-3th quarters) of [lo,up] |
341 | ** "randomized" by 'rnd' | 344 | ** "randomized" by 'rnd' |
342 | */ | 345 | */ |
343 | static unsigned int choosePivot (unsigned int lo, unsigned int up, | 346 | static IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) { |
344 | unsigned int rnd) { | 347 | IdxT r4 = (up - lo) / 4; /* range/4 */ |
345 | unsigned int r4 = (unsigned int)(up - lo) / 4u; /* range/4 */ | 348 | IdxT p = rnd % (r4 * 2) + (lo + r4); |
346 | unsigned int p = rnd % (r4 * 2) + (lo + r4); | ||
347 | lua_assert(lo + r4 <= p && p <= up - r4); | 349 | lua_assert(lo + r4 <= p && p <= up - r4); |
348 | return p; | 350 | return p; |
349 | } | 351 | } |
@@ -352,11 +354,11 @@ static unsigned int choosePivot (unsigned int lo, unsigned int up, | |||
352 | /* | 354 | /* |
353 | ** QuickSort algorithm (recursive function) | 355 | ** QuickSort algorithm (recursive function) |
354 | */ | 356 | */ |
355 | static void auxsort (lua_State *L, unsigned int lo, unsigned int up, | 357 | static void auxsort (lua_State *L, IdxT lo, IdxT up, |
356 | unsigned int rnd) { | 358 | unsigned int rnd) { |
357 | while (lo < up) { /* loop for tail recursion */ | 359 | while (lo < up) { /* loop for tail recursion */ |
358 | unsigned int p; /* Pivot index */ | 360 | IdxT p; /* Pivot index */ |
359 | unsigned int n; /* to be used later */ | 361 | IdxT n; /* to be used later */ |
360 | /* sort elements 'lo', 'p', and 'up' */ | 362 | /* sort elements 'lo', 'p', and 'up' */ |
361 | lua_geti(L, 1, lo); | 363 | lua_geti(L, 1, lo); |
362 | lua_geti(L, 1, up); | 364 | lua_geti(L, 1, up); |
@@ -400,7 +402,7 @@ static void auxsort (lua_State *L, unsigned int lo, unsigned int up, | |||
400 | n = up - p; /* size of smaller interval */ | 402 | n = up - p; /* size of smaller interval */ |
401 | up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ | 403 | up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ |
402 | } | 404 | } |
403 | if ((up - lo) / 128u > n) /* partition too imbalanced? */ | 405 | if ((up - lo) / 128 > n) /* partition too imbalanced? */ |
404 | rnd = l_randomizePivot(); /* try a new randomization */ | 406 | rnd = l_randomizePivot(); /* try a new randomization */ |
405 | } /* tail call auxsort(L, lo, up, rnd) */ | 407 | } /* tail call auxsort(L, lo, up, rnd) */ |
406 | } | 408 | } |
@@ -410,11 +412,10 @@ static int sort (lua_State *L) { | |||
410 | lua_Integer n = aux_getn(L, 1, TAB_RW); | 412 | lua_Integer n = aux_getn(L, 1, TAB_RW); |
411 | if (n > 1) { /* non-trivial interval? */ | 413 | if (n > 1) { /* non-trivial interval? */ |
412 | luaL_argcheck(L, n < INT_MAX, 1, "array too big"); | 414 | luaL_argcheck(L, n < INT_MAX, 1, "array too big"); |
413 | luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */ | ||
414 | if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ | 415 | if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ |
415 | luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ | 416 | luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ |
416 | lua_settop(L, 2); /* make sure there are two arguments */ | 417 | lua_settop(L, 2); /* make sure there are two arguments */ |
417 | auxsort(L, 1, (unsigned int)n, 0u); | 418 | auxsort(L, 1, (IdxT)n, 0); |
418 | } | 419 | } |
419 | return 0; | 420 | return 0; |
420 | } | 421 | } |