如何有效地找到最后一个键和值GTree

Question

我需要开发一套功能扩展glib2GTree有：

• 找到第一个元素
• 找到最后
• 找到最近的（地板，小区，最大小于，最小大于）

找到第一个很容易。首先，您只需停止g_tree_foreach()回调。但是如何找到最后一个元素而不需要遍历整棵树？

我以为我可以使用g_tree_search()的回调函数，它会一直返回正值直到找到，但我怎么知道我目前在最后一个元素上？

#include <stdio.h> 
#include <sys/types.h> 
#include <string.h> 

#include <glib.h> 

static 
gint compare_int(gconstpointer p1, gconstpointer p2) { 
    int i1 = GPOINTER_TO_INT(p1); 
    int i2 = GPOINTER_TO_INT(p2); 
    //printf("%d %d\n", i1, i2); 
    return i1 == i2 ? 0 : i1 > i2 ? 1 : -1; 
} 


static 
gboolean traverse(gpointer key, gpointer value, gpointer data) { 
    //int ikey = GPOINTER_TO_INT(key); 
    const char *sval = (const char *)value; 
    printf("%s\n", sval); 
    return FALSE; 
} 

static 
gint find_last(gconstpointer p, gpointer user_data) { 
    return 1; 
} 

static inline const char *NULS(const char *s) { 
    return s ? s : "NULL"; 
} 

int main(int argc, char *argv[]) { 
    GTree *tree = g_tree_new(compare_int); 
    g_tree_insert(tree, GINT_TO_POINTER(10), "ten"); 
    g_tree_insert(tree, GINT_TO_POINTER(-99), "minus ninety-nine"); 
    g_tree_insert(tree, GINT_TO_POINTER(8), "eight"); 
    g_tree_foreach(tree, traverse, NULL); 
    printf("=======\n%s\n", NULS((const char*)g_tree_search(tree, (GCompareFunc)find_last, NULL))); 
    return 0; 
} 

Answer 1

我不想完全实现我自己的树，因为我想从第三方代码收到GTree情况下进行高级搜索。

相反，我认为Glib作者现在很难改变他们的内部结构，我可以直接使用他们的领域。

结果是从gtree.c扩展了内部函数g_tree_find_node()的版本。我添加了两个参数来控制我是否想要第一个，最后一个或最近的节点。最近节点的算法与java的TreeMap不同，因为我们的节点没有指向其父节点的指针。完整的单元测试代码在这里：gtreeex.c。

typedef enum { 
    FIND_EXACT = 0, 
    FIND_FLOOR = 0x2, 
    FIND_CEIL = 0x20, 
    FIND_LOWER = (FIND_FLOOR + 1), 
    FIND_HIGHER = (FIND_CEIL + 1) 
} find_mode; 

static GTreeNode * 
g_tree_find_node_ex (GTree  *tree, 
        gconstpointer key, 
        GCompareDataFunc key_compare, 
        find_mode mode 
       ) 
{ 
    GTreeNode *node; 
    gint cmp; 
    GTreeNode *last_lesser_node = NULL; 
    GTreeNode *last_greater_node = NULL; 

    node = tree->root; 
    if (!node) 
     return NULL; 

    while (1) 
     { 
      cmp = key_compare (key, node->key, tree->key_compare_data); 
      if (cmp == 0) { 
       if (mode == FIND_LOWER) { 
        cmp = -1; 
       } else if (mode == FIND_HIGHER) { 
        cmp = 1; 
       } else { 
        return node; 
       } 
      } 

      if (cmp < 0) 
       { 
        if (!node->left_child) { 
         if ((mode & FIND_FLOOR)) { 
          return last_lesser_node; /* can be null */ 
         } 
         if ((mode & FIND_CEIL)) { 
          return node; 
         } 
         return NULL; 
        } 

        last_greater_node = node; 
        node = node->left; 
       } 
      else 
       { 
        if (!node->right_child) { 
         if ((mode & FIND_CEIL)) { 
          return last_greater_node; /* can be null */ 
         } 
         if ((mode & FIND_FLOOR)) { 
          return node; 
         } 
         return NULL; 
        } 

        last_lesser_node = node; 
        node = node->right; 
       } 
     } 
} 

为了获得更好的性能，可能使用预处理宏，而不是两个新的参数，更换if与#if，包括位头多次。