aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Barkalow <barkalow@iabervon.org>2005-04-23 18:47:23 -0700
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-23 18:47:23 -0700
commitb6b15db3f464b18180eee79927cb324fd63e15ff (patch)
treec39c3027cb15e3d014f959c07794f96b4d4218ea
parent8237b1854c64492ab5772994b4ac4efd7f1c2fc0 (diff)
downloadgit-b6b15db3f464b18180eee79927cb324fd63e15ff.tar.gz
git-b6b15db3f464b18180eee79927cb324fd63e15ff.tar.xz
[PATCH] Replace merge-base implementation
The old implementation was a nice algorithm, but, unfortunately, it could be confused in some cases and would not necessarily do the obvious thing if one argument was decended from the other. This version fixes that by changing the criterion to the most recent common ancestor. Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
-rw-r--r--merge-base.c92
1 files changed, 44 insertions, 48 deletions
diff --git a/merge-base.c b/merge-base.c
index ac1153bc5..0e4c58ede 100644
--- a/merge-base.c
+++ b/merge-base.c
@@ -5,67 +5,63 @@
static struct commit *process_list(struct commit_list **list_p, int this_mark,
int other_mark)
{
- 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;
+ struct commit *item = (*list_p)->item;
+
+ if (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.
+ */
+ *list_p = (*list_p)->next;
+ } else if (item->object.flags & other_mark) {
+ return item;
+ } else {
+ /*
+ printf("%d based on %s\n",
+ this_mark,
+ sha1_to_hex(posn->parent->sha1));
+ */
+ pop_most_recent_commit(list_p);
+ item->object.flags |= this_mark;
}
return NULL;
}
struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
{
- struct commit_list *rev1list = malloc(sizeof(struct commit_list));
- struct commit_list *rev2list = malloc(sizeof(struct commit_list));
+ struct commit_list *rev1list = NULL;
+ struct commit_list *rev2list = NULL;
- rev1list->item = rev1;
- rev1list->next = NULL;
+ commit_list_insert(rev1, &rev1list);
+ commit_list_insert(rev2, &rev2list);
- rev2list->item = rev2;
- rev2list->next = NULL;
+ parse_commit(rev1);
+ parse_commit(rev2);
while (rev1list || rev2list) {
struct commit *ret;
- ret = process_list(&rev1list, 0x1, 0x2);
- if (ret) {
- /* XXXX free lists */
- return ret;
+ if (!rev1list) {
+ // process 2
+ ret = process_list(&rev2list, 0x2, 0x1);
+ } else if (!rev2list) {
+ // process 1
+ ret = process_list(&rev1list, 0x1, 0x2);
+ } else if (rev1list->item->date < rev2list->item->date) {
+ // process 2
+ ret = process_list(&rev2list, 0x2, 0x1);
+ } else {
+ // process 1
+ ret = process_list(&rev1list, 0x1, 0x2);
}
- ret = process_list(&rev2list, 0x2, 0x1);
if (ret) {
- /* XXXX free lists */
+ free_commit_list(rev1list);
+ free_commit_list(rev2list);
return ret;
}
}