Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. /* List implementation of a partition of consecutive integers.
  2.    Copyright (C) 2000, 2001 Free Software Foundation, Inc.
  3.    Contributed by CodeSourcery, LLC.
  4.  
  5.    This file is part of GNU CC.
  6.  
  7.    GNU CC is free software; you can redistribute it and/or modify
  8.    it under the terms of the GNU General Public License as published by
  9.    the Free Software Foundation; either version 2, or (at your option)
  10.    any later version.
  11.  
  12.    GNU CC 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
  15.    GNU General Public License for more details.
  16.  
  17.    You should have received a copy of the GNU General Public License
  18.    along with GNU CC; see the file COPYING.  If not, write to
  19.    the Free Software Foundation, 51 Franklin Street - Fifth Floor,
  20.    Boston, MA 02110-1301, USA.  */
  21.  
  22. #ifdef HAVE_CONFIG_H
  23. #include "config.h"
  24. #endif
  25.  
  26. #ifdef HAVE_STDLIB_H
  27. #include <stdlib.h>
  28. #endif
  29.  
  30. #ifdef HAVE_STRING_H
  31. #include <string.h>
  32. #endif
  33.  
  34. #include "libiberty.h"
  35. #include "partition.h"
  36.  
  37. static int elem_compare (const void *, const void *);
  38.  
  39. /* Creates a partition of NUM_ELEMENTS elements.  Initially each
  40.    element is in a class by itself.  */
  41.  
  42. partition
  43. partition_new (int num_elements)
  44. {
  45.   int e;
  46.  
  47.   partition part = (partition)
  48.     xmalloc (sizeof (struct partition_def) +
  49.              (num_elements - 1) * sizeof (struct partition_elem));
  50.   part->num_elements = num_elements;
  51.   for (e = 0; e < num_elements; ++e)
  52.     {
  53.       part->elements[e].class_element = e;
  54.       part->elements[e].next = &(part->elements[e]);
  55.       part->elements[e].class_count = 1;
  56.     }
  57.  
  58.   return part;
  59. }
  60.  
  61. /* Freeds a partition.  */
  62.  
  63. void
  64. partition_delete (partition part)
  65. {
  66.   free (part);
  67. }
  68.  
  69. /* Unites the classes containing ELEM1 and ELEM2 into a single class
  70.    of partition PART.  If ELEM1 and ELEM2 are already in the same
  71.    class, does nothing.  Returns the canonical element of the
  72.    resulting union class.  */
  73.  
  74. int
  75. partition_union (partition part, int elem1, int elem2)
  76. {
  77.   struct partition_elem *elements = part->elements;
  78.   struct partition_elem *e1;
  79.   struct partition_elem *e2;
  80.   struct partition_elem *p;
  81.   struct partition_elem *old_next;
  82.   /* The canonical element of the resulting union class.  */
  83.   int class_element = elements[elem1].class_element;
  84.  
  85.   /* If they're already in the same class, do nothing.  */
  86.   if (class_element == elements[elem2].class_element)
  87.     return class_element;
  88.  
  89.   /* Make sure ELEM1 is in the larger class of the two.  If not, swap
  90.      them.  This way we always scan the shorter list.  */
  91.   if (elements[elem1].class_count < elements[elem2].class_count)
  92.     {
  93.       int temp = elem1;
  94.       elem1 = elem2;
  95.       elem2 = temp;
  96.       class_element = elements[elem1].class_element;
  97.     }
  98.  
  99.   e1 = &(elements[elem1]);
  100.   e2 = &(elements[elem2]);
  101.  
  102.   /* Keep a count of the number of elements in the list.  */
  103.   elements[class_element].class_count
  104.     += elements[e2->class_element].class_count;
  105.  
  106.   /* Update the class fields in elem2's class list.  */
  107.   e2->class_element = class_element;
  108.   for (p = e2->next; p != e2; p = p->next)
  109.     p->class_element = class_element;
  110.  
  111.   /* Splice ELEM2's class list into ELEM1's.  These are circular
  112.      lists.  */
  113.   old_next = e1->next;
  114.   e1->next = e2->next;
  115.   e2->next = old_next;
  116.  
  117.   return class_element;
  118. }
  119.  
  120. /* Compare elements ELEM1 and ELEM2 from array of integers, given a
  121.    pointer to each.  Used to qsort such an array.  */
  122.  
  123. static int
  124. elem_compare (const void *elem1, const void *elem2)
  125. {
  126.   int e1 = * (const int *) elem1;
  127.   int e2 = * (const int *) elem2;
  128.   if (e1 < e2)
  129.     return -1;
  130.   else if (e1 > e2)
  131.     return 1;
  132.   else
  133.     return 0;
  134. }
  135.  
  136. /* Prints PART to the file pointer FP.  The elements of each
  137.    class are sorted.  */
  138.  
  139. void
  140. partition_print (partition part, FILE *fp)
  141. {
  142.   char *done;
  143.   int num_elements = part->num_elements;
  144.   struct partition_elem *elements = part->elements;
  145.   int *class_elements;
  146.   int e;
  147.  
  148.   /* Flag the elements we've already printed.  */
  149.   done = (char *) xmalloc (num_elements);
  150.   memset (done, 0, num_elements);
  151.  
  152.   /* A buffer used to sort elements in a class.  */
  153.   class_elements = (int *) xmalloc (num_elements * sizeof (int));
  154.  
  155.   fputc ('[', fp);
  156.   for (e = 0; e < num_elements; ++e)
  157.     /* If we haven't printed this element, print its entire class.  */
  158.     if (! done[e])
  159.       {
  160.         int c = e;
  161.         int count = elements[elements[e].class_element].class_count;
  162.         int i;
  163.  
  164.       /* Collect the elements in this class.  */
  165.         for (i = 0; i < count; ++i) {
  166.           class_elements[i] = c;
  167.           done[c] = 1;
  168.           c = elements[c].next - elements;
  169.         }
  170.         /* Sort them.  */
  171.         qsort ((void *) class_elements, count, sizeof (int), elem_compare);
  172.         /* Print them.  */
  173.         fputc ('(', fp);
  174.         for (i = 0; i < count; ++i)
  175.           fprintf (fp, i == 0 ? "%d" : " %d", class_elements[i]);
  176.         fputc (')', fp);
  177.       }
  178.   fputc (']', fp);
  179.  
  180.   free (class_elements);
  181.   free (done);
  182. }
  183.  
  184.