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