Back to index

cell-binutils  2.17cvs20070401
partition.c
Go to the documentation of this file.
00001 /* List implementation of a partition of consecutive integers.
00002    Copyright (C) 2000, 2001 Free Software Foundation, Inc.
00003    Contributed by CodeSourcery, LLC.
00004 
00005    This file is part of GNU CC.
00006 
00007    GNU CC is free software; you can redistribute it and/or modify
00008    it under the terms of the GNU General Public License as published by
00009    the Free Software Foundation; either version 2, or (at your option)
00010    any later version.
00011 
00012    GNU CC is distributed in the hope that it will be useful,
00013    but WITHOUT ANY WARRANTY; without even the implied warranty of
00014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015    GNU General Public License for more details.
00016 
00017    You should have received a copy of the GNU General Public License
00018    along with GNU CC; see the file COPYING.  If not, write to
00019    the Free Software Foundation, 51 Franklin Street - Fifth Floor,
00020    Boston, MA 02110-1301, USA.  */
00021 
00022 #ifdef HAVE_CONFIG_H
00023 #include "config.h"
00024 #endif
00025 
00026 #ifdef HAVE_STDLIB_H
00027 #include <stdlib.h>
00028 #endif
00029 
00030 #ifdef HAVE_STRING_H
00031 #include <string.h>
00032 #endif
00033 
00034 #include "libiberty.h"
00035 #include "partition.h"
00036 
00037 static int elem_compare (const void *, const void *);
00038 
00039 /* Creates a partition of NUM_ELEMENTS elements.  Initially each
00040    element is in a class by itself.  */
00041 
00042 partition
00043 partition_new (int num_elements)
00044 {
00045   int e;
00046   
00047   partition part = (partition) 
00048     xmalloc (sizeof (struct partition_def) + 
00049             (num_elements - 1) * sizeof (struct partition_elem));
00050   part->num_elements = num_elements;
00051   for (e = 0; e < num_elements; ++e) 
00052     {
00053       part->elements[e].class_element = e;
00054       part->elements[e].next = &(part->elements[e]);
00055       part->elements[e].class_count = 1;
00056     }
00057 
00058   return part;
00059 }
00060 
00061 /* Freeds a partition.  */
00062 
00063 void
00064 partition_delete (partition part)
00065 {
00066   free (part);
00067 }
00068 
00069 /* Unites the classes containing ELEM1 and ELEM2 into a single class
00070    of partition PART.  If ELEM1 and ELEM2 are already in the same
00071    class, does nothing.  Returns the canonical element of the
00072    resulting union class.  */
00073 
00074 int
00075 partition_union (partition part, int elem1, int elem2)
00076 {
00077   struct partition_elem *elements = part->elements;
00078   struct partition_elem *e1;
00079   struct partition_elem *e2;
00080   struct partition_elem *p;
00081   struct partition_elem *old_next;
00082   /* The canonical element of the resulting union class.  */
00083   int class_element = elements[elem1].class_element;
00084 
00085   /* If they're already in the same class, do nothing.  */
00086   if (class_element == elements[elem2].class_element)
00087     return class_element;
00088 
00089   /* Make sure ELEM1 is in the larger class of the two.  If not, swap
00090      them.  This way we always scan the shorter list.  */
00091   if (elements[elem1].class_count < elements[elem2].class_count) 
00092     {
00093       int temp = elem1;
00094       elem1 = elem2;
00095       elem2 = temp;
00096       class_element = elements[elem1].class_element;
00097     }
00098 
00099   e1 = &(elements[elem1]);
00100   e2 = &(elements[elem2]);
00101 
00102   /* Keep a count of the number of elements in the list.  */
00103   elements[class_element].class_count 
00104     += elements[e2->class_element].class_count;
00105 
00106   /* Update the class fields in elem2's class list.  */
00107   e2->class_element = class_element;
00108   for (p = e2->next; p != e2; p = p->next)
00109     p->class_element = class_element;
00110   
00111   /* Splice ELEM2's class list into ELEM1's.  These are circular
00112      lists.  */
00113   old_next = e1->next;
00114   e1->next = e2->next;
00115   e2->next = old_next;
00116 
00117   return class_element;
00118 }
00119 
00120 /* Compare elements ELEM1 and ELEM2 from array of integers, given a
00121    pointer to each.  Used to qsort such an array.  */
00122 
00123 static int 
00124 elem_compare (const void *elem1, const void *elem2)
00125 {
00126   int e1 = * (const int *) elem1;
00127   int e2 = * (const int *) elem2;
00128   if (e1 < e2)
00129     return -1;
00130   else if (e1 > e2)
00131     return 1;
00132   else
00133     return 0;
00134 }
00135 
00136 /* Prints PART to the file pointer FP.  The elements of each
00137    class are sorted.  */
00138 
00139 void
00140 partition_print (partition part, FILE *fp)
00141 {
00142   char *done;
00143   int num_elements = part->num_elements;
00144   struct partition_elem *elements = part->elements;
00145   int *class_elements;
00146   int e;
00147 
00148   /* Flag the elements we've already printed.  */
00149   done = (char *) xmalloc (num_elements);
00150   memset (done, 0, num_elements);
00151 
00152   /* A buffer used to sort elements in a class.  */
00153   class_elements = (int *) xmalloc (num_elements * sizeof (int));
00154 
00155   fputc ('[', fp);
00156   for (e = 0; e < num_elements; ++e)
00157     /* If we haven't printed this element, print its entire class.  */
00158     if (! done[e]) 
00159       {
00160        int c = e;
00161        int count = elements[elements[e].class_element].class_count;
00162        int i;
00163 
00164       /* Collect the elements in this class.  */
00165        for (i = 0; i < count; ++i) {
00166          class_elements[i] = c;
00167          done[c] = 1;
00168          c = elements[c].next - elements;
00169        }
00170        /* Sort them.  */
00171        qsort ((void *) class_elements, count, sizeof (int), elem_compare);
00172        /* Print them.  */
00173        fputc ('(', fp);
00174        for (i = 0; i < count; ++i) 
00175          fprintf (fp, i == 0 ? "%d" : " %d", class_elements[i]);
00176        fputc (')', fp);
00177       }
00178   fputc (']', fp);
00179 
00180   free (class_elements);
00181   free (done);
00182 }
00183