Introduction

qsort, heapsort, mergesort, bsearch, and many more search and sort functions all take a compar argument to determine the sorting order of elements in an array. The compar function takes the form int (*compar)(const void *, const void *). The compar function’s parameters are the address of two of the elements in the array. The parameters will need to be dereferenced before they can be compared. Any type of value can have a compar function written for it and it can be used to sort an array of any type.

Dereferencing

The comparison function will depend on how we construct the array of element. This is the most important part of the comparison function prototype. Since it’s a pointer to an element in the array, how the array holds element determines how we need to dereference everything.

Array of objects

type_t array[NUM_ELEMENTS];

Since the address of the element in the array is the object, we can access it directly.

int obj_cmp(const void *a, const void *b)
{
    const c_obj_t *o1 = (const c_obj_t *)a;
    const c_obj_t *o2 = (const c_obj_t *)b;
    ...
}

Array of pointers to objects

type_t **array;

The array is an array of pointers so the comparison function receives the address of the array index. We need to dereference the array address to get the object.

int obj_cmp(const void *a, const void *b)
{
    const c_obj_t *o1 = *(const c_obj_t **)a;
    const c_obj_t *o2 = *(const c_obj_t **)b;
    ...

Common Compared Types

Strings and integers are two of the most common types that need to be sorted. Since the dereference requirement tends to trip people up, here are sort functions for these two types.

static int string_cmp(const void *a, const void *b)
{
	const char *sa = *(const char **)a;
	const char *sb = *(const char **)b;

	return strcmp(sa, sb);
}

static int int_cmp(const void *a, const void *b)
{
	int ia = *(int *)a;
	int ib = *(int *)b;

	if (ia == ib)
		return 0;
	if (ia > ib)
		return 1;
	return -1;
}

Example

Using the above comparison functions is really easy. We just need to pass the function as the compar argument to the sort or search function.

int main(int argc, char **argv)
{
	size_t i;
	int    aints[]  = { 9, 7, 8, 1, 2, 4, 10, 9 };
	char  *mystrs[] = { "abc", "1", "a", "c", "dog", "cat", "bat", "xyz" };

	qsort(aints, sizeof(aints)/sizeof(*aints), sizeof(*aints), int_cmp);
	for (i=0; i<sizeof(aints)/sizeof(*aints); i++) {
		printf("%dn", aints[i]);
	}

	printf("---n");

	qsort(mystrs, sizeof(mystrs)/sizeof(*mystrs), sizeof(*mystrs), string_cmp);
	for (i=0; i<sizeof(mystrs)/sizeof(*mystrs); i++) {
		printf("%sn", mystrs[i]);
	}
	return 0;
}

In this example aints is an array of objects (of type int) and mystrs is an array of pointers to each object (strings). That said, since the int_cmp receives a pointer to the array index, we still need to dereference to get the integer values.

Complex Types

Now let’s think about complex types (structs). They’re no different than the previous int and string examples. Let’s use this example type and use some more complete code examples to illustrate.

typedef struct {
    char  *key;
    size_t cnt;
} c_obj_t;

Array of objects

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct {
    char  *key;
    size_t cnt;
} c_obj_t;

int obj_cmp(const void *a, const void *b)
{
    const c_obj_t *o1 = (const c_obj_t *)a;
    const c_obj_t *o2 = (const c_obj_t *)b;

    printf("Comparing obj1: %p, key='%s', cnt=%zu and obj1: %p, key='%s', cnt=%zu\n", o1, o1->key, o1->cnt, o2, o2->key, o2->cnt);
    return strcmp(o1->key, o2->key);
}

#define NUM_ELEMENTS 10
int main(int argc, char **argv)
{
    c_obj_t array[NUM_ELEMENTS];
    char tempa[128];
    size_t i;

    for (i=0; i<NUM_ELEMENTS; i++) {
        size_t cnt = NUM_ELEMENTS-i-1;
        snprintf(tempa, sizeof(tempa), "Object #%zu", cnt);
        array[i].key = strdup(tempa);
        array[i].cnt = cnt;

        printf("Added obj: key='%s', cnt=%zu\n", array[i].key, array[i].cnt);
    } 

    qsort(array, NUM_ELEMENTS, sizeof(*array), obj_cmp);
    for (i=0; i<NUM_ELEMENTS; i++) {
        printf("Validating obj: key='%s', cnt=%zu\n", array[i].key, array[i].cnt);
    }

    return 0;
}

This is similar to the array of ints where each element in the array is the type. The obj_cmp function does not need to dereference the arguments because the array index is the object.

Array of pointers to objects

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct {
    char  *key;
    size_t cnt;
} c_obj_t;

int obj_cmp(const void *a, const void *b)
{
    const c_obj_t *o1 = *(const c_obj_t **)a;
    const c_obj_t *o2 = *(const c_obj_t **)b;

    if (o1 && !o2)
        return 1;
    if (!o1 && o2)
        return -1;
    if (!o1 && !o2)
        return 0;

    printf("Comparing obj1: %p, key='%s', cnt=%zu and obj1: %p, key='%s', cnt=%zu\n", o1, o1->key, o1->cnt, o2, o2->key, o2->cnt);
    return strcmp(o1->key, o2->key);
}

int main(int argc, char **argv)
{
    c_obj_t *obj;
    c_obj_t **array;
    size_t num_elements = 10;
    char tempa[128];
    size_t i;

    array = calloc(num_elements, sizeof(*array));
    for (i=num_elements; i-->0; ) {
        snprintf(tempa, sizeof(tempa), "Object #%zu", i);

        obj      = malloc(sizeof(*obj));
        obj->key = strdup(tempa);
        obj->cnt = i;
        array[i] = obj;

        printf("Added obj: %p, key='%s', cnt=%zu\n", obj, obj->key, obj->cnt);
    } 

    qsort(array, num_elements, sizeof(*array), obj_cmp);
    for (i=0; i<num_elements; i++) {
        obj = array[i];
        printf("Validating obj: %p, key='%s', cnt=%zu\n", obj, obj->key, obj->cnt);
    }

    for (i=0; i<num_elements; i++) {
        free(array[i]);
    }
    free(array);

    return 0;
}

This one is similar to the array of strings where each element is a pointer to an object. The obj_cmp function needs to dereference the arguments because they’re pointers to pointers in this example.

Also, in this obj_cmp function we check the pointers are valid. Unlike the array of objects example, some of the entries in the array could be NULL. We need to have these extra checks to ensure we don’t access an element in a NULL pointer.