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

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

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

Postby Roger|Dyalog on Wed Nov 25, 2020 6:51 pm

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).
Roger|Dyalog
 
Posts: 238
Joined: Thu Jul 28, 2011 10:53 am

Re: adventures in code coverage: a curious property of qsort

Postby JoHo on Sat Nov 28, 2020 3:41 pm

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
User avatar
JoHo
 
Posts: 29
Joined: Sat Nov 28, 2009 12:51 pm
Location: Austria, EU

Re: adventures in code coverage: a curious property of qsort

Postby Roger|Dyalog on Sun Nov 29, 2020 5:49 am

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).
Roger|Dyalog
 
Posts: 238
Joined: Thu Jul 28, 2011 10:53 am


Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest