From 345cea780a4d3d11673c176cde39e20a043a1dea Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Mon, 4 Mar 2002 14:15:01 +0000 Subject: [PATCH] * lib/bbitset.h, lib/bitset.c, lib/bitset.h, lib/bitsetv.c, * lib/bitsetv.h, lib/ebitset.c, lib/lbitset.c, lib/sbitset.c: Update. From Michael Hayes. --- ChangeLog | 7 ++ THANKS | 1 + lib/bbitset.h | 12 +-- lib/bitset.c | 50 +++++++++---- lib/bitset.h | 9 ++- lib/bitsetv.c | 31 ++++++++ lib/bitsetv.h | 14 ++++ lib/ebitset.c | 119 ++++++++++++------------------ lib/lbitset.c | 197 ++++++++++++++++++++++++-------------------------- lib/sbitset.c | 49 +++++-------- 10 files changed, 261 insertions(+), 228 deletions(-) diff --git a/ChangeLog b/ChangeLog index 67f6f91f..b2efa038 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2002-03-04 Akim Demaille + + * lib/bbitset.h, lib/bitset.c, lib/bitset.h, lib/bitsetv.c, + * lib/bitsetv.h, lib/ebitset.c, lib/lbitset.c, lib/sbitset.c: + Update. + From Michael Hayes. + 2002-03-04 Akim Demaille * src/closure.c (closure): `r' is unused. diff --git a/THANKS b/THANKS index 9186c0ff..efb67667 100644 --- a/THANKS +++ b/THANKS @@ -26,6 +26,7 @@ Kees Zeelenberg kzlg@users.sourceforge.net Keith Browne kbrowne@legato.com Laurent Mascherpa laurent.mascherpa@epita.fr Marc Autret autret_m@epita.fr +Michael Hayes m.hayes@elec.canterbury.ac.nz Mike Castle dalgoda@ix.netcom.com Neil Booth NeilB@earthling.net Nelson H. F. Beebe beebe@math.utah.edu diff --git a/lib/bbitset.h b/lib/bbitset.h index a20e285f..53b56c02 100644 --- a/lib/bbitset.h +++ b/lib/bbitset.h @@ -103,8 +103,7 @@ enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES, BITSET_OP_COPY, BITSET_OP_NOT, BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P, BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P, - BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, - BITSET_OP_ANDN, BITSET_OP_ORN, + BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN, BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR}; /* Return size in bits of bitset SRC. */ @@ -181,10 +180,6 @@ enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES, #define BITSET_ANDN_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ BITSET_OP_ANDN) -/* DST = SRC1 | ~SRC2. */ -#define BITSET_ORN_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ - BITSET_OP_ORN) - /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if DST != (SRC1 & SRC2) | SRC3. */ #define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3)\ @@ -219,6 +214,11 @@ struct bbitset_struct 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. */ }; diff --git a/lib/bitset.c b/lib/bitset.c index 23df1791..a8897fb7 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -345,6 +345,42 @@ bitset_last (src) } +/* Return non-zero if BITNO in SRC is the only set bit. */ +int +bitset_only_set_p (src, bitno) + bitset src; + bitset_bindex bitno; +{ + bitset_bindex val[2]; + bitset_bindex next = 0; + + if (bitset_list (src, val, 2, &next) != 1) + return 0; + return val[0] == 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) @@ -545,18 +581,6 @@ bitset_andn (dst, src1, src2) } -/* DST = SRC1 | ~SRC2. Return non-zero if DST != SRC1 | ~SRC2. */ -int -bitset_orn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - BITSET_CHECK3_ (dst, src1, src2); - return BITSET_ORN_ (dst, src1, src2); -} - - int bitset_op4 (dst, src1, src2, src3, op) bitset dst; @@ -569,7 +593,7 @@ bitset_op4 (dst, src1, src2, src3, op) bitset tmp; /* Create temporary bitset. */ - tmp = bitset_alloc (BITSET_TYPE_ (dst), 0); + tmp = bitset_alloc (0, BITSET_TYPE_ (dst)); switch (op) { diff --git a/lib/bitset.h b/lib/bitset.h index b96a7e67..62d4c651 100644 --- a/lib/bitset.h +++ b/lib/bitset.h @@ -179,6 +179,9 @@ do \ #define bitset_test(SRC, BITNO) BITSET_TEST_ (SRC, BITNO) #endif +/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */ +extern int bitset_toggle PARAMS ((bitset, bitset_bindex)); + /* DST = 0. */ extern int bitset_zero PARAMS ((bitset)); @@ -215,9 +218,6 @@ extern int bitset_xor PARAMS ((bitset, bitset, bitset)); /* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */ extern int bitset_andn PARAMS ((bitset, bitset, bitset)); -/* DST = SRC1 | ~SRC2. Return non-zero if DST != SRC1 | ~SRC2. */ -extern int bitset_orn PARAMS ((bitset, bitset, bitset)); - /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if DST != (SRC1 | SRC2) & SRC3. */ extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset)); @@ -236,6 +236,9 @@ extern int bitset_next PARAMS ((bitset, bitset_bindex)); /* Find previous bit set in BSET starting from and including BITNO. */ extern int bitset_prev PARAMS ((bitset, bitset_bindex)); +/* Return non-zero if BITNO in SRC is the only set bit. */ +extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex)); + /* 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. */ diff --git a/lib/bitsetv.c b/lib/bitsetv.c index b6eb77e8..be4bfa7d 100644 --- a/lib/bitsetv.c +++ b/lib/bitsetv.c @@ -111,6 +111,37 @@ bitsetv_ones (bsetv) } +/* Given a vector BSETV of N bitsets of size N, modify its contents to + be the transitive closure of what was given. */ +void +bitsetv_transitive_closure (bsetv) + bitset *bsetv; +{ + unsigned int i; + unsigned int j; + + for (i = 0; bsetv[i]; i++) + for (j = 0; bsetv[j]; j++) + if (bitset_test (bsetv[j], i)) + bitset_or (bsetv[j], bsetv[j], bsetv[i]); +} + + +/* Given a vector BSETV of N bitsets of size N, modify its contents to + be the reflexive transitive closure of what was given. This is + the same as transitive closure but with all bits on the diagonal + of the bit matrix set. */ +void +bitsetv_reflexive_transitive_closure (bitsetv bsetv) +{ + int i; + + bitsetv_transitive_closure (bsetv); + for (i = 0; bsetv[i]; i++) + bitset_set (bsetv[i], i); +} + + /* Dump the contents of a bitset vector BSETV with N_VECS elements to FILE. */ void diff --git a/lib/bitsetv.h b/lib/bitsetv.h index 34617054..84a2c667 100644 --- a/lib/bitsetv.h +++ b/lib/bitsetv.h @@ -42,7 +42,21 @@ extern void bitsetv_zero PARAMS ((bitsetv)); /* Set vector of bitsets. */ extern void bitsetv_ones PARAMS ((bitsetv)); +/* Given a vector BSETV of N bitsets of size N, modify its contents to + be the transitive closure of what was given. */ +extern void bitsetv_transitive_closure PARAMS ((bitsetv)); + +/* Given a vector BSETV of N bitsets of size N, modify its contents to + be the reflexive transitive closure of what was given. This is + the same as transitive closure but with all bits on the diagonal + of the bit matrix set. */ +extern void bitsetv_reflexive_transitive_closure PARAMS ((bitsetv)); + /* Dump vector of bitsets. */ extern void bitsetv_dump PARAMS ((FILE *, const char *, const char *, bitsetv)); + +/* Function to debug vector of bitsets from debugger. */ +extern void debug_bitsetv PARAMS ((bitsetv)); + #endif /* _BITSETV_H */ diff --git a/lib/ebitset.c b/lib/ebitset.c index 9b1d91bf..3e84efa8 100644 --- a/lib/ebitset.c +++ b/lib/ebitset.c @@ -14,13 +14,14 @@ You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +*/ #ifdef HAVE_CONFIG_H #include "config.h" #endif -#include "bbitset.h" +#include "ebitset.h" #include "obstack.h" #include @@ -311,9 +312,9 @@ ebitset_elt_zero_p (elt) static ebitset_elt * -ebitset_elt_find (bset, index, mode) +ebitset_elt_find (bset, windex, mode) bitset bset; - bitset_windex index; + bitset_windex windex; enum ebitset_find_mode mode; { ebitset_elt *elt; @@ -321,15 +322,13 @@ ebitset_elt_find (bset, index, mode) unsigned int eindex; ebitset_elts *elts; - eindex = index / EBITSET_ELT_WORDS; + eindex = windex / EBITSET_ELT_WORDS; elts = EBITSET_ELTS (bset); size = EBITSET_SIZE (bset); if (eindex < size) { - ebitset_elt *elt; - if ((elt = elts[eindex])) { if (EBITSET_WORDS (elt) == bset->b.cdata) @@ -581,11 +580,11 @@ ebitset_set (dst, bitno) bitset dst; bitset_bindex bitno; { - bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex windex = bitno / BITSET_WORD_BITS; - ebitset_elt_find (dst, index, EBITSET_CREATE); + ebitset_elt_find (dst, windex, EBITSET_CREATE); - dst->b.cdata[index - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[windex - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS)); } @@ -595,15 +594,15 @@ ebitset_reset (dst, bitno) bitset dst; bitset_bindex bitno; { - bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex windex = bitno / BITSET_WORD_BITS; - if (!ebitset_elt_find (dst, index, EBITSET_FIND)) + if (!ebitset_elt_find (dst, windex, EBITSET_FIND)) return; - dst->b.cdata[index - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[windex - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); /* If all the data is zero, perhaps we should remove it now... - However, there could be a good chance that the element will be needed + However, there is a good chance that the element will be needed again soon. */ } @@ -614,13 +613,13 @@ ebitset_test (src, bitno) bitset src; bitset_bindex bitno; { - bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex windex = bitno / BITSET_WORD_BITS; - if (!ebitset_elt_find (src, index, EBITSET_FIND)) + if (!ebitset_elt_find (src, windex, EBITSET_FIND)) return 0; return (src->b. - cdata[index - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1; + cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1; } @@ -646,11 +645,11 @@ ebitset_reverse_list (bset, list, num, next) bitset_bindex n_bits; bitset_bindex bitno; bitset_bindex rbitno; - unsigned int bitcnt; - bitset_bindex bitoff; - bitset_windex index; - unsigned int eindex; + unsigned int bcount; + bitset_bindex boffset; bitset_windex windex; + unsigned int eindex; + bitset_windex woffset; bitset_bindex count; bitset_windex size; bitset_word word; @@ -670,18 +669,19 @@ ebitset_reverse_list (bset, list, num, next) bitno = n_bits - (rbitno + 1); - index = bitno / BITSET_WORD_BITS; + windex = bitno / BITSET_WORD_BITS; eindex = bitno / EBITSET_ELT_BITS; - windex = index - eindex * EBITSET_ELT_WORDS; + woffset = windex - eindex * EBITSET_ELT_WORDS; /* If num is 1, we could speed things up with a binary search of the word of interest. */ count = 0; - bitcnt = bitno % BITSET_WORD_BITS; - bitoff = index * BITSET_WORD_BITS; + bcount = bitno % BITSET_WORD_BITS; + boffset = windex * BITSET_WORD_BITS; - for (; eindex != ~0U; eindex--) + for (; eindex != ~0U; + boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS, eindex--) { ebitset_elt *elt; bitset_word *srcp; @@ -692,19 +692,19 @@ ebitset_reverse_list (bset, list, num, next) srcp = EBITSET_WORDS (elt); - for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS, - bitcnt = BITSET_WORD_BITS - 1) + for (; woffset != ~0U; woffset--, boffset -= BITSET_WORD_BITS, + bcount = BITSET_WORD_BITS - 1) { - word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); + word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); - for (; word; bitcnt--) + for (; word; bcount--) { if (word & BITSET_MSB) { - list[count++] = bitoff + bitcnt; + list[count++] = boffset + bcount; if (count >= num) { - *next = n_bits - (bitoff + bitcnt); + *next = n_bits - (boffset + bcount); return count; } } @@ -712,10 +712,10 @@ ebitset_reverse_list (bset, list, num, next) } } - windex = EBITSET_ELT_WORDS; + woffset = EBITSET_ELT_WORDS; } - *next = n_bits - (bitoff + 1); + *next = n_bits - (boffset + 1); return count; } @@ -731,7 +731,7 @@ ebitset_list (bset, list, num, next) bitset_bindex *next; { bitset_bindex bitno; - bitset_windex index; + bitset_windex windex; unsigned int eindex; bitset_bindex count; bitset_windex size; @@ -756,15 +756,15 @@ ebitset_list (bset, list, num, next) elt = elts[eindex]; if (elt) { - bitset_windex windex; + bitset_windex woffset; bitset_word *srcp = EBITSET_WORDS (elt); - index = bitno / BITSET_WORD_BITS; - windex = eindex / EBITSET_ELT_WORDS; + windex = bitno / BITSET_WORD_BITS; + woffset = eindex / EBITSET_ELT_WORDS; - for (; (index - windex) < EBITSET_ELT_WORDS; index++) + for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++) { - word = srcp[index - windex] >> (bitno % BITSET_WORD_BITS); + word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS); for (; word; bitno++) { @@ -779,7 +779,7 @@ ebitset_list (bset, list, num, next) } word >>= 1; } - bitno = (index + 1) * BITSET_WORD_BITS; + bitno = (windex + 1) * BITSET_WORD_BITS; } } @@ -793,7 +793,6 @@ ebitset_list (bset, list, num, next) for (; eindex < size; eindex++) { int i; - ebitset_elt *elt; bitset_word *srcp; elt = elts[eindex]; @@ -801,15 +800,15 @@ ebitset_list (bset, list, num, next) continue; srcp = EBITSET_WORDS (elt); - index = eindex * EBITSET_ELT_WORDS; + windex = eindex * EBITSET_ELT_WORDS; if ((count + EBITSET_ELT_BITS) < num) { /* The coast is clear, plant boot! */ - for (i = 0; i < EBITSET_ELT_WORDS; i++, index++) + for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++) { - bitno = index * BITSET_WORD_BITS; + bitno = windex * BITSET_WORD_BITS; word = srcp[i]; if (word) @@ -838,9 +837,9 @@ ebitset_list (bset, list, num, next) /* Tread more carefully since we need to check if array overflows. */ - for (i = 0; i < EBITSET_ELT_WORDS; i++, index++) + for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++) { - bitno = index * BITSET_WORD_BITS; + bitno = windex * BITSET_WORD_BITS; for (word = srcp[i]; word; bitno++) { @@ -953,9 +952,6 @@ ebitset_op2 (dst, src, op) for (j = 0; j < ssize; j++) { - ebitset_elt *selt; - ebitset_elt *delt; - selt = j < ssize ? selts[j] : 0; delt = j < dsize ? delts[j] : 0; @@ -992,20 +988,12 @@ ebitset_op2 (dst, src, op) for (j = 0; j < ssize; j++) { - ebitset_elt *selt; - ebitset_elt *delt; - selt = j < ssize ? selts[j] : 0; delt = j < dsize ? delts[j] : 0; - if (!selt && !delt) + 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 (selt)[i] & EBITSET_WORDS (delt)[i])) return 0; @@ -1175,19 +1163,6 @@ ebitset_op3 (dst, src1, src2, op) } break; - case BITSET_OP_ORN: - for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) - { - bitset_word tmp = *srcp1++ | ~(*srcp2++); - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - default: abort (); } diff --git a/lib/lbitset.c b/lib/lbitset.c index 39e5b4e5..f426c301 100644 --- a/lib/lbitset.c +++ b/lib/lbitset.c @@ -14,13 +14,14 @@ You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +*/ #ifdef HAVE_CONFIG_H #include "config.h" #endif -#include "bbitset.h" +#include "lbitset.h" #include "obstack.h" #include @@ -82,7 +83,7 @@ struct bitset_struct enum lbitset_find_mode { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST }; -static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */ +static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */ /* Obstack to allocate bitset elements from. */ static struct obstack lbitset_obstack; @@ -306,7 +307,7 @@ lbitset_elt_link (bset, elt) bitset bset; lbitset_elt *elt; { - bitset_windex index = elt->index; + bitset_windex windex = elt->index; lbitset_elt *ptr; lbitset_elt *current; @@ -325,10 +326,10 @@ lbitset_elt_link (bset, elt) /* If this index is less than that of the current element, it goes somewhere before the current element. */ - else if (index < bset->b.cindex) + else if (windex < bset->b.cindex) { for (ptr = current; - ptr->prev && ptr->prev->index > index; ptr = ptr->prev) + ptr->prev && ptr->prev->index > windex; ptr = ptr->prev) continue; if (ptr->prev) @@ -345,7 +346,7 @@ lbitset_elt_link (bset, elt) else { for (ptr = current; - ptr->next && ptr->next->index < index; ptr = ptr->next) + ptr->next && ptr->next->index < windex; ptr = ptr->next) continue; if (ptr->next) @@ -359,16 +360,16 @@ lbitset_elt_link (bset, elt) } /* Set up so this is the first element searched. */ - bset->b.cindex = index; + bset->b.cindex = windex; bset->b.csize = LBITSET_ELT_WORDS; bset->b.cdata = elt->words; } static lbitset_elt * -lbitset_elt_find (bset, index, mode) +lbitset_elt_find (bset, windex, mode) bitset bset; - bitset_windex index; + bitset_windex windex; enum lbitset_find_mode mode; { lbitset_elt *elt; @@ -378,7 +379,7 @@ lbitset_elt_find (bset, index, mode) { current = LBITSET_CURRENT (bset); /* Check if element is the cached element. */ - if ((index - bset->b.cindex) < bset->b.csize) + if ((windex - bset->b.cindex) < bset->b.csize) return current; } else @@ -388,23 +389,23 @@ lbitset_elt_find (bset, index, mode) if (current) { - if (index < bset->b.cindex) + if (windex < bset->b.cindex) { for (elt = current; - elt->prev && elt->index > index; elt = elt->prev) + elt->prev && elt->index > windex; elt = elt->prev) continue; } else { for (elt = current; - elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < index; + elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex; elt = elt->next) continue; } /* `element' 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 && (index - elt->index) < LBITSET_ELT_WORDS) + if (elt && (windex - elt->index) < LBITSET_ELT_WORDS) { bset->b.cindex = elt->index; bset->b.csize = LBITSET_ELT_WORDS; @@ -419,10 +420,10 @@ lbitset_elt_find (bset, index, mode) return 0; case LBITSET_CREATE: - index = (index / (unsigned) LBITSET_ELT_WORDS) * LBITSET_ELT_WORDS; + windex = (windex / (unsigned) LBITSET_ELT_WORDS) * LBITSET_ELT_WORDS; elt = lbitset_elt_calloc (); - elt->index = index; + elt->index = windex; lbitset_elt_link (bset, elt); return elt; @@ -585,11 +586,11 @@ lbitset_set (dst, bitno) bitset dst; bitset_bindex bitno; { - bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex windex = bitno / BITSET_WORD_BITS; - lbitset_elt_find (dst, index, LBITSET_CREATE); + lbitset_elt_find (dst, windex, LBITSET_CREATE); - dst->b.cdata[index - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[windex - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS)); } @@ -599,12 +600,12 @@ lbitset_reset (dst, bitno) bitset dst; bitset_bindex bitno; { - bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex windex = bitno / BITSET_WORD_BITS; - if (!lbitset_elt_find (dst, index, LBITSET_FIND)) + if (!lbitset_elt_find (dst, windex, LBITSET_FIND)) return; - dst->b.cdata[index - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[windex - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); /* If all the data is zero, perhaps we should unlink it now... */ } @@ -616,13 +617,13 @@ lbitset_test (src, bitno) bitset src; bitset_bindex bitno; { - bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex windex = bitno / BITSET_WORD_BITS; - if (!lbitset_elt_find (src, index, LBITSET_FIND)) + if (!lbitset_elt_find (src, windex, LBITSET_FIND)) return 0; - return (src->b. - cdata[index - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1; + return (src->b.cdata[windex - src->b.cindex] + >> (bitno % BITSET_WORD_BITS)) & 1; } @@ -646,9 +647,9 @@ lbitset_reverse_list (bset, list, num, next) { bitset_bindex rbitno; bitset_bindex bitno; - unsigned int bitcnt; - bitset_bindex bitoff; - bitset_windex index; + unsigned int bcount; + bitset_bindex boffset; + bitset_windex windex; bitset_bindex count; lbitset_elt *elt; bitset_word word; @@ -666,10 +667,10 @@ lbitset_reverse_list (bset, list, num, next) bitno = n_bits - (rbitno + 1); - index = bitno / BITSET_WORD_BITS; + windex = bitno / BITSET_WORD_BITS; /* Skip back to starting element. */ - for (; elt && elt->index > index; elt = elt->prev) + for (; elt && elt->index > windex; elt = elt->prev) continue; if (!elt) @@ -679,28 +680,28 @@ lbitset_reverse_list (bset, list, num, next) of the word of interest. */ count = 0; - bitcnt = bitno % BITSET_WORD_BITS; - bitoff = index * BITSET_WORD_BITS; + bcount = bitno % BITSET_WORD_BITS; + boffset = windex * BITSET_WORD_BITS; while (elt) { bitset_word *srcp = elt->words; - for (; (index - elt->index) < LBITSET_ELT_WORDS; - index--, bitoff -= BITSET_WORD_BITS, - bitcnt = BITSET_WORD_BITS - 1) + for (; (windex - elt->index) < LBITSET_ELT_WORDS; + windex--, boffset -= BITSET_WORD_BITS, + bcount = BITSET_WORD_BITS - 1) { word = - srcp[index - elt->index] << (BITSET_WORD_BITS - 1 - bitcnt); + srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount); - for (; word; bitcnt--) + for (; word; bcount--) { if (word & BITSET_MSB) { - list[count++] = bitoff + bitcnt; + list[count++] = boffset + bcount; if (count >= num) { - *next = n_bits - (bitoff + bitcnt); + *next = n_bits - (boffset + bcount); return count; } } @@ -711,12 +712,12 @@ lbitset_reverse_list (bset, list, num, next) elt = elt->prev; if (elt) { - index = elt->index + LBITSET_ELT_WORDS - 1; - bitoff = index * BITSET_WORD_BITS; + windex = elt->index + LBITSET_ELT_WORDS - 1; + boffset = windex * BITSET_WORD_BITS; } } - *next = n_bits - (bitoff + 1); + *next = n_bits - (boffset + 1); return count; } @@ -732,7 +733,7 @@ lbitset_list (bset, list, num, next) bitset_bindex *next; { bitset_bindex bitno; - bitset_windex index; + bitset_windex windex; bitset_bindex count; lbitset_elt *elt; lbitset_elt *head; @@ -751,26 +752,26 @@ lbitset_list (bset, list, num, next) /* Start with the first element. */ elt = head; - index = elt->index; - bitno = index * BITSET_WORD_BITS; + windex = elt->index; + bitno = windex * BITSET_WORD_BITS; } else { - index = bitno / BITSET_WORD_BITS; + windex = bitno / BITSET_WORD_BITS; /* Skip to starting element. */ for (elt = head; - elt && (elt->index + LBITSET_ELT_WORDS - 1) < index; + elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex; elt = elt->next) continue; if (!elt) return 0; - if (index < elt->index) + if (windex < elt->index) { - index = elt->index; - bitno = index * BITSET_WORD_BITS; + windex = elt->index; + bitno = windex * BITSET_WORD_BITS; } else { @@ -778,9 +779,9 @@ lbitset_list (bset, list, num, next) /* We are starting within an element. */ - for (; (index - elt->index) < LBITSET_ELT_WORDS; index++) + for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) { - word = srcp[index - elt->index] >> (bitno % BITSET_WORD_BITS); + word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS); for (; word; bitno++) { @@ -795,14 +796,14 @@ lbitset_list (bset, list, num, next) } word >>= 1; } - bitno = (index + 1) * BITSET_WORD_BITS; + bitno = (windex + 1) * BITSET_WORD_BITS; } elt = elt->next; if (elt) { - index = elt->index; - bitno = index * BITSET_WORD_BITS; + windex = elt->index; + bitno = windex * BITSET_WORD_BITS; } } } @@ -841,8 +842,8 @@ lbitset_list (bset, list, num, next) word >>= 1; } } - index++; - bitno = index * BITSET_WORD_BITS; + windex++; + bitno = windex * BITSET_WORD_BITS; word = srcp[1]; if (word) @@ -859,8 +860,8 @@ lbitset_list (bset, list, num, next) word >>= 1; } } - index++; - bitno = index * BITSET_WORD_BITS; + windex++; + bitno = windex * BITSET_WORD_BITS; #else for (i = 0; i < LBITSET_ELT_WORDS; i++) { @@ -884,8 +885,8 @@ lbitset_list (bset, list, num, next) word >>= 1; } } - index++; - bitno = index * BITSET_WORD_BITS; + windex++; + bitno = windex * BITSET_WORD_BITS; } #endif } @@ -909,16 +910,16 @@ lbitset_list (bset, list, num, next) } word >>= 1; } - index++; - bitno = index * BITSET_WORD_BITS; + windex++; + bitno = windex * BITSET_WORD_BITS; } } elt = elt->next; if (elt) { - index = elt->index; - bitno = index * BITSET_WORD_BITS; + windex = elt->index; + bitno = windex * BITSET_WORD_BITS; } } @@ -933,7 +934,7 @@ lbitset_op1 (dst, op) enum bitset_ops op; { unsigned int i; - bitset_windex index; + bitset_windex windex; lbitset_elt *elt; switch (op) @@ -950,8 +951,8 @@ lbitset_op1 (dst, op) if (!elt) return 0; - index = elt->index; - for (i = 0; i < index; i += LBITSET_ELT_WORDS) + 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); @@ -984,7 +985,7 @@ lbitset_op2 (dst, src, op) lbitset_elt *delt; unsigned int i; unsigned int j; - bitset_windex index; + bitset_windex windex; switch (op) { @@ -1000,8 +1001,8 @@ lbitset_op2 (dst, src, op) if (!elt) return 0; - index = elt->index; - for (i = 0; i < index; i += LBITSET_ELT_WORDS) + 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. */ @@ -1065,6 +1066,9 @@ lbitset_op2 (dst, src, op) lbitset_zero_elts[1].next = selt; selt = &lbitset_zero_elts[1]; } + /* Since the elements are different, there is no + intersection of these elements. */ + continue; } for (j = 0; j < LBITSET_ELT_WORDS; j++) @@ -1091,9 +1095,9 @@ lbitset_op3 (dst, src1, src2, op) lbitset_elt *selt1 = LBITSET_HEAD (src1); lbitset_elt *selt2 = LBITSET_HEAD (src2); lbitset_elt *delt = LBITSET_HEAD (dst); - bitset_windex index1; - bitset_windex index2; - bitset_windex index; + bitset_windex windex1; + bitset_windex windex2; + bitset_windex windex; lbitset_elt *stmp1; lbitset_elt *stmp2; lbitset_elt *dtmp; @@ -1137,50 +1141,50 @@ lbitset_op3 (dst, src1, src2, op) LBITSET_HEAD (dst) = 0; dst->b.csize = 0; - index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; - index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; + windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; while (selt1 || selt2) { /* Figure out whether we need to substitute zero elements for missing links. */ - if (index1 == index2) + if (windex1 == windex2) { - index = index1; + windex = windex1; stmp1 = selt1; stmp2 = selt2; selt1 = selt1->next; - index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; + windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; selt2 = selt2->next; - index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; } - else if (index1 < index2) + else if (windex1 < windex2) { - index = index1; + windex = windex1; stmp1 = selt1; stmp2 = &lbitset_zero_elts[0]; selt1 = selt1->next; - index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; + windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; } else { - index = index2; + windex = windex2; stmp1 = &lbitset_zero_elts[0]; stmp2 = selt2; selt2 = selt2->next; - index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; } /* Find the appropriate element from DST. Begin by discarding elements that we've skipped. */ - while (delt && delt->index < index) + while (delt && delt->index < windex) { changed = 1; dtmp = delt; delt = delt->next; lbitset_elt_free (dtmp); } - if (delt && delt->index == index) + if (delt && delt->index == windex) { dtmp = delt; delt = delt->next; @@ -1247,26 +1251,13 @@ lbitset_op3 (dst, src1, src2, op) } break; - case BITSET_OP_ORN: - for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) - { - bitset_word tmp = *srcp1++ | ~(*srcp2++); - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - default: abort (); } if (!lbitset_elt_zero_p (dtmp)) { - dtmp->index = index; + dtmp->index = windex; /* Perhaps this could be optimised... */ lbitset_elt_link (dst, dtmp); } diff --git a/lib/sbitset.c b/lib/sbitset.c index 2e42e9b0..97d13335 100644 --- a/lib/sbitset.c +++ b/lib/sbitset.c @@ -14,7 +14,8 @@ You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +*/ #ifdef HAVE_CONFIG_H #include "config.h" @@ -184,7 +185,7 @@ sbitset_reverse_list (src, list, num, next) bitset_bindex bitno; bitset_bindex rbitno; bitset_bindex count; - bitset_windex index; + bitset_windex windex; unsigned int bitcnt; bitset_bindex bitoff; bitset_word word; @@ -203,14 +204,14 @@ sbitset_reverse_list (src, list, num, next) bitno = n_bits - (rbitno + 1); - index = bitno / BITSET_WORD_BITS; + windex = bitno / BITSET_WORD_BITS; bitcnt = bitno % BITSET_WORD_BITS; - bitoff = index * BITSET_WORD_BITS; + bitoff = windex * BITSET_WORD_BITS; - for (; index != ~0U; index--, bitoff -= BITSET_WORD_BITS, + for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS, bitcnt = BITSET_WORD_BITS - 1) { - word = srcp[index] << (BITSET_WORD_BITS - 1 - bitcnt); + word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); for (; word; bitcnt--) { if (word & BITSET_MSB) @@ -243,7 +244,7 @@ sbitset_list (src, list, num, next) { bitset_bindex bitno; bitset_bindex count; - bitset_windex index; + bitset_windex windex; bitset_bindex bitoff; bitset_windex size = src->b.csize; bitset_word *srcp = SBITSET_WORDS (src); @@ -255,22 +256,22 @@ sbitset_list (src, list, num, next) if (!bitno) { /* Many bitsets are zero, so make this common case fast. */ - for (index = 0; index < size && !srcp[index]; index++) + for (windex = 0; windex < size && !srcp[windex]; windex++) continue; - if (index >= size) + if (windex >= size) return 0; /* If num is 1, we could speed things up with a binary search of the current word. */ - bitoff = index * BITSET_WORD_BITS; + bitoff = windex * BITSET_WORD_BITS; } else { if (bitno >= SBITSET_N_BITS (src)) return 0; - index = bitno / BITSET_WORD_BITS; + windex = bitno / BITSET_WORD_BITS; bitno = bitno % BITSET_WORD_BITS; if (bitno) @@ -280,8 +281,8 @@ sbitset_list (src, list, num, next) with many set bits where we filled the array on the previous call to this function. */ - bitoff = index * BITSET_WORD_BITS; - word = srcp[index] >> bitno; + bitoff = windex * BITSET_WORD_BITS; + word = srcp[windex] >> bitno; for (bitno = bitoff + bitno; word; bitno++) { if (word & 1) @@ -295,14 +296,14 @@ sbitset_list (src, list, num, next) } word >>= 1; } - index++; + windex++; } - bitoff = index * BITSET_WORD_BITS; + bitoff = windex * BITSET_WORD_BITS; } - for (; index < size; index++, bitoff += BITSET_WORD_BITS) + for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) { - if (!(word = srcp[index])) + if (!(word = srcp[windex])) continue; if ((count + BITSET_WORD_BITS) < num) @@ -519,20 +520,6 @@ sbitset_op3 (dst, src1, src2, op) } break; - case BITSET_OP_ORN: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = *src1p++ | ~(*src2p++); - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - sbitset_unused_clear (dst); - break; - default: abort (); } -- 2.45.2