11debfc3dSmrg /* List implementation of a partition of consecutive integers. 2*8feb0f0bSmrg Copyright (C) 2000-2020 Free Software Foundation, Inc. 31debfc3dSmrg Contributed by CodeSourcery, LLC. 41debfc3dSmrg 51debfc3dSmrg This file is part of GCC. 61debfc3dSmrg 71debfc3dSmrg GCC is free software; you can redistribute it and/or modify 81debfc3dSmrg it under the terms of the GNU General Public License as published by 91debfc3dSmrg the Free Software Foundation; either version 2, or (at your option) 101debfc3dSmrg any later version. 111debfc3dSmrg 121debfc3dSmrg GCC is distributed in the hope that it will be useful, 131debfc3dSmrg but WITHOUT ANY WARRANTY; without even the implied warranty of 141debfc3dSmrg MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 151debfc3dSmrg GNU General Public License for more details. 161debfc3dSmrg 171debfc3dSmrg You should have received a copy of the GNU General Public License 181debfc3dSmrg along with GCC; see the file COPYING. If not, write to 191debfc3dSmrg the Free Software Foundation, 51 Franklin Street - Fifth Floor, 201debfc3dSmrg Boston, MA 02110-1301, USA. */ 211debfc3dSmrg 221debfc3dSmrg /* This package implements a partition of consecutive integers. The 231debfc3dSmrg elements are partitioned into classes. Each class is represented 241debfc3dSmrg by one of its elements, the canonical element, which is chosen 251debfc3dSmrg arbitrarily from elements in the class. The principal operations 261debfc3dSmrg on a partition are FIND, which takes an element, determines its 271debfc3dSmrg class, and returns the canonical element for that class, and UNION, 281debfc3dSmrg which unites the two classes that contain two given elements into a 291debfc3dSmrg single class. 301debfc3dSmrg 311debfc3dSmrg The list implementation used here provides constant-time finds. By 321debfc3dSmrg storing the size of each class with the class's canonical element, 331debfc3dSmrg it is able to perform unions over all the classes in the partition 341debfc3dSmrg in O (N log N) time. */ 351debfc3dSmrg 361debfc3dSmrg #ifndef _PARTITION_H 371debfc3dSmrg #define _PARTITION_H 381debfc3dSmrg 391debfc3dSmrg #ifdef __cplusplus 401debfc3dSmrg extern "C" { 411debfc3dSmrg #endif /* __cplusplus */ 421debfc3dSmrg 431debfc3dSmrg #include "ansidecl.h" 441debfc3dSmrg #include <stdio.h> 451debfc3dSmrg 461debfc3dSmrg struct partition_elem 471debfc3dSmrg { 481debfc3dSmrg /* The next element in this class. Elements in each class form a 491debfc3dSmrg circular list. */ 501debfc3dSmrg struct partition_elem* next; 511debfc3dSmrg /* The canonical element that represents the class containing this 521debfc3dSmrg element. */ 531debfc3dSmrg int class_element; 541debfc3dSmrg /* The number of elements in this class. Valid only if this is the 551debfc3dSmrg canonical element for its class. */ 561debfc3dSmrg unsigned class_count; 571debfc3dSmrg }; 581debfc3dSmrg 591debfc3dSmrg typedef struct partition_def 601debfc3dSmrg { 611debfc3dSmrg /* The number of elements in this partition. */ 621debfc3dSmrg int num_elements; 631debfc3dSmrg /* The elements in the partition. */ 641debfc3dSmrg struct partition_elem elements[1]; 651debfc3dSmrg } *partition; 661debfc3dSmrg 671debfc3dSmrg extern partition partition_new (int); 681debfc3dSmrg extern void partition_delete (partition); 691debfc3dSmrg extern int partition_union (partition, int, int); 701debfc3dSmrg extern void partition_print (partition, FILE*); 711debfc3dSmrg 721debfc3dSmrg /* Returns the canonical element corresponding to the class containing 731debfc3dSmrg ELEMENT__ in PARTITION__. */ 741debfc3dSmrg 751debfc3dSmrg #define partition_find(partition__, element__) \ 761debfc3dSmrg ((partition__)->elements[(element__)].class_element) 771debfc3dSmrg 781debfc3dSmrg #ifdef __cplusplus 791debfc3dSmrg } 801debfc3dSmrg #endif /* __cplusplus */ 811debfc3dSmrg 821debfc3dSmrg #endif /* _PARTITION_H */ 83