lib/bitsetv.c

   1 /* Bitset vectors.
   2
   3    Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009, 2010 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   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.  */
  64 bitset *
  65 bitsetv_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.  */
  75 void
  76 bitsetv_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.  */
  87 void
  88 bitsetv_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.  */
  98 void
  99 bitsetv_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.  */
 110 void
 111 bitsetv_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.  */
 127 void
 128 bitsetv_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.  */
 140 void
 141 bitsetv_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
 157 void
 158 debug_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 }