KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C

Callbacks in C: een vergelijkingsfunctie voor `qsort`

Geef een vergelijkingsfunctie door als getypeerde functiepointer, vergelijk het hele `int`-bereik zonder overflow en behoud de invoervolgorde bij gelijke sleutels.

Versie: ISO C23; implementation support may vary

Syntax

#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);

Een callback is een functie die je aan andere code meegeeft, zodat die code haar kan aanroepen. qsort uit <stdlib.h> sorteert een beschrijfbare array ter plekke en geeft geen waarde terug. De functie krijgt het beginadres, het aantal elementen, de grootte van één element in bytes en een functiepointer van het type int (*)(const void *, const void *). Geef compare_items door, niet compare_items(...): de functienaam wordt hier omgezet in een pointer, terwijl de tweede expressie de functie aanroept. Dwing geen passend type af met een cast van een incompatibele functiepointer: aanroepen via een incompatibel pointertype geeft ongedefinieerd gedrag.

De argumenten const void * wijzen naar de twee te vergelijken elementen. Wijs ze toe aan pointers naar het werkelijke elementtype met const voordat je velden leest. Wijzig de array niet in de vergelijkingsfunctie en baseer de uitkomst niet op de huidige posities: de bibliotheek mag elementen tussen aanroepen verplaatsen. Definieer een consistente volgorde: geef een negatieve waarde, nul of een positieve waarde terug als het eerste element respectievelijk kleiner, gelijkwaardig of groter is dan het tweede. Alleen het teken telt.

INT_MIN en INT_MAX uit <limits.h> zijn de grenzen van int. Geef niet a->key - b->key terug: INT_MAX - INT_MIN past bijvoorbeeld niet in int, en overflow van een geheel getal met teken geeft ongedefinieerd gedrag. Gebruik relationele vergelijkingen. In -1 negeert de unaire min 1 in rekenkundige zin; ook het nemen van het tegengestelde van INT_MIN heeft in C23 ongedefinieerd gedrag.

Een stabiele sortering behoudt de invoervolgorde van elementen die als gelijk worden vergeleken. qsort garandeert dit niet. Gebruik bij gelijke sleutels de opgeslagen oorspronkelijke positie als tweede criterium, of kies een stabiele sortering als de vergelijkingsfunctie de elementen als gelijkwaardig moet blijven behandelen.

In een array met een eindmarkering geeft NULL het einde van de tokenpointers aan; het is niet het teken \0. Tel de eindmarkering niet mee bij het sorteren. Controleer bij het zoeken de arraygrens vóór het lezen en zorg dat een int-teller ook bij het verhogen nooit boven INT_MAX uitkomt. De zoekuitkomst -1 betekent ‘niet gevonden’ en is geen negatieve vergelijkingsuitkomst.

Voorbeelden

#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;
}

Resultaat

low
first
second
high
missing index: -1

`first` en `second` hebben dezelfde sleutel. Hun volgorde komt door `original`, niet door stabiliteit van `qsort`. Het zoeken stopt bij `NULL` en levert `-1` op.

Gerelateerde lessen

  • C · Les 88 · Gevorderd · Versie: 3
  • C · Les 90 · Gevorderd · Versie: 3

Bronnen