189857Sobrien/* List implementation of a partition of consecutive integers. 289857Sobrien Copyright (C) 2000, 2001 Free Software Foundation, Inc. 360484Sobrien Contributed by CodeSourcery, LLC. 460484Sobrien 560484Sobrien This file is part of GNU CC. 660484Sobrien 760484Sobrien GNU CC is free software; you can redistribute it and/or modify 860484Sobrien it under the terms of the GNU General Public License as published by 960484Sobrien the Free Software Foundation; either version 2, or (at your option) 1060484Sobrien any later version. 1160484Sobrien 1260484Sobrien GNU CC is distributed in the hope that it will be useful, 1360484Sobrien but WITHOUT ANY WARRANTY; without even the implied warranty of 1460484Sobrien MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1560484Sobrien GNU General Public License for more details. 1660484Sobrien 1760484Sobrien You should have received a copy of the GNU General Public License 1860484Sobrien along with GNU CC; see the file COPYING. If not, write to 19218822Sdim the Free Software Foundation, 51 Franklin Street - Fifth Floor, 20218822Sdim Boston, MA 02110-1301, USA. */ 2160484Sobrien 2260484Sobrien#ifdef HAVE_CONFIG_H 2360484Sobrien#include "config.h" 2460484Sobrien#endif 2560484Sobrien 2660484Sobrien#ifdef HAVE_STDLIB_H 2760484Sobrien#include <stdlib.h> 2860484Sobrien#endif 2960484Sobrien 3077298Sobrien#ifdef HAVE_STRING_H 3177298Sobrien#include <string.h> 3277298Sobrien#endif 3377298Sobrien 3460484Sobrien#include "libiberty.h" 3560484Sobrien#include "partition.h" 3660484Sobrien 37218822Sdimstatic int elem_compare (const void *, const void *); 3877298Sobrien 3960484Sobrien/* Creates a partition of NUM_ELEMENTS elements. Initially each 4060484Sobrien element is in a class by itself. */ 4160484Sobrien 4260484Sobrienpartition 43218822Sdimpartition_new (int num_elements) 4460484Sobrien{ 4560484Sobrien int e; 4660484Sobrien 4760484Sobrien partition part = (partition) 4860484Sobrien xmalloc (sizeof (struct partition_def) + 4960484Sobrien (num_elements - 1) * sizeof (struct partition_elem)); 5060484Sobrien part->num_elements = num_elements; 5160484Sobrien for (e = 0; e < num_elements; ++e) 5260484Sobrien { 5360484Sobrien part->elements[e].class_element = e; 5460484Sobrien part->elements[e].next = &(part->elements[e]); 5560484Sobrien part->elements[e].class_count = 1; 5660484Sobrien } 5760484Sobrien 5860484Sobrien return part; 5960484Sobrien} 6060484Sobrien 6160484Sobrien/* Freeds a partition. */ 6260484Sobrien 6360484Sobrienvoid 64218822Sdimpartition_delete (partition part) 6560484Sobrien{ 6660484Sobrien free (part); 6760484Sobrien} 6860484Sobrien 6960484Sobrien/* Unites the classes containing ELEM1 and ELEM2 into a single class 7060484Sobrien of partition PART. If ELEM1 and ELEM2 are already in the same 7160484Sobrien class, does nothing. Returns the canonical element of the 7260484Sobrien resulting union class. */ 7360484Sobrien 7460484Sobrienint 75218822Sdimpartition_union (partition part, int elem1, int elem2) 7660484Sobrien{ 7760484Sobrien struct partition_elem *elements = part->elements; 7860484Sobrien struct partition_elem *e1; 7960484Sobrien struct partition_elem *e2; 8060484Sobrien struct partition_elem *p; 8160484Sobrien struct partition_elem *old_next; 8260484Sobrien /* The canonical element of the resulting union class. */ 8360484Sobrien int class_element = elements[elem1].class_element; 8460484Sobrien 8560484Sobrien /* If they're already in the same class, do nothing. */ 8660484Sobrien if (class_element == elements[elem2].class_element) 8760484Sobrien return class_element; 8860484Sobrien 8960484Sobrien /* Make sure ELEM1 is in the larger class of the two. If not, swap 9060484Sobrien them. This way we always scan the shorter list. */ 9160484Sobrien if (elements[elem1].class_count < elements[elem2].class_count) 9260484Sobrien { 9360484Sobrien int temp = elem1; 9460484Sobrien elem1 = elem2; 9560484Sobrien elem2 = temp; 9660484Sobrien class_element = elements[elem1].class_element; 9760484Sobrien } 9860484Sobrien 9960484Sobrien e1 = &(elements[elem1]); 10060484Sobrien e2 = &(elements[elem2]); 10160484Sobrien 10260484Sobrien /* Keep a count of the number of elements in the list. */ 10360484Sobrien elements[class_element].class_count 10460484Sobrien += elements[e2->class_element].class_count; 10560484Sobrien 10660484Sobrien /* Update the class fields in elem2's class list. */ 10760484Sobrien e2->class_element = class_element; 10860484Sobrien for (p = e2->next; p != e2; p = p->next) 10960484Sobrien p->class_element = class_element; 11060484Sobrien 11160484Sobrien /* Splice ELEM2's class list into ELEM1's. These are circular 11260484Sobrien lists. */ 11360484Sobrien old_next = e1->next; 11460484Sobrien e1->next = e2->next; 11560484Sobrien e2->next = old_next; 11660484Sobrien 11760484Sobrien return class_element; 11860484Sobrien} 11960484Sobrien 12060484Sobrien/* Compare elements ELEM1 and ELEM2 from array of integers, given a 12160484Sobrien pointer to each. Used to qsort such an array. */ 12260484Sobrien 12360484Sobrienstatic int 124218822Sdimelem_compare (const void *elem1, const void *elem2) 12560484Sobrien{ 12677298Sobrien int e1 = * (const int *) elem1; 12777298Sobrien int e2 = * (const int *) elem2; 12860484Sobrien if (e1 < e2) 12960484Sobrien return -1; 13060484Sobrien else if (e1 > e2) 13160484Sobrien return 1; 13260484Sobrien else 13360484Sobrien return 0; 13460484Sobrien} 13560484Sobrien 13660484Sobrien/* Prints PART to the file pointer FP. The elements of each 13760484Sobrien class are sorted. */ 13860484Sobrien 13960484Sobrienvoid 140218822Sdimpartition_print (partition part, FILE *fp) 14160484Sobrien{ 14260484Sobrien char *done; 14360484Sobrien int num_elements = part->num_elements; 14460484Sobrien struct partition_elem *elements = part->elements; 14560484Sobrien int *class_elements; 14660484Sobrien int e; 14760484Sobrien 14860484Sobrien /* Flag the elements we've already printed. */ 14960484Sobrien done = (char *) xmalloc (num_elements); 15060484Sobrien memset (done, 0, num_elements); 15160484Sobrien 15260484Sobrien /* A buffer used to sort elements in a class. */ 15360484Sobrien class_elements = (int *) xmalloc (num_elements * sizeof (int)); 15460484Sobrien 15560484Sobrien fputc ('[', fp); 15660484Sobrien for (e = 0; e < num_elements; ++e) 15760484Sobrien /* If we haven't printed this element, print its entire class. */ 15860484Sobrien if (! done[e]) 15960484Sobrien { 16060484Sobrien int c = e; 16160484Sobrien int count = elements[elements[e].class_element].class_count; 16260484Sobrien int i; 16360484Sobrien 16460484Sobrien /* Collect the elements in this class. */ 16560484Sobrien for (i = 0; i < count; ++i) { 16660484Sobrien class_elements[i] = c; 16760484Sobrien done[c] = 1; 16860484Sobrien c = elements[c].next - elements; 16960484Sobrien } 17060484Sobrien /* Sort them. */ 17177298Sobrien qsort ((void *) class_elements, count, sizeof (int), elem_compare); 17260484Sobrien /* Print them. */ 17360484Sobrien fputc ('(', fp); 17460484Sobrien for (i = 0; i < count; ++i) 17560484Sobrien fprintf (fp, i == 0 ? "%d" : " %d", class_elements[i]); 17660484Sobrien fputc (')', fp); 17760484Sobrien } 17860484Sobrien fputc (']', fp); 17960484Sobrien 180218822Sdim free (class_elements); 18160484Sobrien free (done); 18260484Sobrien} 18360484Sobrien 184