From eaef5507fcebaafa7e713139bc7eb9910a6ab5de Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 2 Jun 2003 10:19:37 +0000 Subject: [PATCH] Import of 2003-06-08 libbitset --- lib/abitset.c | 40 ++++++++++++++++++---------------- lib/bitset.c | 54 ++++++++++++++++++++++++++++++++++------------ lib/bitset_stats.c | 31 ++++++++++++++++++++------ 3 files changed, 86 insertions(+), 39 deletions(-) diff --git a/lib/abitset.c b/lib/abitset.c index 99c1c2f1..0fe1b47b 100644 --- a/lib/abitset.c +++ b/lib/abitset.c @@ -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_bindex *list, 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_bindex *list, 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_UNUSED, { /* 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_bindex *list, 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 *list, } 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_vtable = { 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 n_bits) 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 diff --git a/lib/bitset.c b/lib/bitset.c index a500d471..3c0d956e 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -21,10 +21,12 @@ #endif #include +#include #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, bitset_bindex n_bits) 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 n_bits, enum bitset_type type) 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 n_bits, enum bitset_type type) 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 bitno) } +/* 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) @@ -334,6 +352,14 @@ bitset_toggle_ (bitset bset, bitset_bindex bitno) } +/* Return number of bits in bitset SRC. */ +bitset_bindex +bitset_size_ (bitset src) +{ + return BITSET_NBITS_ (src); +} + + /* Return number of bits set in bitset SRC. */ bitset_bindex bitset_count_ (bitset src) diff --git a/lib/bitset_stats.c b/lib/bitset_stats.c index c504a616..e1692d88 100644 --- a/lib/bitset_stats.c +++ b/lib/bitset_stats.c @@ -1,5 +1,5 @@ /* Bitset statistics. - Copyright (C) 2002, 2003 Free Software Foundation, Inc. + Copyright (C) 2002 Free Software Foundation, Inc. Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). This program is free software; you can redistribute it and/or modify @@ -33,13 +33,18 @@ #include "abitset.h" #include "ebitset.h" #include "lbitset.h" +#include "vbitset.h" #include "bitset_stats.h" #include #include #include +#ifdef HAVE_GETTEXT_H #include "gettext.h" #define _(Msgid) gettext (Msgid) +#else +#define _(Msgid) Msgid +#endif /* Configuration macros. */ #define BITSET_STATS_FILE "bitset.dat" @@ -375,6 +380,13 @@ bitset_stats_test (bitset src, bitset_bindex bitno) } +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) { @@ -518,7 +530,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 +538,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 +546,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 +554,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 +562,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 +570,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 +582,11 @@ bitset_stats_list (bitset bset, bitset_bindex *list, 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 +634,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 +694,8 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) 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) @@ -707,6 +718,12 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) 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: abort (); } -- 2.45.2