Using bsearch() with GLib Arrays

GLib provides many handy array classes. GArray, GByteArray, and GPtrArray cover most use cases for arrays. However, you might notice they don't include a binary search function. There is a pretty simple way to do this yourself, using the bsearch() function from libc.

bsearch() is a generic binary search implementation that is part of libc and C89. It should be available everywhere GLib is.

Let's implement it for GPtrArray.

#include <glib.h>
#include <stdlib.h>

gpointer
g_ptr_array_bsearch (GPtrArray     *array,
                     GCompareFunc   compare_func,
                     gconstpointer  key)
{
    gpointer *ret;

    g_return_if_fail(array);
    g_return_if_fail(compare_func);

    ret = bsearch(key, array->pdata, array->len, sizeof(gpointer), compare_func);
    return ret ? *ret : NULL;
}

Keep in mind that your compare func will get the key as the first parameter and a pointer to the array member, not the actual pointer as the second. This should be familiar to those who have used GHashTable.

The others are left as an exercise for the reader.

-- Christian Hergert 2013-07-11

Back to Index