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