On Thu, Jul 01, 2010 at 11:03:31AM -0400, Jeff King wrote:
> $ time git tag --contains HEAD~200
> v1.7.1
> v1.7.1-rc2
> v1.7.1.1
> v1.7.2-rc0
> v1.7.2-rc1
>
> real 0m2.179s
> user 0m2.156s
> sys 0m0.020s
>
> [...]
>
> I suspect we could do even better by sharing information between
> traversals. That is, walk the graph from each ref, but retain marks on
Here is a quick and dirty patch to implement what I suggested. With it,
I get the same results as above, but it runs between 3 and 4 times as
fast:
real 0m0.621s
user 0m0.588s
sys 0m0.032s
Implementing the timestamp-checking thing that name-rev does would
probably drop it even more (at the expense of less accuracy in the
face of clock skew).
diff --git a/builtin/tag.c b/builtin/tag.c
index d311491..d18c3ed 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -10,6 +10,8 @@
#include "builtin.h"
#include "refs.h"
#include "tag.h"
+#include "diff.h"
+#include "revision.h"
#include "run-command.h"
#include "parse-options.h"
@@ -31,6 +33,42 @@ struct tag_filter {
#define PGP_SIGNATURE "-----BEGIN PGP SIGNATURE-----"
+static int in_commit_list(const struct commit_list *want, struct commit *c)
+{
+ for (; want; want = want->next)
+ if (!hashcmp(want->item->object.sha1, c->object.sha1))
+ return 1;
+ return 0;
+}
+
+static int contains(const struct commit_list *want, struct commit *candidate)
+{
+ struct commit_list *p;
+
+ /* was it previously marked as containing a want commit? */
+ if (candidate->object.flags & TMP_MARK)
+ return 1;
+ /* or marked as not possibly containing a want commit? */
+ if (candidate->object.flags & UNINTERESTING)
+ return 0;
+ /* or are we it? */
+ if (in_commit_list(want, candidate))
+ return 1;
+
+ /* If not, then try parents, and be sure to mark ourselves
+ * for future traversals. */
+ parse_commit(candidate);
+ for (p = candidate->parents; p; p = p->next) {
+ if (contains(want, p->item)) {
+ candidate->object.flags |= TMP_MARK;
+ return 1;
+ }
+ }
+
+ candidate->object.flags |= UNINTERESTING;
+ return 0;
+}
+
static int show_reference(const char *refname, const unsigned char *sha1,
int flag, void *cb_data)
{
@@ -49,7 +87,7 @@ static int show_reference(const char *refname, const unsigned char *sha1,
commit = lookup_commit_reference_gently(sha1, 1);
if (!commit)
return 0;
- if (!is_descendant_of(commit, filter->with_commit))
+ if (!contains(filter->with_commit, commit))
return 0;
}
--
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