global: remove unnecessary horizontal tabs.

[bison.git] / lib / lbitset.c

diff --git a/lib/lbitset.c b/lib/lbitset.c
index 2e5b208140126711f0a21331a14336587f385b2d..5922cd205c365499689b10d4d294c1d99db8e7a4 100644 (file)
--- a/lib/lbitset.c
+++ b/lib/lbitset.c
@@ -1,10 +1,13 @@
 /* Functions to support link list bitsets.
 /* Functions to support link list bitsets.

-   Copyright (C) 2002, 2003 Free Software Foundation, Inc.
+
+   Copyright (C) 2002-2004, 2006, 2009-2011 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,19 +16,17 @@
    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 "lbitset.h"
 
 #include "lbitset.h"

+

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

+#include <string.h>

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


@@ -40,7 +41,10 @@
 /* Number of words to use for each element.  The larger the value the
    greater the size of the cache and the shorter the time to find a given bit
    but the more memory wasted for sparse bitsets and the longer the time
 /* Number of words to use for each element.  The larger the value the
    greater the size of the cache and the shorter the time to find a given bit
    but the more memory wasted for sparse bitsets and the longer the time

-   to search for set bits.  */
+   to search for set bits.
+
+   The routines that dominate timing profiles are lbitset_elt_find
+   and lbitset_elt_link, especially when accessing the bits randomly.  */

 
 #define LBITSET_ELT_WORDS 2
 
 
 #define LBITSET_ELT_WORDS 2
 


@@ -50,16 +54,16 @@ typedef bitset_word lbitset_word;
 
 /* Number of bits stored in each element.  */
 #define LBITSET_ELT_BITS \
 
 /* Number of bits stored in each element.  */
 #define LBITSET_ELT_BITS \

-  ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
+  ((unsigned int) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))

 
 /* Lbitset element.   We use an array of bits for each element.
    These are linked together in a doubly-linked list.  */
 typedef struct lbitset_elt_struct
 {
 
 /* Lbitset element.   We use an array of bits for each element.
    These are linked together in a doubly-linked list.  */
 typedef struct lbitset_elt_struct
 {

-  struct lbitset_elt_struct *next;     /* Next element.  */
-  struct lbitset_elt_struct *prev;     /* Previous element.  */
-  bitset_windex index; /* bitno / BITSET_WORD_BITS.  */
-  bitset_word words[LBITSET_ELT_WORDS];        /* Bits that are set.  */
+  struct lbitset_elt_struct *next;      /* Next element.  */
+  struct lbitset_elt_struct *prev;      /* Previous element.  */
+  bitset_windex index;  /* bitno / BITSET_WORD_BITS.  */
+  bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set.  */

 }
 lbitset_elt;
 
 }
 lbitset_elt;
 


@@ -72,9 +76,9 @@ static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits.  */
 /* Obstack to allocate bitset elements from.  */
 static struct obstack lbitset_obstack;
 static bool lbitset_obstack_init = false;
 /* Obstack to allocate bitset elements from.  */
 static struct obstack lbitset_obstack;
 static bool lbitset_obstack_init = false;

-static lbitset_elt *lbitset_free_list; /* Free list of bitset elements.  */
+static lbitset_elt *lbitset_free_list;  /* Free list of bitset elements.  */

 
 

-extern void debug_lbitset PARAMS ((bitset));
+extern void debug_lbitset (bitset);

 
 #define LBITSET_CURRENT1(X) \
   ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))
 
 #define LBITSET_CURRENT1(X) \
   ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))


@@ -98,16 +102,16 @@ lbitset_elt_alloc (void)
   else
     {
       if (!lbitset_obstack_init)
   else
     {
       if (!lbitset_obstack_init)

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


@@ -117,22 +121,20 @@ lbitset_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 (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
-                                     __alignof__ (lbitset_elt),
-                                     (void *(*)PARAMS ((long)))
-                                     OBSTACK_CHUNK_ALLOC,
-                                     (void (*)PARAMS ((void *)))
-                                     OBSTACK_CHUNK_FREE);
-       }
+          obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
+                                      __alignof__ (lbitset_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 = (lbitset_elt *) obstack_alloc (&lbitset_obstack,
       elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack,

-                                          sizeof (lbitset_elt));
+                                           sizeof (lbitset_elt));

     }
 
   return elt;
     }
 
   return elt;


