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 --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 94d7a2bd999ce5e8603f6d6639ba34d224c2bee5..7386bcab3ec30a06f4663c953fa46e78ed26c07b 100644 (file)
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -38,7 +38,8 @@ member (you need this if you add things later) and you should set the
   `unsorted_string_list_delete_item`.
 
 . Can remove items not matching a criterion from a sorted or unsorted
-  list using `filter_string_list`.
+  list using `filter_string_list`, or remove empty strings using
+  `string_list_remove_empty_items`.
 
 . Finally it should free the list using `string_list_clear`.
 
@@ -75,6 +76,12 @@ Functions
        to be deleted.  Preserve the order of the items that are
        retained.
 
+`string_list_remove_empty_items`::
+
+       Remove any empty strings from the list.  If free_util is true,
+       call free() on the util members of any items that have to be
+       deleted.  Preserve the order of the items that are retained.
+
 `string_list_longest_prefix`::
 
        Return the longest string within a string_list that is a

diff --git a/notes.c b/notes.c
index ee8f01f1d5c1dcb39c40eee443eddaedde380d20..19b0eaada28ffc603d0bbc1914303fd1de6bf22c 100644 (file)
--- a/notes.c
+++ b/notes.c
@@ -848,15 +848,16 @@ int combine_notes_ignore(unsigned char *cur_sha1,
        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 @@ static int string_list_add_note_lines(struct string_list *sort_uniq_list,
                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 @@ static int string_list_join_lines_helper(struct string_list_item *item,
 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 @@ int combine_notes_cat_sort_uniq(unsigned char *cur_sha1,
                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 @@ void string_list_add_refs_by_glob(struct string_list *list, const char *glob)
 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)

diff --git a/string-list.c b/string-list.c
index c54b816244f69614c67c532d20719081a4b34bd4..397e6cfa7db82bdb17f7cdbe4662a1607c0773af 100644 (file)
--- a/string-list.c
+++ b/string-list.c
@@ -136,6 +136,15 @@ void filter_string_list(struct string_list *list, int free_util,
        list->nr = dst;
 }
 
+static int item_is_not_empty(struct string_list_item *item, void *unused)
+{
+       return *item->string != '\0';
+}
+
+void string_list_remove_empty_items(struct string_list *list, int free_util) {
+       filter_string_list(list, free_util, item_is_not_empty, NULL);
+}
+
 char *string_list_longest_prefix(const struct string_list *prefixes,
                                 const char *string)
 {

diff --git a/string-list.h b/string-list.h
index 5efd07b44e020428326ff32ff258449ec347861f..c50b0d0deac086cd5a50a5c021103a5f5e76c1cd 100644 (file)
--- a/string-list.h
+++ b/string-list.h
@@ -38,6 +38,13 @@ int for_each_string_list(struct string_list *list,
 void filter_string_list(struct string_list *list, int free_util,
                        string_list_each_func_t want, void *cb_data);
 
+/*
+ * Remove any empty strings from the list.  If free_util is true, call
+ * free() on the util members of any items that have to be deleted.
+ * Preserve the order of the items that are retained.
+ */
+void string_list_remove_empty_items(struct string_list *list, int free_util);
+
 /*
  * Return the longest string in prefixes that is a prefix (in the
  * sense of prefixcmp()) of string, or NULL if no such prefix exists.