lib/bitsetv.c

   1 /* Bitset vectors.
   2    Copyright (C) 2001-2002, 2004-2006, 2009-2010 Free Software
   3    Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation, either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include "bitsetv.h"
  21
  22 #include <stdlib.h>
  23
  24
  25 /* Create a vector of N_VECS bitsets, each of N_BITS, and of
  26    type TYPE.  */
  27 bitset *
  28 bitsetv_alloc (bitset_bindex n_vecs, bitset_bindex n_bits,
  29                enum bitset_type type)
  30 {
  31   size_t vector_bytes;
  32   size_t bytes;
  33   bitset *bsetv;
  34   bitset_bindex i;
  35
  36   /* Determine number of bytes for each set.  */
  37   bytes = bitset_bytes (type, n_bits);
  38
  39   /* If size calculation overflows, memory is exhausted.  */
  40   if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs)
  41     xalloc_die ();
  42
  43   /* Allocate vector table at head of bitset array.  */
  44   vector_bytes = (n_vecs + 1) * sizeof (bitset) + bytes - 1;
  45   vector_bytes -= vector_bytes % bytes;
  46   bsetv = xcalloc (1, vector_bytes + bytes * n_vecs);
  47
  48   for (i = 0; i < n_vecs; i++)
  49     {
  50       bsetv[i] = (bitset) (void *) ((char *) bsetv + vector_bytes + i * bytes);
  51
  52       bitset_init (bsetv[i], n_bits, type);
  53     }
  54
  55   /* Null terminate table.  */
  56   bsetv[i] = 0;
  57   return bsetv;
  58 }
  59
  60
  61 /* Create a vector of N_VECS bitsets, each of N_BITS, and with
  62    attribute hints specified by ATTR.  */
  63 bitset *
  64 bitsetv_create (bitset_bindex n_vecs, bitset_bindex n_bits, unsigned int attr)
  65 {
  66   enum bitset_type type;
  67
  68   type = bitset_type_choose (n_bits, attr);
  69   return bitsetv_alloc (n_vecs, n_bits, type);
  70 }
  71
  72
  73 /* Free bitset vector BSETV.  */
  74 void
  75 bitsetv_free (bitsetv bsetv)
  76 {
  77   bitset_bindex i;
  78
  79   for (i = 0; bsetv[i]; i++)
  80       BITSET_FREE_ (bsetv[i]);
  81   free (bsetv);
  82 }
  83
  84
  85 /* Zero a vector of bitsets.  */
  86 void
  87 bitsetv_zero (bitsetv bsetv)
  88 {
  89   bitset_bindex i;
  90
  91   for (i = 0; bsetv[i]; i++)
  92     bitset_zero (bsetv[i]);
  93 }
  94
  95
  96 /* Set a vector of bitsets to ones.  */
  97 void
  98 bitsetv_ones (bitsetv bsetv)
  99 {
 100   bitset_bindex i;
 101
 102   for (i = 0; bsetv[i]; i++)
 103     bitset_ones (bsetv[i]);
 104 }
 105
 106
 107 /* Given a vector BSETV of N bitsets of size N, modify its contents to
 108    be the transitive closure of what was given.  */
 109 void
 110 bitsetv_transitive_closure (bitsetv bsetv)
 111 {
 112   bitset_bindex i;
 113   bitset_bindex j;
 114
 115   for (i = 0; bsetv[i]; i++)
 116     for (j = 0; bsetv[j]; j++)
 117       if (bitset_test (bsetv[j], i))
 118         bitset_or (bsetv[j], bsetv[j], bsetv[i]);
 119 }
 120
 121
 122 /* Given a vector BSETV of N bitsets of size N, modify its contents to
 123    be the reflexive transitive closure of what was given.  This is
 124    the same as transitive closure but with all bits on the diagonal
 125    of the bit matrix set.  */
 126 void
 127 bitsetv_reflexive_transitive_closure (bitsetv bsetv)
 128 {
 129   bitset_bindex i;
 130
 131   bitsetv_transitive_closure (bsetv);
 132   for (i = 0; bsetv[i]; i++)
 133     bitset_set (bsetv[i], i);
 134 }
 135
 136
 137 /* Dump the contents of a bitset vector BSETV with N_VECS elements to
 138    FILE.  */
 139 void
 140 bitsetv_dump (FILE *file, char const *title, char const *subtitle,
 141               bitsetv bsetv)
 142 {
 143   bitset_windex i;
 144
 145   fprintf (file, "%s\n", title);
 146   for (i = 0; bsetv[i]; i++)
 147     {
 148       fprintf (file, "%s %lu\n", subtitle, (unsigned long int) i);
 149       bitset_dump (file, bsetv[i]);
 150     }
 151
 152   fprintf (file, "\n");
 153 }
 154
 155
 156 void
 157 debug_bitsetv (bitsetv bsetv)
 158 {
 159   bitset_windex i;
 160
 161   for (i = 0; bsetv[i]; i++)
 162     {
 163       fprintf (stderr, "%lu: ", (unsigned long int) i);
 164       debug_bitset (bsetv[i]);
 165     }
 166
 167   fprintf (stderr, "\n");
 168 }