[PATCH v2 18/23] ref_remove_duplicates(): avoid redundant bisection
- From
Michael Haggerty <mhagger@alum.mit.edu>
- Date
- Oct 30, 2013, 05:33 UTC
- Message-ID
- <1383111192-23780-19-git-send-email-mhagger@alum.mit.edu>
- In-Reply-To
- <1383111192-23780-1-git-send-email-mhagger@alum.mit.edu>
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> --- remote.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
diff --git a/remote.c b/remote.c index a5e6c7f..15f3dc5 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); }
-- 1.8.4.1