Data Structures

Lists

glib provides generic single and doubly linked lists, GSList and GList, respectively. These are implemented as lists of gpointer; you can use them to hold integers with the GINT_TO_POINTER and GPOINTER_TO_INT macros. GSList and GList have identical API's, except that there is a g_list_previous() function and no g_slist_previous(). This section will discuss GSList but everything also applies to the doubly linked list.

In the glib implementation, the empty list is simply a NULL pointer. It's always safe to pass NULL to list functions since it's a valid list of length 0. Code to create a list and add one element might look like this:

GSList* list = NULL;
gchar* element = g_strdup("a string");
list = g_slist_append(list, element);

glib lists have a noticeable Lisp influence; the empty list is a special "nil" value for that reason. g_slist_prepend() works much like cons---it's a constant-time operation that adds a new cell to the front of the list.

Notice that you must replace the list passed to list-modifying functions with their return value, in case the head of the list changes. glib will handle memory issues, deallocating and allocating list links as needed.

For example, the following code would remove the above-added element and empty the list:

list = g_slist_remove(list, element);

list is now NULL. You still have to free element yourself, of course. To clear an entire list, use g_slist_free(), which removes all the links in one fell swoop. g_slist_free() has no return value because it would always be NULL, and you can simply assign that value to your list if you like. Obviously, g_slist_free() frees only the list cells; it has no way of knowing what to do with the list contents.

To access a list element, you refer to the GSList struct directly:

gchar* my_data = list->data;

To iterate over the list, you might write code like this:

GSList* tmp = list;
while (tmp != NULL)
  {
    printf("List data: %p\n", tmp->data);
    tmp = g_slist_next(tmp);
  }

Figure 13 shows the basic functions for changing GSList contents. For all of these, you must assign the return value to your list pointer in case the head of the list changes. Note that glib does not store a pointer to the tail of the list, so prepending is a constant-time operation, while append, insert, and remove are proportional to the list's size.

In particular, this means that constructing a list using g_slist_append() is a terrible idea; use g_slist_prepend() and then call g_slist_reverse() if you need items in a particular order. If you anticipate frequently appending to a list, you can also keep a pointer to the last element. The following code can be used to perform efficient appends:

void
efficient_append(GSList** list, GSList** list_end, gpointer data)
{
  g_return_if_fail(list != NULL);
  g_return_if_fail(list_end != NULL);

  if (*list == NULL)
    {
      g_assert(*list_end == NULL);
      
      *list = g_slist_append(*list, data);
      *list_end = *list;     
    }
  else 
    {
      *list_end = g_slist_append(*list_end, data)->next;
    }
} 

To use this function, you would store the list and its end somewhere, and pass their address to efficient_append():

  GSList* list = NULL;
  GSList* list_end = NULL;

  efficient_append(&list, &list_end, g_strdup("Foo"));
  efficient_append(&list, &list_end, g_strdup("Bar"));
  efficient_append(&list, &list_end, g_strdup("Baz"));

Of course you have to be careful not to use any list functions that might change the end of the list without updating list_end.

#include <glib.h>

For accessing list elements, the functions in Figure 14 are provided. None of these change the list's structure. g_slist_foreach() applies a GFunc to each element of the list. A GFunc is defined as follows:

typedef void (*GFunc)(gpointer data, gpointer user_data);

Used in g_slist_foreach(), your GFunc will be called on each list->data in list, passing the user_data you provided to g_slist_foreach(). g_slist_foreach() is comparable to Scheme's "map" function.

For example, you might have a list of strings, and you might want to be able to create a parallel list with some transformation applied to the strings. Here is some code, using the efficient_append() function from an earlier example:

typedef struct _AppendContext AppendContext;
struct _AppendContext {
  GSList* list;
  GSList* list_end;
  const gchar* append;
};

static void 
append_foreach(gpointer data, gpointer user_data)
{
  AppendContext* ac = (AppendContext*) user_data;
  gchar* oldstring = (gchar*) data;

  efficient_append(&ac->list, &ac->list_end, 
                   g_strconcat(oldstring, ac->append, NULL));
}

GSList*
copy_with_append(GSList* list_of_strings, const gchar* append)
{
  AppendContext ac;

  ac.list = NULL;
  ac.list_end = NULL;
  ac.append = append;

  g_slist_foreach(list_of_strings, append_foreach, &ac);

  return ac.list;
}

glib and GTK+ use the "function pointer and user data" idiom heavily. If you have functional programming experience, this is much like using lambda expressions to create a closure. (A closure combines a function with an environment---a set of name-value bindings. In this case the "environment" is the user data you pass to append_foreach(), and the "closure" is the combination of the function pointer and the user data.)

#include <glib.h>

There are some handy list-manipulation routines, listed in Figure 15. With the exception of g_slist_copy(), all of these affect the lists in-place. Which means you must assign the return value and forget about the passed-in pointer, just as you do when adding or removing list elements. g_slist_copy() returns a newly-allocated list, so you can continue to use both lists and must free both lists eventually.

#include <glib.h>

Finally, there are some provisions for sorted lists, shown in Figure 16. To use these, you must write a GCompareFunc, which is just like the comparison function in the standard C qsort(). Using glib types, this becomes:

typedef gint (*GCompareFunc) (gconstpointer a, gconstpointer b);

If a < b, the function should return a negative value; if a > b a positive value; if a == b it should return 0.

Once you have a comparison function, you can insert an element into an already-sorted list, or sort an entire list. Lists are sorted in ascending order. You can even recycle your GCompareFunc to find list elements, using g_slist_find_custom(). (A word of caution: GCompareFunc is used inconsistently in glib; sometimes it glib expects an equality predicate instead of a qsort()-style function. However, the usage is consistent within the list API.)

Be careful with sorted lists; misusing them can rapidly become very inefficient. For example, g_slist_insert_sorted() is an O(n) operation, but if you use it in a loop to insert multiple elements the loop runs in exponential time. It's better to simply prepend all your elements, then call g_slist_sort().

#include <glib.h>