[PATCH] Speed up git-merge-base a lot
[git/dscho.git] / merge-base.c
blob18d81d08a5147acd09b6f1e2f57f647ea5bf1fc5
1 #include <stdlib.h>
2 #include "cache.h"
3 #include "commit.h"
5 #define PARENT1 1
6 #define PARENT2 2
7 #define UNINTERESTING 4
9 static int interesting(struct commit_list *list)
11 while (list) {
12 struct commit *commit = list->item;
13 list = list->next;
14 if (commit->object.flags & UNINTERESTING)
15 continue;
16 return 1;
18 return 0;
21 static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
23 struct commit_list *list = NULL;
24 struct commit_list *result = NULL;
26 if (rev1 == rev2)
27 return rev1;
29 parse_commit(rev1);
30 parse_commit(rev2);
32 rev1->object.flags |= 1;
33 rev2->object.flags |= 2;
34 insert_by_date(rev1, &list);
35 insert_by_date(rev2, &list);
37 while (interesting(list)) {
38 struct commit *commit = list->item;
39 struct commit_list *tmp = list, *parents;
40 int flags = commit->object.flags & 7;
42 list = list->next;
43 free(tmp);
44 if (flags == 3) {
45 insert_by_date(commit, &result);
47 /* Mark children of a found merge uninteresting */
48 flags |= UNINTERESTING;
50 parents = commit->parents;
51 while (parents) {
52 struct commit *p = parents->item;
53 parents = parents->next;
54 if ((p->object.flags & flags) == flags)
55 continue;
56 parse_commit(p);
57 p->object.flags |= flags;
58 insert_by_date(p, &list);
61 if (!result)
62 return NULL;
63 return result->item;
66 int main(int argc, char **argv)
68 struct commit *rev1, *rev2, *ret;
69 unsigned char rev1key[20], rev2key[20];
71 if (argc != 3 ||
72 get_sha1(argv[1], rev1key) ||
73 get_sha1(argv[2], rev2key)) {
74 usage("git-merge-base <commit-id> <commit-id>");
76 rev1 = lookup_commit_reference(rev1key);
77 rev2 = lookup_commit_reference(rev2key);
78 if (!rev1 || !rev2)
79 return 1;
80 ret = common_ancestor(rev1, rev2);
81 if (!ret)
82 return 1;
83 printf("%s\n", sha1_to_hex(ret->object.sha1));
84 return 0;