| 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 | |