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