Import of 2003-06-08 libbitset <http://mail.gnu.org/archive/html/bison-patches/2003...

diff --git a/lib/abitset.c b/lib/abitset.c
index 99c1c2f107d76a822926ed1aa0c17595da2440c2..0fe1b47bbbaee8cee7ceef3ff6238047ef0d018d 100644 (file)
--- a/lib/abitset.c
+++ b/lib/abitset.c
@@ -31,16 +31,18 @@
 
 #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
 #define ABITSET_WORDS(X) ((X)->a.words)
 
 #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
 #define ABITSET_WORDS(X) ((X)->a.words)

-#define ABITSET_N_BITS(X) ((X)->a.n_bits)

 
 
 
 

-/* Return size in bits of bitset SRC.  */

 static bitset_bindex
 static bitset_bindex

-abitset_size (bitset src)
+abitset_resize (bitset src ATTRIBUTE_UNUSED,
+               bitset_bindex size ATTRIBUTE_UNUSED)

 {
 {

-  return ABITSET_N_BITS (src);
-}
+    if (BITSET_SIZE_ (src) == size)
+       return size;

 
 

+    /* These bitsets have a fixed size.  */
+    abort ();
+}

 
 /* Find list of up to NUM bits set in BSET starting from and including
  *NEXT and store in array LIST.  Return with actual number of bits
 
 /* Find list of up to NUM bits set in BSET starting from and including
  *NEXT and store in array LIST.  Return with actual number of bits


@@ -60,7 +62,7 @@ abitset_small_list (bitset src, bitset_bindex *list,
   if (!word)
     return 0;
 
   if (!word)
     return 0;
 

-  size = ABITSET_N_BITS (src);
+  size = BITSET_SIZE_ (src);

   bitno = *next;
   if (bitno >= size)
     return 0;
   bitno = *next;
   if (bitno >= size)
     return 0;


@@ -105,8 +107,9 @@ abitset_small_list (bitset src, bitset_bindex *list,
 static void
 abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
 {
 static void
 abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
 {

-  /* This should never occur for abitsets since we should always
-     hit the cache.  */
+  /* This should never occur for abitsets since we should always hit
+     the cache.  It is likely someone is trying to access outside the
+     bounds of the bitset.  */

   abort ();
 }
 
   abort ();
 }
 


@@ -116,9 +119,9 @@ static void
 abitset_reset (bitset dst ATTRIBUTE_UNUSED,
               bitset_bindex bitno ATTRIBUTE_UNUSED)
 {
 abitset_reset (bitset dst ATTRIBUTE_UNUSED,
               bitset_bindex bitno ATTRIBUTE_UNUSED)
 {

-  /* This should never occur for abitsets since we should always
-     hit the cache.  */
-  abort ();
+  /* This should never occur for abitsets since we should always hit
+     the cache.  It is likely someone is trying to access outside the
+     bounds of the bitset.  Since the bit is zero anyway, let it pass.  */

 }
 
 
 }
 
 


