(ebitset_size, ebitset_list, ebitset_list_reverse):

[bison.git] / lib / bitsetv.c

diff --git a/lib/bitsetv.c b/lib/bitsetv.c
index 7fd8226820883081622ad4a1affd6be8abfed35f..2c26549afcfded93841c5bce738a122def712edb 100644 (file)
--- a/lib/bitsetv.c
+++ b/lib/bitsetv.c
@@ -1,5 +1,5 @@
 /* Bitset vectors.
-   Copyright (C) 2001 Free Software Foundation, Inc.
+   Copyright (C) 2001, 2002 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -30,29 +30,36 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
    type TYPE.  */
 bitset *
 bitsetv_alloc (n_vecs, n_bits, type)
-    unsigned int n_vecs;
-    unsigned int n_bits;
-    enum bitset_type type;
+     bitset_bindex n_vecs;
+     bitset_bindex n_bits;
+     enum bitset_type type;
 {
-    unsigned int vector_bytes;
-    unsigned int bytes;
-    bitset *bsetv;
-    unsigned int i;
-
-    /* Determine number of bytes for each set.  */
-    bytes = bitset_bytes (type, n_bits);
-
-    /* Allocate vector table at head of bitset array.  */
-    vector_bytes = n_vecs * sizeof (bitset);
-    bsetv = (bitset *) xmalloc (vector_bytes + bytes * n_vecs);
-
-    for (i = 0; i < n_vecs; i++)
+  size_t vector_bytes;
+  size_t bytes;
+  bitset *bsetv;
+  bitset_bindex i;
+  
+  /* Determine number of bytes for each set.  */
+  bytes = bitset_bytes (type, n_bits);
+
+  /* If size calculation overflows, memory is exhausted.  */
+  if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs)
+    xalloc_die ();
+  
+  /* Allocate vector table at head of bitset array.  */
+  vector_bytes = (n_vecs + 1) * sizeof (bitset);
+  bsetv = (bitset *) xcalloc (1, vector_bytes + bytes * n_vecs);
+  
+  for (i = 0; i < n_vecs; i++)
     {
-      bsetv[i] = (bitset)((char *)bsetv + vector_bytes + i * bytes);
-
+      bsetv[i] = (bitset) ((char *) bsetv + vector_bytes + i * bytes);
+      
       bitset_init (bsetv[i], n_bits, type);
     }
-    return bsetv;
+  
+  /* Null terminate table.  */
+  bsetv[i] = 0;
+  return bsetv;
 }
 
 
@@ -60,69 +67,117 @@ bitsetv_alloc (n_vecs, n_bits, type)
    attribute hints specified by ATTR.  */
 bitset *
 bitsetv_create (n_vecs, n_bits, attr)
-    unsigned int n_vecs;
-    unsigned int n_bits;
-    unsigned int attr;
+     bitset_bindex n_vecs;
+     bitset_bindex n_bits;
+     unsigned int attr;
 {
-    enum bitset_type type;
-
-    type = bitset_type_choose (n_bits, attr);
-    return bitsetv_alloc (n_vecs, n_bits, type);
+  enum bitset_type type;
+  
+  type = bitset_type_choose (n_bits, attr);
+  return bitsetv_alloc (n_vecs, n_bits, type);
 }
 
 
 /* Free bitset vector BSETV.  */
 void
 bitsetv_free (bsetv)
-    bitset *bsetv;
+     bitset *bsetv;
 {
-    free (bsetv);
+  bitset_bindex i;
+
+  for (i = 0; bsetv[i]; i++)
+      BITSET_FREE_ (bsetv[i]);
+  free (bsetv);
 }
 
 
-/* Zero a vector of N_VECS bitsets.  */
+/* Zero a vector of bitsets.  */
 void
-bitsetv_zero (bsetv, n_vecs)
+bitsetv_zero (bsetv)
      struct bitset_struct **bsetv;
-     unsigned int n_vecs;
 {
-  unsigned int i;
+  bitset_bindex i;
+  
+  for (i = 0; bsetv[i]; i++)
+    bitset_zero (bsetv[i]);
+}
 
-  for (i = 0; i < n_vecs; i++)
-      bitset_zero (bsetv[i]);
+
+/* Set a vector of bitsets to ones.  */
+void
+bitsetv_ones (bsetv)
+     bitset *bsetv;
+{
+  bitset_bindex i;
+  
+  for (i = 0; bsetv[i]; i++)
+    bitset_ones (bsetv[i]);
 }
 
 
-/* Set a vector of N_VECS bitsets to ones.  */
+/* Given a vector BSETV of N bitsets of size N, modify its contents to
+   be the transitive closure of what was given.  */
 void
-bitsetv_ones (bsetv, n_vecs)
+bitsetv_transitive_closure (bsetv)
      bitset *bsetv;
-     unsigned int n_vecs;
 {
-  unsigned int i;
+  bitset_bindex i;
+  bitset_bindex j;
 
-  for (i = 0; i < n_vecs; i++)
-    bitset_ones (bsetv[i]);
+  for (i = 0; bsetv[i]; i++)
+    for (j = 0; bsetv[j]; j++)
+      if (bitset_test (bsetv[j], i))
+        bitset_or (bsetv[j], bsetv[j], bsetv[i]);
+}
+
+
+/* Given a vector BSETV of N bitsets of size N, modify its contents to
+   be the reflexive transitive closure of what was given.  This is 
+   the same as transitive closure but with all bits on the diagonal
+   of the bit matrix set.  */
+void
+bitsetv_reflexive_transitive_closure (bitsetv bsetv)
+{
+  bitset_bindex i;
+
+  bitsetv_transitive_closure (bsetv);
+  for (i = 0; bsetv[i]; i++)
+    bitset_set (bsetv[i], i);
 }
 
 
 /* Dump the contents of a bitset vector BSETV with N_VECS elements to
    FILE.  */
 void
-bitsetv_dump (file, title, subtitle, bsetv, n_vecs)
+bitsetv_dump (file, title, subtitle, bsetv)
      FILE *file;
      const char *title, *subtitle;
      bitset *bsetv;
-     unsigned int n_vecs;
 {
-  unsigned int i;
-
+  bitset_windex i;
+  
   fprintf (file, "%s\n", title);
-  for (i = 0; i < n_vecs; i++)
+  for (i = 0; bsetv[i]; i++)
     {
-      fprintf (file, "%s %d\n", subtitle, i);
+      fprintf (file, "%s %lu\n", subtitle, (unsigned long) i);
       bitset_dump (file, bsetv[i]);
     }
-
+  
   fprintf (file, "\n");
 }
+
+
+void
+debug_bitsetv (bsetv)
+     bitset *bsetv;
+{
+  bitset_windex i;
+  
+  for (i = 0; bsetv[i]; i++)
+    {
+      fprintf (stderr, "%lu: ", (unsigned long) i);
+      debug_bitset (bsetv[i]);
+    }
+  
+  fprintf (stderr, "\n");
+}