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