Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 21, 2014, 16:44 UTC
Message-ID: <CAPc5daWubo+CSD-C+AH6Y-PKQ7h2MoUU=DbW+nYKO9uceogsAg@mail.gmail.com>
In-Reply-To: <1416578950-23210-4-git-send-email-mhagger@alum.mit.edu>

On Fri, Nov 21, 2014 at 6:09 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Show 8 quoted lines

> Inserting items into a list in sorted order is O(N^2) whereas
> appending them unsorted and then sorting the list all at once is
> O(N lg N).
>
> string_list_insert() also removes duplicates, and this change loses
> that functionality. But the strings in this list, which ultimately
> come from a for_each_ref() iteration, cannot contain duplicates.
>

A similar conversion in other places we may do in the future might find a need for an equivalent to "-u" option of "sort" in the string_list_sort() function, but the above nicely explains why it is not necessary for this one. Good.

Eh, why is that called sort_string_list()? Perhaps it is a good opening to introduce string_list_sort(list, flag) where flag would be a bitmask that represents ignore-case, uniquify, etc., and then either deprecate the current one or make it a thin wrapper of the one that is more consistently named.

Show 23 quoted lines

> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
> ---
>  builtin/remote.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/builtin/remote.c b/builtin/remote.c
> index d5a5a16..7d5c8d2 100644
> --- a/builtin/remote.c
> +++ b/builtin/remote.c
> @@ -1341,8 +1341,9 @@ static int prune_remote(const char *remote, int dry_run)
>                 const char *refname = states.stale.items[i].util;
>
>                 delete_refs[i] = refname;
> -               string_list_insert(&delete_refs_list, refname);
> +               string_list_append(&delete_refs_list, refname);
>         }
> +       sort_string_list(&delete_refs_list);
>
>         if (!dry_run) {
>                 struct strbuf err = STRBUF_INIT;
> --
> 2.1.3
>