Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

Callbacks in C: writing a `qsort` comparator

Pass a comparator as a typed function pointer, compare the full `int` range without overflow, and preserve the input order of records with equal keys.

Version: 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);

A callback is a function you give to other code for it to call. qsort from <stdlib.h> sorts a writable array in place and returns no value. It takes the array's starting address, element count, element size in bytes, and a function pointer of type int (*)(const void *, const void *). Pass compare_items, not compare_items(...): the function name converts to a pointer here, while the latter expression calls it. Do not cast an incompatible function pointer to make it fit; calling through an incompatible pointer type is undefined behavior.

The const void * arguments point to the two elements being compared. Assign them to pointers to the actual const-qualified element type before reading fields. Do not modify the array in the comparator or base the result on current positions: the library may move elements between calls. Define a consistent ordering: return a negative value, zero, or a positive value when the first element is less than, equivalent to, or greater than the second, respectively. Only the sign matters.

INT_MIN and INT_MAX from <limits.h> are the limits of int. Do not return a->key - b->key: for example, INT_MAX - INT_MIN does not fit in int, and signed overflow is undefined behavior. Use relational comparisons instead. In -1, unary minus negates 1; negating INT_MIN itself also has undefined behavior in C23.

A stable sort preserves the input order of elements that compare equal. qsort does not guarantee this. Break ties using the stored original position, or use a stable sort if the comparator must still treat those elements as equivalent.

In a sentinel-terminated array, NULL marks the end of the token pointers; it is not the character \0. Exclude the sentinel from the sort count. When scanning, check the array bound before reading and ensure an int counter never exceeds INT_MAX, including when incremented. The lookup result -1 means not found; it is not a negative comparison result.

Examples

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

Result

low
first
second
high
missing index: -1

`first` and `second` share a key. Their order comes from `original`, not from `qsort` being stable. The lookup stops at `NULL` and returns `-1`.

Related lessons

  • C · Lesson 88 · Advanced · Version: 3
  • C · Lesson 90 · Advanced · Version: 3

Sources