如何有效地找到最後一個鍵和值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，包括位頭多次。