@@ -183,20 +185,20 @@ lbitset_elt_unlink (bitset bset, lbitset_elt *elt)
   if (LBITSET_CURRENT (bset) == elt)
     {
       if (next)
   if (LBITSET_CURRENT (bset) == elt)
     {
       if (next)

-       {
-         bset->b.cdata = next->words;
-         bset->b.cindex = next->index;
-       }
+        {
+          bset->b.cdata = next->words;
+          bset->b.cindex = next->index;
+        }

       else if (prev)
       else if (prev)

-       {
-         bset->b.cdata = prev->words;
-         bset->b.cindex = prev->index;
-       }
+        {
+          bset->b.cdata = prev->words;
+          bset->b.cindex = prev->index;
+        }

       else
       else

-       {
-         bset->b.csize = 0;
-         bset->b.cdata = 0;
-       }
+        {
+          bset->b.csize = 0;
+          bset->b.cdata = 0;
+        }

     }
 
   lbitset_elt_free (elt);
     }
 
   lbitset_elt_free (elt);


@@ -276,13 +278,13 @@ lbitset_elt_link (bitset bset, lbitset_elt *elt)
   else if (windex < bset->b.cindex)
     {
       for (ptr = current;
   else if (windex < bset->b.cindex)
     {
       for (ptr = current;

-          ptr->prev && ptr->prev->index > windex; ptr = ptr->prev)
-       continue;
+           ptr->prev && ptr->prev->index > windex; ptr = ptr->prev)
+        continue;

 
       if (ptr->prev)
 
       if (ptr->prev)

-       ptr->prev->next = elt;
+        ptr->prev->next = elt;

       else
       else

-       LBITSET_HEAD (bset) = elt;
+        LBITSET_HEAD (bset) = elt;

 
       elt->prev = ptr->prev;
       elt->next = ptr;
 
       elt->prev = ptr->prev;
       elt->next = ptr;


@@ -293,13 +295,13 @@ lbitset_elt_link (bitset bset, lbitset_elt *elt)
   else
     {
       for (ptr = current;
   else
     {
       for (ptr = current;

-          ptr->next && ptr->next->index < windex; ptr = ptr->next)
-       continue;
+           ptr->next && ptr->next->index < windex; ptr = ptr->next)
+        continue;

 
       if (ptr->next)
 
       if (ptr->next)

-       ptr->next->prev = elt;
+        ptr->next->prev = elt;

       else
       else

-       LBITSET_TAIL (bset) = elt;
+        LBITSET_TAIL (bset) = elt;

 
       elt->next = ptr->next;
       elt->prev = ptr;
 
       elt->next = ptr->next;
       elt->prev = ptr;


@@ -315,7 +317,7 @@ lbitset_elt_link (bitset bset, lbitset_elt *elt)
 
 static lbitset_elt *
 lbitset_elt_find (bitset bset, bitset_windex windex,
 
 static lbitset_elt *
 lbitset_elt_find (bitset bset, bitset_windex windex,

-                 enum lbitset_find_mode mode)
+                  enum lbitset_find_mode mode)

 {
   lbitset_elt *elt;
   lbitset_elt *current;
 {
   lbitset_elt *elt;
   lbitset_elt *current;


@@ -325,7 +327,7 @@ lbitset_elt_find (bitset bset, bitset_windex windex,
       current = LBITSET_CURRENT (bset);
       /* Check if element is the cached element.  */
       if ((windex - bset->b.cindex) < bset->b.csize)
       current = LBITSET_CURRENT (bset);
       /* Check if element is the cached element.  */
       if ((windex - bset->b.cindex) < bset->b.csize)

-       return current;
+        return current;

     }
   else
     {
     }
   else
     {


@@ -335,32 +337,35 @@ lbitset_elt_find (bitset bset, bitset_windex windex,
   if (current)
     {
       if (windex < bset->b.cindex)
   if (current)
     {
       if (windex < bset->b.cindex)

-       {
-         for (elt = current;
-              elt->prev && elt->index > windex; elt = elt->prev)
-           continue;
-       }
+        {
+          for (elt = current;
+               elt->prev && elt->index > windex; elt = elt->prev)
+            continue;
+        }

       else
       else

-       {
-         for (elt = current;
-              elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
-              elt = elt->next)
-           continue;
-       }
+        {
+          for (elt = current;
+               elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
+               elt = elt->next)
+            continue;
+        }

 
       /* ELT is the nearest to the one we want.  If it's not the one
 
       /* ELT is the nearest to the one we want.  If it's not the one

-        we want, the one we want does not exist.  */
+         we want, the one we want does not exist.  */

       if (elt && (windex - elt->index) < LBITSET_ELT_WORDS)
       if (elt && (windex - elt->index) < LBITSET_ELT_WORDS)

-       {
-         bset->b.cindex = elt->index;
-         bset->b.csize = LBITSET_ELT_WORDS;
-         bset->b.cdata = elt->words;
-         return elt;
-       }
+        {
+          bset->b.cindex = elt->index;
+          bset->b.csize = LBITSET_ELT_WORDS;
+          bset->b.cdata = elt->words;
+          return elt;
+        }

     }
 
   switch (mode)
     {
     }
 
   switch (mode)
     {

+    default:
+      abort ();
+

     case LBITSET_FIND:
       return 0;
 
     case LBITSET_FIND:
       return 0;
 


@@ -374,9 +379,6 @@ lbitset_elt_find (bitset bset, bitset_windex windex,
 
     case LBITSET_SUBST:
       return &lbitset_zero_elts[0];
 
     case LBITSET_SUBST:
       return &lbitset_zero_elts[0];

-
-    default:
-      abort ();

     }
 }
 
     }
 }
 


@@ -392,7 +394,7 @@ lbitset_weed (bitset bset)
     {
       next = elt->next;
       if (lbitset_elt_zero_p (elt))
     {
       next = elt->next;
       if (lbitset_elt_zero_p (elt))

-       lbitset_elt_unlink (bset, elt);
+        lbitset_elt_unlink (bset, elt);

     }
 }
 
     }
 }
 


@@ -429,11 +431,11 @@ lbitset_equal_p (bitset dst, bitset src)
        selt && delt; selt = selt->next, delt = delt->next)
     {
       if (selt->index != delt->index)
        selt && delt; selt = selt->next, delt = delt->next)
     {
       if (selt->index != delt->index)

-       return false;
+        return false;

 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)
 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)

-       if (delt->words[j] != selt->words[j])
-         return false;
+        if (delt->words[j] != selt->words[j])
+          return false;

     }
   return !selt && !delt;
 }
     }
   return !selt && !delt;
 }


