{"thread":{"id":"32008","subject":"[PATCH 0/5] Use string_lists when processing notes","startedAt":"2012-11-04T07:07:05Z","lastAt":"2012-11-06T14:20:42Z","messageCount":8,"participants":["Michael Haggerty","Jeff King","Johan Herland"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"202501","messageId":"1352012830-13591-1-git-send-email-mhagger@alum.mit.edu","threadId":"32008","inReplyTo":null,"subject":"[PATCH 0/5] Use string_lists when processing notes","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T07:07:05Z","receivedAt":"2012-11-04T07:07:05Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"This simplifies the code.  Also, sort lines all at once (O(N lg N))\nrather than insertion sorting as lines are processed (O(N^2)) and fix\nthe handling of empty values in GIT_NOTES_DISPLAY_REF and\nGIT_NOTES_REWRITE_REF.\n\nMichael Haggerty (5):\n  string_list: add a function string_list_remove_empty_items()\n  Initialize sort_uniq_list using named constant\n  combine_notes_cat_sort_uniq(): sort and dedup lines all at once\n  notes: fix handling of colon-separated values\n  string_list_add_refs_from_colon_sep(): use string_list_split()\n\n Documentation/technical/api-string-list.txt |  9 ++++-\n notes.c                                     | 61 ++++++++++++-----------------\n string-list.c                               |  9 +++++\n string-list.h                               |  7 ++++\n 4 files changed, 49 insertions(+), 37 deletions(-)\n\n-- \n1.8.0\n"},{"id":"202505","messageId":"1352012830-13591-2-git-send-email-mhagger@alum.mit.edu","threadId":"32008","inReplyTo":"1352012830-13591-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 1/5] string_list: add a function string_list_remove_empty_items()","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T07:07:06Z","receivedAt":"2012-11-04T07:07:06Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n Documentation/technical/api-string-list.txt | 9 ++++++++-\n string-list.c                               | 9 +++++++++\n string-list.h                               | 7 +++++++\n 3 files changed, 24 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt\nindex 94d7a2b..7386bca 100644\n--- a/Documentation/technical/api-string-list.txt\n+++ b/Documentation/technical/api-string-list.txt\n@@ -38,7 +38,8 @@ member (you need this if you add things later) and you should set the\n   `unsorted_string_list_delete_item`.\n \n . Can remove items not matching a criterion from a sorted or unsorted\n-  list using `filter_string_list`.\n+  list using `filter_string_list`, or remove empty strings using\n+  `string_list_remove_empty_items`.\n \n . Finally it should free the list using `string_list_clear`.\n \n@@ -75,6 +76,12 @@ Functions\n \tto be deleted.  Preserve the order of the items that are\n \tretained.\n \n+`string_list_remove_empty_items`::\n+\n+\tRemove any empty strings from the list.  If free_util is true,\n+\tcall free() on the util members of any items that have to be\n+\tdeleted.  Preserve the order of the items that are retained.\n+\n `string_list_longest_prefix`::\n \n \tReturn the longest string within a string_list that is a\ndiff --git a/string-list.c b/string-list.c\nindex c54b816..397e6cf 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -136,6 +136,15 @@ void filter_string_list(struct string_list *list, int free_util,\n \tlist->nr = dst;\n }\n \n+static int item_is_not_empty(struct string_list_item *item, void *unused)\n+{\n+\treturn *item->string != '\\0';\n+}\n+\n+void string_list_remove_empty_items(struct string_list *list, int free_util) {\n+\tfilter_string_list(list, free_util, item_is_not_empty, NULL);\n+}\n+\n char *string_list_longest_prefix(const struct string_list *prefixes,\n \t\t\t\t const char *string)\n {\ndiff --git a/string-list.h b/string-list.h\nindex 5efd07b..c50b0d0 100644\n--- a/string-list.h\n+++ b/string-list.h\n@@ -39,6 +39,13 @@ void filter_string_list(struct string_list *list, int free_util,\n \t\t\tstring_list_each_func_t want, void *cb_data);\n \n /*\n+ * Remove any empty strings from the list.  If free_util is true, call\n+ * free() on the util members of any items that have to be deleted.\n+ * Preserve the order of the items that are retained.\n+ */\n+void string_list_remove_empty_items(struct string_list *list, int free_util);\n+\n+/*\n  * Return the longest string in prefixes that is a prefix (in the\n  * sense of prefixcmp()) of string, or NULL if no such prefix exists.\n  * This function does not require the string_list to be sorted (it\n-- \n1.8.0\n"},{"id":"202502","messageId":"1352012830-13591-3-git-send-email-mhagger@alum.mit.edu","threadId":"32008","inReplyTo":"1352012830-13591-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 2/5] Initialize sort_uniq_list using named constant","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T07:07:07Z","receivedAt":"2012-11-04T07:07:07Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n notes.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/notes.c b/notes.c\nindex bc454e1..8652f8f 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -901,7 +901,7 @@ static int string_list_join_lines_helper(struct string_list_item *item,\n int combine_notes_cat_sort_uniq(unsigned char *cur_sha1,\n \t\tconst unsigned char *new_sha1)\n {\n-\tstruct string_list sort_uniq_list = { NULL, 0, 0, 1 };\n+\tstruct string_list sort_uniq_list = STRING_LIST_INIT_DUP;\n \tstruct strbuf buf = STRBUF_INIT;\n \tint ret = 1;\n \n-- \n1.8.0\n"},{"id":"202504","messageId":"1352012830-13591-4-git-send-email-mhagger@alum.mit.edu","threadId":"32008","inReplyTo":"1352012830-13591-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 3/5] combine_notes_cat_sort_uniq(): sort and dedup lines all at once","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T07:07:08Z","receivedAt":"2012-11-04T07:07:08Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Instead of reading lines one by one and insertion-sorting them into a\nstring_list, read all of the lines, sort them, then remove duplicates.\nAside from being less code, this reduces the complexity from O(N^2) to\nO(N lg N) in the total number of lines.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n notes.c | 38 ++++++++++++++++----------------------\n 1 file changed, 16 insertions(+), 22 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 8652f8f..62f8f6f 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -848,15 +848,16 @@ int combine_notes_ignore(unsigned char *cur_sha1,\n \treturn 0;\n }\n \n-static int string_list_add_note_lines(struct string_list *sort_uniq_list,\n+/*\n+ * Add the lines from the named object to list, with trailing\n+ * newlines removed.\n+ */\n+static int string_list_add_note_lines(struct string_list *list,\n \t\t\t\t      const unsigned char *sha1)\n {\n \tchar *data;\n \tunsigned long len;\n \tenum object_type t;\n-\tstruct strbuf buf = STRBUF_INIT;\n-\tstruct strbuf **lines = NULL;\n-\tint i, list_index;\n \n \tif (is_null_sha1(sha1))\n \t\treturn 0;\n@@ -868,24 +869,14 @@ static int string_list_add_note_lines(struct string_list *sort_uniq_list,\n \t\treturn t != OBJ_BLOB || !data;\n \t}\n \n-\tstrbuf_attach(&buf, data, len, len + 1);\n-\tlines = strbuf_split(&buf, '\\n');\n-\n-\tfor (i = 0; lines[i]; i++) {\n-\t\tif (lines[i]->buf[lines[i]->len - 1] == '\\n')\n-\t\t\tstrbuf_setlen(lines[i], lines[i]->len - 1);\n-\t\tif (!lines[i]->len)\n-\t\t\tcontinue; /* skip empty lines */\n-\t\tlist_index = string_list_find_insert_index(sort_uniq_list,\n-\t\t\t\t\t\t\t   lines[i]->buf, 0);\n-\t\tif (list_index < 0)\n-\t\t\tcontinue; /* skip duplicate lines */\n-\t\tstring_list_insert_at_index(sort_uniq_list, list_index,\n-\t\t\t\t\t    lines[i]->buf);\n-\t}\n-\n-\tstrbuf_list_free(lines);\n-\tstrbuf_release(&buf);\n+\t/*\n+\t * If the last line of the file is EOL-terminated, this will\n+\t * add an empty string to the list.  But it will be removed\n+\t * later, along with any empty strings that came from empty\n+\t * lines within the file.\n+\t */\n+\tstring_list_split(list, data, '\\n', -1);\n+\tfree(data);\n \treturn 0;\n }\n \n@@ -910,6 +901,9 @@ int combine_notes_cat_sort_uniq(unsigned char *cur_sha1,\n \t\tgoto out;\n \tif (string_list_add_note_lines(&sort_uniq_list, new_sha1))\n \t\tgoto out;\n+\tstring_list_remove_empty_items(&sort_uniq_list, 0);\n+\tsort_string_list(&sort_uniq_list);\n+\tstring_list_remove_duplicates(&sort_uniq_list, 0);\n \n \t/* create a new blob object from sort_uniq_list */\n \tif (for_each_string_list(&sort_uniq_list,\n-- \n1.8.0\n"},{"id":"202503","messageId":"1352012830-13591-5-git-send-email-mhagger@alum.mit.edu","threadId":"32008","inReplyTo":"1352012830-13591-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 4/5] notes: fix handling of colon-separated values","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T07:07:09Z","receivedAt":"2012-11-04T07:07:09Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"The substrings output by strbuf_split() include the ':' delimiters.\nWhen processing GIT_NOTES_DISPLAY_REF and GIT_NOTES_REWRITE_REF, strip\noff the delimiter character *before* checking whether the substring is\nempty rather than after, so that empty strings within the list are\nalso skipped.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n notes.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 62f8f6f..63b2a09 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -951,10 +951,10 @@ void string_list_add_refs_from_colon_sep(struct string_list *list,\n \tsplit = strbuf_split(&globbuf, ':');\n \n \tfor (i = 0; split[i]; i++) {\n+\t\tif (split[i]->len && split[i]->buf[split[i]->len-1] == ':')\n+\t\t\tstrbuf_setlen(split[i], split[i]->len-1);\n \t\tif (!split[i]->len)\n \t\t\tcontinue;\n-\t\tif (split[i]->buf[split[i]->len-1] == ':')\n-\t\t\tstrbuf_setlen(split[i], split[i]->len-1);\n \t\tstring_list_add_refs_by_glob(list, split[i]->buf);\n \t}\n \n-- \n1.8.0\n"},{"id":"202506","messageId":"1352012830-13591-6-git-send-email-mhagger@alum.mit.edu","threadId":"32008","inReplyTo":"1352012830-13591-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 5/5] string_list_add_refs_from_colon_sep(): use string_list_split()","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-11-04T07:07:10Z","receivedAt":"2012-11-04T07:07:10Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"It makes for simpler code than strbuf_split().\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n notes.c | 21 ++++++++-------------\n 1 file changed, 8 insertions(+), 13 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 63b2a09..b823701 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -943,23 +943,18 @@ void string_list_add_refs_by_glob(struct string_list *list, const char *glob)\n void string_list_add_refs_from_colon_sep(struct string_list *list,\n \t\t\t\t\t const char *globs)\n {\n-\tstruct strbuf globbuf = STRBUF_INIT;\n-\tstruct strbuf **split;\n+\tstruct string_list split = STRING_LIST_INIT_NODUP;\n+\tchar *globs_copy = xstrdup(globs);\n \tint i;\n \n-\tstrbuf_addstr(&globbuf, globs);\n-\tsplit = strbuf_split(&globbuf, ':');\n+\tstring_list_split_in_place(&split, globs_copy, ':', -1);\n+\tstring_list_remove_empty_items(&split, 0);\n \n-\tfor (i = 0; split[i]; i++) {\n-\t\tif (split[i]->len && split[i]->buf[split[i]->len-1] == ':')\n-\t\t\tstrbuf_setlen(split[i], split[i]->len-1);\n-\t\tif (!split[i]->len)\n-\t\t\tcontinue;\n-\t\tstring_list_add_refs_by_glob(list, split[i]->buf);\n-\t}\n+\tfor (i = 0; i < split.nr; i++)\n+\t\tstring_list_add_refs_by_glob(list, split.items[i].string);\n \n-\tstrbuf_list_free(split);\n-\tstrbuf_release(&globbuf);\n+\tstring_list_clear(&split, 0);\n+\tfree(globs_copy);\n }\n \n static int notes_display_config(const char *k, const char *v, void *cb)\n-- \n1.8.0\n"},{"id":"202510","messageId":"20121104115750.GC336@sigill.intra.peff.net","threadId":"32008","inReplyTo":"1352012830-13591-6-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 5/5] string_list_add_refs_from_colon_sep(): use string_list_split()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-04T11:57:50Z","receivedAt":"2012-11-04T11:57:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Nov 04, 2012 at 08:07:10AM +0100, Michael Haggerty wrote:\n\n> It makes for simpler code than strbuf_split().\n\nAgreed.\n\nI wonder how useful the strbuf_split functions really are. Callers might\ncare about splitting content in a strbuf, but in general, getting a list\nof strbufs out is just a hassle, and a string_list makes more sense.\n\nIt's probably not worth spending time converting them unless we happen\nto be working in the area, though.\n\n-Peff\n"},{"id":"202593","messageId":"CALKQrgf2TbHeGm1na92vgNr1cJeY8RRrnYCBcMVRSFEWc8njNg@mail.gmail.com","threadId":"32008","inReplyTo":"5098C29A.4010901@alum.mit.edu","subject":"Re: [PATCH 0/5] Use string_lists when processing notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2012-11-06T14:20:42Z","receivedAt":"2012-11-06T14:20:42Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Tue, Nov 6, 2012 at 8:56 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> On 11/04/2012 10:05 PM, Johan Herland wrote:\n>> On Sun, Nov 4, 2012 at 8:07 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>>> This simplifies the code.  Also, sort lines all at once (O(N lg N))\n>>> rather than insertion sorting as lines are processed (O(N^2)) and fix\n>>> the handling of empty values in GIT_NOTES_DISPLAY_REF and\n>>> GIT_NOTES_REWRITE_REF.\n>>>\n>>> Michael Haggerty (5):\n>>>   string_list: add a function string_list_remove_empty_items()\n>>>   Initialize sort_uniq_list using named constant\n>>>   combine_notes_cat_sort_uniq(): sort and dedup lines all at once\n>>>   notes: fix handling of colon-separated values\n>>>   string_list_add_refs_from_colon_sep(): use string_list_split()\n>>\n>> Series looks good to me.\n>>\n>> Acked-by: Johan Herland <johan@herland.net>\n>\n> Thanks for reviewing the series.\n>\n> Was it intentional that you didn't CC the mailing list?\n\nNo, not at all. Sorry.\n\nHere we go again, with the appropriate CC:\n\nAcked-by: Johan Herland <johan@herland.net>\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"}]}