aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
authorChristopher Faylor <me+cygwin@cgf.cx>2000-03-25 02:15:38 +0000
committerChristopher Faylor <me+cygwin@cgf.cx>2000-03-25 02:15:38 +0000
commit11bb320587113cc97e3bcc56c7399c91c1203751 (patch)
tree0cc6a2eae1515fb2777ba08be95d8524b7bb2fbe /include
parent57c987aa1017d17b686c47f916c9e1bf7f5e13eb (diff)
downloadgdb-11bb320587113cc97e3bcc56c7399c91c1203751.zip
gdb-11bb320587113cc97e3bcc56c7399c91c1203751.tar.gz
gdb-11bb320587113cc97e3bcc56c7399c91c1203751.tar.bz2
* partition.h: New file.
Diffstat (limited to 'include')
-rw-r--r--include/partition.h81
1 files changed, 81 insertions, 0 deletions
diff --git a/include/partition.h b/include/partition.h
new file mode 100644
index 0000000..f49d67a
--- /dev/null
+++ b/include/partition.h
@@ -0,0 +1,81 @@
+/* List implentation of a partition of consecutive integers.
+ Copyright (C) 2000 Free Software Foundation, Inc.
+ Contributed by CodeSourcery, LLC.
+
+ This file is part of GNU CC.
+
+ GNU CC 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.
+
+ GNU CC 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 GNU CC; see the file COPYING. If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, 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 PARAMS((int));
+extern void partition_delete PARAMS((partition));
+extern int partition_union PARAMS((partition,
+ int,
+ int));
+extern void partition_print PARAMS((partition,
+ FILE*));
+
+/* Returns the canonical element corresponding to the class containing
+ ELEMENT__ in PARTITION__. */
+
+#define partition_find(partition__, element__) \
+ ((partition__)->elements[(element__)].class_element)
+
+#endif /* _PARTITION_H */