]>
Commit | Line | Data |
---|---|---|
0e751f46 | 1 | /* List implementation of a partition of consecutive integers. |
fbd26352 | 2 | Copyright (C) 2000-2019 Free Software Foundation, Inc. |
dadde703 | 3 | Contributed by CodeSourcery, LLC. |
4 | ||
59f59894 | 5 | This file is part of GCC. |
dadde703 | 6 | |
59f59894 | 7 | GCC is free software; you can redistribute it and/or modify |
dadde703 | 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 | ||
59f59894 | 12 | GCC is distributed in the hope that it will be useful, |
dadde703 | 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 | |
59f59894 | 18 | along with GCC; see the file COPYING. If not, write to |
2f8ebb8e | 19 | the Free Software Foundation, 51 Franklin Street - Fifth Floor, |
20 | Boston, MA 02110-1301, USA. */ | |
dadde703 | 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 | ||
5f94337d | 43 | #include "ansidecl.h" |
dadde703 | 44 | #include <stdio.h> |
45 | ||
46 | struct partition_elem | |
47 | { | |
dadde703 | 48 | /* The next element in this class. Elements in each class form a |
49 | circular list. */ | |
50 | struct partition_elem* next; | |
5b208a42 | 51 | /* The canonical element that represents the class containing this |
52 | element. */ | |
53 | int class_element; | |
dadde703 | 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 | ||
f8d9d6a0 | 67 | extern partition partition_new (int); |
68 | extern void partition_delete (partition); | |
69 | extern int partition_union (partition, int, int); | |
70 | extern void partition_print (partition, FILE*); | |
dadde703 | 71 | |
72 | /* Returns the canonical element corresponding to the class containing | |
73 | ELEMENT__ in PARTITION__. */ | |
74 | ||
75 | #define partition_find(partition__, element__) \ | |
76 | ((partition__)->elements[(element__)].class_element) | |
77 | ||
45b1e9e3 | 78 | #ifdef __cplusplus |
79 | } | |
80 | #endif /* __cplusplus */ | |
81 | ||
dadde703 | 82 | #endif /* _PARTITION_H */ |