Merge remote-tracking branch 'origin/maint'

[bison.git] / lib / ebitset.c

diff --git a/lib/ebitset.c b/lib/ebitset.c
index 3fea4afd28eb607e4347a27a64dc0f5d2baf2f54..77cc7a0148ec75baa1ce74b77ef961ebb9dc2f71 100644 (file)
--- a/lib/ebitset.c
+++ b/lib/ebitset.c
@@ -1,10 +1,12 @@
 /* Functions to support expandable bitsets.
 /* Functions to support expandable bitsets.

-   Copyright (C) 2002 Free Software Foundation, Inc.
+
+   Copyright (C) 2002-2006, 2009-2012 Free Software Foundation, Inc.
+

    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
 
    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
 

-   This program is free software; you can redistribute it and/or modify
+   This program is free software: you can redistribute it and/or modify

    it under the terms of the GNU General Public License as published by
    it under the terms of the GNU General Public License as published by

-   the Free Software Foundation; either version 2 of the License, or
+   the Free Software Foundation, either version 3 of the License, or

    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,


@@ -13,17 +15,15 @@
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License

-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 
-*/
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

 
 

-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
+#include <config.h>

 
 #include "ebitset.h"
 
 #include "ebitset.h"

+

 #include "obstack.h"
 #include <stdlib.h>
 #include "obstack.h"
 #include <stdlib.h>

+#include <string.h>

 
 /* This file implements expandable bitsets.  These bitsets can be of
    arbitrary length and are more efficient than arrays of bits for
 
 /* This file implements expandable bitsets.  These bitsets can be of
    arbitrary length and are more efficient than arrays of bits for


@@ -37,12 +37,12 @@
    Bitsets are commonly empty so we need to ensure that this special
    case is fast.  A zero bitset is indicated when cdata is 0.  This is
    conservative since cdata may be non zero and the bitset may still
    Bitsets are commonly empty so we need to ensure that this special
    case is fast.  A zero bitset is indicated when cdata is 0.  This is
    conservative since cdata may be non zero and the bitset may still

-   be zero. 
+   be zero.

 
    The bitset cache can be disabled either by setting cindex to
 
    The bitset cache can be disabled either by setting cindex to

-   BITSET_WINDEX_MAX or by setting csize to 0.  Here 
+   BITSET_WINDEX_MAX or by setting csize to 0.  Here

    we use the former approach since cindex needs to be updated whenever
    we use the former approach since cindex needs to be updated whenever

-   cdata is changed.   
+   cdata is changed.

 */
 
 
 */
 
 


@@ -51,14 +51,14 @@
 
 /* Number of bits stored in each element.  */
 #define EBITSET_ELT_BITS \
 
 /* Number of bits stored in each element.  */
 #define EBITSET_ELT_BITS \

