We have a list of refs that we want to compare against the
"match" array. The current code searches the match list
linearly, giving quadratic behavior over the number of refs
when you want to fetch all of them.
Instead, we can compare the lists as we go, giving us linear
behavior.
Signed-off-by: Jeff King <peff@xxxxxxxx>
---
This is the only actual tricky patch in the series. I think I got the
list traversing right, but more eyeballs are appreciated.
This makes the result O(n). An alternative implementation would be to
simply binary-search the sorted "match" array for each ref. That's O(n
lg n), but we've already spent O(n lg n) sorting in the first place, so
it's not a big deal. The code for that would be a little bit simpler.
However, it's not as simple as you'd like, because we zero-out the match
array to mark entries as "found". So we'd have to add a separate
bit array.
I think this version is simple enough.
builtin/fetch-pack.c | 19 +++++++++++++------
1 file changed, 13 insertions(+), 6 deletions(-)
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index bee329f..d091865 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);
--
1.7.10.1.19.g711d603
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html