Invalid pointer when deleting GLib.Tree elements in Vala

Question

This code causes the following error

free(): invalid pointer

Online example

using GLib;
using GLib.Random;

// Global variable
Tree<string, Tree<int, string> > mainTree;

public static int main (string[] args) {
    // Initiate random seed
    Random.set_seed ((uint32) get_monotonic_time());
    // mainTree initialization
    mainTree = new Tree<string, Tree<int, string> >.full (mainTreeCompareDataFunction, free, free);
    // Random sized for loop
    for (int i = 0; i < int_range (1000, 10001); i++) {
        // If a condition is met (i is even)
        if (i % 2 == 0) {
            // Create a Tree to nest onto mainTree
            Tree<int, string> treeToNest = new Tree<int, string>.full (treeToNestCompareDataFunction, free, free);
            // Insert random content into treeToNest
            treeToNest.insert (int_range (0, 101), randomString ());
            // Insert the tree onto mainTree
            mainTree.insert (randomString (), treeToNest);
        }
    }

    // Empty the tree
    mainTree.@foreach ((mainTreeKey, mainTreeValue) => {
        mainTree.remove (mainTreeKey); // This line causes a free(): invalid pointer error
        return false;
    });

    return 0;
}

public string randomString () {
    string charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    string stringToReturn = "";
    // Create a random 8 character string
    for (int i = 0; i < 8; i++) {
        stringToReturn += charset[int_range (0, charset.length)].to_string ();
    }
    return stringToReturn;
}

public int treeToNestCompareDataFunction (int a, int b) {
    if (a < b) return -1;
    if (a > b) return 1;
    return 0; 
}

public int mainTreeCompareDataFunction (string a, string b) {
    return strcmp (a, b);
}

I suspect that it is because there is a nested GLib.Tree inside the tree and free() cannot be used on those objects. If I use null instead for the destroy function for the values of mainTree, no crash happens, but a memory leak is created if I were to reuse the mainTree variable.

Is there any way to empty the tree and have the memory freed?

Answer 1

You can write a lambda that will delete the sub tree using an ownership transfer.

    mainTree = new Tree<string, Tree<int, string> >.full (mainTreeCompareDataFunction, free,
        (data) => {
          var tree = (Tree<string, Tree<int, string>>) data;
          // Ownership is transfered to this local var which calls unref when it goes out of scope
          var tree2 = (owned) tree;
        });

Here is the full code:

using GLib;
using GLib.Random;

// Global variable
Tree<string, Tree<int, string> > mainTree;

public static int main (string[] args) {
    // Initiate random seed
    Random.set_seed ((uint32) get_monotonic_time());
    // mainTree initialization
    mainTree = new Tree<string, Tree<int, string> >.full (mainTreeCompareDataFunction, free,
        (data) => {
          var tree = (Tree<string, Tree<int, string>>) data;
          // Ownership is transfered to this local var which calls unref when it goes out of scope
          var tree2 = (owned) tree;
        });
    // Random sized for loop
    for (int i = 0; i < int_range (1000, 10001); i++) {
        // If a condition is met (i is even)
        if (i % 2 == 0) {
            // Create a Tree to nest onto mainTree
            Tree<int, string> treeToNest = new Tree<int, string>.full (treeToNestCompareDataFunction, null, free);
            // Insert random content into treeToNest
            treeToNest.insert (int_range (0, 101), randomString ());
            // Insert the tree onto mainTree
            mainTree.insert (randomString (), treeToNest);
        }
    }

    // Empty the tree
    mainTree.@foreach ((mainTreeKey, mainTreeValue) => {
        mainTree.remove (mainTreeKey);
        return false;
    });

    return 0;
}

public string randomString () {
    string charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    string stringToReturn = "";
    // Create a random 8 character string
    for (int i = 0; i < 8; i++) {
        stringToReturn += charset[int_range (0, charset.length)].to_string ();
    }
    return stringToReturn;
}

public int treeToNestCompareDataFunction (int a, int b) {
    if (a < b) return -1;
    if (a > b) return 1;
    return 0; 
}

public int mainTreeCompareDataFunction (string a, string b) {
    return strcmp (a, b);
}

I would avoid using the GLib.Tree class in Vala, because of the difficulty to get the memory management right. You should consider using a Gee.TreeMap instead.