-  ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
+  ((unsigned int) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))

 
 /* Ebitset element.  We use an array of bits.  */
 typedef struct ebitset_elt_struct
 {
   union
   {
 
 /* Ebitset element.  We use an array of bits.  */
 typedef struct ebitset_elt_struct
 {
   union
   {

-    bitset_word words[EBITSET_ELT_WORDS];      /* Bits that are set.  */
+    bitset_word words[EBITSET_ELT_WORDS];       /* Bits that are set.  */

     struct ebitset_elt_struct *next;
   }
   u;
     struct ebitset_elt_struct *next;
   }
   u;


@@ -68,17 +68,6 @@ ebitset_elt;
 
 typedef ebitset_elt *ebitset_elts;
 
 
 typedef ebitset_elt *ebitset_elts;
 

-/* Head of ebitset linked list.  */
-typedef struct ebitset_struct
-{
-  bitset_windex size;          /* Number of elements.  */
-  ebitset_elts *elts;          /* Expanding array of pointers to elements.  */
-}
-*ebitset;
-
-
-typedef void(*PFV)();
-

 
 /* Number of elements to initially allocate.  */
 
 
 /* Number of elements to initially allocate.  */
 


@@ -86,17 +75,6 @@ typedef void(*PFV)();
 #define EBITSET_INITIAL_SIZE 2
 #endif
 
 #define EBITSET_INITIAL_SIZE 2
 #endif
 

-/* Minimum number of elements to grow table.  */
-
-#ifndef EBITSET_GROW_SIZE
-#define EBITSET_GROW_SIZE 4
-#endif
-
-struct bitset_struct
-{
-  struct bbitset_struct b;
-  struct ebitset_struct e;
-};

 
 enum ebitset_find_mode
   { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
 
 enum ebitset_find_mode
   { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };


@@ -105,45 +83,13 @@ static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits.  */
 
 /* Obstack to allocate bitset elements from.  */
 static struct obstack ebitset_obstack;
 
 /* Obstack to allocate bitset elements from.  */
 static struct obstack ebitset_obstack;

-static int ebitset_obstack_init = 0;
-static ebitset_elt *ebitset_free_list; /* Free list of bitset elements.  */
-
-static void ebitset_elts_grow PARAMS ((bitset, bitset_windex));
-static ebitset_elt *ebitset_elt_alloc PARAMS ((void));
-static ebitset_elt *ebitset_elt_calloc PARAMS ((void));
-static void ebitset_elt_add PARAMS ((bitset, ebitset_elt *, bitset_windex));
-static void ebitset_elt_remove PARAMS ((bitset, bitset_windex));
-static void ebitset_elt_free PARAMS ((ebitset_elt *));
-static ebitset_elt *ebitset_elt_find PARAMS ((bitset, bitset_windex,
-                                             enum ebitset_find_mode));
-static ebitset_elt *ebitset_elt_last PARAMS ((bitset));
-static int ebitset_elt_zero_p PARAMS ((ebitset_elt *));
-
-static bitset_windex ebitset_weed PARAMS ((bitset));
-static void ebitset_zero PARAMS ((bitset));
-static void ebitset_copy_ PARAMS ((bitset, bitset));
-static int ebitset_copy_cmp PARAMS ((bitset, bitset));
-static void ebitset_set PARAMS ((bitset, bitset_bindex));
-static void ebitset_reset PARAMS ((bitset, bitset_bindex));
-static int ebitset_test PARAMS ((bitset, bitset_bindex));
-static bitset_bindex ebitset_size PARAMS ((bitset));
-static int ebitset_disjoint_p PARAMS ((bitset, bitset));
-static int ebitset_equal_p PARAMS ((bitset, bitset));
-static void ebitset_not PARAMS ((bitset, bitset));
-static int ebitset_subset_p PARAMS ((bitset, bitset));
-static int ebitset_op3_cmp PARAMS ((bitset, bitset, bitset, enum bitset_ops));
-static int ebitset_and_cmp PARAMS ((bitset, bitset, bitset));
-static int ebitset_andn_cmp PARAMS ((bitset, bitset, bitset));
-static int ebitset_or_cmp PARAMS ((bitset, bitset, bitset));
-static int ebitset_xor_cmp PARAMS ((bitset, bitset, bitset));
-static bitset_bindex ebitset_list PARAMS ((bitset, bitset_bindex *,
-                                          bitset_bindex, bitset_bindex *));
-static bitset_bindex ebitset_list_reverse
-PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
-static void ebitset_free PARAMS ((bitset));
+static bool ebitset_obstack_init = false;
+static ebitset_elt *ebitset_free_list;  /* Free list of bitset elements.  */

 
 

+#define EBITSET_N_ELTS(N) (((N) + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS)

 #define EBITSET_ELTS(BSET) ((BSET)->e.elts)
 #define EBITSET_ELTS(BSET) ((BSET)->e.elts)

-#define EBITSET_SIZE(BSET) ((BSET)->e.size)
+#define EBITSET_SIZE(BSET) EBITSET_N_ELTS (BITSET_NBITS_ (BSET))
+#define EBITSET_ASIZE(BSET) ((BSET)->e.size)

 
 #define EBITSET_NEXT(ELT) ((ELT)->u.next)
 #define EBITSET_WORDS(ELT) ((ELT)->u.words)
 
 #define EBITSET_NEXT(ELT) ((ELT)->u.next)
 #define EBITSET_WORDS(ELT) ((ELT)->u.words)


@@ -162,39 +108,77 @@ static void ebitset_free PARAMS ((bitset));
    This is non-zero only if we know for sure that the bitset is zero.  */
 #define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
 
    This is non-zero only if we know for sure that the bitset is zero.  */
 #define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
 

-/* Enable cache to point to element with table index EINDEX. 
+/* Enable cache to point to element with table index EINDEX.

    The element must exist.  */
 #define EBITSET_CACHE_SET(BSET, EINDEX) \
  ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
   (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
 
    The element must exist.  */
 #define EBITSET_CACHE_SET(BSET, EINDEX) \
  ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
   (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
 

+#undef min
+#undef max
+#define min(a, b) ((a) > (b) ? (b) : (a))
+#define max(a, b) ((a) > (b) ? (a) : (b))

 
 

-/* Grow the expandable table for BSET by SIZE elements.  */
-static void
-ebitset_elts_grow (bset, size)
-     bitset bset;
-     bitset_windex size;
+static bitset_bindex
+ebitset_resize (bitset src, bitset_bindex n_bits)

 {
   bitset_windex oldsize;
   bitset_windex newsize;
 
 {
   bitset_windex oldsize;
   bitset_windex newsize;
 

-  oldsize = EBITSET_SIZE (bset);
-  newsize = oldsize + size;
+  if (n_bits == BITSET_NBITS_ (src))
+    return n_bits;

 
 

-  if (BITSET_SIZE_MAX / sizeof (ebitset_elt *) < newsize)
-    xalloc_die ();
+  oldsize = EBITSET_SIZE (src);
+  newsize = EBITSET_N_ELTS (n_bits);

 
 

-  EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
-                                 newsize * sizeof (ebitset_elt *));
-  EBITSET_SIZE (bset) = newsize;
+  if (oldsize < newsize)
+    {
+      bitset_windex size;
+
+      /* The bitset needs to grow.  If we already have enough memory
+         allocated, then just zero what we need.  */
+      if (newsize > EBITSET_ASIZE (src))
+        {
+          /* We need to allocate more memory.  When oldsize is
+             non-zero this means that we are changing the size, so
+             grow the bitset 25% larger than requested to reduce
+             number of reallocations.  */
+
+          if (oldsize == 0)
+            size = newsize;
+          else
+            size = newsize + newsize / 4;
+
+          EBITSET_ELTS (src)
+            = realloc (EBITSET_ELTS (src), size * sizeof (ebitset_elt *));
+          EBITSET_ASIZE (src) = size;
+        }
+
+      memset (EBITSET_ELTS (src) + oldsize, 0,
+              (newsize - oldsize) * sizeof (ebitset_elt *));
+    }
+  else
+    {
+      /* The bitset needs to shrink.  There's no point deallocating
+         the memory unless it is shrinking by a reasonable amount.  */
+      if ((oldsize - newsize) >= oldsize / 2)
+        {
+          EBITSET_ELTS (src)
+            = realloc (EBITSET_ELTS (src), newsize * sizeof (ebitset_elt *));
+          EBITSET_ASIZE (src) = newsize;
+        }
+
+      /* Need to prune any excess bits.  FIXME.  */
+    }

 
 

-  memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *));
+  BITSET_NBITS_ (src) = n_bits;
+  return n_bits;

 }
 
 
 /* Allocate a ebitset element.  The bits are not cleared.  */
 static inline ebitset_elt *
 }
 
 
 /* Allocate a ebitset element.  The bits are not cleared.  */
 static inline ebitset_elt *

-ebitset_elt_alloc ()
+ebitset_elt_alloc (void)

 {
   ebitset_elt *elt;
 
 {
   ebitset_elt *elt;
 


@@ -206,16 +190,16 @@ ebitset_elt_alloc ()
   else
     {
       if (!ebitset_obstack_init)
   else
     {
       if (!ebitset_obstack_init)

-       {
-         ebitset_obstack_init = 1;
+        {
+          ebitset_obstack_init = true;

 
 

-         /* Let particular systems override the size of a chunk.  */
+          /* Let particular systems override the size of a chunk.  */

 
 #ifndef OBSTACK_CHUNK_SIZE
 #define OBSTACK_CHUNK_SIZE 0
 #endif
 
 
 #ifndef OBSTACK_CHUNK_SIZE
 #define OBSTACK_CHUNK_SIZE 0
 #endif
 

-         /* Let them override the alloc and free routines too.  */
+          /* Let them override the alloc and free routines too.  */

 
 #ifndef OBSTACK_CHUNK_ALLOC
 #define OBSTACK_CHUNK_ALLOC xmalloc
 
 #ifndef OBSTACK_CHUNK_ALLOC
 #define OBSTACK_CHUNK_ALLOC xmalloc


@@ -225,22 +209,20 @@ ebitset_elt_alloc ()
 #define OBSTACK_CHUNK_FREE free
 #endif
 
 #define OBSTACK_CHUNK_FREE free
 #endif
 

-#if !defined(__GNUC__) || (__GNUC__ < 2)
+#if ! defined __GNUC__ || __GNUC__ < 2

 #define __alignof__(type) 0
 #endif
 
 #define __alignof__(type) 0
 #endif
 

-         obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
-                                     __alignof__ (ebitset_elt),
-                                     (void *(*)PARAMS ((long)))
-                                     OBSTACK_CHUNK_ALLOC,
-                                     (void (*)PARAMS ((void *)))
-                                     OBSTACK_CHUNK_FREE);
-       }
+          obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
+                                      __alignof__ (ebitset_elt),
+                                      OBSTACK_CHUNK_ALLOC,
+                                      OBSTACK_CHUNK_FREE);
+        }

 
       /* Perhaps we should add a number of new elements to the free
 
       /* Perhaps we should add a number of new elements to the free

-        list.  */
+         list.  */

       elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack,
       elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack,

-                                          sizeof (ebitset_elt));
+                                           sizeof (ebitset_elt));

     }
 
   return elt;
     }
 
   return elt;


@@ -249,7 +231,7 @@ ebitset_elt_alloc ()
 
 /* Allocate a ebitset element.  The bits are cleared.  */
 static inline ebitset_elt *
 
 /* Allocate a ebitset element.  The bits are cleared.  */
 static inline ebitset_elt *

-ebitset_elt_calloc ()
+ebitset_elt_calloc (void)

 {
   ebitset_elt *elt;
 
 {
   ebitset_elt *elt;
 


@@ -260,8 +242,7 @@ ebitset_elt_calloc ()
 
 
 static inline void
 
 
 static inline void

-ebitset_elt_free (elt)
-     ebitset_elt *elt;
+ebitset_elt_free (ebitset_elt *elt)

 {
   EBITSET_NEXT (elt) = ebitset_free_list;
   ebitset_free_list = elt;
 {
   EBITSET_NEXT (elt) = ebitset_free_list;
   ebitset_free_list = elt;


@@ -270,9 +251,7 @@ ebitset_elt_free (elt)
 
 /* Remove element with index EINDEX from bitset BSET.  */
 static inline void
 
 /* Remove element with index EINDEX from bitset BSET.  */
 static inline void

-ebitset_elt_remove (bset, eindex)
-     bitset bset;
-     bitset_windex eindex;
+ebitset_elt_remove (bitset bset, bitset_windex eindex)

 {
   ebitset_elts *elts;
   ebitset_elt *elt;
 {
   ebitset_elts *elts;
   ebitset_elt *elt;


@@ -288,10 +267,7 @@ ebitset_elt_remove (bset, eindex)
 
 /* Add ELT into elts at index EINDEX of bitset BSET.  */
 static inline void
 
 /* Add ELT into elts at index EINDEX of bitset BSET.  */
 static inline void

-ebitset_elt_add (bset, elt, eindex)
-     bitset bset;
-     ebitset_elt *elt;
-     bitset_windex eindex;
+ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex)

 {
   ebitset_elts *elts;
 
 {
   ebitset_elts *elts;
 


@@ -301,33 +277,30 @@ ebitset_elt_add (bset, elt, eindex)
 }
 
 
 }
 
 

-/* Return nonzero if all bits in an element are zero.  */
-static inline int
-ebitset_elt_zero_p (elt)
-     ebitset_elt *elt;
+/* Are all bits in an element zero?  */
+static inline bool
+ebitset_elt_zero_p (ebitset_elt *elt)

 {
   int i;
 
   for (i = 0; i < EBITSET_ELT_WORDS; i++)
     if (EBITSET_WORDS (elt)[i])
 {
   int i;
 
   for (i = 0; i < EBITSET_ELT_WORDS; i++)
     if (EBITSET_WORDS (elt)[i])

-      return 0;
+      return false;

 
 

-  return 1;
+  return true;

 }
 
 
 static ebitset_elt *
 }
 
 
 static ebitset_elt *

-ebitset_elt_find (bset, windex, mode)
-     bitset bset;
-     bitset_windex windex;
-     enum ebitset_find_mode mode;
+ebitset_elt_find (bitset bset, bitset_bindex bindex,
+                  enum ebitset_find_mode mode)

 {
   ebitset_elt *elt;
   bitset_windex size;
   bitset_windex eindex;
   ebitset_elts *elts;
 
 {
   ebitset_elt *elt;
   bitset_windex size;
   bitset_windex eindex;
   ebitset_elts *elts;
 

-  eindex = windex / EBITSET_ELT_WORDS;
+  eindex = bindex / EBITSET_ELT_BITS;

 
   elts = EBITSET_ELTS (bset);
   size = EBITSET_SIZE (bset);
 
   elts = EBITSET_ELTS (bset);
   size = EBITSET_SIZE (bset);


@@ -335,39 +308,28 @@ ebitset_elt_find (bset, windex, mode)
   if (eindex < size)
     {
       if ((elt = elts[eindex]))
   if (eindex < size)
     {
       if ((elt = elts[eindex]))

-       {
-         if (EBITSET_WORDS (elt) == bset->b.cdata)
-           return elt;
+        {
+          if (EBITSET_WORDS (elt) == bset->b.cdata)
+            return elt;

 
 

-         EBITSET_CACHE_SET (bset, eindex);
-         return elt;
-       }
+          EBITSET_CACHE_SET (bset, eindex);
+          return elt;
+        }

     }
 
   /* The element could not be found.  */
 
   switch (mode)
     {
     }
 
   /* The element could not be found.  */
 
   switch (mode)
     {

+    default:
+      abort ();
+

     case EBITSET_FIND:
       return 0;
 
     case EBITSET_CREATE:
       if (eindex >= size)
     case EBITSET_FIND:
       return 0;
 
     case EBITSET_CREATE:
       if (eindex >= size)

-       {
-         bitset_windex extra;
-
-         extra = eindex - size + 1;
-
-         /* We need to expand the table by EXTRA elements.  It may be
-            better with large bitsets to grow the number of
-            elements by some fraction of the current size otherwise
-            we can spend a lot of time slowly increasing the size of the
-            bitset.  */
-         if (extra < EBITSET_GROW_SIZE)
-           extra = EBITSET_GROW_SIZE;
-
-         ebitset_elts_grow (bset, extra);
-       }
+        ebitset_resize (bset, bindex);

 
       /* Create a new element.  */
       elt = ebitset_elt_calloc ();
 
       /* Create a new element.  */
       elt = ebitset_elt_calloc ();


@@ -377,30 +339,13 @@ ebitset_elt_find (bset, windex, mode)
 
     case EBITSET_SUBST:
       return &ebitset_zero_elts[0];
 
     case EBITSET_SUBST:
       return &ebitset_zero_elts[0];

-
-    default:
-      abort ();

     }
 }
 
 
     }
 }
 
 

-static inline ebitset_elt *
-ebitset_elt_last (bset)
-     bitset bset;
-{
-  ebitset_elts *elts;
-
-  elts = EBITSET_ELTS (bset);
-
-  /* Assume that have at least one element in elts.  */
-  return elts[EBITSET_SIZE (bset) - 1];
-}
-
-

 /* Weed out the zero elements from the elts.  */
 static inline bitset_windex
 /* Weed out the zero elements from the elts.  */
 static inline bitset_windex

-ebitset_weed (bset)
-     bitset bset;
+ebitset_weed (bitset bset)

 {
   ebitset_elts *elts;
   bitset_windex j;
 {
   ebitset_elts *elts;
   bitset_windex j;


@@ -416,22 +361,22 @@ ebitset_weed (bset)
       ebitset_elt *elt = elts[j];
 
       if (elt)
       ebitset_elt *elt = elts[j];
 
       if (elt)

-       {
-         if (elt && ebitset_elt_zero_p (elt))
-           {
-             ebitset_elt_remove (bset, j);
-             count++;
-           }
-       }
+        {
+          if (ebitset_elt_zero_p (elt))
+            {
+              ebitset_elt_remove (bset, j);
+              count++;
+            }
+        }

       else
       else

-       count++;
+        count++;

     }
 
   count = j - count;
   if (!count)
     {
     }
 
   count = j - count;
   if (!count)
     {

-      /* All the bits are zero.  We could shrink the elts. 
-        For now just mark BSET as known to be zero.  */
+      /* All the bits are zero.  We could shrink the elts.
+         For now just mark BSET as known to be zero.  */

       EBITSET_ZERO_SET (bset);
     }
   else
       EBITSET_ZERO_SET (bset);
     }
   else


@@ -443,8 +388,7 @@ ebitset_weed (bset)
 
 /* Set all bits in the bitset to zero.  */
 static inline void
 
 /* Set all bits in the bitset to zero.  */
 static inline void

-ebitset_zero (bset)
-     bitset bset;
+ebitset_zero (bitset bset)

 {
   ebitset_elts *elts;
   bitset_windex j;
 {
   ebitset_elts *elts;
   bitset_windex j;


@@ -458,32 +402,30 @@ ebitset_zero (bset)
       ebitset_elt *elt = elts[j];
 
       if (elt)
       ebitset_elt *elt = elts[j];
 
       if (elt)

-       ebitset_elt_remove (bset, j);
+        ebitset_elt_remove (bset, j);

     }
 
     }
 

-  /* All the bits are zero.  We could shrink the elts. 
+  /* All the bits are zero.  We could shrink the elts.

      For now just mark BSET as known to be zero.  */
   EBITSET_ZERO_SET (bset);
 }
 
 
      For now just mark BSET as known to be zero.  */
   EBITSET_ZERO_SET (bset);
 }
 
 

-static inline int
-ebitset_equal_p (dst, src)
-     bitset dst;
-     bitset src;
+static inline bool
+ebitset_equal_p (bitset dst, bitset src)

 {
   ebitset_elts *selts;
   ebitset_elts *delts;
   bitset_windex j;
 
   if (src == dst)
 {
   ebitset_elts *selts;
   ebitset_elts *delts;
   bitset_windex j;
 
   if (src == dst)

-    return 1;
+    return true;

 
   ebitset_weed (dst);
   ebitset_weed (src);
 
   if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
 
   ebitset_weed (dst);
   ebitset_weed (src);
 
   if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))

-    return 0;
+    return false;

 
   selts = EBITSET_ELTS (src);
   delts = EBITSET_ELTS (dst);
 
   selts = EBITSET_ELTS (src);
   delts = EBITSET_ELTS (dst);


@@ -495,23 +437,21 @@ ebitset_equal_p (dst, src)
       ebitset_elt *delt = delts[j];
 
       if (!selt && !delt)
       ebitset_elt *delt = delts[j];
 
       if (!selt && !delt)

-       continue;
+        continue;

       if ((selt && !delt) || (!selt && delt))
       if ((selt && !delt) || (!selt && delt))

-       return 0;
+        return false;

 
       for (i = 0; i < EBITSET_ELT_WORDS; i++)
 
       for (i = 0; i < EBITSET_ELT_WORDS; i++)

-       if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
-         return 0;
+        if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
+          return false;

     }
     }

-  return 1;
+  return true;

 }
 
 
 /* Copy bits from bitset SRC to bitset DST.  */
 static inline void
 }
 
 
 /* Copy bits from bitset SRC to bitset DST.  */
 static inline void

-ebitset_copy_ (dst, src)
-     bitset dst;
-     bitset src;
+ebitset_copy_ (bitset dst, bitset src)

 {
   ebitset_elts *selts;
   ebitset_elts *delts;
 {
   ebitset_elts *selts;
   ebitset_elts *delts;


@@ -522,8 +462,8 @@ ebitset_copy_ (dst, src)
 
   ebitset_zero (dst);
 
 
   ebitset_zero (dst);
 

-  if (EBITSET_SIZE (dst) < EBITSET_SIZE (src))
-    ebitset_elts_grow (dst, EBITSET_SIZE (src) - EBITSET_SIZE (dst));
+  if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
+    ebitset_resize (dst, BITSET_NBITS_ (src));

 
   selts = EBITSET_ELTS (src);
   delts = EBITSET_ELTS (dst);
 
   selts = EBITSET_ELTS (src);
   delts = EBITSET_ELTS (dst);


@@ -532,28 +472,26 @@ ebitset_copy_ (dst, src)
       ebitset_elt *selt = selts[j];
 
       if (selt)
       ebitset_elt *selt = selts[j];
 
       if (selt)

-       {
-         ebitset_elt *tmp;
-
-         tmp = ebitset_elt_alloc ();
-         delts[j] = tmp;
-         memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt),
-                 sizeof (EBITSET_WORDS (selt)));
-       }
+        {
+          ebitset_elt *tmp;
+
+          tmp = ebitset_elt_alloc ();
+          delts[j] = tmp;
+          memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt),
+                  sizeof (EBITSET_WORDS (selt)));
+        }

     }
   EBITSET_NONZERO_SET (dst);
 }
 
 
     }
   EBITSET_NONZERO_SET (dst);
 }
 
 

-/* Copy bits from bitset SRC to bitset DST.  Return non-zero if
+/* Copy bits from bitset SRC to bitset DST.  Return true if

    bitsets different.  */
    bitsets different.  */

-static inline int
-ebitset_copy_cmp (dst, src)
-     bitset dst;
-     bitset src;
+static inline bool
+ebitset_copy_cmp (bitset dst, bitset src)

 {
   if (src == dst)
 {
   if (src == dst)

-    return 0;
+    return false;

 
   if (EBITSET_ZERO_P (dst))
     {
 
   if (EBITSET_ZERO_P (dst))
     {


@@ -562,32 +500,20 @@ ebitset_copy_cmp (dst, src)
     }
 
   if (ebitset_equal_p (dst, src))
     }
 
   if (ebitset_equal_p (dst, src))

-    return 0;
+    return false;

 
   ebitset_copy_ (dst, src);
 
   ebitset_copy_ (dst, src);

-  return 1;
-}
-
-
-/* Return size in bits of bitset SRC.  */
-static bitset_bindex
-ebitset_size (src)
-     bitset src;
-{
-  /* Return current size of bitset in bits.  */
-  return EBITSET_SIZE (src) * EBITSET_ELT_BITS;
+  return true;

 }
 
 
 /* Set bit BITNO in bitset DST.  */
 static void
 }
 
 
 /* Set bit BITNO in bitset DST.  */
 static void

-ebitset_set (dst, bitno)
-     bitset dst;
-     bitset_bindex bitno;
+ebitset_set (bitset dst, bitset_bindex bitno)

 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 

-  ebitset_elt_find (dst, windex, EBITSET_CREATE);
+  ebitset_elt_find (dst, bitno, EBITSET_CREATE);

 
   dst->b.cdata[windex - dst->b.cindex] |=
     (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
 
   dst->b.cdata[windex - dst->b.cindex] |=
     (bitset_word) 1 << (bitno % BITSET_WORD_BITS);


@@ -596,43 +522,37 @@ ebitset_set (dst, bitno)
 
 /* Reset bit BITNO in bitset DST.  */
 static void
 
 /* Reset bit BITNO in bitset DST.  */
 static void

-ebitset_reset (dst, bitno)
-     bitset dst;
-     bitset_bindex bitno;
+ebitset_reset (bitset dst, bitset_bindex bitno)

 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 

-  if (!ebitset_elt_find (dst, windex, EBITSET_FIND))
+  if (!ebitset_elt_find (dst, bitno, EBITSET_FIND))

     return;
 
   dst->b.cdata[windex - dst->b.cindex] &=
     ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 
     return;
 
   dst->b.cdata[windex - dst->b.cindex] &=
     ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 

-  /* If all the data is zero, perhaps we should remove it now... 
+  /* If all the data is zero, perhaps we should remove it now...

      However, there is a good chance that the element will be needed
      again soon.  */
 }
 
 
 /* Test bit BITNO in bitset SRC.  */
      However, there is a good chance that the element will be needed
      again soon.  */
 }
 
 
 /* Test bit BITNO in bitset SRC.  */

-static int
-ebitset_test (src, bitno)
-     bitset src;
-     bitset_bindex bitno;
+static bool
+ebitset_test (bitset src, bitset_bindex bitno)

 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 

-  if (!ebitset_elt_find (src, windex, EBITSET_FIND))
-    return 0;
-
-  return (src->b.
-         cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
+  return (ebitset_elt_find (src, bitno, EBITSET_FIND)
+          && ((src->b.cdata[windex - src->b.cindex]
+               >> (bitno % BITSET_WORD_BITS))
+              & 1));

 }
 
 
 static void
 }
 
 
 static void

-ebitset_free (bset)
-     bitset bset;
+ebitset_free (bitset bset)

 {
   ebitset_zero (bset);
   free (EBITSET_ELTS (bset));
 {
   ebitset_zero (bset);
   free (EBITSET_ELTS (bset));


@@ -643,11 +563,8 @@ ebitset_free (bset)
  *NEXT and store in array LIST.  Return with actual number of bits
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
  *NEXT and store in array LIST.  Return with actual number of bits
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex

-ebitset_list_reverse (bset, list, num, next)
-     bitset bset;
-     bitset_bindex *list;
-     bitset_bindex num;
-     bitset_bindex *next;
+ebitset_list_reverse (bitset bset, bitset_bindex *list,
+                      bitset_bindex num, bitset_bindex *next)

 {
   bitset_bindex n_bits;
   bitset_bindex bitno;
 {
   bitset_bindex n_bits;
   bitset_bindex bitno;


@@ -690,36 +607,36 @@ ebitset_list_reverse (bset, list, num, next)
     {
       ebitset_elt *elt;
       bitset_word *srcp;
     {
       ebitset_elt *elt;
       bitset_word *srcp;

-      
+

       elt = elts[eindex];
       if (elt)
       elt = elts[eindex];
       if (elt)

-       {      
-         srcp = EBITSET_WORDS (elt);
-         
-         do
-           {
-             bitset_word word;
-             
-             word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
-             
-             for (; word; bcount--)
-               {
-                 if (word & BITSET_MSB)
-                   {
-                     list[count++] = boffset + bcount;
-                     if (count >= num)
-                       {
-                         *next = n_bits - (boffset + bcount);
-                         return count;
-                       }
-                   }
-                 word <<= 1;
-               }
-             boffset -= BITSET_WORD_BITS;
-             bcount = BITSET_WORD_BITS - 1;      
-           }
-         while (woffset--);
-       }
+        {
+          srcp = EBITSET_WORDS (elt);
+
+          do
+            {
+              bitset_word word;
+
+              word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
+
+              for (; word; bcount--)
+                {
+                  if (word & BITSET_MSB)
+                    {
+                      list[count++] = boffset + bcount;
+                      if (count >= num)
+                        {
+                          *next = n_bits - (boffset + bcount);
+                          return count;
+                        }
+                    }
+                  word <<= 1;
+                }
+              boffset -= BITSET_WORD_BITS;
+              bcount = BITSET_WORD_BITS - 1;
+            }
+          while (woffset--);
+        }

 
       woffset = EBITSET_ELT_WORDS - 1;
       boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
 
       woffset = EBITSET_ELT_WORDS - 1;
       boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;


@@ -735,11 +652,8 @@ ebitset_list_reverse (bset, list, num, next)
  *NEXT and store in array LIST.  Return with actual number of bits
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
  *NEXT and store in array LIST.  Return with actual number of bits
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex

-ebitset_list (bset, list, num, next)
-     bitset bset;
-     bitset_bindex *list;
-     bitset_bindex num;
-     bitset_bindex *next;
+ebitset_list (bitset bset, bitset_bindex *list,
+              bitset_bindex num, bitset_bindex *next)

 {
   bitset_bindex bitno;
   bitset_windex windex;
 {
   bitset_bindex bitno;
   bitset_windex windex;


@@ -766,33 +680,33 @@ ebitset_list (bset, list, num, next)
 
       elt = elts[eindex];
       if (elt)
 
       elt = elts[eindex];
       if (elt)

-       {
-         bitset_windex woffset;
-         bitset_word *srcp = EBITSET_WORDS (elt);
-
-         windex = bitno / BITSET_WORD_BITS;
-         woffset = eindex * EBITSET_ELT_WORDS;
-
-         for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
-           {
-             word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
-
-             for (; word; bitno++)
-               {
-                 if (word & 1)
-                   {
-                     list[count++] = bitno;
-                     if (count >= num)
-                       {
-                         *next = bitno + 1;
-                         return count;
-                       }
-                   }
-                 word >>= 1;
-               }
-             bitno = (windex + 1) * BITSET_WORD_BITS;
-           }
-       }
+        {
+          bitset_windex woffset;
+          bitset_word *srcp = EBITSET_WORDS (elt);
+
+          windex = bitno / BITSET_WORD_BITS;
+          woffset = eindex * EBITSET_ELT_WORDS;
+
+          for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
+            {
+              word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
+
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    {
+                      list[count++] = bitno;
+                      if (count >= num)
+                        {
+                          *next = bitno + 1;
+                          return count;
+                        }
+                    }
+                  word >>= 1;
+                }
+              bitno = (windex + 1) * BITSET_WORD_BITS;
+            }
+        }

 
       /* Skip to next element.  */
       eindex++;
 
       /* Skip to next element.  */
       eindex++;


@@ -808,65 +722,108 @@ ebitset_list (bset, list, num, next)
 
       elt = elts[eindex];
       if (!elt)
 
       elt = elts[eindex];
       if (!elt)

-       continue;
+        continue;

 
       srcp = EBITSET_WORDS (elt);
       windex = eindex * EBITSET_ELT_WORDS;
 
       if ((count + EBITSET_ELT_BITS) < num)
 
       srcp = EBITSET_WORDS (elt);
       windex = eindex * EBITSET_ELT_WORDS;
 
       if ((count + EBITSET_ELT_BITS) < num)

-       {
-         /* The coast is clear, plant boot!  */
-
-         for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
-           {
-             bitno = windex * BITSET_WORD_BITS;
-
-             word = srcp[i];
-             if (word)
-               {
-                 if (!(word & 0xffff))
-                   {
-                     word >>= 16;
-                     bitno += 16;
-                   }
-                 if (!(word & 0xff))
-                   {
-                     word >>= 8;
-                     bitno += 8;
-                   }
-                 for (; word; bitno++)
-                   {
-                     if (word & 1)
-                       list[count++] = bitno;
-                     word >>= 1;
-                   }
-               }
-           }
-       }
+        {
+          /* The coast is clear, plant boot!  */
+
+#if EBITSET_ELT_WORDS == 2
+          word = srcp[0];
+          if (word)
+            {
+              if (!(word & 0xffff))
+                {
+                  word >>= 16;
+                  bitno += 16;
+                }
+              if (!(word & 0xff))
+                {
+                  word >>= 8;
+                  bitno += 8;
+                }
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    list[count++] = bitno;
+                  word >>= 1;
+                }
+            }
+          windex++;
+          bitno = windex * BITSET_WORD_BITS;
+
+          word = srcp[1];
+          if (word)
+            {
+              if (!(word & 0xffff))
+                {
+                  word >>= 16;
+                  bitno += 16;
+                }
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    list[count++] = bitno;
+                  word >>= 1;
+                }
+            }
+          windex++;
+          bitno = windex * BITSET_WORD_BITS;
+#else
+          for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
+            {
+              bitno = windex * BITSET_WORD_BITS;
+
+              word = srcp[i];
+              if (word)
+                {
+                  if (!(word & 0xffff))
+                    {
+                      word >>= 16;
+                      bitno += 16;
+                    }
+                  if (!(word & 0xff))
+                    {
+                      word >>= 8;
+                      bitno += 8;
+                    }
+                  for (; word; bitno++)
+                    {
+                      if (word & 1)
+                        list[count++] = bitno;
+                      word >>= 1;
+                    }
+                }
+            }
+#endif
+        }

       else
       else

-       {
-         /* Tread more carefully since we need to check
-            if array overflows.  */
-
-         for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
-           {
-             bitno = windex * BITSET_WORD_BITS;
-
-             for (word = srcp[i]; word; bitno++)
-               {
-                 if (word & 1)
-                   {
-                     list[count++] = bitno;
-                     if (count >= num)
-                       {
-                         *next = bitno + 1;
-                         return count;
-                       }
-                   }
-                 word >>= 1;
-               }
-           }
-       }
+        {
+          /* Tread more carefully since we need to check
+             if array overflows.  */
+
+          for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
+            {
+              bitno = windex * BITSET_WORD_BITS;
+
+              for (word = srcp[i]; word; bitno++)
+                {
+                  if (word & 1)
+                    {
+                      list[count++] = bitno;
+                      if (count >= num)
+                        {
+                          *next = bitno + 1;
+                          return count;
+                        }
+                    }
+                  word >>= 1;
+                }
+            }
+        }

     }
 
   *next = bitno;
     }
 
   *next = bitno;


@@ -874,78 +831,137 @@ ebitset_list (bset, list, num, next)
 }
 
 
 }
 
 

+/* Ensure that any unused bits within the last element are clear.  */
+static inline void
+ebitset_unused_clear (bitset dst)
+{
+  unsigned int last_bit;
+  bitset_bindex n_bits;
+
+  n_bits = BITSET_NBITS_ (dst);
+  last_bit = n_bits % EBITSET_ELT_BITS;
+
+  if (last_bit)
+    {
+      bitset_windex eindex;
+      ebitset_elts *elts;
+      ebitset_elt *elt;
+
+      elts = EBITSET_ELTS (dst);
+
+      eindex = n_bits / EBITSET_ELT_BITS;
+
+      elt = elts[eindex];
+      if (elt)
+        {
+          bitset_windex windex;
+          bitset_windex woffset;
+          bitset_word *srcp = EBITSET_WORDS (elt);
+
+          windex = n_bits / BITSET_WORD_BITS;
+          woffset = eindex * EBITSET_ELT_WORDS;
+
+          srcp[windex - woffset] &= ((bitset_word) 1 << last_bit) - 1;
+          windex++;
+          for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
+            srcp[windex - woffset] = 0;
+        }
+    }
+}
+
+

 static void
 static void

-ebitset_ones (dst)
-     bitset dst;
+ebitset_ones (bitset dst)

 {
   bitset_windex j;
   ebitset_elt *elt;
 
 {
   bitset_windex j;
   ebitset_elt *elt;
 

-

   for (j = 0; j < EBITSET_SIZE (dst); j++)
     {
       /* Create new elements if they cannot be found.  Perhaps
   for (j = 0; j < EBITSET_SIZE (dst); j++)
     {
       /* Create new elements if they cannot be found.  Perhaps

-        we should just add pointers to a ones element.  */
+         we should just add pointers to a ones element?  */

       elt =
       elt =

-       ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
+        ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);

       memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
     }
   EBITSET_NONZERO_SET (dst);
       memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
     }
   EBITSET_NONZERO_SET (dst);

+  ebitset_unused_clear (dst);

 }
 
 
 }
 
 

-static int
-ebitset_empty_p (dst)
-     bitset dst;
+static bool
+ebitset_empty_p (bitset dst)

 {
 {

-  return !ebitset_weed (dst);
+  ebitset_elts *elts;
+  bitset_windex j;
+
+  if (EBITSET_ZERO_P (dst))
+    return 1;
+
+  elts = EBITSET_ELTS (dst);
+  for (j = 0; j < EBITSET_SIZE (dst); j++)
+    {
+      ebitset_elt *elt = elts[j];
+
+      if (elt)
+        {
+          if (!ebitset_elt_zero_p (elt))
+            return 0;
+          /* Do some weeding as we go.  */
+          ebitset_elt_remove (dst, j);
+        }
+    }
+
+  /* All the bits are zero.  We could shrink the elts.
+     For now just mark DST as known to be zero.  */
+  EBITSET_ZERO_SET (dst);
+  return 1;

 }
 
 
 static void
 }
 
 
 static void

-ebitset_not (dst, src)
-     bitset dst;
-     bitset src;
+ebitset_not (bitset dst, bitset src)

 {
   unsigned int i;
   ebitset_elt *selt;
   ebitset_elt *delt;
   bitset_windex j;
 
 {
   unsigned int i;
   ebitset_elt *selt;
   ebitset_elt *delt;
   bitset_windex j;
 

+  ebitset_resize (dst, BITSET_NBITS_ (src));
+

   for (j = 0; j < EBITSET_SIZE (src); j++)
     {
       /* Create new elements for dst if they cannot be found
   for (j = 0; j < EBITSET_SIZE (src); j++)
     {
       /* Create new elements for dst if they cannot be found

-            or substitute zero elements if src elements not found.  */
+         or substitute zero elements if src elements not found.  */

       selt =
       selt =

-       ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
+        ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_SUBST);

       delt =
       delt =

-       ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
+        ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);

 
       for (i = 0; i < EBITSET_ELT_WORDS; i++)
 
       for (i = 0; i < EBITSET_ELT_WORDS; i++)

-       EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
+        EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];

     }
   EBITSET_NONZERO_SET (dst);
     }
   EBITSET_NONZERO_SET (dst);

-}  
+  ebitset_unused_clear (dst);
+}

 
 
 
 

