lib/bitsetv.c

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