git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v3 2/6] string-list: introduce `string_list_setlen()`

From
Taylor Blau <me@ttaylorr.com>
Date
Apr 24, 2023, 22:20 UTC
Message-ID
<ae8d0ce1f25f26da09f2e3f5bc68f85cc162ce64.1682374789.git.me@ttaylorr.com>
In-Reply-To
<cover.1682374789.git.me@ttaylorr.com>

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 <peff@peff.net>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 string-list.c |  9 +++++++++
 string-list.h | 10 ++++++++++
 2 files changed, 19 insertions(+)
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.
-- 
2.40.0.380.gd2df7d2365
Previous: Taylor BlauNext: Jeff King
Message 34 of 47 in “banned: mark `strok()`, `strtok_r()` as banned”
  1. 0/5 banned: mark `strok()`, `strtok_r()` as bannedTaylor Blau, Apr 13, 2023
  2. 1/5 string-list: introduce `string_list_split_in_place_multi()`Taylor Blau, Apr 13, 2023
  3. Jeff KingApr 18, 2023
  4. Taylor BlauApr 18, 2023
  5. 2/5 t/helper/test-hashmap.c: avoid using `strtok()`Taylor Blau, Apr 13, 2023
  6. Jeff KingApr 18, 2023
  7. Taylor BlauApr 18, 2023
  8. 3/5 t/helper/test-oidmap.c: avoid using `strtok()`Taylor Blau, Apr 13, 2023
  9. 4/5 t/helper/test-json-writer.c: avoid using `strtok()`Taylor Blau, Apr 13, 2023
  10. 5/5 banned.h: mark `strtok()`, `strtok_r()` as bannedTaylor Blau, Apr 13, 2023
  11. Junio C HamanoApr 14, 2023
  12. Chris TorekApr 14, 2023
  13. Taylor BlauApr 14, 2023
  14. 0/6 banned: mark `strok()` as bannedTaylor Blau, Apr 18, 2023
  15. 1/6 string-list: introduce `string_list_split_in_place_multi()`Taylor Blau, Apr 18, 2023
  16. Junio C HamanoApr 18, 2023
  17. Taylor BlauApr 18, 2023
  18. Jeff KingApr 22, 2023
  19. René ScharfeApr 22, 2023
  20. Jeff KingApr 23, 2023
  21. Junio C HamanoApr 24, 2023
  22. Taylor BlauApr 23, 2023
  23. Taylor BlauApr 23, 2023
  24. 2/6 string-list: introduce `string_list_setlen()`Taylor Blau, Apr 18, 2023
  25. Jeff KingApr 22, 2023
  26. 3/6 t/helper/test-hashmap.c: avoid using `strtok()`Taylor Blau, Apr 18, 2023
  27. Jeff KingApr 22, 2023
  28. Taylor BlauApr 24, 2023
  29. 4/6 t/helper/test-oidmap.c: avoid using `strtok()`Taylor Blau, Apr 18, 2023
  30. 5/6 t/helper/test-json-writer.c: avoid using `strtok()`Taylor Blau, Apr 18, 2023
  31. 6/6 banned.h: mark `strtok()` as bannedTaylor Blau, Apr 18, 2023
  32. 0/6 banned: mark `strok()`, `strtok_r()` as bannedTaylor Blau, Apr 24, 2023
  33. 1/6 string-list: multi-delimiter `string_list_split_in_place()`Taylor Blau, Apr 24, 2023
  34. 2/6 string-list: introduce `string_list_setlen()`Taylor Blau, Apr 24, 2023
  35. Jeff KingApr 25, 2023
  36. Taylor BlauApr 25, 2023
  37. 3/6 t/helper/test-hashmap.c: avoid using `strtok()`Taylor Blau, Apr 24, 2023
  38. 4/6 t/helper/test-oidmap.c: avoid using `strtok()`Taylor Blau, Apr 24, 2023
  39. 5/6 t/helper/test-json-writer.c: avoid using `strtok()`Taylor Blau, Apr 24, 2023
  40. Jeff HostetlerApr 25, 2023
  41. 6/6 banned.h: mark `strtok()` and `strtok_r()` as bannedTaylor Blau, Apr 24, 2023
  42. Chris TorekApr 24, 2023
  43. Taylor BlauApr 24, 2023
  44. Jeff KingApr 25, 2023
  45. Taylor BlauApr 25, 2023
  46. Jeff KingApr 25, 2023
  47. Taylor BlauApr 25, 2023

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.