* type_size_sort
@ 2005-12-06 21:19 Morten Welinder
2005-12-06 21:38 ` type_size_sort Andreas Ericsson
2005-12-06 21:45 ` type_size_sort Junio C Hamano
0 siblings, 2 replies; 7+ messages in thread
From: Morten Welinder @ 2005-12-06 21:19 UTC (permalink / raw)
To: GIT Mailing List
static int type_size_sort(const struct object_entry *a, const struct
object_entry *b)
{
...
return a < b ? -1 : (a > b);
}
This does not look valid. the standard says you must not depend on the
location:
[#4] When the same objects (consisting of size bytes,
irrespective of their current positions in the array) are
passed more than once to the comparison function, the
results shall be consistent with one another. That is, for
qsort they shall define a total ordering on the array, and
for bsearch the same object shall always compare the same
way with the key.
M.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: type_size_sort
2005-12-06 21:19 type_size_sort Morten Welinder
@ 2005-12-06 21:38 ` Andreas Ericsson
2005-12-06 21:46 ` type_size_sort Junio C Hamano
2005-12-07 0:51 ` type_size_sort Morten Welinder
2005-12-06 21:45 ` type_size_sort Junio C Hamano
1 sibling, 2 replies; 7+ messages in thread
From: Andreas Ericsson @ 2005-12-06 21:38 UTC (permalink / raw)
To: GIT Mailing List
Morten Welinder wrote:
> static int type_size_sort(const struct object_entry *a, const struct
> object_entry *b)
> {
> ...
> return a < b ? -1 : (a > b);
> }
>
> This does not look valid. the standard says you must not depend on the
> location:
>
>
> [#4] When the same objects (consisting of size bytes,
> irrespective of their current positions in the array) are
> passed more than once to the comparison function, the
> results shall be consistent with one another. That is, for
> qsort they shall define a total ordering on the array, and
> for bsearch the same object shall always compare the same
> way with the key.
>
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;
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: type_size_sort
2005-12-06 21:19 type_size_sort Morten Welinder
2005-12-06 21:38 ` type_size_sort Andreas Ericsson
@ 2005-12-06 21:45 ` Junio C Hamano
1 sibling, 0 replies; 7+ messages in thread
From: Junio C Hamano @ 2005-12-06 21:45 UTC (permalink / raw)
To: Morten Welinder; +Cc: git
Morten Welinder <mwelinder@gmail.com> writes:
> static int type_size_sort(const struct object_entry *a, const struct
> object_entry *b)
> {
> ...
> return a < b ? -1 : (a > b);
> }
>
> This does not look valid.
Then something like this?
---
diff --git a/pack-objects.c b/pack-objects.c
index a62c9f8..c27fee5 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -296,7 +296,7 @@ static int type_size_sort(const struct o
return -1;
if (a->size > b->size)
return 1;
- return a < b ? -1 : (a > b);
+ return memcmp(a->sha1, b->sha1, 20);
}
struct unpacked {
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: type_size_sort
2005-12-06 21:38 ` type_size_sort Andreas Ericsson
@ 2005-12-06 21:46 ` Junio C Hamano
2005-12-07 0:51 ` type_size_sort Morten Welinder
1 sibling, 0 replies; 7+ messages in thread
From: Junio C Hamano @ 2005-12-06 21:46 UTC (permalink / raw)
To: Andreas Ericsson; +Cc: git
Andreas Ericsson <ae@op5.se> writes:
> 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;
And I suspect Morten would say the same thing about ptrdiff_t
could be larger than an int.
I personally feel this would not make any practical difference
on sane architectures either way, though..
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: type_size_sort
2005-12-06 21:38 ` type_size_sort Andreas Ericsson
2005-12-06 21:46 ` type_size_sort Junio C Hamano
@ 2005-12-07 0:51 ` Morten Welinder
2005-12-07 2:28 ` type_size_sort Junio C Hamano
1 sibling, 1 reply; 7+ messages in thread
From: Morten Welinder @ 2005-12-07 0:51 UTC (permalink / raw)
To: Andreas Ericsson; +Cc: GIT Mailing List
> 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.
And it is well known that some qsort implementations will do nasty
things if the sorting order is not consistent. I've seen Perl core
dumps on that account, although that is a while ago.
M.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: type_size_sort
2005-12-07 0:51 ` type_size_sort Morten Welinder
@ 2005-12-07 2:28 ` Junio C Hamano
2005-12-07 3:01 ` type_size_sort Morten Welinder
0 siblings, 1 reply; 7+ messages in thread
From: Junio C Hamano @ 2005-12-07 2:28 UTC (permalink / raw)
To: Morten Welinder; +Cc: git
Morten Welinder <mwelinder@gmail.com> writes:
>> 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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: type_size_sort
2005-12-07 2:28 ` type_size_sort Junio C Hamano
@ 2005-12-07 3:01 ` Morten Welinder
0 siblings, 0 replies; 7+ messages in thread
From: Morten Welinder @ 2005-12-07 3:01 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
> Notice? The comparison of two pointers you originally pointed
> out is not about the location in list[]. They are values stored
> there.
Ah, right you are.
Mildly relatedly, notice that a<b can be valid when a-b<0 is
not. ptrdiff_t is not required to be big enough to hold the difference!
(A highly dubious part of the C standard.)
M.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2005-12-07 3:01 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-12-06 21:19 type_size_sort Morten Welinder
2005-12-06 21:38 ` type_size_sort Andreas Ericsson
2005-12-06 21:46 ` type_size_sort Junio C Hamano
2005-12-07 0:51 ` type_size_sort Morten Welinder
2005-12-07 2:28 ` type_size_sort Junio C Hamano
2005-12-07 3:01 ` type_size_sort Morten Welinder
2005-12-06 21:45 ` type_size_sort Junio C Hamano
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.