CKTIS / C
Funções de callback em C: comparador para `qsort`
Passe um comparador como ponteiro para função com tipo, compare todo o intervalo de `int` sem transbordo e preserve a ordem dos registos com a mesma chave.
Versão: ISO C23; implementation support may vary
Sintaxe
#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);Uma função de callback é uma função que se passa a outro código para que este a invoque. qsort, de <stdlib.h>, ordena um vetor modificável no próprio local e não devolve valor. Recebe o endereço inicial, o número de elementos, o tamanho de um elemento em bytes e um ponteiro para função do tipo int (*)(const void *, const void *). Passe compare_items, não compare_items(...): aqui, o nome da função é convertido num ponteiro, ao passo que a segunda expressão chama a função. Não force a conversão de um ponteiro para função incompatível: uma chamada através de um tipo de ponteiro incompatível tem comportamento indefinido.
Os argumentos const void * apontam para os dois elementos a comparar. Atribua-os a ponteiros para o tipo real dos elementos, qualificado com const, antes de ler os campos. Não altere o vetor no comparador nem use as posições atuais para decidir o resultado: a biblioteca pode mover os elementos entre chamadas. Defina uma ordem coerente: devolva um valor negativo, zero ou um valor positivo se o primeiro elemento for, respetivamente, menor, equivalente ou maior do que o segundo. Só o sinal interessa.
INT_MIN e INT_MAX, de <limits.h>, são os limites de int. Não devolva a->key - b->key: por exemplo, INT_MAX - INT_MIN não cabe em int, e o transbordo de um inteiro com sinal tem comportamento indefinido. Use comparações relacionais. Em -1, o menos unário nega 1; negar o próprio INT_MIN também tem comportamento indefinido em C23.
Uma ordenação estável preserva a ordem de entrada dos elementos que o comparador considera equivalentes. qsort não o garante. Em caso de empate, use a posição original guardada ou escolha uma ordenação estável se o comparador tiver de continuar a considerar esses elementos equivalentes.
Num vetor terminado por uma sentinela, NULL indica o fim dos ponteiros para tokens; não é o caráter \0. Exclua a sentinela da contagem de elementos a ordenar. Durante a pesquisa, verifique o limite do vetor antes da leitura e garanta que um contador int não ultrapassa INT_MAX, nem ao ser incrementado. O resultado -1 da pesquisa significa «não encontrado» e não é um resultado negativo da comparação.
Exemplos
#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` e `second` têm a mesma chave. A ordem resulta de `original`, não da estabilidade de `qsort`. A pesquisa para em `NULL` e devolve `-1`.
Lições relacionadas
- C · Lição 88 · Avançado · Versão: 3
- C · Lição 90 · Avançado · Versão: 3