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