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