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