]>
Commit | Line | Data |
---|---|---|
d9d4fb43 AS |
1 | /* List implentation of a partition of consecutive integers. |
2 | Copyright (C) 2000 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, 59 Temple Place - Suite 330, | |
20 | Boston, MA 02111-1307, 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 | ||
d11ec6f0 ZW |
30 | #ifdef HAVE_STRING_H |
31 | #include <string.h> | |
32 | #endif | |
33 | ||
d9d4fb43 AS |
34 | #include "libiberty.h" |
35 | #include "partition.h" | |
36 | ||
37 | /* Creates a partition of NUM_ELEMENTS elements. Initially each | |
38 | element is in a class by itself. */ | |
39 | ||
40 | partition | |
41 | partition_new (num_elements) | |
42 | int num_elements; | |
43 | { | |
44 | int e; | |
45 | ||
46 | partition part = (partition) | |
47 | xmalloc (sizeof (struct partition_def) + | |
48 | (num_elements - 1) * sizeof (struct partition_elem)); | |
49 | part->num_elements = num_elements; | |
50 | for (e = 0; e < num_elements; ++e) | |
51 | { | |
52 | part->elements[e].class_element = e; | |
53 | part->elements[e].next = &(part->elements[e]); | |
54 | part->elements[e].class_count = 1; | |
55 | } | |
56 | ||
57 | return part; | |
58 | } | |
59 | ||
60 | /* Freeds a partition. */ | |
61 | ||
62 | void | |
63 | partition_delete (part) | |
64 | 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 (part, elem1, elem2) | |
76 | partition part; | |
77 | int elem1; | |
78 | int elem2; | |
79 | { | |
80 | struct partition_elem *elements = part->elements; | |
81 | struct partition_elem *e1; | |
82 | struct partition_elem *e2; | |
83 | struct partition_elem *p; | |
84 | struct partition_elem *old_next; | |
85 | /* The canonical element of the resulting union class. */ | |
86 | int class_element = elements[elem1].class_element; | |
87 | ||
88 | /* If they're already in the same class, do nothing. */ | |
89 | if (class_element == elements[elem2].class_element) | |
90 | return class_element; | |
91 | ||
92 | /* Make sure ELEM1 is in the larger class of the two. If not, swap | |
93 | them. This way we always scan the shorter list. */ | |
94 | if (elements[elem1].class_count < elements[elem2].class_count) | |
95 | { | |
96 | int temp = elem1; | |
97 | elem1 = elem2; | |
98 | elem2 = temp; | |
99 | class_element = elements[elem1].class_element; | |
100 | } | |
101 | ||
102 | e1 = &(elements[elem1]); | |
103 | e2 = &(elements[elem2]); | |
104 | ||
105 | /* Keep a count of the number of elements in the list. */ | |
106 | elements[class_element].class_count | |
107 | += elements[e2->class_element].class_count; | |
108 | ||
109 | /* Update the class fields in elem2's class list. */ | |
110 | e2->class_element = class_element; | |
111 | for (p = e2->next; p != e2; p = p->next) | |
112 | p->class_element = class_element; | |
113 | ||
114 | /* Splice ELEM2's class list into ELEM1's. These are circular | |
115 | lists. */ | |
116 | old_next = e1->next; | |
117 | e1->next = e2->next; | |
118 | e2->next = old_next; | |
119 | ||
120 | return class_element; | |
121 | } | |
122 | ||
123 | /* Compare elements ELEM1 and ELEM2 from array of integers, given a | |
124 | pointer to each. Used to qsort such an array. */ | |
125 | ||
126 | static int | |
127 | elem_compare (elem1, elem2) | |
128 | const void *elem1; | |
129 | const void *elem2; | |
130 | { | |
131 | int e1 = * (int *) elem1; | |
132 | int e2 = * (int *) elem2; | |
133 | if (e1 < e2) | |
134 | return -1; | |
135 | else if (e1 > e2) | |
136 | return 1; | |
137 | else | |
138 | return 0; | |
139 | } | |
140 | ||
141 | /* Prints PART to the file pointer FP. The elements of each | |
142 | class are sorted. */ | |
143 | ||
144 | void | |
145 | partition_print (part, fp) | |
146 | partition part; | |
147 | FILE *fp; | |
148 | { | |
149 | char *done; | |
150 | int num_elements = part->num_elements; | |
151 | struct partition_elem *elements = part->elements; | |
152 | int *class_elements; | |
153 | int e; | |
154 | ||
155 | /* Flag the elements we've already printed. */ | |
156 | done = (char *) xmalloc (num_elements); | |
157 | memset (done, 0, num_elements); | |
158 | ||
159 | /* A buffer used to sort elements in a class. */ | |
160 | class_elements = (int *) xmalloc (num_elements * sizeof (int)); | |
161 | ||
162 | fputc ('[', fp); | |
163 | for (e = 0; e < num_elements; ++e) | |
164 | /* If we haven't printed this element, print its entire class. */ | |
165 | if (! done[e]) | |
166 | { | |
167 | int c = e; | |
168 | int count = elements[elements[e].class_element].class_count; | |
169 | int i; | |
170 | ||
171 | /* Collect the elements in this class. */ | |
172 | for (i = 0; i < count; ++i) { | |
173 | class_elements[i] = c; | |
174 | done[c] = 1; | |
175 | c = elements[c].next - elements; | |
176 | } | |
177 | /* Sort them. */ | |
178 | qsort ((void *) class_elements, count, sizeof (int), &elem_compare); | |
179 | /* Print them. */ | |
180 | fputc ('(', fp); | |
181 | for (i = 0; i < count; ++i) | |
182 | fprintf (fp, i == 0 ? "%d" : " %d", class_elements[i]); | |
183 | fputc (')', fp); | |
184 | } | |
185 | fputc (']', fp); | |
186 | ||
187 | free (done); | |
188 | } | |
189 |