Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C

Funzioni di callback in C: comparatore per `qsort`

Passa un comparatore come puntatore a funzione tipizzato, confronta l’intero intervallo di `int` senza overflow e conserva l’ordine dei record con la stessa chiave.

Versione: ISO C23; implementation support may vary

Sintassi

#include <stdlib.h>

typedef int (*compare_fn)(const void *, const void *);
int compare_items(const void *left, const void *right);

/* For a writable array named items, inside a function: */
compare_fn callback = compare_items;
qsort(items, sizeof items / sizeof items[0], sizeof items[0], callback);

Una callback è una funzione che passi ad altro codice affinché la chiami. qsort, dichiarata in <stdlib.h>, ordina direttamente un array modificabile e non restituisce alcun valore. Riceve l’indirizzo iniziale, il numero di elementi, la dimensione in byte di un elemento e un puntatore a funzione di tipo int (*)(const void *, const void *). Passa compare_items, non compare_items(...): qui il nome della funzione viene convertito in un puntatore, mentre la seconda espressione chiama la funzione. Non usare un cast per adattare un puntatore a funzione incompatibile: chiamare una funzione tramite un tipo di puntatore incompatibile ha comportamento indefinito.

Gli argomenti const void * puntano ai due elementi confrontati. Prima di leggere i campi, assegnali a puntatori al tipo effettivo degli elementi, qualificato con const. Non modificare l’array nel comparatore e non usare le posizioni correnti per determinare il risultato: la libreria può spostare gli elementi tra le chiamate. Definisci un ordine coerente: restituisci un valore negativo, zero o un valore positivo se il primo elemento è rispettivamente minore, equivalente o maggiore del secondo. Conta solo il segno.

INT_MIN e INT_MAX, da <limits.h>, sono i limiti di int. Non restituire a->key - b->key: per esempio, INT_MAX - INT_MIN non è rappresentabile come int, e l’overflow di un intero con segno ha comportamento indefinito. Usa confronti relazionali. In -1, il meno unario nega 1; negare INT_MIN ha a sua volta comportamento indefinito in C23.

Un ordinamento stabile conserva l’ordine di ingresso degli elementi che risultano equivalenti. qsort non lo garantisce. A parità di chiave usa la posizione originale memorizzata come secondo criterio, oppure scegli un ordinamento stabile se il comparatore deve continuare a considerare equivalenti quegli elementi.

In un array terminato da una sentinella, NULL segna la fine dei puntatori ai token; non è il carattere \0. Escludi la sentinella dal conteggio degli elementi da ordinare. Nella ricerca, verifica il limite dell’array prima della lettura e assicurati che un contatore int non superi INT_MAX, nemmeno quando viene incrementato. Il risultato -1 della ricerca significa «non trovato», non è un risultato negativo del confronto.

Esempi

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct item {
    int key;
    int original;
    const char *token;
};

typedef int (*compare_fn)(const void *, const void *);

static int compare_items(const void *left, const void *right)
{
    const struct item *a = left;
    const struct item *b = right;

    if (a->key < b->key) return -1;
    if (a->key > b->key) return 1;
    return (a->original > b->original) - (a->original < b->original);
}

static int find_token(const struct item *items, int capacity, const char *token)
{
    for (int i = 0; i < capacity && items[i].token != NULL; ++i) {
        if (strcmp(items[i].token, token) == 0) return i;
    }
    return -1;
}

int main(void)
{
    struct item items[] = {
        {INT_MAX, 0, "high"},
        {0,       1, "first"},
        {INT_MIN, 2, "low"},
        {0,       3, "second"},
        {0,       0, NULL}
    };
    enum { CAPACITY = sizeof items / sizeof items[0] };
    compare_fn callback = compare_items;

    qsort(items, CAPACITY - 1, sizeof items[0], callback);
    for (int i = 0; i < CAPACITY - 1; ++i) {
        puts(items[i].token);
    }
    printf("missing index: %d\n", find_token(items, CAPACITY, "missing"));
    return 0;
}

Risultato

low
first
second
high
missing index: -1

`first` e `second` hanno la stessa chiave. Il loro ordine dipende da `original`, non dalla stabilità di `qsort`. La ricerca si ferma a `NULL` e restituisce `-1`.

Lezioni correlate

  • C · Lezione 88 · Avanzato · Versione: 3
  • C · Lezione 90 · Avanzato · Versione: 3

Fonti