@@ -129,7 +132,6 @@ abitset_test (bitset src ATTRIBUTE_UNUSED,
 {
   /* This should never occur for abitsets since we should always
      hit the cache.  */
 {
   /* This should never occur for abitsets since we should always
      hit the cache.  */

-  abort ();

   return false;
 }
 
   return false;
 }
 


@@ -149,7 +151,7 @@ abitset_list_reverse (bitset src, bitset_bindex *list,
   unsigned int bitcnt;
   bitset_bindex bitoff;
   bitset_word *srcp = ABITSET_WORDS (src);
   unsigned int bitcnt;
   bitset_bindex bitoff;
   bitset_word *srcp = ABITSET_WORDS (src);

-  bitset_bindex n_bits = ABITSET_N_BITS (src);
+  bitset_bindex n_bits = BITSET_SIZE_ (src);

 
   rbitno = *next;
 
 
   rbitno = *next;
 


@@ -228,7 +230,7 @@ abitset_list (bitset src, bitset_bindex *list,
     }
   else
     {
     }
   else
     {

-      if (bitno >= ABITSET_N_BITS (src))
+      if (bitno >= BITSET_SIZE_ (src))

        return 0;
 
       windex = bitno / BITSET_WORD_BITS;
        return 0;
 
       windex = bitno / BITSET_WORD_BITS;


@@ -304,7 +306,7 @@ abitset_unused_clear (bitset dst)
 {
   unsigned int last_bit;
 
 {
   unsigned int last_bit;
 

-  last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS;
+  last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;

   if (last_bit)
     ABITSET_WORDS (dst)[dst->b.csize - 1] &=
       ((bitset_word) 1 << last_bit) - 1;
   if (last_bit)
     ABITSET_WORDS (dst)[dst->b.csize - 1] &=
       ((bitset_word) 1 << last_bit) - 1;


@@ -711,7 +713,8 @@ struct bitset_vtable abitset_small_vtable = {
   abitset_reset,
   bitset_toggle_,
   abitset_test,
   abitset_reset,
   bitset_toggle_,
   abitset_test,

-  abitset_size,
+  abitset_resize,
+  bitset_size_,

   bitset_count_,
   abitset_empty_p,
   abitset_ones,
   bitset_count_,
   abitset_empty_p,
   abitset_ones,


@@ -748,7 +751,8 @@ struct bitset_vtable abitset_vtable = {
   abitset_reset,
   bitset_toggle_,
   abitset_test,
   abitset_reset,
   bitset_toggle_,
   abitset_test,

-  abitset_size,
+  abitset_resize,
+  bitset_size_,

   bitset_count_,
   abitset_empty_p,
   abitset_ones,
   bitset_count_,
   abitset_empty_p,
   abitset_ones,


@@ -809,7 +813,7 @@ abitset_init (bitset bset, bitset_bindex n_bits)
   bitset_windex size;
 
   size = ABITSET_N_WORDS (n_bits);
   bitset_windex size;
 
   size = ABITSET_N_WORDS (n_bits);

-  ABITSET_N_BITS (bset) = n_bits;
+  BITSET_NBITS_ (bset) = n_bits;

 
   /* Use optimized routines if bitset fits within a single word.
      There is probably little merit if using caching since
 
   /* Use optimized routines if bitset fits within a single word.
      There is probably little merit if using caching since

diff --git a/lib/bitset.c b/lib/bitset.c
index a500d471015416177d2d059c0c612afe74541257..3c0d956eaa7951d4a065cb5b93b22c62e7a27028 100644 (file)
--- a/lib/bitset.c
+++ b/lib/bitset.c
@@ -21,10 +21,12 @@
 #endif
 
 #include <stdlib.h>
 #endif
 
 #include <stdlib.h>

+#include <string.h>

 #include "bitset.h"
 #include "abitset.h"
 #include "lbitset.h"
 #include "ebitset.h"
 #include "bitset.h"
 #include "abitset.h"
 #include "lbitset.h"
 #include "ebitset.h"

+#include "vbitset.h"

 #include "bitset_stats.h"
 #include "obstack.h"
 
 #include "bitset_stats.h"
 #include "obstack.h"
 


@@ -55,6 +57,10 @@ bitset_bytes (enum bitset_type type, bitset_bindex n_bits)
       bytes = ebitset_bytes (n_bits);
       break;
 
       bytes = ebitset_bytes (n_bits);
       break;
 

+    case BITSET_VARRAY:
+      bytes = vbitset_bytes (n_bits);
+      break;
+

     default:
       abort ();
     }
     default:
       abort ();
     }


@@ -81,6 +87,9 @@ bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
     case BITSET_TABLE:
       return ebitset_init (bset, n_bits);
 
     case BITSET_TABLE:
       return ebitset_init (bset, n_bits);
 

+    case BITSET_VARRAY:
+      return vbitset_init (bset, n_bits);
+

     default:
       abort ();
     }
     default:
       abort ();
     }


@@ -93,27 +102,30 @@ bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
 enum bitset_type
 bitset_type_choose (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned int attr)
 {
 enum bitset_type
 bitset_type_choose (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned int attr)
 {

-  enum bitset_type type;
-

   /* Check attributes.  */
   if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
     abort ();
   if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
     abort ();
 
   /* Check attributes.  */
   if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
     abort ();
   if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
     abort ();
 

-  /* Choose the type of bitset. Note that sometimes we will be asked
+  /* Choose the type of bitset.  Note that sometimes we will be asked

   for a zero length fixed size bitset.  */
 
   for a zero length fixed size bitset.  */
 

-  type = BITSET_ARRAY;
-  /* Currently, the simple bitsets do not support a variable size.  */
-  if (attr & BITSET_VARIABLE || attr & BITSET_SPARSE)
-    {
-      type = BITSET_LIST;
-      if (attr & BITSET_DENSE || attr & BITSET_GREEDY)
-       type = BITSET_TABLE;
-    }
+  
+  /* If no attributes selected, choose a good compromise.  */
+  if (!attr)
+    return BITSET_VARRAY;
+
+  if (attr & BITSET_SPARSE)
+    return BITSET_LIST;
+
+  if (attr & BITSET_FIXED)
+    return BITSET_ARRAY;

 
 

-  return type;
+  if (attr & BITSET_GREEDY)
+    return BITSET_TABLE;
+
+  return BITSET_VARRAY;

 }
 
 
 }
 
 


@@ -223,6 +235,14 @@ bitset_next (bitset src, bitset_bindex bitno)
 }
 
 
 }
 
 

+/* Return true if both bitsets are of the same type and size.  */
+extern bool
+bitset_compatible_p (bitset bset1, bitset bset2)
+{
+    return BITSET_COMPATIBLE_ (bset1, bset2);
+}
+
+

 /* Find previous bit set in SRC starting from and including BITNO.
    Return BITSET_BINDEX_MAX if SRC empty.  */
 bitset_bindex
 /* Find previous bit set in SRC starting from and including BITNO.
    Return BITSET_BINDEX_MAX if SRC empty.  */
 bitset_bindex


@@ -304,7 +324,6 @@ bitset_dump (FILE *file, bitset bset)
 }
 
 
 }
 
 

-

 /* Release memory associated with bitsets.  */
 void
 bitset_release_memory (void)
 /* Release memory associated with bitsets.  */
 void
 bitset_release_memory (void)


@@ -314,7 +333,6 @@ bitset_release_memory (void)
 }
 
 
 }
 
 

