Finer input type for yytranslate.

[bison.git] / lib / lbitset.c

diff --git a/lib/lbitset.c b/lib/lbitset.c
index f426c3010527e4141fac33a815c9042a2a6e06ae..9a6fc0aeebdf1dd0f7a4adfb4afa06fd942fdb21 100644 (file)
--- a/lib/lbitset.c
+++ b/lib/lbitset.c
@@ -1,10 +1,10 @@
 /* Functions to support link list bitsets.
 /* Functions to support link list bitsets.

-   Copyright (C) 2002 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003, 2004, 2006 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 +13,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 "obstack.h"

+#include <stddef.h>

 #include <stdlib.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


@@ -38,11 +38,12 @@
 /* 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.  */

 
 

-#ifndef LBITSET_ELT_WORDS

 #define LBITSET_ELT_WORDS 2
 #define LBITSET_ELT_WORDS 2

-#endif

 
 typedef bitset_word lbitset_word;
 
 
 typedef bitset_word lbitset_word;
 


@@ -50,7 +51,7 @@ 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.  */
 
 /* Lbitset element.   We use an array of bits for each element.
    These are linked together in a doubly-linked list.  */


@@ -64,22 +65,6 @@ typedef struct lbitset_elt_struct
 lbitset_elt;
 
 
 lbitset_elt;
 
 

-/* Head of lbitset linked list.  */
-typedef struct lbitset_struct
-{
-  lbitset_elt *head;           /* First element in linked list.  */
-  lbitset_elt *tail;           /* Last element in linked list.  */
-}
-*lbitset;
-
-
-struct bitset_struct
-{
-  struct bbitset_struct b;
-  struct lbitset_struct l;
-};
-
-

 enum lbitset_find_mode
   { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
 
 enum lbitset_find_mode
   { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
 


@@ -87,39 +72,13 @@ static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits.  */
 
 /* Obstack to allocate bitset elements from.  */
 static struct obstack lbitset_obstack;
 
 /* Obstack to allocate bitset elements from.  */
 static struct obstack lbitset_obstack;

-static int lbitset_obstack_init = 0;
+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.  */
 

-static lbitset_elt *lbitset_elt_alloc PARAMS ((void));
-static lbitset_elt *lbitset_elt_calloc PARAMS ((void));
-static void lbitset_elt_link PARAMS ((bitset, lbitset_elt *));
-static void lbitset_elt_unlink PARAMS ((bitset, lbitset_elt *));
-static void lbitset_elt_free PARAMS ((lbitset_elt *));
-static lbitset_elt *lbitset_elt_find PARAMS ((bitset, bitset_windex,
-                                             enum lbitset_find_mode));
-static int lbitset_elt_zero_p PARAMS ((lbitset_elt *));
-
-static void lbitset_prune PARAMS ((bitset, lbitset_elt *));
-static void lbitset_weed PARAMS ((bitset));
-static void lbitset_zero PARAMS ((bitset));
-static int lbitset_equal_p PARAMS ((bitset, bitset));
-static void lbitset_copy PARAMS ((bitset, bitset));
-static int lbitset_copy_compare PARAMS ((bitset, bitset));
-static void lbitset_set PARAMS ((bitset, bitset_bindex));
-static void lbitset_reset PARAMS ((bitset, bitset_bindex));
-static int lbitset_test PARAMS ((bitset, bitset_bindex));
-static int lbitset_size PARAMS ((bitset));
-static int lbitset_op1 PARAMS ((bitset, enum bitset_ops));
-static int lbitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
-static int lbitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
-static int lbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
-                                bitset_bindex *));
-static int lbitset_reverse_list
-PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
-static void lbitset_free PARAMS ((bitset));
-
-
-#define LBITSET_CURRENT1(X) (lbitset_elt *)((char *)(X) + ((char *)&(((lbitset_elt *)(X))->next) - (char *)&(((lbitset_elt *)(X))->words)))
+extern void debug_lbitset (bitset);
+
+#define LBITSET_CURRENT1(X) \
+  ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))

 
 #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
 
 
 #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
 


@@ -128,7 +87,7 @@ static void lbitset_free PARAMS ((bitset));
 
 /* Allocate a lbitset element.  The bits are not cleared.  */
 static inline lbitset_elt *
 
 /* Allocate a lbitset element.  The bits are not cleared.  */
 static inline lbitset_elt *

-lbitset_elt_alloc ()
+lbitset_elt_alloc (void)

 {
   lbitset_elt *elt;
 
 {
   lbitset_elt *elt;
 


@@ -139,12 +98,9 @@ lbitset_elt_alloc ()
     }
   else
     {
     }
   else
     {

-      /* We can't use gcc_obstack_init to initialize the obstack since
-        print-rtl.c now calls bitset functions, and bitset is linked
-        into the gen* functions.  */

       if (!lbitset_obstack_init)
        {
       if (!lbitset_obstack_init)
        {

-         lbitset_obstack_init = 1;
+         lbitset_obstack_init = true;

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


@@ -162,15 +118,13 @@ lbitset_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
 
          obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
                                      __alignof__ (lbitset_elt),
 #define __alignof__(type) 0
 #endif
 
          obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
                                      __alignof__ (lbitset_elt),

-                                     (void *(*)PARAMS ((long)))

                                      OBSTACK_CHUNK_ALLOC,
                                      OBSTACK_CHUNK_ALLOC,

-                                     (void (*)PARAMS ((void *)))

                                      OBSTACK_CHUNK_FREE);
        }
 
                                      OBSTACK_CHUNK_FREE);
        }
 


@@ -184,9 +138,9 @@ lbitset_elt_alloc ()
 }
 
 
 }
 
 

-/* Allocate a lbitset element.  The bits are not cleared.  */
+/* Allocate a lbitset element.  The bits are cleared.  */

 static inline lbitset_elt *
 static inline lbitset_elt *

-lbitset_elt_calloc ()
+lbitset_elt_calloc (void)

 {
   lbitset_elt *elt;
 
 {
   lbitset_elt *elt;
 


@@ -197,8 +151,7 @@ lbitset_elt_calloc ()
 
 
 static inline void
 
 
 static inline void

-lbitset_elt_free (elt)
-     lbitset_elt *elt;
+lbitset_elt_free (lbitset_elt *elt)

 {
   elt->next = lbitset_free_list;
   lbitset_free_list = elt;
 {
   elt->next = lbitset_free_list;
   lbitset_free_list = elt;


@@ -207,9 +160,7 @@ lbitset_elt_free (elt)
 
 /* Unlink element ELT from bitset BSET.  */
 static inline void
 
 /* Unlink element ELT from bitset BSET.  */
 static inline void

-lbitset_elt_unlink (bset, elt)
-     bitset bset;
-     lbitset_elt *elt;
+lbitset_elt_unlink (bitset bset, lbitset_elt *elt)

 {
   lbitset_elt *next = elt->next;
   lbitset_elt *prev = elt->prev;
 {
   lbitset_elt *next = elt->next;
   lbitset_elt *prev = elt->prev;


@@ -254,9 +205,7 @@ lbitset_elt_unlink (bset, elt)
 /* Cut the chain of bitset BSET before element ELT and free the
    elements.  */
 static inline void
 /* Cut the chain of bitset BSET before element ELT and free the
    elements.  */
 static inline void

-lbitset_prune (bset, elt)
-     bitset bset;
-     lbitset_elt *elt;
+lbitset_prune (bitset bset, lbitset_elt *elt)

 {
   lbitset_elt *next;
 
 {
   lbitset_elt *next;
 


@@ -286,26 +235,23 @@ lbitset_prune (bset, elt)
 }
 
 
 }
 
 

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

 {
   int i;
 
   for (i = 0; i < LBITSET_ELT_WORDS; i++)
     if (elt->words[i])
 {
   int i;
 
   for (i = 0; i < LBITSET_ELT_WORDS; i++)
     if (elt->words[i])

-      return 0;
+      return false;

 
 

-  return 1;
+  return true;

 }
 
 
 /* Link the bitset element into the current bitset linked list.  */
 static inline void
 }
 
 
 /* Link the bitset element into the current bitset linked list.  */
 static inline void

-lbitset_elt_link (bset, elt)
-     bitset bset;
-     lbitset_elt *elt;
+lbitset_elt_link (bitset bset, lbitset_elt *elt)

 {
   bitset_windex windex = elt->index;
   lbitset_elt *ptr;
 {
   bitset_windex windex = elt->index;
   lbitset_elt *ptr;


@@ -367,10 +313,8 @@ lbitset_elt_link (bset, elt)
 
 
 static lbitset_elt *
 
 
 static lbitset_elt *

-lbitset_elt_find (bset, windex, mode)
-     bitset bset;
-     bitset_windex windex;
-     enum lbitset_find_mode mode;
+lbitset_elt_find (bitset bset, bitset_windex windex,
+                 enum lbitset_find_mode mode)

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


@@ -403,7 +347,7 @@ lbitset_elt_find (bset, windex, mode)
            continue;
        }
 
            continue;
        }
 

-      /* `element' 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.  */
       if (elt && (windex - elt->index) < LBITSET_ELT_WORDS)
        {
         we want, the one we want does not exist.  */
       if (elt && (windex - elt->index) < LBITSET_ELT_WORDS)
        {


@@ -416,11 +360,14 @@ lbitset_elt_find (bset, windex, mode)
 
   switch (mode)
     {
 
   switch (mode)
     {

+    default:
+      abort ();
+

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

-      windex = (windex / (unsigned) LBITSET_ELT_WORDS) * LBITSET_ELT_WORDS;
+      windex -= windex % LBITSET_ELT_WORDS;

 
       elt = lbitset_elt_calloc ();
       elt->index = windex;
 
       elt = lbitset_elt_calloc ();
       elt->index = windex;


@@ -429,17 +376,13 @@ lbitset_elt_find (bset, windex, mode)
 
     case LBITSET_SUBST:
       return &lbitset_zero_elts[0];
 
     case LBITSET_SUBST:
       return &lbitset_zero_elts[0];

-
-    default:
-      abort ();

     }
 }
 
 
 /* Weed out the zero elements from the list.  */
 static inline void
     }
 }
 
 
 /* Weed out the zero elements from the list.  */
 static inline void

-lbitset_weed (bset)
-     bitset bset;
+lbitset_weed (bitset bset)

 {
   lbitset_elt *elt;
   lbitset_elt *next;
 {
   lbitset_elt *elt;
   lbitset_elt *next;


@@ -454,9 +397,8 @@ lbitset_weed (bset)
 
 
 /* Set all bits in the bitset to zero.  */
 
 
 /* Set all bits in the bitset to zero.  */

-static inline void
-lbitset_zero (bset)
-     bitset bset;
+static void
+lbitset_zero (bitset bset)

 {
   lbitset_elt *head;
 
 {
   lbitset_elt *head;
 


@@ -469,17 +411,16 @@ lbitset_zero (bset)
 }
 
 
 }
 
 

-static inline int
-lbitset_equal_p (dst, src)
-     bitset dst;
-     bitset src;
+/* Is DST == SRC?  */
+static inline bool
+lbitset_equal_p (bitset dst, bitset src)

 {
   lbitset_elt *selt;
   lbitset_elt *delt;
   int j;
 
   if (src == dst)
 {
   lbitset_elt *selt;
   lbitset_elt *delt;
   int j;
 
   if (src == dst)

-    return 1;
+    return true;

 
   lbitset_weed (src);
   lbitset_weed (dst);
 
   lbitset_weed (src);
   lbitset_weed (dst);


@@ -487,11 +428,11 @@ lbitset_equal_p (dst, 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 0;
+       return false;

 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)
        if (delt->words[j] != selt->words[j])
 
       for (j = 0; j < LBITSET_ELT_WORDS; j++)
        if (delt->words[j] != selt->words[j])

-         return 0;
+         return false;

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


@@ -499,9 +440,7 @@ lbitset_equal_p (dst, src)
 
 /* Copy bits from bitset SRC to bitset DST.  */
 static inline void
 
 /* Copy bits from bitset SRC to bitset DST.  */
 static inline void

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

 {
   lbitset_elt *elt;
   lbitset_elt *head;
 {
   lbitset_elt *elt;
   lbitset_elt *head;


@@ -540,15 +479,13 @@ lbitset_copy (dst, src)
 }
 
 
 }
 
 

-/* 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
-lbitset_copy_compare (dst, src)
-     bitset dst;
-     bitset src;
+static inline bool
+lbitset_copy_cmp (bitset dst, bitset src)

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

-    return 0;
+    return false;

 
   if (!LBITSET_HEAD (dst))
     {
 
   if (!LBITSET_HEAD (dst))
     {


@@ -557,79 +494,66 @@ lbitset_copy_compare (dst, src)
     }
 
   if (lbitset_equal_p (dst, src))
     }
 
   if (lbitset_equal_p (dst, src))

-    return 0;
+    return false;

 
   lbitset_copy (dst, src);
 
   lbitset_copy (dst, src);

-  return 1;
+  return true;

 }
 
 
 }
 
 

-/* Return size in bits of bitset SRC.  */
-static int
-lbitset_size (src)
-     bitset src;
+static bitset_bindex
+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
 /* Set bit BITNO in bitset DST.  */
 static void

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

 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
   lbitset_elt_find (dst, windex, LBITSET_CREATE);
 
 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
   lbitset_elt_find (dst, windex, LBITSET_CREATE);
 

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

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

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

 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
   if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
     return;
 
 {
   bitset_windex windex = bitno / BITSET_WORD_BITS;
 
   if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
     return;
 

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

 
   /* If all the data is zero, perhaps we should unlink it now...  */
 }
 
 
 /* Test bit BITNO in bitset SRC.  */
 
   /* If all the data is zero, perhaps we should unlink it now...  */
 }
 
 
 /* Test bit BITNO in bitset SRC.  */

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

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

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

 }
 
 
 static void
 }
 
 
 static void

-lbitset_free (bset)
-     bitset bset;
+lbitset_free (bitset bset)

 {
   lbitset_zero (bset);
 }
 {
   lbitset_zero (bset);
 }


@@ -638,12 +562,9 @@ lbitset_free (bset)
 /* Find list of up to NUM bits set in BSET starting from and including
  *NEXT and store in array LIST.  Return with actual number of bits
  found and with *NEXT indicating where search stopped.  */
 /* Find list of up to NUM bits set in BSET starting from and including
  *NEXT and store in array LIST.  Return with actual number of bits
  found and with *NEXT indicating where search stopped.  */

-static int
-lbitset_reverse_list (bset, list, num, next)
-     bitset bset;
-     bitset_bindex *list;
-     bitset_bindex num;
-     bitset_bindex *next;
+static bitset_bindex
+lbitset_list_reverse (bitset bset, bitset_bindex *list,
+                     bitset_bindex num, bitset_bindex *next)

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


@@ -676,13 +597,24 @@ lbitset_reverse_list (bset, list, num, next)
   if (!elt)
     return 0;
 
   if (!elt)
     return 0;
 

-  /* If num is 1, we could speed things up with a binary search
-     of the word of interest.  */
+  if (windex >= elt->index + LBITSET_ELT_WORDS)
+    {
+      /* We are trying to start in no-mans land so start
+        at end of current elt.  */
+      bcount = BITSET_WORD_BITS - 1;
+      windex = elt->index + LBITSET_ELT_WORDS - 1;
+    }
+  else
+    {
+      bcount = bitno % BITSET_WORD_BITS;
+    }

 
   count = 0;
 
   count = 0;

-  bcount = bitno % BITSET_WORD_BITS;

   boffset = windex * BITSET_WORD_BITS;
 
   boffset = windex * BITSET_WORD_BITS;
 

+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+

   while (elt)
     {
       bitset_word *srcp = elt->words;
   while (elt)
     {
       bitset_word *srcp = elt->words;


@@ -725,12 +657,9 @@ lbitset_reverse_list (bset, list, num, next)
 /* Find list of up to NUM bits set in BSET starting from and including
  *NEXT and store in array LIST.  Return with actual number of bits
  found and with *NEXT indicating where search stopped.  */
 /* Find list of up to NUM bits set in BSET starting from and including
  *NEXT and store in array LIST.  Return with actual number of bits
  found and with *NEXT indicating where search stopped.  */

-static int
-lbitset_list (bset, list, num, next)
-     bitset bset;
-     bitset_bindex *list;
-     bitset_bindex num;
-     bitset_bindex *next;
+static bitset_bindex
+lbitset_list (bitset bset, bitset_bindex *list,
+             bitset_bindex num, bitset_bindex *next)

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


@@ -928,169 +857,186 @@ lbitset_list (bset, list, num, next)
 }
 
 
 }
 
 

-static int
-lbitset_op1 (dst, op)
-     bitset dst;
-     enum bitset_ops op;
+static bool
+lbitset_empty_p (bitset dst)

 {
 {

-  unsigned int i;
-  bitset_windex windex;

   lbitset_elt *elt;
   lbitset_elt *elt;

+  lbitset_elt *next;

 
 

-  switch (op)
+  for (elt = LBITSET_HEAD (dst); elt; elt = next)

     {
     {

-    case BITSET_OP_ZERO:
-      lbitset_zero (dst);
-      break;
+      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;

 
 

-    case BITSET_OP_ONES:
-      /* This is a decidedly unfriendly operation for a linked list
-        bitset!   */

       elt = LBITSET_TAIL (dst);
       elt = LBITSET_TAIL (dst);

-      /* Ignore empty set.  */
-      if (!elt)
-       return 0;
+      srcp = elt->words;
+      windex = n_bits / BITSET_WORD_BITS;

 
 

-      windex = elt->index;
-      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, ~0, sizeof (elt->words));
-       }
-      break;
+      srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1;
+      windex++;

 
 

-    case BITSET_OP_EMPTY_P:
-      lbitset_weed (dst);
-      if (LBITSET_HEAD (dst))
-       return 0;
-      break;
+      for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
+       srcp[windex - elt->index] = 0;
+    }
+}

 
 

-    default:
-      abort ();
+
+static void
+lbitset_ones (bitset dst)
+{
+  bitset_windex i;
+  bitset_windex windex;
+  lbitset_elt *elt;
+
+  /* This is a decidedly unfriendly operation for a linked list
+      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.  */
+
+  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));

     }
 
     }
 

-  return 1;
+  lbitset_unused_clear (dst);

 }
 
 
 }
 
 

-static int
-lbitset_op2 (dst, src, op)
-     bitset dst;
-     bitset src;
-     enum bitset_ops op;
+static void
+lbitset_not (bitset dst, bitset src)

 {
   lbitset_elt *elt;
   lbitset_elt *selt;
   lbitset_elt *delt;
 {
   lbitset_elt *elt;
   lbitset_elt *selt;
   lbitset_elt *delt;

-  unsigned int i;
+  bitset_windex i;

   unsigned int j;
   bitset_windex windex;
 
   unsigned int j;
   bitset_windex windex;
 

-  switch (op)
-    {
-    case BITSET_OP_COPY:
-      lbitset_copy (dst, src);
-      break;
+  /* This is another unfriendly operation for a linked list
+     bitset!  */
+  elt = LBITSET_TAIL (dst);

 
 

-    case BITSET_OP_NOT:
-      /* This is another unfriendly operation for a linked list
-        bitset!  */
-      elt = LBITSET_TAIL (dst);
-      /* Ignore empty set.  */
-      if (!elt)
-       return 0;
+  windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;

 
 

-      windex = elt->index;
-      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.  */
-         selt = lbitset_elt_find (dst, i, LBITSET_SUBST);
-         delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+  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.  */
+      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];
+    }
+  lbitset_unused_clear (dst);
+  lbitset_weed (dst);
+  return;
+}

 
 

-         for (j = 0; j < LBITSET_ELT_WORDS; j++)
-           delt->words[j] = ~selt->words[j];
-       }
-      lbitset_weed (dst);
-      break;

 
 

-      /* Return 1 if DST == SRC.  */
-    case BITSET_OP_EQUAL_P:
-      return lbitset_equal_p (dst, src);
-      break;
+/* Is DST == DST | SRC?  */
+static bool
+lbitset_subset_p (bitset dst, bitset src)
+{
+  lbitset_elt *selt;
+  lbitset_elt *delt;
+  unsigned int j;

 
 

-      /* Return 1 if DST == DST | SRC.  */
-    case BITSET_OP_SUBSET_P:
-      for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
-          selt || delt; selt = selt->next, delt = delt->next)
+  for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
+       selt || delt; selt = selt->next, delt = delt->next)
+    {
+      if (!selt)
+       selt = &lbitset_zero_elts[0];
+      else if (!delt)
+       delt = &lbitset_zero_elts[0];
+      else if (selt->index != delt->index)

        {
        {

-         if (!selt)
-           selt = &lbitset_zero_elts[0];
-         else if (!delt)
-           delt = &lbitset_zero_elts[0];
-         else if (selt->index != delt->index)
+         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];
-               }
+             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++)
-           if (delt->words[j] != (selt->words[j] | delt->words[j]))
-             return 0;

        }
        }

