/*      $NetBSD: strlist.c,v 1.3 2023/08/11 07:05:39 mrg Exp $  */

/*-
 * Copyright (c) 2021 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Jason R. Thorpe.
 *
 * 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.
 */

/*
 * strlist --
 *
 *      A set of routines for interacting with IEEE 1275 (OpenFirmware)
 *      style string lists.
 *
 *      An OpenFirmware string list is simply a buffer containing
 *      multiple NUL-terminated strings concatenated together.
 *
 *      So, for example, the a string list consisting of the strings
 *      "foo", "bar", and "baz" would be represented in memory like:
 *
 *              foo\0bar\0baz\0
 */

#include <sys/types.h>

/*
 * Memory allocation wrappers to handle different environments.
 */
#if defined(_KERNEL)
#include <sys/kmem.h>
#include <sys/systm.h>

static void *
strlist_alloc(size_t const size)
{
        return kmem_zalloc(size, KM_SLEEP);
}

static void
strlist_free(void * const v, size_t const size)
{
        kmem_free(v, size);
}
#elif defined(_STANDALONE)
#include <lib/libkern/libkern.h>
#include <lib/libsa/stand.h>

static void *
strlist_alloc(size_t const size)
{
        char *cp = alloc(size);
        if (cp != NULL) {
                memset(cp, 0, size);
        }
        return cp;
}

static void
strlist_free(void * const v, size_t const size)
{
        dealloc(v, size);
}
#else /* user-space */
#include <stdlib.h>
#include <string.h>

extern int pmatch(const char *, const char *, const char **);

static void *
strlist_alloc(size_t const size)
{
        return calloc(1, size);
}

static void
strlist_free(void * const v, size_t const size __unused)
{
        free(v);
}
#endif

#include "strlist.h"

/*
 * strlist_next --
 *
 *      Return a pointer to the next string in the strlist,
 *      or NULL if there are no more strings.
 */
const char *
strlist_next(const char * const sl, size_t const slsize, size_t * const cursorp)
{

        if (sl == NULL || slsize == 0 || cursorp == NULL) {
                return NULL;
        }

        size_t cursor = *cursorp;

        if (cursor >= slsize) {
                /* No more strings in the list. */
                return NULL;
        }

        const char *cp = sl + cursor;
        *cursorp = cursor + strlen(cp) + 1;

        return cp;
}

/*
 * strlist_count --
 *
 *      Return the number of strings in the strlist.
 */
unsigned int
strlist_count(const char *sl, size_t slsize)
{

        if (sl == NULL || slsize == 0) {
                return 0;
        }

        size_t cursize;
        unsigned int count;

        for (count = 0; slsize != 0;
             count++, sl += cursize, slsize -= cursize) {
                cursize = strlen(sl) + 1;
        }
        return count;
}

/*
 * strlist_string --
 *
 *      Returns the string in the strlist at the specified index.
 *      Returns NULL if the index is beyond the strlist range.
 */
const char *
strlist_string(const char * sl, size_t slsize, unsigned int const idx)
{

        if (sl == NULL || slsize == 0) {
                return NULL;
        }

        size_t cursize;
        unsigned int i;

        for (i = 0; slsize != 0; i++, slsize -= cursize, sl += cursize) {
                cursize = strlen(sl) + 1;
                if (i == idx) {
                        return sl;
                }
        }

        return NULL;
}

static bool
match_strcmp(const char * const s1, const char * const s2)
{
        return strcmp(s1, s2) == 0;
}

#if !defined(_STANDALONE)
static bool
match_pmatch(const char * const s1, const char * const s2)
{
        return pmatch(s1, s2, NULL) == 2;
}
#endif /* _STANDALONE */

static bool
strlist_match_internal(const char * const sl, size_t slsize,
    const char * const str, int * const indexp, unsigned int * const countp,
    bool (*match_fn)(const char *, const char *))
{
        const char *cp;
        size_t l;
        int i;
        bool rv = false;

        if (sl == NULL || slsize == 0) {
                return false;
        }

        cp = sl;

        for (i = 0; slsize != 0;
             l = strlen(cp) + 1, slsize -= l, cp += l, i++) {
                if (rv) {
                        /*
                         * We've already matched. We must be
                         * counting to the end.
                         */
                        continue;
                }
                if ((*match_fn)(cp, str)) {
                        /*
                         * Matched!  Get the index.  If we don't
                         * also want the total count, then get
                         * out early.
                         */
                        *indexp = i;
                        rv = true;
                        if (countp == NULL) {
                                break;
                        }
                }
        }

        if (countp != NULL) {
                *countp = i;
        }

        return rv;
}

