00001 /* List implementation of a partition of consecutive integers. 00002 Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. 00003 Contributed by CodeSourcery, LLC. 00004 00005 This file is part of GCC. 00006 00007 GCC is free software; you can redistribute it and/or modify 00008 it under the terms of the GNU General Public License as published by 00009 the Free Software Foundation; either version 2, or (at your option) 00010 any later version. 00011 00012 GCC is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 GNU General Public License for more details. 00016 00017 You should have received a copy of the GNU General Public License 00018 along with GCC; see the file COPYING. If not, write to 00019 the Free Software Foundation, 51 Franklin Street - Fifth Floor, 00020 Boston, MA 02110-1301, USA. */ 00021 00022 /* This package implements a partition of consecutive integers. The 00023 elements are partitioned into classes. Each class is represented 00024 by one of its elements, the canonical element, which is chosen 00025 arbitrarily from elements in the class. The principal operations 00026 on a partition are FIND, which takes an element, determines its 00027 class, and returns the canonical element for that class, and UNION, 00028 which unites the two classes that contain two given elements into a 00029 single class. 00030 00031 The list implementation used here provides constant-time finds. By 00032 storing the size of each class with the class's canonical element, 00033 it is able to perform unions over all the classes in the partition 00034 in O (N log N) time. */ 00035 00036 #ifndef _PARTITION_H 00037 #define _PARTITION_H 00038 00039 #ifdef __cplusplus 00040 extern "C" { 00041 #endif /* __cplusplus */ 00042 00043 #include "ansidecl.h" 00044 #include <stdio.h> 00045 00046 struct partition_elem 00047 { 00048 /* The canonical element that represents the class containing this 00049 element. */ 00050 int class_element; 00051 /* The next element in this class. Elements in each class form a 00052 circular list. */ 00053 struct partition_elem* next; 00054 /* The number of elements in this class. Valid only if this is the 00055 canonical element for its class. */ 00056 unsigned class_count; 00057 }; 00058 00059 typedef struct partition_def 00060 { 00061 /* The number of elements in this partition. */ 00062 int num_elements; 00063 /* The elements in the partition. */ 00064 struct partition_elem elements[1]; 00065 } *partition; 00066 00067 extern partition partition_new (int); 00068 extern void partition_delete (partition); 00069 extern int partition_union (partition, int, int); 00070 extern void partition_print (partition, FILE*); 00071 00072 /* Returns the canonical element corresponding to the class containing 00073 ELEMENT__ in PARTITION__. */ 00074 00075 #define partition_find(partition__, element__) \ 00076 ((partition__)->elements[(element__)].class_element) 00077 00078 #ifdef __cplusplus 00079 } 00080 #endif /* __cplusplus */ 00081 00082 #endif /* _PARTITION_H */
1.5.6