-      break;

 
 

-      /* Return 1 if DST & SRC == 0.  */
-    case BITSET_OP_DISJOINT_P:
-      for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
-          selt && delt; selt = selt->next, delt = delt->next)
+      for (j = 0; j < LBITSET_ELT_WORDS; j++)
+       if (delt->words[j] != (selt->words[j] | delt->words[j]))
+         return false;
+    }
+  return true;
+}
+
+
+/* Is DST & SRC == 0?  */
+static bool
+lbitset_disjoint_p (bitset dst, bitset src)
+{
+  lbitset_elt *selt;
+  lbitset_elt *delt;
+  unsigned int j;
+
+  for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
+       selt && delt; selt = selt->next, delt = delt->next)
+    {
+      if (selt->index != delt->index)

        {
        {

-         if (selt->index != delt->index)
+         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;
+             lbitset_zero_elts[2].next = delt;
+             delt = &lbitset_zero_elts[2];

            }
            }

-
-         for (j = 0; j < LBITSET_ELT_WORDS; j++)
-           if (selt->words[j] & delt->words[j])
-             return 0;
+         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;

        }
        }

-      break;

 
 

-    default:
-      abort ();
+      for (j = 0; j < LBITSET_ELT_WORDS; j++)
+       if (selt->words[j] & delt->words[j])
+         return false;

     }
     }