@@ -465,9 +467,9 @@ lbitset_copy (bitset dst, bitset src)
       tmp->prev = prev;
       tmp->next = 0;
       if (prev)
       tmp->prev = prev;
       tmp->next = 0;
       if (prev)

-       prev->next = tmp;
+        prev->next = tmp;

       else
       else

-       LBITSET_HEAD (dst) = tmp;
+        LBITSET_HEAD (dst) = tmp;

       prev = tmp;
 
       memcpy (tmp->words, elt->words, sizeof (elt->words));
       prev = tmp;
 
       memcpy (tmp->words, elt->words, sizeof (elt->words));


@@ -502,21 +504,15 @@ lbitset_copy_cmp (bitset dst, bitset src)
 }
 
 
 }
 
 

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

 static bitset_bindex
 static bitset_bindex

-lbitset_size (bitset src)
+lbitset_resize (bitset src, bitset_bindex size)

 {
 {

-  lbitset_elt *elt;
+    BITSET_NBITS_ (src) = size;

 
 

-  elt = LBITSET_TAIL (src);
-  if (!elt)
-    return 0;
-
-  /* Return current size of bitset in bits.  */
-  return (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
+    /* Need to prune any excess bits.  FIXME.  */
+    return size;

 }
 
 }
 

-

 /* Set bit BITNO in bitset DST.  */
 static void
 lbitset_set (bitset dst, bitset_bindex bitno)
 /* Set bit BITNO in bitset DST.  */
 static void
 lbitset_set (bitset dst, bitset_bindex bitno)


@@ -553,9 +549,9 @@ lbitset_test (bitset src, bitset_bindex bitno)
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
   return (lbitset_elt_find (src, windex, LBITSET_FIND)
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
   return (lbitset_elt_find (src, windex, LBITSET_FIND)

-         && ((src->b.cdata[windex - src->b.cindex]
-              >> (bitno % BITSET_WORD_BITS))
-             & 1));
+          && ((src->b.cdata[windex - src->b.cindex]
+               >> (bitno % BITSET_WORD_BITS))
+              & 1));

 }
 
 
 }
 
 


