diff options
author | Edward Thomson <ethomson@edwardthomson.com> | 2014-10-10 09:59:26 -0400 |
---|---|---|
committer | Edward Thomson <ethomson@edwardthomson.com> | 2014-10-10 09:59:26 -0400 |
commit | f339f441f930de624413968270ea4c164437daec (patch) | |
tree | 5f28da7d4d90555c5f0390133f6d7129951887a4 | |
parent | bd62dc6fdde123339844dc199a6c3b8ba0630afa (diff) | |
parent | d6afda62d94d7bb29d864cf1c86648839ef60b2d (diff) | |
download | libgit2-f339f441f930de624413968270ea4c164437daec.tar.gz |
Merge pull request #2603 from libgit2/cmn/revwalk-merge-base
Walk only as far as the common ancestors of uninteresting commits
-rw-r--r-- | src/revwalk.c | 118 | ||||
-rw-r--r-- | src/revwalk.h | 9 |
2 files changed, 101 insertions, 26 deletions
diff --git a/src/revwalk.c b/src/revwalk.c index bd07d02cb..4dca7599a 100644 --- a/src/revwalk.c +++ b/src/revwalk.c @@ -116,6 +116,7 @@ static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int error; git_object *obj, *oobj; git_commit_list_node *commit; + git_commit_list *list; if ((error = git_object_lookup(&oobj, walk->repo, oid, GIT_OBJ_ANY)) < 0) return error; @@ -141,14 +142,20 @@ static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, if (commit == NULL) return -1; /* error already reported by failed lookup */ + if (uninteresting) + walk->did_hide = 1; + else + walk->did_push = 1; + commit->uninteresting = uninteresting; - if (walk->one == NULL && !uninteresting) { - walk->one = commit; - } else { - if (git_vector_insert(&walk->twos, commit) < 0) - return -1; + list = walk->user_input; + if (git_commit_list_insert(commit, &list) == NULL) { + giterr_set_oom(); + return -1; } + walk->user_input = list; + return 0; } @@ -367,29 +374,97 @@ static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk * } +static int interesting(git_pqueue *list) +{ + size_t i; + + for (i = 0; i < git_pqueue_size(list); i++) { + git_commit_list_node *commit = git_pqueue_get(list, i); + if (!commit->uninteresting) + return 1; + } + + return 0; +} + +static int contains(git_pqueue *list, git_commit_list_node *node) +{ + size_t i; + + for (i = 0; i < git_pqueue_size(list); i++) { + git_commit_list_node *commit = git_pqueue_get(list, i); + if (commit == node) + return 1; + } + + return 0; +} + +static int premark_uninteresting(git_revwalk *walk) +{ + int error = 0; + unsigned short i; + git_pqueue q; + git_commit_list *list; + git_commit_list_node *commit, *parent; + + if ((error = git_pqueue_init(&q, 0, 8, git_commit_list_time_cmp)) < 0) + return error; + + for (list = walk->user_input; list; list = list->next) { + if ((error = git_commit_list_parse(walk, list->item)) < 0) + goto cleanup; + + if ((error = git_pqueue_insert(&q, list->item)) < 0) + goto cleanup; + } + + while (interesting(&q)) { + commit = git_pqueue_pop(&q); + + for (i = 0; i < commit->out_degree; i++) { + parent = commit->parents[i]; + + if ((error = git_commit_list_parse(walk, parent)) < 0) + goto cleanup; + + if (commit->uninteresting) + parent->uninteresting = 1; + + if (contains(&q, parent)) + continue; + + if ((error = git_pqueue_insert(&q, parent)) < 0) + goto cleanup; + } + } + +cleanup: + git_pqueue_free(&q); + return error; +} + static int prepare_walk(git_revwalk *walk) { int error; - unsigned int i; - git_commit_list_node *next, *two; - - /* - * If walk->one is NULL, there were no positive references, - * so we know that the walk is already over. - */ - if (walk->one == NULL) { + git_commit_list *list; + git_commit_list_node *next; + + /* If there were no pushes, we know that the walk is already over */ + if (!walk->did_push) { giterr_clear(); return GIT_ITEROVER; } - if (process_commit(walk, walk->one, walk->one->uninteresting) < 0) - return -1; + if (walk->did_hide && (error = premark_uninteresting(walk)) < 0) + return error; - git_vector_foreach(&walk->twos, i, two) { - if (process_commit(walk, two, two->uninteresting) < 0) + for (list = walk->user_input; list; list = list->next) { + if (process_commit(walk, list->item, list->item->uninteresting) < 0) return -1; } + if (walk->sorting & GIT_SORT_TOPOLOGICAL) { unsigned short i; @@ -440,7 +515,6 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo) if (git_pqueue_init( &walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0 || - git_vector_init(&walk->twos, 4, NULL) < 0 || git_pool_init(&walk->commit_pool, 1, git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0) return -1; @@ -470,7 +544,6 @@ void git_revwalk_free(git_revwalk *walk) git_oidmap_free(walk->commits); git_pool_clear(&walk->commit_pool); git_pqueue_free(&walk->iterator_time); - git_vector_free(&walk->twos); git__free(walk); } @@ -540,16 +613,17 @@ void git_revwalk_reset(git_revwalk *walk) commit->in_degree = 0; commit->topo_delay = 0; commit->uninteresting = 0; + commit->flags = 0; }); git_pqueue_clear(&walk->iterator_time); git_commit_list_free(&walk->iterator_topo); git_commit_list_free(&walk->iterator_rand); git_commit_list_free(&walk->iterator_reverse); + git_commit_list_free(&walk->user_input); + walk->first_parent = 0; walk->walking = 0; - - walk->one = NULL; - git_vector_clear(&walk->twos); + walk->did_push = walk->did_hide = 0; } int git_revwalk_add_hide_cb( diff --git a/src/revwalk.h b/src/revwalk.h index d81f97c01..72ddedc75 100644 --- a/src/revwalk.h +++ b/src/revwalk.h @@ -32,12 +32,13 @@ struct git_revwalk { int (*enqueue)(git_revwalk *, git_commit_list_node *); unsigned walking:1, - first_parent: 1; + first_parent: 1, + did_hide: 1, + did_push: 1; unsigned int sorting; - /* merge base calculation */ - git_commit_list_node *one; - git_vector twos; + /* the pushes and hides */ + git_commit_list *user_input; /* hide callback */ git_revwalk_hide_cb hide_cb; |