Re: [PATCH v2 12/24] pack-bitmap-write: fill bitmap with commit history

[Jonathan Tan <jonathantanmy@google.com>]

> From: Derrick Stolee <dstolee@microsoft.com>
> 
> The fill_bitmap_commit() method assumes that every parent of the given
> commit is already part of the current bitmap. Instead of making that
> assumption, let's walk parents until we reach commits already part of
> the bitmap. Set the value for that parent immediately after querying to
> save time doing double calls to find_object_pos() and to avoid inserting
> the parent into the queue multiple times.

I see from the later patches that this has no effect until the part
where we can skip commits, but as Junio says [1], it's worth mentioning
it here. Maybe something like:

  The fill_bitmap_commit() method assumes that every parent of the given
  commit is already part of the current bitmap. This is currently
  correct, but a subsequent patch will change the nature of the edges of
  the graph from parent-child to ancestor-descendant. In preparation for
  that, let's walk parents...

>  static void fill_bitmap_commit(struct bb_commit *ent,
> -			       struct commit *commit)
> +			       struct commit *commit,
> +			       struct prio_queue *queue)

As far as I can see, this function expects an empty queue and always
ends with the queue empty, and the only reason why we don't instantiate
a new queue every time is so that we can save on the internal array
allocation/deallocation. Maybe add a comment to that effect.

>  {
>  	if (!ent->bitmap)
>  		ent->bitmap = bitmap_new();
>  
> -	/*
> -	 * mark ourselves, but do not bother with parents; their values
> -	 * will already have been propagated to us
> -	 */
>  	bitmap_set(ent->bitmap, find_object_pos(&commit->object.oid));
> -	fill_bitmap_tree(ent->bitmap, get_commit_tree(commit));
> +	prio_queue_put(queue, commit);
> +
> +	while (queue->nr) {
> +		struct commit_list *p;
> +		struct commit *c = prio_queue_get(queue);
> +
> +		bitmap_set(ent->bitmap, find_object_pos(&c->object.oid));
> +		fill_bitmap_tree(ent->bitmap, get_commit_tree(c));
> +
> +		for (p = c->parents; p; p = p->next) {
> +			int pos = find_object_pos(&p->item->object.oid);
> +			if (!bitmap_get(ent->bitmap, pos)) {
> +				bitmap_set(ent->bitmap, pos);
> +				prio_queue_put(queue, p->item);
> +			}
> +		}
> +	}
>  }

[snip rest of code]

Everything else makes sense.