lib/bitsetv.c

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