在 GLib N-ary 树中查找节点

Question

我正在尝试使用 GLib 2.58.1 构建一个 N-ary 节点树，它表示不同项目之间的依赖关系（parents 必须在它们的 children 之前处理，但是兄弟姐妹可以按任何顺序处理）。我在每个节点中存储的结构（或者更准确地说，是指向该结构的指针）是：

struct item
{
  int id;
  // Some other fields
};

每次我创建并填充一个新的 struct item 时，我都想搜索树以查看它是否已经包含一个 GNode 以及一个指向 struct item 的指针id，如果有一个指向 GNode returned 的指针，以便我可以操作它，或者 NULL 如果没有找到匹配项，那么我可以插入一个新的 GNode。树和搜索的约束是：

只有 id 字段的相等性与匹配相关。其他字段可以忽略（这就是我没有全部列出的原因）。
对于任何给定的 id，永远只会有零个或一个节点，因此搜索可以在找到匹配项或访问所有节点后停止，以先到者为准。
根据 struct item 中的任何信息，树将很小并且不平衡，因此任何遍历顺序都是可以接受的。

我正在努力寻找合适的功能或功能组合来实现这一目标，尤其是因为文档基本上是 API 参考而不是教程，而且 N-ary 树似乎与链表等结构相比使用频率较低。

看起来最接近我想要的两个函数是：

g_node_find：这将要查找的数据作为gpointer data，这实际上是指向内存项的指针。但是，我不想比较指针，我想比较指针指向的结构中的值（如果有意义的话）。

g_node_traverse：这会遍历整棵树，让我指定一个函数来比较节点，但是 returns void，而我希望它 return GNode *.

有没有办法使用 GLib 的 N-ary 树实现实现上述目标，或者我应该寻找替代库？我可以推出自己的 N-ary 树结构作为最后的手段，但在这种情况下这似乎有点过分了。

Answer 1

您可以将 g_node_traverse 的 gpointer data 参数用于 return 来自 GNodeTraverseFunc 函数的数据。只需将 data 设置为它找到的 GNode * 和 return TRUE.

这是一个类似的示例，其中 gchar * 字符串在 data 中被 return 编辑：

static gboolean
node_build_string (GNode    *node,
           gpointer  data)
{
  gchar **p = data;
  gchar *string;
  gchar c[2] = "_";

  c[0] = ((gchar) ((gintptr) (node->data)));

  string = g_strconcat (*p ? *p : "", c, NULL);
  g_free (*p);
  *p = string;

  return FALSE;
}

static void
gnode_test (void)
{
  gchar *tstring;
  ...
  tstring = NULL;
  g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_ALL, -1, node_build_string, &tstring);
  g_assert_cmpstr (tstring, ==, "ABCDEFGHIJK");

https://sources.debian.org/src/glib2.0/2.58.1-2/tests/testglib.c/?hl=321#L321

在 GLib N-ary 树中查找节点

Finding a node in a GLib N-ary tree

c

tree

glib