Subject: Re: [PATCH v3 00/14] Clean up how fetch_pack() handles the heads list

From: Michael Haggerty <[email-masked]>
Date: Mon, 17 Sep 2012 14:55:37 +0200

On 09/11/2012 12:10 AM, Junio C Hamano wrote:
> Michael Haggerty <[email-masked]> writes:
> 
>>> OK.  As long as the sort order matches the order string-list
>>> internally uses for its bisection search, it won't be a problem,
>>> then.
>>
>> The sorting is crucial but there is no bisection involved.  The sorted
>> linked-list of references available from the remote and the sorted
>> string_list of requested references are iterated through in parallel.
> 
> What I meant was that the order used by string-list is pretty much
> internal to string-list implementation for its "quickly locate where
> to insert" bisection.  It happens to be the byte value order, I
> think, but the point is whatever order it is, that has to match the
> order we keep references in the other data source you walk in
> parallel to match (i.e. the linked list of references).

Yes, your point is good that the two sort orders have to agree.
Currently, they both use strcmp() order, so the situation is OK.

It is interesting that you consider the sort order of string_list to be
somewhat of an internal implementation detail.  I had thought of its
current behavior as being the obvious thing and considered it part of
the API's contract.  For example, the current sort order is already
observable via the API through iteration or by calling
print_string_list().  Therefore I think that we should document the
strcmp() sort order as part of the string_list contract.  Patch coming soon.

If, at some future time, somebody wants a string_list that is sorted by
a different criterion, then the order should be determined via a
callback function specified by the user.  The callback function could
even be stored in the string_list header, to allow such lists to be used
in combination with the "functions for sorted lists only".

Michael

-- 
Michael Haggerty
[email-masked]
http://softwareswirl.blogspot.com/