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