From 52acddf36c8cb3778ab2098a0d95cc2e375a4069 Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Mon, 24 Apr 2023 18:20:10 -0400 Subject: string-list: multi-delimiter `string_list_split_in_place()` Enhance `string_list_split_in_place()` to accept multiple characters as delimiters instead of a single character. Instead of using `strchr(2)` to locate the first occurrence of the given delimiter character, `string_list_split_in_place_multi()` uses `strcspn(2)` to move past the initial segment of characters comprised of any characters in the delimiting set. When only a single delimiting character is provided, `strpbrk(2)` (which is implemented with `strcspn(2)`) has equivalent performance to `strchr(2)`. Modern `strcspn(2)` implementations treat an empty delimiter or the singleton delimiter as a special case and fall back to calling strchrnul(). Both glibc[1] and musl[2] implement `strcspn(2)` this way. This change is one step to removing `strtok(2)` from the tree. Note that `string_list_split_in_place()` is not a strict replacement for `strtok()`, since it will happily turn sequential delimiter characters into empty entries in the resulting string_list. For example: string_list_split_in_place(&xs, "foo:;:bar:;:baz", ":;", -1) would yield a string list of: ["foo", "", "", "bar", "", "", "baz"] Callers that wish to emulate the behavior of strtok(2) more directly should call `string_list_remove_empty_items()` after splitting. To avoid regressions for the new multi-character delimter cases, update t0063 in this patch as well. [1]: https://sourceware.org/git/?p=glibc.git;a=blob;f=string/strcspn.c;hb=glibc-2.37#l35 [2]: https://git.musl-libc.org/cgit/musl/tree/src/string/strcspn.c?h=v1.2.3#n11 Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- string-list.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'string-list.h') diff --git a/string-list.h b/string-list.h index c7b0d5d000..77854840f7 100644 --- a/string-list.h +++ b/string-list.h @@ -270,5 +270,5 @@ int string_list_split(struct string_list *list, const char *string, * list->strdup_strings must *not* be set. */ int string_list_split_in_place(struct string_list *list, char *string, - int delim, int maxsplit); + const char *delim, int maxsplit); #endif /* STRING_LIST_H */ -- cgit v1.3 From 492ba81346cc45322d0c26bc927b01a34becf304 Mon Sep 17 00:00:00 2001 From: Taylor Blau Date: Mon, 24 Apr 2023 18:20:14 -0400 Subject: string-list: introduce `string_list_setlen()` It is sometimes useful to reduce the size of a `string_list`'s list of items without having to re-allocate them. For example, doing the following: struct strbuf buf = STRBUF_INIT; struct string_list parts = STRING_LIST_INIT_NO_DUP; while (strbuf_getline(&buf, stdin) != EOF) { parts.nr = 0; string_list_split_in_place(&parts, buf.buf, ":", -1); /* ... */ } string_list_clear(&parts, 0); is preferable over calling `string_list_clear()` on every iteration of the loop. This is because `string_list_clear()` causes us free our existing `items` array. This means that every time we call `string_list_split_in_place()`, the string-list internals re-allocate the same size array. Since in the above example we do not care about the individual parts after processing each line, it is much more efficient to pretend that there aren't any elements in the `string_list` by setting `list->nr` to 0 while leaving the list of elements allocated as-is. This allows `string_list_split_in_place()` to overwrite any existing entries without needing to free and re-allocate them. However, setting `list->nr` manually is not safe in all instances. There are a couple of cases worth worrying about: - If the `string_list` is initialized with `strdup_strings`, truncating the list can lead to overwriting strings which are allocated elsewhere. If there aren't any other pointers to those strings other than the ones inside of the `items` array, they will become unreachable and leak. (We could ourselves free the truncated items between string_list->items[nr] and `list->nr`, but no present or future callers would benefit from this additional complexity). - If the given `nr` is larger than the current value of `list->nr`, we'll trick the `string_list` into a state where it thinks there are more items allocated than there actually are, which can lead to undefined behavior if we try to read or write those entries. Guard against both of these by introducing a helper function which guards assignment of `list->nr` against each of the above conditions. Co-authored-by: Jeff King Signed-off-by: Jeff King Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano --- string-list.c | 9 +++++++++ string-list.h | 10 ++++++++++ 2 files changed, 19 insertions(+) (limited to 'string-list.h') diff --git a/string-list.c b/string-list.c index 5f5b60fe1c..0f8ac117fd 100644 --- a/string-list.c +++ b/string-list.c @@ -203,6 +203,15 @@ void string_list_clear_func(struct string_list *list, string_list_clear_func_t c list->nr = list->alloc = 0; } +void string_list_setlen(struct string_list *list, size_t nr) +{ + if (list->strdup_strings) + BUG("cannot setlen a string_list which owns its entries"); + if (nr > list->nr) + BUG("cannot grow a string_list with setlen"); + list->nr = nr; +} + struct string_list_item *string_list_append_nodup(struct string_list *list, char *string) { diff --git a/string-list.h b/string-list.h index 77854840f7..122b318641 100644 --- a/string-list.h +++ b/string-list.h @@ -134,6 +134,16 @@ typedef void (*string_list_clear_func_t)(void *p, const char *str); /** Call a custom clear function on each util pointer */ void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc); +/* + * Set the length of a string_list to `nr`, provided that (a) `list` + * does not own its own storage, and (b) that `nr` is no larger than + * `list->nr`. + * + * Useful when "shrinking" `list` to write over existing entries that + * are no longer used without reallocating. + */ +void string_list_setlen(struct string_list *list, size_t nr); + /** * Apply `func` to each item. If `func` returns nonzero, the * iteration aborts and the return value is propagated. -- cgit v1.3