Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 10, 2013, 07:21 UTC
Message-ID: <7vwqq2l9cz.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20130610052500.GD3621@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

> It may be worth looking again for other places to use this over
> commit_list, but even the caller you are introducing here justifies its
> presence.

The next candidate is paint-down-to-common, probably.

> Also, I wrote some basic tests to cover the priority queue as a unit. I
> can rebase them on your commit if you are interested.

It would be great.

Show 10 quoted lines

> A few comments on the code itself:
>
>> +void commit_queue_put(struct commit_queue *queue, struct commit *commit)
>
> Is it worth making this "struct commit *" a void pointer, and handling
> arbitrary items in our priority queue? The compare function should be
> the only thing that dereferences them.
>  
> I do not have any non-commit priority queue use in mind, but I do not
> think it adds any complexity in this case.

I didn't either (and still I don't think of one), but I agree that the implementation can be reused for pq of any type, as long as it is a pointer to struct.

Show 10 quoted lines

>> +	/* Bubble up the new one */
>> +	for (ix = queue->nr - 1; ix; ix = parent) {
>> +		parent = (ix - 1) / 2;
>> +		if (compare(queue->array[parent], queue->array[ix],
>> +			    queue->cb_data) < 0)
>> +			break;
>
> In my implementation, I stopped on "compare() <= 0". It is late and my
> mind is fuzzy, but I recall that heaps are never stable with respect to
> insertion order, so I don't think it would matter.

It would matter in the sense that we cannot replace linked-list, if the caller wants stability. It is more like "we cannot do anything about it" than "it would not matter".

We can make each queue element a pair of <pointer to payload, insertion counter>, and tiebreak using the insertion order, if the callers want the same stability as linked-list implementation, but I tend to think it really matters.