1 /* Bitset vectors.
2
3 Copyright (C) 2001-2002, 2004-2006, 2009-2012 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
26 /* Create a vector of N_VECS bitsets, each of N_BITS, and of
27 type TYPE. */
28 bitset *
bitsetv_alloc(bitset_bindex n_vecs,bitset_bindex n_bits,enum bitset_type type)29 bitsetv_alloc (bitset_bindex n_vecs, bitset_bindex n_bits,
30 enum bitset_type type)
31 {
32 size_t vector_bytes;
33 size_t bytes;
34 bitset *bsetv;
35 bitset_bindex i;
36
37 /* Determine number of bytes for each set. */
38 bytes = bitset_bytes (type, n_bits);
39
40 /* If size calculation overflows, memory is exhausted. */
41 if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs)
42 xalloc_die ();
43
44 /* Allocate vector table at head of bitset array. */
45 vector_bytes = (n_vecs + 1) * sizeof (bitset) + bytes - 1;
46 vector_bytes -= vector_bytes % bytes;
47 bsetv = xcalloc (1, vector_bytes + bytes * n_vecs);
48
49 for (i = 0; i < n_vecs; i++)
50 {
51 bsetv[i] = (bitset) (void *) ((char *) bsetv + vector_bytes + i * bytes);
52
53 bitset_init (bsetv[i], n_bits, type);
54 }
55
56 /* Null terminate table. */
57 bsetv[i] = 0;
58 return bsetv;
59 }
60
61
62 /* Create a vector of N_VECS bitsets, each of N_BITS, and with
63 attribute hints specified by ATTR. */
64 bitset *
bitsetv_create(bitset_bindex n_vecs,bitset_bindex n_bits,unsigned int attr)65 bitsetv_create (bitset_bindex n_vecs, bitset_bindex n_bits, unsigned int attr)
66 {
67 enum bitset_type type;
68
69 type = bitset_type_choose (n_bits, attr);
70 return bitsetv_alloc (n_vecs, n_bits, type);
71 }
72
73
74 /* Free bitset vector BSETV. */
75 void
bitsetv_free(bitsetv bsetv)76 bitsetv_free (bitsetv bsetv)
77 {
78 bitset_bindex i;
79
80 for (i = 0; bsetv[i]; i++)
81 BITSET_FREE_ (bsetv[i]);
82 free (bsetv);
83 }
84
85
86 /* Zero a vector of bitsets. */
87 void
bitsetv_zero(bitsetv bsetv)88 bitsetv_zero (bitsetv bsetv)
89 {
90 bitset_bindex i;
91
92 for (i = 0; bsetv[i]; i++)
93 bitset_zero (bsetv[i]);
94 }
95
96
97 /* Set a vector of bitsets to ones. */
98 void
bitsetv_ones(bitsetv bsetv)99 bitsetv_ones (bitsetv bsetv)
100 {
101 bitset_bindex i;
102
103 for (i = 0; bsetv[i]; i++)
104 bitset_ones (bsetv[i]);
105 }
106
107
108 /* Given a vector BSETV of N bitsets of size N, modify its contents to
109 be the transitive closure of what was given. */
110 void
bitsetv_transitive_closure(bitsetv bsetv)111 bitsetv_transitive_closure (bitsetv bsetv)
112 {
113 bitset_bindex i;
114 bitset_bindex j;
115
116 for (i = 0; bsetv[i]; i++)
117 for (j = 0; bsetv[j]; j++)
118 if (bitset_test (bsetv[j], i))
119 bitset_or (bsetv[j], bsetv[j], bsetv[i]);
120 }
121
122
123 /* Given a vector BSETV of N bitsets of size N, modify its contents to
124 be the reflexive transitive closure of what was given. This is
125 the same as transitive closure but with all bits on the diagonal
126 of the bit matrix set. */
127 void
bitsetv_reflexive_transitive_closure(bitsetv bsetv)128 bitsetv_reflexive_transitive_closure (bitsetv bsetv)
129 {
130 bitset_bindex i;
131
132 bitsetv_transitive_closure (bsetv);
133 for (i = 0; bsetv[i]; i++)
134 bitset_set (bsetv[i], i);
135 }
136
137
138 /* Dump the contents of a bitset vector BSETV with N_VECS elements to
139 FILE. */
140 void
bitsetv_dump(FILE * file,char const * title,char const * subtitle,bitsetv bsetv)141 bitsetv_dump (FILE *file, char const *title, char const *subtitle,
142 bitsetv bsetv)
143 {
144 bitset_windex i;
145
146 fprintf (file, "%s\n", title);
147 for (i = 0; bsetv[i]; i++)
148 {
149 fprintf (file, "%s %lu\n", subtitle, (unsigned long int) i);
150 bitset_dump (file, bsetv[i]);
151 }
152
153 fprintf (file, "\n");
154 }
155
156
157 void
debug_bitsetv(bitsetv bsetv)158 debug_bitsetv (bitsetv bsetv)
159 {
160 bitset_windex i;
161
162 for (i = 0; bsetv[i]; i++)
163 {
164 fprintf (stderr, "%lu: ", (unsigned long int) i);
165 debug_bitset (bsetv[i]);
166 }
167
168 fprintf (stderr, "\n");
169 }
170