diff options
| author | thorpej <thorpej@NetBSD.org> | 2021-01-21 15:43:37 +0000 |
|---|---|---|
| committer | thorpej <thorpej@NetBSD.org> | 2021-01-21 15:43:37 +0000 |
| commit | 649717513c569266c4a88c2cf207651c9cd2fc02 (patch) | |
| tree | 98efd27ce3b378b275df03708fc868072de1c9d0 /sys/lib | |
| parent | 485ac2076dc51294308ef3f402b6344db35ff4f6 (diff) | |
Add a generic set of routines for interacting with OpenFirmware-style
string lists.
Diffstat (limited to 'sys/lib')
| -rw-r--r-- | sys/lib/libkern/libkern.h | 4 | ||||
| -rw-r--r-- | sys/lib/libkern/strlist.c | 490 | ||||
| -rw-r--r-- | sys/lib/libkern/strlist.h | 50 |
3 files changed, 543 insertions, 1 deletions
diff --git a/sys/lib/libkern/libkern.h b/sys/lib/libkern/libkern.h index 40ae38a7270..ea9e38bfe3d 100644 --- a/sys/lib/libkern/libkern.h +++ b/sys/lib/libkern/libkern.h @@ -1,4 +1,4 @@ -/* $NetBSD: libkern.h,v 1.141 2021/01/16 23:51:51 chs Exp $ */ +/* $NetBSD: libkern.h,v 1.142 2021/01/21 15:43:37 thorpej Exp $ */ /*- * Copyright (c) 1992, 1993 @@ -44,6 +44,8 @@ #include <sys/inttypes.h> #include <sys/null.h> +#include <lib/libkern/strlist.h> + #ifndef LIBKERN_INLINE #define LIBKERN_INLINE static __inline #define LIBKERN_BODY diff --git a/sys/lib/libkern/strlist.c b/sys/lib/libkern/strlist.c new file mode 100644 index 00000000000..0cbfd65847d --- /dev/null +++ b/sys/lib/libkern/strlist.c @@ -0,0 +1,490 @@ +/* $NetBSD: strlist.c,v 1.1 2021/01/21 15:43:37 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/libsa/stand.h> + +static void * +strlist_alloc(size_t const size) +{ + 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 */ diff --git a/sys/lib/libkern/strlist.h b/sys/lib/libkern/strlist.h new file mode 100644 index 00000000000..6f8b6ddb572 --- /dev/null +++ b/sys/lib/libkern/strlist.h @@ -0,0 +1,50 @@ +/* $NetBSD: strlist.h,v 1.1 2021/01/21 15:43:37 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. + */ + +#ifndef _LIB_LIBKERN_STRLIST_H_ +#define _LIB_LIBKERN_STRLIST_H_ + +#include <sys/types.h> +#if !defined(_KERNEL) && !defined(_STANDALONE) +#include <stdbool.h> +#endif /* ! _KERNEL && !_STANDALONE */ + +const char * strlist_next(const char *, size_t, size_t *); +unsigned int strlist_count(const char *, size_t); +const char * strlist_string(const char *, size_t, unsigned int); + +int strlist_match(const char *, size_t, const char *); +int strlist_pmatch(const char *, size_t, const char *); +int strlist_index(const char *, size_t, const char *); + +bool strlist_append(char **, size_t *, const char *); + +#endif /* _LIB_LIBKERN_STRLIST_H_ */ |
