glib implements many common data structures, so you don’t have to reinvent the wheel every time you want a linked list. This section covers glib’s implementation of linked lists, sorted binary trees, N-ary trees, and hash tables.
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:
[sourcecode language=”cpp”]
GSList* list = NULL;
gchar* element = g_strdup("a string");
list = g_slist_append(list, element);
[/sourcecode]
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:
[sourcecode language=”cpp”]
list = g_slist_remove(list, element);
[/sourcecode]
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:
[sourcecode language=”cpp”]
gchar* my_data = list->data;
[/sourcecode]
To iterate over the list, you might write code like this:
[sourcecode language=”cpp”]
GSList* tmp = list;
while (tmp != NULL)
{
printf("List data: %p\n", tmp->data);
tmp = g_slist_next(tmp);
}
[/sourcecode]
Figure 2-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:
[sourcecode language=”cpp”]
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);
}
else
{
}
}
*list = g_slist_append(*list, data);
*list_end = *list;
*list_end = g_slist_append(*list_end, data)->next;
[/sourcecode]
To use this function, you would store the list and its end somewhere, and pass their address to efficient_append():
[sourcecode language=”cpp”]
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"));
[/sourcecode]
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.
[sourcecode language=”cpp”]
#include <glib.h>
GSList* g_slist_append(GSList* list, gpointer data); GSList* g_slist_prepend(GSList* list, gpointer data);
GSList* g_slist_insert(GSList* list, gpointer data, gint position); GSList* g_slist_remove(GSList* list, gpointer data);
[/sourcecode]
Figure 2-13. Changing linked list contents
For accessing list elements, the functions in Figure 2-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:
[sourcecode language=”cpp”]
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;
}
[/sourcecode]
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.)
[sourcecode language=”cpp”]
#include <glib.h>
GSList* g_slist_find(GSList* list, gpointer data);
GSList* g_slist_nth(GSList* list, guint n);
gpointer g_slist_nth_data(GSList* list, guint n);
GSList* g_slist_last(GSList* list);
gint g_slist_index(GSList* list, gpointer data);
void g_slist_foreach(GSList* list, GFunc func, gpointer user_data);
[/sourcecode]
Figure 2-14. Accessing data in a linked list
There are some handy list-manipulation routines, listed in Figure 2-15. With the ex- ception 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,