1 /* List implementation of a partition of consecutive integers.
2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
3 Contributed by CodeSourcery, LLC.
5 This file is part of GCC.
7 GCC 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)
12 GCC 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.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
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
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. */
41 #endif /* __cplusplus */
48 /* The canonical element that represents the class containing this
51 /* The next element in this class. Elements in each class form a
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. */
59 typedef struct partition_def
61 /* The number of elements in this partition. */
63 /* The elements in the partition. */
64 struct partition_elem elements
[1];
67 extern partition partition_new
PARAMS((int));
68 extern void partition_delete
PARAMS((partition
));
69 extern int partition_union
PARAMS((partition
,
72 extern void partition_print
PARAMS((partition
,
75 /* Returns the canonical element corresponding to the class containing
76 ELEMENT__ in PARTITION__. */
78 #define partition_find(partition__, element__) \
79 ((partition__)->elements[(element__)].class_element)
81 #endif /* _PARTITION_H */
This page took 0.031517 seconds and 4 git commands to generate.