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 * 57 strlist_alloc(size_t const size) 58 { 59 return kmem_zalloc(size, KM_SLEEP); 60 } 61 62 static void 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 * 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 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 * 93 strlist_alloc(size_t const size) 94 { 95 return calloc(1, size); 96 } 97 98 static void 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 * 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 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 * 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 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 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 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 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 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 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 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 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
Indexes created Sun Sep 21 16:09:51 GMT 2025