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