--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/include/partition.h	Fri Jul 17 14:47:48 2009 +0900
@@ -0,0 +1,82 @@
+/* List implementation of a partition of consecutive integers.
+   Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
+   Contributed by CodeSourcery, LLC.
+
+   This file is part of GCC.
+
+   GCC is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   GCC is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with GCC; see the file COPYING.  If not, write to
+   the Free Software Foundation, 51 Franklin Street - Fifth Floor,
+   Boston, MA 02110-1301, USA.  */
+
+/* This package implements a partition of consecutive integers.  The
+   elements are partitioned into classes.  Each class is represented
+   by one of its elements, the canonical element, which is chosen
+   arbitrarily from elements in the class.  The principal operations
+   on a partition are FIND, which takes an element, determines its
+   class, and returns the canonical element for that class, and UNION,
+   which unites the two classes that contain two given elements into a
+   single class.
+
+   The list implementation used here provides constant-time finds.  By
+   storing the size of each class with the class's canonical element,
+   it is able to perform unions over all the classes in the partition
+   in O (N log N) time.  */
+
+#ifndef _PARTITION_H
+#define _PARTITION_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+#include "ansidecl.h"
+#include <stdio.h>
+
+struct partition_elem
+{
+  /* The canonical element that represents the class containing this
+     element.  */
+  int class_element;
+  /* The next element in this class.  Elements in each class form a
+     circular list.  */
+  struct partition_elem* next;
+  /* The number of elements in this class.  Valid only if this is the
+     canonical element for its class.  */
+  unsigned class_count;
+};
+
+typedef struct partition_def 
+{
+  /* The number of elements in this partition.  */
+  int num_elements;
+  /* The elements in the partition.  */
+  struct partition_elem elements[1];
+} *partition;
+
+extern partition partition_new (int);
+extern void partition_delete (partition);
+extern int partition_union (partition, int, int);
+extern void partition_print (partition,	FILE*);
+
+/* Returns the canonical element corresponding to the class containing
+   ELEMENT__ in PARTITION__.  */
+
+#define partition_find(partition__, element__) \
+    ((partition__)->elements[(element__)].class_element)
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* _PARTITION_H */