-
-  return 1;
+  return true;

 }
 
 
 }
 
 

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

 {
   lbitset_elt *selt1 = LBITSET_HEAD (src1);
   lbitset_elt *selt2 = LBITSET_HEAD (src2);
 {
   lbitset_elt *selt1 = LBITSET_HEAD (src1);
   lbitset_elt *selt2 = LBITSET_HEAD (src2);


@@ -1104,45 +1050,14 @@ lbitset_op3 (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;
 
   unsigned int i;
 

-  /* Fast track common, simple cases.  */
-  if (!selt2)
-    {
-      if (op == BITSET_OP_AND)
-       {
-         lbitset_weed (dst);
-         changed = !LBITSET_HEAD (dst);
-         lbitset_zero (dst);
-         return changed;
-       }
-      else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR
-              || op == BITSET_OP_XOR)
-       {
-         return lbitset_copy_compare (dst, src1);
-       }
-    }
-  else if (!selt1)
-    {
-      if (op == BITSET_OP_AND || op == BITSET_OP_ANDN)
-       {
-         lbitset_weed (dst);
-         changed = !LBITSET_HEAD (dst);
-         lbitset_zero (dst);
-         return changed;
-       }
-      else if (op == BITSET_OP_OR || op == BITSET_OP_XOR)
-       {
-         return lbitset_copy_compare (dst, src2);
-       }
-    }
-

   LBITSET_HEAD (dst) = 0;
   dst->b.csize = 0;
 
   LBITSET_HEAD (dst) = 0;
   dst->b.csize = 0;
 

-  windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
-  windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
+  windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+  windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;

 
   while (selt1 || selt2)
     {
 
   while (selt1 || selt2)
     {


@@ -1154,9 +1069,9 @@ lbitset_op3 (dst, src1, src2, op)
          stmp1 = selt1;
          stmp2 = selt2;
          selt1 = selt1->next;
          stmp1 = selt1;
          stmp2 = selt2;
          selt1 = selt1->next;

-         windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
+         windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;

          selt2 = selt2->next;
          selt2 = selt2->next;

-         windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
+         windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;

        }
       else if (windex1 < windex2)
        {
        }
       else if (windex1 < windex2)
        {


@@ -1164,7 +1079,7 @@ lbitset_op3 (dst, src1, src2, op)
          stmp1 = selt1;
          stmp2 = &lbitset_zero_elts[0];
          selt1 = selt1->next;
          stmp1 = selt1;
          stmp2 = &lbitset_zero_elts[0];
          selt1 = selt1->next;

-         windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
+         windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;

        }
       else
        {
        }
       else
        {


@@ -1172,14 +1087,14 @@ lbitset_op3 (dst, src1, src2, op)
          stmp1 = &lbitset_zero_elts[0];
          stmp2 = selt2;
          selt2 = selt2->next;
          stmp1 = &lbitset_zero_elts[0];
          stmp2 = selt2;
          selt2 = selt2->next;

-         windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
+         windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;

        }
 
       /* Find the appropriate element from DST.  Begin by discarding
         elements that we've skipped.  */
       while (delt && delt->index < windex)
        {
        }
 
       /* Find the appropriate element from DST.  Begin by discarding
         elements that we've skipped.  */
       while (delt && delt->index < windex)
        {

-         changed = 1;
+         changed = true;

          dtmp = delt;
          delt = delt->next;
          lbitset_elt_free (dtmp);
          dtmp = delt;
          delt = delt->next;
          lbitset_elt_free (dtmp);


@@ -1199,6 +1114,9 @@ lbitset_op3 (dst, src1, src2, op)
       dstp = dtmp->words;
       switch (op)
        {
       dstp = dtmp->words;
       switch (op)
        {

+       default:
+         abort ();
+

        case BITSET_OP_OR:
          for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
            {
        case BITSET_OP_OR:
          for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
            {


@@ -1206,7 +1124,7 @@ lbitset_op3 (dst, src1, src2, op)
 
              if (*dstp != tmp)
                {
 
              if (*dstp != tmp)
                {

-                 changed = 1;
+                 changed = true;

                  *dstp = tmp;
                }
            }
                  *dstp = tmp;
                }
            }


@@ -1219,7 +1137,7 @@ lbitset_op3 (dst, src1, src2, op)
 
              if (*dstp != tmp)
                {
 
              if (*dstp != tmp)
                {

-                 changed = 1;
+                 changed = true;

                  *dstp = tmp;
                }
            }
                  *dstp = tmp;
                }
            }


@@ -1232,7 +1150,7 @@ lbitset_op3 (dst, src1, src2, op)
 
              if (*dstp != tmp)
                {
 
              if (*dstp != tmp)
                {

-                 changed = 1;
+                 changed = true;

                  *dstp = tmp;
                }
            }
                  *dstp = tmp;
                }
            }


@@ -1245,14 +1163,11 @@ lbitset_op3 (dst, src1, src2, op)
 
              if (*dstp != tmp)
                {
 
              if (*dstp != tmp)
                {

-                 changed = 1;
+                 changed = true;

                  *dstp = tmp;
                }
            }
          break;
                  *dstp = tmp;
                }
            }
          break;

