diff options
author | Junio C Hamano <gitster@pobox.com> | 2012-05-30 00:09:08 +0400 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2012-05-30 00:09:08 +0400 |
commit | 12d7d150743acebe9684100e98979f2d0188114e (patch) | |
tree | fe72c047cf62f859983c48a2d69588084293372b /builtin/fetch-pack.c | |
parent | a7060009e1272aa43c8fb941f039cff9e9a0459b (diff) | |
parent | 3d2a33e57faa84be3ab83a80c8b75dad3e747054 (diff) |
Merge branch 'jk/fetch-pack-remove-dups-optim'
The way "fetch-pack" that is given multiple references to fetch tried to
remove duplicates was very inefficient.
By Jeff King
* jk/fetch-pack-remove-dups-optim:
fetch-pack: sort incoming heads list earlier
fetch-pack: avoid quadratic loop in filter_refs
fetch-pack: sort the list of incoming refs
add sorting infrastructure for list refs
fetch-pack: avoid quadratic behavior in remove_duplicates
fetch-pack: sort incoming heads
Diffstat (limited to 'builtin/fetch-pack.c')
-rw-r--r-- | builtin/fetch-pack.c | 52 |
1 files changed, 30 insertions, 22 deletions
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c index 7ad9e54a75..149db88726 100644 --- a/builtin/fetch-pack.c +++ b/builtin/fetch-pack.c @@ -528,6 +528,7 @@ static void filter_refs(struct ref **refs, int nr_match, char **match) struct ref **newtail = &newlist; struct ref *ref, *next; struct ref *fastarray[32]; + int match_pos; if (nr_match && !args.fetch_all) { if (ARRAY_SIZE(fastarray) < nr_match) @@ -540,6 +541,7 @@ static void filter_refs(struct ref **refs, int nr_match, char **match) else return_refs = NULL; + match_pos = 0; for (ref = *refs; ref; ref = next) { next = ref->next; if (!memcmp(ref->name, "refs/", 5) && @@ -553,15 +555,20 @@ static void filter_refs(struct ref **refs, int nr_match, char **match) continue; } else { - int i; - for (i = 0; i < nr_match; i++) { - if (!strcmp(ref->name, match[i])) { - match[i][0] = '\0'; - return_refs[i] = ref; + int cmp = -1; + while (match_pos < nr_match) { + cmp = strcmp(ref->name, match[match_pos]); + if (cmp < 0) /* definitely do not have it */ + break; + else if (cmp == 0) { /* definitely have it */ + match[match_pos][0] = '\0'; + return_refs[match_pos] = ref; break; } + else /* might have it; keep looking */ + match_pos++; } - if (i < nr_match) + if (!cmp) continue; /* we will link it later */ } free(ref); @@ -777,6 +784,8 @@ static struct ref *do_fetch_pack(int fd[2], struct ref *ref = copy_ref_list(orig_ref); unsigned char sha1[20]; + sort_ref_list(&ref, ref_compare_name); + if (is_repository_shallow() && !server_supports("shallow")) die("Server does not support shallow clients"); if (server_supports("multi_ack_detailed")) { @@ -834,21 +843,12 @@ static int remove_duplicates(int nr_heads, char **heads) { int src, dst; - for (src = dst = 0; src < nr_heads; src++) { - /* If heads[src] is different from any of - * heads[0..dst], push it in. - */ - int i; - for (i = 0; i < dst; i++) { - if (!strcmp(heads[i], heads[src])) - break; - } - if (i < dst) - continue; - if (src != dst) - heads[dst] = heads[src]; - dst++; - } + if (!nr_heads) + return 0; + + for (src = dst = 1; src < nr_heads; src++) + if (strcmp(heads[src], heads[dst-1])) + heads[dst++] = heads[src]; return dst; } @@ -1054,6 +1054,11 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix) return ret; } +static int compare_heads(const void *a, const void *b) +{ + return strcmp(*(const char **)a, *(const char **)b); +} + struct ref *fetch_pack(struct fetch_pack_args *my_args, int fd[], struct child_process *conn, const struct ref *ref, @@ -1073,8 +1078,11 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args, st.st_mtime = 0; } - if (heads && nr_heads) + if (heads && nr_heads) { + qsort(heads, nr_heads, sizeof(*heads), compare_heads); nr_heads = remove_duplicates(nr_heads, heads); + } + if (!ref) { packet_flush(fd[1]); die("no matching remote head"); |