175fd0b74Schristos /* List implementation of a partition of consecutive integers. 2*e992f068Schristos Copyright (C) 2000-2022 Free Software Foundation, Inc. 375fd0b74Schristos Contributed by CodeSourcery, LLC. 475fd0b74Schristos 575fd0b74Schristos This file is part of GCC. 675fd0b74Schristos 775fd0b74Schristos GCC is free software; you can redistribute it and/or modify 875fd0b74Schristos it under the terms of the GNU General Public License as published by 975fd0b74Schristos the Free Software Foundation; either version 2, or (at your option) 1075fd0b74Schristos any later version. 1175fd0b74Schristos 1275fd0b74Schristos GCC is distributed in the hope that it will be useful, 1375fd0b74Schristos but WITHOUT ANY WARRANTY; without even the implied warranty of 1475fd0b74Schristos MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1575fd0b74Schristos GNU General Public License for more details. 1675fd0b74Schristos 1775fd0b74Schristos You should have received a copy of the GNU General Public License 1875fd0b74Schristos along with GCC; see the file COPYING. If not, write to 1975fd0b74Schristos the Free Software Foundation, 51 Franklin Street - Fifth Floor, 2075fd0b74Schristos Boston, MA 02110-1301, USA. */ 2175fd0b74Schristos 2275fd0b74Schristos /* This package implements a partition of consecutive integers. The 2375fd0b74Schristos elements are partitioned into classes. Each class is represented 2475fd0b74Schristos by one of its elements, the canonical element, which is chosen 2575fd0b74Schristos arbitrarily from elements in the class. The principal operations 2675fd0b74Schristos on a partition are FIND, which takes an element, determines its 2775fd0b74Schristos class, and returns the canonical element for that class, and UNION, 2875fd0b74Schristos which unites the two classes that contain two given elements into a 2975fd0b74Schristos single class. 3075fd0b74Schristos 3175fd0b74Schristos The list implementation used here provides constant-time finds. By 3275fd0b74Schristos storing the size of each class with the class's canonical element, 3375fd0b74Schristos it is able to perform unions over all the classes in the partition 3475fd0b74Schristos in O (N log N) time. */ 3575fd0b74Schristos 3675fd0b74Schristos #ifndef _PARTITION_H 3775fd0b74Schristos #define _PARTITION_H 3875fd0b74Schristos 3975fd0b74Schristos #ifdef __cplusplus 4075fd0b74Schristos extern "C" { 4175fd0b74Schristos #endif /* __cplusplus */ 4275fd0b74Schristos 4375fd0b74Schristos #include "ansidecl.h" 4475fd0b74Schristos #include <stdio.h> 4575fd0b74Schristos 4675fd0b74Schristos struct partition_elem 4775fd0b74Schristos { 4875fd0b74Schristos /* The next element in this class. Elements in each class form a 4975fd0b74Schristos circular list. */ 5075fd0b74Schristos struct partition_elem* next; 5175fd0b74Schristos /* The canonical element that represents the class containing this 5275fd0b74Schristos element. */ 5375fd0b74Schristos int class_element; 5475fd0b74Schristos /* The number of elements in this class. Valid only if this is the 5575fd0b74Schristos canonical element for its class. */ 5675fd0b74Schristos unsigned class_count; 5775fd0b74Schristos }; 5875fd0b74Schristos 5975fd0b74Schristos typedef struct partition_def 6075fd0b74Schristos { 6175fd0b74Schristos /* The number of elements in this partition. */ 6275fd0b74Schristos int num_elements; 6375fd0b74Schristos /* The elements in the partition. */ 6475fd0b74Schristos struct partition_elem elements[1]; 6575fd0b74Schristos } *partition; 6675fd0b74Schristos 6775fd0b74Schristos extern partition partition_new (int); 6875fd0b74Schristos extern void partition_delete (partition); 6975fd0b74Schristos extern int partition_union (partition, int, int); 7075fd0b74Schristos extern void partition_print (partition, FILE*); 7175fd0b74Schristos 7275fd0b74Schristos /* Returns the canonical element corresponding to the class containing 7375fd0b74Schristos ELEMENT__ in PARTITION__. */ 7475fd0b74Schristos 7575fd0b74Schristos #define partition_find(partition__, element__) \ 7675fd0b74Schristos ((partition__)->elements[(element__)].class_element) 7775fd0b74Schristos 7875fd0b74Schristos #ifdef __cplusplus 7975fd0b74Schristos } 8075fd0b74Schristos #endif /* __cplusplus */ 8175fd0b74Schristos 8275fd0b74Schristos #endif /* _PARTITION_H */ 83