lib/bitsetv.c

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