qsort su un array di puntatori a oggetti Objective-C

Question

Ho un array di puntatori a oggetti Objective-C. Questi oggetti hanno una chiave di ordinamento ad essi associati. Sto cercando di utilizzare qsort per ordinare l'array di puntatori a questi oggetti. Tuttavia, la prima volta che il mio comparatore è chiamato, i primi punti argomento al primo elemento nella mia matrice, ma i secondi punti argomento per spazzatura, dandomi un EXC_BAD_ACCESS quando provo ad accedere alla sua chiave di ordinamento.

Ecco il mio codice (parafrasato):

- (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;
}

Tutte le idee perché questo sta accadendo?

Answer 1

Il problema è duplice:

• il primo argomento esigenze qsort essere un puntatore all'inizio dell'array

• gli argomenti passati alla funzione di ordinamento sono in realtà puntatori alle indicazioni dei dati

Si consideri questo codice di lavoro:

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;
}

Si noti che la funzione di confronto risolve i puntatori di dati dal NSObject *aO = *(NSObject **)a e la funzione qsort prende array come argomento direttamente.

Tutto questo, però, pone la questione di Perché preoccuparsi?

NSArray è molto buona in possesso di matrici di oggetti ed è molto convenientemente sortable. Le prestazioni sono eccellenti nel caso generale. Se l'analisi delle prestazioni indica che non lo è, è possibile ottimizzare via in modo relativamente semplice.

Si noti, inoltre, che sono stato coerente in uso di sizeof() - stesso tipo in entrambi i luoghi. Inoltre, il const nel codice originale non è necessaria.

Answer 2

Credo che, bugie un errore a destra nella linea

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

Prova

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

o anche

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

, invece. Il compilatore non si lamenterà qui, come qsort dovrebbe prendere un void* e si passa una Thingy* che può essere legalmente cast void* senza preavviso, ma si vuole veramente qsort di operare su tutta la gamma, che è di tipo Thingy**.

Un'altra cosa è: il comparatore sarà chiamato con puntatori alle slot matrice come argomenti, quindi quello che si ottiene è in realtà un Thingy**:

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

    ...
}