POSIX + BSD-extensions implementation of shuf(1)

Question

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);
}
```

Answer 1

• 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++)