1*404b540aSrobert /* List implementation of a partition of consecutive integers. 2*404b540aSrobert Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. 3*404b540aSrobert Contributed by CodeSourcery, LLC. 4*404b540aSrobert 5*404b540aSrobert This file is part of GCC. 6*404b540aSrobert 7*404b540aSrobert GCC is free software; you can redistribute it and/or modify 8*404b540aSrobert it under the terms of the GNU General Public License as published by 9*404b540aSrobert the Free Software Foundation; either version 2, or (at your option) 10*404b540aSrobert any later version. 11*404b540aSrobert 12*404b540aSrobert GCC is distributed in the hope that it will be useful, 13*404b540aSrobert but WITHOUT ANY WARRANTY; without even the implied warranty of 14*404b540aSrobert MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15*404b540aSrobert GNU General Public License for more details. 16*404b540aSrobert 17*404b540aSrobert You should have received a copy of the GNU General Public License 18*404b540aSrobert along with GCC; see the file COPYING. If not, write to 19*404b540aSrobert the Free Software Foundation, 51 Franklin Street - Fifth Floor, 20*404b540aSrobert Boston, MA 02110-1301, USA. */ 21*404b540aSrobert 22*404b540aSrobert /* This package implements a partition of consecutive integers. The 23*404b540aSrobert elements are partitioned into classes. Each class is represented 24*404b540aSrobert by one of its elements, the canonical element, which is chosen 25*404b540aSrobert arbitrarily from elements in the class. The principal operations 26*404b540aSrobert on a partition are FIND, which takes an element, determines its 27*404b540aSrobert class, and returns the canonical element for that class, and UNION, 28*404b540aSrobert which unites the two classes that contain two given elements into a 29*404b540aSrobert single class. 30*404b540aSrobert 31*404b540aSrobert The list implementation used here provides constant-time finds. By 32*404b540aSrobert storing the size of each class with the class's canonical element, 33*404b540aSrobert it is able to perform unions over all the classes in the partition 34*404b540aSrobert in O (N log N) time. */ 35*404b540aSrobert 36*404b540aSrobert #ifndef _PARTITION_H 37*404b540aSrobert #define _PARTITION_H 38*404b540aSrobert 39*404b540aSrobert #ifdef __cplusplus 40*404b540aSrobert extern "C" { 41*404b540aSrobert #endif /* __cplusplus */ 42*404b540aSrobert 43*404b540aSrobert #include "ansidecl.h" 44*404b540aSrobert #include <stdio.h> 45*404b540aSrobert 46*404b540aSrobert struct partition_elem 47*404b540aSrobert { 48*404b540aSrobert /* The canonical element that represents the class containing this 49*404b540aSrobert element. */ 50*404b540aSrobert int class_element; 51*404b540aSrobert /* The next element in this class. Elements in each class form a 52*404b540aSrobert circular list. */ 53*404b540aSrobert struct partition_elem* next; 54*404b540aSrobert /* The number of elements in this class. Valid only if this is the 55*404b540aSrobert canonical element for its class. */ 56*404b540aSrobert unsigned class_count; 57*404b540aSrobert }; 58*404b540aSrobert 59*404b540aSrobert typedef struct partition_def 60*404b540aSrobert { 61*404b540aSrobert /* The number of elements in this partition. */ 62*404b540aSrobert int num_elements; 63*404b540aSrobert /* The elements in the partition. */ 64*404b540aSrobert struct partition_elem elements[1]; 65*404b540aSrobert } *partition; 66*404b540aSrobert 67*404b540aSrobert extern partition partition_new (int); 68*404b540aSrobert extern void partition_delete (partition); 69*404b540aSrobert extern int partition_union (partition, int, int); 70*404b540aSrobert extern void partition_print (partition, FILE*); 71*404b540aSrobert 72*404b540aSrobert /* Returns the canonical element corresponding to the class containing 73*404b540aSrobert ELEMENT__ in PARTITION__. */ 74*404b540aSrobert 75*404b540aSrobert #define partition_find(partition__, element__) \ 76*404b540aSrobert ((partition__)->elements[(element__)].class_element) 77*404b540aSrobert 78*404b540aSrobert #ifdef __cplusplus 79*404b540aSrobert } 80*404b540aSrobert #endif /* __cplusplus */ 81*404b540aSrobert 82*404b540aSrobert #endif /* _PARTITION_H */ 83