Re: [PATCH 01/10] strbuf_split: add a max parameter

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 13, 2011, 17:30 UTC
Message-ID: <7voc21od0g.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20110609155121.GA25507@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

> I am tempted to just call this new one strbuf_split and update all
> callers. There aren't that many.

Yes, that is indeed tempting, and because we have a new parameter the compiler will catch any new callers that pop up in a mismerge so that would be perfectly safe.

Show 17 quoted lines

> -struct strbuf **strbuf_split(const struct strbuf *sb, int delim)
> +struct strbuf **strbuf_split_max(const struct strbuf *sb, int delim, int max)
>  {
>  	int alloc = 2, pos = 0;
>  	char *n, *p;
> @@ -114,7 +114,10 @@ struct strbuf **strbuf_split(const struct strbuf *sb, int delim)
>  	p = n = sb->buf;
>  	while (n < sb->buf + sb->len) {
>  		int len;
> -		n = memchr(n, delim, sb->len - (n - sb->buf));
> +		if (max <= 0 || pos + 1 < max)
> +			n = memchr(n, delim, sb->len - (n - sb->buf));
> +		else
> +			n = NULL;
>  		if (pos + 1 >= alloc) {
>  			alloc = alloc * 2;
>  			ret = xrealloc(ret, sizeof(struct strbuf *) * alloc);

Hmm, even when we know the value of max, we go exponential, and even do so by hand without using ALLOC_GROW(). Somewhat sad.

Also do we currently rely on the bug that strbuf_split() returns (NULL,) instead of ("", NULL) when given an empty string? If not, perhaps...

 strbuf.c |   50 +++++++++++++++++++++++++++++++-------------------
 1 files changed, 31 insertions(+), 19 deletions(-)

diff --git a/strbuf.c b/strbuf.c
index 09c43ae..7a8ee3a 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -103,31 +103,43 @@ void strbuf_ltrim(struct strbuf *sb)
 	sb->buf[sb->len] = '\0';
 }
 
-struct strbuf **strbuf_split(const struct strbuf *sb, int delim)
+struct strbuf **strbuf_split_max(const struct strbuf *sb, int delim, int max)
 {
-	int alloc = 2, pos = 0;
 	char *n, *p;
-	struct strbuf **ret;
+	struct strbuf **ret = NULL;
 	struct strbuf *t;
-
-	ret = xcalloc(alloc, sizeof(struct strbuf *));
-	p = n = sb->buf;
-	while (n < sb->buf + sb->len) {
-		int len;
-		n = memchr(n, delim, sb->len - (n - sb->buf));
-		if (pos + 1 >= alloc) {
-			alloc = alloc * 2;
-			ret = xrealloc(ret, sizeof(struct strbuf *) * alloc);
+	int pass, count = 0;
+
+	for (pass = 0; pass < 2; pass++) {
+		/* First pass counts, second pass allocates and fills */
+		if (pass)
+			ret = xcalloc(count + 1 + !count, sizeof(struct strbuf *));
+		count = 0;
+		n = sb->buf;
+		while (n < sb->buf + sb->len) {
+			p = n;
+			if (max <= 0 || count + 1 < max)
+				n = memchr(n, delim, sb->len - (n - sb->buf));
+			else
+				n = NULL;
+			if (!n)
+				n = sb->buf + sb->len - 1;
+
+			if (pass) {
+				int len = n - p + 1;
+				t = xmalloc(sizeof(struct strbuf));
+				strbuf_init(t, len);
+				strbuf_add(t, p, len);
+				ret[count] = t;
+			}
+			count++;
+			n++;
 		}
-		if (!n)
-			n = sb->buf + sb->len - 1;
-		len = n - p + 1;
+	}
+	if (!count) {
 		t = xmalloc(sizeof(struct strbuf));
-		strbuf_init(t, len);
-		strbuf_add(t, p, len);
-		ret[pos] = t;
-		ret[++pos] = NULL;
-		p = ++n;
+		strbuf_init(t, 0);
+		ret[0] = t;
 	}
 	return ret;
 }