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