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