From 09ea1f8e0e85dd65307b29219ef1f5a3958eb918 Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Wed, 30 Oct 2013 06:33:07 +0100 Subject: [PATCH] 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 Signed-off-by: Junio C Hamano --- remote.c | 12 ++++++------ 1 file 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); } -- 2.39.2