summaryrefslogtreecommitdiff
path: root/remote.c
diff options
context:
space:
mode:
authorMichael Haggerty <mhagger@alum.mit.edu>2013-10-30 06:33:07 +0100
committerJunio C Hamano <gitster@pobox.com>2013-10-30 14:16:41 -0700
commit09ea1f8e0e85dd65307b29219ef1f5a3958eb918 (patch)
tree1a9b68e600ee6408c1926d675d2b28e6bf8f2239 /remote.c
parent37f0dcbdc1585dafd81c393aa750292e8634035d (diff)
downloadgit-09ea1f8e0e85dd65307b29219ef1f5a3958eb918.tar.gz
ref_remove_duplicates(): avoid redundant bisection
The old code called string_list_lookup(), and if that failed called string_list_insert(), thus doing the bisection search through the string list twice in the latter code path. Instead, just call string_list_insert() right away. If an entry for that peer reference name already existed, then its util pointer is always non-NULL. Of course this doesn't change the fact that the repeated string_list_insert() calls make the function scale like O(N^2) if the input reference list is not already approximately sorted. Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'remote.c')
-rw-r--r--remote.c12
1 files changed, 6 insertions, 6 deletions
diff --git a/remote.c b/remote.c
index 4d45f5dc72..1fb87de01c 100644
--- a/remote.c
+++ b/remote.c
@@ -750,13 +750,15 @@ void ref_remove_duplicates(struct ref *ref_map)
struct string_list refs = STRING_LIST_INIT_NODUP;
struct string_list_item *item = NULL;
struct ref *prev = NULL, *next = NULL;
+
for (; ref_map; prev = ref_map, ref_map = next) {
next = ref_map->next;
if (!ref_map->peer_ref)
continue;
- item = string_list_lookup(&refs, ref_map->peer_ref->name);
- if (item) {
+ item = string_list_insert(&refs, ref_map->peer_ref->name);
+ if (item->util) {
+ /* Entry already existed */
if (strcmp(((struct ref *)item->util)->name,
ref_map->name))
die("%s tracks both %s and %s",
@@ -767,11 +769,9 @@ void ref_remove_duplicates(struct ref *ref_map)
free(ref_map->peer_ref);
free(ref_map);
ref_map = prev; /* skip this; we freed it */
- continue;
+ } else {
+ item->util = ref_map;
}
-
- item = string_list_insert(&refs, ref_map->peer_ref->name);
- item->util = ref_map;
}
string_list_clear(&refs, 0);
}