View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0000754 | 1003.1(2013)/Issue7+TC1 | System Interfaces | public | 2013-09-21 00:24 | 2013-10-10 16:06 |
| Reporter | nsz | Assigned To | |||
| Priority | normal | Severity | Editorial | Type | Clarification Requested |
| Status | Closed | Resolution | Rejected | ||
| 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. | ||||
|
|
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. |
|
|
"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. |
|
|
The comments about the R(a,b) function in 0000754: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) |
|
|
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. |
|
|
As noted in 0000754:0001839 and 0000754: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. |
| 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 |
