From: Junio C Hamano Date: Fri, 22 Apr 2016 21:52:26 GMT Subject: Re: [PATCH v5 2/4] format-patch: add '--base' option to record base tree info Message-ID: In-Reply-To: <1461303756-25975-3-git-send-email-xiaolong.ye@intel.com> Xiaolong Ye writes: > +static struct commit *get_base_commit(const char *base_commit, > + struct commit **list, > + int total) > +{ > + struct commit *base = NULL; > + struct commit **rev; > + int i = 0, rev_nr = 0; > + > + base = lookup_commit_reference_by_name(base_commit); > + if (!base) > + die(_("Unknown commit %s"), base_commit); > + > + ALLOC_ARRAY(rev, total); > + for (i = 0; i < total; i++) > + rev[i] = list[i]; > + > + rev_nr = total; > + /* > + * Get merge base through pair-wise computations > + * and store it in rev[0]. > + */ > + while (rev_nr > 1) { > + for (i = 0; i < rev_nr / 2; i++) { > + struct commit_list *merge_base; > + merge_base = get_merge_bases(rev[2 * i], rev[2 * i + 1]); > + if (!merge_base || merge_base->next) > + die(_("Failed to find exact merge base")); > + > + rev[i] = merge_base->item; > + } So merge-base(0,1) is stored in rev[0], merge-base(2,3) is then stored in rev[1], etc. and the last item, if rev_nr is odd, is left in rev[rev_nr-1]. When the loop finishes, i is left as rev_nr/2 and... > + if (rev_nr % 2) > + rev[i] = rev[2 * i]; ... when rev_nr is odd, that left-over thing moved down here. E.g. if rev_nr == 5, the loop is left with i==2, rev[0] and rev[1] are filled with pairwise merge bases, and this moves rev[4] to rev[2], so that we can further process rev[0,1,2] with rev_nr set to 3 (i.e. (rev_nr + 1) / 2 below). Sounds correct. > + rev_nr = (rev_nr + 1) / 2; > + } > + > + if (!in_merge_bases(base, rev[0])) > + die(_("base commit should be the ancestor of revision list")); > + > + for (i = 0; i < total; i++) { > + if (base == list[i]) > + die(_("base commit shouldn't be in revision list")); > + } > + > + free(rev); > + return base; > +}