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