gnode.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * GNode: N-way tree implementation.
   5  * Copyright (C) 1998 Tim Janik
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public
  18  * License along with this library; if not, write to the
  19  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20  * Boston, MA 02111-1307, USA.
  21  */
  22
  23 /*
  24  * Modified by the GLib Team and others 1997-1999.  See the AUTHORS
  25  * file for a list of people on the GLib Team.  See the ChangeLog
  26  * files for a list of changes.  These files are distributed with
  27  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  28  */
  29
  30 /*
  31  * MT safe
  32  */
  33
  34 #include "glib.h"
  35
  36 /* node allocation
  37  */
  38 struct _GAllocator /* from gmem.c */
  39 {
  40   gchar         *name;
  41   guint16        n_preallocs;
  42   guint          is_unused : 1;
  43   guint          type : 4;
  44   GAllocator    *last;
  45   GMemChunk     *mem_chunk;
  46   GNode         *free_nodes; /* implementation specific */
  47 };
  48
  49 G_LOCK_DEFINE_STATIC (current_allocator);
  50 static GAllocator *current_allocator = NULL;
  51
  52 /* HOLDS: current_allocator_lock */
  53 static void
  54 g_node_validate_allocator (GAllocator *allocator)
  55 {
  56   g_return_if_fail (allocator != NULL);
  57   g_return_if_fail (allocator->is_unused == TRUE);
  58
  59   if (allocator->type != G_ALLOCATOR_NODE)
  60     {
  61       allocator->type = G_ALLOCATOR_NODE;
  62       if (allocator->mem_chunk)
  63         {
  64           g_mem_chunk_destroy (allocator->mem_chunk);
  65           allocator->mem_chunk = NULL;
  66         }
  67     }
  68
  69   if (!allocator->mem_chunk)
  70     {
  71       allocator->mem_chunk = g_mem_chunk_new (allocator->name,
  72                                               sizeof (GNode),
  73                                               sizeof (GNode) * allocator->n_preallocs,
  74                                               G_ALLOC_ONLY);
  75       allocator->free_nodes = NULL;
  76     }
  77
  78   allocator->is_unused = FALSE;
  79 }
  80
  81 void
  82 g_node_push_allocator (GAllocator *allocator)
  83 {
  84   G_LOCK (current_allocator);
  85   g_node_validate_allocator ( allocator );
  86   allocator->last = current_allocator;
  87   current_allocator = allocator;
  88   G_UNLOCK (current_allocator);
  89 }
  90
  91 void
  92 g_node_pop_allocator (void)
  93 {
  94   G_LOCK (current_allocator);
  95   if (current_allocator)
  96     {
  97       GAllocator *allocator;
  98
  99       allocator = current_allocator;
 100       current_allocator = allocator->last;
 101       allocator->last = NULL;
 102       allocator->is_unused = TRUE;
 103     }
 104   G_UNLOCK (current_allocator);
 105 }
 106
 107
 108 /* --- functions --- */
 109 GNode*
 110 g_node_new (gpointer data)
 111 {
 112   GNode *node;
 113
 114   G_LOCK (current_allocator);
 115   if (!current_allocator)
 116     {
 117        GAllocator *allocator = g_allocator_new ("GLib default GNode allocator",
 118                                                 128);
 119        g_node_validate_allocator (allocator);
 120        allocator->last = NULL;
 121        current_allocator = allocator;
 122     }
 123   if (!current_allocator->free_nodes)
 124     node = g_chunk_new (GNode, current_allocator->mem_chunk);
 125   else
 126     {
 127       node = current_allocator->free_nodes;
 128       current_allocator->free_nodes = node->next;
 129     }
 130   G_UNLOCK (current_allocator);
 131
 132   node->data = data;
 133   node->next = NULL;
 134   node->prev = NULL;
 135   node->parent = NULL;
 136   node->children = NULL;
 137
 138   return node;
 139 }
 140
 141 static void
 142 g_nodes_free (GNode *node)
 143 {
 144   GNode *parent;
 145
 146   parent = node;
 147   while (1)
 148     {
 149       if (parent->children)
 150         g_nodes_free (parent->children);
 151       if (parent->next)
 152         parent = parent->next;
 153       else
 154         break;
 155     }
 156
 157   G_LOCK (current_allocator);
 158   parent->next = current_allocator->free_nodes;
 159   current_allocator->free_nodes = node;
 160   G_UNLOCK (current_allocator);
 161 }
 162
 163 void
 164 g_node_destroy (GNode *root)
 165 {
 166   g_return_if_fail (root != NULL);
 167
 168   if (!G_NODE_IS_ROOT (root))
 169     g_node_unlink (root);
 170
 171   g_nodes_free (root);
 172 }
 173
 174 void
 175 g_node_unlink (GNode *node)
 176 {
 177   g_return_if_fail (node != NULL);
 178
 179   if (node->prev)
 180     node->prev->next = node->next;
 181   else if (node->parent)
 182     node->parent->children = node->next;
 183   node->parent = NULL;
 184   if (node->next)
 185     {
 186       node->next->prev = node->prev;
 187       node->next = NULL;
 188     }
 189   node->prev = NULL;
 190 }
 191
 192 GNode*
 193 g_node_copy (GNode *node)
 194 {
 195   GNode *new_node = NULL;
 196
 197   if (node)
 198     {
 199       GNode *child;
 200
 201       new_node = g_node_new (node->data);
 202
 203       for (child = g_node_last_child (node); child; child = child->prev)
 204         g_node_prepend (new_node, g_node_copy (child));
 205     }
 206
 207   return new_node;
 208 }
 209
 210 GNode*
 211 g_node_insert (GNode *parent,
 212                gint   position,
 213                GNode *node)
 214 {
 215   g_return_val_if_fail (parent != NULL, node);
 216   g_return_val_if_fail (node != NULL, node);
 217   g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
 218
 219   if (position > 0)
 220     return g_node_insert_before (parent,
 221                                  g_node_nth_child (parent, position),
 222                                  node);
 223   else if (position == 0)
 224     return g_node_prepend (parent, node);
 225   else /* if (position < 0) */
 226     return g_node_append (parent, node);
 227 }
 228
 229 GNode*
 230 g_node_insert_before (GNode *parent,
 231                       GNode *sibling,
 232                       GNode *node)
 233 {
 234   g_return_val_if_fail (parent != NULL, node);
 235   g_return_val_if_fail (node != NULL, node);
 236   g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
 237   if (sibling)
 238     g_return_val_if_fail (sibling->parent == parent, node);
 239
 240   node->parent = parent;
 241
 242   if (sibling)
 243     {
 244       if (sibling->prev)
 245         {
 246           node->prev = sibling->prev;
 247           node->prev->next = node;
 248           node->next = sibling;
 249           sibling->prev = node;
 250         }
 251       else
 252         {
 253           node->parent->children = node;
 254           node->next = sibling;
 255           sibling->prev = node;
 256         }
 257     }
 258   else
 259     {
 260       if (parent->children)
 261         {
 262           sibling = parent->children;
 263           while (sibling->next)
 264             sibling = sibling->next;
 265           node->prev = sibling;
 266           sibling->next = node;
 267         }
 268       else
 269         node->parent->children = node;
 270     }
 271
 272   return node;
 273 }
 274
 275 GNode*
 276 g_node_prepend (GNode *parent,
 277                 GNode *node)
 278 {
 279   g_return_val_if_fail (parent != NULL, node);
 280
 281   return g_node_insert_before (parent, parent->children, node);
 282 }
 283
 284 GNode*
 285 g_node_get_root (GNode *node)
 286 {
 287   g_return_val_if_fail (node != NULL, NULL);
 288
 289   while (node->parent)
 290     node = node->parent;
 291
 292   return node;
 293 }
 294
 295 gboolean
 296 g_node_is_ancestor (GNode *node,
 297                     GNode *descendant)
 298 {
 299   g_return_val_if_fail (node != NULL, FALSE);
 300   g_return_val_if_fail (descendant != NULL, FALSE);
 301
 302   while (descendant)
 303     {
 304       if (descendant->parent == node)
 305         return TRUE;
 306
 307       descendant = descendant->parent;
 308     }
 309
 310   return FALSE;
 311 }
 312
 313 /* returns 1 for root, 2 for first level children,
 314  * 3 for children's children...
 315  */
 316 guint
 317 g_node_depth (GNode *node)
 318 {
 319   register guint depth = 0;
 320
 321   while (node)
 322     {
 323       depth++;
 324       node = node->parent;
 325     }
 326
 327   return depth;
 328 }
 329
 330 void
 331 g_node_reverse_children (GNode *node)
 332 {
 333   GNode *child;
 334   GNode *last;
 335
 336   g_return_if_fail (node != NULL);
 337
 338   child = node->children;
 339   last = NULL;
 340   while (child)
 341     {
 342       last = child;
 343       child = last->next;
 344       last->next = last->prev;
 345       last->prev = child;
 346     }
 347   node->children = last;
 348 }
 349
 350 guint
 351 g_node_max_height (GNode *root)
 352 {
 353   register GNode *child;
 354   register guint max_height = 0;
 355
 356   if (!root)
 357     return 0;
 358
 359   child = root->children;
 360   while (child)
 361     {
 362       register guint tmp_height;
 363
 364       tmp_height = g_node_max_height (child);
 365       if (tmp_height > max_height)
 366         max_height = tmp_height;
 367       child = child->next;
 368     }
 369
 370   return max_height + 1;
 371 }
 372
 373 static gboolean
 374 g_node_traverse_pre_order (GNode            *node,
 375                            GTraverseFlags    flags,
 376                            GNodeTraverseFunc func,
 377                            gpointer          data)
 378 {
 379   if (node->children)
 380     {
 381       GNode *child;
 382
 383       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 384           func (node, data))
 385         return TRUE;
 386
 387       child = node->children;
 388       while (child)
 389         {
 390           register GNode *current;
 391
 392           current = child;
 393           child = current->next;
 394           if (g_node_traverse_pre_order (current, flags, func, data))
 395             return TRUE;
 396         }
 397     }
 398   else if ((flags & G_TRAVERSE_LEAFS) &&
 399            func (node, data))
 400     return TRUE;
 401
 402   return FALSE;
 403 }
 404
 405 static gboolean
 406 g_node_depth_traverse_pre_order (GNode            *node,
 407                                  GTraverseFlags    flags,
 408                                  guint             depth,
 409                                  GNodeTraverseFunc func,
 410                                  gpointer          data)
 411 {
 412   if (node->children)
 413     {
 414       GNode *child;
 415
 416       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 417           func (node, data))
 418         return TRUE;
 419
 420       depth--;
 421       if (!depth)
 422         return FALSE;
 423
 424       child = node->children;
 425       while (child)
 426         {
 427           register GNode *current;
 428
 429           current = child;
 430           child = current->next;
 431           if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
 432             return TRUE;
 433         }
 434     }
 435   else if ((flags & G_TRAVERSE_LEAFS) &&
 436            func (node, data))
 437     return TRUE;
 438
 439   return FALSE;
 440 }
 441
 442 static gboolean
 443 g_node_traverse_post_order (GNode            *node,
 444                             GTraverseFlags    flags,
 445                             GNodeTraverseFunc func,
 446                             gpointer          data)
 447 {
 448   if (node->children)
 449     {
 450       GNode *child;
 451
 452       child = node->children;
 453       while (child)
 454         {
 455           register GNode *current;
 456
 457           current = child;
 458           child = current->next;
 459           if (g_node_traverse_post_order (current, flags, func, data))
 460             return TRUE;
 461         }
 462
 463       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 464           func (node, data))
 465         return TRUE;
 466
 467     }
 468   else if ((flags & G_TRAVERSE_LEAFS) &&
 469            func (node, data))
 470     return TRUE;
 471
 472   return FALSE;
 473 }
 474
 475 static gboolean
 476 g_node_depth_traverse_post_order (GNode            *node,
 477                                   GTraverseFlags    flags,
 478                                   guint             depth,
 479                                   GNodeTraverseFunc func,
 480                                   gpointer          data)
 481 {
 482   if (node->children)
 483     {
 484       depth--;
 485       if (depth)
 486         {
 487           GNode *child;
 488
 489           child = node->children;
 490           while (child)
 491             {
 492               register GNode *current;
 493
 494               current = child;
 495               child = current->next;
 496               if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
 497                 return TRUE;
 498             }
 499         }
 500
 501       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 502           func (node, data))
 503         return TRUE;
 504
 505     }
 506   else if ((flags & G_TRAVERSE_LEAFS) &&
 507            func (node, data))
 508     return TRUE;
 509
 510   return FALSE;
 511 }
 512
 513 static gboolean
 514 g_node_traverse_in_order (GNode            *node,
 515                           GTraverseFlags    flags,
 516                           GNodeTraverseFunc func,
 517                           gpointer          data)
 518 {
 519   if (node->children)
 520     {
 521       GNode *child;
 522       register GNode *current;
 523
 524       child = node->children;
 525       current = child;
 526       child = current->next;
 527
 528       if (g_node_traverse_in_order (current, flags, func, data))
 529         return TRUE;
 530
 531       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 532           func (node, data))
 533         return TRUE;
 534
 535       while (child)
 536         {
 537           current = child;
 538           child = current->next;
 539           if (g_node_traverse_in_order (current, flags, func, data))
 540             return TRUE;
 541         }
 542     }
 543   else if ((flags & G_TRAVERSE_LEAFS) &&
 544            func (node, data))
 545     return TRUE;
 546
 547   return FALSE;
 548 }
 549
 550 static gboolean
 551 g_node_depth_traverse_in_order (GNode            *node,
 552                                 GTraverseFlags    flags,
 553                                 guint             depth,
 554                                 GNodeTraverseFunc func,
 555                                 gpointer          data)
 556 {
 557   if (node->children)
 558     {
 559       depth--;
 560       if (depth)
 561         {
 562           GNode *child;
 563           register GNode *current;
 564
 565           child = node->children;
 566           current = child;
 567           child = current->next;
 568
 569           if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
 570             return TRUE;
 571
 572           if ((flags & G_TRAVERSE_NON_LEAFS) &&
 573               func (node, data))
 574             return TRUE;
 575
 576           while (child)
 577             {
 578               current = child;
 579               child = current->next;
 580               if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
 581                 return TRUE;
 582             }
 583         }
 584       else if ((flags & G_TRAVERSE_NON_LEAFS) &&
 585                func (node, data))
 586         return TRUE;
 587     }
 588   else if ((flags & G_TRAVERSE_LEAFS) &&
 589            func (node, data))
 590     return TRUE;
 591
 592   return FALSE;
 593 }
 594
 595 static gboolean
 596 g_node_traverse_children (GNode             *node,
 597                           GTraverseFlags     flags,
 598                           GNodeTraverseFunc  func,
 599                           gpointer           data)
 600 {
 601   GNode *child;
 602
 603   child = node->children;
 604
 605   while (child)
 606     {
 607       register GNode *current;
 608
 609       current = child;
 610       child = current->next;
 611
 612       if (current->children)
 613         {
 614           if ((flags & G_TRAVERSE_NON_LEAFS) &&
 615               func (current, data))
 616             return TRUE;
 617         }
 618       else if ((flags & G_TRAVERSE_LEAFS) &&
 619                func (current, data))
 620         return TRUE;
 621     }
 622
 623   child = node->children;
 624
 625   while (child)
 626     {
 627       register GNode *current;
 628
 629       current = child;
 630       child = current->next;
 631
 632       if (current->children &&
 633           g_node_traverse_children (current, flags, func, data))
 634         return TRUE;
 635     }
 636
 637   return FALSE;
 638 }
 639
 640 static gboolean
 641 g_node_depth_traverse_children (GNode            *node,
 642                                 GTraverseFlags    flags,
 643                                 guint             depth,
 644                                 GNodeTraverseFunc func,
 645                                 gpointer          data)
 646 {
 647   GNode *child;
 648
 649   child = node->children;
 650
 651   while (child)
 652     {
 653       register GNode *current;
 654
 655       current = child;
 656       child = current->next;
 657
 658       if (current->children)
 659         {
 660           if ((flags & G_TRAVERSE_NON_LEAFS) &&
 661               func (current, data))
 662             return TRUE;
 663         }
 664       else if ((flags & G_TRAVERSE_LEAFS) &&
 665                func (current, data))
 666         return TRUE;
 667     }
 668
 669   depth--;
 670   if (!depth)
 671     return FALSE;
 672
 673   child = node->children;
 674
 675   while (child)
 676     {
 677       register GNode *current;
 678
 679       current = child;
 680       child = current->next;
 681
 682       if (current->children &&
 683           g_node_depth_traverse_children (current, flags, depth, func, data))
 684         return TRUE;
 685     }
 686
 687   return FALSE;
 688 }
 689
 690 void
 691 g_node_traverse (GNode            *root,
 692                  GTraverseType     order,
 693                  GTraverseFlags    flags,
 694                  gint              depth,
 695                  GNodeTraverseFunc func,
 696                  gpointer          data)
 697 {
 698   g_return_if_fail (root != NULL);
 699   g_return_if_fail (func != NULL);
 700   g_return_if_fail (order <= G_LEVEL_ORDER);
 701   g_return_if_fail (flags <= G_TRAVERSE_MASK);
 702   g_return_if_fail (depth == -1 || depth > 0);
 703
 704   switch (order)
 705     {
 706     case G_PRE_ORDER:
 707       if (depth < 0)
 708         g_node_traverse_pre_order (root, flags, func, data);
 709       else
 710         g_node_depth_traverse_pre_order (root, flags, depth, func, data);
 711       break;
 712     case G_POST_ORDER:
 713       if (depth < 0)
 714         g_node_traverse_post_order (root, flags, func, data);
 715       else
 716         g_node_depth_traverse_post_order (root, flags, depth, func, data);
 717       break;
 718     case G_IN_ORDER:
 719       if (depth < 0)
 720         g_node_traverse_in_order (root, flags, func, data);
 721       else
 722         g_node_depth_traverse_in_order (root, flags, depth, func, data);
 723       break;
 724     case G_LEVEL_ORDER:
 725       if (root->children)
 726         {
 727           if (!((flags & G_TRAVERSE_NON_LEAFS) &&
 728                 func (root, data)))
 729             {
 730               if (depth < 0)
 731                 g_node_traverse_children (root, flags, func, data);
 732               else
 733                 {
 734                   depth--;
 735                   if (depth)
 736                     g_node_depth_traverse_children (root, flags, depth, func, data);
 737                 }
 738             }
 739         }
 740       else if (flags & G_TRAVERSE_LEAFS)
 741         func (root, data);
 742       break;
 743     }
 744 }
 745
 746 static gboolean
 747 g_node_find_func (GNode   *node,
 748                   gpointer data)
 749 {
 750   register gpointer *d = data;
 751
 752   if (*d != node->data)
 753     return FALSE;
 754
 755   *(++d) = node;
 756
 757   return TRUE;
 758 }
 759
 760 GNode*
 761 g_node_find (GNode             *root,
 762              GTraverseType      order,
 763              GTraverseFlags     flags,
 764              gpointer           data)
 765 {
 766   gpointer d[2];
 767
 768   g_return_val_if_fail (root != NULL, NULL);
 769   g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
 770   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
 771
 772   d[0] = data;
 773   d[1] = NULL;
 774
 775   g_node_traverse (root, order, flags, -1, g_node_find_func, d);
 776
 777   return d[1];
 778 }
 779
 780 static void
 781 g_node_count_func (GNode         *node,
 782                    GTraverseFlags flags,
 783                    guint         *n)
 784 {
 785   if (node->children)
 786     {
 787       GNode *child;
 788
 789       if (flags & G_TRAVERSE_NON_LEAFS)
 790         (*n)++;
 791
 792       child = node->children;
 793       while (child)
 794         {
 795           g_node_count_func (child, flags, n);
 796           child = child->next;
 797         }
 798     }
 799   else if (flags & G_TRAVERSE_LEAFS)
 800     (*n)++;
 801 }
 802
 803 guint
 804 g_node_n_nodes (GNode         *root,
 805                 GTraverseFlags flags)
 806 {
 807   guint n = 0;
 808
 809   g_return_val_if_fail (root != NULL, 0);
 810   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
 811
 812   g_node_count_func (root, flags, &n);
 813
 814   return n;
 815 }
 816
 817 GNode*
 818 g_node_last_child (GNode *node)
 819 {
 820   g_return_val_if_fail (node != NULL, NULL);
 821
 822   node = node->children;
 823   if (node)
 824     while (node->next)
 825       node = node->next;
 826
 827   return node;
 828 }
 829
 830 GNode*
 831 g_node_nth_child (GNode *node,
 832                   guint  n)
 833 {
 834   g_return_val_if_fail (node != NULL, NULL);
 835
 836   node = node->children;
 837   if (node)
 838     while ((n-- > 0) && node)
 839       node = node->next;
 840
 841   return node;
 842 }
 843
 844 guint
 845 g_node_n_children (GNode *node)
 846 {
 847   guint n = 0;
 848
 849   g_return_val_if_fail (node != NULL, 0);
 850
 851   node = node->children;
 852   while (node)
 853     {
 854       n++;
 855       node = node->next;
 856     }
 857
 858   return n;
 859 }
 860
 861 GNode*
 862 g_node_find_child (GNode         *node,
 863                    GTraverseFlags flags,
 864                    gpointer       data)
 865 {
 866   g_return_val_if_fail (node != NULL, NULL);
 867   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
 868
 869   node = node->children;
 870   while (node)
 871     {
 872       if (node->data == data)
 873         {
 874           if (G_NODE_IS_LEAF (node))
 875             {
 876               if (flags & G_TRAVERSE_LEAFS)
 877                 return node;
 878             }
 879           else
 880             {
 881               if (flags & G_TRAVERSE_NON_LEAFS)
 882                 return node;
 883             }
 884         }
 885       node = node->next;
 886     }
 887
 888   return NULL;
 889 }
 890
 891 gint
 892 g_node_child_position (GNode *node,
 893                        GNode *child)
 894 {
 895   register guint n = 0;
 896
 897   g_return_val_if_fail (node != NULL, -1);
 898   g_return_val_if_fail (child != NULL, -1);
 899   g_return_val_if_fail (child->parent == node, -1);
 900
 901   node = node->children;
 902   while (node)
 903     {
 904       if (node == child)
 905         return n;
 906       n++;
 907       node = node->next;
 908     }
 909
 910   return -1;
 911 }
 912
 913 gint
 914 g_node_child_index (GNode   *node,
 915                     gpointer data)
 916 {
 917   register guint n = 0;
 918
 919   g_return_val_if_fail (node != NULL, -1);
 920
 921   node = node->children;
 922   while (node)
 923     {
 924       if (node->data == data)
 925         return n;
 926       n++;
 927       node = node->next;
 928     }
 929
 930   return -1;
 931 }
 932
 933 GNode*
 934 g_node_first_sibling (GNode *node)
 935 {
 936   g_return_val_if_fail (node != NULL, NULL);
 937
 938   if (node->parent)
 939     return node->parent->children;
 940
 941   while (node->prev)
 942     node = node->prev;
 943
 944   return node;
 945 }
 946
 947 GNode*
 948 g_node_last_sibling (GNode *node)
 949 {
 950   g_return_val_if_fail (node != NULL, NULL);
 951
 952   while (node->next)
 953     node = node->next;
 954
 955   return node;
 956 }
 957
 958 void
 959 g_node_children_foreach (GNode           *node,
 960                          GTraverseFlags   flags,
 961                          GNodeForeachFunc func,
 962                          gpointer         data)
 963 {
 964   g_return_if_fail (node != NULL);
 965   g_return_if_fail (flags <= G_TRAVERSE_MASK);
 966   g_return_if_fail (func != NULL);
 967
 968   node = node->children;
 969   while (node)
 970     {
 971       register GNode *current;
 972
 973       current = node;
 974       node = current->next;
 975       if (G_NODE_IS_LEAF (current))
 976         {
 977           if (flags & G_TRAVERSE_LEAFS)
 978             func (current, data);
 979         }
 980       else
 981         {
 982           if (flags & G_TRAVERSE_NON_LEAFS)
 983             func (current, data);
 984         }
 985     }
 986 }