/*
 * strlist_match --
 *
 *      Returns a weighted match value (1 <= match <= sl->count) if the
 *      specified string appears in the strlist.  A match at the
 *      beginning of the list carriest the greatest weight (i.e. sl->count)
 *      and a match at the end of the list carriest the least (i.e. 1).
 *      Returns 0 if there is no match.
 *
 *      This routine operates independently of the cursor used to enumerate
 *      a strlist.
 */
int
strlist_match(const char * const sl, size_t const slsize,
    const char * const str)
{
        unsigned int count;
        int idx = 0 /* XXXGCC 12 */;

        if (strlist_match_internal(sl, slsize, str, &idx, &count,
                                   match_strcmp)) {
                return count - idx;
        }
        return 0;
}

#if !defined(_STANDALONE)
/*
 * strlist_pmatch --
 *
 *      Like strlist_match(), but uses pmatch(9) to match the
 *      strings.
 */
int
strlist_pmatch(const char * const sl, size_t const slsize,
    const char * const pattern)
{
        unsigned int count;
        int idx = 0; /* XXXGCC12 */

        if (strlist_match_internal(sl, slsize, pattern, &idx, &count,
                                   match_pmatch)) {
                return count - idx;
        }
        return 0;
}
#endif /* _STANDALONE */

/*
 * strlist_index --
 *
 *      Returns the index of the specified string if it appears
 *      in the strlist.  Returns -1 if the string is not found.
 *
 *      This routine operates independently of the cursor used to enumerate
 *      a strlist.
 */
int
strlist_index(const char * const sl, size_t const slsize,
    const char * const str)
{
        int idx;

        if (strlist_match_internal(sl, slsize, str, &idx, NULL,
                                   match_strcmp)) {
                return idx;
        }
        return -1;
}

/*
 * strlist_append --
 *
 *      Append the specified string to a mutable strlist.  Turns
 *      true if successful, false upon failure for any reason.
 */
bool
strlist_append(char ** const slp, size_t * const slsizep,
    const char * const str)
{
        size_t const slsize = *slsizep;
        char * const sl = *slp;

        size_t const addsize = strlen(str) + 1;
        size_t const newsize = slsize + addsize;
        char * const newbuf = strlist_alloc(newsize);

        if (newbuf == NULL) {
                return false;
        }

        if (sl != NULL) {
                memcpy(newbuf, sl, slsize);
        }

        memcpy(newbuf + slsize, str, addsize);

        if (sl != NULL) {
                strlist_free(sl, slsize);
        }

        *slp = newbuf;
        *slsizep = newsize;

        return true;
}

#ifdef STRLIST_TEST
/*
 * To build and run the tests:
 *
 * % cc -DSTRLIST_TEST -Os pmatch.c strlist.c
 * % ./a.out
 * Testing basic properties.
 * Testing enumeration.
 * Testing weighted matching.
 * Testing pattern matching.
 * Testing index return.
 * Testing string-at-index.
 * Testing gross blob count.
 * Testing gross blob indexing.
 * Testing creating a strlist.
 * Verifying new strlist.
 * All tests completed successfully.
 * %
 */

static char nice_blob[] = "zero\0one\0two\0three\0four\0five";
static char gross_blob[] = "zero\0\0two\0\0four\0\0";

#include <assert.h>
#include <stdio.h>

