如何有效地找到最后一个键和值GTree
我需要开发一套功能扩展glib2
GTree
有:如何有效地找到最后一个键和值GTree
- 找到第一个元素
- 找到最后
- 找到最近的(地板,小区,最大小于,最小大于)
找到第一个很容易。首先,您只需停止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;
}
我不想完全实现我自己的树,因为我想从第三方代码收到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
,包括位头多次。
好奇你为什么用'printf'而不是'g_print'和'sprintf'而不是'g_sprintf'(来自'
@ DavidC.Rankin因为我不知道GLib – basin
没问题,glib提供了你所需要的一切。一般来说,只有包含'glib.h'头文件和任何其他的'glib/... h''才可以包含任何可能包含的特殊功能。他们建议不要混合使用'stdio'和'glib'打印功能。 –
'g_tree_nnodes()'应该为您提供您可以用作find_first的方法的节点数量。虽然没有那么优化,但GTree的目标不是这样。 –
更好的替代glib2? – basin
编写您自己的满足您需求的树实现。 –