Function ahead_behind

commit-reach.c:1117–1193

}

void ahead_behind(struct repository *r,
		  struct commit **commits, size_t commits_nr,
		  struct ahead_behind_count *counts, size_t counts_nr)
{
	struct nonstale_queue queue = {
		{ .compare = compare_commits_by_gen_then_commit_date }
	};
	size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);

	if (!commits_nr || !counts_nr)
		return;

	for (size_t i = 0; i < counts_nr; i++) {
		counts[i].ahead = 0;
		counts[i].behind = 0;
	}

	ensure_generations_valid(r, commits, commits_nr);

	init_bit_arrays(&bit_arrays);

	for (size_t i = 0; i < commits_nr; i++) {
		struct commit *c = commits[i];
		struct bitmap *bitmap = get_bit_array(c, width);

		bitmap_set(bitmap, i);
		insert_no_dup(&queue, c);
	}

	while (queue.max_nonstale) {
		struct commit *c = nonstale_queue_get(&queue);
		struct commit_list *p;
		struct bitmap *bitmap_c = get_bit_array(c, width);

		for (size_t i = 0; i < counts_nr; i++) {
			int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
			int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);

			if (reach_from_tip ^ reach_from_base) {
				if (reach_from_base)
					counts[i].behind++;
				else
					counts[i].ahead++;
			}
		}

		for (p = c->parents; p; p = p->next) {
			struct bitmap *bitmap_p;

			repo_parse_commit(r, p->item);

			bitmap_p = get_bit_array(p->item, width);
			bitmap_or(bitmap_p, bitmap_c);

			/*
			 * If this parent is reachable from every starting
			 * commit, then none of its ancestors can contribute
			 * to the ahead/behind count. Mark it as STALE, so