[Rpm-maint] [PATCH 2/5] Reimplemented argvJoin function

[Alexey Tourbin]

Joining lines with consecutive rstrscat() calls was bad idea, because,
to append n-th argument, rstrscat() first has to calculate the length
of its previous result, that is, in a sense, the length of all its (n-1)
arguments.  Thus the complexity was O(n^2), due to arithmetic progression.

This change introduces a highly optimized version of argvJoin.  In
particular, strlen() call for each argv element is issued only once.
Also, the inner loop is tuned for the special case of empty or
single-character separator, to avoid extra memcpy per-element call.

Callgrind annotations for 'rpmspec -P anaconda.spec', previous commit:
363,974,889  PROGRAM TOTALS
232,675,214  glibc-2.16-75f0d304/string/../sysdeps/x86_64/strlen.S:__GI_strlen
 47,845,240  rpmio/argv.c:argvCount
 13,702,038  build/parseSpec.c:readLine
...

Callgrind annotations for 'rpmspec -P anaconda.spec', this commit:
130,717,478  PROGRAM TOTALS
47,862,184  rpmio/argv.c:argvCount
13,702,038  build/parseSpec.c:readLine
...
---
 rpmio/argv.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 54 insertions(+), 6 deletions(-)

diff --git a/rpmio/argv.c b/rpmio/argv.c
index d68422b..60ded3a 100644
--- a/rpmio/argv.c
+++ b/rpmio/argv.c
@@ -213,12 +213,60 @@ int argvSplit(ARGV_t * argvp, const char * str, const char * seps)
 
 char *argvJoin(ARGV_const_t argv, const char *sep)
 {
-    char *dest = NULL;
-    char * const *arg;
+    int argc = argvCount(argv);
+    if (argc < 1)
+	return NULL;
+
+    /* calculate lengths */
+    size_t lenbuf[32], *lens = lenbuf;
+    if (argc > 32)
+	lens = xmalloc(argc * sizeof(*lens));
+    size_t argvlen = 0;
+    for (int i = 0; i < argc; i++) {
+	size_t len = strlen(argv[i]);
+	lens[i] = len;
+	argvlen += len;
+    }
+
+    /* alloate destination buffer */
+    size_t seplen = sep ? strlen(sep) : 0;
+    char *dest = xmalloc(argvlen + seplen * (argc - 1) + 1);
+
+    /* first element */
+    size_t len = lens[0];
+    char *p = memcpy(dest, argv[0], len);
+    p += len;
+
+    /* remaining elements, with separators */
+    switch (seplen) {
+    case 0:
+	for (int i = 1; i < argc; i++) {
+	    len = lens[i];
+	    memcpy(p, argv[i], len);
+	    p += len;
+	}
+	break;
+    case 1:
+	for (int i = 1; i < argc; i++) {
+	    *p++ = *sep;
+	    len = lens[i];
+	    memcpy(p, argv[i], len);
+	    p += len;
+	}
+	break;
+    default:
+	for (int i = 1; i < argc; i++) {
+	    memcpy(p, sep, seplen);
+	    p += seplen;
+	    len = lens[i];
+	    memcpy(p, argv[i], len);
+	    p += len;
+	}
+	break;
+    }
 
-    for (arg = argv; arg && *arg; arg++) {
-	rstrscat(&dest, *arg, *(arg+1) ? sep : "", NULL);
-    } 
+    *p = '\0';
+    if (lens != lenbuf)
+	free(lens);
     return dest;
 }
-    
-- 
1.8.1