1 /* List implementation of a partition of consecutive integers.
2    Copyright (C) 2000-2018 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