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