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