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