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