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