summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLibravatar Junio C Hamano <gitster@pobox.com>2013-07-18 12:48:25 -0700
committerLibravatar Junio C Hamano <gitster@pobox.com>2013-07-18 12:48:25 -0700
commitdb1a848421fe05482e36fcba76f019299ae93b25 (patch)
tree7190ea58d567677feb6a0f7db9aae57257e0f5a2
parentMerge branch 'rr/rebase-reflog-message-reword' (diff)
parentremote.c: avoid O(m*n) behavior in match_push_refs (diff)
downloadtgif-db1a848421fe05482e36fcba76f019299ae93b25.tar.xz
Merge branch 'bc/push-match-many-refs'
Pushing to repositories with many refs employed O(m*n) algorithm where n is the number of refs on the receiving end. * bc/push-match-many-refs: remote.c: avoid O(m*n) behavior in match_push_refs
-rw-r--r--remote.c27
1 files changed, 25 insertions, 2 deletions
diff --git a/remote.c b/remote.c
index 6f57830b64..efcba931ec 100644
--- a/remote.c
+++ b/remote.c
@@ -1302,6 +1302,14 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
free(sent_tips.tip);
}
+static void prepare_ref_index(struct string_list *ref_index, struct ref *ref)
+{
+ for ( ; ref; ref = ref->next)
+ string_list_append_nodup(ref_index, ref->name)->util = ref;
+
+ sort_string_list(ref_index);
+}
+
/*
* Given the set of refs the local repository has, the set of refs the
* remote repository has, and the refspec used for push, determine
@@ -1320,6 +1328,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
int errs;
static const char *default_refspec[] = { ":", NULL };
struct ref *ref, **dst_tail = tail_ref(dst);
+ struct string_list dst_ref_index = STRING_LIST_INIT_NODUP;
if (!nr_refspec) {
nr_refspec = 1;
@@ -1330,6 +1339,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
/* pick the remainder */
for (ref = src; ref; ref = ref->next) {
+ struct string_list_item *dst_item;
struct ref *dst_peer;
const struct refspec *pat = NULL;
char *dst_name;
@@ -1338,7 +1348,11 @@ int match_push_refs(struct ref *src, struct ref **dst,
if (!dst_name)
continue;
- dst_peer = find_ref_by_name(*dst, dst_name);
+ if (!dst_ref_index.nr)
+ prepare_ref_index(&dst_ref_index, *dst);
+
+ dst_item = string_list_lookup(&dst_ref_index, dst_name);
+ dst_peer = dst_item ? dst_item->util : NULL;
if (dst_peer) {
if (dst_peer->peer_ref)
/* We're already sending something to this ref. */
@@ -1355,6 +1369,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
/* Create a new one and link it */
dst_peer = make_linked_ref(dst_name, &dst_tail);
hashcpy(dst_peer->new_sha1, ref->new_sha1);
+ string_list_insert(&dst_ref_index,
+ dst_peer->name)->util = dst_peer;
}
dst_peer->peer_ref = copy_ref(ref);
dst_peer->force = pat->force;
@@ -1362,10 +1378,13 @@ int match_push_refs(struct ref *src, struct ref **dst,
free(dst_name);
}
+ string_list_clear(&dst_ref_index, 0);
+
if (flags & MATCH_REFS_FOLLOW_TAGS)
add_missing_tags(src, dst, &dst_tail);
if (send_prune) {
+ struct string_list src_ref_index = STRING_LIST_INIT_NODUP;
/* check for missing refs on the remote */
for (ref = *dst; ref; ref = ref->next) {
char *src_name;
@@ -1376,11 +1395,15 @@ int match_push_refs(struct ref *src, struct ref **dst,
src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);
if (src_name) {
- if (!find_ref_by_name(src, src_name))
+ if (!src_ref_index.nr)
+ prepare_ref_index(&src_ref_index, src);
+ if (!string_list_has_string(&src_ref_index,
+ src_name))
ref->peer_ref = alloc_delete_ref();
free(src_name);
}
}
+ string_list_clear(&src_ref_index, 0);
}
if (errs)
return -1;