{"thread":{"id":"32007","subject":"[PATCH 1/4] strbuf_split_buf(): use ALLOC_GROW()","startedAt":"2012-11-04T06:46:50Z","lastAt":"2012-11-08T16:38:03Z","messageCount":9,"participants":["Michael Haggerty","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"202498","messageId":"1352011614-29334-1-git-send-email-mhagger@alum.mit.edu","threadId":"32007","inReplyTo":null,"subject":"[PATCH 0/4] Simplify and document strbuf_split() functions","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T06:46:50Z","receivedAt":"2012-11-04T06:46:50Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"The strbuf_split() family of functions was completely undocumented.\nAdd documentation and also simplify the definition of\nstrbuf_split_buf().\n\nMichael Haggerty (4):\n strbuf_split_buf(): use ALLOC_GROW()\n strbuf_split_buf(): simplify iteration\n strbuf_split*(): rename \"delim\" parameter to \"terminator\"\n strbuf_split*(): document functions\n\n Documentation/technical/api-strbuf.txt | 16 ++++++++++++\n strbuf.c | 39 ++++++++++++---------------\n strbuf.h | 48 +++++++++++++++++++++++++++++-----\n 3 files changed, 74 insertions(+), 29 deletions(-)\n\n-- \n1.8.0\n"},{"id":"202496","messageId":"1352011614-29334-2-git-send-email-mhagger@alum.mit.edu","threadId":"32007","inReplyTo":"1352011614-29334-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 1/4] strbuf_split_buf(): use ALLOC_GROW()","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T06:46:51Z","receivedAt":"2012-11-04T06:46:51Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Use ALLOC_GROW() rather than inline code to manage memory in\nstrbuf_split_buf(). Rename \"pos\" to \"nr\" because it better describes\nthe use of the variable and it better conforms to the \"ALLOC_GROW\"\nidiom.\n\nAlso, instead of adding a sentinal NULL value after each entry is\nadded to the list, only add it once after all of the entries have been\nadded.\n\nSigned-off-by: Michael Haggerty \n---\n strbuf.c | 17 +++++++----------\n 1 file changed, 7 insertions(+), 10 deletions(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 4b9e30c..5256c2a 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -108,33 +108,30 @@ void strbuf_ltrim(struct strbuf *sb)\n \n struct strbuf **strbuf_split_buf(const char *str, size_t slen, int delim, int max)\n {\n-\tint alloc = 2, pos = 0;\n+\tstruct strbuf **ret = NULL;\n+\tsize_t nr = 0, alloc = 0;\n \tconst char *n, *p;\n-\tstruct strbuf **ret;\n \tstruct strbuf *t;\n \n-\tret = xcalloc(alloc, sizeof(struct strbuf *));\n \tp = n = str;\n \twhile (n < str + slen) {\n \t\tint len;\n-\t\tif (max <= 0 || pos + 1 < max)\n+\t\tif (max <= 0 || nr + 1 < max)\n \t\t\tn = memchr(n, delim, slen - (n - str));\n \t\telse\n \t\t\tn = NULL;\n-\t\tif (pos + 1 >= alloc) {\n-\t\t\talloc = alloc * 2;\n-\t\t\tret = xrealloc(ret, sizeof(struct strbuf *) * alloc);\n-\t\t}\n \t\tif (!n)\n \t\t\tn = str + slen - 1;\n \t\tlen = n - p + 1;\n \t\tt = xmalloc(sizeof(struct strbuf));\n \t\tstrbuf_init(t, len);\n \t\tstrbuf_add(t, p, len);\n-\t\tret[pos] = t;\n-\t\tret[++pos] = NULL;\n+\t\tALLOC_GROW(ret, nr + 2, alloc);\n+\t\tret[nr++] = t;\n \t\tp = ++n;\n \t}\n+\tALLOC_GROW(ret, nr + 1, alloc); /* In case string was empty */\n+\tret[nr] = NULL;\n \treturn ret;\n }\n \n-- \n1.8.0\n"},{"id":"202500","messageId":"1352011614-29334-3-git-send-email-mhagger@alum.mit.edu","threadId":"32007","inReplyTo":"1352011614-29334-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 2/4] strbuf_split_buf(): simplify iteration","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T06:46:52Z","receivedAt":"2012-11-04T06:46:52Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"While iterating, update str and slen to keep track of the part of the\nstring that hasn't been processed yet rather than computing things\nrelative to the start of the original string. This eliminates one\nlocal variable, reduces the scope of another, and reduces the amount\nof arithmetic needed within the loop.\n\nSigned-off-by: Michael Haggerty \n---\n strbuf.c | 23 ++++++++++-------------\n 1 file changed, 10 insertions(+), 13 deletions(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 5256c2a..c7cd529 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -110,25 +110,22 @@ struct strbuf **strbuf_split_buf(const char *str, size_t slen, int delim, int ma\n {\n \tstruct strbuf **ret = NULL;\n \tsize_t nr = 0, alloc = 0;\n-\tconst char *n, *p;\n \tstruct strbuf *t;\n \n-\tp = n = str;\n-\twhile (n < str + slen) {\n-\t\tint len;\n-\t\tif (max <= 0 || nr + 1 < max)\n-\t\t\tn = memchr(n, delim, slen - (n - str));\n-\t\telse\n-\t\t\tn = NULL;\n-\t\tif (!n)\n-\t\t\tn = str + slen - 1;\n-\t\tlen = n - p + 1;\n+\twhile (slen) {\n+\t\tint len = slen;\n+\t\tif (max <= 0 || nr + 1 < max) {\n+\t\t\tconst char *end = memchr(str, delim, slen);\n+\t\t\tif (end)\n+\t\t\t\tlen = end - str + 1;\n+\t\t}\n \t\tt = xmalloc(sizeof(struct strbuf));\n \t\tstrbuf_init(t, len);\n-\t\tstrbuf_add(t, p, len);\n+\t\tstrbuf_add(t, str, len);\n \t\tALLOC_GROW(ret, nr + 2, alloc);\n \t\tret[nr++] = t;\n-\t\tp = ++n;\n+\t\tstr += len;\n+\t\tslen -= len;\n \t}\n \tALLOC_GROW(ret, nr + 1, alloc); /* In case string was empty */\n \tret[nr] = NULL;\n-- \n1.8.0\n"},{"id":"202497","messageId":"1352011614-29334-4-git-send-email-mhagger@alum.mit.edu","threadId":"32007","inReplyTo":"1352011614-29334-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 3/4] strbuf_split*(): rename \"delim\" parameter to \"terminator\"","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T06:46:53Z","receivedAt":"2012-11-04T06:46:53Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"The word \"delimiter\" suggests that the argument separates the\nsubstrings, whereas in fact (1) the delimiter characters are included\nin the output, and (2) if the input string ends with the delimiter,\nthen the output does not include a final empty string. So rename the\n\"delim\" arguments of the strbuf_split() family of functions to\n\"terminator\", which is more suggestive of how it is used.\n\nSigned-off-by: Michael Haggerty \n---\n strbuf.c | 5 +++--\n strbuf.h | 15 ++++++++-------\n 2 files changed, 11 insertions(+), 9 deletions(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex c7cd529..05d0693 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -106,7 +106,8 @@ void strbuf_ltrim(struct strbuf *sb)\n \tsb->buf[sb->len] = '\\0';\n }\n \n-struct strbuf **strbuf_split_buf(const char *str, size_t slen, int delim, int max)\n+struct strbuf **strbuf_split_buf(const char *str, size_t slen,\n+\t\t\t\t int terminator, int max)\n {\n \tstruct strbuf **ret = NULL;\n \tsize_t nr = 0, alloc = 0;\n@@ -115,7 +116,7 @@ struct strbuf **strbuf_split_buf(const char *str, size_t slen, int delim, int ma\n \twhile (slen) {\n \t\tint len = slen;\n \t\tif (max <= 0 || nr + 1 < max) {\n-\t\t\tconst char *end = memchr(str, delim, slen);\n+\t\t\tconst char *end = memchr(str, terminator, slen);\n \t\t\tif (end)\n \t\t\t\tlen = end - str + 1;\n \t\t}\ndiff --git a/strbuf.h b/strbuf.h\nindex be941ee..c896a47 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -45,20 +45,21 @@ extern void strbuf_ltrim(struct strbuf *);\n extern int strbuf_cmp(const struct strbuf *, const struct strbuf *);\n \n extern struct strbuf **strbuf_split_buf(const char *, size_t,\n-\t\t\t\t\tint delim, int max);\n+\t\t\t\t\tint terminator, int max);\n static inline struct strbuf **strbuf_split_str(const char *str,\n-\t\t\t\t\t int delim, int max)\n+\t\t\t\t\t int terminator, int max)\n {\n-\treturn strbuf_split_buf(str, strlen(str), delim, max);\n+\treturn strbuf_split_buf(str, strlen(str), terminator, max);\n }\n static inline struct strbuf **strbuf_split_max(const struct strbuf *sb,\n-\t\t\t\t\t\tint delim, int max)\n+\t\t\t\t\t\tint terminator, int max)\n {\n-\treturn strbuf_split_buf(sb->buf, sb->len, delim, max);\n+\treturn strbuf_split_buf(sb->buf, sb->len, terminator, max);\n }\n-static inline struct strbuf **strbuf_split(const struct strbuf *sb, int delim)\n+static inline struct strbuf **strbuf_split(const struct strbuf *sb,\n+\t\t\t\t\t int terminator)\n {\n-\treturn strbuf_split_max(sb, delim, 0);\n+\treturn strbuf_split_max(sb, terminator, 0);\n }\n extern void strbuf_list_free(struct strbuf **);\n \n-- \n1.8.0\n"},{"id":"202499","messageId":"1352011614-29334-5-git-send-email-mhagger@alum.mit.edu","threadId":"32007","inReplyTo":"1352011614-29334-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 4/4] strbuf_split*(): document functions","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T06:46:54Z","receivedAt":"2012-11-04T06:46:54Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Document strbuf_split_buf(), strbuf_split_str(), strbuf_split_max(),\nstrbuf_split(), and strbuf_list_free() in the header file and in\napi-strbuf.txt. (These functions were previously completely\nundocumented.)\n\nSigned-off-by: Michael Haggerty \n---\n Documentation/technical/api-strbuf.txt | 16 ++++++++++++++++\n strbuf.h | 33 +++++++++++++++++++++++++++++++++\n 2 files changed, 49 insertions(+)\n\ndiff --git a/Documentation/technical/api-strbuf.txt b/Documentation/technical/api-strbuf.txt\nindex 95a8bf3..84686b5 100644\n--- a/Documentation/technical/api-strbuf.txt\n+++ b/Documentation/technical/api-strbuf.txt\n@@ -279,6 +279,22 @@ same behaviour as well.\n \tStrip whitespace from a buffer. The second parameter controls if\n \tcomments are considered contents to be removed or not.\n \n+`strbuf_split_buf`::\n+`strbuf_split_str`::\n+`strbuf_split_max`::\n+`strbuf_split`::\n+\n+\tSplit a string or strbuf into a list of strbufs at a specified\n+\tterminator character. The returned substrings include the\n+\tterminator characters. Some of these functions take a `max`\n+\tparameter, which, if positive, limits the output to that\n+\tnumber of substrings.\n+\n+`strbuf_list_free`::\n+\n+\tFree a list of strbufs (for example, the return values of the\n+\t`strbuf_split()` functions).\n+\n `launch_editor`::\n \n \tLaunch the user preferred editor to edit a file and fill the buffer\ndiff --git a/strbuf.h b/strbuf.h\nindex c896a47..aa386c6 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -44,23 +44,56 @@ extern void strbuf_rtrim(struct strbuf *);\n extern void strbuf_ltrim(struct strbuf *);\n extern int strbuf_cmp(const struct strbuf *, const struct strbuf *);\n \n+/*\n+ * Split str (of length slen) at the specified terminator character.\n+ * Return a null-terminated array of pointers to strbuf objects\n+ * holding the substrings. The substrings include the terminator,\n+ * except for the last substring, which might be unterminated if the\n+ * original string did not end with a terminator. If max is positive,\n+ * then split the string into at most max substrings (with the last\n+ * substring containing everything following the (max-1)th terminator\n+ * character).\n+ *\n+ * For lighter-weight alternatives, see string_list_split() and\n+ * string_list_split_in_place().\n+ */\n extern struct strbuf **strbuf_split_buf(const char *, size_t,\n \t\t\t\t\tint terminator, int max);\n+\n+/*\n+ * Split a NUL-terminated string at the specified terminator\n+ * character. See strbuf_split_buf() for more information.\n+ */\n static inline struct strbuf **strbuf_split_str(const char *str,\n \t\t\t\t\t int terminator, int max)\n {\n \treturn strbuf_split_buf(str, strlen(str), terminator, max);\n }\n+\n+/*\n+ * Split a strbuf at the specified terminator character. See\n+ * strbuf_split_buf() for more information.\n+ */\n static inline struct strbuf **strbuf_split_max(const struct strbuf *sb,\n \t\t\t\t\t\tint terminator, int max)\n {\n \treturn strbuf_split_buf(sb->buf, sb->len, terminator, max);\n }\n+\n+/*\n+ * Split a strbuf at the specified terminator character. See\n+ * strbuf_split_buf() for more information.\n+ */\n static inline struct strbuf **strbuf_split(const struct strbuf *sb,\n \t\t\t\t\t int terminator)\n {\n \treturn strbuf_split_max(sb, terminator, 0);\n }\n+\n+/*\n+ * Free a NULL-terminated list of strbufs (for example, the return\n+ * values of the strbuf_split*() functions).\n+ */\n extern void strbuf_list_free(struct strbuf **);\n \n /*----- add data in your buffer -----*/\n-- \n1.8.0\n"},{"id":"202508","messageId":"20121104114101.GA336@sigill.intra.peff.net","threadId":"32007","inReplyTo":"1352011614-29334-2-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 1/4] strbuf_split_buf(): use ALLOC_GROW()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-04T11:41:01Z","receivedAt":"2012-11-04T11:41:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Nov 04, 2012 at 07:46:51AM +0100, Michael Haggerty wrote:\n\n> Use ALLOC_GROW() rather than inline code to manage memory in\n> strbuf_split_buf(). Rename \"pos\" to \"nr\" because it better describes\n> the use of the variable and it better conforms to the \"ALLOC_GROW\"\n> idiom.\n\nI suspect this was not used originally because ALLOC_GROW relies on\nalloc_nr, which does fast growth early on. At (x+16)*3/2, we end up with\n24 slots for the first allocation. We are typically splitting 1 or 2\nvalues.\n\nIt probably doesn't make a big difference in practice, though, as we're\ntalking about wasting less than 200 bytes on a 64-bit platform, and we\ndo not tend to keep large numbers of split lists around.\n\n-Peff\n"},{"id":"202509","messageId":"20121104115043.GB336@sigill.intra.peff.net","threadId":"32007","inReplyTo":"1352011614-29334-1-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 0/4] Simplify and document strbuf_split() functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-04T11:50:44Z","receivedAt":"2012-11-04T11:50:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Nov 04, 2012 at 07:46:50AM +0100, Michael Haggerty wrote:\n\n> The strbuf_split() family of functions was completely undocumented.\n> Add documentation and also simplify the definition of\n> strbuf_split_buf().\n\nThanks. Looks good overall, even with the comments I raised for patch 1\n(I think it is not a big deal, and even if it does become a big deal,\nthe right fix is probably to make alloc_nr smarter about early growth).\n\n-Peff\n"},{"id":"202583","messageId":"5098C21F.6030803@alum.mit.edu","threadId":"32007","inReplyTo":"20121104114101.GA336@sigill.intra.peff.net","subject":"Re: [PATCH 1/4] strbuf_split_buf(): use ALLOC_GROW()","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-06T07:54:07Z","receivedAt":"2012-11-06T07:54:07Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 11/04/2012 12:41 PM, Jeff King wrote:\n> On Sun, Nov 04, 2012 at 07:46:51AM +0100, Michael Haggerty wrote:\n> \n>> Use ALLOC_GROW() rather than inline code to manage memory in\n>> strbuf_split_buf(). Rename \"pos\" to \"nr\" because it better describes\n>> the use of the variable and it better conforms to the \"ALLOC_GROW\"\n>> idiom.\n> \n> I suspect this was not used originally because ALLOC_GROW relies on\n> alloc_nr, which does fast growth early on. At (x+16)*3/2, we end up with\n> 24 slots for the first allocation. We are typically splitting 1 or 2\n> values.\n> \n> It probably doesn't make a big difference in practice, though, as we're\n> talking about wasting less than 200 bytes on a 64-bit platform, and we\n> do not tend to keep large numbers of split lists around.\n\nI did a little bit of archeology, and found out that\n\n* ALLOC_GROW() did indeed exist when this code was developed, so it\n *could have* been used.\n\n* OTOH, I didn't find any indication on the mailing list that the\n choice not to use ALLOC_GROW() was a conscious decision.\n\nSo history doesn't give us much guidance.\n\nIf the size of the initial allocation is a concern, then I would suggest\nadding a macro like ALLOC_SET_SIZE(ary,nr,alloc) that could be called to\ninitialize the size to some number less than 24. Such a macro might be\nuseful elsewhere, too. It wouldn't, of course, slow the growth rate\n*after* the first allocation.\n\nFWIW, the \"max\" parameter of strbuf_split*() is only used in one place,\nthough strbuf_split*() is used in some other places where not too many\nsubstrings would be expected.\n\nI am working on some patch series that will eliminate even more uses of\nstrbuf_split*(), so I won't work more on optimizing its resource usage\nunless somebody gives me a stronger nudge.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"202651","messageId":"20121108163803.GE15560@sigill.intra.peff.net","threadId":"32007","inReplyTo":"5098C21F.6030803@alum.mit.edu","subject":"Re: [PATCH 1/4] strbuf_split_buf(): use ALLOC_GROW()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-08T16:38:03Z","receivedAt":"2012-11-08T16:38:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 06, 2012 at 08:54:07AM +0100, Michael Haggerty wrote:\n\n> > I suspect this was not used originally because ALLOC_GROW relies on\n> > alloc_nr, which does fast growth early on. At (x+16)*3/2, we end up with\n> > 24 slots for the first allocation. We are typically splitting 1 or 2\n> > values.\n> > \n> > It probably doesn't make a big difference in practice, though, as we're\n> > talking about wasting less than 200 bytes on a 64-bit platform, and we\n> > do not tend to keep large numbers of split lists around.\n> \n> I did a little bit of archeology, and found out that\n> \n> * ALLOC_GROW() did indeed exist when this code was developed, so it\n> *could have* been used.\n> \n> * OTOH, I didn't find any indication on the mailing list that the\n> choice not to use ALLOC_GROW() was a conscious decision.\n> \n> So history doesn't give us much guidance.\n\nThanks for digging.\n\n> If the size of the initial allocation is a concern, then I would suggest\n> adding a macro like ALLOC_SET_SIZE(ary,nr,alloc) that could be called to\n> initialize the size to some number less than 24. Such a macro might be\n> useful elsewhere, too. It wouldn't, of course, slow the growth rate\n> *after* the first allocation.\n\nI think we are getting into premature optimization territory. Let's\ntake your series as a cleanup, and we can worry about micro-optimizing\nthe allocation if and when it ever becomes an issue.\n\n-Peff\n"}]}