1169695Skan/* List implementation of a partition of consecutive integers. 2169695Skan Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. 3169695Skan Contributed by CodeSourcery, LLC. 4169695Skan 5169695Skan This file is part of GCC. 6169695Skan 7169695Skan GCC is free software; you can redistribute it and/or modify 8169695Skan it under the terms of the GNU General Public License as published by 9169695Skan the Free Software Foundation; either version 2, or (at your option) 10169695Skan any later version. 11169695Skan 12169695Skan GCC is distributed in the hope that it will be useful, 13169695Skan but WITHOUT ANY WARRANTY; without even the implied warranty of 14169695Skan MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169695Skan GNU General Public License for more details. 16169695Skan 17169695Skan You should have received a copy of the GNU General Public License 18169695Skan along with GCC; see the file COPYING. If not, write to 19169695Skan the Free Software Foundation, 51 Franklin Street - Fifth Floor, 20169695Skan Boston, MA 02110-1301, USA. */ 21169695Skan 22169695Skan/* This package implements a partition of consecutive integers. The 23169695Skan elements are partitioned into classes. Each class is represented 24169695Skan by one of its elements, the canonical element, which is chosen 25169695Skan arbitrarily from elements in the class. The principal operations 26169695Skan on a partition are FIND, which takes an element, determines its 27169695Skan class, and returns the canonical element for that class, and UNION, 28169695Skan which unites the two classes that contain two given elements into a 29169695Skan single class. 30169695Skan 31169695Skan The list implementation used here provides constant-time finds. By 32169695Skan storing the size of each class with the class's canonical element, 33169695Skan it is able to perform unions over all the classes in the partition 34169695Skan in O (N log N) time. */ 35169695Skan 36169695Skan#ifndef _PARTITION_H 37169695Skan#define _PARTITION_H 38169695Skan 39169695Skan#ifdef __cplusplus 40169695Skanextern "C" { 41169695Skan#endif /* __cplusplus */ 42169695Skan 43169695Skan#include "ansidecl.h" 44169695Skan#include <stdio.h> 45169695Skan 46169695Skanstruct partition_elem 47169695Skan{ 48169695Skan /* The canonical element that represents the class containing this 49169695Skan element. */ 50169695Skan int class_element; 51169695Skan /* The next element in this class. Elements in each class form a 52169695Skan circular list. */ 53169695Skan struct partition_elem* next; 54169695Skan /* The number of elements in this class. Valid only if this is the 55169695Skan canonical element for its class. */ 56169695Skan unsigned class_count; 57169695Skan}; 58169695Skan 59169695Skantypedef struct partition_def 60169695Skan{ 61169695Skan /* The number of elements in this partition. */ 62169695Skan int num_elements; 63169695Skan /* The elements in the partition. */ 64169695Skan struct partition_elem elements[1]; 65169695Skan} *partition; 66169695Skan 67169695Skanextern partition partition_new (int); 68169695Skanextern void partition_delete (partition); 69169695Skanextern int partition_union (partition, int, int); 70169695Skanextern void partition_print (partition, FILE*); 71169695Skan 72169695Skan/* Returns the canonical element corresponding to the class containing 73169695Skan ELEMENT__ in PARTITION__. */ 74169695Skan 75169695Skan#define partition_find(partition__, element__) \ 76169695Skan ((partition__)->elements[(element__)].class_element) 77169695Skan 78169695Skan#ifdef __cplusplus 79169695Skan} 80169695Skan#endif /* __cplusplus */ 81169695Skan 82169695Skan#endif /* _PARTITION_H */ 83