1 /* Bitset vectors.
2
3 Copyright (C) 2001-2002, 2004-2006, 2009-2015, 2018-2021 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 <https://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 }