-/* Return 1 if DST == DST | SRC.  */
-static int
-ebitset_subset_p (dst, src)
-     bitset dst;
-     bitset src;
+/* Is DST == DST | SRC?  */
+static bool
+ebitset_subset_p (bitset dst, bitset src)

 {
   bitset_windex j;
   ebitset_elts *selts;
   ebitset_elts *delts;
   bitset_windex ssize;
   bitset_windex dsize;
 {
   bitset_windex j;
   ebitset_elts *selts;
   ebitset_elts *delts;
   bitset_windex ssize;
   bitset_windex dsize;

-  
+

   selts = EBITSET_ELTS (src);
   delts = EBITSET_ELTS (dst);
   selts = EBITSET_ELTS (src);
   delts = EBITSET_ELTS (dst);

-  
+

   ssize = EBITSET_SIZE (src);
   dsize = EBITSET_SIZE (dst);
   ssize = EBITSET_SIZE (src);
   dsize = EBITSET_SIZE (dst);

-  
+

   for (j = 0; j < ssize; j++)
     {
       unsigned int i;
   for (j = 0; j < ssize; j++)
     {
       unsigned int i;


@@ -954,42 +970,40 @@ ebitset_subset_p (dst, src)
 
       selt = j < ssize ? selts[j] : 0;
       delt = j < dsize ? delts[j] : 0;
 
       selt = j < ssize ? selts[j] : 0;
       delt = j < dsize ? delts[j] : 0;

-      
+

       if (!selt && !delt)
       if (!selt && !delt)

-       continue;
-      
+        continue;
+

       if (!selt)
       if (!selt)

-       selt = &ebitset_zero_elts[0];
+        selt = &ebitset_zero_elts[0];

       if (!delt)
       if (!delt)

-       delt = &ebitset_zero_elts[0];
-      
+        delt = &ebitset_zero_elts[0];
+

       for (i = 0; i < EBITSET_ELT_WORDS; i++)
       for (i = 0; i < EBITSET_ELT_WORDS; i++)

-       if (EBITSET_WORDS (delt)[i]
-           != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
-         return 0;
+        if (EBITSET_WORDS (delt)[i]
+            != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
+          return false;

     }
     }

-  return 1;
+  return true;

 }
 
 
 }
 
 

-/* Return 1 if DST & SRC == 0.  */
-static int
-ebitset_disjoint_p (dst, src)
-     bitset dst;
-     bitset src;
+/* Is DST & SRC == 0?  */
+static bool
+ebitset_disjoint_p (bitset dst, bitset src)

 {
   bitset_windex j;
   ebitset_elts *selts;
   ebitset_elts *delts;
   bitset_windex ssize;
   bitset_windex dsize;
 {
   bitset_windex j;
   ebitset_elts *selts;
   ebitset_elts *delts;
   bitset_windex ssize;
   bitset_windex dsize;

-  
+

   selts = EBITSET_ELTS (src);
   delts = EBITSET_ELTS (dst);
   selts = EBITSET_ELTS (src);
   delts = EBITSET_ELTS (dst);

-  
+

   ssize = EBITSET_SIZE (src);
   dsize = EBITSET_SIZE (dst);
   ssize = EBITSET_SIZE (src);
   dsize = EBITSET_SIZE (dst);

-  
+

   for (j = 0; j < ssize; j++)
     {
       unsigned int i;
   for (j = 0; j < ssize; j++)
     {
       unsigned int i;


@@ -998,25 +1012,21 @@ ebitset_disjoint_p (dst, src)
 
       selt = j < ssize ? selts[j] : 0;
       delt = j < dsize ? delts[j] : 0;
 
       selt = j < ssize ? selts[j] : 0;
       delt = j < dsize ? delts[j] : 0;

-      
+

       if (!selt || !delt)
       if (!selt || !delt)

-       continue;
-      
+        continue;
+

       for (i = 0; i < EBITSET_ELT_WORDS; i++)
       for (i = 0; i < EBITSET_ELT_WORDS; i++)

-       if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
-         return 0;
+        if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
+          return false;

     }
     }

-  return 1;
+  return true;

 }
 
 
 
 }
 
 
 

-static int
-ebitset_op3_cmp (dst, src1, src2, op)
-     bitset dst;
-     bitset src1;
-     bitset src2;
-     enum bitset_ops op;
+static bool
+ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)

 {
   bitset_windex ssize1;
   bitset_windex ssize2;
 {
   bitset_windex ssize1;
   bitset_windex ssize2;


@@ -1028,10 +1038,12 @@ ebitset_op3_cmp (dst, src1, src2, op)
   bitset_word *srcp1;
   bitset_word *srcp2;
   bitset_word *dstp;
   bitset_word *srcp1;
   bitset_word *srcp2;
   bitset_word *dstp;

-  int changed = 0;
+  bool changed = false;

   unsigned int i;
   bitset_windex j;
 
   unsigned int i;
   bitset_windex j;
 

+  ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
+

   ssize1 = EBITSET_SIZE (src1);
   ssize2 = EBITSET_SIZE (src2);
   dsize = EBITSET_SIZE (dst);
   ssize1 = EBITSET_SIZE (src1);
   ssize2 = EBITSET_SIZE (src2);
   dsize = EBITSET_SIZE (dst);


@@ -1039,9 +1051,6 @@ ebitset_op3_cmp (dst, src1, src2, op)
   if (size < ssize2)
     size = ssize2;
 
   if (size < ssize2)
     size = ssize2;
 

-  if (size > dsize)
-    ebitset_elts_grow (dst, size - dsize);
-

   selts1 = EBITSET_ELTS (src1);
   selts2 = EBITSET_ELTS (src2);
   delts = EBITSET_ELTS (dst);
   selts1 = EBITSET_ELTS (src1);
   selts2 = EBITSET_ELTS (src2);
   delts = EBITSET_ELTS (dst);


@@ -1057,93 +1066,93 @@ ebitset_op3_cmp (dst, src1, src2, op)
       delt = j < dsize ? delts[j] : 0;
 
       if (!selt1 && !selt2)
       delt = j < dsize ? delts[j] : 0;
 
       if (!selt1 && !selt2)

-       {
-         if (delt)
-           {
-             changed = 1;
-             ebitset_elt_remove (dst, j);
-           }
-         continue;
-       }
+        {
+          if (delt)
+            {
+              changed = true;
+              ebitset_elt_remove (dst, j);
+            }
+          continue;
+        }

 
       if (!selt1)
 
       if (!selt1)

-       selt1 = &ebitset_zero_elts[0];
+        selt1 = &ebitset_zero_elts[0];

       if (!selt2)
       if (!selt2)

-       selt2 = &ebitset_zero_elts[0];
+        selt2 = &ebitset_zero_elts[0];

       if (!delt)
       if (!delt)

-       delt = ebitset_elt_calloc ();
+        delt = ebitset_elt_calloc ();

       else
       else

-       delts[j] = 0;
+        delts[j] = 0;

 
       srcp1 = EBITSET_WORDS (selt1);
       srcp2 = EBITSET_WORDS (selt2);
       dstp = EBITSET_WORDS (delt);
       switch (op)
 
       srcp1 = EBITSET_WORDS (selt1);
       srcp2 = EBITSET_WORDS (selt2);
       dstp = EBITSET_WORDS (delt);
       switch (op)

-       {
-       case BITSET_OP_OR:
-         for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
-           {
-             bitset_word tmp = *srcp1++ | *srcp2++;
-
-             if (*dstp != tmp)
-               {
-                 changed = 1;
-                 *dstp = tmp;
-               }
-           }
-         break;
-
-       case BITSET_OP_AND:
-         for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
-           {
-             bitset_word tmp = *srcp1++ & *srcp2++;
-
-             if (*dstp != tmp)
-               {
-                 changed = 1;
-                 *dstp = tmp;
-               }
-           }
-         break;
-
-       case BITSET_OP_XOR:
-         for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
-           {
-             bitset_word tmp = *srcp1++ ^ *srcp2++;
-
-             if (*dstp != tmp)
-               {
-                 changed = 1;
-                 *dstp = tmp;
-               }
-           }
-         break;
-
-       case BITSET_OP_ANDN:
-         for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
-           {
-             bitset_word tmp = *srcp1++ & ~(*srcp2++);
-
-             if (*dstp != tmp)
-               {
-                 changed = 1;
-                 *dstp = tmp;
-               }
-           }
-         break;
-
-       default:
-         abort ();
-       }
+        {
+        default:
+          abort ();
+
+        case BITSET_OP_OR:
+          for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ | *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_AND:
+          for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ & *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_XOR:
+          for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ ^ *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_ANDN:
+          for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ & ~(*srcp2++);
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+        }

 
       if (!ebitset_elt_zero_p (delt))
 
       if (!ebitset_elt_zero_p (delt))

-       {
-         ebitset_elt_add (dst, delt, j);
-       }
+        {
+          ebitset_elt_add (dst, delt, j);
+        }

       else
       else

-       {
-         ebitset_elt_free (delt);
-       }
+        {
+          ebitset_elt_free (delt);
+        }

     }
 
   /* If we have elements of DST left over, free them all.  */
     }
 
   /* If we have elements of DST left over, free them all.  */


@@ -1151,12 +1160,12 @@ ebitset_op3_cmp (dst, src1, src2, op)
     {
       ebitset_elt *delt;
 
     {
       ebitset_elt *delt;
 

-      changed = 1;
+      changed = true;

 
       delt = delts[j];
 
       if (delt)
 
       delt = delts[j];
 
       if (delt)

-       ebitset_elt_remove (dst, j);
+        ebitset_elt_remove (dst, j);

     }
 
   EBITSET_NONZERO_SET (dst);
     }
 
   EBITSET_NONZERO_SET (dst);


@@ -1164,13 +1173,10 @@ ebitset_op3_cmp (dst, src1, src2, op)
 }
 
 
 }
 
 

