Merge branch 'jk/tag-contains-ab' (early part) into maint
authorJunio C Hamano <gitster@pobox.com>
Mon, 12 Sep 2011 04:54:32 +0000 (21:54 -0700)
committerJunio C Hamano <gitster@pobox.com>
Mon, 12 Sep 2011 04:54:32 +0000 (21:54 -0700)
* 'jk/tag-contains-ab' (early part):
  tag: speed up --contains calculation

1  2 
builtin/tag.c

diff --cc builtin/tag.c
index cef27263bc79e519398ae5eb0a49d78f3b389090,f7a7943c9ddf783270addc3a50b23496f44fe175..667515e5278d22548fb83507347ab652533a67b2
@@@ -29,17 -31,50 +31,59 @@@ struct tag_filter 
        struct commit_list *with_commit;
  };
  
 -#define PGP_SIGNATURE "-----BEGIN PGP SIGNATURE-----"
 +static int match_pattern(const char **patterns, const char *ref)
 +{
 +      /* no pattern means match everything */
 +      if (!*patterns)
 +              return 1;
 +      for (; *patterns; patterns++)
 +              if (!fnmatch(*patterns, ref, 0))
 +                      return 1;
 +      return 0;
 +}
  
+ 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_recurse(struct commit *candidate,
+                           const struct commit_list *want)
+ {
+       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 (parse_commit(candidate) < 0)
+               return 0;
+       /* Otherwise recurse and mark ourselves for future traversals. */
+       for (p = candidate->parents; p; p = p->next) {
+               if (contains_recurse(p->item, want)) {
+                       candidate->object.flags |= TMP_MARK;
+                       return 1;
+               }
+       }
+       candidate->object.flags |= UNINTERESTING;
+       return 0;
+ }
+ static int contains(struct commit *candidate, const struct commit_list *want)
+ {
+       return contains_recurse(candidate, want);
+ }
  static int show_reference(const char *refname, const unsigned char *sha1,
                          int flag, void *cb_data)
  {