adventures in code coverage: a curious property of qsort()

[Roger|Dyalog]

qsort() is a C library function for quicksort.

      ⍝
qsort(void*base, size_t nitems, size_t size, 
                                  int (*compf)(const void*, const void*))
 // base   pointer to the values to be sorted
 // n      # of items
 // size   size of each item (←→ sizeof(void*))
 // compf  function for comparing items, given the pointers to them

The point of interest here is the comparison function compf(). Its arguments are two pointers xv and yv to the array to be sorted; its result should be ¯1, 0, or 1, depending on whether the cell pointed to by xv is less than, equal to, or greater than the cell pointed to by yv. An example of such a function:

      ⍝
static int LIBCALL comparef(const void *xv, const void *yv)
{
    BOUND i, j;
    i=*(BOUND*)xv;
    j=*(BOUND*)yv;
    ASSERT(i<j, INTERNAL_ERROR);
    return *(rargv0+i)-*(rargv0+j);
}

In this instance, the array pointed to by xv and yv is initialized to be the integers ⍳≢⍵, the i and the j in comparef(), remains a permutation of ⍳≢⍵ throughout, and eventually becoming the result of ⍋⍵. (rargv0 points to ⍵.) The curious property is that qsort() seems to always invoke comparef() so that i (*xv) is always less than j (*yv), and the INTERNAL ERROR is never signaled. (At least, this is true for the C libraries I have access to.) I can not think of why this should be true.

I discovered this property in trying to reach some code, which is effectively:

      ⍝
 // return *(rargv0+i)-*(rargv0+j);
    if(d=*(rargv0+i)-*(rargv0+j))return d;
    return i<j?-1:1;

But on the last line, it never reaches the 1 (because i<j is always true).

[JoHo]

Hi Roger,

Long time no C.

The things I do not understand:
a) in

Code: Select all

 *(rargv0+i)-*(rargv0+j)

is this pointer arithmetic on Item level?
Since i is a interger (or integer array) and rargv0 still is a pointer to ⍵.
Why would *(rargv0+i)-*(rargv0+j) be limited to result in just [-1,0,1]?

b)

Code: Select all

 // return *(rargv0+i)-*(rargv0+j);
    if(d=*(rargv0+i)-*(rargv0+j))return d;
    return i<j?-1:1;

What is d? Is if(d) true for non-zero or non-NULL values?
- - -

I am guessing, qsort would just walk upward along one axis, probably serveral times?

Greetings,
JoHo

[Roger|Dyalog]

Hi JoHo.

a. You are correct. I misspoke: The specs say that the result of the compf() function is permitted to be <0, =0, or >0, not restricted to ¯1, 0, or 1.

b. In the C construct if(blah), a non-zero blah is construed as true and a zero blah is construed as false.

qsort() as used in an APL interpreter would traverse the major cells of ⍵, expected to be O(⍟≢⍵) times. But I can not see any reason why qsort() would supplied the pointers/indices to the major cells to compf() such that the first pointer/index is always less than the second pointer/index (however the major cells compare in the ordering).