@@ -571,7 +567,7 @@ lbitset_free (bitset bset)
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
 lbitset_list_reverse (bitset bset, bitset_bindex *list,
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
 lbitset_list_reverse (bitset bset, bitset_bindex *list,

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

 {
   bitset_bindex rbitno;
   bitset_bindex bitno;
 {
   bitset_bindex rbitno;
   bitset_bindex bitno;


@@ -607,7 +603,7 @@ lbitset_list_reverse (bitset bset, bitset_bindex *list,
   if (windex >= elt->index + LBITSET_ELT_WORDS)
     {
       /* We are trying to start in no-mans land so start
   if (windex >= elt->index + LBITSET_ELT_WORDS)
     {
       /* We are trying to start in no-mans land so start

-        at end of current elt.  */
+         at end of current elt.  */

       bcount = BITSET_WORD_BITS - 1;
       windex = elt->index + LBITSET_ELT_WORDS - 1;
     }
       bcount = BITSET_WORD_BITS - 1;
       windex = elt->index + LBITSET_ELT_WORDS - 1;
     }


@@ -627,33 +623,33 @@ lbitset_list_reverse (bitset bset, bitset_bindex *list,
       bitset_word *srcp = elt->words;
 
       for (; (windex - elt->index) < LBITSET_ELT_WORDS;
       bitset_word *srcp = elt->words;
 
       for (; (windex - elt->index) < LBITSET_ELT_WORDS;

-          windex--, boffset -= BITSET_WORD_BITS,
-            bcount = BITSET_WORD_BITS - 1)
-       {
-         word =
-           srcp[windex - elt->index] << (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;
-           }
-       }
+           windex--, boffset -= BITSET_WORD_BITS,
+             bcount = BITSET_WORD_BITS - 1)
+        {
+          word =
+            srcp[windex - elt->index] << (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;
+            }
+        }

 
       elt = elt->prev;
       if (elt)
 
       elt = elt->prev;
       if (elt)

-       {
-         windex = elt->index + LBITSET_ELT_WORDS - 1;
-         boffset = windex * BITSET_WORD_BITS;
-       }
+        {
+          windex = elt->index + LBITSET_ELT_WORDS - 1;
+          boffset = windex * BITSET_WORD_BITS;
+        }

     }
 
   *next = n_bits - (boffset + 1);
     }
 
   *next = n_bits - (boffset + 1);


@@ -666,7 +662,7 @@ lbitset_list_reverse (bitset bset, bitset_bindex *list,
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
 lbitset_list (bitset bset, bitset_bindex *list,
  found and with *NEXT indicating where search stopped.  */
 static bitset_bindex
 lbitset_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;


@@ -697,51 +693,51 @@ lbitset_list (bitset bset, bitset_bindex *list,
 
       /* Skip to starting element.  */
       for (elt = head;
 
       /* Skip to starting element.  */
       for (elt = head;

-          elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
-          elt = elt->next)
-       continue;
+           elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
+           elt = elt->next)
+        continue;

 
       if (!elt)
 
       if (!elt)

-       return 0;
+        return 0;

 
       if (windex < elt->index)
 
       if (windex < elt->index)

-       {
-         windex = elt->index;
-         bitno = windex * BITSET_WORD_BITS;
-       }
+        {
+          windex = elt->index;
+          bitno = windex * BITSET_WORD_BITS;
+        }

       else
       else

-       {
-         bitset_word *srcp = elt->words;
-
-         /* We are starting within an element.  */
-
-         for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
-           {
-             word = srcp[windex - elt->index] >> (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;
-           }
-
-         elt = elt->next;
-         if (elt)
-           {
-             windex = elt->index;
-             bitno = windex * BITSET_WORD_BITS;
-           }
-       }
+        {
+          bitset_word *srcp = elt->words;
+
+          /* We are starting within an element.  */
+
+          for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
+            {
+              word = srcp[windex - elt->index] >> (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;
+            }
+
+          elt = elt->next;
+          if (elt)
+            {
+              windex = elt->index;
+              bitno = windex * BITSET_WORD_BITS;
+            }
+        }

     }
 
 
     }
 
 


@@ -754,109 +750,109 @@ lbitset_list (bitset bset, bitset_bindex *list,
       bitset_word *srcp = elt->words;
 
       if ((count + LBITSET_ELT_BITS) < num)
       bitset_word *srcp = elt->words;
 
       if ((count + LBITSET_ELT_BITS) < num)

-       {
-         /* The coast is clear, plant boot!  */
+        {
+          /* The coast is clear, plant boot!  */

 
 #if LBITSET_ELT_WORDS == 2
 
 #if LBITSET_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;
+          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
 #else

-         for (i = 0; i < LBITSET_ELT_WORDS; i++)
-           {
-             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;
-                   }
-               }
-             windex++;
-             bitno = windex * BITSET_WORD_BITS;
-           }
+          for (i = 0; i < LBITSET_ELT_WORDS; i++)
+            {
+              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;
+                    }
+                }
+              windex++;
+              bitno = windex * BITSET_WORD_BITS;
+            }

 #endif
 #endif

-       }
+        }

       else
       else

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

 
       elt = elt->next;
       if (elt)
 
       elt = elt->next;
       if (elt)

-       {
-         windex = elt->index;
-         bitno = windex * BITSET_WORD_BITS;
-       }
+        {
+          windex = elt->index;
+          bitno = windex * BITSET_WORD_BITS;
+        }

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


@@ -867,8 +863,48 @@ lbitset_list (bitset bset, bitset_bindex *list,
 static bool
 lbitset_empty_p (bitset dst)
 {
 static bool
 lbitset_empty_p (bitset dst)
 {

-  lbitset_weed (dst);
-  return !LBITSET_HEAD (dst);
+  lbitset_elt *elt;
+  lbitset_elt *next;
+
+  for (elt = LBITSET_HEAD (dst); elt; elt = next)
+    {
+      next = elt->next;
+      if (!lbitset_elt_zero_p (elt))
+        return 0;
+      /* Weed as we go.  */
+      lbitset_elt_unlink (dst, elt);
+    }
+
+  return 1;
+}
+
+
+/* Ensure that any unused bits within the last element are clear.  */
+static inline void
+lbitset_unused_clear (bitset dst)
+{
+  unsigned int last_bit;
+  bitset_bindex n_bits;
+
+  n_bits = BITSET_SIZE_ (dst);
+  last_bit = n_bits % LBITSET_ELT_BITS;
+
+  if (last_bit)
+    {
+      lbitset_elt *elt;
+      bitset_windex windex;
+      bitset_word *srcp;
+
+      elt = LBITSET_TAIL (dst);
+      srcp = elt->words;
+      windex = n_bits / BITSET_WORD_BITS;
+
+      srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1;
+      windex++;
+
+      for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
+        srcp[windex - elt->index] = 0;
+    }

 }
 
 
 }
 
 


@@ -883,18 +919,17 @@ lbitset_ones (bitset dst)
       bitset!  It makes a sparse bitset become dense.  An alternative
       is to have a flag that indicates that the bitset stores the
       complement of what it indicates.  */
       bitset!  It makes a sparse bitset become dense.  An alternative
       is to have a flag that indicates that the bitset stores the
       complement of what it indicates.  */

-  elt = LBITSET_TAIL (dst);
-  /* Ignore empty set.  */
-  if (!elt)
-    return;

 
 

-  windex = elt->index;
+  windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
+

   for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
     {
       /* Create new elements if they cannot be found.  */
       elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
       memset (elt->words, -1, sizeof (elt->words));
     }
   for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
     {
       /* Create new elements if they cannot be found.  */
       elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
       memset (elt->words, -1, sizeof (elt->words));
     }

+
+  lbitset_unused_clear (dst);

 }
 
 
 }
 
 


@@ -911,21 +946,20 @@ lbitset_not (bitset dst, bitset src)
   /* This is another unfriendly operation for a linked list
      bitset!  */
   elt = LBITSET_TAIL (dst);
   /* This is another unfriendly operation for a linked list
      bitset!  */
   elt = LBITSET_TAIL (dst);

-  /* Ignore empty set.  */
-  if (!elt)
-    return;

 
 

-  windex = elt->index;
+  windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
+

   for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
     {
       /* Create new elements for dst if they cannot be found
   for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
     {
       /* 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 = lbitset_elt_find (src, i, LBITSET_SUBST);
       delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)
       selt = lbitset_elt_find (src, i, LBITSET_SUBST);
       delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)

-       delt->words[j] = ~selt->words[j];
+        delt->words[j] = ~selt->words[j];

     }
     }

+  lbitset_unused_clear (dst);

   lbitset_weed (dst);
   return;
 }
   lbitset_weed (dst);
   return;
 }


@@ -943,26 +977,26 @@ lbitset_subset_p (bitset dst, bitset src)
        selt || delt; selt = selt->next, delt = delt->next)
     {
       if (!selt)
        selt || delt; selt = selt->next, delt = delt->next)
     {
       if (!selt)

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

       else if (!delt)
       else if (!delt)

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

       else if (selt->index != delt->index)
       else if (selt->index != delt->index)

-       {
-         if (selt->index < delt->index)
-           {
-             lbitset_zero_elts[2].next = delt;
-             delt = &lbitset_zero_elts[2];
-           }
-         else
-           {
-             lbitset_zero_elts[1].next = selt;
-             selt = &lbitset_zero_elts[1];
-           }
-       }
+        {
+          if (selt->index < delt->index)
+            {
+              lbitset_zero_elts[2].next = delt;
+              delt = &lbitset_zero_elts[2];
+            }
+          else
+            {
+              lbitset_zero_elts[1].next = selt;
+              selt = &lbitset_zero_elts[1];
+            }
+        }

 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)
 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)

-       if (delt->words[j] != (selt->words[j] | delt->words[j]))
-         return false;
+        if (delt->words[j] != (selt->words[j] | delt->words[j]))
+          return false;

     }
   return true;
 }
     }
   return true;
 }


@@ -980,25 +1014,25 @@ lbitset_disjoint_p (bitset dst, bitset src)
        selt && delt; selt = selt->next, delt = delt->next)
     {
       if (selt->index != delt->index)
        selt && delt; selt = selt->next, delt = delt->next)
     {
       if (selt->index != delt->index)

-       {
-         if (selt->index < delt->index)
-           {
-             lbitset_zero_elts[2].next = delt;
-             delt = &lbitset_zero_elts[2];
-           }
-         else
-           {
-             lbitset_zero_elts[1].next = selt;
-             selt = &lbitset_zero_elts[1];
-           }
-         /* Since the elements are different, there is no
-            intersection of these elements.  */
-         continue;
-       }
+        {
+          if (selt->index < delt->index)
+            {
+              lbitset_zero_elts[2].next = delt;
+              delt = &lbitset_zero_elts[2];
+            }
+          else
+            {
+              lbitset_zero_elts[1].next = selt;
+              selt = &lbitset_zero_elts[1];
+            }
+          /* Since the elements are different, there is no
+             intersection of these elements.  */
+          continue;
+        }

 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)
 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)

