lib/bitsetv.c

   1 /* Bitset vectors.
   2
   3    Copyright (C) 2001-2002, 2004-2006, 2009-2015, 2018-2019 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 #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 = xcalloc (1, 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   for (bitset_bindex i = 0; bsetv[i]; i++)
  75     BITSET_FREE_ (bsetv[i]);
  76   free (bsetv);
  77 }
  78
  79
  80 /* Zero a vector of bitsets.  */
  81 void
  82 bitsetv_zero (bitsetv bsetv)
  83 {
  84   for (bitset_bindex i = 0; bsetv[i]; i++)
  85     bitset_zero (bsetv[i]);
  86 }
  87
  88
  89 /* Set a vector of bitsets to ones.  */
  90 void
  91 bitsetv_ones (bitsetv bsetv)
  92 {
  93   for (bitset_bindex i = 0; bsetv[i]; i++)
  94     bitset_ones (bsetv[i]);
  95 }
  96
  97
  98 /* Given a vector BSETV of N bitsets of size N, modify its contents to
  99    be the transitive closure of what was given.  */
 100 void
 101 bitsetv_transitive_closure (bitsetv bsetv)
 102 {
 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]);
 107 }
 108
 109
 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.  */
 114 void
 115 bitsetv_reflexive_transitive_closure (bitsetv bsetv)
 116 {
 117   bitsetv_transitive_closure (bsetv);
 118   for (bitset_bindex i = 0; bsetv[i]; i++)
 119     bitset_set (bsetv[i], i);
 120 }
 121
 122
 123 /* Dump the contents of a bitset vector BSETV with N_VECS elements to
 124    FILE.  */
 125 void
 126 bitsetv_dump (FILE *file, char const *title, char const *subtitle,
 127               bitsetv bsetv)
 128 {
 129   fprintf (file, "%s\n", title);
 130   for (bitset_windex i = 0; bsetv[i]; i++)
 131     {
 132       fprintf (file, "%s %lu\n", subtitle, (unsigned long) i);
 133       bitset_dump (file, bsetv[i]);
 134     }
 135
 136   fprintf (file, "\n");
 137 }
 138
 139
 140 void
 141 debug_bitsetv (bitsetv bsetv)
 142 {
 143   for (bitset_windex i = 0; bsetv[i]; i++)
 144     {
 145       fprintf (stderr, "%lu: ", (unsigned long) i);
 146       debug_bitset (bsetv[i]);
 147     }
 148
 149   fprintf (stderr, "\n");
 150 }
 151
 152
 153 /*--------------------------------------------------------.
 154 | Display the MATRIX array of SIZE bitsets of size SIZE.  |
 155 `--------------------------------------------------------*/
 156
 157 void
 158 bitsetv_matrix_dump (FILE *out, const char *title, bitsetv bset)
 159 {
 160   bitset_bindex hsize = bitset_size (bset[0]);
 161
 162   /* Title. */
 163   fprintf (out, "%s BEGIN\n", title);
 164
 165   /* Column numbers. */
 166   fputs ("   ", out);
 167   for (bitset_bindex i = 0; i < hsize; ++i)
 168     putc (i / 10 ? '0' + i / 10 : ' ', out);
 169   putc ('\n', out);
 170   fputs ("   ", out);
 171   for (bitset_bindex i = 0; i < hsize; ++i)
 172     fprintf (out, "%d", (int) (i % 10));
 173   putc ('\n', out);
 174
 175   /* Bar. */
 176   fputs ("  .", out);
 177   for (bitset_bindex i = 0; i < hsize; ++i)
 178     putc ('-', out);
 179   fputs (".\n", out);
 180
 181   /* Contents. */
 182   for (bitset_bindex i = 0; bset[i]; ++i)
 183     {
 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);
 187       fputs ("|\n", out);
 188     }
 189
 190   /* Bar. */
 191   fputs ("  `", out);
 192   for (bitset_bindex i = 0; i < hsize; ++i)
 193     putc ('-', out);
 194   fputs ("'\n", out);
 195
 196   /* End title. */
 197   fprintf (out, "%s END\n\n", title);
 198 }