-

 /* Toggle bit BITNO in bitset BSET and the new value of the bit.  */
 bool
 bitset_toggle_ (bitset bset, bitset_bindex bitno)
 /* Toggle bit BITNO in bitset BSET and the new value of the bit.  */
 bool
 bitset_toggle_ (bitset bset, bitset_bindex bitno)


@@ -334,6 +352,14 @@ bitset_toggle_ (bitset bset, bitset_bindex bitno)
 }
 
 
 }
 
 

+/* Return number of bits in bitset SRC.  */
+bitset_bindex
+bitset_size_ (bitset src)
+{
+    return BITSET_NBITS_ (src);
+}
+
+

 /* Return number of bits set in bitset SRC.  */
 bitset_bindex
 bitset_count_ (bitset src)
 /* Return number of bits set in bitset SRC.  */
 bitset_bindex
 bitset_count_ (bitset src)

diff --git a/lib/bitset_stats.c b/lib/bitset_stats.c
index c504a61659dfb6015a33f6f2417574216c4fd666..e1692d88e9dbf9a3ec1bb4ec0c9314764c7b6785 100644 (file)
--- a/lib/bitset_stats.c
+++ b/lib/bitset_stats.c
@@ -1,5 +1,5 @@
 /* Bitset statistics.
 /* Bitset statistics.

-   Copyright (C) 2002, 2003 Free Software Foundation, Inc.
+   Copyright (C) 2002 Free Software Foundation, Inc.

    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
 
    This program is free software; you can redistribute it and/or modify
    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
 
    This program is free software; you can redistribute it and/or modify


@@ -33,13 +33,18 @@
 #include "abitset.h"
 #include "ebitset.h"
 #include "lbitset.h"
 #include "abitset.h"
 #include "ebitset.h"
 #include "lbitset.h"

+#include "vbitset.h"

 #include "bitset_stats.h"
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
 
 #include "bitset_stats.h"
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
 

+#ifdef HAVE_GETTEXT_H

 #include "gettext.h"
 #define _(Msgid)  gettext (Msgid)
 #include "gettext.h"
 #define _(Msgid)  gettext (Msgid)

+#else
+#define _(Msgid)  Msgid
+#endif

 
 /* Configuration macros.  */
 #define BITSET_STATS_FILE "bitset.dat"
 
 /* Configuration macros.  */
 #define BITSET_STATS_FILE "bitset.dat"


