Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse
From: Junio C Hamano <hidden>
Date: 2016-06-15 23:03:05
On Fri, Nov 21, 2014 at 6:09 AM, Michael Haggerty [off-list ref] wrote:
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.
quoted hunk ↗ jump to hunk
Signed-off-by: Michael Haggerty <redacted> --- 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