1 | /* Bitset vectors. |
2 | |
3 | Copyright (C) 2001-2002, 2004-2006, 2009-2015, 2018-2019 Free Software |
4 | Foundation, Inc. |
5 | |
6 | This program is free software: you can redistribute it and/or modify |
7 | it under the terms of the GNU General Public License as published by |
8 | the Free Software Foundation, either version 3 of the License, or |
9 | (at your option) any later version. |
10 | |
11 | This program is distributed in the hope that it will be useful, |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | GNU General Public License for more details. |
15 | |
16 | You should have received a copy of the GNU General Public License |
17 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
18 | |
19 | #include <config.h> |
20 | |
21 | #include "bitsetv.h" |
22 | |
23 | #include <stdlib.h> |
24 | |
25 | #include "xalloc.h" |
26 | |
27 | |
28 | /* Create a vector of N_VECS bitsets, each of N_BITS, and of |
29 | type TYPE. */ |
30 | bitset * |
31 | bitsetv_alloc (bitset_bindex n_vecs, bitset_bindex n_bits, |
32 | enum bitset_type type) |
33 | { |
34 | /* Determine number of bytes for each set. */ |
35 | size_t bytes = bitset_bytes (type, n_bits); |
36 | |
37 | /* If size calculation overflows, memory is exhausted. */ |
38 | if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs) |
39 | xalloc_die (); |
40 | |
41 | /* Allocate vector table at head of bitset array. */ |
42 | size_t vector_bytes = (n_vecs + 1) * sizeof (bitset) + bytes - 1; |
43 | vector_bytes -= vector_bytes % bytes; |
44 | bitset *bsetv = xzalloc (vector_bytes + bytes * n_vecs); |
45 | |
46 | bitset_bindex i = 0; |
47 | for (i = 0; i < n_vecs; i++) |
48 | { |
49 | bsetv[i] = (bitset) (void *) ((char *) bsetv + vector_bytes + i * bytes); |
50 | |
51 | bitset_init (bsetv[i], n_bits, type); |
52 | } |
53 | |
54 | /* Null terminate table. */ |
55 | bsetv[i] = 0; |
56 | return bsetv; |
57 | } |
58 | |
59 | |
60 | /* Create a vector of N_VECS bitsets, each of N_BITS, and with |
61 | attribute hints specified by ATTR. */ |
62 | bitset * |
63 | bitsetv_create (bitset_bindex n_vecs, bitset_bindex n_bits, unsigned attr) |
64 | { |
65 | enum bitset_type type = bitset_type_choose (n_bits, attr); |
66 | return bitsetv_alloc (n_vecs, n_bits, type); |
67 | } |
68 | |
69 | |
70 | /* Free bitset vector BSETV. */ |
71 | void |
72 | bitsetv_free (bitsetv bsetv) |
73 | { |
74 | if (bsetv) |
75 | { |
76 | for (bitset_bindex i = 0; bsetv[i]; i++) |
77 | BITSET_FREE_ (bsetv[i]); |
78 | free (bsetv); |
79 | } |
80 | } |
81 | |
82 | |
83 | /* Zero a vector of bitsets. */ |
84 | void |
85 | bitsetv_zero (bitsetv bsetv) |
86 | { |
87 | for (bitset_bindex i = 0; bsetv[i]; i++) |
88 | bitset_zero (bsetv[i]); |
89 | } |
90 | |
91 | |
92 | /* Set a vector of bitsets to ones. */ |
93 | void |
94 | bitsetv_ones (bitsetv bsetv) |
95 | { |
96 | for (bitset_bindex i = 0; bsetv[i]; i++) |
97 | bitset_ones (bsetv[i]); |
98 | } |
99 | |
100 | |
101 | /* Given a vector BSETV of N bitsets of size N, modify its contents to |
102 | be the transitive closure of what was given. */ |
103 | void |
104 | bitsetv_transitive_closure (bitsetv bsetv) |
105 | { |
106 | for (bitset_bindex i = 0; bsetv[i]; i++) |
107 | for (bitset_bindex j = 0; bsetv[j]; j++) |
108 | if (bitset_test (bsetv[j], i)) |
109 | bitset_or (bsetv[j], bsetv[j], bsetv[i]); |
110 | } |
111 | |
112 | |
113 | /* Given a vector BSETV of N bitsets of size N, modify its contents to |
114 | be the reflexive transitive closure of what was given. This is |
115 | the same as transitive closure but with all bits on the diagonal |
116 | of the bit matrix set. */ |
117 | void |
118 | bitsetv_reflexive_transitive_closure (bitsetv bsetv) |
119 | { |
120 | bitsetv_transitive_closure (bsetv); |
121 | for (bitset_bindex i = 0; bsetv[i]; i++) |
122 | bitset_set (bsetv[i], i); |
123 | } |
124 | |
125 | |
126 | /* Dump the contents of a bitset vector BSETV with N_VECS elements to |
127 | FILE. */ |
128 | void |
129 | bitsetv_dump (FILE *file, char const *title, char const *subtitle, |
130 | bitsetv bsetv) |
131 | { |
132 | fprintf (file, "%s\n" , title); |
133 | for (bitset_windex i = 0; bsetv[i]; i++) |
134 | { |
135 | fprintf (file, "%s %lu\n" , subtitle, (unsigned long) i); |
136 | bitset_dump (file, bsetv[i]); |
137 | } |
138 | |
139 | fprintf (file, "\n" ); |
140 | } |
141 | |
142 | |
143 | void |
144 | debug_bitsetv (bitsetv bsetv) |
145 | { |
146 | for (bitset_windex i = 0; bsetv[i]; i++) |
147 | { |
148 | fprintf (stderr, "%lu: " , (unsigned long) i); |
149 | debug_bitset (bsetv[i]); |
150 | } |
151 | |
152 | fprintf (stderr, "\n" ); |
153 | } |
154 | |
155 | |
156 | /*--------------------------------------------------------. |
157 | | Display the MATRIX array of SIZE bitsets of size SIZE. | |
158 | `--------------------------------------------------------*/ |
159 | |
160 | void |
161 | bitsetv_matrix_dump (FILE *out, const char *title, bitsetv bset) |
162 | { |
163 | bitset_bindex hsize = bitset_size (bset[0]); |
164 | |
165 | /* Title. */ |
166 | fprintf (out, "%s BEGIN\n" , title); |
167 | |
168 | /* Column numbers. */ |
169 | fputs (" " , out); |
170 | for (bitset_bindex i = 0; i < hsize; ++i) |
171 | putc (i / 10 ? '0' + i / 10 : ' ', out); |
172 | putc ('\n', out); |
173 | fputs (" " , out); |
174 | for (bitset_bindex i = 0; i < hsize; ++i) |
175 | fprintf (out, "%d" , (int) (i % 10)); |
176 | putc ('\n', out); |
177 | |
178 | /* Bar. */ |
179 | fputs (" ." , out); |
180 | for (bitset_bindex i = 0; i < hsize; ++i) |
181 | putc ('-', out); |
182 | fputs (".\n" , out); |
183 | |
184 | /* Contents. */ |
185 | for (bitset_bindex i = 0; bset[i]; ++i) |
186 | { |
187 | fprintf (out, "%2lu|" , (unsigned long) i); |
188 | for (bitset_bindex j = 0; j < hsize; ++j) |
189 | fputs (bitset_test (bset[i], j) ? "1" : " " , out); |
190 | fputs ("|\n" , out); |
191 | } |
192 | |
193 | /* Bar. */ |
194 | fputs (" `" , out); |
195 | for (bitset_bindex i = 0; i < hsize; ++i) |
196 | putc ('-', out); |
197 | fputs ("'\n" , out); |
198 | |
199 | /* End title. */ |
200 | fprintf (out, "%s END\n\n" , title); |
201 | } |
202 | |