Glib中如何高效遍历树的两个指定键间节点（规避废弃/低效接口）

Great question! Since g_tree_transverse() is deprecated and g_tree_foreach() forces a full tree traversal (which is inefficient for range queries), we can leverage the fact that GTree is implemented as a balanced red-black tree to build a targeted range traversal. The key here is to use the GTreeNode API (introduced in Glib 2.68) — this is the official replacement for the deprecated traversal functions, and it lets us iterate through nodes in order without visiting every element.

Step-by-Step Solution #

1. Verify Glib Version Compatibility #

First, make sure you're using Glib 2.68 or newer. The GTreeNode family of functions was added specifically to replace g_tree_transverse() and enable more flexible traversal patterns.

2. Implement the Range Traversal Function #

We'll use g_tree_lookup_extended() to find the starting point (the first node with a key >= your lower bound), then iterate through subsequent nodes using g_tree_node_next() until we exceed the upper bound. Here's a complete example:

#include <glib.h>

// Helper to check if a key falls within our target range
static gboolean is_key_in_range(gconstpointer key, gconstpointer start_key, gconstpointer end_key, GCompareFunc compare_func) {
    gint cmp_start = compare_func(key, start_key);
    gint cmp_end = compare_func(key, end_key);
    return (cmp_start >= 0 && cmp_end <= 0);
}

// Core function to traverse nodes between start_key and end_key (inclusive)
void traverse_range(GTree *tree, gconstpointer start_key, gconstpointer end_key, GCompareFunc compare_func, GTraverseFunc func, gpointer user_data) {
    g_return_if_fail(tree != NULL);
    g_return_if_fail(start_key != NULL);
    g_return_if_fail(end_key != NULL);
    g_return_if_fail(compare_func != NULL);
    g_return_if_fail(func != NULL);

    GTreeNode *node = NULL;
    gboolean found_exact_match = g_tree_lookup_extended(tree, start_key, NULL, (gpointer *)&node);

    // If no exact match, node points to the first key larger than start_key
    // If all keys are smaller than start_key, node will be NULL — exit early
    if (!found_exact_match && node == NULL) {
        return;
    }

    // Iterate through nodes until we exceed the upper bound
    while (node != NULL) {
        gconstpointer current_key = g_tree_node_key(node);
        gint cmp_to_end = compare_func(current_key, end_key);

        // Stop if we've passed the upper bound
        if (cmp_to_end > 0) {
            break;
        }

        // Process the current node (using your custom callback)
        func(current_key, g_tree_node_value(node), user_data);

        // Move to the next in-order node (successor)
        node = g_tree_node_next(node);
    }
}

// Example callback to print node data
static void print_node(gconstpointer key, gconstpointer value, gpointer user_data) {
    g_print("Key: %d, Value: %s\n", GPOINTER_TO_INT(key), (const gchar *)value);
}

int main() {
    // Create a tree with integer keys
    GTree *tree = g_tree_new(g_int_compare);

    // Populate sample data
    g_tree_insert(tree, GINT_TO_POINTER(10), "Ten");
    g_tree_insert(tree, GINT_TO_POINTER(20), "Twenty");
    g_tree_insert(tree, GINT_TO_POINTER(30), "Thirty");
    g_tree_insert(tree, GINT_TO_POINTER(40), "Forty");
    g_tree_insert(tree, GINT_TO_POINTER(50), "Fifty");

    // Traverse keys between 20 and 40 (inclusive)
    g_print("Traversing range 20-40:\n");
    traverse_range(tree, GINT_TO_POINTER(20), GINT_TO_POINTER(40), g_int_compare, print_node, NULL);

    // Cleanup
    g_tree_destroy(tree);
    return 0;
}

3. How It Works #

• Finding the Start: g_tree_lookup_extended() does double duty here — if it finds an exact match for start_key, it returns that node. If not, it gives us the first node with a key larger than start_key (or NULL if all keys are smaller).
• Iterating Through the Range: We use g_tree_node_next() to move to the next in-order successor (maintaining sorted order). For each node, we check if it's still within the upper bound; if not, we break the loop immediately.
• Efficiency: This approach only visits nodes within your target range, so it's O(k + log n) time where k is the number of nodes in the range — way more efficient than a full tree traversal.

For Older Glib Versions (Pre-2.68) #

If you can't upgrade Glib, you're in a trickier spot since the internal GTree node structure isn't public. The only reliable (though not ideal) workaround is to use g_tree_foreach() with a callback that returns FALSE once you pass the upper bound. While this technically uses g_tree_foreach(), it stops early once the range is exhausted:

static gboolean range_foreach_callback(gconstpointer key, gconstpointer value, gpointer user_data) {
    typedef struct {
        gconstpointer start_key;
        gconstpointer end_key;
        GCompareFunc compare_func;
        GTraverseFunc func;
        gpointer func_data;
    } RangeData;

    RangeData *data = (RangeData *)user_data;
    gint cmp_start = data->compare_func(key, data->start_key);
    gint cmp_end = data->compare_func(key, data->end_key);

    if (cmp_end > 0) {
        // Stop traversal once we exceed the upper bound
        return FALSE;
    }

    if (cmp_start >= 0) {
        // Process nodes within the range
        data->func(key, value, data->func_data);
    }

    // Continue traversal until we hit the upper bound
    return TRUE;
}

void traverse_range_old(GTree *tree, gconstpointer start_key, gconstpointer end_key, GCompareFunc compare_func, GTraverseFunc func, gpointer user_data) {
    RangeData data = {start_key, end_key, compare_func, func, user_data};
    g_tree_foreach(tree, range_foreach_callback, &data);
}

Note: This early termination works because GTree's g_tree_foreach() uses in-order traversal (sorted order), so once we pass the upper bound, all remaining nodes will be larger and can be skipped.

内容的提问来源于stack exchange，提问作者Ricardo Canela