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.  */
28bitset *
29bitsetv_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.  */
64bitset *
65bitsetv_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.  */
75void
76bitsetv_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.  */
87void
88bitsetv_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.  */
98void
99bitsetv_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.  */
110void
111bitsetv_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.  */
127void
128bitsetv_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.  */
140void
141bitsetv_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
157void
158debug_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