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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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.

Signed-off-by: Michael Haggerty <mhagger@xxxxxxxxxxxx>
---
 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

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html




[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]