c - 在 GLib N 叉树中查找节点

Question

我正在尝试使用 GLib 2.58.1 构建一个 N 元节点树，它表示不同项目之间的依赖关系( parent 必须在他们的 child 之前处理，但 sibling 可以按任何顺序处理)。我在每个节点中存储的结构(或者更准确地说，是指向该结构的指针)是:

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

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

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

我正在努力寻找合适的功能或功能组合来实现这一目标，尤其是因为文档基本上是 API 引用而不是教程，而且 N 元树似乎不如此类结构使用频繁作为链表。

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

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

g_node_traverse:这会遍历整个树并让我指定一个函数来比较节点，但返回 void，而我希望它返回 GNode *.

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

Answer 1

您可以使用 g_node_traverse 的 gpointer data 参数从您的 GNodeTraverseFunc 函数返回数据。只需将 data 设置为它找到的 GNode * 并返回 TRUE。

这是一个类似的例子，其中 gchar * 字符串在 data 中返回:

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