3 Copyright (C) 2001-2002, 2004-2006, 2009-2015, 2018-2019 Free Software
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.
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.
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/>. */
28 /* Create a vector of N_VECS bitsets, each of N_BITS, and of
31 bitsetv_alloc (bitset_bindex n_vecs
, bitset_bindex n_bits
,
32 enum bitset_type type
)
34 /* Determine number of bytes for each set. */
35 size_t bytes
= bitset_bytes (type
, n_bits
);
37 /* If size calculation overflows, memory is exhausted. */
38 if (BITSET_SIZE_MAX
/ (sizeof (bitset
) + bytes
) <= n_vecs
)
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
= xcalloc (1, vector_bytes
+ bytes
* n_vecs
);
47 for (i
= 0; i
< n_vecs
; i
++)
49 bsetv
[i
] = (bitset
) (void *) ((char *) bsetv
+ vector_bytes
+ i
* bytes
);
51 bitset_init (bsetv
[i
], n_bits
, type
);
54 /* Null terminate table. */
60 /* Create a vector of N_VECS bitsets, each of N_BITS, and with
61 attribute hints specified by ATTR. */
63 bitsetv_create (bitset_bindex n_vecs
, bitset_bindex n_bits
, unsigned attr
)
65 enum bitset_type type
= bitset_type_choose (n_bits
, attr
);
66 return bitsetv_alloc (n_vecs
, n_bits
, type
);
70 /* Free bitset vector BSETV. */
72 bitsetv_free (bitsetv bsetv
)
74 for (bitset_bindex i
= 0; bsetv
[i
]; i
++)
75 BITSET_FREE_ (bsetv
[i
]);
80 /* Zero a vector of bitsets. */
82 bitsetv_zero (bitsetv bsetv
)
84 for (bitset_bindex i
= 0; bsetv
[i
]; i
++)
85 bitset_zero (bsetv
[i
]);
89 /* Set a vector of bitsets to ones. */
91 bitsetv_ones (bitsetv bsetv
)
93 for (bitset_bindex i
= 0; bsetv
[i
]; i
++)
94 bitset_ones (bsetv
[i
]);
98 /* Given a vector BSETV of N bitsets of size N, modify its contents to
99 be the transitive closure of what was given. */
101 bitsetv_transitive_closure (bitsetv bsetv
)
103 for (bitset_bindex i
= 0; bsetv
[i
]; i
++)
104 for (bitset_bindex j
= 0; bsetv
[j
]; j
++)
105 if (bitset_test (bsetv
[j
], i
))
106 bitset_or (bsetv
[j
], bsetv
[j
], bsetv
[i
]);
110 /* Given a vector BSETV of N bitsets of size N, modify its contents to
111 be the reflexive transitive closure of what was given. This is
112 the same as transitive closure but with all bits on the diagonal
113 of the bit matrix set. */
115 bitsetv_reflexive_transitive_closure (bitsetv bsetv
)
117 bitsetv_transitive_closure (bsetv
);
118 for (bitset_bindex i
= 0; bsetv
[i
]; i
++)
119 bitset_set (bsetv
[i
], i
);
123 /* Dump the contents of a bitset vector BSETV with N_VECS elements to
126 bitsetv_dump (FILE *file
, char const *title
, char const *subtitle
,
129 fprintf (file
, "%s\n", title
);
130 for (bitset_windex i
= 0; bsetv
[i
]; i
++)
132 fprintf (file
, "%s %lu\n", subtitle
, (unsigned long) i
);
133 bitset_dump (file
, bsetv
[i
]);
136 fprintf (file
, "\n");
141 debug_bitsetv (bitsetv bsetv
)
143 for (bitset_windex i
= 0; bsetv
[i
]; i
++)
145 fprintf (stderr
, "%lu: ", (unsigned long) i
);
146 debug_bitset (bsetv
[i
]);
149 fprintf (stderr
, "\n");
153 /*--------------------------------------------------------.
154 | Display the MATRIX array of SIZE bitsets of size SIZE. |
155 `--------------------------------------------------------*/
158 bitsetv_matrix_dump (FILE *out
, const char *title
, bitsetv bset
)
160 bitset_bindex hsize
= bitset_size (bset
[0]);
163 fprintf (out
, "%s BEGIN\n", title
);
165 /* Column numbers. */
167 for (bitset_bindex i
= 0; i
< hsize
; ++i
)
168 putc (i
/ 10 ? '0' + i
/ 10 : ' ', out
);
171 for (bitset_bindex i
= 0; i
< hsize
; ++i
)
172 fprintf (out
, "%d", (int) (i
% 10));
177 for (bitset_bindex i
= 0; i
< hsize
; ++i
)
182 for (bitset_bindex i
= 0; bset
[i
]; ++i
)
184 fprintf (out
, "%2lu|", (unsigned long) i
);
185 for (bitset_bindex j
= 0; j
< hsize
; ++j
)
186 fputs (bitset_test (bset
[i
], j
) ? "1" : " ", out
);
192 for (bitset_bindex i
= 0; i
< hsize
; ++i
)
197 fprintf (out
, "%s END\n\n", title
);