Back to index

cell-binutils  2.17cvs20070401
partition.h
Go to the documentation of this file.
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 */