Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
5191 | serge | 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 |
||
28 | #endif |
||
29 | |||
30 | #ifdef HAVE_STRING_H |
||
31 | #include |
||
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 |