From: Akim Demaille Date: Mon, 30 Sep 2002 12:50:49 +0000 (+0000) Subject: * lib/abitset.c, lib/bbitset.h, lib/bitset.c, lib/bitset.h, X-Git-Tag: BISON-1_75~86 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/6aa452a643c65a8df244013e05d41854531ec762 * lib/abitset.c, lib/bbitset.h, lib/bitset.c, lib/bitset.h, * lib/bitset_stats.c, lib/bitsetv.c, lib/ebitset.c, lib/lbitset.c: Updates from Michael Hayes. --- diff --git a/ChangeLog b/ChangeLog index b4ed0ebf..e467d760 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2002-09-30 Akim Demaille + + * lib/abitset.c, lib/bbitset.h, lib/bitset.c, lib/bitset.h, + * lib/bitset_stats.c, lib/bitsetv.c, lib/ebitset.c, lib/lbitset.c: + Updates from Michael Hayes. + 2002-09-30 Art Haas * configure.ac: Update AC_OUTPUT and AM_CONFIG_HEADER diff --git a/lib/abitset.c b/lib/abitset.c index f3c32ef4..9eb2eeb9 100644 --- a/lib/abitset.c +++ b/lib/abitset.c @@ -51,14 +51,9 @@ static void abitset_set PARAMS ((bitset, bitset_bindex)); static void abitset_reset PARAMS ((bitset, bitset_bindex)); static int abitset_test PARAMS ((bitset, bitset_bindex)); static int abitset_size PARAMS ((bitset)); -static int abitset_op1 PARAMS ((bitset, enum bitset_ops)); -static int abitset_op2 PARAMS ((bitset, bitset, enum bitset_ops)); -static int abitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); -static int abitset_op4 PARAMS ((bitset, bitset, bitset, bitset, - enum bitset_ops)); static int abitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); -static int abitset_reverse_list +static int abitset_list_reverse PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) @@ -143,7 +138,8 @@ abitset_set (dst, bitno) bitset dst ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for abitsets. */ + /* This should never occur for abitsets since we should always + hit the cache. */ abort (); } @@ -154,7 +150,8 @@ abitset_reset (dst, bitno) bitset dst ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for abitsets. */ + /* This should never occur for abitsets since we should always + hit the cache. */ abort (); } @@ -165,7 +162,8 @@ abitset_test (src, bitno) bitset src ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for abitsets. */ + /* This should never occur for abitsets since we should always + hit the cache. */ abort (); return 0; } @@ -176,7 +174,7 @@ abitset_test (src, bitno) actual number of bits found and with *NEXT indicating where search stopped. */ static int -abitset_reverse_list (src, list, num, next) +abitset_list_reverse (src, list, num, next) bitset src; bitset_bindex *list; bitset_bindex num; @@ -188,7 +186,6 @@ abitset_reverse_list (src, list, num, next) bitset_windex windex; unsigned int bitcnt; bitset_bindex bitoff; - bitset_word word; bitset_word *srcp = ABITSET_WORDS (src); bitset_bindex n_bits = ABITSET_N_BITS (src); @@ -210,6 +207,8 @@ abitset_reverse_list (src, list, num, next) do { + bitset_word word; + word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); for (; word; bitcnt--) { @@ -354,99 +353,153 @@ abitset_unused_clear (dst) } -static int -abitset_op1 (dst, op) +static void +abitset_ones (dst) bitset dst; - enum bitset_ops op; { - unsigned int i; bitset_word *dstp = ABITSET_WORDS (dst); unsigned int bytes; bytes = sizeof (bitset_word) * dst->b.csize; - switch (op) - { - case BITSET_OP_ZERO: - memset (dstp, 0, bytes); - break; - - case BITSET_OP_ONES: - memset (dstp, -1, bytes); - abitset_unused_clear (dst); - break; - - case BITSET_OP_EMPTY_P: - for (i = 0; i < dst->b.csize; i++) - if (dstp[i]) - return 0; - break; + memset (dstp, -1, bytes); + abitset_unused_clear (dst); +} + + +static void +abitset_zero (dst) + bitset dst; +{ + bitset_word *dstp = ABITSET_WORDS (dst); + unsigned int bytes; + + bytes = sizeof (bitset_word) * dst->b.csize; + + memset (dstp, 0, bytes); +} - default: - abort (); - } + +static int +abitset_empty_p (dst) + bitset dst; +{ + unsigned int i; + bitset_word *dstp = ABITSET_WORDS (dst); + + for (i = 0; i < dst->b.csize; i++) + if (dstp[i]) + return 0; return 1; } +static void +abitset_copy1 (dst, src) + bitset dst; + bitset src; +{ + bitset_word *srcp = ABITSET_WORDS (src); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + if (srcp == dstp) + return; + memcpy (dstp, srcp, sizeof (bitset_word) * size); +} + + +static void +abitset_not (dst, src) + bitset dst; + bitset src; +{ + unsigned int i; + bitset_word *srcp = ABITSET_WORDS (src); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++) + *dstp++ = ~(*srcp++); + abitset_unused_clear (dst); +} + + static int -abitset_op2 (dst, src, op) +abitset_equal_p (dst, src) bitset dst; bitset src; - enum bitset_ops op; { unsigned int i; bitset_word *srcp = ABITSET_WORDS (src); bitset_word *dstp = ABITSET_WORDS (dst); bitset_windex size = dst->b.csize; - switch (op) - { - case BITSET_OP_COPY: - if (srcp == dstp) - break; - memcpy (dstp, srcp, sizeof (bitset_word) * size); - break; - - case BITSET_OP_NOT: - for (i = 0; i < size; i++) - *dstp++ = ~(*srcp++); - abitset_unused_clear (dst); - break; - - case BITSET_OP_EQUAL_P: - for (i = 0; i < size; i++) - if (*srcp++ != *dstp++) + for (i = 0; i < size; i++) + if (*srcp++ != *dstp++) return 0; - break; - - case BITSET_OP_SUBSET_P: - for (i = 0; i < size; i++, dstp++, srcp++) - if (*dstp != (*srcp | *dstp)) + return 1; +} + + +static int +abitset_subset_p (dst, src) + bitset dst; + bitset src; +{ + unsigned int i; + bitset_word *srcp = ABITSET_WORDS (src); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++, dstp++, srcp++) + if (*dstp != (*srcp | *dstp)) return 0; - break; - - case BITSET_OP_DISJOINT_P: - for (i = 0; i < size; i++) - if (*srcp++ & *dstp++) + return 1; +} + + +static int +abitset_disjoint_p (dst, src) + bitset dst; + bitset src; +{ + unsigned int i; + bitset_word *srcp = ABITSET_WORDS (src); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++) + if (*srcp++ & *dstp++) return 0; - break; - - default: - abort (); - } return 1; } +static void +abitset_and (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++) + *dstp++ = *src1p++ & *src2p++; +} + + static int -abitset_op3 (dst, src1, src2, op) +abitset_and_cmp (dst, src1, src2) bitset dst; bitset src1; bitset src2; - enum bitset_ops op; { unsigned int i; int changed = 0; @@ -455,75 +508,177 @@ abitset_op3 (dst, src1, src2, op) bitset_word *dstp = ABITSET_WORDS (dst); bitset_windex size = dst->b.csize; - switch (op) + for (i = 0; i < size; i++, dstp++) { - case BITSET_OP_OR: - for (i = 0; i < size; i++, dstp++) + bitset_word tmp = *src1p++ & *src2p++; + + if (*dstp != tmp) { - bitset_word tmp = *src1p++ | *src2p++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } + changed = 1; + *dstp = tmp; } - break; + } + return changed; +} - case BITSET_OP_AND: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = *src1p++ & *src2p++; - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; +static void +abitset_andn (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; - case BITSET_OP_XOR: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = *src1p++ ^ *src2p++; + for (i = 0; i < size; i++) + *dstp++ = *src1p++ & ~(*src2p++); +} - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - case BITSET_OP_ANDN: - for (i = 0; i < size; i++, dstp++) +static int +abitset_andn_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ & ~(*src2p++); + + if (*dstp != tmp) { - bitset_word tmp = *src1p++ & ~(*src2p++); - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } + changed = 1; + *dstp = tmp; } - break; + } + return changed; +} + + +static void +abitset_or (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++) + *dstp++ = *src1p++ | *src2p++; +} + - default: - abort (); +static int +abitset_or_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ | *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } } + return changed; +} + +static void +abitset_xor (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++) + *dstp++ = *src1p++ ^ *src2p++; +} + + +static int +abitset_xor_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ ^ *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } return changed; } +static void +abitset_and_or (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *src3p = ABITSET_WORDS (src3); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++) + *dstp++ = (*src1p++ & *src2p++) | *src3p++; +} + + static int -abitset_op4 (dst, src1, src2, src3, op) +abitset_and_or_cmp (dst, src1, src2, src3) bitset dst; bitset src1; bitset src2; bitset src3; - enum bitset_ops op; { unsigned int i; int changed = 0; @@ -532,85 +687,198 @@ abitset_op4 (dst, src1, src2, src3, op) bitset_word *src3p = ABITSET_WORDS (src3); bitset_word *dstp = ABITSET_WORDS (dst); bitset_windex size = dst->b.csize; - - switch (op) + + for (i = 0; i < size; i++, dstp++) { - case BITSET_OP_OR_AND: - for (i = 0; i < size; i++, dstp++) + bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; + + if (*dstp != tmp) { - bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } + changed = 1; + *dstp = tmp; } - break; + } + return changed; +} - case BITSET_OP_AND_OR: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; +static void +abitset_andn_or (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *src3p = ABITSET_WORDS (src3); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++) + *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++; +} - case BITSET_OP_ANDN_OR: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } +static int +abitset_andn_or_cmp (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *src3p = ABITSET_WORDS (src3); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; } - break; - - default: - abort (); } + return changed; +} + + +static void +abitset_or_and (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *src3p = ABITSET_WORDS (src3); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++) + *dstp++ = (*src1p++ | *src2p++) & *src3p++; +} + +static int +abitset_or_and_cmp (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *src3p = ABITSET_WORDS (src3); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } return changed; } +void +abitset_copy (dst, src) + bitset dst; + bitset src; +{ + if (BITSET_COMPATIBLE_ (dst, src)) + abitset_copy1 (dst, src); + else + bitset_copy_ (dst, src); +} + + /* Vector of operations for single word bitsets. */ -struct bitset_ops_struct abitset_small_ops = { +struct bitset_vtable abitset_small_vtable = { abitset_set, abitset_reset, + bitset_toggle_, abitset_test, abitset_size, - abitset_op1, - abitset_op2, - abitset_op3, - abitset_op4, + bitset_count_, + abitset_empty_p, + abitset_ones, + abitset_zero, + abitset_copy, + abitset_disjoint_p, + abitset_equal_p, + abitset_not, + abitset_subset_p, + abitset_and, + abitset_and_cmp, + abitset_andn, + abitset_andn_cmp, + abitset_or, + abitset_or_cmp, + abitset_xor, + abitset_xor_cmp, + abitset_and_or, + abitset_and_or_cmp, + abitset_andn_or, + abitset_andn_or_cmp, + abitset_or_and, + abitset_or_and_cmp, abitset_small_list, - abitset_reverse_list, + abitset_list_reverse, NULL, BITSET_ARRAY }; /* Vector of operations for multiple word bitsets. */ -struct bitset_ops_struct abitset_ops = { +struct bitset_vtable abitset_vtable = { abitset_set, abitset_reset, + bitset_toggle_, abitset_test, abitset_size, - abitset_op1, - abitset_op2, - abitset_op3, - abitset_op4, + bitset_count_, + abitset_empty_p, + abitset_ones, + abitset_zero, + abitset_copy, + abitset_disjoint_p, + abitset_equal_p, + abitset_not, + abitset_subset_p, + abitset_and, + abitset_and_cmp, + abitset_andn, + abitset_andn_cmp, + abitset_or, + abitset_or_cmp, + abitset_xor, + abitset_xor_cmp, + abitset_and_or, + abitset_and_or_cmp, + abitset_andn_or, + abitset_andn_or_cmp, + abitset_or_and, + abitset_or_and_cmp, abitset_list, - abitset_reverse_list, + abitset_list_reverse, NULL, BITSET_ARRAY }; @@ -642,9 +910,9 @@ abitset_init (bset, n_bits) There is probably little merit if using caching since the small bitset will always fit in the cache. */ if (size == 1) - bset->b.ops = &abitset_small_ops; + bset->b.vtable = &abitset_small_vtable; else - bset->b.ops = &abitset_ops; + bset->b.vtable = &abitset_vtable; bset->b.cindex = 0; bset->b.csize = size; diff --git a/lib/bbitset.h b/lib/bbitset.h index 1e5710d3..059c3e44 100644 --- a/lib/bbitset.h +++ b/lib/bbitset.h @@ -26,11 +26,11 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #endif /* Currently we support three flavours of bitsets: - BITSET_ARRAY: Array of bits (fixed size, faster). + BITSET_ARRAY: Array of bits (fixed size, fast for dense bitsets). BITSET_LIST: Linked list of array of bits (variable size, least storage - for large very sparse sets). + for large very sparse sets). BITSET_TABLE: Expandable table of pointers to array of bits - (variable size, less storage for large sparse sets). + (variable size, less storage for large sparse sets). BITSET_STATS: Wrapper bitset for internal use only. */ @@ -38,6 +38,8 @@ enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM, BITSET_STATS}; #define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset"} +extern const char * const bitset_type_names[]; + enum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC}; /* Non-zero to use inline functions instead of macros. */ @@ -68,163 +70,213 @@ enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES, BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN, BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR}; +struct bbitset_struct +{ + const struct bitset_vtable * vtable; + bitset_windex cindex; /* Cache word index. */ + bitset_windex csize; /* Cache size in words. */ + bitset_word *cdata; /* Cache data pointer. */ + /* 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. + This would speed up some of the searches but slightly slow down + bit set/reset operations of cached bits. */ +}; + + +typedef struct bitset_struct *bitset; + + +/* The contents of this structure should be considered private. */ +struct bitset_vtable +{ + void (*set) PARAMS ((struct bitset_struct *, bitset_bindex)); + void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex)); + int (*toggle) PARAMS ((struct bitset_struct *, bitset_bindex)); + int (*test) PARAMS ((struct bitset_struct *, bitset_bindex)); + int (*size) PARAMS ((struct bitset_struct *)); + int (*count) PARAMS ((struct bitset_struct *)); + + int (*empty_p) PARAMS ((struct bitset_struct *)); + void (*ones) PARAMS ((struct bitset_struct *)); + void (*zero) PARAMS ((struct bitset_struct *)); + + void (*copy) PARAMS ((struct bitset_struct *, struct bitset_struct *)); + int (*disjoint_p) PARAMS ((struct bitset_struct *, struct bitset_struct *)); + int (*equal_p) PARAMS ((struct bitset_struct *, struct bitset_struct *)); + void (*not) PARAMS ((struct bitset_struct *, struct bitset_struct *)); + int (*subset_p) PARAMS ((struct bitset_struct *, struct bitset_struct *)); + + void (*and) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *)); + int (*and_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *)); + void (*andn) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *)); + int (*andn_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *)); + void (*or) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *)); + int (*or_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *)); + void (*xor) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *)); + int (*xor_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *)); + + void (*and_or) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, struct bitset_struct *)); + int (*and_or_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, struct bitset_struct *)); + void (*andn_or) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, struct bitset_struct *)); + int (*andn_or_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, struct bitset_struct *)); + void (*or_and) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, struct bitset_struct *)); + int (*or_and_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, struct bitset_struct *)); + + int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *, + bitset_bindex, bitset_bindex *)); + int (*list_reverse) PARAMS ((struct bitset_struct *, bitset_bindex *, + bitset_bindex, bitset_bindex *)); + void (*free) PARAMS ((struct bitset_struct *)); + enum bitset_type type; +}; + +#define BITSET_COMPATIBLE_(BSET1, BSET2) ((BSET1)->b.vtable == (BSET2)->b.vtable) + +#define BITSET_CHECK2_(DST, SRC) \ +if (!BITSET_COMPATIBLE_ (DST, SRC)) abort (); + +#define BITSET_CHECK3_(DST, SRC1, SRC2) \ +if (!BITSET_COMPATIBLE_ (DST, SRC1) \ + || !BITSET_COMPATIBLE_ (DST, SRC2)) abort (); + +#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \ +if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \ + || !BITSET_COMPATIBLE_ (DST, SRC3)) abort (); + + /* Return size in bits of bitset SRC. */ -#define BITSET_SIZE_(SRC) (SRC)->b.ops->size (SRC) +#define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC) + +/* Return number of bits set in bitset SRC. */ +#define BITSET_COUNT_(SRC) (SRC)->b.vtable->count (SRC) /* Return type of bitset SRC. */ -#define BITSET_TYPE_(DST) (DST)->b.ops->type +#define BITSET_TYPE_(DST) (DST)->b.vtable->type /* Set bit BITNO in bitset DST. */ -#define BITSET_SET_(DST, BITNO) (DST)->b.ops->set (DST, BITNO) +#define BITSET_SET_(DST, BITNO) (DST)->b.vtable->set (DST, BITNO) /* Reset bit BITNO in bitset DST. */ -#define BITSET_RESET_(DST, BITNO) (DST)->b.ops->reset (DST, BITNO) +#define BITSET_RESET_(DST, BITNO) (DST)->b.vtable->reset (DST, BITNO) + +/* Toggle bit BITNO in bitset DST. */ +#define BITSET_TOGGLE_(DST, BITNO) (DST)->b.vtable->toggle (DST, BITNO) /* Return non-zero if bit BITNO in bitset SRC is set. */ -#define BITSET_TEST_(SRC, BITNO) (SRC)->b.ops->test (SRC, BITNO) +#define BITSET_TEST_(SRC, BITNO) (SRC)->b.vtable->test (SRC, BITNO) /* Free bitset SRC. */ #define BITSET_FREE_(SRC)\ - ((SRC)->b.ops->free ? (SRC)->b.ops->free (SRC) :(void)0) - -/* Perform operation OP on DST. */ -#define BITSET_OP1_(DST, OP) (DST)->b.ops->op1 (DST, OP) + ((SRC)->b.vtable->free ? (SRC)->b.vtable->free (SRC) :(void)0) -/* Perform operation OP on SRC and store in DST. */ -#define BITSET_OP2_(DST, SRC, OP) (DST)->b.ops->op2 (DST, SRC, OP) -/* DST = SRC1 OP SRC2. */ -#define BITSET_OP3_(DST, SRC1, SRC2, OP) \ -(DST)->b.ops->op3 (DST, SRC1, SRC2, OP) +/* Return SRC == 0. */ +#define BITSET_EMPTY_P_(SRC) (SRC)->b.vtable->empty_p (SRC) -/* DST = (SRC1 OP1 SRC2) OP2 SRC3. */ -#define BITSET_OP4_(DST, SRC1, SRC2, SRC3, OP) \ -(DST)->b.ops->op4 (DST, SRC1, SRC2, SRC3, OP) +/* DST = ~0. */ +#define BITSET_ONES_(DST) (DST)->b.vtable->ones (DST) /* DST = 0. */ -#define BITSET_ZERO_(DST) BITSET_OP1_ (DST, BITSET_OP_ZERO); +#define BITSET_ZERO_(DST) (DST)->b.vtable->zero (DST) -/* DST = ~0. */ -#define BITSET_ONES_(DST) BITSET_OP1_ (DST, BITSET_OP_ONES); -/* Return SRC == 0. */ -#define BITSET_EMPTY_P_(SRC) BITSET_OP1_ (SRC, BITSET_OP_EMPTY_P); + +/* DST = SRC. */ +#define BITSET_COPY_(DST, SRC) (SRC)->b.vtable->copy (DST, SRC) + +/* Return DST & SRC == 0. */ +#define BITSET_DISJOINT_P_(DST, SRC) (SRC)->b.vtable->disjoint_p (DST, SRC) /* Return DST == SRC. */ -#define BITSET_EQUAL_P_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_EQUAL_P) +#define BITSET_EQUAL_P_(DST, SRC) (SRC)->b.vtable->equal_p (DST, SRC) + +/* DST = ~SRC. */ +#define BITSET_NOT_(DST, SRC) (SRC)->b.vtable->not (DST, SRC) /* Return DST == DST | SRC. */ -#define BITSET_SUBSET_P_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_SUBSET_P) +#define BITSET_SUBSET_P_(DST, SRC) (SRC)->b.vtable->subset_p (DST, SRC) -/* Return DST & SRC == 0. */ -#define BITSET_DISJOINT_P_(DST, SRC)\ - BITSET_OP2_ (DST, SRC, BITSET_OP_DISJOINT_P) -/* DST = SRC. */ -#define BITSET_COPY_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_COPY) +/* DST = SRC1 & SRC2. */ +#define BITSET_AND_(DST, SRC1, SRC2) (SRC1)->b.vtable->and (DST, SRC1, SRC2) +#define BITSET_AND_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_cmp (DST, SRC1, SRC2) -/* DST = ~SRC. */ -#define BITSET_NOT_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_NOT) +/* DST = SRC1 & ~SRC2. */ +#define BITSET_ANDN_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn (DST, SRC1, SRC2) +#define BITSET_ANDN_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn_cmp (DST, SRC1, SRC2) /* DST = SRC1 | SRC2. */ -#define BITSET_OR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\ - BITSET_OP_OR) +#define BITSET_OR_(DST, SRC1, SRC2) (SRC1)->b.vtable->or (DST, SRC1, SRC2) +#define BITSET_OR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_cmp (DST, SRC1, SRC2) /* DST = SRC1 ^ SRC2. */ -#define BITSET_XOR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\ - BITSET_OP_XOR) +#define BITSET_XOR_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor (DST, SRC1, SRC2) +#define BITSET_XOR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_cmp (DST, SRC1, SRC2) -/* DST = SRC1 & SRC2. */ -#define BITSET_AND_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ - BITSET_OP_AND) -/* DST = SRC1 & ~SRC2. */ -#define BITSET_ANDN_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ - BITSET_OP_ANDN) /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if DST != (SRC1 & SRC2) | SRC3. */ -#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3)\ - BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_AND_OR) +#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3) \ + (SRC1)->b.vtable->and_or (DST, SRC1, SRC2, SRC3) +#define BITSET_AND_OR_CMP_(DST, SRC1, SRC2, SRC3) \ + (SRC1)->b.vtable->and_or_cmp (DST, SRC1, SRC2, SRC3) + +/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if + DST != (SRC1 & ~SRC2) | SRC3. */ +#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3) \ + (SRC1)->b.vtable->andn_or (DST, SRC1, SRC2, SRC3) +#define BITSET_ANDN_OR_CMP_(DST, SRC1, SRC2, SRC3) \ + (SRC1)->b.vtable->andn_or_cmp (DST, SRC1, SRC2, SRC3) /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if DST != (SRC1 | SRC2) & SRC3. */ -#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3)\ - BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_OR_AND) +#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3) \ + (SRC1)->b.vtable->or_and (DST, SRC1, SRC2, SRC3) +#define BITSET_OR_AND_CMP_(DST, SRC1, SRC2, SRC3) \ + (SRC1)->b.vtable->or_and_cmp (DST, SRC1, SRC2, SRC3) -/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if - DST != (SRC1 & ~SRC2) | SRC3. */ -#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3)\ - BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_ANDN_OR) /* Find list of up to NUM bits set in BSET starting from and including *NEXT. Return with actual number of bits found and with *NEXT indicating where search stopped. */ #define BITSET_LIST_(BSET, LIST, NUM, NEXT) \ -(BSET)->b.ops->list (BSET, LIST, NUM, NEXT) + (BSET)->b.vtable->list (BSET, LIST, NUM, NEXT) /* Find reverse list of up to NUM bits set in BSET starting from and including NEXT. Return with actual number of bits found and with *NEXT indicating where search stopped. */ -#define BITSET_REVERSE_LIST_(BSET, LIST, NUM, NEXT) \ -(BSET)->b.ops->reverse_list (BSET, LIST, NUM, NEXT) +#define BITSET_LIST_REVERSE_(BSET, LIST, NUM, NEXT) \ + (BSET)->b.vtable->list_reverse (BSET, LIST, NUM, NEXT) -struct bbitset_struct -{ - struct bitset_ops_struct *ops; - bitset_windex cindex; /* Cache word index. */ - bitset_windex csize; /* Cache size in words. */ - bitset_word *cdata; /* Cache data pointer. */ - /* 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. - This would speed up some of the searches but slightly slow down - bit set/reset operations of cached bits. */ -}; +/* Private functions for bitset implementations. */ + +extern int bitset_toggle_ PARAMS ((bitset, bitset_bindex)); +extern int bitset_count_ PARAMS ((bitset)); -typedef struct bitset_struct *bitset; - - -/* The contents of this structure should be considered private. */ -struct bitset_ops_struct -{ - void (*set) PARAMS ((struct bitset_struct *, bitset_bindex)); - void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex)); - int (*test) PARAMS ((struct bitset_struct *, bitset_bindex)); - int (*size) PARAMS ((struct bitset_struct *)); - int (*op1) PARAMS ((struct bitset_struct *, enum bitset_ops)); - int (*op2) PARAMS ((struct bitset_struct *, struct bitset_struct *, - enum bitset_ops)); - int (*op3) PARAMS ((struct bitset_struct *, struct bitset_struct *, - struct bitset_struct *, enum bitset_ops)); - int (*op4) PARAMS ((struct bitset_struct *, struct bitset_struct *, - struct bitset_struct *, struct bitset_struct *, - enum bitset_ops)); - int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *, - bitset_bindex, bitset_bindex *)); - int (*reverse_list) PARAMS ((struct bitset_struct *, bitset_bindex *, - bitset_bindex, bitset_bindex *)); - void (*free) PARAMS ((struct bitset_struct *)); - enum bitset_type type; -}; +extern int bitset_copy_ PARAMS ((bitset, bitset)); -#define BITSET_COMPATIBLE_(BSET1, BSET2) ((BSET1)->b.ops == (BSET2)->b.ops) - -#define BITSET_CHECK2_(DST, SRC) \ -if (!BITSET_COMPATIBLE_ (DST, SRC)) abort (); - -#define BITSET_CHECK3_(DST, SRC1, SRC2) \ -if (!BITSET_COMPATIBLE_ (DST, SRC1) \ - || !BITSET_COMPATIBLE_ (DST, SRC2)) abort (); - -#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \ -if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \ - || !BITSET_COMPATIBLE_ (DST, SRC3)) abort (); +extern int bitset_and_or_cmp_ PARAMS ((bitset, bitset, bitset, bitset)); +extern int bitset_andn_or_cmp_ PARAMS ((bitset, bitset, bitset, bitset)); -extern int bitset_op4 PARAMS ((bitset, bitset, bitset, bitset, - enum bitset_ops op)); +extern int bitset_or_and_cmp_ PARAMS ((bitset, bitset, bitset, bitset)); #endif /* _BBITSET_H */ diff --git a/lib/bitset.c b/lib/bitset.c index 0e8d26c9..4a0f9c02 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -28,6 +28,8 @@ #include "bitset_stats.h" #include "obstack.h" +const char * const bitset_type_names[] = BITSET_TYPE_NAMES; + static void bitset_print PARAMS ((FILE *, bitset, int)); @@ -108,10 +110,8 @@ bitset_type_choose (n_bits, attr) if (attr & BITSET_SPARSE && attr & BITSET_DENSE) abort (); - /* Note that sometimes we will be asked for a zero length - fixed size bitset. */ - - /* Choose the type of bitset. */ + /* 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. */ @@ -215,6 +215,19 @@ bitset_type_get (bset) } +/* Return name of bitset type. */ +const char * +bitset_type_name_get (bset) + bitset bset; +{ + enum bitset_type type; + + type = bitset_type_get (bset); + + return bitset_type_names[type]; +} + + /* Find next bit set in SRC starting from and including BITNO. Return -1 if SRC empty. */ int @@ -241,7 +254,7 @@ bitset_prev (src, bitno) bitset_bindex val; bitset_bindex next = bitno; - if (!bitset_reverse_list (src, &val, 1, &next)) + if (!bitset_list_reverse (src, &val, 1, &next)) return -1; return val; } @@ -280,27 +293,6 @@ bitset_only_set_p (src, bitno) } -/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */ -int -bitset_toggle (bset, bitno) - bitset bset; - bitset_bindex bitno; -{ - /* This routine is for completeness. It could be optimized if - required. */ - if (bitset_test (bset, bitno)) - { - bitset_reset (bset, bitno); - return 0; - } - else - { - bitset_set (bset, bitno); - return 1; - } -} - - /* Print contents of bitset BSET to FILE. */ static void bitset_print (file, bset, verbose) @@ -308,7 +300,8 @@ bitset_print (file, bset, verbose) bitset bset; int verbose; { - unsigned int i, pos; + unsigned int pos; + bitset_bindex i; bitset_iterator iter; if (verbose) @@ -332,42 +325,51 @@ bitset_print (file, bset, verbose) } -/* DST = SRC. Return non-zero if DST != SRC. */ -int -bitset_copy (dst, src) - bitset dst; - bitset src; +/* Dump bitset BSET to FILE. */ +void +bitset_dump (file, bset) + FILE *file; + bitset bset; { - unsigned int i; - bitset_iterator iter; + bitset_print (file, bset, 0); +} - if (BITSET_COMPATIBLE_ (dst, src)) - return BITSET_COPY_ (dst, src); - /* Convert bitset types. We assume that the DST bitset - is large enough to hold the SRC bitset. */ - bitset_zero (dst); - BITSET_FOR_EACH (iter, src, i, 0) - { - bitset_set (dst, i); - }; - return 1; +/* Release memory associated with bitsets. */ +void +bitset_release_memory () +{ + lbitset_release_memory (); + ebitset_release_memory (); } -/* Return size in bits of bitset SRC. */ + +/* Toggle bit BITNO in bitset BSET and return non-zero if not set. */ int -bitset_size (src) - bitset src; +bitset_toggle_ (bset, bitno) + bitset bset; + bitset_bindex bitno; { - return BITSET_SIZE_ (src); + /* This routine is for completeness. It could be optimized if + required. */ + if (bitset_test (bset, bitno)) + { + bitset_reset (bset, bitno); + return 0; + } + else + { + bitset_set (bset, bitno); + return 1; + } } /* Return number of bits set in bitset SRC. */ int -bitset_count (src) +bitset_count_ (src) bitset src; { bitset_bindex list[BITSET_LIST_SIZE]; @@ -388,121 +390,33 @@ bitset_count (src) } -/* DST = 0. */ -int -bitset_zero (dst) - bitset dst; -{ - return BITSET_ZERO_ (dst); -} - - -/* DST = ~0. */ -int -bitset_ones (dst) - bitset dst; -{ - return BITSET_ONES_ (dst); -} - - -/* Return SRC == 0. */ -int -bitset_empty_p (src) - bitset src; -{ - return BITSET_EMPTY_P_ (src); -} - - -/* Return DST == DST | SRC. */ -int -bitset_subset_p (dst, src) - bitset dst; - bitset src; -{ - return BITSET_SUBSET_P_ (dst, src); -} - - -/* Return DST == SRC. */ -int -bitset_equal_p (dst, src) - bitset dst; - bitset src; -{ - return BITSET_EQUAL_P_ (dst, src); -} - - -/* Return DST & SRC == 0. */ +/* DST = SRC. Return non-zero if DST != SRC. + This is a fallback for the case where SRC and DST are different + bitset types. */ int -bitset_disjoint_p (dst, src) +bitset_copy_ (dst, src) bitset dst; bitset src; { - return BITSET_DISJOINT_P_ (dst, src); -} - - -/* DST = ~SRC. */ -int -bitset_not (dst, src) - bitset dst; - bitset src; -{ - return BITSET_NOT_ (dst, src); -} - - -/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */ -int -bitset_or (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - return BITSET_OR_ (dst, src1, src2); -} - - -/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */ -int -bitset_and (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - return BITSET_AND_ (dst, src1, src2); -} - - -/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */ -int -bitset_xor (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - return BITSET_XOR_ (dst, src1, src2); -} + bitset_bindex i; + bitset_iterator iter; + /* Convert bitset types. We assume that the DST bitset + is large enough to hold the SRC bitset. */ + bitset_zero (dst); + BITSET_FOR_EACH (iter, src, i, 0) + { + bitset_set (dst, i); + }; -/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */ -int -bitset_andn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - return BITSET_ANDN_ (dst, src1, src2); + return 1; } /* This is a fallback for implementations that do not support four operand operations. */ -int -bitset_op4 (dst, src1, src2, src3, op) +static inline int +bitset_op4_cmp (dst, src1, src2, src3, op) bitset dst; bitset src1; bitset src2; @@ -510,26 +424,30 @@ bitset_op4 (dst, src1, src2, src3, op) enum bitset_ops op; { int changed = 0; + int stats_enabled_save; bitset tmp; /* Create temporary bitset. */ + stats_enabled_save = bitset_stats_enabled; + bitset_stats_enabled = 0; tmp = bitset_alloc (0, bitset_type_get (dst)); + bitset_stats_enabled = stats_enabled_save; switch (op) { case BITSET_OP_OR_AND: - BITSET_OR_ (tmp, src1, src2); - changed = BITSET_AND_ (dst, src3, tmp); + bitset_or (tmp, src1, src2); + changed = bitset_and_cmp (dst, src3, tmp); break; case BITSET_OP_AND_OR: - BITSET_AND_ (tmp, src1, src2); - changed = BITSET_OR_ (dst, src3, tmp); + bitset_and (tmp, src1, src2); + changed = bitset_or_cmp (dst, src3, tmp); break; case BITSET_OP_ANDN_OR: - BITSET_ANDN_ (tmp, src1, src2); - changed = BITSET_OR_ (dst, src3, tmp); + bitset_andn (tmp, src1, src2); + changed = bitset_or_cmp (dst, src3, tmp); break; default: @@ -541,52 +459,42 @@ bitset_op4 (dst, src1, src2, src3, op) } -/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if - DST != (SRC1 | SRC2) & SRC3. */ +/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if + DST != (SRC1 & SRC2) | SRC3. */ int -bitset_or_and (dst, src1, src2, src3) +bitset_and_or_cmp_ (dst, src1, src2, src3) bitset dst; bitset src1; bitset src2; bitset src3; { - return BITSET_OR_AND_ (dst, src1, src2, src3); + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR); } -/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if - DST != (SRC1 & SRC2) | SRC3. */ +/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if + DST != (SRC1 & ~SRC2) | SRC3. */ int -bitset_and_or (dst, src1, src2, src3) +bitset_andn_or_cmp_ (dst, src1, src2, src3) bitset dst; bitset src1; bitset src2; bitset src3; { - return BITSET_AND_OR_ (dst, src1, src2, src3); + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR); } -/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if - DST != (SRC1 & ~SRC2) | SRC3. */ +/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if + DST != (SRC1 | SRC2) & SRC3. */ int -bitset_andn_or (dst, src1, src2, src3) +bitset_or_and_cmp_ (dst, src1, src2, src3) bitset dst; bitset src1; bitset src2; bitset src3; { - return BITSET_ANDN_OR_ (dst, src1, src2, src3); -} - - -/* Dump bitset BSET to FILE. */ -void -bitset_dump (file, bset) - FILE *file; - bitset bset; -{ - bitset_print (file, bset, 0); + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND); } @@ -598,12 +506,3 @@ debug_bitset (bset) if (bset) bitset_print (stderr, bset, 1); } - - -/* Release memory associated with bitsets. */ -void -bitset_release_memory () -{ - lbitset_release_memory (); - ebitset_release_memory (); -} diff --git a/lib/bitset.h b/lib/bitset.h index 42cf06f9..7d794909 100644 --- a/lib/bitset.h +++ b/lib/bitset.h @@ -32,7 +32,7 @@ enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */ BITSET_DENSE = 4, /* Bitset dense. */ BITSET_SPARSE = 8, /* Bitset sparse. */ BITSET_FRUGAL = 16, /* Prefer most compact. */ - BITSET_GREEDY = 32}; /* Prefer fastest. */ + BITSET_GREEDY = 32}; /* Prefer fastest at memory expense. */ typedef unsigned int bitset_attrs; @@ -84,15 +84,12 @@ extern void bitset_obstack_free PARAMS ((bitset)); /* Create a bitset of desired size and attributes. The bitset is zeroed. */ extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs)); -/* Return size in bits of bitset SRC. */ -extern int bitset_size PARAMS ((bitset)); - -/* Return number of bits set in bitset SRC. */ -extern int bitset_count PARAMS ((bitset)); - /* Return bitset type. */ extern enum bitset_type bitset_type_get PARAMS ((bitset)); +/* Return bitset type name. */ +extern const char *bitset_type_name_get PARAMS ((bitset)); + #if BITSET_INLINE static inline void bitset_set PARAMS ((bitset, bitset_bindex)); static inline void bitset_reset PARAMS ((bitset, bitset_bindex)); @@ -169,9 +166,8 @@ do \ bitset_windex _index = _bitno / BITSET_WORD_BITS; \ bitset_windex _offset = _index - (bset)->b.cindex; \ \ - if (_offset < (bset)->b.csize) \ - (bset)->b.cdata[_offset] &= \ - ~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \ + if (_offset < (bset)->b.csize) \ + (bset)->b.cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \ else \ BITSET_RESET_ ((bset), _bitno); \ } while (0) @@ -179,86 +175,116 @@ do \ /* Test bit BITNO in bitset BSET. */ #define bitset_test(bset, bitno) \ -(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \ - ? (((int) \ - ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \ - >> ((bitno) % BITSET_WORD_BITS))) \ - & 1) \ - : BITSET_TEST_ ((bset), (bitno))) +(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \ + ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \ + >> ((bitno) % BITSET_WORD_BITS)) & 1 \ + : (unsigned int) BITSET_TEST_ ((bset), (bitno))) #endif /* Toggle bit BITNO in bitset BSET and return non-zero if now set. */ -extern int bitset_toggle PARAMS ((bitset, bitset_bindex)); +#define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno) -/* DST = 0. */ -extern int bitset_zero PARAMS ((bitset)); +/* Return size in bits of bitset SRC. */ +#define bitset_size(SRC) BITSET_SIZE_ (SRC) + +/* Return number of bits set in bitset SRC. */ +#define bitset_count(SRC) BITSET_COUNT_ (SRC) + + +/* Return SRC == 0. */ +#define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC) /* DST = ~0. */ -extern int bitset_ones PARAMS ((bitset)); +#define bitset_ones(DST) BITSET_ONES_ (DST) -/* Return non-zero if all bits in bitset SRC are reset. */ -extern int bitset_empty_p PARAMS ((bitset)); +/* DST = 0. */ +#define bitset_zero(DST) BITSET_ZERO_ (DST) -/* Return DST == DST | SRC. */ -extern int bitset_subset_p PARAMS ((bitset, bitset)); -/* Return DST == SRC. */ -extern int bitset_equal_p PARAMS ((bitset, bitset)); + +/* DST = SRC. */ +#define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC) /* Return DST & SRC == 0. */ -extern int bitset_disjoint_p PARAMS ((bitset, bitset)); +#define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC) -/* DST == SRC. */ -extern int bitset_copy PARAMS ((bitset, bitset)); +/* Return DST == SRC. */ +#define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC) /* DST = ~SRC. */ -extern int bitset_not PARAMS ((bitset, bitset)); +#define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC) + +/* Return DST == DST | SRC. */ +#define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC) -/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */ -extern int bitset_or PARAMS ((bitset, bitset, bitset)); + + +/* DST = SRC1 & SRC2. */ +#define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2) /* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */ -extern int bitset_and PARAMS ((bitset, bitset, bitset)); +#define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2) -/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */ -extern int bitset_xor PARAMS ((bitset, bitset, bitset)); +/* DST = SRC1 & ~SRC2. */ +#define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2) /* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */ -extern int bitset_andn PARAMS ((bitset, bitset, bitset)); +#define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2) -/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if - DST != (SRC1 | SRC2) & SRC3. */ -extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset)); +/* DST = SRC1 | SRC2. */ +#define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2) + +/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */ +#define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2) + +/* DST = SRC1 ^ SRC2. */ +#define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2) + +/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */ +#define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2) + + + +/* DST = (SRC1 & SRC2) | SRC3. */ +#define bitset_and_or(DST, SRC1, SRC2, SRC3) \ + BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3) /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if DST != (SRC1 & SRC2) | SRC3. */ -extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset)); +#define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \ + BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3) + +/* DST = (SRC1 & ~SRC2) | SRC3. */ +#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \ + BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3) /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if DST != (SRC1 & ~SRC2) | SRC3. */ -extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset)); - -/* Find next bit set in BSET starting from and including BITNO. */ -extern int bitset_next PARAMS ((bitset, bitset_bindex)); +#define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \ + BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3) -/* Find previous bit set in BSET starting from and including BITNO. */ -extern int bitset_prev PARAMS ((bitset, bitset_bindex)); +/* DST = (SRC1 | SRC2) & SRC3. */ +#define bitset_or_and(DST, SRC1, SRC2, SRC3)\ + BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3) -/* Return non-zero if BITNO in SRC is the only set bit. */ -extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex)); +/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if + DST != (SRC1 | SRC2) & SRC3. */ +#define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\ + BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3) /* Find list of up to NUM bits set in BSET starting from and including *NEXT. Return with actual number of bits found and with *NEXT indicating where search stopped. */ #define bitset_list(BSET, LIST, NUM, NEXT) \ -BITSET_LIST_ (BSET, LIST, NUM, NEXT) + BITSET_LIST_ (BSET, LIST, NUM, NEXT) /* Find reverse list of up to NUM bits set in BSET starting from and including NEXT. Return with actual number of bits found and with *NEXT indicating where search stopped. */ -#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \ -BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT) +#define bitset_list_reverse(BSET, LIST, NUM, NEXT) \ + BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT) + /* Find first set bit. */ extern int bitset_first PARAMS ((bitset)); @@ -270,7 +296,18 @@ extern int bitset_last PARAMS ((bitset)); extern void bitset_dump PARAMS ((FILE *, bitset)); /* Loop over all elements of BSET, starting with MIN, setting BIT - to the index of each set bit. */ + to the index of each set bit. For example, the following will print + the bits set in a bitset: + + bitset_bindex i; + bitset_iterator iter; + + bitset_zero (dst); + BITSET_FOR_EACH (iter, src, i, 0) + { + printf ("%ld ", i); + }; +*/ #define BITSET_FOR_EACH(ITER, BSET, BIT, MIN) \ for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \ (ITER.num == BITSET_LIST_SIZE) \ @@ -280,7 +317,18 @@ extern void bitset_dump PARAMS ((FILE *, bitset)); /* Loop over all elements of BSET, in reverse order starting with - MIN, setting BIT to the index of each set bit. */ + MIN, setting BIT 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; + bitset_iterator iter; + + bitset_zero (dst); + BITSET_FOR_EACH_REVERSE (iter, src, i, 0) + { + printf ("%ld ", i); + }; +*/ #define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN) \ for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \ (ITER.num == BITSET_LIST_SIZE) \ @@ -291,14 +339,25 @@ extern void bitset_dump PARAMS ((FILE *, bitset)); /* Define set operations in terms of logical operations. */ -#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2) +#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2) +#define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2) -#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2) +#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2) +#define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2) -#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2) +#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2) +#define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2) +/* Symmetrical difference. */ +#define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2) +#define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2) + +/* Union of difference. */ #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \ 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. */ diff --git a/lib/bitset_stats.c b/lib/bitset_stats.c index 11f3d6f8..629c0e19 100644 --- a/lib/bitset_stats.c +++ b/lib/bitset_stats.c @@ -118,16 +118,12 @@ int bitset_stats_enabled = 0; static void bitset_stats_set PARAMS ((bitset, bitset_bindex)); static void bitset_stats_reset PARAMS ((bitset, bitset_bindex)); +static int bitset_stats_toggle PARAMS ((bitset, bitset_bindex)); static int bitset_stats_test PARAMS ((bitset, bitset_bindex)); static int bitset_stats_size PARAMS ((bitset)); -static int bitset_stats_op1 PARAMS ((bitset, enum bitset_ops)); -static int bitset_stats_op2 PARAMS ((bitset, bitset, enum bitset_ops)); -static int bitset_stats_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); -static int bitset_stats_op4 PARAMS ((bitset, bitset, bitset, bitset, - enum bitset_ops)); static int bitset_stats_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); -static int bitset_stats_reverse_list +static int bitset_stats_list_reverse PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); static void bitset_stats_free PARAMS ((bitset)); static void bitset_percent_histogram_print PARAMS ((FILE *, const char *, @@ -183,7 +179,6 @@ bitset_log_histogram_print (file, name, msg, n_bins, bins) unsigned int i; unsigned int total; unsigned int max_width; - unsigned int last_bin; total = 0; for (i = 0; i < n_bins; i++) @@ -192,9 +187,10 @@ bitset_log_histogram_print (file, name, msg, n_bins, bins) if (!total) return; + /* Determine number of useful bins. */ for (i = n_bins; i > 3 && ! bins[i - 1]; i--) continue; - last_bin = i - 1; + n_bins = i; /* 2 * ceil (log10 (2) * (N - 1)) + 1. */ max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1; @@ -204,7 +200,7 @@ bitset_log_histogram_print (file, name, msg, n_bins, bins) fprintf (file, "%*d\t%8d (%5.1f%%)\n", max_width, i, bins[i], 100.0 * bins[i] / total); - for (; i <= last_bin; i++) + for (; i < n_bins; i++) fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n", max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1), 1 << (i - 1), (1 << i) - 1, bins[i], @@ -256,7 +252,6 @@ bitset_stats_print (file, verbose) int verbose ATTRIBUTE_UNUSED; { int i; - static const char *names[] = BITSET_TYPE_NAMES; if (!bitset_stats_info) return; @@ -267,7 +262,8 @@ bitset_stats_print (file, verbose) fprintf (file, _("Accumulated runs = %d\n"), bitset_stats_info->runs); for (i = 0; i < BITSET_TYPE_NUM; i++) - bitset_stats_print_1 (file, names[i], &bitset_stats_info->types[i]); + bitset_stats_print_1 (file, bitset_type_names[i], + &bitset_stats_info->types[i]); } @@ -404,6 +400,15 @@ bitset_stats_reset (dst, bitno) } +static int +bitset_stats_toggle (src, bitno) + bitset src; + bitset_bindex bitno; +{ + return BITSET_TOGGLE_ (src->s.bset, bitno); +} + + static int bitset_stats_test (src, bitno) bitset src; @@ -434,56 +439,250 @@ bitset_stats_size (src) static int -bitset_stats_op1 (dst, op) +bitset_stats_count (src) + bitset src; +{ + return BITSET_COUNT_ (src->s.bset); +} + + +static int +bitset_stats_empty_p (dst) + bitset dst; +{ + return BITSET_EMPTY_P_ (dst->s.bset); +} + + +static void +bitset_stats_ones (dst) + bitset dst; +{ + BITSET_ONES_ (dst->s.bset); +} + + +static void +bitset_stats_zero (dst) + bitset dst; +{ + BITSET_ZERO_ (dst->s.bset); +} + + +static void +bitset_stats_copy (dst, src) + bitset dst; + bitset src; +{ + BITSET_CHECK2_ (dst, src); + BITSET_COPY_ (dst->s.bset, src->s.bset); +} + + +static int +bitset_stats_disjoint_p (dst, src) bitset dst; - enum bitset_ops op; + bitset src; { - return BITSET_OP1_ (dst->s.bset, op); + BITSET_CHECK2_ (dst, src); + return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset); } static int -bitset_stats_op2 (dst, src, op) +bitset_stats_equal_p (dst, src) bitset dst; bitset src; - enum bitset_ops op; { BITSET_CHECK2_ (dst, src); - return BITSET_OP2_ (dst->s.bset, src->s.bset, op); + return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset); +} + + +static void +bitset_stats_not (dst, src) + bitset dst; + bitset src; +{ + BITSET_CHECK2_ (dst, src); + BITSET_NOT_ (dst->s.bset, src->s.bset); +} + + +static int +bitset_stats_subset_p (dst, src) + bitset dst; + bitset src; +{ + BITSET_CHECK2_ (dst, src); + return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset); +} + + +static void +bitset_stats_and (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + BITSET_CHECK3_ (dst, src1, src2); + BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset); +} + + +static int +bitset_stats_and_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); +} + + +static void +bitset_stats_andn (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + BITSET_CHECK3_ (dst, src1, src2); + BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset); +} + + +static int +bitset_stats_andn_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); +} + + +static void +bitset_stats_or (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + BITSET_CHECK3_ (dst, src1, src2); + BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset); +} + + +static int +bitset_stats_or_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); +} + + +static void +bitset_stats_xor (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + BITSET_CHECK3_ (dst, src1, src2); + BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset); } static int -bitset_stats_op3 (dst, src1, src2, op) +bitset_stats_xor_cmp (dst, src1, src2) bitset dst; bitset src1; bitset src2; - enum bitset_ops op; { BITSET_CHECK3_ (dst, src1, src2); - return BITSET_OP3_ (dst->s.bset, src1->s.bset, src2->s.bset, op); + return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); +} + + +static void +bitset_stats_and_or (dst, src1, src2, src3) + 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); } static int -bitset_stats_op4 (dst, src1, src2, src3, op) +bitset_stats_and_or_cmp (dst, src1, src2, src3) bitset dst; bitset src1; bitset src2; bitset src3; - enum bitset_ops op; { BITSET_CHECK4_ (dst, src1, src2, src3); - /* This is a bit of a hack. If the implementation handles - a four operand operation then vector to it, passing - the enclosed bitsets. Otherwise use the fallback - bitset_op4 routine. */ - if (dst->s.bset->b.ops->op4 != bitset_op4) - return BITSET_OP4_ (dst->s.bset, src1->s.bset, src2->s.bset, - src3->s.bset, op); + return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); +} + + +static void +bitset_stats_andn_or (dst, src1, src2, src3) + 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); +} + + +static int +bitset_stats_andn_or_cmp (dst, src1, src2, src3) + 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); +} + + +static void +bitset_stats_or_and (dst, src1, src2, src3) + 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); +} + + +static int +bitset_stats_or_and_cmp (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + BITSET_CHECK4_ (dst, src1, src2, src3); - return bitset_op4 (dst, src1, src2, src3, op); + return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); } @@ -530,13 +729,13 @@ bitset_stats_list (bset, list, num, next) static int -bitset_stats_reverse_list (bset, list, num, next) +bitset_stats_list_reverse (bset, list, num, next) bitset bset; bitset_bindex *list; bitset_bindex num; bitset_bindex *next; { - return BITSET_REVERSE_LIST_ (bset->s.bset, list, num, next); + return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next); } @@ -549,17 +748,37 @@ bitset_stats_free (bset) } -struct bitset_ops_struct bitset_stats_ops = { +struct bitset_vtable bitset_stats_vtable = { bitset_stats_set, bitset_stats_reset, + bitset_stats_toggle, bitset_stats_test, bitset_stats_size, - bitset_stats_op1, - bitset_stats_op2, - bitset_stats_op3, - bitset_stats_op4, + bitset_stats_count, + bitset_stats_empty_p, + bitset_stats_ones, + bitset_stats_zero, + bitset_stats_copy, + bitset_stats_disjoint_p, + bitset_stats_equal_p, + bitset_stats_not, + bitset_stats_subset_p, + bitset_stats_and, + bitset_stats_and_cmp, + bitset_stats_andn, + bitset_stats_andn_cmp, + bitset_stats_or, + bitset_stats_or_cmp, + bitset_stats_xor, + bitset_stats_xor_cmp, + bitset_stats_and_or, + bitset_stats_and_or_cmp, + bitset_stats_andn_or, + bitset_stats_andn_or_cmp, + bitset_stats_or_and, + bitset_stats_or_and_cmp, bitset_stats_list, - bitset_stats_reverse_list, + bitset_stats_list_reverse, bitset_stats_free, BITSET_STATS }; @@ -589,7 +808,7 @@ bitset_stats_init (bset, n_bits, type) unsigned int bytes; bitset sbset; - bset->b.ops = &bitset_stats_ops; + bset->b.vtable = &bitset_stats_vtable; /* Disable cache. */ bset->b.cindex = 0; diff --git a/lib/bitsetv.c b/lib/bitsetv.c index 3d8e368a..ab2ed1ea 100644 --- a/lib/bitsetv.c +++ b/lib/bitsetv.c @@ -1,5 +1,5 @@ /* Bitset vectors. - Copyright (C) 2001 Free Software Foundation, Inc. + Copyright (C) 2001, 2002 Free Software Foundation, Inc. This file is part of GCC. diff --git a/lib/ebitset.c b/lib/ebitset.c index 9751e4dd..1d25b7c9 100644 --- a/lib/ebitset.c +++ b/lib/ebitset.c @@ -77,6 +77,9 @@ typedef struct ebitset_struct *ebitset; +typedef void(*PFV)(); + + /* Number of elements to initially allocate. */ #ifndef EBITSET_INITIAL_SIZE @@ -118,19 +121,24 @@ static int ebitset_elt_zero_p PARAMS ((ebitset_elt *)); static int ebitset_weed PARAMS ((bitset)); static void ebitset_zero PARAMS ((bitset)); -static int ebitset_equal_p PARAMS ((bitset, bitset)); -static void ebitset_copy PARAMS ((bitset, bitset)); -static int ebitset_copy_compare PARAMS ((bitset, bitset)); +static void ebitset_copy_ PARAMS ((bitset, bitset)); +static int ebitset_copy_cmp PARAMS ((bitset, bitset)); static void ebitset_set PARAMS ((bitset, bitset_bindex)); static void ebitset_reset PARAMS ((bitset, bitset_bindex)); static int ebitset_test PARAMS ((bitset, bitset_bindex)); static int ebitset_size PARAMS ((bitset)); -static int ebitset_op1 PARAMS ((bitset, enum bitset_ops)); -static int ebitset_op2 PARAMS ((bitset, bitset, enum bitset_ops)); -static int ebitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); +static int ebitset_disjoint_p PARAMS ((bitset, bitset)); +static int ebitset_equal_p PARAMS ((bitset, bitset)); +static void ebitset_not PARAMS ((bitset, bitset)); +static int ebitset_subset_p PARAMS ((bitset, bitset)); +static int ebitset_op3_cmp PARAMS ((bitset, bitset, bitset, enum bitset_ops)); +static int ebitset_and_cmp PARAMS ((bitset, bitset, bitset)); +static int ebitset_andn_cmp PARAMS ((bitset, bitset, bitset)); +static int ebitset_or_cmp PARAMS ((bitset, bitset, bitset)); +static int ebitset_xor_cmp PARAMS ((bitset, bitset, bitset)); static int ebitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); -static int ebitset_reverse_list +static int ebitset_list_reverse PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); static void ebitset_free PARAMS ((bitset)); @@ -141,7 +149,7 @@ static void ebitset_free PARAMS ((bitset)); #define EBITSET_WORDS(ELT) ((ELT)->u.words) /* Disable bitset cache and mark BSET as being zero. */ -#define EBITSET_OP_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX, \ +#define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX, \ (BSET)->b.cdata = 0) #define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX) @@ -152,7 +160,7 @@ static void ebitset_free PARAMS ((bitset)); /* A conservative estimate of whether the bitset is zero. This is non-zero only if we know for sure that the bitset is zero. */ -#define EBITSET_OP_ZERO_P(BSET) ((BSET)->b.cdata == 0) +#define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0) /* Enable cache to point to element with table index EINDEX. The element must exist. */ @@ -395,7 +403,7 @@ ebitset_weed (bset) bitset_windex j; int count; - if (EBITSET_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return 0; elts = EBITSET_ELTS (bset); @@ -421,7 +429,7 @@ ebitset_weed (bset) { /* All the bits are zero. We could shrink the elts. For now just mark BSET as known to be zero. */ - EBITSET_OP_ZERO_SET (bset); + EBITSET_ZERO_SET (bset); } else EBITSET_NONZERO_SET (bset); @@ -438,7 +446,7 @@ ebitset_zero (bset) ebitset_elts *elts; bitset_windex j; - if (EBITSET_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return; elts = EBITSET_ELTS (bset); @@ -452,7 +460,7 @@ ebitset_zero (bset) /* All the bits are zero. We could shrink the elts. For now just mark BSET as known to be zero. */ - EBITSET_OP_ZERO_SET (bset); + EBITSET_ZERO_SET (bset); } @@ -498,7 +506,7 @@ ebitset_equal_p (dst, src) /* Copy bits from bitset SRC to bitset DST. */ static inline void -ebitset_copy (dst, src) +ebitset_copy_ (dst, src) bitset dst; bitset src; { @@ -537,23 +545,23 @@ ebitset_copy (dst, src) /* Copy bits from bitset SRC to bitset DST. Return non-zero if bitsets different. */ static inline int -ebitset_copy_compare (dst, src) +ebitset_copy_cmp (dst, src) bitset dst; bitset src; { if (src == dst) return 0; - if (EBITSET_OP_ZERO_P (dst)) + if (EBITSET_ZERO_P (dst)) { - ebitset_copy (dst, src); - return !EBITSET_OP_ZERO_P (src); + ebitset_copy_ (dst, src); + return !EBITSET_ZERO_P (src); } if (ebitset_equal_p (dst, src)) return 0; - ebitset_copy (dst, src); + ebitset_copy_ (dst, src); return 1; } @@ -632,7 +640,7 @@ ebitset_free (bset) *NEXT and store in array LIST. Return with actual number of bits found and with *NEXT indicating where search stopped. */ static int -ebitset_reverse_list (bset, list, num, next) +ebitset_list_reverse (bset, list, num, next) bitset bset; bitset_bindex *list; bitset_bindex num; @@ -650,7 +658,7 @@ ebitset_reverse_list (bset, list, num, next) bitset_windex size; ebitset_elts *elts; - if (EBITSET_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return 0; size = EBITSET_SIZE (bset); @@ -678,20 +686,19 @@ ebitset_reverse_list (bset, list, num, next) do { ebitset_elt *elt; - + bitset_word *srcp; + elt = elts[eindex]; if (elt) - { - bitset_word *srcp; - + { srcp = EBITSET_WORDS (elt); - + do { bitset_word word; - + word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); - + for (; word; bcount--) { if (word & BITSET_MSB) @@ -705,15 +712,13 @@ ebitset_reverse_list (bset, list, num, next) } word <<= 1; } - boffset -= BITSET_WORD_BITS; - bcount = BITSET_WORD_BITS - 1; + bcount = BITSET_WORD_BITS - 1; } while (woffset--); - - woffset = EBITSET_ELT_WORDS; } + woffset = EBITSET_ELT_WORDS - 1; boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS; } while (eindex--); @@ -742,7 +747,7 @@ ebitset_list (bset, list, num, next) bitset_word word; ebitset_elts *elts; - if (EBITSET_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return 0; bitno = *next; @@ -866,156 +871,145 @@ ebitset_list (bset, list, num, next) } -static int -ebitset_op1 (dst, op) +static void +ebitset_ones (dst) bitset dst; - enum bitset_ops op; { bitset_windex j; ebitset_elt *elt; - switch (op) - { - case BITSET_OP_ZERO: - ebitset_zero (dst); - return 1; - - case BITSET_OP_ONES: - 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. */ - elt = - ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); - memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt))); - } - break; - - case BITSET_OP_EMPTY_P: - return !ebitset_weed (dst); - default: - abort (); + 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. */ + elt = + ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); + memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt))); } - EBITSET_NONZERO_SET (dst); - return 1; } static int -ebitset_op2 (dst, src, op) +ebitset_empty_p (dst) + bitset dst; +{ + return !ebitset_weed (dst); +} + + +static void +ebitset_not (dst, src) bitset dst; bitset src; - enum bitset_ops op; { + unsigned int i; ebitset_elt *selt; ebitset_elt *delt; - unsigned int i; bitset_windex j; - switch (op) + for (j = 0; j < EBITSET_SIZE (src); j++) { - case BITSET_OP_COPY: - ebitset_copy (dst, src); - break; - - case BITSET_OP_NOT: - for (j = 0; j < EBITSET_SIZE (src); j++) - { - /* Create new elements for dst if they cannot be found + /* Create new elements for dst if they cannot be found or substitute zero elements if src elements not found. */ - selt = - ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST); - delt = - ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); + selt = + ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST); + delt = + ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); - for (i = 0; i < EBITSET_ELT_WORDS; i++) - EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; - } - break; - - /* Return 1 if DST == SRC. */ - case BITSET_OP_EQUAL_P: - return ebitset_equal_p (dst, src); - - /* Return 1 if DST == DST | SRC. */ - case BITSET_OP_SUBSET_P: - { - ebitset_elts *selts; - ebitset_elts *delts; - bitset_windex ssize; - bitset_windex dsize; - - selts = EBITSET_ELTS (src); - delts = EBITSET_ELTS (dst); - - ssize = EBITSET_SIZE (src); - dsize = EBITSET_SIZE (dst); - - for (j = 0; j < ssize; j++) - { - selt = j < ssize ? selts[j] : 0; - delt = j < dsize ? delts[j] : 0; - - if (!selt && !delt) - continue; - - if (!selt) - selt = &ebitset_zero_elts[0]; - if (!delt) - delt = &ebitset_zero_elts[0]; - - for (i = 0; i < EBITSET_ELT_WORDS; i++) - if (EBITSET_WORDS (delt)[i] - != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i])) - return 0; - } - return 1; - } - break; - - /* Return 1 if DST & SRC == 0. */ - case BITSET_OP_DISJOINT_P: - { - ebitset_elts *selts; - ebitset_elts *delts; - bitset_windex ssize; - bitset_windex dsize; - - selts = EBITSET_ELTS (src); - delts = EBITSET_ELTS (dst); - - ssize = EBITSET_SIZE (src); - dsize = EBITSET_SIZE (dst); - - for (j = 0; j < ssize; j++) - { - selt = j < ssize ? selts[j] : 0; - delt = j < dsize ? delts[j] : 0; - - if (!selt || !delt) - continue; - - for (i = 0; i < EBITSET_ELT_WORDS; i++) - if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i])) - return 0; - } - return 1; - } - break; + for (i = 0; i < EBITSET_ELT_WORDS; i++) + EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; + } + EBITSET_NONZERO_SET (dst); +} - default: - abort (); + +/* Return 1 if DST == DST | SRC. */ +static int +ebitset_subset_p (dst, src) + bitset dst; + bitset src; +{ + bitset_windex j; + ebitset_elts *selts; + ebitset_elts *delts; + bitset_windex ssize; + bitset_windex dsize; + + selts = EBITSET_ELTS (src); + delts = EBITSET_ELTS (dst); + + ssize = EBITSET_SIZE (src); + dsize = EBITSET_SIZE (dst); + + for (j = 0; j < ssize; j++) + { + unsigned int i; + ebitset_elt *selt; + ebitset_elt *delt; + + selt = j < ssize ? selts[j] : 0; + delt = j < dsize ? delts[j] : 0; + + if (!selt && !delt) + continue; + + if (!selt) + selt = &ebitset_zero_elts[0]; + if (!delt) + delt = &ebitset_zero_elts[0]; + + for (i = 0; i < EBITSET_ELT_WORDS; i++) + if (EBITSET_WORDS (delt)[i] + != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i])) + return 0; } + return 1; +} - EBITSET_NONZERO_SET (dst); + +/* Return 1 if DST & SRC == 0. */ +static int +ebitset_disjoint_p (dst, src) + bitset dst; + bitset src; +{ + bitset_windex j; + ebitset_elts *selts; + ebitset_elts *delts; + bitset_windex ssize; + bitset_windex dsize; + + selts = EBITSET_ELTS (src); + delts = EBITSET_ELTS (dst); + + ssize = EBITSET_SIZE (src); + dsize = EBITSET_SIZE (dst); + + for (j = 0; j < ssize; j++) + { + unsigned int i; + ebitset_elt *selt; + ebitset_elt *delt; + + selt = j < ssize ? selts[j] : 0; + delt = j < dsize ? delts[j] : 0; + + if (!selt || !delt) + continue; + + for (i = 0; i < EBITSET_ELT_WORDS; i++) + if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i])) + return 0; + } return 1; } + static int -ebitset_op3 (dst, src1, src2, op) +ebitset_op3_cmp (dst, src1, src2, op) bitset dst; bitset src1; bitset src2; @@ -1035,37 +1029,6 @@ ebitset_op3 (dst, src1, src2, op) unsigned int i; bitset_windex j; - /* Fast track common, simple cases. */ - if (EBITSET_OP_ZERO_P (src2)) - { - if (op == BITSET_OP_AND) - { - ebitset_weed (dst); - changed = EBITSET_OP_ZERO_P (dst); - ebitset_zero (dst); - return changed; - } - else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR - || op == BITSET_OP_XOR) - { - return ebitset_copy_compare (dst, src1); - } - } - else if (EBITSET_OP_ZERO_P (src1)) - { - if (op == BITSET_OP_AND || op == BITSET_OP_ANDN) - { - ebitset_weed (dst); - changed = EBITSET_OP_ZERO_P (dst); - ebitset_zero (dst); - return changed; - } - else if (op == BITSET_OP_OR || op == BITSET_OP_XOR) - { - return ebitset_copy_compare (dst, src2); - } - } - ssize1 = EBITSET_SIZE (src1); ssize2 = EBITSET_SIZE (src2); dsize = EBITSET_SIZE (dst); @@ -1198,18 +1161,135 @@ ebitset_op3 (dst, src1, src2, op) } +static int +ebitset_and_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + int changed; + + if (EBITSET_ZERO_P (src2)) + { + ebitset_weed (dst); + changed = EBITSET_ZERO_P (dst); + ebitset_zero (dst); + return changed; + } + else if (EBITSET_ZERO_P (src1)) + { + ebitset_weed (dst); + changed = EBITSET_ZERO_P (dst); + ebitset_zero (dst); + return changed; + } + return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); +} + + +static int +ebitset_andn_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + int changed; + + if (EBITSET_ZERO_P (src2)) + { + return ebitset_copy_cmp (dst, src1); + } + else if (EBITSET_ZERO_P (src1)) + { + ebitset_weed (dst); + changed = EBITSET_ZERO_P (dst); + ebitset_zero (dst); + return changed; + } + return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); +} + + +static int +ebitset_or_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + if (EBITSET_ZERO_P (src2)) + { + return ebitset_copy_cmp (dst, src1); + } + else if (EBITSET_ZERO_P (src1)) + { + return ebitset_copy_cmp (dst, src2); + } + return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); +} + + +static int +ebitset_xor_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + if (EBITSET_ZERO_P (src2)) + { + return ebitset_copy_cmp (dst, src1); + } + else if (EBITSET_ZERO_P (src1)) + { + return ebitset_copy_cmp (dst, src2); + } + return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); +} + + +static void +ebitset_copy (dst, src) + bitset dst; + bitset src; +{ + if (BITSET_COMPATIBLE_ (dst, src)) + ebitset_copy_ (dst, src); + else + bitset_copy_ (dst, src); +} + + /* Vector of operations for linked-list bitsets. */ -struct bitset_ops_struct ebitset_ops = { +struct bitset_vtable ebitset_vtable = { ebitset_set, ebitset_reset, + bitset_toggle_, ebitset_test, ebitset_size, - ebitset_op1, - ebitset_op2, - ebitset_op3, - bitset_op4, + bitset_count_, + ebitset_empty_p, + ebitset_ones, + ebitset_zero, + ebitset_copy, + ebitset_disjoint_p, + ebitset_equal_p, + ebitset_not, + ebitset_subset_p, + (PFV) ebitset_and_cmp, + ebitset_and_cmp, + (PFV) ebitset_andn_cmp, + ebitset_andn_cmp, + (PFV) ebitset_or_cmp, + ebitset_or_cmp, + (PFV) ebitset_xor_cmp, + ebitset_xor_cmp, + (PFV) bitset_and_or_cmp_, + bitset_and_or_cmp_, + (PFV) bitset_andn_or_cmp_, + bitset_andn_or_cmp_, + (PFV) bitset_or_and_cmp_, + bitset_or_and_cmp_, ebitset_list, - ebitset_reverse_list, + ebitset_list_reverse, ebitset_free, BITSET_TABLE }; @@ -1233,11 +1313,11 @@ ebitset_init (bset, n_bits) { unsigned int size; - bset->b.ops = &ebitset_ops; + bset->b.vtable = &ebitset_vtable; bset->b.csize = EBITSET_ELT_WORDS; - EBITSET_OP_ZERO_SET (bset); + EBITSET_ZERO_SET (bset); size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS : EBITSET_INITIAL_SIZE; diff --git a/lib/lbitset.c b/lib/lbitset.c index f5f8c4fa..5ce9e903 100644 --- a/lib/lbitset.c +++ b/lib/lbitset.c @@ -24,6 +24,7 @@ #include "lbitset.h" #include "obstack.h" #include +#include /* This file implements linked-list bitsets. These bitsets can be of arbitrary length and are more efficient than arrays of bits for @@ -78,6 +79,9 @@ struct bitset_struct }; +typedef void(*PFV)(); + + enum lbitset_find_mode { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST }; @@ -102,17 +106,15 @@ 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 int lbitset_copy_cmp 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_op3_cmp PARAMS ((bitset, bitset, bitset, enum bitset_ops)); static int lbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); -static int lbitset_reverse_list +static int lbitset_list_reverse PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); static void lbitset_free PARAMS ((bitset)); @@ -398,7 +400,7 @@ lbitset_elt_find (bset, windex, mode) 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) { @@ -449,7 +451,7 @@ lbitset_weed (bset) /* Set all bits in the bitset to zero. */ -static inline void +static void lbitset_zero (bset) bitset bset; { @@ -464,6 +466,7 @@ lbitset_zero (bset) } +/* Return 1 if DST == SRC. */ static inline int lbitset_equal_p (dst, src) bitset dst; @@ -538,7 +541,7 @@ lbitset_copy (dst, src) /* Copy bits from bitset SRC to bitset DST. Return non-zero if bitsets different. */ static inline int -lbitset_copy_compare (dst, src) +lbitset_copy_cmp (dst, src) bitset dst; bitset src; { @@ -636,7 +639,7 @@ lbitset_free (bset) *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) +lbitset_list_reverse (bset, list, num, next) bitset bset; bitset_bindex *list; bitset_bindex num; @@ -673,13 +676,24 @@ lbitset_reverse_list (bset, list, num, next) 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; - bcount = bitno % 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; @@ -926,56 +940,47 @@ lbitset_list (bset, list, num, next) static int -lbitset_op1 (dst, op) +lbitset_empty_p (dst) + bitset dst; +{ + lbitset_weed (dst); + if (LBITSET_HEAD (dst)) + return 0; + return 1; +} + + +static void +lbitset_ones (dst) bitset dst; - enum bitset_ops op; { unsigned int i; bitset_windex windex; lbitset_elt *elt; - switch (op) + /* 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. */ + elt = LBITSET_TAIL (dst); + /* Ignore empty set. */ + if (!elt) + return; + + windex = elt->index; + for (i = 0; i < windex; i += LBITSET_ELT_WORDS) { - case BITSET_OP_ZERO: - lbitset_zero (dst); - break; - - case BITSET_OP_ONES: - /* This is a decidedly unfriendly operation for a linked list - bitset! */ - elt = LBITSET_TAIL (dst); - /* Ignore empty set. */ - if (!elt) - return 0; - - 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, -1, sizeof (elt->words)); - } - break; - - case BITSET_OP_EMPTY_P: - lbitset_weed (dst); - if (LBITSET_HEAD (dst)) - return 0; - break; - - default: - abort (); + /* 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; } -static int -lbitset_op2 (dst, src, op) +static void +lbitset_not (dst, src) bitset dst; bitset src; - enum bitset_ops op; { lbitset_elt *elt; lbitset_elt *selt; @@ -984,106 +989,108 @@ lbitset_op2 (dst, src, op) unsigned int j; bitset_windex windex; - switch (op) + /* This is another unfriendly operation for a linked list + bitset! */ + elt = LBITSET_TAIL (dst); + /* Ignore empty set. */ + if (!elt) + return; + + windex = elt->index; + for (i = 0; i < windex; i += LBITSET_ELT_WORDS) { - case BITSET_OP_COPY: - lbitset_copy (dst, src); - break; - - 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 = 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); + /* 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_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; +/* Return 1 if DST == DST | SRC. */ +static int +lbitset_subset_p (dst, src) + 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; + + for (j = 0; j < LBITSET_ELT_WORDS; j++) + if (delt->words[j] != (selt->words[j] | delt->words[j])) + return 0; + } + return 1; +} + - /* 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) +/* Return 1 if DST & SRC == 0. */ +static int +lbitset_disjoint_p (dst, src) + 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 0; } - return 1; } static int -lbitset_op3 (dst, src1, src2, op) +lbitset_op3_cmp (dst, src1, src2, op) bitset dst; bitset src1; bitset src2; @@ -1104,37 +1111,6 @@ lbitset_op3 (dst, src1, src2, op) int changed = 0; 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; @@ -1275,18 +1251,134 @@ lbitset_op3 (dst, src1, src2, op) } +static int +lbitset_and_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + lbitset_elt *selt1 = LBITSET_HEAD (src1); + lbitset_elt *selt2 = LBITSET_HEAD (src2); + int 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 int +lbitset_andn_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + lbitset_elt *selt1 = LBITSET_HEAD (src1); + lbitset_elt *selt2 = LBITSET_HEAD (src2); + int 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 int +lbitset_or_cmp (dst, src1, src2) + 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 int +lbitset_xor_cmp (dst, src1, src2) + 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); +} + + + /* Vector of operations for linked-list bitsets. */ -struct bitset_ops_struct lbitset_ops = { +struct bitset_vtable lbitset_vtable = { lbitset_set, lbitset_reset, + bitset_toggle_, lbitset_test, lbitset_size, - lbitset_op1, - lbitset_op2, - lbitset_op3, - bitset_op4, + bitset_count_, + lbitset_empty_p, + lbitset_ones, + lbitset_zero, + lbitset_copy, + lbitset_disjoint_p, + lbitset_equal_p, + lbitset_not, + lbitset_subset_p, + (PFV) lbitset_and_cmp, + lbitset_and_cmp, + (PFV) lbitset_andn_cmp, + lbitset_andn_cmp, + (PFV) lbitset_or_cmp, + lbitset_or_cmp, + (PFV) lbitset_xor_cmp, + lbitset_xor_cmp, + (PFV) bitset_and_or_cmp_, + bitset_and_or_cmp_, + (PFV) bitset_andn_or_cmp_, + bitset_andn_or_cmp_, + (PFV) bitset_or_and_cmp_, + bitset_or_and_cmp_, lbitset_list, - lbitset_reverse_list, + lbitset_list_reverse, lbitset_free, BITSET_LIST }; @@ -1302,13 +1394,12 @@ lbitset_bytes (n_bits) /* Initialize a bitset. */ - bitset lbitset_init (bset, n_bits) bitset bset; bitset_bindex n_bits ATTRIBUTE_UNUSED; { - bset->b.ops = &lbitset_ops; + bset->b.vtable = &lbitset_vtable; return bset; } @@ -1323,3 +1414,34 @@ lbitset_release_memory () obstack_free (&lbitset_obstack, NULL); } } + + +/* Function to be called from debugger to debug lbitset. */ +void +debug_lbitset (bset) + bitset bset; +{ + lbitset_elt *elt; + unsigned int i; + + if (!bset) + return; + + for (elt = LBITSET_HEAD (bset); elt; elt = elt->next) + { + fprintf (stderr, "Elt %d\n", elt->index); + for (i = 0; i < LBITSET_ELT_WORDS; i++) + { + unsigned int j; + bitset_word word; + + word = elt->words[i]; + + fprintf (stderr, " Word %d:", i); + for (j = 0; j < LBITSET_WORD_BITS; j++) + if ((word & (1 << j))) + fprintf (stderr, " %d", j); + fprintf (stderr, "\n"); + } + } +}