CODEWITHSUNDEEP
ctreeglib
pwaring
pwaring

Reputation: 3074

Finding a node in a GLib N-ary tree

I'm trying to build a N-ary tree of nodes using GLib 2.58.1, which represents dependencies between different items (parents must be processed before their children, but siblings can be processed in any order). The struct I'm storing within each node (or, more precisely, a pointer to the struct) is:

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

Each time I create and populate a new struct item, I want to search the tree to see whether it already contains a GNode with a pointer to a struct item with the same id, and if so have a pointer to that GNode returned so that I can manipulate it, or NULL if no match is found so I can insert a new GNode. The constraints on the tree and searching are:

  1. Only the equality of the id field is relevant for a match. The other fields can be ignored (which is why I haven't listed them all).
  2. There will only ever be zero or one nodes with any given id, so the search can stop either once it has found a match or when all nodes have been visited, whichever comes first.
  3. The tree will be small and not balanced based on any information within the struct item, therefore any traversal order is acceptable.

I'm struggling to find the right function, or combination of functions, to achieve this goal, especially as the documentation is basically an API reference rather than a tutorial and N-ary trees seem to be less frequently used than structures such as linked lists.

The two functions which appear to be closest to what I want are:

g_node_find: This takes the data to find as gpointer data, which is effectively a pointer to an item of memory. However, I don't want to compare pointers, I want to compare values within a struct that the pointer points to (if that makes sense).

g_node_traverse: This traverses the whole tree and lets me specify a function to compare nodes, but returns void, whereas I want it to return GNode *.

Is there a way to achieve the above using GLib's N-ary tree implementation, or should I be looking at an alternative library? I could roll my own N-ary tree structure as a last resort, but that seems overkill in this situation.

Upvotes: 1

Views: 354

Answers (1)

Tim
Tim

Reputation: 4948

You can use the gpointer data argument of g_node_traverse to return data from your GNodeTraverseFunc function. Just set data to the GNode * that it finds and return TRUE.

Here's a similar example where a gchar * string is returned in 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

Upvotes: 1

Related Questions