1 /* $NetBSD: strlist.c,v 1.3 2023/08/11 07:05:39 mrg Exp $ */
2
3 /*-
4 * Copyright (c) 2021 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Jason R. Thorpe.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /*
33 * strlist --
34 *
35 * A set of routines for interacting with IEEE 1275 (OpenFirmware)
36 * style string lists.
37 *
38 * An OpenFirmware string list is simply a buffer containing
39 * multiple NUL-terminated strings concatenated together.
40 *
41 * So, for example, the a string list consisting of the strings
42 * "foo", "bar", and "baz" would be represented in memory like:
43 *
44 * foo\0bar\0baz\0
45 */
46
47 #include <sys/types.h>
48
49 /*
50 * Memory allocation wrappers to handle different environments.
51 */
52 #if defined(_KERNEL)
53 #include <sys/kmem.h>
54 #include <sys/systm.h>
55
56 static void *
strlist_alloc(size_t const size)57 strlist_alloc(size_t const size)
58 {
59 return kmem_zalloc(size, KM_SLEEP);
60 }
61
62 static void
strlist_free(void * const v,size_t const size)63 strlist_free(void * const v, size_t const size)
64 {
65 kmem_free(v, size);
66 }
67 #elif defined(_STANDALONE)
68 #include <lib/libkern/libkern.h>
69 #include <lib/libsa/stand.h>
70
71 static void *
strlist_alloc(size_t const size)72 strlist_alloc(size_t const size)
73 {
74 char *cp = alloc(size);
75 if (cp != NULL) {
76 memset(cp, 0, size);
77 }
78 return cp;
79 }
80
81 static void
strlist_free(void * const v,size_t const size)82 strlist_free(void * const v, size_t const size)
83 {
84 dealloc(v, size);
85 }
86 #else /* user-space */
87 #include <stdlib.h>
88 #include <string.h>
89
90 extern int pmatch(const char *, const char *, const char **);
91
92 static void *
strlist_alloc(size_t const size)93 strlist_alloc(size_t const size)
94 {
95 return calloc(1, size);
96 }
97
98 static void
strlist_free(void * const v,size_t const size __unused)99 strlist_free(void * const v, size_t const size __unused)
100 {
101 free(v);
102 }
103 #endif
104
105 #include "strlist.h"
106
107 /*
108 * strlist_next --
109 *
110 * Return a pointer to the next string in the strlist,
111 * or NULL if there are no more strings.
112 */
113 const char *
strlist_next(const char * const sl,size_t const slsize,size_t * const cursorp)114 strlist_next(const char * const sl, size_t const slsize, size_t * const cursorp)
115 {
116
117 if (sl == NULL || slsize == 0 || cursorp == NULL) {
118 return NULL;
119 }
120
121 size_t cursor = *cursorp;
122
123 if (cursor >= slsize) {
124 /* No more strings in the list. */
125 return NULL;
126 }
127
128 const char *cp = sl + cursor;
129 *cursorp = cursor + strlen(cp) + 1;
130
131 return cp;
132 }
133
134 /*
135 * strlist_count --
136 *
137 * Return the number of strings in the strlist.
138 */
139 unsigned int
strlist_count(const char * sl,size_t slsize)140 strlist_count(const char *sl, size_t slsize)
141 {
142
143 if (sl == NULL || slsize == 0) {
144 return 0;
145 }
146
147 size_t cursize;
148 unsigned int count;
149
150 for (count = 0; slsize != 0;
151 count++, sl += cursize, slsize -= cursize) {
152 cursize = strlen(sl) + 1;
153 }
154 return count;
155 }
156
157 /*
158 * strlist_string --
159 *
160 * Returns the string in the strlist at the specified index.
161 * Returns NULL if the index is beyond the strlist range.
162 */
163 const char *
strlist_string(const char * sl,size_t slsize,unsigned int const idx)164 strlist_string(const char * sl, size_t slsize, unsigned int const idx)
165 {
166
167 if (sl == NULL || slsize == 0) {
168 return NULL;
169 }
170
171 size_t cursize;
172 unsigned int i;
173
174 for (i = 0; slsize != 0; i++, slsize -= cursize, sl += cursize) {
175 cursize = strlen(sl) + 1;
176 if (i == idx) {
177 return sl;
178 }
179 }
180
181 return NULL;
182 }
183
184 static bool
match_strcmp(const char * const s1,const char * const s2)185 match_strcmp(const char * const s1, const char * const s2)
186 {
187 return strcmp(s1, s2) == 0;
188 }
189
190 #if !defined(_STANDALONE)
191 static bool
match_pmatch(const char * const s1,const char * const s2)192 match_pmatch(const char * const s1, const char * const s2)
193 {
194 return pmatch(s1, s2, NULL) == 2;
195 }
196 #endif /* _STANDALONE */
197
198 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 *))199 strlist_match_internal(const char * const sl, size_t slsize,
200 const char * const str, int * const indexp, unsigned int * const countp,
201 bool (*match_fn)(const char *, const char *))
202 {
203 const char *cp;
204 size_t l;
205 int i;
206 bool rv = false;
207
208 if (sl == NULL || slsize == 0) {
209 return false;
210 }
211
212 cp = sl;
213
214 for (i = 0; slsize != 0;
215 l = strlen(cp) + 1, slsize -= l, cp += l, i++) {
216 if (rv) {
217 /*
218 * We've already matched. We must be
219 * counting to the end.
220 */
221 continue;
222 }
223 if ((*match_fn)(cp, str)) {
224 /*
225 * Matched! Get the index. If we don't
226 * also want the total count, then get
227 * out early.
228 */
229 *indexp = i;
230 rv = true;
231 if (countp == NULL) {
232 break;
233 }
234 }
235 }
236
237 if (countp != NULL) {
238 *countp = i;
239 }
240
241 return rv;
242 }
243
244 /*
245 * strlist_match --
246 *
247 * Returns a weighted match value (1 <= match <= sl->count) if the
248 * specified string appears in the strlist. A match at the
249 * beginning of the list carriest the greatest weight (i.e. sl->count)
250 * and a match at the end of the list carriest the least (i.e. 1).
251 * Returns 0 if there is no match.
252 *
253 * This routine operates independently of the cursor used to enumerate
254 * a strlist.
255 */
256 int
strlist_match(const char * const sl,size_t const slsize,const char * const str)257 strlist_match(const char * const sl, size_t const slsize,
258 const char * const str)
259 {
260 unsigned int count;
261 int idx = 0 /* XXXGCC 12 */;
262
263 if (strlist_match_internal(sl, slsize, str, &idx, &count,
264 match_strcmp)) {
265 return count - idx;
266 }
267 return 0;
268 }
269
270 #if !defined(_STANDALONE)
271 /*
272 * strlist_pmatch --
273 *
274 * Like strlist_match(), but uses pmatch(9) to match the
275 * strings.
276 */
277 int
strlist_pmatch(const char * const sl,size_t const slsize,const char * const pattern)278 strlist_pmatch(const char * const sl, size_t const slsize,
279 const char * const pattern)
280 {
281 unsigned int count;
282 int idx = 0; /* XXXGCC12 */
283
284 if (strlist_match_internal(sl, slsize, pattern, &idx, &count,
285 match_pmatch)) {
286 return count - idx;
287 }
288 return 0;
289 }
290 #endif /* _STANDALONE */
291
292 /*
293 * strlist_index --
294 *
295 * Returns the index of the specified string if it appears
296 * in the strlist. Returns -1 if the string is not found.
297 *
298 * This routine operates independently of the cursor used to enumerate
299 * a strlist.
300 */
301 int
strlist_index(const char * const sl,size_t const slsize,const char * const str)302 strlist_index(const char * const sl, size_t const slsize,
303 const char * const str)
304 {
305 int idx;
306
307 if (strlist_match_internal(sl, slsize, str, &idx, NULL,
308 match_strcmp)) {
309 return idx;
310 }
311 return -1;
312 }
313
314 /*
315 * strlist_append --
316 *
317 * Append the specified string to a mutable strlist. Turns
318 * true if successful, false upon failure for any reason.
319 */
320 bool
strlist_append(char ** const slp,size_t * const slsizep,const char * const str)321 strlist_append(char ** const slp, size_t * const slsizep,
322 const char * const str)
323 {
324 size_t const slsize = *slsizep;
325 char * const sl = *slp;
326
327 size_t const addsize = strlen(str) + 1;
328 size_t const newsize = slsize + addsize;
329 char * const newbuf = strlist_alloc(newsize);
330
331 if (newbuf == NULL) {
332 return false;
333 }
334
335 if (sl != NULL) {
336 memcpy(newbuf, sl, slsize);
337 }
338
339 memcpy(newbuf + slsize, str, addsize);
340
341 if (sl != NULL) {
342 strlist_free(sl, slsize);
343 }
344
345 *slp = newbuf;
346 *slsizep = newsize;
347
348 return true;
349 }
350
351 #ifdef STRLIST_TEST
352 /*
353 * To build and run the tests:
354 *
355 * % cc -DSTRLIST_TEST -Os pmatch.c strlist.c
356 * % ./a.out
357 * Testing basic properties.
358 * Testing enumeration.
359 * Testing weighted matching.
360 * Testing pattern matching.
361 * Testing index return.
362 * Testing string-at-index.
363 * Testing gross blob count.
364 * Testing gross blob indexing.
365 * Testing creating a strlist.
366 * Verifying new strlist.
367 * All tests completed successfully.
368 * %
369 */
370
371 static char nice_blob[] = "zero\0one\0two\0three\0four\0five";
372 static char gross_blob[] = "zero\0\0two\0\0four\0\0";
373
374 #include <assert.h>
375 #include <stdio.h>
376
377 int
main(int argc,char * argv[])378 main(int argc, char *argv[])
379 {
380 const char *sl;
381 size_t slsize;
382 size_t cursor;
383 const char *cp;
384 size_t size;
385
386 sl = nice_blob;
387 slsize = sizeof(nice_blob);
388
389 printf("Testing basic properties.\n");
390 assert(strlist_count(sl, slsize) == 6);
391
392 printf("Testing enumeration.\n");
393 cursor = 0;
394 assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
395 assert(strcmp(cp, "zero") == 0);
396
397 assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
398 assert(strcmp(cp, "one") == 0);
399
400 assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
401 assert(strcmp(cp, "two") == 0);
402
403 assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
404 assert(strcmp(cp, "three") == 0);
405
406 assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
407 assert(strcmp(cp, "four") == 0);
408
409 assert((cp = strlist_next(sl, slsize, &cursor)) != NULL);
410 assert(strcmp(cp, "five") == 0);
411
412 assert((cp = strlist_next(sl, slsize, &cursor)) == NULL);
413
414 printf("Testing weighted matching.\n");
415 assert(strlist_match(sl, slsize, "non-existent") == 0);
416 assert(strlist_match(sl, slsize, "zero") == 6);
417 assert(strlist_match(sl, slsize, "one") == 5);
418 assert(strlist_match(sl, slsize, "two") == 4);
419 assert(strlist_match(sl, slsize, "three") == 3);
420 assert(strlist_match(sl, slsize, "four") == 2);
421 assert(strlist_match(sl, slsize, "five") == 1);
422
423 printf("Testing pattern matching.\n");
424 assert(strlist_pmatch(sl, slsize, "t?o") == 4);
425 assert(strlist_pmatch(sl, slsize, "f[a-o][o-u][a-z]") == 2);
426
427 printf("Testing index return.\n");
428 assert(strlist_index(sl, slsize, "non-existent") == -1);
429 assert(strlist_index(sl, slsize, "zero") == 0);
430 assert(strlist_index(sl, slsize, "one") == 1);
431 assert(strlist_index(sl, slsize, "two") == 2);
432 assert(strlist_index(sl, slsize, "three") == 3);
433 assert(strlist_index(sl, slsize, "four") == 4);
434 assert(strlist_index(sl, slsize, "five") == 5);
435
436 printf("Testing string-at-index.\n");
437 assert(strcmp(strlist_string(sl, slsize, 0), "zero") == 0);
438 assert(strcmp(strlist_string(sl, slsize, 1), "one") == 0);
439 assert(strcmp(strlist_string(sl, slsize, 2), "two") == 0);
440 assert(strcmp(strlist_string(sl, slsize, 3), "three") == 0);
441 assert(strcmp(strlist_string(sl, slsize, 4), "four") == 0);
442 assert(strcmp(strlist_string(sl, slsize, 5), "five") == 0);
443 assert(strlist_string(sl, slsize, 6) == NULL);
444
445 sl = gross_blob;
446 slsize = sizeof(gross_blob);
447
448 printf("Testing gross blob count.\n");
449 assert(strlist_count(sl, slsize) == 7);
450
451 printf("Testing gross blob indexing.\n");
452 assert(strcmp(strlist_string(sl, slsize, 0), "zero") == 0);
453 assert(strcmp(strlist_string(sl, slsize, 1), "") == 0);
454 assert(strcmp(strlist_string(sl, slsize, 2), "two") == 0);
455 assert(strcmp(strlist_string(sl, slsize, 3), "") == 0);
456 assert(strcmp(strlist_string(sl, slsize, 4), "four") == 0);
457 assert(strcmp(strlist_string(sl, slsize, 5), "") == 0);
458 assert(strcmp(strlist_string(sl, slsize, 6), "") == 0);
459 assert(strlist_string(sl, slsize, 7) == NULL);
460
461
462 printf("Testing creating a strlist.\n");
463 char *newsl = NULL;
464 size_t newslsize = 0;
465 assert(strlist_append(&newsl, &newslsize, "zero"));
466 assert(strlist_append(&newsl, &newslsize, "one"));
467 assert(strlist_append(&newsl, &newslsize, "two"));
468 assert(strlist_append(&newsl, &newslsize, "three"));
469 assert(strlist_append(&newsl, &newslsize, "four"));
470 assert(strlist_append(&newsl, &newslsize, "five"));
471
472 printf("Verifying new strlist.\n");
473 assert(strlist_count(newsl, newslsize) == 6);
474 assert(strcmp(strlist_string(newsl, newslsize, 0), "zero") == 0);
475 assert(strcmp(strlist_string(newsl, newslsize, 1), "one") == 0);
476 assert(strcmp(strlist_string(newsl, newslsize, 2), "two") == 0);
477 assert(strcmp(strlist_string(newsl, newslsize, 3), "three") == 0);
478 assert(strcmp(strlist_string(newsl, newslsize, 4), "four") == 0);
479 assert(strcmp(strlist_string(newsl, newslsize, 5), "five") == 0);
480 assert(strlist_string(newsl, newslsize, 6) == NULL);
481
482 /* This should be equivalent to nice_blob. */
483 assert(newslsize == sizeof(nice_blob));
484 assert(memcmp(newsl, nice_blob, newslsize) == 0);
485
486
487 printf("All tests completed successfully.\n");
488 return 0;
489 }
490
491 #endif /* STRLIST_TEST */
492