3
\$\begingroup\$

I implemented GNU shuf(1) in C using POSIX system calls and some BSD extensions. You must compile it with -lbsd.

shuf(1) shuffles the lines of the files given as arguments or the standard input (if no argument was provided) and print it. If the -n NUM option were given, prints NUM random lines from the files.

It first reads the files into memory in the string buf. Then the function shuf() breaks buf into lines by converting \n into \0 and creates an array of strings nl where each element points to a newline in buf. Then, it permutates randomly the array nl and prints the lines in it. I think that shuf() is overloaded with too much computation.

The algorithm for creating growing arrays I stole from the book The Practice of Programming, by Brian Kernighan and Rob Pike.

I am using the suckless coding style.

PS: The only option I implemented from GNU shuf(1) was -n. Read the manual for your local shuf(1) to understand better what the command does.

#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <bsd/stdlib.h>

#define NLINIT 1
#define NLGROW 2

/* growing list of lines in buffer */
struct Newlines {
    size_t nval;    /* current number of values */
    size_t max;     /* allocated number of values */
    char **array;   /* array of lines */
};

static ssize_t readfile(int, char **, size_t *);
static void addline(struct Newlines *, char *);
static void shuf(char *, int);
static int getint(const char *);
static void usage(void);

/* shuf: get random line of file */
int
main(int argc, char *argv[])
{
    int exitval, nshuf, c, fd;
    char *buf = NULL;
    size_t n = 0;

    nshuf = 0;
    while ((c = getopt(argc, argv, "n:")) != -1) {
        switch (c) {
        case 'n':
            nshuf = getint(optarg);
            if (nshuf < 1)
                errx(EXIT_FAILURE, "%s: invalid number of lines", optarg);
            break;
        default:
            usage();
            break;
        }
    }
    argc -= optind;
    argv += optind;

    exitval = EXIT_SUCCESS;
    if (argc == 0) {
        if (readfile(STDIN_FILENO, &buf, &n) == -1)
            err(EXIT_FAILURE, "stdin");
    } else {
        while (argc-- > 0) {
            if ((fd = open(*argv, O_RDONLY)) == -1) {
                warn("%s", *argv);
                exitval = EXIT_FAILURE;
            } else {
                if (readfile(fd, &buf, &n) == -1)
                    err(EXIT_FAILURE, "%s", *argv);
                close(fd);
            }
            argv++;
        }
    }
    shuf(buf, nshuf);

    return exitval;
}

/* appends file fd into memory in *buf, *used is the number of chars already read */
static ssize_t
readfile(int fd, char **buf, size_t *used)
{
    char tmpbuf[BUFSIZ], *tmp;
    size_t size = *used;
    ssize_t n;

    while ((n = read(fd, tmpbuf, sizeof tmpbuf)) != -0 && n != -1) {
        if (n + *used >= size) {
            size = *used + BUFSIZ + 1;

            /* overflow check */
            if (size <= *used) {
                errno = EOVERFLOW;
                return -1;
            }

            if ((tmp = realloc(*buf, size)) == NULL)
                return -1;
            *buf = tmp;
        }
        memcpy(*buf + *used, tmpbuf, n);
        (*buf)[*used + n] = '\0';
        *used += n;
    }
    if (n == -1)
        return -1;

    return size;
}

/* get nshuf random lines from buf (all lines if nshuf == 0) */
static void
shuf(char *buf, int nshuf)
{
    struct Newlines nl;
    size_t i, randn;
    char *p, *tmp;

    nl.array = NULL;
    nl.nval = 0;
    nl.max = 0;

    /* count newlines and create array of pointer to lines */
    addline(&nl, buf);
    for (p = buf; *p != '\0'; p++) {
        if (*p == '\n') {
            *p = '\0';
            if (*(p+1) != '\0')
                addline(&nl, p+1);
        }
    }

    /* randomly permutate lines */
    for (i = 0; i < nl.nval; i++) {
        randn = arc4random_uniform(nl.nval);

        tmp = nl.array[i];
        nl.array[i] = nl.array[randn];
        nl.array[randn] = tmp;
    }

    /* print random lines */
    for (i = 0; i < nl.nval && (nshuf == 0 || i < nshuf); i++)
        printf("%s\n", nl.array[i]);

    free(nl.array);
}

/* add a new line to the array of newlines */
static void
addline(struct Newlines *nl, char *line)
{
    char **newp;
    size_t newsize;

    if (nl->array == NULL) { /* first time */
        newsize = NLINIT;
        newp = reallocarray(NULL, newsize, sizeof *nl->array);
        if (newp == NULL)
            err(EXIT_FAILURE, "realloc");
        nl->array = newp;
        nl->nval = 0;
        nl->max = newsize;
    } else if (nl->nval >= nl->max) { /* grow */
        newsize = NLGROW * nl->max;
        newp = reallocarray(nl->array, newsize, sizeof *nl->array);
        if (newp == NULL)
            err(EXIT_FAILURE, "realloc");
        nl->array = newp;
        nl->max = newsize;
    }
    nl->array[nl->nval] = line;
    nl->nval++;
}

/* get a number from a string */
static int
getint(const char *s)
{
    long n;
    char *endp;

    n = strtol(s, &endp, 10);
    if (n > INT_MAX || n < INT_MIN || endp == s || *endp != '\0')
        return -1;
    return (int) n;
}

static void
usage(void)
{
    (void) fprintf(stderr, "usage: [-n nlines] shuf file...\n");
    exit(EXIT_FAILURE);
}
```
\$\endgroup\$
  • \$\begingroup\$ With -Wextra: shuf.c:137:49: warning: comparison of integers of different signs: 'size_t' (aka 'unsigned long') and 'int' \$\endgroup\$ – Arkadiusz Drabczyk Apr 17 at 19:25
2
\$\begingroup\$
  • I very strongly recommend to always type explicit braces, even around one-liners, e.g.

    if (newp == NULL) {
        err(EXIT_FAILURE, "realloc");
    }
    
  • Every time you feel compelled to put a comment like /* count newlines and create array of pointer to lines */, or /* randomly permutate lines */, it is a strong indication that the commented piece of code wants to be a function.

    In general, avoid naked loops. A loop implements an algorithm, and hence deserves a name.

  • The shuffling algorithm

    for (i = 0; i < nl.nval; i++) {
        randn = arc4random_uniform(nl.nval);
    
        tmp = nl.array[i];
        nl.array[i] = nl.array[randn];
        nl.array[randn] = tmp;
    }
    

    is biased. Some permutations are more likely than others. For details, see here.

  • The /* print random lines */ loop condition is very convoluted. Consider fixing nshuf as soon as you know the number of lines:

    if ((nshuf == 0) || (nshuf > nl.nval)) {
        nshuf = nl.nval;
    }
    

    Then the loop condition becomes much simpler:

    for (i = 0; i < nshuf; i++)
    
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.