diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | merge-base.c | 122 |
2 files changed, 82 insertions, 44 deletions
@@ -64,8 +64,8 @@ check-files: check-files.o read-cache.o ls-tree: ls-tree.o read-cache.o $(CC) $(CFLAGS) -o ls-tree ls-tree.o read-cache.o $(LIBS) -merge-base: merge-base.o read-cache.o - $(CC) $(CFLAGS) -o merge-base merge-base.o read-cache.o $(LIBS) +merge-base: merge-base.o read-cache.o object.o commit.o tree.o blob.o + $(CC) $(CFLAGS) -o merge-base merge-base.o read-cache.o object.o commit.o tree.o blob.o $(LIBS) read-cache.o: cache.h show-diff.o: cache.h diff --git a/merge-base.c b/merge-base.c index 36ac42008c..0b99598f30 100644 --- a/merge-base.c +++ b/merge-base.c @@ -1,57 +1,95 @@ +#include <stdlib.h> #include "cache.h" -#include "revision.h" +#include "commit.h" -/* - * This is stupid. We could have much better heurstics, I bet. - */ -static int better(struct revision *new, struct revision *old) +static struct commit *process_list(struct commit_list **list_p, int this_mark, + int other_mark) { - return new->date > old->date; + struct commit_list *parent, *temp; + struct commit_list *posn = *list_p; + *list_p = NULL; + while (posn) { + parse_commit(posn->item); + if (posn->item->object.flags & this_mark) { + /* + printf("%d already seen %s %x\n", + this_mark + sha1_to_hex(posn->parent->sha1), + posn->parent->flags); + */ + /* do nothing; this indicates that this side + * split and reformed, and we only need to + * mark it once. + */ + } else if (posn->item->object.flags & other_mark) { + return posn->item; + } else { + /* + printf("%d based on %s\n", + this_mark, + sha1_to_hex(posn->parent->sha1)); + */ + posn->item->object.flags |= this_mark; + + parent = posn->item->parents; + while (parent) { + temp = malloc(sizeof(struct commit_list)); + temp->next = *list_p; + temp->item = parent->item; + *list_p = temp; + parent = parent->next; + } + } + posn = posn->next; + } + return NULL; } -static struct revision *common_parent(struct revision *rev1, struct revision *rev2) +struct commit *common_ancestor(struct commit *rev1, struct commit *rev2) { - int i; - struct revision *best = NULL; + struct commit_list *rev1list = malloc(sizeof(struct commit_list)); + struct commit_list *rev2list = malloc(sizeof(struct commit_list)); + + rev1list->item = rev1; + rev1list->next = NULL; - mark_reachable(rev1, 1); - mark_reachable(rev2, 2); - for (i = 0; i < nr_revs ;i++) { - struct revision *rev = revs[i]; - if ((rev->flags & 3) != 3) - continue; - if (!best) { - best = rev; - continue; + rev2list->item = rev2; + rev2list->next = NULL; + + while (rev1list || rev2list) { + struct commit *ret; + ret = process_list(&rev1list, 0x1, 0x2); + if (ret) { + /* XXXX free lists */ + return ret; + } + ret = process_list(&rev2list, 0x2, 0x1); + if (ret) { + /* XXXX free lists */ + return ret; } - if (better(rev, best)) - best = rev; } - return best; + return NULL; } int main(int argc, char **argv) { - unsigned char rev1[20], rev2[20]; - struct revision *common; + struct commit *rev1, *rev2, *ret; + unsigned char rev1key[20], rev2key[20]; - if (argc != 3 || get_sha1_hex(argv[1], rev1) || get_sha1_hex(argv[2], rev2)) - usage("merge-base <commit1> <commit2>"); - - /* - * We will eventually want to include a revision cache file - * that "rev-tree.c" has generated, since this is going to - * otherwise be quite expensive for big trees.. - * - * That's some time off, though, and in the meantime we know - * that we have a solution to the eventual expense. - */ - parse_commit(rev1); - parse_commit(rev2); - - common = common_parent(lookup_rev(rev1), lookup_rev(rev2)); - if (!common) - die("no common parent found"); - printf("%s\n", sha1_to_hex(common->sha1)); - return 0; + if (argc != 3 || + get_sha1_hex(argv[1], rev1key) || + get_sha1_hex(argv[2], rev2key)) { + usage("merge-base <commit-id> <commit-id>"); + } + rev1 = lookup_commit(rev1key); + rev2 = lookup_commit(rev2key); + ret = common_ancestor(rev1, rev2); + if (ret) { + printf("%s\n", sha1_to_hex(ret->object.sha1)); + return 0; + } else { + return 1; + } + } |