lib/bitsetv.c

   1 /* Bitset vectors.
   2    Copyright (C) 2001, 2002 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, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, 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 (n_vecs, n_bits, type)
  33      bitset_bindex n_vecs;
  34      bitset_bindex n_bits;
  35      enum bitset_type type;
  36 {
  37   size_t vector_bytes;
  38   size_t bytes;
  39   bitset *bsetv;
  40   bitset_bindex i;
  41
  42   /* Determine number of bytes for each set.  */
  43   bytes = bitset_bytes (type, n_bits);
  44
  45   /* If size calculation overflows, memory is exhausted.  */
  46   if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs)
  47     xalloc_die ();
  48
  49   /* Allocate vector table at head of bitset array.  */
  50   vector_bytes = (n_vecs + 1) * sizeof (bitset);
  51   bsetv = (bitset *) xcalloc (1, vector_bytes + bytes * n_vecs);
  52
  53   for (i = 0; i < n_vecs; i++)
  54     {
  55       bsetv[i] = (bitset) ((char *) bsetv + vector_bytes + i * bytes);
  56
  57       bitset_init (bsetv[i], n_bits, type);
  58     }
  59
  60   /* Null terminate table.  */
  61   bsetv[i] = 0;
  62   return bsetv;
  63 }
  64
  65
  66 /* Create a vector of N_VECS bitsets, each of N_BITS, and with
  67    attribute hints specified by ATTR.  */
  68 bitset *
  69 bitsetv_create (n_vecs, n_bits, attr)
  70      bitset_bindex n_vecs;
  71      bitset_bindex n_bits;
  72      unsigned int attr;
  73 {
  74   enum bitset_type type;
  75
  76   type = bitset_type_choose (n_bits, attr);
  77   return bitsetv_alloc (n_vecs, n_bits, type);
  78 }
  79
  80
  81 /* Free bitset vector BSETV.  */
  82 void
  83 bitsetv_free (bsetv)
  84      bitset *bsetv;
  85 {
  86   bitset_bindex i;
  87
  88   for (i = 0; bsetv[i]; i++)
  89       BITSET_FREE_ (bsetv[i]);
  90   free (bsetv);
  91 }
  92
  93
  94 /* Zero a vector of bitsets.  */
  95 void
  96 bitsetv_zero (bsetv)
  97      struct bitset_struct **bsetv;
  98 {
  99   bitset_bindex i;
 100
 101   for (i = 0; bsetv[i]; i++)
 102     bitset_zero (bsetv[i]);
 103 }
 104
 105
 106 /* Set a vector of bitsets to ones.  */
 107 void
 108 bitsetv_ones (bsetv)
 109      bitset *bsetv;
 110 {
 111   bitset_bindex i;
 112
 113   for (i = 0; bsetv[i]; i++)
 114     bitset_ones (bsetv[i]);
 115 }
 116
 117
 118 /* Given a vector BSETV of N bitsets of size N, modify its contents to
 119    be the transitive closure of what was given.  */
 120 void
 121 bitsetv_transitive_closure (bsetv)
 122      bitset *bsetv;
 123 {
 124   bitset_bindex i;
 125   bitset_bindex j;
 126
 127   for (i = 0; bsetv[i]; i++)
 128     for (j = 0; bsetv[j]; j++)
 129       if (bitset_test (bsetv[j], i))
 130         bitset_or (bsetv[j], bsetv[j], bsetv[i]);
 131 }
 132
 133
 134 /* Given a vector BSETV of N bitsets of size N, modify its contents to
 135    be the reflexive transitive closure of what was given.  This is
 136    the same as transitive closure but with all bits on the diagonal
 137    of the bit matrix set.  */
 138 void
 139 bitsetv_reflexive_transitive_closure (bitsetv bsetv)
 140 {
 141   bitset_bindex i;
 142
 143   bitsetv_transitive_closure (bsetv);
 144   for (i = 0; bsetv[i]; i++)
 145     bitset_set (bsetv[i], i);
 146 }
 147
 148
 149 /* Dump the contents of a bitset vector BSETV with N_VECS elements to
 150    FILE.  */
 151 void
 152 bitsetv_dump (file, title, subtitle, bsetv)
 153      FILE *file;
 154      const char *title, *subtitle;
 155      bitset *bsetv;
 156 {
 157   bitset_windex i;
 158
 159   fprintf (file, "%s\n", title);
 160   for (i = 0; bsetv[i]; i++)
 161     {
 162       fprintf (file, "%s %lu\n", subtitle, (unsigned long) i);
 163       bitset_dump (file, bsetv[i]);
 164     }
 165
 166   fprintf (file, "\n");
 167 }
 168
 169
 170 void
 171 debug_bitsetv (bsetv)
 172      bitset *bsetv;
 173 {
 174   bitset_windex i;
 175
 176   for (i = 0; bsetv[i]; i++)
 177     {
 178       fprintf (stderr, "%lu: ", (unsigned long) i);
 179       debug_bitset (bsetv[i]);
 180     }
 181
 182   fprintf (stderr, "\n");
 183 }