[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Bitsets
|
From: |
Paul Eggert |
|
Subject: |
Re: Bitsets |
|
Date: |
01 Jul 2003 16:27:18 -0700 |
|
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.3 |
According to the mail.gnu.org archive I forgot to issue a formal
report on the bitset updates to bison-patches. Sorry about that. So,
here is the patch to Bison that I installed on June 17 to merge to the
new bitset version that Michael Hayes released last month. This patch
is a companion to
<http://mail.gnu.org/archive/html/bison-patches/2003-06/msg00034.html>,
which reports the changes I made to libbitset in order to do the
merge.
2003-06-17 Paul Eggert <address@hidden>
* lib/bbitset.h: Do not include config.h; that's the includer's job.
Do not include <sys/types.h>; shouldn't be needed on a C89 host.
* lib/bitset.h (bitset_compatible_p): Indent as per GNU standard.
Don't use 'index' in comments, as it's a builtin fn on some hosts.
* lib/bitset_stats.c: Include gettext.h unconditionally, as
per recent gettext manual's suggestion.
* lib/ebitset.c (ebitset_resize, ebitset_unused_clear):
Use prototypes, not old-style definitions.
* lib/lbitset.c (lbitset_unused_clear): Likewise.
* lib/vbitset.c (vbitset_resize, vbitset_ones, vbitset_zero,
vbitset_empty_p, vbitset_copy1, vbitset_not, vbitset_equal_p,
vbitset_subset_p, vbitset_disjoint_p, vbitset_and, vbitset_and_cmp,
vbitset_andn, vbitset_andn_cmp, vbitset_or, vbitset_or_cmp,
vbitset_xor, vbitset_xor_cmp, vbitset_and_or, vbitset_and_or_cmp,
vbitset_andn_or, vbitset_andn_or_cmp, vbitset_or_and,
vbitset_or_and_cmp, vbitset_copy): Likewise.
* lib/libiberty.h: Do not include config.h; that's the includer's job.
Do not include <stdlib.h>.
(PARAMS): Define unconditionally for C89.
(ATTRIBUTE_NORETURN): Remove.
(ATTRIBUTE_UNUSED): Define unconditionally.
Upgrade to 2003-06-08 libbitset, submitted by Michael Hayes in:
<http://mail.gnu.org/archive/html/bison-patches/2003-06/msg00005.html>
* lib/Makefile.am (bitsets_sources): Add vbitset.c, vbitset.h.
* lib/vbitset.c, lib/vbitset.h: New files.
* lib/abitset.c, lib/bbitset.h, lib/bitset.c, lib/bitset.h,
lib/bitset_stats.c, lib/ebitset.c, lib/lbitset.c: Import
from libbitset.
Index: lib/Makefile.am
===================================================================
RCS file: /cvsroot/bison/bison/lib/Makefile.am,v
retrieving revision 1.40
diff -p -u -r1.40 Makefile.am
--- lib/Makefile.am 16 Jun 2003 19:41:37 -0000 1.40
+++ lib/Makefile.am 17 Jun 2003 07:11:40 -0000
@@ -56,10 +56,9 @@ libbison_a_SOURCES = \
# Implementation of bitsets
bitsets_sources = \
-libiberty.h \
-abitset.c bitset.c bitset_stats.h ebitset.c lbitset.h \
-abitset.h bitset.h bitsetv.c ebitset.h \
-bbitset.h bitset_stats.c bitsetv.h lbitset.c
+ abitset.c abitset.h bbitset.h bitset.c bitset.h bitset_stats.c \
+ bitset_stats.h bitsetv.c bitsetv.h ebitset.c ebitset.h lbitset.c \
+ lbitset.h libiberty.h vbitset.c vbitset.h
# Additional bitset operations.
additional_bitsets_sources = \
Index: lib/abitset.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/abitset.c,v
retrieving revision 1.7
diff -p -u -r1.7 abitset.c
--- lib/abitset.c 24 May 2003 19:16:02 -0000 1.7
+++ lib/abitset.c 17 Jun 2003 07:11:40 -0000
@@ -31,16 +31,18 @@
#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
#define ABITSET_WORDS(X) ((X)->a.words)
-#define ABITSET_N_BITS(X) ((X)->a.n_bits)
-/* Return size in bits of bitset SRC. */
static bitset_bindex
-abitset_size (bitset src)
+abitset_resize (bitset src ATTRIBUTE_UNUSED,
+ bitset_bindex size ATTRIBUTE_UNUSED)
{
- return ABITSET_N_BITS (src);
-}
+ if (BITSET_SIZE_ (src) == size)
+ return size;
+ /* These bitsets have a fixed size. */
+ abort ();
+}
/* Find list of up to NUM bits set in BSET starting from and including
*NEXT and store in array LIST. Return with actual number of bits
@@ -60,7 +62,7 @@ abitset_small_list (bitset src, bitset_b
if (!word)
return 0;
- size = ABITSET_N_BITS (src);
+ size = BITSET_SIZE_ (src);
bitno = *next;
if (bitno >= size)
return 0;
@@ -105,8 +107,9 @@ abitset_small_list (bitset src, bitset_b
static void
abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
{
- /* This should never occur for abitsets since we should always
- hit the cache. */
+ /* This should never occur for abitsets since we should always hit
+ the cache. It is likely someone is trying to access outside the
+ bounds of the bitset. */
abort ();
}
@@ -116,9 +119,9 @@ static void
abitset_reset (bitset dst ATTRIBUTE_UNUSED,
bitset_bindex bitno ATTRIBUTE_UNUSED)
{
- /* This should never occur for abitsets since we should always
- hit the cache. */
- abort ();
+ /* This should never occur for abitsets since we should always hit
+ the cache. It is likely someone is trying to access outside the
+ bounds of the bitset. Since the bit is zero anyway, let it pass. */
}
@@ -129,7 +132,6 @@ abitset_test (bitset src ATTRIBUTE_UNUSE
{
/* This should never occur for abitsets since we should always
hit the cache. */
- abort ();
return false;
}
@@ -149,7 +151,7 @@ abitset_list_reverse (bitset src, bitset
unsigned int bitcnt;
bitset_bindex bitoff;
bitset_word *srcp = ABITSET_WORDS (src);
- bitset_bindex n_bits = ABITSET_N_BITS (src);
+ bitset_bindex n_bits = BITSET_SIZE_ (src);
rbitno = *next;
@@ -228,7 +230,7 @@ abitset_list (bitset src, bitset_bindex
}
else
{
- if (bitno >= ABITSET_N_BITS (src))
+ if (bitno >= BITSET_SIZE_ (src))
return 0;
windex = bitno / BITSET_WORD_BITS;
@@ -304,7 +306,7 @@ abitset_unused_clear (bitset dst)
{
unsigned int last_bit;
- last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS;
+ last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
if (last_bit)
ABITSET_WORDS (dst)[dst->b.csize - 1] &=
((bitset_word) 1 << last_bit) - 1;
@@ -711,7 +713,8 @@ struct bitset_vtable abitset_small_vtabl
abitset_reset,
bitset_toggle_,
abitset_test,
- abitset_size,
+ abitset_resize,
+ bitset_size_,
bitset_count_,
abitset_empty_p,
abitset_ones,
@@ -748,7 +751,8 @@ struct bitset_vtable abitset_vtable = {
abitset_reset,
bitset_toggle_,
abitset_test,
- abitset_size,
+ abitset_resize,
+ bitset_size_,
bitset_count_,
abitset_empty_p,
abitset_ones,
@@ -809,7 +813,7 @@ abitset_init (bitset bset, bitset_bindex
bitset_windex size;
size = ABITSET_N_WORDS (n_bits);
- ABITSET_N_BITS (bset) = n_bits;
+ BITSET_NBITS_ (bset) = n_bits;
/* Use optimized routines if bitset fits within a single word.
There is probably little merit if using caching since
Index: lib/bbitset.h
===================================================================
RCS file: /cvsroot/bison/bison/lib/bbitset.h,v
retrieving revision 1.12
diff -p -u -r1.12 bbitset.h
--- lib/bbitset.h 24 May 2003 19:16:02 -0000 1.12
+++ lib/bbitset.h 17 Jun 2003 07:11:40 -0000
@@ -24,18 +24,23 @@ Foundation, Inc., 59 Temple Place - Suit
#include <stdbool.h>
#include <limits.h>
-/* Currently we support three flavours of bitsets:
+/* Currently we support five flavours of bitsets:
BITSET_ARRAY: Array of bits (fixed size, fast for dense bitsets).
- BITSET_LIST: Linked list of array of bits (variable size, least storage
+ Memory for bit array and bitset structure allocated
+ contiguously.
+ BITSET_LIST: Linked list of arrays of bits (variable size, least storage
for large very sparse sets).
- BITSET_TABLE: Expandable table of pointers to array of bits
+ BITSET_TABLE: Expandable table of pointers to arrays of bits
(variable size, less storage for large sparse sets).
-
- BITSET_STATS: Wrapper bitset for internal use only.
+ Faster than BITSET_LIST for random access.
+ BITSET_VARRAY: Variable array of bits (variable size, fast for
+ dense bitsets).
+ BITSET_STATS: Wrapper bitset for internal use only. Used for gathering
+ statistics and/or better run-time checking.
*/
-enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM,
- BITSET_STATS};
-#define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset"}
+enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_VARRAY,
+ BITSET_TYPE_NUM, BITSET_STATS};
+#define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset", "vbitset"}
extern const char * const bitset_type_names[];
@@ -78,10 +83,11 @@ enum bitset_ops {BITSET_OP_ZERO, BITSET_
struct bbitset_struct
{
- const struct bitset_vtable * vtable;
+ const struct bitset_vtable *vtable;
bitset_windex cindex; /* Cache word index. */
bitset_windex csize; /* Cache size in words. */
bitset_word *cdata; /* Cache data pointer. */
+ bitset_bindex n_bits; /* Number of bits. */
/* Perhaps we could sacrifice another word to indicate
that the bitset is known to be zero, that a bit has been set
in the cache, and that a bit has been cleared in the cache.
@@ -93,6 +99,14 @@ struct bbitset_struct
typedef union bitset_union *bitset;
+/* Private accessor macros to bitset structure. */
+#define BITSET_VTABLE_(SRC) (SRC)->b.vtable
+#define BITSET_CINDEX_(SRC) (SRC)->b.cindex
+#define BITSET_CDATA_(SRC) (SRC)->b.cdata
+#define BITSET_CSIZE_(SRC) (SRC)->b.csize
+#define BITSET_NBITS_(SRC) (SRC)->b.n_bits
+
+
/* The contents of this structure should be considered private. */
struct bitset_vtable
{
@@ -100,6 +114,7 @@ struct bitset_vtable
void (*reset) PARAMS ((bitset, bitset_bindex));
bool (*toggle) PARAMS ((bitset, bitset_bindex));
bool (*test) PARAMS ((bitset, bitset_bindex));
+ bitset_bindex (*resize) PARAMS ((bitset, bitset_bindex));
bitset_bindex (*size) PARAMS ((bitset));
bitset_bindex (*count) PARAMS ((bitset));
@@ -138,7 +153,8 @@ struct bitset_vtable
enum bitset_type type;
};
-#define BITSET_COMPATIBLE_(BSET1, BSET2) ((BSET1)->b.vtable ==
(BSET2)->b.vtable)
+#define BITSET_COMPATIBLE_(BSET1, BSET2) \
+((BSET1)->b.vtable == (BSET2)->b.vtable)
#define BITSET_CHECK2_(DST, SRC) \
if (!BITSET_COMPATIBLE_ (DST, SRC)) abort ();
@@ -152,6 +168,9 @@ if (!BITSET_COMPATIBLE_ (DST, SRC1) || !
|| !BITSET_COMPATIBLE_ (DST, SRC3)) abort ();
+/* Redefine number of bits in bitset DST. */
+#define BITSET_RESIZE_(DST, SIZE) (DST)->b.vtable->resize (DST, SIZE)
+
/* Return size in bits of bitset SRC. */
#define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC)
@@ -263,6 +282,8 @@ if (!BITSET_COMPATIBLE_ (DST, SRC1) || !
extern bool bitset_toggle_ PARAMS ((bitset, bitset_bindex));
extern bitset_bindex bitset_count_ PARAMS ((bitset));
+
+extern bitset_bindex bitset_size_ PARAMS ((bitset));
extern bool bitset_copy_ PARAMS ((bitset, bitset));
Index: lib/bitset.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/bitset.c,v
retrieving revision 1.9
diff -p -u -r1.9 bitset.c
--- lib/bitset.c 24 May 2003 19:16:02 -0000 1.9
+++ lib/bitset.c 17 Jun 2003 07:11:40 -0000
@@ -21,10 +21,12 @@
#endif
#include <stdlib.h>
+#include <string.h>
#include "bitset.h"
#include "abitset.h"
#include "lbitset.h"
#include "ebitset.h"
+#include "vbitset.h"
#include "bitset_stats.h"
#include "obstack.h"
@@ -55,6 +57,10 @@ bitset_bytes (enum bitset_type type, bit
bytes = ebitset_bytes (n_bits);
break;
+ case BITSET_VARRAY:
+ bytes = vbitset_bytes (n_bits);
+ break;
+
default:
abort ();
}
@@ -81,6 +87,9 @@ bitset_init (bitset bset, bitset_bindex
case BITSET_TABLE:
return ebitset_init (bset, n_bits);
+ case BITSET_VARRAY:
+ return vbitset_init (bset, n_bits);
+
default:
abort ();
}
@@ -93,27 +102,30 @@ bitset_init (bitset bset, bitset_bindex
enum bitset_type
bitset_type_choose (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned int attr)
{
- enum bitset_type type;
-
/* Check attributes. */
if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
abort ();
if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
abort ();
- /* Choose the type of bitset. Note that sometimes we will be asked
+ /* Choose the type of bitset. Note that sometimes we will be asked
for a zero length fixed size bitset. */
- type = BITSET_ARRAY;
- /* Currently, the simple bitsets do not support a variable size. */
- if (attr & BITSET_VARIABLE || attr & BITSET_SPARSE)
- {
- type = BITSET_LIST;
- if (attr & BITSET_DENSE || attr & BITSET_GREEDY)
- type = BITSET_TABLE;
- }
+
+ /* If no attributes selected, choose a good compromise. */
+ if (!attr)
+ return BITSET_VARRAY;
+
+ if (attr & BITSET_SPARSE)
+ return BITSET_LIST;
+
+ if (attr & BITSET_FIXED)
+ return BITSET_ARRAY;
- return type;
+ if (attr & BITSET_GREEDY)
+ return BITSET_TABLE;
+
+ return BITSET_VARRAY;
}
@@ -223,6 +235,14 @@ bitset_next (bitset src, bitset_bindex b
}
+/* Return true if both bitsets are of the same type and size. */
+extern bool
+bitset_compatible_p (bitset bset1, bitset bset2)
+{
+ return BITSET_COMPATIBLE_ (bset1, bset2);
+}
+
+
/* Find previous bit set in SRC starting from and including BITNO.
Return BITSET_BINDEX_MAX if SRC empty. */
bitset_bindex
@@ -304,7 +324,6 @@ bitset_dump (FILE *file, bitset bset)
}
-
/* Release memory associated with bitsets. */
void
bitset_release_memory (void)
@@ -314,7 +333,6 @@ bitset_release_memory (void)
}
-
/* Toggle bit BITNO in bitset BSET and the new value of the bit. */
bool
bitset_toggle_ (bitset bset, bitset_bindex bitno)
@@ -331,6 +349,14 @@ bitset_toggle_ (bitset bset, bitset_bind
bitset_set (bset, bitno);
return true;
}
+}
+
+
+/* Return number of bits in bitset SRC. */
+bitset_bindex
+bitset_size_ (bitset src)
+{
+ return BITSET_NBITS_ (src);
}
Index: lib/bitset.h
===================================================================
RCS file: /cvsroot/bison/bison/lib/bitset.h,v
retrieving revision 1.14
diff -p -u -r1.14 bitset.h
--- lib/bitset.h 24 May 2003 19:16:02 -0000 1.14
+++ lib/bitset.h 17 Jun 2003 07:11:40 -0000
@@ -54,12 +54,11 @@ union bitset_union
{
/* This must be the first member of every other structure that is a
member of this union. */
- struct bbitset_struct b;
+ struct bbitset_struct b; /* Base bitset data. */
struct abitset_struct
{
struct bbitset_struct b;
- bitset_bindex n_bits; /* Number of bits. */
bitset_word words[1]; /* The array of bits. */
} a;
@@ -82,6 +81,13 @@ union bitset_union
struct bbitset_struct b;
bitset bset;
} s;
+
+ struct vbitset_struct
+ {
+ struct bbitset_struct b;
+ bitset_windex size; /* Allocated size of array. */
+ } v;
+
};
@@ -179,6 +185,9 @@ bitset_test (bitset bset, bitset_bindex
/* Return size in bits of bitset SRC. */
#define bitset_size(SRC) BITSET_SIZE_ (SRC)
+/* Change size of bitset. */
+extern void bitset_resize PARAMS ((bitset, bitset_bindex));
+
/* Return number of bits set in bitset SRC. */
#define bitset_count(SRC) BITSET_COUNT_ (SRC)
@@ -276,11 +285,13 @@ bitset_test (bitset bset, bitset_bindex
#define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
+/* Return true if both bitsets are of the same type and size. */
+extern bool bitset_compatible_p (bitset bset1, bitset bset2);
-/* Find next set bit. */
+/* Find next set bit from the given bit index. */
extern bitset_bindex bitset_next PARAMS ((bitset, bitset_bindex));
-/* Find previous set bit. */
+/* Find previous set bit from the given bit index. */
extern bitset_bindex bitset_prev PARAMS ((bitset, bitset_bindex));
/* Find first set bit. */
@@ -295,7 +306,7 @@ extern bool bitset_only_set_p PARAMS ((b
/* Dump bitset. */
extern void bitset_dump PARAMS ((FILE *, bitset));
-/* Loop over all elements of BSET, starting with MIN, setting BIT
+/* Loop over all elements of BSET, starting with MIN, setting INDEX
to the index of each set bit. For example, the following will print
the bits set in a bitset:
@@ -304,21 +315,21 @@ extern void bitset_dump PARAMS ((FILE *,
BITSET_FOR_EACH (iter, src, i, 0)
{
- printf ("%ld ", i);
+ printf ("%lu ", (unsigned long int) i);
};
*/
-#define BITSET_FOR_EACH(ITER, BSET, BIT, MIN) \
+#define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN)
\
for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
(ITER.num == BITSET_LIST_SIZE) \
&& (ITER.num = bitset_list (BSET, ITER.list, \
BITSET_LIST_SIZE, &ITER.next));) \
for (ITER.i = 0; \
- ITER.i < ITER.num && ((BIT) = ITER.list[ITER.i], 1); \
+ ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
ITER.i++)
/* Loop over all elements of BSET, in reverse order starting with
- MIN, setting BIT to the index of each set bit. For example, the
+ MIN, setting INDEX to the index of each set bit. For example, the
following will print the bits set in a bitset in reverse order:
bitset_bindex i;
@@ -326,16 +337,16 @@ extern void bitset_dump PARAMS ((FILE *,
BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
{
- printf ("%ld ", i);
+ printf ("%lu ", (unsigned long int) i);
};
*/
-#define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN) \
+#define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN)
\
for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
(ITER.num == BITSET_LIST_SIZE) \
&& (ITER.num = bitset_list_reverse (BSET, ITER.list, \
- BITSET_LIST_SIZE, &ITER.next));) \
+ BITSET_LIST_SIZE, &ITER.next));) \
for (ITER.i = 0; \
- ITER.i < ITER.num && ((BIT) = ITER.list[ITER.i], 1); \
+ ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
ITER.i++)
@@ -359,7 +370,6 @@ extern void bitset_dump PARAMS ((FILE *,
bitset_andn_or (DST, SRC1, SRC2, SRC3)
#define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
-
/* Release any memory tied up with bitsets. */
Index: lib/bitset_stats.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/bitset_stats.c,v
retrieving revision 1.10
diff -p -u -r1.10 bitset_stats.c
--- lib/bitset_stats.c 24 May 2003 19:16:02 -0000 1.10
+++ lib/bitset_stats.c 17 Jun 2003 07:11:41 -0000
@@ -33,6 +33,7 @@
#include "abitset.h"
#include "ebitset.h"
#include "lbitset.h"
+#include "vbitset.h"
#include "bitset_stats.h"
#include <stdlib.h>
#include <string.h>
@@ -376,6 +377,13 @@ bitset_stats_test (bitset src, bitset_bi
static bitset_bindex
+bitset_stats_resize (bitset src, bitset_bindex size)
+{
+ return BITSET_RESIZE_ (src->s.bset, size);
+}
+
+
+static bitset_bindex
bitset_stats_size (bitset src)
{
return BITSET_SIZE_ (src->s.bset);
@@ -518,7 +526,6 @@ static void
bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
{
BITSET_CHECK4_ (dst, src1, src2, src3);
-
BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
}
@@ -527,7 +534,6 @@ static bool
bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
BITSET_CHECK4_ (dst, src1, src2, src3);
-
return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset,
src3->s.bset);
}
@@ -536,7 +542,6 @@ static void
bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
{
BITSET_CHECK4_ (dst, src1, src2, src3);
-
BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
}
@@ -545,7 +550,6 @@ static bool
bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
BITSET_CHECK4_ (dst, src1, src2, src3);
-
return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset,
src3->s.bset);
}
@@ -554,7 +558,6 @@ static void
bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
{
BITSET_CHECK4_ (dst, src1, src2, src3);
-
BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
}
@@ -563,7 +566,6 @@ static bool
bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
BITSET_CHECK4_ (dst, src1, src2, src3);
-
return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset,
src3->s.bset);
}
@@ -576,9 +578,11 @@ bitset_stats_list (bitset bset, bitset_b
bitset_bindex tmp;
bitset_bindex size;
bitset_bindex i;
+ enum bitset_type type;
count = BITSET_LIST_ (bset->s.bset, list, num, next);
+ type = BITSET_TYPE_ (bset->s.bset);
BITSET_STATS_LISTS_INC (bset->s.bset);
/* Log histogram of number of set bits. */
@@ -626,6 +630,7 @@ struct bitset_vtable bitset_stats_vtable
bitset_stats_reset,
bitset_stats_toggle,
bitset_stats_test,
+ bitset_stats_resize,
bitset_stats_size,
bitset_stats_count,
bitset_stats_empty_p,
@@ -685,6 +690,8 @@ bitset_stats_init (bitset bset, bitset_b
bset->b.csize = 0;
bset->b.cdata = 0;
+ BITSET_NBITS_ (bset) = n_bits;
+
/* Set up the actual bitset implementation that
we are a wrapper over. */
switch (type)
@@ -705,6 +712,12 @@ bitset_stats_init (bitset bset, bitset_b
bytes = ebitset_bytes (n_bits);
sbset = (bitset) xcalloc (1, bytes);
ebitset_init (sbset, n_bits);
+ break;
+
+ case BITSET_VARRAY:
+ bytes = vbitset_bytes (n_bits);
+ sbset = (bitset) xcalloc (1, bytes);
+ vbitset_init (sbset, n_bits);
break;
default:
Index: lib/ebitset.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/ebitset.c,v
retrieving revision 1.11
diff -p -u -r1.11 ebitset.c
--- lib/ebitset.c 24 May 2003 19:16:02 -0000 1.11
+++ lib/ebitset.c 17 Jun 2003 07:11:41 -0000
@@ -24,6 +24,7 @@
#include "ebitset.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
@@ -75,11 +76,6 @@ typedef ebitset_elt *ebitset_elts;
#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 };
@@ -91,8 +87,10 @@ static struct obstack ebitset_obstack;
static bool ebitset_obstack_init = false;
static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */
+#define EBITSET_N_ELTS(N) (((N) + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS)
#define EBITSET_ELTS(BSET) ((BSET)->e.elts)
-#define EBITSET_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)
@@ -118,24 +116,64 @@ static ebitset_elt *ebitset_free_list; /
(BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
-/* Grow the expandable table for BSET by SIZE elements. */
-static void
-ebitset_elts_grow (bitset bset, bitset_windex size)
+#define min(a, b) ((a) > (b) ? (b) : (a))
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
+
+static bitset_bindex
+ebitset_resize (bitset src, bitset_bindex n_bits)
{
bitset_windex oldsize;
bitset_windex newsize;
- oldsize = EBITSET_SIZE (bset);
- newsize = oldsize + size;
+ if (n_bits == BITSET_NBITS_ (src))
+ return n_bits;
+
+ oldsize = EBITSET_SIZE (src);
+ newsize = EBITSET_N_ELTS (n_bits);
+
+ 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;
+ }
- if (BITSET_SIZE_MAX / sizeof (ebitset_elt *) < newsize)
- xalloc_die ();
+ 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;
+ }
- EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
- newsize * sizeof (ebitset_elt *));
- EBITSET_SIZE (bset) = 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;
}
@@ -257,7 +295,7 @@ ebitset_elt_zero_p (ebitset_elt *elt)
static ebitset_elt *
-ebitset_elt_find (bitset bset, bitset_windex windex,
+ebitset_elt_find (bitset bset, bitset_bindex bindex,
enum ebitset_find_mode mode)
{
ebitset_elt *elt;
@@ -265,7 +303,7 @@ ebitset_elt_find (bitset bset, bitset_wi
bitset_windex eindex;
ebitset_elts *elts;
- eindex = windex / EBITSET_ELT_WORDS;
+ eindex = bindex / EBITSET_ELT_BITS;
elts = EBITSET_ELTS (bset);
size = EBITSET_SIZE (bset);
@@ -291,21 +329,7 @@ ebitset_elt_find (bitset bset, bitset_wi
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 ();
@@ -322,18 +346,6 @@ ebitset_elt_find (bitset bset, bitset_wi
}
-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)
@@ -353,7 +365,7 @@ ebitset_weed (bitset bset)
if (elt)
{
- if (elt && ebitset_elt_zero_p (elt))
+ if (ebitset_elt_zero_p (elt))
{
ebitset_elt_remove (bset, j);
count++;
@@ -453,8 +465,8 @@ ebitset_copy_ (bitset dst, bitset src)
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);
@@ -498,22 +510,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;
- 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);
@@ -526,7 +529,7 @@ ebitset_reset (bitset dst, bitset_bindex
{
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] &=
@@ -544,7 +547,7 @@ ebitset_test (bitset src, bitset_bindex
{
bitset_windex windex = bitno / BITSET_WORD_BITS;
- return (ebitset_elt_find (src, windex, EBITSET_FIND)
+ return (ebitset_elt_find (src, bitno, EBITSET_FIND)
&& ((src->b.cdata[windex - src->b.cindex]
>> (bitno % BITSET_WORD_BITS))
& 1));
@@ -731,6 +734,48 @@ ebitset_list (bitset bset, bitset_bindex
{
/* 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;
@@ -756,6 +801,7 @@ ebitset_list (bitset bset, bitset_bindex
}
}
}
+#endif
}
else
{
@@ -788,29 +834,91 @@ ebitset_list (bitset bset, bitset_bindex
}
+/* 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;
-
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 =
- 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);
+ ebitset_unused_clear (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 +930,22 @@ ebitset_not (bitset dst, bitset src)
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
- or substitute zero elements if src elements not found. */
+ or substitute zero elements if src elements not found. */
selt =
- ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
+ ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_SUBST);
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++)
EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
}
EBITSET_NONZERO_SET (dst);
+ ebitset_unused_clear (dst);
}
@@ -934,6 +1045,8 @@ ebitset_op3_cmp (bitset dst, bitset src1
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);
@@ -941,9 +1054,6 @@ ebitset_op3_cmp (bitset dst, bitset src1
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);
@@ -1183,7 +1293,8 @@ struct bitset_vtable ebitset_vtable = {
ebitset_reset,
bitset_toggle_,
ebitset_test,
- ebitset_size,
+ ebitset_resize,
+ bitset_size_,
bitset_count_,
ebitset_empty_p,
ebitset_ones,
@@ -1238,9 +1349,9 @@ ebitset_init (bitset bset, bitset_bindex
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_grow (bset, size);
+ ebitset_resize (bset, n_bits);
return bset;
}
Index: lib/lbitset.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/lbitset.c,v
retrieving revision 1.11
diff -p -u -r1.11 lbitset.c
--- lib/lbitset.c 24 May 2003 19:16:02 -0000 1.11
+++ lib/lbitset.c 17 Jun 2003 07:11:41 -0000
@@ -26,6 +26,7 @@
#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
@@ -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
- 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
@@ -502,21 +506,15 @@ lbitset_copy_cmp (bitset dst, bitset src
}
-/* Return size in bits of bitset SRC. */
static bitset_bindex
-lbitset_size (bitset src)
+lbitset_resize (bitset src, bitset_bindex size)
{
- lbitset_elt *elt;
-
- elt = LBITSET_TAIL (src);
- if (!elt)
- return 0;
+ BITSET_NBITS_ (src) = size;
- /* 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)
@@ -867,8 +865,48 @@ lbitset_list (bitset bset, bitset_bindex
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 +921,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. */
- 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));
}
+
+ lbitset_unused_clear (dst);
}
@@ -911,11 +948,9 @@ lbitset_not (bitset dst, bitset src)
/* 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
@@ -926,6 +961,7 @@ lbitset_not (bitset dst, bitset src)
for (j = 0; j < LBITSET_ELT_WORDS; j++)
delt->words[j] = ~selt->words[j];
}
+ lbitset_unused_clear (dst);
lbitset_weed (dst);
return;
}
@@ -1280,7 +1316,8 @@ struct bitset_vtable lbitset_vtable = {
lbitset_reset,
bitset_toggle_,
lbitset_test,
- lbitset_size,
+ lbitset_resize,
+ bitset_size_,
bitset_count_,
lbitset_empty_p,
lbitset_ones,
@@ -1323,6 +1360,7 @@ lbitset_bytes (bitset_bindex n_bits ATTR
bitset
lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
{
+ BITSET_NBITS_ (bset) = n_bits;
bset->b.vtable = &lbitset_vtable;
return bset;
}
Index: lib/libiberty.h
===================================================================
RCS file: /cvsroot/bison/bison/lib/libiberty.h,v
retrieving revision 1.1
diff -p -u -r1.1 libiberty.h
--- lib/libiberty.h 2 Jul 2002 13:51:26 -0000 1.1
+++ lib/libiberty.h 17 Jun 2003 07:11:41 -0000
@@ -1,5 +1,5 @@
/* Fake libiberty.h for Bison.
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003 Free Software Foundation, Inc.
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
@@ -23,21 +23,7 @@
#ifndef BISON_LIBIBERTY_H_
# define BISON_LIBIBERTY_H_ 1
-# if HAVE_CONFIG_H
-# include <config.h>
-# endif
-# include <stdlib.h>
-
-/* This file is the public interface to the bitset abstract data type.
- Only use the functions and macros defined in this file. */
-
-# ifndef PARAMS
-# if defined PROTOTYPES || (defined __STDC__ && __STDC__)
-# define PARAMS(Args) Args
-# else
-# define PARAMS(Args) ()
-# endif
-# endif
+# define PARAMS(X) X
# ifndef __attribute__
# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
@@ -45,13 +31,7 @@
# endif
# endif
-# ifndef ATTRIBUTE_NORETURN
-# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
-# endif
-
-# ifndef ATTRIBUTE_UNUSED
-# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
-# endif
+# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
# include "xalloc.h"
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: Bitsets,
Paul Eggert <=