Re: type_size_sort

From: Junio C Hamano <junkio@cox.net>
Date: Dec 7, 2005, 02:28 UTC
Message-ID: <7vmzjdy721.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <118833cc0512061651y57ddcdc7pd26996b40c08d225@mail.gmail.com>

Morten Welinder <mwelinder@gmail.com> writes:

Show 11 quoted lines

>> It's perfectly correct. If the same list was to be passed to
>> create_sorted_list() twice it will come out exactly the same the second
>> time as it did the first. The only thing to remark on is that the return
>> above could be written as below instead:
>>
>>         return a - b;
>
> That is not what the part  of the standard I quoted says.  It very
> clearly forbids the sorting function from depending on the pointers'
> values.  I can even see an implementation actually using this
> requirement.

What you say is correct, and people should be careful when using qsort(), but it does not apply to this case. The patch I posted is not necessary. Andreas' rewrite quoted above, however, is invalid when ptrdiff_t (a-b) overflows int range.

The code as written by Linus back on June 25 is correct, but that sort callchain is written in an unusual way to confuse us (you were, and I was initially after seeing your message).

(1) The caller look like this.  It prepares an array of pointers
    in list[], calls qsort with sort_comparator() as the
    function to sort this list[].  Each element in this list[]
    is a pointer to struct object_entry.

	for (i = 0; i < nr_objects; i++)
		list[i] = objects + i;
	current_sort = sort;
	qsort(list, nr_objects, sizeof(struct object_entry *), sort_comparator);

(2) sort_comparator() is called by qsort() with the standard
    calling convention -- two pointers pointing into the array
    being sorted.  It calls current_sort() function set up by
    (1), giving it the pointers *FETCHED* *FROM* the locations
    these two incoming pointers are pointing at.

        static entry_sort_t current_sort;
        static int sort_comparator(const void *_a, const void *_b)
        {
                struct object_entry *a = *(struct object_entry **)_a;
                struct object_entry *b = *(struct object_entry **)_b;
                return current_sort(a,b);
        }

(3) Then type_size_sort() uses compariosn of these two pointers
    as the tiebreaker.

Notice? The comparison of two pointers you originally pointed out is not about the location in list[]. They are values stored there.