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