Austin Group Defect Tracker

Aardvark Mark III


Viewing Issue Simple Details Jump to Notes ] Issue History ] Print ]
ID Category Severity Type Date Submitted Last Update
0000754 [1003.1(2013)/Issue7+TC1] System Interfaces Editorial Clarification Requested 2013-09-21 00:24 2013-10-10 16:06
Reporter nsz View Status public  
Assigned To
Priority normal Resolution Rejected  
Status Closed  
Name Szabolcs Nagy
Organization musl libc
User Reference
Section qsort
Page Number 1744
Line Number 56102
Interp Status ---
Final Accepted Text
Summary 0000754: total ordering in qsort is unclear
Description The description of qsort says

    When the same objects (consisting of width 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, they shall define a total ordering on the array.

the first sentence may be read as "cmp shall return the same results
for the same inputs" which does not guarantee transitivity, so the
second sentence is not justified.

i think totality in the context of binary relations means that R(a,b)
and/or R(b,a) hold for all a,b (ie. it does not make much sense in
the context of binary functions)

one might even argue that the comparision function defines a partial
ordering instead of a total one because of the equal elements.

i'm not sure why this sentence is in posix, iso c does not have the
equivalent, and as far as i can tell all sort algorithms terminate
even if the comparision function returns arbitrary results.

in the description of scandir:

    Entries [..] sorted as if by a call to qsort() with the comparison
    function compar, except that compar need not provide total ordering.

i think "except that compar may return arbitrary results" would be clearer
Desired Action If the ordering requirement for the comparision function
is important in qsort then clarify the definition, otherwise
remove that paragraph.

update the description of scandir accordingly.
Tags No tags attached.
Attached Files

- Relationships

-  Notes
(0001839)
Don Cragun (manager)
2013-09-21 01:13

Despite the claims in the Description of this bug, the ISO C99 and C11 standards both say:
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.

In C99 this is subclause 7.20.5 paragraph 4 and in C11 it is subclause 7.22.5 paragraph 4.
(0001840)
shware_systems (reporter)
2013-09-21 04:14

"one might even argue that the comparision function defines a partial
ordering instead of a total one because of the equal elements."

The implication, to me, is that if R(a,b) returns *a <= *b, R(b,a) shall return *b >= *a. Total ordering occurs by only swapping when R(a,b) returns explicitly *a > *b for qsort, not when equals, to make the transitivity issue fairly moot. For a given data set input, afaik, the sorted pointer order should be the same on output; it's not one order on a first run and a different one the next.

I believe bsearch() is allowed to swap pointers because some implementations sort on pointer value, if necessary, when there is more than one equal value and returns the post sub sort lowest addressed equal index, as an extra step that might optimize some application processing. qsort just guarantees equal values will be grouped together as required by bsearch, so that it can indicate at least one record matches key, not that the pointers will be in a particular order within each group.
(0001841)
Don Cragun (manager)
2013-09-21 04:39
edited on: 2013-09-21 04:40

The comments about the R(a,b) function in Note: 0001840 do not apply to the compar() argument to qsort(). It seems that R(a,b) returns non-zero if the item pointed to by a is <= the item pointed to by b and zero if *a > *b (a binary choice). But the compar(a,b) function is required to return a value less than 0 if *a < *b, 0 if *a == *b, and a value greater than 0 if *a > *b (a ternary choice)

(0001844)
shware_systems (reporter)
2013-09-21 05:53

I read it as him saying R(a, b) is shorthand for compar(a, b), and I carried that over. For compar '<=' is 0 or negative then, '>=' 0 or positive, and '>' positive only. Yes, he's using it in the description more as greater/less or equal and I'm showing order of a and b is important because of the compar semantics; swapping the order of a and b requires swapping the sign of the result, and this in conjunction with the qsort algorithm determines the ordering. If qsort swapped on >= then you might get transitivity issues.
(0001871)
Don Cragun (manager)
2013-10-10 16:06

As noted in Note: 0001839 and Note: 0001841, the text in POSIX does come from the C Standard and was not invented by the developers of the POSIX standards, and the statement that compar() is a binary function not giving a total ordering is incorrect. The compar(a,b) function is defined to provide a tertiary response (less than 0 if a is less than b; 0 if they are equal, and greater than 0 if a is greater than b).

For these reasons, this change is rejected.

- Issue History
Date Modified Username Field Change
2013-09-21 00:24 nsz New Issue
2013-09-21 00:24 nsz Name => Szabolcs Nagy
2013-09-21 00:24 nsz Organization => musl libc
2013-09-21 00:24 nsz Section => qsort
2013-09-21 00:24 nsz Page Number => 0
2013-09-21 00:24 nsz Line Number => 0
2013-09-21 00:51 Don Cragun Page Number 0 => 1744
2013-09-21 00:51 Don Cragun Line Number 0 => 56102
2013-09-21 00:51 Don Cragun Interp Status => ---
2013-09-21 01:13 Don Cragun Note Added: 0001839
2013-09-21 04:14 shware_systems Note Added: 0001840
2013-09-21 04:39 Don Cragun Note Added: 0001841
2013-09-21 04:40 Don Cragun Note Edited: 0001841
2013-09-21 05:53 shware_systems Note Added: 0001844
2013-10-10 16:06 Don Cragun Note Added: 0001871
2013-10-10 16:06 Don Cragun Status New => Closed
2013-10-10 16:06 Don Cragun Resolution Open => Rejected


Mantis 1.1.6[^]
Copyright © 2000 - 2008 Mantis Group
Powered by Mantis Bugtracker