diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-11-20 10:30:20 -0200 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-11-20 10:30:20 -0200 |
commit | 146508b28e942fbfed5eedc6965857be558e9c57 (patch) | |
tree | 60c8cd90f4754ba3a40f84bb81340aa5023a55ca /ltablib.c | |
parent | d103312661d4d2428516924658154df09b3168a4 (diff) | |
download | lua-146508b28e942fbfed5eedc6965857be558e9c57.tar.gz lua-146508b28e942fbfed5eedc6965857be558e9c57.tar.bz2 lua-146508b28e942fbfed5eedc6965857be558e9c57.zip |
randomness in pivot for 'table.sort' done by a macro (easier to change)
Diffstat (limited to 'ltablib.c')
-rw-r--r-- | ltablib.c | 28 |
1 files changed, 17 insertions, 11 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: ltablib.c,v 1.84 2015/11/06 16:07:14 roberto Exp roberto $ | 2 | ** $Id: ltablib.c,v 1.85 2015/11/12 18:07:25 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,7 +12,6 @@ | |||
12 | 12 | ||
13 | #include <limits.h> | 13 | #include <limits.h> |
14 | #include <stddef.h> | 14 | #include <stddef.h> |
15 | #include <time.h> | ||
16 | 15 | ||
17 | #include "lua.h" | 16 | #include "lua.h" |
18 | 17 | ||
@@ -24,10 +23,10 @@ | |||
24 | ** Operations that an object must define to mimic a table | 23 | ** Operations that an object must define to mimic a table |
25 | ** (some functions only need some of them) | 24 | ** (some functions only need some of them) |
26 | */ | 25 | */ |
27 | #define TAB_R 1 | 26 | #define TAB_R 1 /* read */ |
28 | #define TAB_W 2 | 27 | #define TAB_W 2 /* write */ |
29 | #define TAB_L 4 | 28 | #define TAB_L 4 /* length */ |
30 | #define TAB_RW (TAB_R | TAB_W) | 29 | #define TAB_RW (TAB_R | TAB_W) /* read/write */ |
31 | 30 | ||
32 | 31 | ||
33 | #define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n)) | 32 | #define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n)) |
@@ -51,7 +50,7 @@ static void checktab (lua_State *L, int arg, int what) { | |||
51 | (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) && | 50 | (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) && |
52 | (!(what & TAB_L) || checkfield(L, "__len", ++n))) { | 51 | (!(what & TAB_L) || checkfield(L, "__len", ++n))) { |
53 | lua_pop(L, n); /* pop metatable and tested metamethods */ | 52 | lua_pop(L, n); /* pop metatable and tested metamethods */ |
54 | } | 53 | } |
55 | else | 54 | else |
56 | luaL_argerror(L, arg, "table expected"); /* force an error */ | 55 | luaL_argerror(L, arg, "table expected"); /* force an error */ |
57 | } | 56 | } |
@@ -295,8 +294,12 @@ static int partition (lua_State *L, int lo, int up) { | |||
295 | 294 | ||
296 | /* | 295 | /* |
297 | ** Choose a "random" pivot in the middle part of the interval [lo, up]. | 296 | ** Choose a "random" pivot in the middle part of the interval [lo, up]. |
298 | ** Use 'time' and 'clock' as sources of "randomness". | 297 | ** (If you don't want/need this "randomness", (lo+up)/2 is an excelent |
298 | ** choice.) | ||
299 | */ | 299 | */ |
300 | #if !defined(l_sortpivot) | ||
301 | /* Use 'time' and 'clock' as sources of "randomness" */ | ||
302 | #include <time.h> | ||
300 | static int choosePivot (int lo, int up) { | 303 | static int choosePivot (int lo, int up) { |
301 | unsigned int t = (unsigned int)(unsigned long)time(NULL); /* time */ | 304 | unsigned int t = (unsigned int)(unsigned long)time(NULL); /* time */ |
302 | unsigned int c = (unsigned int)(unsigned long)clock(); /* clock */ | 305 | unsigned int c = (unsigned int)(unsigned long)clock(); /* clock */ |
@@ -306,11 +309,14 @@ static int choosePivot (int lo, int up) { | |||
306 | return (int)p; | 309 | return (int)p; |
307 | } | 310 | } |
308 | 311 | ||
312 | #define l_sortpivot(lo,up) choosePivot(lo,up) | ||
313 | #endif | ||
314 | |||
309 | 315 | ||
310 | static void auxsort (lua_State *L, int lo, int up) { | 316 | static void auxsort (lua_State *L, int lo, int up) { |
311 | while (lo < up) { /* loop for tail recursion */ | 317 | while (lo < up) { /* loop for tail recursion */ |
312 | int p; | 318 | int p; /* Pivot index */ |
313 | /* sort elements 'lo', '(lo + up)/2' and 'up' */ | 319 | /* sort elements 'lo', 'p', and 'up' */ |
314 | lua_geti(L, 1, lo); | 320 | lua_geti(L, 1, lo); |
315 | lua_geti(L, 1, up); | 321 | lua_geti(L, 1, up); |
316 | if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ | 322 | if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ |
@@ -322,7 +328,7 @@ static void auxsort (lua_State *L, int lo, int up) { | |||
322 | if (up - lo < 100) /* small interval? */ | 328 | if (up - lo < 100) /* small interval? */ |
323 | p = (lo + up)/2; /* middle element is a good pivot */ | 329 | p = (lo + up)/2; /* middle element is a good pivot */ |
324 | else /* for larger intervals, it is worth a random pivot */ | 330 | else /* for larger intervals, it is worth a random pivot */ |
325 | p = choosePivot(lo, up); | 331 | p = l_sortpivot(lo, up); |
326 | lua_geti(L, 1, p); | 332 | lua_geti(L, 1, p); |
327 | lua_geti(L, 1, lo); | 333 | lua_geti(L, 1, lo); |
328 | if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ | 334 | if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ |