Commit a3a81ae5420fca1f00980f9d232c9197a7f98738
2012-12-09T20:43:26
Copy git_merge__bases_many() for new ahead-behind code To be used as a basis for a function which marks nodes with parents up to the merge base.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
diff --git a/src/graph.c b/src/graph.c
index fd789d6..6394125 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -10,6 +10,102 @@
#include "merge.h"
#include "git2/graph.h"
+static int interesting(git_pqueue *list)
+{
+ unsigned int i;
+ /* element 0 isn't used - we need to start at 1 */
+ for (i = 1; i < list->size; i++) {
+ git_commit_list_node *commit = list->d[i];
+ if ((commit->flags & STALE) == 0)
+ return 1;
+ }
+
+ return 0;
+}
+
+int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos)
+{
+ int error;
+ unsigned int i;
+ git_commit_list_node *two;
+ git_commit_list *result = NULL, *tmp = NULL;
+ git_pqueue list;
+
+ /* if the commit is repeated, we have a our merge base already */
+ git_vector_foreach(twos, i, two) {
+ if (one == two)
+ return git_commit_list_insert(one, out) ? 0 : -1;
+ }
+
+ if (git_pqueue_init(&list, twos->length * 2, git_commit_list_time_cmp) < 0)
+ return -1;
+
+ if (git_commit_list_parse(walk, one) < 0)
+ return -1;
+
+ one->flags |= PARENT1;
+ if (git_pqueue_insert(&list, one) < 0)
+ return -1;
+
+ git_vector_foreach(twos, i, two) {
+ git_commit_list_parse(walk, two);
+ two->flags |= PARENT2;
+ if (git_pqueue_insert(&list, two) < 0)
+ return -1;
+ }
+
+ /* as long as there are non-STALE commits */
+ while (interesting(&list)) {
+ git_commit_list_node *commit;
+ int flags;
+
+ commit = git_pqueue_pop(&list);
+
+ flags = commit->flags & (PARENT1 | PARENT2 | STALE);
+ if (flags == (PARENT1 | PARENT2)) {
+ if (!(commit->flags & RESULT)) {
+ commit->flags |= RESULT;
+ if (git_commit_list_insert(commit, &result) == NULL)
+ return -1;
+ }
+ /* we mark the parents of a merge stale */
+ flags |= STALE;
+ }
+
+ for (i = 0; i < commit->out_degree; i++) {
+ git_commit_list_node *p = commit->parents[i];
+ if ((p->flags & flags) == flags)
+ continue;
+
+ if ((error = git_commit_list_parse(walk, p)) < 0)
+ return error;
+
+ p->flags |= flags;
+ if (git_pqueue_insert(&list, p) < 0)
+ return -1;
+ }
+ }
+
+ git_pqueue_free(&list);
+
+ /* filter out any stale commits in the results */
+ tmp = result;
+ result = NULL;
+
+ while (tmp) {
+ struct git_commit_list *next = tmp->next;
+ if (!(tmp->item->flags & STALE))
+ if (git_commit_list_insert_by_date(tmp->item, &result) == NULL)
+ return -1;
+
+ git__free(tmp);
+ tmp = next;
+ }
+
+ *out = result;
+ return 0;
+}
+
static int ahead_behind(git_commit_list_node *one, git_commit_list_node *two,
size_t *ahead, size_t *behind)
{