Mercurial > hg > CbC > CbC_gcc
comparison libiberty/partition.c @ 0:a06113de4d67
first commit
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 17 Jul 2009 14:47:48 +0900 |
parents | |
children | 04ced10e8804 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a06113de4d67 |
---|---|
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 <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 |