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>

diff --git a/remote.c b/remote.c
index 4d45f5dc72b240b344435076c120e394accfc79c..1fb87de01c6a3e7cede213b64a99408060eef33a 100644 (file)
--- 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);
 }