include/partition.h

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