Home | History | Annotate | Download | only in lib 
      1 /* Bitset vectors.
      2 
      3    Copyright (C) 2001-2002, 2004-2006, 2009-2012 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 }
    170