How to empty a GLib Tree?

Question

In order to empty a GLib Tree, one must first iterate through the tree and fill a list of all found keys. Then one can use the g_tree_remove function to empty the tree. The problem is I am not sure how to fill a list from a traversal function. This is what I tried

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

//Prototypes
gint treeCompareFunction (const gchar* a, const gchar* b, gpointer self);
gboolean traverseTree(gpointer key, gpointer value, gpointer data);

int main()
{
    GTree* tree = g_tree_new_full ((GCompareDataFunc) treeCompareFunction, NULL, NULL, NULL);
    // Insert data into the tree
    g_tree_insert (tree, "key 1", "val 1");
    g_tree_insert (tree, "key 2", "val 2");
    g_tree_insert (tree, "key 3", "val 3");

    GSList* list = NULL;
    // Try to get all the keys of the tree in a list
    g_tree_foreach (tree, (GTraverseFunc)traverseTree, list);
    printf ("List size after tree traversal: %"  G_GUINT32_FORMAT "\n", g_slist_length(list));
    //TODO empty the tree
    return 0;
}

gint treeCompareFunction (const gchar* a, const gchar* b, gpointer self) {
    return g_strcmp0(a, b);
}

gboolean traverseTree(gpointer key, gpointer value, gpointer data) {
 data = g_slist_append(data, key);
 printf ("List size in traversal function: %"  G_GUINT32_FORMAT "\n", g_slist_length(data));
 return FALSE;
}

The output is

List size in traversal function: 1
List size in traversal function: 1
List size in traversal function: 1
List size after tree traversal: 0

How would I go to get all the keys in a list and then empty the tree?

Answer 1

You need to pass a pointer to your GSList*, not the GSList* itself, otherwise the traversal function is modifying a local pointer to the head of the list, not the pointer to the head of the list in main().

GSList *list = NULL;
g_tree_foreach (tree, (GTraverseFunc)traverseTree, &list);
…

gboolean traverseTree(gpointer key, gpointer value, gpointer data) {
 GSList *out_list = data;
 *out_list = g_slist_append(*out_list, key);
 printf ("List size in traversal function: %"  G_GUINT32_FORMAT "\n", g_slist_length(*out_list));
 return FALSE;
}

Separately, note that iteratively appending to a linked list using g_slist_append() will give you O(N^2) performance, and that g_slist_length() takes O(N) time. It would be easier and more efficient overall to use a pointer array:

GPtrArray *items_to_remove = g_ptr_array_sized_new (g_tree_nnodes (tree));
g_tree_foreach (tree, (GTraverseFunc)traverseTree, items_to_remove);
…

gboolean traverseTree(gpointer key, gpointer value, gpointer data) {
 GPtrArray *items_to_remove = data;
 g_ptr_array_add(items_to_remove, key);
 printf ("List size in traversal function: %u\n", items_to_remove->len);
 return FALSE;
}