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

> On Mon, Jun 10, 2013 at 12:21:00AM -0700, Junio C Hamano wrote:
>
>> > 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.
>
> Yeah, I don't think I looked at that at all last time (mostly because it
> only large as the graph gets wide, which is typically acceptable for
> us). But it should be easy to do.
>
>> > 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.
>
> Squashable patch is below.
>
>> > 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.
>
> I converted this to a void pointer in my patch below, simply because it
> makes it easier to write a test-queue that operates on ints. Due to
> implicit casting, it should work for the most part without changing the
> calling code unless you have a caller that does something like:
>
>   commit_queue_get(&q)->date
>
> or similar. I didn't change the name, either. It may be silly to call it
> "commit_queue" still since it is now more general. I simply called mine
> "queue" (I wanted "pqueue", but that conflicted with globals defined by
> OpenSSL; yours is a more general queue anyway, so maybe that is a good
> name).

> Here's the patch with the tests, meant to be squashed into your 2/4. As
> I mentioned above, you may want to further tweak the name, which would
> require fixing up the rebase patches on top.
>
> If you don't want to do the "s/struct commit/void/" change now, we can
> probably just have test-queue stuff the ints into commit pointers.
>
> The tests themselves are not extremely extensive, but at least let you
> check that you implemented the heap correctly. :)