-
-       default:
-         abort ();

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


@@ -1270,7 +1185,7 @@ lbitset_op3 (dst, src1, src2, op)
   /* If we have elements of DST left over, free them all.  */
   if (delt)
     {
   /* If we have elements of DST left over, free them all.  */
   if (delt)
     {

-      changed = 1;
+      changed = true;

       lbitset_prune (dst, delt);
     }
 
       lbitset_prune (dst, delt);
     }
 


@@ -1278,51 +1193,211 @@ lbitset_op3 (dst, src1, src2, op)
 }
 
 
 }
 
 

+static bool
+lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+  bool changed;
+
+  if (!selt2)
+    {
+      lbitset_weed (dst);
+      changed = !LBITSET_HEAD (dst);
+      lbitset_zero (dst);
+      return changed;
+    }
+  else if (!selt1)
+    {
+      lbitset_weed (dst);
+      changed = !LBITSET_HEAD (dst);
+      lbitset_zero (dst);
+      return changed;
+    }
+  return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
+}
+
+
+static void
+lbitset_and (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_and_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+  bool changed;
+
+  if (!selt2)
+    {
+      return lbitset_copy_cmp (dst, src1);
+    }
+  else if (!selt1)
+    {
+      lbitset_weed (dst);
+      changed = !LBITSET_HEAD (dst);
+      lbitset_zero (dst);
+      return changed;
+    }
+  return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
+}
+
+
+static void
+lbitset_andn (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_andn_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+  if (!selt2)
+    {
+      return lbitset_copy_cmp (dst, src1);
+    }
+  else if (!selt1)
+    {
+      return lbitset_copy_cmp (dst, src2);
+    }
+  return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
+}
+
+
+static void
+lbitset_or (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_or_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+  if (!selt2)
+    {
+      return lbitset_copy_cmp (dst, src1);
+    }
+  else if (!selt1)
+    {
+      return lbitset_copy_cmp (dst, src2);
+    }
+  return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
+}
+
+
+static void
+lbitset_xor (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_xor_cmp (dst, src1, src2);
+}
+
+
+

 /* Vector of operations for linked-list bitsets.  */
 /* Vector of operations for linked-list bitsets.  */

