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