12a6b7db3Sskrll /* List implementation of a partition of consecutive integers. 2*cb63e24eSchristos Copyright (C) 2000-2024 Free Software Foundation, Inc. 32a6b7db3Sskrll Contributed by CodeSourcery, LLC. 42a6b7db3Sskrll 52a6b7db3Sskrll This file is part of GCC. 62a6b7db3Sskrll 72a6b7db3Sskrll GCC is free software; you can redistribute it and/or modify 82a6b7db3Sskrll it under the terms of the GNU General Public License as published by 92a6b7db3Sskrll the Free Software Foundation; either version 2, or (at your option) 102a6b7db3Sskrll any later version. 112a6b7db3Sskrll 122a6b7db3Sskrll GCC is distributed in the hope that it will be useful, 132a6b7db3Sskrll but WITHOUT ANY WARRANTY; without even the implied warranty of 142a6b7db3Sskrll MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 152a6b7db3Sskrll GNU General Public License for more details. 162a6b7db3Sskrll 172a6b7db3Sskrll You should have received a copy of the GNU General Public License 182a6b7db3Sskrll along with GCC; see the file COPYING. If not, write to 192a6b7db3Sskrll the Free Software Foundation, 51 Franklin Street - Fifth Floor, 202a6b7db3Sskrll Boston, MA 02110-1301, USA. */ 212a6b7db3Sskrll 222a6b7db3Sskrll /* This package implements a partition of consecutive integers. The 232a6b7db3Sskrll elements are partitioned into classes. Each class is represented 242a6b7db3Sskrll by one of its elements, the canonical element, which is chosen 252a6b7db3Sskrll arbitrarily from elements in the class. The principal operations 262a6b7db3Sskrll on a partition are FIND, which takes an element, determines its 272a6b7db3Sskrll class, and returns the canonical element for that class, and UNION, 282a6b7db3Sskrll which unites the two classes that contain two given elements into a 292a6b7db3Sskrll single class. 302a6b7db3Sskrll 312a6b7db3Sskrll The list implementation used here provides constant-time finds. By 322a6b7db3Sskrll storing the size of each class with the class's canonical element, 332a6b7db3Sskrll it is able to perform unions over all the classes in the partition 342a6b7db3Sskrll in O (N log N) time. */ 352a6b7db3Sskrll 362a6b7db3Sskrll #ifndef _PARTITION_H 372a6b7db3Sskrll #define _PARTITION_H 382a6b7db3Sskrll 392a6b7db3Sskrll #ifdef __cplusplus 402a6b7db3Sskrll extern "C" { 412a6b7db3Sskrll #endif /* __cplusplus */ 422a6b7db3Sskrll 432a6b7db3Sskrll #include "ansidecl.h" 442a6b7db3Sskrll #include <stdio.h> 452a6b7db3Sskrll 462a6b7db3Sskrll struct partition_elem 472a6b7db3Sskrll { 482a6b7db3Sskrll /* The next element in this class. Elements in each class form a 492a6b7db3Sskrll circular list. */ 502a6b7db3Sskrll struct partition_elem* next; 519573673dSchristos /* The canonical element that represents the class containing this 529573673dSchristos element. */ 539573673dSchristos int class_element; 542a6b7db3Sskrll /* The number of elements in this class. Valid only if this is the 552a6b7db3Sskrll canonical element for its class. */ 562a6b7db3Sskrll unsigned class_count; 572a6b7db3Sskrll }; 582a6b7db3Sskrll 592a6b7db3Sskrll typedef struct partition_def 602a6b7db3Sskrll { 612a6b7db3Sskrll /* The number of elements in this partition. */ 622a6b7db3Sskrll int num_elements; 632a6b7db3Sskrll /* The elements in the partition. */ 642a6b7db3Sskrll struct partition_elem elements[1]; 652a6b7db3Sskrll } *partition; 662a6b7db3Sskrll 672a6b7db3Sskrll extern partition partition_new (int); 682a6b7db3Sskrll extern void partition_delete (partition); 692a6b7db3Sskrll extern int partition_union (partition, int, int); 702a6b7db3Sskrll extern void partition_print (partition, FILE*); 712a6b7db3Sskrll 722a6b7db3Sskrll /* Returns the canonical element corresponding to the class containing 732a6b7db3Sskrll ELEMENT__ in PARTITION__. */ 742a6b7db3Sskrll 752a6b7db3Sskrll #define partition_find(partition__, element__) \ 762a6b7db3Sskrll ((partition__)->elements[(element__)].class_element) 772a6b7db3Sskrll 782a6b7db3Sskrll #ifdef __cplusplus 792a6b7db3Sskrll } 802a6b7db3Sskrll #endif /* __cplusplus */ 812a6b7db3Sskrll 822a6b7db3Sskrll #endif /* _PARTITION_H */ 83