Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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

Fontes