Re: [PATCH 01/10] strbuf_split: add a max parameter
- From
Jeff King <peff@peff.net>
- Date
- Jun 13, 2011, 19:20 UTC
- Message-ID
- <20110613192055.GE17845@sigill.intra.peff.net>
- In-Reply-To
- <7voc21od0g.fsf@alter.siamese.dyndns.org>
On Mon, Jun 13, 2011 at 10:30:07AM -0700, Junio C Hamano wrote:
Show 8 quoted lines
> 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.
Should we also change the naming later in the series to remain consistent with strbuf_add. IOW, to end up at:
struct strbuf **strbuf_split(const char *buf, int len, int delim, int max); struct strbuf **strbuf_split_str(const char *s, int delim, int max); struct strbuf **strbuf_split_buf(const struct strbuf *, int delim, int max);
(though I think consistency would also dictate "splitstr" and "splitbuf" without the extra underscore. Personally I find it a bit unreadable).
Show 20 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.Thanks for reminding me. I noticed it wasn't using ALLOC_GROW, but decided not to change it because I wanted to introduce an optimization later on not to grow beyond max. But then I forgot. :)
The optimization I was going to do was to simply allocate "max" slots at the beginning (if it's defined). You know you can't grow beyond that, and in most splits with a max, the caller is expecting all of them to be filled.
But your two-pass patch below is also reasonable.
> Also do we currently rely on the bug that strbuf_split() returns (NULL,)
> instead of ("", NULL) when given an empty string? If not, perhaps...I assumed that behavior was not a bug (and even had to avoid a segfault with it in a later series, as you saw). But thinking on it more, it really is one; splitting even a single character without delimiter ends up with a non-NULL portion, and I think the empty string should do the same.
> strbuf.c | 50 +++++++++++++++++++++++++++++++------------------- > 1 files changed, 31 insertions(+), 19 deletions(-)
I think your patch looks reasonable. In theory doing two passes over a very large buffer (e.g., splitting lines from a large commit message) might be slightly less efficient, but I imagine it is drowned out in the noise of malloc'ing strbufs.
> + for (pass = 0; pass < 2; pass++) {
> + /* First pass counts, second pass allocates and fills */Maybe it is just me, but I tend not to like writing multi-pass stuff like this as a for-loop, but instead to factor it into a function with an "actually allocate" parameter. I find it makes the code much more obvious.
Show 10 quoted lines
> + 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;
> }I think my test in 4/10 (which avoids the segfault by checking explicitly for NULL in the caller) should go with this part, and then 4/10 can go away.
-Peff