-struct bitset_ops_struct lbitset_ops = {
+struct bitset_vtable lbitset_vtable = {

   lbitset_set,
   lbitset_reset,
   lbitset_set,
   lbitset_reset,

+  bitset_toggle_,

   lbitset_test,
   lbitset_test,

-  lbitset_size,
-  lbitset_op1,
-  lbitset_op2,
-  lbitset_op3,
-  bitset_op4,
+  lbitset_resize,
+  bitset_size_,
+  bitset_count_,
+  lbitset_empty_p,
+  lbitset_ones,
+  lbitset_zero,
+  lbitset_copy,
+  lbitset_disjoint_p,
+  lbitset_equal_p,
+  lbitset_not,
+  lbitset_subset_p,
+  lbitset_and,
+  lbitset_and_cmp,
+  lbitset_andn,
+  lbitset_andn_cmp,
+  lbitset_or,
+  lbitset_or_cmp,
+  lbitset_xor,
+  lbitset_xor_cmp,
+  bitset_and_or_,
+  bitset_and_or_cmp_,
+  bitset_andn_or_,
+  bitset_andn_or_cmp_,
+  bitset_or_and_,
+  bitset_or_and_cmp_,

   lbitset_list,
   lbitset_list,

-  lbitset_reverse_list,
+  lbitset_list_reverse,

   lbitset_free,
   BITSET_LIST
 };
 
 
 /* Return size of initial structure.  */
   lbitset_free,
   BITSET_LIST
 };
 
 
 /* Return size of initial structure.  */

