docs/reference/glib/tmpl/trees-nary.sgml

   1 <!-- ##### SECTION Title ##### -->
   2 N-ary Trees
   3
   4 <!-- ##### SECTION Short_Description ##### -->
   5 trees of data with any number of branches.
   6
   7 <!-- ##### SECTION Long_Description ##### -->
   8 <para>
   9 The #GNode struct and its associated functions provide a N-ary tree data
  10 structure, where nodes in the tree can contain arbitrary data.
  11 </para>
  12 <para>
  13 To create a new tree use g_node_new().
  14 </para>
  15 <para>
  16 To insert a node into a tree use g_node_insert(), g_node_insert_before(),
  17 g_node_append() and g_node_prepend().
  18 </para>
  19 <para>
  20 To create a new node and insert it into a tree use g_node_insert_data(),
  21 g_node_insert_data_before(), g_node_append_data() and g_node_prepend_data().
  22 </para>
  23 <para>
  24 To reverse the children of a node use g_node_reverse_children().
  25 </para>
  26 <para>
  27 To find a node use g_node_get_root(), g_node_find(), g_node_find_child(),
  28 g_node_child_index(), g_node_child_position(),
  29 g_node_first_child(), g_node_last_child(),
  30 g_node_nth_child(), g_node_first_sibling(), g_node_prev_sibling(),
  31 g_node_next_sibling() or g_node_last_sibling().
  32 </para>
  33 <para>
  34 To get information about a node or tree use G_NODE_IS_LEAF(),
  35 G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(), g_node_n_children(),
  36 g_node_is_ancestor() or g_node_max_height().
  37 </para>
  38 <para>
  39 To traverse a tree, calling a function for each node visited in the
  40 traversal, use g_node_traverse() or g_node_children_foreach().
  41 </para>
  42 <para>
  43 To remove a node or subtree from a tree use g_node_unlink() or
  44 g_node_destroy().
  45 </para>
  46
  47 <!-- ##### SECTION See_Also ##### -->
  48 <para>
  49
  50 </para>
  51
  52 <!-- ##### SECTION Stability_Level ##### -->
  53
  54
  55 <!-- ##### STRUCT GNode ##### -->
  56 <para>
  57 The <structname>GNode</structname> struct represents one node in a
  58 <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
  59 The <structfield>data</structfield> field contains the actual data of the node.
  60 The <structfield>next</structfield> and <structfield>prev</structfield>
  61 fields point to the node's siblings (a sibling is another <structname>GNode</structname> with the
  62 same parent).
  63 The <structfield>parent</structfield> field points to the parent of the <structname>GNode</structname>,
  64 or is %NULL if the <structname>GNode</structname> is the root of the tree.
  65 The <structfield>children</structfield> field points to the first child of the
  66 <structname>GNode</structname>. The other children are accessed by using the
  67 <structfield>next</structfield> pointer of each child.
  68 </para>
  69
  70 @data:
  71 @next:
  72 @prev:
  73 @parent:
  74 @children:
  75
  76 <!-- ##### FUNCTION g_node_new ##### -->
  77 <para>
  78 Creates a new #GNode containing the given data.
  79 Used to create the first node in a tree.
  80 </para>
  81
  82 @data: the data of the new node.
  83 @Returns: a new #GNode.
  84
  85
  86 <!-- ##### FUNCTION g_node_copy ##### -->
  87 <para>
  88 Recursively copies a #GNode (but does not deep-copy the data inside the nodes,
  89 see g_node_copy_deep() if you need that).
  90 </para>
  91
  92 @node: a #GNode.
  93 @Returns: a new #GNode containing the same data pointers.
  94
  95
  96 <!-- ##### USER_FUNCTION GCopyFunc ##### -->
  97 <para>
  98 A function of this signature is used to copy the node data when doing a deep-copy
  99 of a tree.
 100 </para>
 101
 102 @src: A pointer to the data which should be copied.
 103 @data: Additional data.
 104 @Returns: A pointer to the copy.
 105 @Since: 2.4
 106
 107
 108 <!-- ##### FUNCTION g_node_copy_deep ##### -->
 109 <para>
 110
 111 </para>
 112
 113 @node:
 114 @copy_func:
 115 @data:
 116 @Returns:
 117
 118
 119 <!-- ##### FUNCTION g_node_insert ##### -->
 120 <para>
 121 Inserts a #GNode beneath the parent at the given position.
 122 </para>
 123
 124 @parent: the #GNode to place @node under.
 125 @position: the position to place @node at, with respect to its siblings.
 126 If position is -1, @node is inserted as the last child of @parent.
 127 @node: the #GNode to insert.
 128 @Returns: the inserted #GNode.
 129
 130
 131 <!-- ##### FUNCTION g_node_insert_before ##### -->
 132 <para>
 133 Inserts a #GNode beneath the parent before the given sibling.
 134 </para>
 135
 136 @parent: the #GNode to place @node under.
 137 @sibling: the sibling #GNode to place @node before. If sibling is %NULL,
 138 the node is inserted as the last child of @parent.
 139 @node: the #GNode to insert.
 140 @Returns: the inserted #GNode.
 141
 142
 143 <!-- ##### FUNCTION g_node_insert_after ##### -->
 144 <para>
 145 Inserts a #GNode beneath the parent after the given sibling.
 146 </para>
 147
 148 @parent: the #GNode to place @node under.
 149 @sibling: the sibling #GNode to place @node after. If sibling is %NULL,
 150 the node is inserted as the first child of @parent.
 151 @node: the #GNode to insert.
 152 @Returns: the inserted #GNode.
 153
 154
 155 <!-- ##### MACRO g_node_append ##### -->
 156 <para>
 157 Inserts a #GNode as the last child of the given parent.
 158 </para>
 159
 160 @parent: the #GNode to place the new #GNode under.
 161 @node: the #GNode to insert.
 162 @Returns: the inserted #GNode.
 163
 164
 165 <!-- ##### FUNCTION g_node_prepend ##### -->
 166 <para>
 167 Inserts a #GNode as the first child of the given parent.
 168 </para>
 169
 170 @parent: the #GNode to place the new #GNode under.
 171 @node: the #GNode to insert.
 172 @Returns: the inserted #GNode.
 173
 174
 175 <!-- ##### MACRO g_node_insert_data ##### -->
 176 <para>
 177 Inserts a new #GNode at the given position.
 178 </para>
 179
 180 @parent: the #GNode to place the new #GNode under.
 181 @position: the position to place the new #GNode at.
 182 If position is -1, the new #GNode is inserted as the last child of @parent.
 183 @data: the data for the new #GNode.
 184 @Returns: the new #GNode.
 185
 186
 187 <!-- ##### MACRO g_node_insert_data_before ##### -->
 188 <para>
 189 Inserts a new #GNode before the given sibling.
 190 </para>
 191
 192 @parent: the #GNode to place the new #GNode under.
 193 @sibling: the sibling #GNode to place the new #GNode before.
 194 @data: the data for the new #GNode.
 195 @Returns: the new #GNode.
 196
 197
 198 <!-- ##### MACRO g_node_append_data ##### -->
 199 <para>
 200 Inserts a new #GNode as the last child of the given parent.
 201 </para>
 202
 203 @parent: the #GNode to place the new #GNode under.
 204 @data: the data for the new #GNode.
 205 @Returns: the new #GNode.
 206
 207
 208 <!-- ##### MACRO g_node_prepend_data ##### -->
 209 <para>
 210 Inserts a new #GNode as the first child of the given parent.
 211 </para>
 212
 213 @parent: the #GNode to place the new #GNode under.
 214 @data: the data for the new #GNode.
 215 @Returns: the new #GNode.
 216
 217
 218 <!-- ##### FUNCTION g_node_reverse_children ##### -->
 219 <para>
 220 Reverses the order of the children of a #GNode.
 221 (It doesn't change the order of the grandchildren.)
 222 </para>
 223
 224 @node: a #GNode.
 225
 226
 227 <!-- ##### FUNCTION g_node_traverse ##### -->
 228 <para>
 229 Traverses a tree starting at the given root #GNode.
 230 It calls the given function for each node visited.
 231 The traversal can be halted at any point by returning %TRUE from @func.
 232 </para>
 233
 234 @root: the root #GNode of the tree to traverse.
 235 @order: the order in which nodes are visited - %G_IN_ORDER, %G_PRE_ORDER,
 236 %G_POST_ORDER, or %G_LEVEL_ORDER.
 237 @flags: which types of children are to be visited, one of %G_TRAVERSE_ALL,
 238 %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES.
 239 @max_depth: the maximum depth of the traversal. Nodes below this
 240 depth will not be visited. If max_depth is -1 all nodes in the tree are
 241 visited. If depth is 1, only the root is visited. If depth is 2, the root
 242 and its children are visited. And so on.
 243 @func: the function to call for each visited #GNode.
 244 @data: user data to pass to the function.
 245
 246
 247 <!-- ##### ENUM GTraverseFlags ##### -->
 248 <para>
 249 Specifies which nodes are visited during several of the tree functions,
 250 including g_node_traverse() and g_node_find().
 251 </para>
 252
 253 @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has been
 254   introduced in 2.6, for older version use %G_TRAVERSE_LEAFS.
 255 @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This name
 256   has been introduced in 2.6, for older version use %G_TRAVERSE_NON_LEAFS.
 257 @G_TRAVERSE_ALL: all nodes should be visited.
 258 @G_TRAVERSE_MASK:
 259 @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES
 260 @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES
 261
 262 <!-- ##### USER_FUNCTION GNodeTraverseFunc ##### -->
 263 <para>
 264 Specifies the type of function passed to g_node_traverse().
 265 The function is called with each of the nodes visited, together with the
 266 user data passed to g_node_traverse().
 267 If the function returns %TRUE, then the traversal is stopped.
 268 </para>
 269
 270 @node: a #GNode.
 271 @data: user data passed to g_node_traverse().
 272 @Returns: %TRUE to stop the traversal.
 273
 274
 275 <!-- ##### FUNCTION g_node_children_foreach ##### -->
 276 <para>
 277 Calls a function for each of the children of a #GNode.
 278 Note that it doesn't descend beneath the child nodes.
 279 </para>
 280
 281 @node: a #GNode.
 282 @flags: which types of children are to be visited, one of %G_TRAVERSE_ALL,
 283 %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES.
 284 @func: the function to call for each visited node.
 285 @data: user data to pass to the function.
 286
 287
 288 <!-- ##### USER_FUNCTION GNodeForeachFunc ##### -->
 289 <para>
 290 Specifies the type of function passed to g_node_children_foreach().
 291 The function is called with each child node, together with the user data
 292 passed to g_node_children_foreach().
 293 </para>
 294
 295 @node: a #GNode.
 296 @data: user data passed to g_node_children_foreach().
 297
 298
 299 <!-- ##### FUNCTION g_node_get_root ##### -->
 300 <para>
 301 Gets the root of a tree.
 302 </para>
 303
 304 @node: a #GNode.
 305 @Returns: the root of the tree.
 306
 307
 308 <!-- ##### FUNCTION g_node_find ##### -->
 309 <para>
 310 Finds a #GNode in a tree.
 311 </para>
 312
 313 @root: the root #GNode of the tree to search.
 314 @order: the order in which nodes are visited - %G_IN_ORDER, %G_PRE_ORDER,
 315 %G_POST_ORDER, or %G_LEVEL_ORDER.
 316 @flags: which types of children are to be searched, one of %G_TRAVERSE_ALL,
 317 %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES.
 318 @data: the data to find.
 319 @Returns: the found #GNode, or %NULL if the data is not found.
 320
 321
 322 <!-- ##### FUNCTION g_node_find_child ##### -->
 323 <para>
 324 Finds the first child of a #GNode with the given data.
 325 </para>
 326
 327 @node: a #GNode.
 328 @flags: which types of children are to be searched, one of %G_TRAVERSE_ALL,
 329 %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES.
 330 @data: the data to find.
 331 @Returns: the found child #GNode, or %NULL if the data is not found.
 332
 333
 334 <!-- ##### FUNCTION g_node_child_index ##### -->
 335 <para>
 336 Gets the position of the first child of a #GNode which contains the given data.
 337 </para>
 338
 339 @node: a #GNode.
 340 @data: the data to find.
 341 @Returns: the index of the child of @node which contains @data, or -1
 342 if the data is not found.
 343
 344
 345 <!-- ##### FUNCTION g_node_child_position ##### -->
 346 <para>
 347 Gets the position of a #GNode with respect to its siblings.
 348 @child must be a child of @node.
 349 The first child is numbered 0, the second 1, and so on.
 350 </para>
 351
 352 @node: a #GNode.
 353 @child: a child of @node.
 354 @Returns: the position of @child with respect to its siblings.
 355
 356
 357 <!-- ##### MACRO g_node_first_child ##### -->
 358 <para>
 359 Gets the first child of a #GNode.
 360 </para>
 361
 362 @node: a #GNode.
 363 @Returns: the last child of @node, or %NULL if @node is %NULL or has no children.
 364
 365
 366 <!-- ##### FUNCTION g_node_last_child ##### -->
 367 <para>
 368 Gets the last child of a #GNode.
 369 </para>
 370
 371 @node: a #GNode (must not be %NULL).
 372 @Returns: the last child of @node, or %NULL if @node has no children.
 373
 374
 375 <!-- ##### FUNCTION g_node_nth_child ##### -->
 376 <para>
 377 Gets a child of a #GNode, using the given index.
 378 The first child is at index 0. If the index is too big, %NULL is returned.
 379 </para>
 380
 381 @node: a #GNode.
 382 @n: the index of the desired child.
 383 @Returns: the child of @node at index @n.
 384
 385
 386 <!-- ##### FUNCTION g_node_first_sibling ##### -->
 387 <para>
 388 Gets the first sibling of a #GNode.
 389 This could possibly be the node itself.
 390 </para>
 391
 392 @node: a #GNode.
 393 @Returns: the first sibling of @node.
 394
 395
 396 <!-- ##### MACRO g_node_next_sibling ##### -->
 397 <para>
 398 Gets the next sibling of a #GNode.
 399 </para>
 400
 401 @node: a #GNode.
 402 @Returns: the next sibling of @node, or %NULL if @node is %NULL.
 403
 404
 405 <!-- ##### MACRO g_node_prev_sibling ##### -->
 406 <para>
 407 Gets the previous sibling of a #GNode.
 408 </para>
 409
 410 @node: a #GNode.
 411 @Returns: the previous sibling of @node, or %NULL if @node is %NULL.
 412
 413
 414 <!-- ##### FUNCTION g_node_last_sibling ##### -->
 415 <para>
 416 Gets the last sibling of a #GNode.
 417 This could possibly be the node itself.
 418 </para>
 419
 420 @node: a #GNode.
 421 @Returns: the last sibling of @node.
 422
 423
 424 <!-- ##### MACRO G_NODE_IS_LEAF ##### -->
 425 <para>
 426 Returns %TRUE if a #GNode is a leaf node.
 427 </para>
 428
 429 @node: a #GNode.
 430 @Returns: %TRUE if the #GNode is a leaf node (i.e. it has no children).
 431
 432
 433 <!-- ##### MACRO G_NODE_IS_ROOT ##### -->
 434 <para>
 435 Returns %TRUE if a #GNode is the root of a tree.
 436 </para>
 437
 438 @node: a #GNode.
 439 @Returns: %TRUE if the #GNode is the root of a tree (i.e. it has no parent
 440 or siblings).
 441
 442
 443 <!-- ##### FUNCTION g_node_depth ##### -->
 444 <para>
 445 Gets the depth of a #GNode.
 446 </para>
 447 <para>
 448 If @node is %NULL the depth is 0.
 449 The root node has a depth of 1.
 450 For the children of the root node the depth is 2. And so on.
 451 </para>
 452
 453 @node: a #GNode.
 454 @Returns: the depth of the #GNode.
 455
 456
 457 <!-- ##### FUNCTION g_node_n_nodes ##### -->
 458 <para>
 459 Gets the number of nodes in a tree.
 460 </para>
 461
 462 @root: a #GNode.
 463 @flags: which types of children are to be counted, one of %G_TRAVERSE_ALL,
 464 %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES.
 465 @Returns: the number of nodes in the tree.
 466
 467
 468 <!-- ##### FUNCTION g_node_n_children ##### -->
 469 <para>
 470 Gets the number of children of a #GNode.
 471 </para>
 472
 473 @node: a #GNode.
 474 @Returns: the number of children of @node.
 475
 476
 477 <!-- ##### FUNCTION g_node_is_ancestor ##### -->
 478 <para>
 479 Returns %TRUE if @node is an ancestor of @descendant.
 480 This is true if node is the parent of @descendant, or if node is the
 481 grandparent of @descendant etc.
 482 </para>
 483
 484 @node: a #GNode.
 485 @descendant: a #GNode.
 486 @Returns: %TRUE if @node is an ancestor of @descendant.
 487
 488
 489 <!-- ##### FUNCTION g_node_max_height ##### -->
 490 <para>
 491 Gets the maximum height of all branches beneath a #GNode.
 492 This is the maximum distance from the #GNode to all leaf nodes.
 493 </para>
 494 <para>
 495 If @root is %NULL, 0 is returned. If @root has no children, 1 is returned.
 496 If @root has children, 2 is returned. And so on.
 497 </para>
 498
 499 @root: a #GNode.
 500 @Returns: the maximum height of the tree beneath @root.
 501
 502
 503 <!-- ##### FUNCTION g_node_unlink ##### -->
 504 <para>
 505 Unlinks a #GNode from a tree, resulting in two separate trees.
 506 </para>
 507
 508 @node: the #GNode to unlink, which becomes the root of a new tree.
 509
 510
 511 <!-- ##### FUNCTION g_node_destroy ##### -->
 512 <para>
 513 Removes the #GNode and its children from the tree, freeing any memory
 514 allocated.
 515 </para>
 516
 517 @root: the root of the tree/subtree to destroy.
 518
 519
 520 <!-- ##### FUNCTION g_node_push_allocator ##### -->
 521 <para>
 522 Sets the allocator to use to allocate #GNode elements.
 523 Use g_node_pop_allocator() to restore the previous allocator.
 524 </para>
 525 <para>
 526 Note that this function is not available if GLib has been compiled
 527 with <option>--disable-mem-pools</option>
 528 </para>
 529
 530 @dummy: the #GAllocator to use when allocating #GNode elements.
 531 @Deprecated: Since 2.10, it does nothing, since #GNode has been
 532 converted to the <link linkend="glib-Memory-Slices">slice allocator</link>
 533
 534
 535 <!-- ##### FUNCTION g_node_pop_allocator ##### -->
 536 <para>
 537 Restores the previous #GAllocator, used when allocating #GNode elements.
 538 </para>
 539 <para>
 540 Note that this function is not available if GLib has been compiled
 541 with <option>--disable-mem-pools</option>
 542 </para>
 543
 544 @Deprecated: Since 2.10, it does nothing, since #GNode has been
 545 converted to the <link linkend="glib-Memory-Slices">slice allocator</link>
 546
 547