lib/bitsetv.c

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