@@ -375,6 +380,13 @@ bitset_stats_test (bitset src, bitset_bindex bitno)
 }
 
 
 }
 
 

+static bitset_bindex
+bitset_stats_resize (bitset src, bitset_bindex size)
+{
+    return BITSET_RESIZE_ (src->s.bset, size);
+}
+
+

 static bitset_bindex
 bitset_stats_size (bitset src)
 {
 static bitset_bindex
 bitset_stats_size (bitset src)
 {


@@ -518,7 +530,6 @@ static void
 bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);
 bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);

-

   BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 
   BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 


@@ -527,7 +538,6 @@ static bool
 bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);
 bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);

-

   return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 
   return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 


@@ -536,7 +546,6 @@ static void
 bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);
 bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);

-

   BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 
   BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 


@@ -545,7 +554,6 @@ static bool
 bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);
 bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);

-

   return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 
   return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 


@@ -554,7 +562,6 @@ static void
 bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);
 bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);

-

   BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 
   BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 


@@ -563,7 +570,6 @@ static bool
 bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);
 bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 {
   BITSET_CHECK4_ (dst, src1, src2, src3);

-

   return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 
   return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
 }
 


@@ -576,9 +582,11 @@ bitset_stats_list (bitset bset, bitset_bindex *list,
   bitset_bindex tmp;
   bitset_bindex size;
   bitset_bindex i;
   bitset_bindex tmp;
   bitset_bindex size;
   bitset_bindex i;

+  enum bitset_type type;

 
   count = BITSET_LIST_ (bset->s.bset, list, num, next);
 
 
   count = BITSET_LIST_ (bset->s.bset, list, num, next);
 

+  type = BITSET_TYPE_ (bset->s.bset);

   BITSET_STATS_LISTS_INC (bset->s.bset);
 
   /* Log histogram of number of set bits.  */
   BITSET_STATS_LISTS_INC (bset->s.bset);
 
   /* Log histogram of number of set bits.  */


@@ -626,6 +634,7 @@ struct bitset_vtable bitset_stats_vtable = {
   bitset_stats_reset,
   bitset_stats_toggle,
   bitset_stats_test,
   bitset_stats_reset,
   bitset_stats_toggle,
   bitset_stats_test,

+  bitset_stats_resize,

   bitset_stats_size,
   bitset_stats_count,
   bitset_stats_empty_p,
   bitset_stats_size,
   bitset_stats_count,
   bitset_stats_empty_p,


@@ -685,6 +694,8 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
   bset->b.csize = 0;
   bset->b.cdata = 0;
 
   bset->b.csize = 0;
   bset->b.cdata = 0;
 

+  BITSET_NBITS_ (bset) = n_bits;
+

   /* Set up the actual bitset implementation that
      we are a wrapper over.  */
   switch (type)
   /* Set up the actual bitset implementation that
      we are a wrapper over.  */
   switch (type)


@@ -707,6 +718,12 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
       ebitset_init (sbset, n_bits);
       break;
 
       ebitset_init (sbset, n_bits);
       break;
 

+    case BITSET_VARRAY:
+      bytes = vbitset_bytes (n_bits);
+      sbset = (bitset) xcalloc (1, bytes);
+      vbitset_init (sbset, n_bits);
+      break;
+

     default:
       abort ();
     }
     default:
       abort ();
     }