release/src/router/glib/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_insert (GNode *parent,
 194                gint   position,
 195                GNode *node)
 196 {
 197   g_return_val_if_fail (parent != NULL, node);
 198   g_return_val_if_fail (node != NULL, node);
 199   g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
 200
 201   if (position > 0)
 202     return g_node_insert_before (parent,
 203                                  g_node_nth_child (parent, position),
 204                                  node);
 205   else if (position == 0)
 206     return g_node_prepend (parent, node);
 207   else /* if (position < 0) */
 208     return g_node_append (parent, node);
 209 }
 210
 211 GNode*
 212 g_node_insert_before (GNode *parent,
 213                       GNode *sibling,
 214                       GNode *node)
 215 {
 216   g_return_val_if_fail (parent != NULL, node);
 217   g_return_val_if_fail (node != NULL, node);
 218   g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
 219   if (sibling)
 220     g_return_val_if_fail (sibling->parent == parent, node);
 221
 222   node->parent = parent;
 223
 224   if (sibling)
 225     {
 226       if (sibling->prev)
 227         {
 228           node->prev = sibling->prev;
 229           node->prev->next = node;
 230           node->next = sibling;
 231           sibling->prev = node;
 232         }
 233       else
 234         {
 235           node->parent->children = node;
 236           node->next = sibling;
 237           sibling->prev = node;
 238         }
 239     }
 240   else
 241     {
 242       if (parent->children)
 243         {
 244           sibling = parent->children;
 245           while (sibling->next)
 246             sibling = sibling->next;
 247           node->prev = sibling;
 248           sibling->next = node;
 249         }
 250       else
 251         node->parent->children = node;
 252     }
 253
 254   return node;
 255 }
 256
 257 GNode*
 258 g_node_prepend (GNode *parent,
 259                 GNode *node)
 260 {
 261   g_return_val_if_fail (parent != NULL, node);
 262
 263   return g_node_insert_before (parent, parent->children, node);
 264 }
 265
 266 GNode*
 267 g_node_get_root (GNode *node)
 268 {
 269   g_return_val_if_fail (node != NULL, NULL);
 270
 271   while (node->parent)
 272     node = node->parent;
 273
 274   return node;
 275 }
 276
 277 gboolean
 278 g_node_is_ancestor (GNode *node,
 279                     GNode *descendant)
 280 {
 281   g_return_val_if_fail (node != NULL, FALSE);
 282   g_return_val_if_fail (descendant != NULL, FALSE);
 283
 284   while (descendant)
 285     {
 286       if (descendant->parent == node)
 287         return TRUE;
 288
 289       descendant = descendant->parent;
 290     }
 291
 292   return FALSE;
 293 }
 294
 295 /* returns 1 for root, 2 for first level children,
 296  * 3 for children's children...
 297  */
 298 guint
 299 g_node_depth (GNode *node)
 300 {
 301   register guint depth = 0;
 302
 303   while (node)
 304     {
 305       depth++;
 306       node = node->parent;
 307     }
 308
 309   return depth;
 310 }
 311
 312 void
 313 g_node_reverse_children (GNode *node)
 314 {
 315   GNode *child;
 316   GNode *last;
 317
 318   g_return_if_fail (node != NULL);
 319
 320   child = node->children;
 321   last = NULL;
 322   while (child)
 323     {
 324       last = child;
 325       child = last->next;
 326       last->next = last->prev;
 327       last->prev = child;
 328     }
 329   node->children = last;
 330 }
 331
 332 guint
 333 g_node_max_height (GNode *root)
 334 {
 335   register GNode *child;
 336   register guint max_height = 0;
 337
 338   if (!root)
 339     return 0;
 340
 341   child = root->children;
 342   while (child)
 343     {
 344       register guint tmp_height;
 345
 346       tmp_height = g_node_max_height (child);
 347       if (tmp_height > max_height)
 348         max_height = tmp_height;
 349       child = child->next;
 350     }
 351
 352   return max_height + 1;
 353 }
 354
 355 static gboolean
 356 g_node_traverse_pre_order (GNode            *node,
 357                            GTraverseFlags    flags,
 358                            GNodeTraverseFunc func,
 359                            gpointer          data)
 360 {
 361   if (node->children)
 362     {
 363       GNode *child;
 364
 365       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 366           func (node, data))
 367         return TRUE;
 368
 369       child = node->children;
 370       while (child)
 371         {
 372           register GNode *current;
 373
 374           current = child;
 375           child = current->next;
 376           if (g_node_traverse_pre_order (current, flags, func, data))
 377             return TRUE;
 378         }
 379     }
 380   else if ((flags & G_TRAVERSE_LEAFS) &&
 381            func (node, data))
 382     return TRUE;
 383
 384   return FALSE;
 385 }
 386
 387 static gboolean
 388 g_node_depth_traverse_pre_order (GNode            *node,
 389                                  GTraverseFlags    flags,
 390                                  guint             depth,
 391                                  GNodeTraverseFunc func,
 392                                  gpointer          data)
 393 {
 394   if (node->children)
 395     {
 396       GNode *child;
 397
 398       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 399           func (node, data))
 400         return TRUE;
 401
 402       depth--;
 403       if (!depth)
 404         return FALSE;
 405
 406       child = node->children;
 407       while (child)
 408         {
 409           register GNode *current;
 410
 411           current = child;
 412           child = current->next;
 413           if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
 414             return TRUE;
 415         }
 416     }
 417   else if ((flags & G_TRAVERSE_LEAFS) &&
 418            func (node, data))
 419     return TRUE;
 420
 421   return FALSE;
 422 }
 423
 424 static gboolean
 425 g_node_traverse_post_order (GNode            *node,
 426                             GTraverseFlags    flags,
 427                             GNodeTraverseFunc func,
 428                             gpointer          data)
 429 {
 430   if (node->children)
 431     {
 432       GNode *child;
 433
 434       child = node->children;
 435       while (child)
 436         {
 437           register GNode *current;
 438
 439           current = child;
 440           child = current->next;
 441           if (g_node_traverse_post_order (current, flags, func, data))
 442             return TRUE;
 443         }
 444
 445       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 446           func (node, data))
 447         return TRUE;
 448
 449     }
 450   else if ((flags & G_TRAVERSE_LEAFS) &&
 451            func (node, data))
 452     return TRUE;
 453
 454   return FALSE;
 455 }
 456
 457 static gboolean
 458 g_node_depth_traverse_post_order (GNode            *node,
 459                                   GTraverseFlags    flags,
 460                                   guint             depth,
 461                                   GNodeTraverseFunc func,
 462                                   gpointer          data)
 463 {
 464   if (node->children)
 465     {
 466       depth--;
 467       if (depth)
 468         {
 469           GNode *child;
 470
 471           child = node->children;
 472           while (child)
 473             {
 474               register GNode *current;
 475
 476               current = child;
 477               child = current->next;
 478               if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
 479                 return TRUE;
 480             }
 481         }
 482
 483       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 484           func (node, data))
 485         return TRUE;
 486
 487     }
 488   else if ((flags & G_TRAVERSE_LEAFS) &&
 489            func (node, data))
 490     return TRUE;
 491
 492   return FALSE;
 493 }
 494
 495 static gboolean
 496 g_node_traverse_in_order (GNode            *node,
 497                           GTraverseFlags    flags,
 498                           GNodeTraverseFunc func,
 499                           gpointer          data)
 500 {
 501   if (node->children)
 502     {
 503       GNode *child;
 504       register GNode *current;
 505
 506       child = node->children;
 507       current = child;
 508       child = current->next;
 509
 510       if (g_node_traverse_in_order (current, flags, func, data))
 511         return TRUE;
 512
 513       if ((flags & G_TRAVERSE_NON_LEAFS) &&
 514           func (node, data))
 515         return TRUE;
 516
 517       while (child)
 518         {
 519           current = child;
 520           child = current->next;
 521           if (g_node_traverse_in_order (current, flags, func, data))
 522             return TRUE;
 523         }
 524     }
 525   else if ((flags & G_TRAVERSE_LEAFS) &&
 526            func (node, data))
 527     return TRUE;
 528
 529   return FALSE;
 530 }
 531
 532 static gboolean
 533 g_node_depth_traverse_in_order (GNode            *node,
 534                                 GTraverseFlags    flags,
 535                                 guint             depth,
 536                                 GNodeTraverseFunc func,
 537                                 gpointer          data)
 538 {
 539   if (node->children)
 540     {
 541       depth--;
 542       if (depth)
 543         {
 544           GNode *child;
 545           register GNode *current;
 546
 547           child = node->children;
 548           current = child;
 549           child = current->next;
 550
 551           if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
 552             return TRUE;
 553
 554           if ((flags & G_TRAVERSE_NON_LEAFS) &&
 555               func (node, data))
 556             return TRUE;
 557
 558           while (child)
 559             {
 560               current = child;
 561               child = current->next;
 562               if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
 563                 return TRUE;
 564             }
 565         }
 566       else if ((flags & G_TRAVERSE_NON_LEAFS) &&
 567                func (node, data))
 568         return TRUE;
 569     }
 570   else if ((flags & G_TRAVERSE_LEAFS) &&
 571            func (node, data))
 572     return TRUE;
 573
 574   return FALSE;
 575 }
 576
 577 static gboolean
 578 g_node_traverse_children (GNode             *node,
 579                           GTraverseFlags     flags,
 580                           GNodeTraverseFunc  func,
 581                           gpointer           data)
 582 {
 583   GNode *child;
 584
 585   child = node->children;
 586
 587   while (child)
 588     {
 589       register GNode *current;
 590
 591       current = child;
 592       child = current->next;
 593
 594       if (current->children)
 595         {
 596           if ((flags & G_TRAVERSE_NON_LEAFS) &&
 597               func (current, data))
 598             return TRUE;
 599         }
 600       else if ((flags & G_TRAVERSE_LEAFS) &&
 601                func (current, data))
 602         return TRUE;
 603     }
 604
 605   child = node->children;
 606
 607   while (child)
 608     {
 609       register GNode *current;
 610
 611       current = child;
 612       child = current->next;
 613
 614       if (current->children &&
 615           g_node_traverse_children (current, flags, func, data))
 616         return TRUE;
 617     }
 618
 619   return FALSE;
 620 }
 621
 622 static gboolean
 623 g_node_depth_traverse_children (GNode            *node,
 624                                 GTraverseFlags    flags,
 625                                 guint             depth,
 626                                 GNodeTraverseFunc func,
 627                                 gpointer          data)
 628 {
 629   GNode *child;
 630
 631   child = node->children;
 632
 633   while (child)
 634     {
 635       register GNode *current;
 636
 637       current = child;
 638       child = current->next;
 639
 640       if (current->children)
 641         {
 642           if ((flags & G_TRAVERSE_NON_LEAFS) &&
 643               func (current, data))
 644             return TRUE;
 645         }
 646       else if ((flags & G_TRAVERSE_LEAFS) &&
 647                func (current, data))
 648         return TRUE;
 649     }
 650
 651   depth--;
 652   if (!depth)
 653     return FALSE;
 654
 655   child = node->children;
 656
 657   while (child)
 658     {
 659       register GNode *current;
 660
 661       current = child;
 662       child = current->next;
 663
 664       if (current->children &&
 665           g_node_depth_traverse_children (current, flags, depth, func, data))
 666         return TRUE;
 667     }
 668
 669   return FALSE;
 670 }
 671
 672 void
 673 g_node_traverse (GNode            *root,
 674                  GTraverseType     order,
 675                  GTraverseFlags    flags,
 676                  gint              depth,
 677                  GNodeTraverseFunc func,
 678                  gpointer          data)
 679 {
 680   g_return_if_fail (root != NULL);
 681   g_return_if_fail (func != NULL);
 682   g_return_if_fail (order <= G_LEVEL_ORDER);
 683   g_return_if_fail (flags <= G_TRAVERSE_MASK);
 684   g_return_if_fail (depth == -1 || depth > 0);
 685
 686   switch (order)
 687     {
 688     case G_PRE_ORDER:
 689       if (depth < 0)
 690         g_node_traverse_pre_order (root, flags, func, data);
 691       else
 692         g_node_depth_traverse_pre_order (root, flags, depth, func, data);
 693       break;
 694     case G_POST_ORDER:
 695       if (depth < 0)
 696         g_node_traverse_post_order (root, flags, func, data);
 697       else
 698         g_node_depth_traverse_post_order (root, flags, depth, func, data);
 699       break;
 700     case G_IN_ORDER:
 701       if (depth < 0)
 702         g_node_traverse_in_order (root, flags, func, data);
 703       else
 704         g_node_depth_traverse_in_order (root, flags, depth, func, data);
 705       break;
 706     case G_LEVEL_ORDER:
 707       if (root->children)
 708         {
 709           if (!((flags & G_TRAVERSE_NON_LEAFS) &&
 710                 func (root, data)))
 711             {
 712               if (depth < 0)
 713                 g_node_traverse_children (root, flags, func, data);
 714               else
 715                 {
 716                   depth--;
 717                   if (depth)
 718                     g_node_depth_traverse_children (root, flags, depth, func, data);
 719                 }
 720             }
 721         }
 722       else if (flags & G_TRAVERSE_LEAFS)
 723         func (root, data);
 724       break;
 725     }
 726 }
 727
 728 static gboolean
 729 g_node_find_func (GNode   *node,
 730                   gpointer data)
 731 {
 732   register gpointer *d = data;
 733
 734   if (*d != node->data)
 735     return FALSE;
 736
 737   *(++d) = node;
 738
 739   return TRUE;
 740 }
 741
 742 GNode*
 743 g_node_find (GNode             *root,
 744              GTraverseType      order,
 745              GTraverseFlags     flags,
 746              gpointer           data)
 747 {
 748   gpointer d[2];
 749
 750   g_return_val_if_fail (root != NULL, NULL);
 751   g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
 752   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
 753
 754   d[0] = data;
 755   d[1] = NULL;
 756
 757   g_node_traverse (root, order, flags, -1, g_node_find_func, d);
 758
 759   return d[1];
 760 }
 761
 762 static void
 763 g_node_count_func (GNode         *node,
 764                    GTraverseFlags flags,
 765                    guint         *n)
 766 {
 767   if (node->children)
 768     {
 769       GNode *child;
 770
 771       if (flags & G_TRAVERSE_NON_LEAFS)
 772         (*n)++;
 773
 774       child = node->children;
 775       while (child)
 776         {
 777           g_node_count_func (child, flags, n);
 778           child = child->next;
 779         }
 780     }
 781   else if (flags & G_TRAVERSE_LEAFS)
 782     (*n)++;
 783 }
 784
 785 guint
 786 g_node_n_nodes (GNode         *root,
 787                 GTraverseFlags flags)
 788 {
 789   guint n = 0;
 790
 791   g_return_val_if_fail (root != NULL, 0);
 792   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
 793
 794   g_node_count_func (root, flags, &n);
 795
 796   return n;
 797 }
 798
 799 GNode*
 800 g_node_last_child (GNode *node)
 801 {
 802   g_return_val_if_fail (node != NULL, NULL);
 803
 804   node = node->children;
 805   if (node)
 806     while (node->next)
 807       node = node->next;
 808
 809   return node;
 810 }
 811
 812 GNode*
 813 g_node_nth_child (GNode *node,
 814                   guint  n)
 815 {
 816   g_return_val_if_fail (node != NULL, NULL);
 817
 818   node = node->children;
 819   if (node)
 820     while ((n-- > 0) && node)
 821       node = node->next;
 822
 823   return node;
 824 }
 825
 826 guint
 827 g_node_n_children (GNode *node)
 828 {
 829   guint n = 0;
 830
 831   g_return_val_if_fail (node != NULL, 0);
 832
 833   node = node->children;
 834   while (node)
 835     {
 836       n++;
 837       node = node->next;
 838     }
 839
 840   return n;
 841 }
 842
 843 GNode*
 844 g_node_find_child (GNode         *node,
 845                    GTraverseFlags flags,
 846                    gpointer       data)
 847 {
 848   g_return_val_if_fail (node != NULL, NULL);
 849   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
 850
 851   node = node->children;
 852   while (node)
 853     {
 854       if (node->data == data)
 855         {
 856           if (G_NODE_IS_LEAF (node))
 857             {
 858               if (flags & G_TRAVERSE_LEAFS)
 859                 return node;
 860             }
 861           else
 862             {
 863               if (flags & G_TRAVERSE_NON_LEAFS)
 864                 return node;
 865             }
 866         }
 867       node = node->next;
 868     }
 869
 870   return NULL;
 871 }
 872
 873 gint
 874 g_node_child_position (GNode *node,
 875                        GNode *child)
 876 {
 877   register guint n = 0;
 878
 879   g_return_val_if_fail (node != NULL, -1);
 880   g_return_val_if_fail (child != NULL, -1);
 881   g_return_val_if_fail (child->parent == node, -1);
 882
 883   node = node->children;
 884   while (node)
 885     {
 886       if (node == child)
 887         return n;
 888       n++;
 889       node = node->next;
 890     }
 891
 892   return -1;
 893 }
 894
 895 gint
 896 g_node_child_index (GNode   *node,
 897                     gpointer data)
 898 {
 899   register guint n = 0;
 900
 901   g_return_val_if_fail (node != NULL, -1);
 902
 903   node = node->children;
 904   while (node)
 905     {
 906       if (node->data == data)
 907         return n;
 908       n++;
 909       node = node->next;
 910     }
 911
 912   return -1;
 913 }
 914
 915 GNode*
 916 g_node_first_sibling (GNode *node)
 917 {
 918   g_return_val_if_fail (node != NULL, NULL);
 919
 920   while (node->prev)
 921     node = node->prev;
 922
 923   return node;
 924 }
 925
 926 GNode*
 927 g_node_last_sibling (GNode *node)
 928 {
 929   g_return_val_if_fail (node != NULL, NULL);
 930
 931   while (node->next)
 932     node = node->next;
 933
 934   return node;
 935 }
 936
 937 void
 938 g_node_children_foreach (GNode           *node,
 939                          GTraverseFlags   flags,
 940                          GNodeForeachFunc func,
 941                          gpointer         data)
 942 {
 943   g_return_if_fail (node != NULL);
 944   g_return_if_fail (flags <= G_TRAVERSE_MASK);
 945   g_return_if_fail (func != NULL);
 946
 947   node = node->children;
 948   while (node)
 949     {
 950       register GNode *current;
 951
 952       current = node;
 953       node = current->next;
 954       if (G_NODE_IS_LEAF (current))
 955         {
 956           if (flags & G_TRAVERSE_LEAFS)
 957             func (current, data);
 958         }
 959       else
 960         {
 961           if (flags & G_TRAVERSE_NON_LEAFS)
 962             func (current, data);
 963         }
 964     }
 965 }