aboutsummaryrefslogtreecommitdiff
path: root/coreutils
diff options
context:
space:
mode:
authorDenys Vlasenko <vda.linux@googlemail.com>2021-09-07 22:51:42 +0200
committerDenys Vlasenko <vda.linux@googlemail.com>2021-09-07 22:51:42 +0200
commit6a9b3f7acfaa7365515f1eb70427d5ddd687c162 (patch)
treecf8f15c4e8f4a1acadc5b14557238396be4c9962 /coreutils
parent574b9c446da11baaf89551f09f951d6523eff731 (diff)
downloadbusybox-w32-6a9b3f7acfaa7365515f1eb70427d5ddd687c162.tar.gz
busybox-w32-6a9b3f7acfaa7365515f1eb70427d5ddd687c162.tar.bz2
busybox-w32-6a9b3f7acfaa7365515f1eb70427d5ddd687c162.zip
shuf: add a TODO, code shrink
function old new delta shuf_main 501 500 -1 Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'coreutils')
-rw-r--r--coreutils/shuf.c24
1 files changed, 14 insertions, 10 deletions
diff --git a/coreutils/shuf.c b/coreutils/shuf.c
index 50483a25e..3def3d80f 100644
--- a/coreutils/shuf.c
+++ b/coreutils/shuf.c
@@ -44,21 +44,25 @@
44 */ 44 */
45static void shuffle_lines(char **lines, unsigned numlines, unsigned outlines) 45static void shuffle_lines(char **lines, unsigned numlines, unsigned outlines)
46{ 46{
47 unsigned i;
48 unsigned r;
49 char *tmp;
50
51 srand(monotonic_us()); 47 srand(monotonic_us());
52 48
53 for (i = numlines - 1; outlines > 0; i--, outlines--) { 49 while (outlines != 0) {
54 r = rand(); 50 char *tmp;
51 unsigned r = rand();
55 /* RAND_MAX can be as small as 32767 */ 52 /* RAND_MAX can be as small as 32767 */
56 if (i > RAND_MAX) 53 if (numlines > RAND_MAX)
57 r ^= rand() << 15; 54 r ^= rand() << 15;
58 r %= i + 1; 55 r %= numlines;
59 tmp = lines[i]; 56//TODO: the above method is seriously non-uniform when numlines is very large.
60 lines[i] = lines[r]; 57//For example, with numlines of 0xf0000000,
58//values of (r % numlines) in [0, 0x0fffffff] range
59//are more likely: e.g. r=1 and r=0xf0000001 both map to 1,
60//whereas only one value, r=0xefffffff, maps to 0xefffffff.
61 numlines--;
62 tmp = lines[numlines];
63 lines[numlines] = lines[r];
61 lines[r] = tmp; 64 lines[r] = tmp;
65 outlines--;
62 } 66 }
63} 67}
64 68