Commit a9833bc916b1790a1f3ff4981a1ebe2dd026c9ae
2019-05-13T10:56:15
add got_commit_graph_find_youngest_common_ancestor()
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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
diff --git a/include/got_commit_graph.h b/include/got_commit_graph.h
index 006b16f..3841e17 100644
--- a/include/got_commit_graph.h
+++ b/include/got_commit_graph.h
@@ -30,3 +30,8 @@ const struct got_error *got_commit_graph_iter_next(struct got_object_id **,
const struct got_error *got_commit_graph_intersect(struct got_object_id **,
struct got_commit_graph *, struct got_commit_graph *,
struct got_repository *);
+
+/* Find the youngest common ancestor of two commits. */
+const struct got_error *got_commit_graph_find_youngest_common_ancestor(
+ struct got_object_id **, struct got_object_id *, struct got_object_id *,
+ struct got_repository *);
diff --git a/lib/commit_graph.c b/lib/commit_graph.c
index cac2b8c..4139ee7 100644
--- a/lib/commit_graph.c
+++ b/lib/commit_graph.c
@@ -639,3 +639,112 @@ got_commit_graph_iter_next(struct got_object_id **id,
graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
return NULL;
}
+
+const struct got_error *
+got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
+ struct got_object_id *commit_id, struct got_object_id *commit_id2,
+ struct got_repository *repo)
+{
+ const struct got_error *err = NULL;
+ struct got_commit_graph *graph = NULL, *graph2 = NULL;
+ int completed = 0, completed2 = 0;
+ struct got_object_idset *commit_ids;
+
+ *yca_id = NULL;
+
+ commit_ids = got_object_idset_alloc();
+ if (commit_ids == NULL)
+ return got_error_prefix_errno("got_object_idset_alloc");
+
+ err = got_commit_graph_open(&graph, commit_id, "/", 1, repo);
+ if (err)
+ goto done;
+
+ err = got_commit_graph_open(&graph2, commit_id2, "/", 1, repo);
+ if (err)
+ goto done;
+
+ err = got_commit_graph_iter_start(graph, commit_id, repo);
+ if (err)
+ goto done;
+
+ err = got_commit_graph_iter_start(graph2, commit_id2, repo);
+ if (err)
+ goto done;
+
+ for (;;) {
+ struct got_object_id *id, *id2;
+
+ if (!completed) {
+ err = got_commit_graph_iter_next(&id, graph);
+ if (err) {
+ if (err->code == GOT_ERR_ITER_COMPLETED)
+ completed = 1;
+ else if (err->code != GOT_ERR_ITER_NEED_MORE)
+ break;
+ err = got_commit_graph_fetch_commits(graph, 1,
+ repo);
+ if (err)
+ break;
+ }
+ }
+
+ if (!completed2) {
+ err = got_commit_graph_iter_next(&id2, graph2);
+ if (err) {
+ if (err->code == GOT_ERR_ITER_COMPLETED)
+ completed2 = 1;
+ else if (err->code != GOT_ERR_ITER_NEED_MORE)
+ break;
+ err = got_commit_graph_fetch_commits(graph2, 1,
+ repo);
+ if (err)
+ break;
+ }
+ }
+
+ if (id) {
+ if (got_object_idset_get(commit_ids, id)) {
+ *yca_id = got_object_id_dup(id);
+ if (*yca_id)
+ break;
+ else
+ err = got_error_prefix_errno(
+ "got_object_id_up");
+ break;
+
+ }
+ err = got_object_idset_add(commit_ids, id, id);
+ if (err)
+ break;
+ }
+ if (id2) {
+ if (got_object_idset_get(commit_ids, id2)) {
+ *yca_id = got_object_id_dup(id2);
+ if (*yca_id)
+ break;
+ else
+ err = got_error_prefix_errno(
+ "got_object_id_up");
+ break;
+
+ }
+ err = got_object_idset_add(commit_ids, id2, id2);
+ if (err)
+ break;
+ }
+
+ if (completed && completed2) {
+ err = got_error(GOT_ERR_ANCESTRY);
+ break;
+ }
+
+ }
+done:
+ got_object_idset_free(commit_ids);
+ if (graph)
+ got_commit_graph_close(graph);
+ if (graph2)
+ got_commit_graph_close(graph2);
+ return err;
+}