basic/strv: add optimizable version of strv_push/consume/extend

This will be helpful in cases where we are repeatedly adding entries
to a long strv and want to skip the iteration over old entries leading
to quadratic behaviour.

Note that we don't want to calculate the length if not necessary, so
the calculation is delayed until after we've checked that value is not
NULL.

3 files changed, 82 insertions, 15 deletions

diff --git a/src/basic/strv.c b/src/basic/strv.c
index 22f5402575..b2fe8d9d4e 100644
--- a/src/basic/strv.c
+++ b/src/basic/strv.c
@@ -403,27 +403,33 @@ char* strv_join_full(char * const *l, const char *separator, const char *prefix,
         return r;
 }
 
-int strv_push(char ***l, char *value) {
-        char **c;
-        size_t n;
+int strv_push_with_size(char ***l, size_t *n, char *value) {
+        /* n is a pointer to a variable to store the size of l.
+         * If not given (i.e. n is NULL or *n is SIZE_MAX), size will be calculated using strv_length().
+         * If n is not NULL, the size after the push will be returned.
+         * If value is empty, no action is taken and *n is not set. */
 
         if (!value)
                 return 0;
 
-        n = strv_length(*l);
+        size_t size = n ? *n : SIZE_MAX;
+        if (size == SIZE_MAX)
+                size = strv_length(*l);
 
         /* Check for overflow */
-        if (n > SIZE_MAX-2)
+        if (size > SIZE_MAX-2)
                 return -ENOMEM;
 
-        c = reallocarray(*l, GREEDY_ALLOC_ROUND_UP(n + 2), sizeof(char*));
+        char **c = reallocarray(*l, GREEDY_ALLOC_ROUND_UP(size + 2), sizeof(char*));
         if (!c)
                 return -ENOMEM;
 
-        c[n] = value;
-        c[n+1] = NULL;
+        c[size] = value;
+        c[size+1] = NULL;
 
         *l = c;
+        if (n)
+                *n = size + 1;
         return 0;
 }
 
@@ -484,10 +490,10 @@ int strv_insert(char ***l, size_t position, char *value) {
         return free_and_replace(*l, c);
 }
 
-int strv_consume(char ***l, char *value) {
+int strv_consume_with_size(char ***l, size_t *n, char *value) {
         int r;
 
-        r = strv_push(l, value);
+        r = strv_push_with_size(l, n, value);
         if (r < 0)
                 free(value);
 
@@ -529,7 +535,7 @@ int strv_prepend(char ***l, const char *value) {
         return strv_consume_prepend(l, v);
 }
 
-int strv_extend(char ***l, const char *value) {
+int strv_extend_with_size(char ***l, size_t *n, const char *value) {
         char *v;
 
         if (!value)
@@ -539,7 +545,7 @@ int strv_extend(char ***l, const char *value) {
         if (!v)
                 return -ENOMEM;
 
-        return strv_consume(l, v);
+        return strv_consume_with_size(l, n, v);
 }
 
 int strv_extend_front(char ***l, const char *value) {
diff --git a/src/basic/strv.h b/src/basic/strv.h
index b9563e8692..c567785cdb 100644
--- a/src/basic/strv.h
+++ b/src/basic/strv.h
@@ -35,18 +35,36 @@ size_t strv_length(char * const *l) _pure_;
 int strv_extend_strv(char ***a, char * const *b, bool filter_duplicates);
 int strv_extend_strv_concat(char ***a, char * const *b, const char *suffix);
 int strv_prepend(char ***l, const char *value);
-int strv_extend(char ***l, const char *value);
+
+/* _with_size() are lower-level functions where the size can be provided externally,
+ * which allows us to skip iterating over the strv to find the end, which saves
+ * a bit of time and reduces the complexity of appending from O(n²) to O(n). */
+
+int strv_extend_with_size(char ***l, size_t *n, const char *value);
+static inline int strv_extend(char ***l, const char *value) {
+        return strv_extend_with_size(l, NULL, value);
+}
+
 int strv_extendf(char ***l, const char *format, ...) _printf_(2,0);
 int strv_extend_front(char ***l, const char *value);
-int strv_push(char ***l, char *value);
+
+int strv_push_with_size(char ***l, size_t *n, char *value);
+static inline int strv_push(char ***l, char *value) {
+        return strv_push_with_size(l, NULL, value);
+}
 int strv_push_pair(char ***l, char *a, char *b);
+
 int strv_insert(char ***l, size_t position, char *value);
 
 static inline int strv_push_prepend(char ***l, char *value) {
         return strv_insert(l, 0, value);
 }
 
-int strv_consume(char ***l, char *value);
+int strv_consume_with_size(char ***l, size_t *n, char *value);
+static inline int strv_consume(char ***l, char *value) {
+        return strv_consume_with_size(l, NULL, value);
+}
+
 int strv_consume_pair(char ***l, char *a, char *b);
 int strv_consume_prepend(char ***l, char *value);
 
diff --git a/src/test/test-strv.c b/src/test/test-strv.c
index 331c277c35..b892396f05 100644
--- a/src/test/test-strv.c
+++ b/src/test/test-strv.c
@@ -601,6 +601,25 @@ TEST(strv_extend_strv) {
         assert_se(strv_length(n) == 4);
 }
 
+TEST(strv_extend_with_size) {
+        _cleanup_strv_free_ char **a = NULL;
+        size_t n = SIZE_MAX;
+
+        a = strv_new("test", "test1");
+        assert_se(a);
+
+        assert_se(strv_extend_with_size(&a, &n, "test2") >= 0);
+        assert_se(n == 3);
+        assert_se(strv_extend_with_size(&a, &n, "test3") >= 0);
+        assert_se(n == 4);
+
+        assert_se(streq(a[0], "test"));
+        assert_se(streq(a[1], "test1"));
+        assert_se(streq(a[2], "test2"));
+        assert_se(streq(a[3], "test3"));
+        assert_se(a[4] == NULL);
+}
+
 TEST(strv_extend) {
         _cleanup_strv_free_ char **a = NULL, **b = NULL;
 
@@ -746,6 +765,30 @@ TEST(strv_push_prepend) {
         assert_se(!a[5]);
 }
 
+TEST(strv_push_with_size) {
+        _cleanup_strv_free_ char **a = NULL;
+        size_t n = 0;
+        char *i, *j;
+
+        assert_se(i = strdup("foo"));
+        assert_se(strv_push_with_size(&a, &n, i) >= 0);
+        assert_se(n == 1);
+
+        assert_se(i = strdup("a"));
+        assert_se(j = strdup("b"));
+        assert_se(strv_push_with_size(&a, &n, i) >= 0);
+        assert_se(n == 2);
+        assert_se(strv_push_with_size(&a, &n, j) >= 0);
+        assert_se(n == 3);
+
+        assert_se(streq_ptr(a[0], "foo"));
+        assert_se(streq_ptr(a[1], "a"));
+        assert_se(streq_ptr(a[2], "b"));
+        assert_se(streq_ptr(a[3], NULL));
+
+        assert_se(n = strv_length(a));
+}
+
 TEST(strv_push) {
         _cleanup_strv_free_ char **a = NULL;
         char *i, *j;