int
main(int argc, char *argv[])
{
        const char *sl;
        size_t slsize;
        size_t cursor;
        const char *cp;
        size_t size;

        sl = nice_blob;
        slsize = sizeof(nice_blob);

        printf("Testing basic properties.\n");
        assert(strlist_count(sl, slsize) == 6);

        printf("Testing enumeration.\n");
        cursor = 0;
        assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
        assert(strcmp(cp, "zero") == 0);

        assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
        assert(strcmp(cp, "one") == 0);

        assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
        assert(strcmp(cp, "two") == 0);

        assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
        assert(strcmp(cp, "three") == 0);

        assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
        assert(strcmp(cp, "four") == 0);

        assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
        assert(strcmp(cp, "five") == 0);

        assert((cp = strlist_next(sl, slsize, &cursor)) == NULL);

        printf("Testing weighted matching.\n");
        assert(strlist_match(sl, slsize, "non-existent") == 0);
        assert(strlist_match(sl, slsize, "zero") == 6);
        assert(strlist_match(sl, slsize, "one") == 5);
        assert(strlist_match(sl, slsize, "two") == 4);
        assert(strlist_match(sl, slsize, "three") == 3);
        assert(strlist_match(sl, slsize, "four") == 2);
        assert(strlist_match(sl, slsize, "five") == 1);

        printf("Testing pattern matching.\n");
        assert(strlist_pmatch(sl, slsize, "t?o") == 4);
        assert(strlist_pmatch(sl, slsize, "f[a-o][o-u][a-z]") == 2);

        printf("Testing index return.\n");
        assert(strlist_index(sl, slsize, "non-existent") == -1);
        assert(strlist_index(sl, slsize, "zero") == 0);
        assert(strlist_index(sl, slsize, "one") == 1);
        assert(strlist_index(sl, slsize, "two") == 2);
        assert(strlist_index(sl, slsize, "three") == 3);
        assert(strlist_index(sl, slsize, "four") == 4);
        assert(strlist_index(sl, slsize, "five") == 5);

        printf("Testing string-at-index.\n");
        assert(strcmp(strlist_string(sl, slsize, 0), "zero") == 0);
        assert(strcmp(strlist_string(sl, slsize, 1), "one") == 0);
        assert(strcmp(strlist_string(sl, slsize, 2), "two") == 0);
        assert(strcmp(strlist_string(sl, slsize, 3), "three") == 0);
        assert(strcmp(strlist_string(sl, slsize, 4), "four") == 0);
        assert(strcmp(strlist_string(sl, slsize, 5), "five") == 0);
        assert(strlist_string(sl, slsize, 6) == NULL);

        sl = gross_blob;
        slsize = sizeof(gross_blob);

        printf("Testing gross blob count.\n");
        assert(strlist_count(sl, slsize) == 7);

        printf("Testing gross blob indexing.\n");
        assert(strcmp(strlist_string(sl, slsize, 0), "zero") == 0);
        assert(strcmp(strlist_string(sl, slsize, 1), "") == 0);
        assert(strcmp(strlist_string(sl, slsize, 2), "two") == 0);
        assert(strcmp(strlist_string(sl, slsize, 3), "") == 0);
        assert(strcmp(strlist_string(sl, slsize, 4), "four") == 0);
        assert(strcmp(strlist_string(sl, slsize, 5), "") == 0);
        assert(strcmp(strlist_string(sl, slsize, 6), "") == 0);
        assert(strlist_string(sl, slsize, 7) == NULL);


        printf("Testing creating a strlist.\n");
        char *newsl = NULL;
        size_t newslsize = 0;
        assert(strlist_append(&newsl, &newslsize, "zero"));
        assert(strlist_append(&newsl, &newslsize, "one"));
        assert(strlist_append(&newsl, &newslsize, "two"));
        assert(strlist_append(&newsl, &newslsize, "three"));
        assert(strlist_append(&newsl, &newslsize, "four"));
        assert(strlist_append(&newsl, &newslsize, "five"));

        printf("Verifying new strlist.\n");
        assert(strlist_count(newsl, newslsize) == 6);
        assert(strcmp(strlist_string(newsl, newslsize, 0), "zero") == 0);
        assert(strcmp(strlist_string(newsl, newslsize, 1), "one") == 0);
        assert(strcmp(strlist_string(newsl, newslsize, 2), "two") == 0);
        assert(strcmp(strlist_string(newsl, newslsize, 3), "three") == 0);
        assert(strcmp(strlist_string(newsl, newslsize, 4), "four") == 0);
        assert(strcmp(strlist_string(newsl, newslsize, 5), "five") == 0);
        assert(strlist_string(newsl, newslsize, 6) == NULL);

        /* This should be equivalent to nice_blob. */
        assert(newslsize == sizeof(nice_blob));
        assert(memcmp(newsl, nice_blob, newslsize) == 0);


        printf("All tests completed successfully.\n");
        return 0;
}

#endif /* STRLIST_TEST */