CKTIS / C
Funciones de retorno de llamada en C: comparador para `qsort`
Pasa un comparador como puntero a función con tipo, compara todo el rango de `int` sin desbordamiento y conserva el orden de los registros con la misma clave.
Versión: ISO C23; implementation support may vary
Sintaxis
#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 función de retorno de llamada (callback) es una función que entregas a otro código para que la invoque. qsort, de <stdlib.h>, ordena un array modificable en el mismo lugar y no devuelve ningún valor. Recibe la dirección inicial, el número de elementos, el tamaño en bytes de un elemento y un puntero a función de tipo int (*)(const void *, const void *). Pasa compare_items, no compare_items(...): el nombre de la función se convierte aquí en un puntero, mientras que la segunda expresión invoca la función. No fuerces con una conversión un puntero a función incompatible: invocar la función mediante un tipo de puntero incompatible tiene comportamiento indefinido.
Los argumentos const void * apuntan a los elementos que se comparan. Asígnalos a punteros al tipo real de los elementos, cualificado con const, antes de leer sus campos. No modifiques el array en el comparador ni bases el resultado en las posiciones actuales: la biblioteca puede mover los elementos entre llamadas. Define un orden coherente: devuelve un valor negativo, cero o un valor positivo si el primer elemento es menor que el segundo, equivalente o mayor, respectivamente. Solo importa el signo.
INT_MIN e INT_MAX, de <limits.h>, son los límites de int. No devuelvas a->key - b->key: por ejemplo, INT_MAX - INT_MIN no cabe en int, y el desbordamiento de un entero con signo tiene comportamiento indefinido. Usa comparaciones relacionales. En -1, el menos unario niega 1; negar INT_MIN también tiene comportamiento indefinido en C23.
Una ordenación estable conserva el orden de entrada de los elementos que se comparan como equivalentes. qsort no lo garantiza. Desempata con la posición original almacenada o usa una ordenación estable si el comparador debe seguir considerando equivalentes esos elementos.
En un array terminado por un centinela, NULL marca el final de los punteros a tokens; no es el carácter \0. Excluye el centinela del recuento de elementos que se ordenarán. Antes de leer, comprueba el límite del array y evita que un contador int supere INT_MAX, incluso al incrementarlo. El resultado -1 de la búsqueda significa «no encontrado», no un resultado negativo de la comparación.
Ejemplos
#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;
}
Resultado
low first second high missing index: -1
`first` y `second` comparten clave. Su orden viene dado por `original`, no por la estabilidad de `qsort`. La búsqueda se detiene en `NULL` y devuelve `-1`.
Lecciones relacionadas
- C · Lección 88 · Avanzado · Versión: 3
- C · Lección 90 · Avanzado · Versión: 3