-       if (selt->words[j] & delt->words[j])
-         return false;
+        if (selt->words[j] & delt->words[j])
+          return false;

     }
   return true;
 }
     }
   return true;
 }


@@ -1031,124 +1065,124 @@ lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
   while (selt1 || selt2)
     {
       /* Figure out whether we need to substitute zero elements for
   while (selt1 || selt2)
     {
       /* Figure out whether we need to substitute zero elements for

-        missing links.  */
+         missing links.  */

       if (windex1 == windex2)
       if (windex1 == windex2)

-       {
-         windex = windex1;
-         stmp1 = selt1;
-         stmp2 = selt2;
-         selt1 = selt1->next;
-         windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
-         selt2 = selt2->next;
-         windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
-       }
+        {
+          windex = windex1;
+          stmp1 = selt1;
+          stmp2 = selt2;
+          selt1 = selt1->next;
+          windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+          selt2 = selt2->next;
+          windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
+        }

       else if (windex1 < windex2)
       else if (windex1 < windex2)

-       {
-         windex = windex1;
-         stmp1 = selt1;
-         stmp2 = &lbitset_zero_elts[0];
-         selt1 = selt1->next;
-         windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
-       }
+        {
+          windex = windex1;
+          stmp1 = selt1;
+          stmp2 = &lbitset_zero_elts[0];
+          selt1 = selt1->next;
+          windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+        }

       else
       else

-       {
-         windex = windex2;
-         stmp1 = &lbitset_zero_elts[0];
-         stmp2 = selt2;
-         selt2 = selt2->next;
-         windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
-       }
+        {
+          windex = windex2;
+          stmp1 = &lbitset_zero_elts[0];
+          stmp2 = selt2;
+          selt2 = selt2->next;
+          windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
+        }

 
       /* Find the appropriate element from DST.  Begin by discarding
 
       /* Find the appropriate element from DST.  Begin by discarding

-        elements that we've skipped.  */
+         elements that we've skipped.  */

       while (delt && delt->index < windex)
       while (delt && delt->index < windex)

-       {
-         changed = true;
-         dtmp = delt;
-         delt = delt->next;
-         lbitset_elt_free (dtmp);
-       }
+        {
+          changed = true;
+          dtmp = delt;
+          delt = delt->next;
+          lbitset_elt_free (dtmp);
+        }

       if (delt && delt->index == windex)
       if (delt && delt->index == windex)

-       {
-         dtmp = delt;
-         delt = delt->next;
-       }
+        {
+          dtmp = delt;
+          delt = delt->next;
+        }

       else
       else

-       dtmp = lbitset_elt_calloc ();
+        dtmp = lbitset_elt_calloc ();

 
       /* Do the operation, and if any bits are set, link it into the
 
       /* Do the operation, and if any bits are set, link it into the

-        linked list.  */
+         linked list.  */

       srcp1 = stmp1->words;
       srcp2 = stmp2->words;
       dstp = dtmp->words;
       switch (op)
       srcp1 = stmp1->words;
       srcp2 = stmp2->words;
       dstp = dtmp->words;
       switch (op)

-       {
-       case BITSET_OP_OR:
-         for (i = 0; i < LBITSET_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 < LBITSET_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 < LBITSET_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 < LBITSET_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 < LBITSET_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 < LBITSET_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 < LBITSET_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 < LBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ & ~(*srcp2++);
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+        }

 
       if (!lbitset_elt_zero_p (dtmp))
 
       if (!lbitset_elt_zero_p (dtmp))

-       {
-         dtmp->index = windex;
-         /* Perhaps this could be optimised...  */
-         lbitset_elt_link (dst, dtmp);
-       }
+        {
+          dtmp->index = windex;
+          /* Perhaps this could be optimised...  */
+          lbitset_elt_link (dst, dtmp);
+        }

       else
       else

-       {
-         lbitset_elt_free (dtmp);
-       }
+        {
+          lbitset_elt_free (dtmp);
+        }

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


@@ -1280,7 +1314,8 @@ struct bitset_vtable lbitset_vtable = {
   lbitset_reset,
   bitset_toggle_,
   lbitset_test,
   lbitset_reset,
   bitset_toggle_,
   lbitset_test,

-  lbitset_size,
+  lbitset_resize,
+  bitset_size_,

   bitset_count_,
   lbitset_empty_p,
   lbitset_ones,
   bitset_count_,
   lbitset_empty_p,
   lbitset_ones,


@@ -1323,6 +1358,7 @@ lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
 bitset
 lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
 {
 bitset
 lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
 {

+  BITSET_NBITS_ (bset) = n_bits;

   bset->b.vtable = &lbitset_vtable;
   return bset;
 }
   bset->b.vtable = &lbitset_vtable;
   return bset;
 }


@@ -1352,19 +1388,19 @@ debug_lbitset (bitset bset)
 
   for (elt = LBITSET_HEAD (bset); elt; elt = elt->next)
     {
 
   for (elt = LBITSET_HEAD (bset); elt; elt = elt->next)
     {

-      fprintf (stderr, "Elt %lu\n", (unsigned long) elt->index);
+      fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index);

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

-       {
-         unsigned int j;
-         bitset_word word;
-
-         word = elt->words[i];
-
-         fprintf (stderr, "  Word %u:", i);
-         for (j = 0; j < LBITSET_WORD_BITS; j++)
-           if ((word & ((bitset_word) 1 << j)))
-             fprintf (stderr, " %u", j);
-         fprintf (stderr, "\n");
-       }
+        {
+          unsigned int j;
+          bitset_word word;
+
+          word = elt->words[i];
+
+          fprintf (stderr, "  Word %u:", i);
+          for (j = 0; j < LBITSET_WORD_BITS; j++)
+            if ((word & ((bitset_word) 1 << j)))
+              fprintf (stderr, " %u", j);
+          fprintf (stderr, "\n");
+        }

     }
 }
     }
 }