-static int
-ebitset_and_cmp (dst, src1, src2)
-     bitset dst;
-     bitset src1;
-     bitset src2;
+static bool
+ebitset_and_cmp (bitset dst, bitset src1, bitset src2)

 {
 {

-  int changed;
+  bool changed;

 
   if (EBITSET_ZERO_P (src2))
     {
 
   if (EBITSET_ZERO_P (src2))
     {


@@ -1190,13 +1196,17 @@ ebitset_and_cmp (dst, src1, src2)
 }
 
 
 }
 
 

-static int
-ebitset_andn_cmp (dst, src1, src2)
-     bitset dst;
-     bitset src1;
-     bitset src2;
+static void
+ebitset_and (bitset dst, bitset src1, bitset src2)
+{
+  ebitset_and_cmp (dst, src1, src2);
+}
+
+
+static bool
+ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)

 {
 {

-  int changed;
+  bool changed;

 
   if (EBITSET_ZERO_P (src2))
     {
 
   if (EBITSET_ZERO_P (src2))
     {


@@ -1213,11 +1223,15 @@ ebitset_andn_cmp (dst, src1, src2)
 }
 
 
 }
 
 

-static int
-ebitset_or_cmp (dst, src1, src2)
-     bitset dst;
-     bitset src1;
-     bitset src2;
+static void
+ebitset_andn (bitset dst, bitset src1, bitset src2)
+{
+  ebitset_andn_cmp (dst, src1, src2);
+}
+
+
+static bool
+ebitset_or_cmp (bitset dst, bitset src1, bitset src2)

 {
   if (EBITSET_ZERO_P (src2))
     {
 {
   if (EBITSET_ZERO_P (src2))
     {


@@ -1231,11 +1245,15 @@ ebitset_or_cmp (dst, src1, src2)
 }
 
 
 }
 
 

-static int
-ebitset_xor_cmp (dst, src1, src2)
-     bitset dst;
-     bitset src1;
-     bitset src2;
+static void
+ebitset_or (bitset dst, bitset src1, bitset src2)
+{
+  ebitset_or_cmp (dst, src1, src2);
+}
+
+
+static bool
+ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)

 {
   if (EBITSET_ZERO_P (src2))
     {
 {
   if (EBITSET_ZERO_P (src2))
     {


@@ -1250,9 +1268,14 @@ ebitset_xor_cmp (dst, src1, src2)
 
 
 static void
 
 
 static void

-ebitset_copy (dst, src)
-     bitset dst;
-     bitset src;
+ebitset_xor (bitset dst, bitset src1, bitset src2)
+{
+  ebitset_xor_cmp (dst, src1, src2);
+}
+
+
+static void
+ebitset_copy (bitset dst, bitset src)

 {
   if (BITSET_COMPATIBLE_ (dst, src))
       ebitset_copy_ (dst, src);
 {
   if (BITSET_COMPATIBLE_ (dst, src))
       ebitset_copy_ (dst, src);


@@ -1267,7 +1290,8 @@ struct bitset_vtable ebitset_vtable = {
   ebitset_reset,
   bitset_toggle_,
   ebitset_test,
   ebitset_reset,
   bitset_toggle_,
   ebitset_test,

-  ebitset_size,
+  ebitset_resize,
+  bitset_size_,

   bitset_count_,
   ebitset_empty_p,
   ebitset_ones,
   bitset_count_,
   ebitset_empty_p,
   ebitset_ones,


@@ -1277,19 +1301,19 @@ struct bitset_vtable ebitset_vtable = {
   ebitset_equal_p,
   ebitset_not,
   ebitset_subset_p,
   ebitset_equal_p,
   ebitset_not,
   ebitset_subset_p,

-  (PFV) ebitset_and_cmp,
+  ebitset_and,

   ebitset_and_cmp,
   ebitset_and_cmp,

-  (PFV) ebitset_andn_cmp,
+  ebitset_andn,

   ebitset_andn_cmp,
   ebitset_andn_cmp,

-  (PFV) ebitset_or_cmp,
+  ebitset_or,

   ebitset_or_cmp,
   ebitset_or_cmp,

-  (PFV) ebitset_xor_cmp,
+  ebitset_xor,

   ebitset_xor_cmp,
   ebitset_xor_cmp,

-  (PFV) bitset_and_or_cmp_,
+  bitset_and_or_,

   bitset_and_or_cmp_,
   bitset_and_or_cmp_,

-  (PFV) bitset_andn_or_cmp_,
+  bitset_andn_or_,

   bitset_andn_or_cmp_,
   bitset_andn_or_cmp_,

-  (PFV) bitset_or_and_cmp_,
+  bitset_or_and_,

   bitset_or_and_cmp_,
   ebitset_list,
   ebitset_list_reverse,
   bitset_or_and_cmp_,
   ebitset_list,
   ebitset_list_reverse,


@@ -1300,46 +1324,38 @@ struct bitset_vtable ebitset_vtable = {
 
 /* Return size of initial structure.  */
 size_t
 
 /* Return size of initial structure.  */
 size_t

-ebitset_bytes (n_bits)
-     bitset_bindex n_bits ATTRIBUTE_UNUSED;
+ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)

 {
 {

-  return sizeof (struct bitset_struct);
+  return sizeof (struct ebitset_struct);

 }
 
 
 /* Initialize a bitset.  */
 
 bitset
 }
 
 
 /* Initialize a bitset.  */
 
 bitset

-ebitset_init (bset, n_bits)
-     bitset bset;
-     bitset_bindex n_bits;
+ebitset_init (bitset bset, bitset_bindex n_bits)

 {
 {

-  bitset_windex size;
-

   bset->b.vtable = &ebitset_vtable;
 
   bset->b.csize = EBITSET_ELT_WORDS;
 
   EBITSET_ZERO_SET (bset);
 
   bset->b.vtable = &ebitset_vtable;
 
   bset->b.csize = EBITSET_ELT_WORDS;
 
   EBITSET_ZERO_SET (bset);
 

-  size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
-    : EBITSET_INITIAL_SIZE;
-
-  EBITSET_SIZE (bset) = 0;
+  EBITSET_ASIZE (bset) = 0;

   EBITSET_ELTS (bset) = 0;
   EBITSET_ELTS (bset) = 0;

-  ebitset_elts_grow (bset, size);
+  ebitset_resize (bset, n_bits);

 
   return bset;
 }
 
 
 void
 
   return bset;
 }
 
 
 void

-ebitset_release_memory ()
+ebitset_release_memory (void)

 {
   ebitset_free_list = 0;
   if (ebitset_obstack_init)
     {
 {
   ebitset_free_list = 0;
   if (ebitset_obstack_init)
     {

-      ebitset_obstack_init = 0;
+      ebitset_obstack_init = false;

       obstack_free (&ebitset_obstack, NULL);
     }
 }
       obstack_free (&ebitset_obstack, NULL);
     }
 }