Merge branch 'mh/notes-string-list'

Improve the asymptotic performance of the cat_sort_uniq notes merge
strategy.

* mh/notes-string-list:
string_list_add_refs_from_colon_sep(): use string_list_split()
notes: fix handling of colon-separated values
combine_notes_cat_sort_uniq(): sort and dedup lines all at once
Initialize sort_uniq_list using named constant
string_list: add a function string_list_remove_empty_items()

diff --combined notes.c
index ee8f01f1d5c1dcb39c40eee443eddaedde380d20,b823701d90fd59d2021779d26b05500a72d0bebe..19b0eaada28ffc603d0bbc1914303fd1de6bf22c
--- 1/notes.c
--- 2/notes.c
+++ b/notes.c
@@@ -848,15 -848,16 +848,16 @@@ int combine_notes_ignore(unsigned char 
        return 0;
  }
  
- static int string_list_add_note_lines(struct string_list *sort_uniq_list,
+ /*
+  * Add the lines from the named object to list, with trailing
+  * newlines removed.
+  */
+ static int string_list_add_note_lines(struct string_list *list,
                                      const unsigned char *sha1)
  {
        char *data;
        unsigned long len;
        enum object_type t;
-       struct strbuf buf = STRBUF_INIT;
-       struct strbuf **lines = NULL;
-       int i, list_index;
  
        if (is_null_sha1(sha1))
                return 0;
@@@ -868,24 -869,14 +869,14 @@@
                return t != OBJ_BLOB || !data;
        }
  
-       strbuf_attach(&buf, data, len, len + 1);
-       lines = strbuf_split(&buf, '\n');
- 
-       for (i = 0; lines[i]; i++) {
-               if (lines[i]->buf[lines[i]->len - 1] == '\n')
-                       strbuf_setlen(lines[i], lines[i]->len - 1);
-               if (!lines[i]->len)
-                       continue; /* skip empty lines */
-               list_index = string_list_find_insert_index(sort_uniq_list,
-                                                          lines[i]->buf, 0);
-               if (list_index < 0)
-                       continue; /* skip duplicate lines */
-               string_list_insert_at_index(sort_uniq_list, list_index,
-                                           lines[i]->buf);
-       }
- 
-       strbuf_list_free(lines);
-       strbuf_release(&buf);
+       /*
+        * If the last line of the file is EOL-terminated, this will
+        * add an empty string to the list.  But it will be removed
+        * later, along with any empty strings that came from empty
+        * lines within the file.
+        */
+       string_list_split(list, data, '\n', -1);
+       free(data);
        return 0;
  }
  
@@@ -901,7 -892,7 +892,7 @@@ static int string_list_join_lines_helpe
  int combine_notes_cat_sort_uniq(unsigned char *cur_sha1,
                const unsigned char *new_sha1)
  {
-       struct string_list sort_uniq_list = { NULL, 0, 0, 1 };
+       struct string_list sort_uniq_list = STRING_LIST_INIT_DUP;
        struct strbuf buf = STRBUF_INIT;
        int ret = 1;
  
@@@ -910,6 -901,9 +901,9 @@@
                goto out;
        if (string_list_add_note_lines(&sort_uniq_list, new_sha1))
                goto out;
+       string_list_remove_empty_items(&sort_uniq_list, 0);
+       sort_string_list(&sort_uniq_list);
+       string_list_remove_duplicates(&sort_uniq_list, 0);
  
        /* create a new blob object from sort_uniq_list */
        if (for_each_string_list(&sort_uniq_list,
@@@ -949,23 -943,18 +943,18 @@@ void string_list_add_refs_by_glob(struc
  void string_list_add_refs_from_colon_sep(struct string_list *list,
                                         const char *globs)
  {
-       struct strbuf globbuf = STRBUF_INIT;
-       struct strbuf **split;
+       struct string_list split = STRING_LIST_INIT_NODUP;
+       char *globs_copy = xstrdup(globs);
        int i;
  
-       strbuf_addstr(&globbuf, globs);
-       split = strbuf_split(&globbuf, ':');
+       string_list_split_in_place(&split, globs_copy, ':', -1);
+       string_list_remove_empty_items(&split, 0);
  
-       for (i = 0; split[i]; i++) {
-               if (!split[i]->len)
-                       continue;
-               if (split[i]->buf[split[i]->len-1] == ':')
-                       strbuf_setlen(split[i], split[i]->len-1);
-               string_list_add_refs_by_glob(list, split[i]->buf);
-       }
+       for (i = 0; i < split.nr; i++)
+               string_list_add_refs_by_glob(list, split.items[i].string);
  
-       strbuf_list_free(split);
-       strbuf_release(&globbuf);
+       string_list_clear(&split, 0);
+       free(globs_copy);
  }
  
  static int notes_display_config(const char *k, const char *v, void *cb)
@@@ -1231,7 -1220,7 +1220,7 @@@ static void format_note(struct notes_tr
        }
  
        if (output_encoding && *output_encoding &&
 -                      strcmp(utf8, output_encoding)) {
 +          !is_encoding_utf8(output_encoding)) {
                char *reencoded = reencode_string(msg, output_encoding, utf8);
                if (reencoded) {
                        free(msg);