-int
-lbitset_bytes (n_bits)
-     bitset_bindex n_bits ATTRIBUTE_UNUSED;
+size_t
+lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)

 {
 {

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

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

-

 bitset
 bitset

-lbitset_init (bset, n_bits)
-     bitset bset;
-     bitset_bindex n_bits ATTRIBUTE_UNUSED;
+lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)

 {
 {

-  bset->b.ops = &lbitset_ops;
+  BITSET_NBITS_ (bset) = n_bits;
+  bset->b.vtable = &lbitset_vtable;

   return bset;
 }
 
 
 void
   return bset;
 }
 
 
 void

-lbitset_release_memory ()
+lbitset_release_memory (void)

 {
   lbitset_free_list = 0;
   if (lbitset_obstack_init)
     {
 {
   lbitset_free_list = 0;
   if (lbitset_obstack_init)
     {

-      lbitset_obstack_init = 0;
+      lbitset_obstack_init = false;

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

+
+
+/* Function to be called from debugger to debug lbitset.  */
+void
+debug_lbitset (bitset bset)
+{
+  lbitset_elt *elt;
+  unsigned int i;
+
+  if (!bset)
+    return;
+
+  for (elt = LBITSET_HEAD (bset); elt; elt = elt->next)
+    {
+      fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index);
+      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");
+       }
+    }
+}