14fee23f9Smrg /* List implementation of a partition of consecutive integers. 2*b1e83836Smrg Copyright (C) 2000-2022 Free Software Foundation, Inc. 34fee23f9Smrg Contributed by CodeSourcery, LLC. 44fee23f9Smrg 54fee23f9Smrg This file is part of GCC. 64fee23f9Smrg 74fee23f9Smrg GCC is free software; you can redistribute it and/or modify 84fee23f9Smrg it under the terms of the GNU General Public License as published by 94fee23f9Smrg the Free Software Foundation; either version 2, or (at your option) 104fee23f9Smrg any later version. 114fee23f9Smrg 124fee23f9Smrg GCC is distributed in the hope that it will be useful, 134fee23f9Smrg but WITHOUT ANY WARRANTY; without even the implied warranty of 144fee23f9Smrg MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 154fee23f9Smrg GNU General Public License for more details. 164fee23f9Smrg 174fee23f9Smrg You should have received a copy of the GNU General Public License 184fee23f9Smrg along with GCC; see the file COPYING. If not, write to 194fee23f9Smrg the Free Software Foundation, 51 Franklin Street - Fifth Floor, 204fee23f9Smrg Boston, MA 02110-1301, USA. */ 214fee23f9Smrg 224fee23f9Smrg /* This package implements a partition of consecutive integers. The 234fee23f9Smrg elements are partitioned into classes. Each class is represented 244fee23f9Smrg by one of its elements, the canonical element, which is chosen 254fee23f9Smrg arbitrarily from elements in the class. The principal operations 264fee23f9Smrg on a partition are FIND, which takes an element, determines its 274fee23f9Smrg class, and returns the canonical element for that class, and UNION, 284fee23f9Smrg which unites the two classes that contain two given elements into a 294fee23f9Smrg single class. 304fee23f9Smrg 314fee23f9Smrg The list implementation used here provides constant-time finds. By 324fee23f9Smrg storing the size of each class with the class's canonical element, 334fee23f9Smrg it is able to perform unions over all the classes in the partition 344fee23f9Smrg in O (N log N) time. */ 354fee23f9Smrg 364fee23f9Smrg #ifndef _PARTITION_H 374fee23f9Smrg #define _PARTITION_H 384fee23f9Smrg 394fee23f9Smrg #ifdef __cplusplus 404fee23f9Smrg extern "C" { 414fee23f9Smrg #endif /* __cplusplus */ 424fee23f9Smrg 434fee23f9Smrg #include "ansidecl.h" 444fee23f9Smrg #include <stdio.h> 454fee23f9Smrg 464fee23f9Smrg struct partition_elem 474fee23f9Smrg { 484fee23f9Smrg /* The next element in this class. Elements in each class form a 494fee23f9Smrg circular list. */ 504fee23f9Smrg struct partition_elem* next; 514d5abbe8Smrg /* The canonical element that represents the class containing this 524d5abbe8Smrg element. */ 534d5abbe8Smrg int class_element; 544fee23f9Smrg /* The number of elements in this class. Valid only if this is the 554fee23f9Smrg canonical element for its class. */ 564fee23f9Smrg unsigned class_count; 574fee23f9Smrg }; 584fee23f9Smrg 594fee23f9Smrg typedef struct partition_def 604fee23f9Smrg { 614fee23f9Smrg /* The number of elements in this partition. */ 624fee23f9Smrg int num_elements; 634fee23f9Smrg /* The elements in the partition. */ 644fee23f9Smrg struct partition_elem elements[1]; 654fee23f9Smrg } *partition; 664fee23f9Smrg 674fee23f9Smrg extern partition partition_new (int); 684fee23f9Smrg extern void partition_delete (partition); 694fee23f9Smrg extern int partition_union (partition, int, int); 704fee23f9Smrg extern void partition_print (partition, FILE*); 714fee23f9Smrg 724fee23f9Smrg /* Returns the canonical element corresponding to the class containing 734fee23f9Smrg ELEMENT__ in PARTITION__. */ 744fee23f9Smrg 754fee23f9Smrg #define partition_find(partition__, element__) \ 764fee23f9Smrg ((partition__)->elements[(element__)].class_element) 774fee23f9Smrg 784fee23f9Smrg #ifdef __cplusplus 794fee23f9Smrg } 804fee23f9Smrg #endif /* __cplusplus */ 814fee23f9Smrg 824fee23f9Smrg #endif /* _PARTITION_H */ 83