178828Sobrien/* List implementation of a partition of consecutive integers. 2104834Sobrien Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. 360484Sobrien Contributed by CodeSourcery, LLC. 460484Sobrien 589857Sobrien This file is part of GCC. 660484Sobrien 789857Sobrien GCC 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 1289857Sobrien GCC 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 1889857Sobrien along with GCC; 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/* This package implements a partition of consecutive integers. The 2360484Sobrien elements are partitioned into classes. Each class is represented 2460484Sobrien by one of its elements, the canonical element, which is chosen 2560484Sobrien arbitrarily from elements in the class. The principal operations 2660484Sobrien on a partition are FIND, which takes an element, determines its 2760484Sobrien class, and returns the canonical element for that class, and UNION, 2860484Sobrien which unites the two classes that contain two given elements into a 2960484Sobrien single class. 3060484Sobrien 3160484Sobrien The list implementation used here provides constant-time finds. By 3260484Sobrien storing the size of each class with the class's canonical element, 3360484Sobrien it is able to perform unions over all the classes in the partition 3460484Sobrien in O (N log N) time. */ 3560484Sobrien 3660484Sobrien#ifndef _PARTITION_H 3760484Sobrien#define _PARTITION_H 3860484Sobrien 3960484Sobrien#ifdef __cplusplus 4060484Sobrienextern "C" { 4160484Sobrien#endif /* __cplusplus */ 4260484Sobrien 43104834Sobrien#include "ansidecl.h" 4460484Sobrien#include <stdio.h> 4560484Sobrien 4660484Sobrienstruct partition_elem 4760484Sobrien{ 4860484Sobrien /* The canonical element that represents the class containing this 4960484Sobrien element. */ 5060484Sobrien int class_element; 5160484Sobrien /* The next element in this class. Elements in each class form a 5260484Sobrien circular list. */ 5360484Sobrien struct partition_elem* next; 5460484Sobrien /* The number of elements in this class. Valid only if this is the 5560484Sobrien canonical element for its class. */ 5660484Sobrien unsigned class_count; 5760484Sobrien}; 5860484Sobrien 5960484Sobrientypedef struct partition_def 6060484Sobrien{ 6160484Sobrien /* The number of elements in this partition. */ 6260484Sobrien int num_elements; 6360484Sobrien /* The elements in the partition. */ 6460484Sobrien struct partition_elem elements[1]; 6560484Sobrien} *partition; 6660484Sobrien 67218822Sdimextern partition partition_new (int); 68218822Sdimextern void partition_delete (partition); 69218822Sdimextern int partition_union (partition, int, int); 70218822Sdimextern void partition_print (partition, FILE*); 7160484Sobrien 7260484Sobrien/* Returns the canonical element corresponding to the class containing 7360484Sobrien ELEMENT__ in PARTITION__. */ 7460484Sobrien 7560484Sobrien#define partition_find(partition__, element__) \ 7660484Sobrien ((partition__)->elements[(element__)].class_element) 7760484Sobrien 78130561Sobrien#ifdef __cplusplus 79130561Sobrien} 80130561Sobrien#endif /* __cplusplus */ 81130561Sobrien 8260484Sobrien#endif /* _PARTITION_H */ 83