/*      $NetBSD: h_sort.c,v 1.3 2025/03/02 23:11:19 riastradh Exp $     */

/*-
 * Copyright (c) 2025 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/cdefs.h>
__RCSID("$NetBSD: h_sort.c,v 1.3 2025/03/02 23:11:19 riastradh Exp $");

#include <assert.h>
#include <err.h>
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

static void
heapsort_r_wrapper(void *a, size_t n, size_t sz,
    int (*cmp)(const void *, const void *, void *), void *cookie)
{

        if (heapsort_r(a, n, sz, cmp, cookie) == -1)
                err(1, "heapsort_r");
}

static void
mergesort_r_wrapper(void *a, size_t n, size_t sz,
    int (*cmp)(const void *, const void *, void *), void *cookie)
{

        if (mergesort_r(a, n, sz, cmp, cookie) == -1)
                err(1, "mergesort_r");
}

struct context {
        const char      *buf;
        const size_t    *linepos;
};

static int
cmp(const void *va, const void *vb, void *cookie)
{
        const struct context *C = cookie;
        const size_t *a = va;
        const size_t *b = vb;

        return strcmp(C->buf + C->linepos[*a], C->buf + C->linepos[*b]);
}

static void __dead
usage(void)
{

        fprintf(stderr, "Usage: %s [-n] <sortfn>\n", getprogname());
        exit(1);
}

int
main(int argc, char **argv)
{
        int ch;
        int nflag = 0;
        void (*sortfn)(void *, size_t, size_t,
            int (*)(const void *, const void *, void *), void *);
        char *buf = NULL;
        size_t nbuf;
        size_t *linepos = NULL;
        size_t nlines;
        size_t *permutation = NULL;
        size_t off;
        ssize_t nread;
        char *p;
        size_t i;
        int error;

        /*
         * Parse arguments.
         */
        setprogname(argv[0]);
        while ((ch = getopt(argc, argv, "hn")) != -1) {
                switch (ch) {
                case 'n':
                        nflag = 1;
                        break;
                case '?':
                case 'h':
                default:
                        usage();
                }
        }
        argc -= optind;
        argv += optind;
        if (argc != 1)
                usage();
        if (strcmp(argv[0], "heapsort_r") == 0)
                sortfn = &heapsort_r_wrapper;
        else if (strcmp(argv[0], "mergesort_r") == 0)
                sortfn = &mergesort_r_wrapper;
        else if (strcmp(argv[0], "qsort_r") == 0)
                sortfn = &qsort_r;
        else
                errx(1, "unknown sort: %s", argv[0]);

        /*
         * Allocate an initial 4K buffer.
         */
        nbuf = 0x1000;
        error = reallocarr(&buf, nbuf, 1);
        if (error)
                errc(1, error, "reallocarr");

        /*
         * Read the input into a contiguous buffer.  Reject input with
         * embedded NULs so we can use strcmp(3) to compare lines.
         */
        off = 0;
        while ((nread = read(STDIN_FILENO, buf + off, nbuf - off - 1)) != 0) {
                if (nread == -1)
                        err(1, "read");
                if ((size_t)nread > nbuf - off - 1)
                        errx(1, "overlong read: %zu", (size_t)nread);
                if (memchr(buf + off, '\0', (size_t)nread) != NULL)
                        errx(1, "NUL byte in input");
                off += (size_t)nread;

                /*
                 * If we filled the buffer, reallocate it with double
                 * the size.  Bail if that would overflow.
                 */
                if (nbuf - off == 1) {
                        if (nbuf > SIZE_MAX/2)
                                errx(1, "input overflow");
                        nbuf *= 2;
                        error = reallocarr(&buf, nbuf, 1);
                        if (error)
                                errc(1, error, "reallocarr");
                }
        }

        /*
         * If the input was empty, nothing to do.
         */
        if (off == 0)
                return 0;

        /*
         * NUL-terminate the input and count the lines.  The last line
         * may have no trailing \n.
         */
        buf[off] = '\0';
        nlines = 1;
        for (p = buf; (p = strchr(p, '\n')) != NULL;) {
                if (*++p == '\0')
                        break;
                nlines++;
        }

        /*
         * Create an array of line positions to sort.  NUL-terminate
         * each line so we can use strcmp(3).
         */
        error = reallocarr(&linepos, nlines, sizeof(linepos[0]));
        if (error)
                errc(1, error, "reallocarr");
        i = 0;
        for (p = buf; linepos[i++] = p - buf, (p = strchr(p, '\n')) != NULL;) {
                *p = '\0';
                if (*++p == '\0')
                        break;
        }
        assert(i == nlines);

        /*
         * Create an array of permuted line numbers.
         */
        error = reallocarr(&permutation, nlines, sizeof(permutation[0]));
        if (error)
                errc(1, error, "reallocarr");
        for (i = 0; i < nlines; i++)
                permutation[i] = i;

        /*
         * Sort the lines via comparison function that consults the
         * buffer as a cookie.
         */
        (*sortfn)(permutation, nlines, sizeof(permutation[0]), &cmp,
            &(struct context) { .buf = buf, .linepos = linepos });

        /*
         * Print the lines in sorted order with the original line
         * numbers.
         */
        for (i = 0; i < nlines; i++) {
                const size_t j = permutation[i];
                if (nflag)
                        printf("%zu %s\n", j, buf + linepos[j]);
                else
                        printf("%s\n", buf + linepos[j]);
        }
        fflush(stdout);
        return ferror(stdout);
}