qsort on an array of pointers to Objective-C objects

Question

I have an array of pointers to Objective-C objects. These objects have a sort key associated with them. I'm trying to use qsort to sort the array of pointers to these objects. However, the first time my comparator is called, the first argument points to the first element in my array, but the second argument points to garbage, giving me an EXC_BAD_ACCESS when I try to access its sort key.

Here is my code (paraphrased):

- (void)foo:(int)numThingies {
    Thingie **array;
    array = malloc(sizeof(deck[0])*numThingies);

    for(int i = 0; i < numThingies; i++) {
        array[i] = [[Thingie alloc] initWithSortKey:(float)random()/RAND_MAX];
    }

    qsort(array[0], numThingies, sizeof(array[0]), thingieCmp);
}

int thingieCmp(const void *a, const void *b) {
    const Thingie *ia = (const Thingie *)a;
    const Thingie *ib = (const Thingie *)b;

    if (ia.sortKey > ib.sortKey) return 1; //ib point to garbage, so ib.sortKey produces the EXC_BAD_ACCESS
    else return -1;
}

Any ideas why this is happening?

Answer 1

The problem is two fold:

• the first argument to qsort needs to be a pointer to the beginning of the array

• the arguments passed to your sort function are actually pointers to the pointers of your data

Consider this working code:

int thingieCmp(const void *a, const void *b) {
    NSObject *aO = *(NSObject **)a;
    NSObject *bO = *(NSObject **)b;

    if (aO.hash > bO.hash) return 1; 
    else return -1;
}


int main (int argc, const char * argv[]) {
    NSObject **array;
    array = malloc(sizeof(NSObject*)*20);

    for(int i = 0; i < 20; i++) {
        array[i] = [NSObject new];
    }

    qsort(array, 20, sizeof(NSObject*), thingieCmp);

    return 0;
}

Note that the comparison function resolves the data pointers by NSObject *aO = *(NSObject **)a and the qsort function takes array as an argument directly.

All of this, though, begs the question of Why bother?

NSArray is very good at holding arrays of objects and is quite conveniently sortable. Performance is excellent in the general case. If performance analysis indicates that it isn't, you can optimize it away relatively easily.

Note, also, that I have been consistent in use of sizeof() -- same type in both places. Also, the const in your original code is not necessary.

Answer 2

I think, one mistake lies right in the line

qsort(array[0], numThingies, sizeof(array[0]), thingieCmp);

Try

qsort(&array[0], numThingies, sizeof(array[0]), thingieCmp);

or even

qsort(array, numThingies, sizeof(array[0]), thingieCmp);

instead. The compiler won't complain here, as qsort is supposed to take a void* and you pass it a Thingy* which can legally be cast to void* without warning, but you really want qsort to operate on the entire array, which has type Thingy**.

Another thing is: the comparator will be called with pointers to the array slots as arguments, so what you get is actually a Thingy**:

int 
thingieCmp(void* a, void* b) 
{
    Thingie *ia = *((Thingie**)a);
    Thingie *ib = *((Thingie**)b);

    ...
}