style: no longer use backquotes in messages

[bison.git] / lib / ebitset.c

diff --git a/lib/ebitset.c b/lib/ebitset.c
index aa8727ff390e762669e5d79e6d34d87f671b0617..e5d6c9239b7263ca526fd2733258e08c6bc61105 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, 2003 Free Software Foundation, Inc.
+
+   Copyright (C) 2002-2006, 2009-2013 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


@@ -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;


@@ -75,11 +75,6 @@ typedef ebitset_elt *ebitset_elts;
 #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

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


@@ -89,17 +84,19 @@ static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits.  */
 /* Obstack to allocate bitset elements from.  */
 static struct obstack ebitset_obstack;
 static bool ebitset_obstack_init = false;
 /* Obstack to allocate bitset elements from.  */
 static struct obstack ebitset_obstack;
 static bool ebitset_obstack_init = false;

-static ebitset_elt *ebitset_free_list; /* Free list of bitset elements.  */
+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)
 
 /* Disable bitset cache and mark BSET as being zero.  */
 #define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
 
 #define EBITSET_NEXT(ELT) ((ELT)->u.next)
 #define EBITSET_WORDS(ELT) ((ELT)->u.words)
 
 /* Disable bitset cache and mark BSET as being zero.  */
 #define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \

-       (BSET)->b.cdata = 0)
+        (BSET)->b.cdata = 0)

 
 #define EBITSET_CACHE_DISABLE(BSET)  ((BSET)->b.cindex = BITSET_WINDEX_MAX)
 
 
 #define EBITSET_CACHE_DISABLE(BSET)  ((BSET)->b.cindex = BITSET_WINDEX_MAX)
 


@@ -117,25 +114,65 @@ static ebitset_elt *ebitset_free_list;    /* Free list of bitset elements.  */
  ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
   (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (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 (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;

 }
 
 
 }
 
 


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

-       {
-         ebitset_obstack_init = true;
+        {
+          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


@@ -172,22 +209,20 @@ ebitset_elt_alloc (void)
 #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;


@@ -257,15 +292,15 @@ ebitset_elt_zero_p (ebitset_elt *elt)
 
 
 static ebitset_elt *
 
 
 static ebitset_elt *

-ebitset_elt_find (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);


@@ -273,39 +308,28 @@ ebitset_elt_find (bitset bset, bitset_windex windex,
   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 ();


@@ -315,25 +339,10 @@ ebitset_elt_find (bitset bset, bitset_windex windex,
 
     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 (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
 ebitset_weed (bitset bset)
 /* Weed out the zero elements from the elts.  */
 static inline bitset_windex
 ebitset_weed (bitset bset)


@@ -352,22 +361,22 @@ ebitset_weed (bitset 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)
     {
       /* All the bits are zero.  We could shrink the elts.
     }
 
   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.  */
+         For now just mark BSET as known to be zero.  */

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


@@ -393,7 +402,7 @@ ebitset_zero (bitset 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.


@@ -428,13 +437,13 @@ ebitset_equal_p (bitset dst, bitset 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 false;
+        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 false;
+        if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
+          return false;

     }
   return true;
 }
     }
   return true;
 }


@@ -453,8 +462,8 @@ ebitset_copy_ (bitset dst, bitset 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);


@@ -463,14 +472,14 @@ ebitset_copy_ (bitset dst, bitset 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);
 }


@@ -498,22 +507,13 @@ ebitset_copy_cmp (bitset dst, bitset src)
 }
 
 
 }
 
 

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

 /* Set bit BITNO in bitset DST.  */
 static void
 ebitset_set (bitset dst, bitset_bindex bitno)
 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
 /* Set bit BITNO in bitset DST.  */
 static void
 ebitset_set (bitset dst, bitset_bindex bitno)
 {
   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);


@@ -526,7 +526,7 @@ 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] &=
     return;
 
   dst->b.cdata[windex - dst->b.cindex] &=


@@ -544,10 +544,10 @@ ebitset_test (bitset src, bitset_bindex bitno)
 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 

-  return (ebitset_elt_find (src, windex, EBITSET_FIND)
-         && ((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));

 }
 
 
 }
 
 


@@ -564,7 +564,7 @@ ebitset_free (bitset bset)
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
 ebitset_list_reverse (bitset bset, bitset_bindex *list,
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
 ebitset_list_reverse (bitset bset, bitset_bindex *list,

-                     bitset_bindex num, bitset_bindex *next)
+                      bitset_bindex num, bitset_bindex *next)

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


@@ -610,33 +610,33 @@ ebitset_list_reverse (bitset bset, bitset_bindex *list,
 
       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;


@@ -653,7 +653,7 @@ ebitset_list_reverse (bitset bset, bitset_bindex *list,
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
 ebitset_list (bitset bset, bitset_bindex *list,
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
 ebitset_list (bitset bset, bitset_bindex *list,

-             bitset_bindex num, bitset_bindex *next)
+              bitset_bindex num, bitset_bindex *next)

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


@@ -680,33 +680,33 @@ ebitset_list (bitset bset, bitset_bindex *list,
 
       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++;


@@ -722,65 +722,108 @@ ebitset_list (bitset bset, bitset_bindex *list,
 
       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;


@@ -788,29 +831,91 @@ ebitset_list (bitset bset, bitset_bindex *list,
 }
 
 
 }
 
 

+/* 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
 ebitset_ones (bitset dst)
 {
   bitset_windex j;
   ebitset_elt *elt;
 
 static void
 ebitset_ones (bitset dst)
 {
   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 bool
 ebitset_empty_p (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;

 }
 
 
 }
 
 


@@ -822,19 +927,22 @@ ebitset_not (bitset dst, bitset src)
   ebitset_elt *delt;
   bitset_windex j;
 
   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);

 }
 
 
 }
 
 


@@ -864,17 +972,17 @@ ebitset_subset_p (bitset dst, bitset src)
       delt = j < dsize ? delts[j] : 0;
 
       if (!selt && !delt)
       delt = j < dsize ? delts[j] : 0;
 
       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 false;
+        if (EBITSET_WORDS (delt)[i]
+            != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
+          return false;

     }
   return true;
 }
     }
   return true;
 }


@@ -906,11 +1014,11 @@ ebitset_disjoint_p (bitset dst, bitset src)
       delt = j < dsize ? delts[j] : 0;
 
       if (!selt || !delt)
       delt = j < dsize ? delts[j] : 0;
 
       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 false;
+        if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
+          return false;

     }
   return true;
 }
     }
   return true;
 }


@@ -934,6 +1042,8 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
   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);


@@ -941,9 +1051,6 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops 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);


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

-       {
-         if (delt)
-           {
-             changed = true;
-             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 = 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;
-
-       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.  */


@@ -1058,7 +1165,7 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
       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);


@@ -1183,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,


@@ -1227,20 +1335,15 @@ ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
 bitset
 ebitset_init (bitset bset, bitset_bindex n_bits)
 {
 bitset
 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;
 }
 
   return bset;
 }