/* $NetBSD: strlist.c,v 1.2 2021/01/23 19:41:16 thorpej 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;
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;
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 */