+2002-03-04 Akim Demaille <akim@epita.fr>
+
+ * 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 <akim@epita.fr>
* src/closure.c (closure): `r' is unused.
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
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. */
#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)\
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. */
};
}
+/* 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)
}
-/* 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;
bitset tmp;
/* Create temporary bitset. */
- tmp = bitset_alloc (BITSET_TYPE_ (dst), 0);
+ tmp = bitset_alloc (0, BITSET_TYPE_ (dst));
switch (op)
{
#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));
/* 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));
/* 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. */
}
+/* 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
/* 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 */
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 <stdlib.h>
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;
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)
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));
}
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. */
}
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;
}
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;
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;
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;
}
}
}
}
- windex = EBITSET_ELT_WORDS;
+ woffset = EBITSET_ELT_WORDS;
}
- *next = n_bits - (bitoff + 1);
+ *next = n_bits - (boffset + 1);
return count;
}
bitset_bindex *next;
{
bitset_bindex bitno;
- bitset_windex index;
+ bitset_windex windex;
unsigned int eindex;
bitset_bindex count;
bitset_windex size;
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++)
{
}
word >>= 1;
}
- bitno = (index + 1) * BITSET_WORD_BITS;
+ bitno = (windex + 1) * BITSET_WORD_BITS;
}
}
for (; eindex < size; eindex++)
{
int i;
- ebitset_elt *elt;
bitset_word *srcp;
elt = elts[eindex];
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)
/* 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++)
{
for (j = 0; j < ssize; j++)
{
- ebitset_elt *selt;
- ebitset_elt *delt;
-
selt = j < ssize ? selts[j] : 0;
delt = j < dsize ? delts[j] : 0;
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;
}
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 ();
}
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 <stdlib.h>
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;
bitset bset;
lbitset_elt *elt;
{
- bitset_windex index = elt->index;
+ bitset_windex windex = elt->index;
lbitset_elt *ptr;
lbitset_elt *current;
/* 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)
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)
}
/* 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;
{
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
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;
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;
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));
}
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... */
}
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;
}
{
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;
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)
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;
}
}
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;
}
bitset_bindex *next;
{
bitset_bindex bitno;
- bitset_windex index;
+ bitset_windex windex;
bitset_bindex count;
lbitset_elt *elt;
lbitset_elt *head;
/* 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
{
/* 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++)
{
}
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;
}
}
}
word >>= 1;
}
}
- index++;
- bitno = index * BITSET_WORD_BITS;
+ windex++;
+ bitno = windex * BITSET_WORD_BITS;
word = srcp[1];
if (word)
word >>= 1;
}
}
- index++;
- bitno = index * BITSET_WORD_BITS;
+ windex++;
+ bitno = windex * BITSET_WORD_BITS;
#else
for (i = 0; i < LBITSET_ELT_WORDS; i++)
{
word >>= 1;
}
}
- index++;
- bitno = index * BITSET_WORD_BITS;
+ windex++;
+ bitno = windex * BITSET_WORD_BITS;
}
#endif
}
}
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;
}
}
enum bitset_ops op;
{
unsigned int i;
- bitset_windex index;
+ bitset_windex windex;
lbitset_elt *elt;
switch (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);
lbitset_elt *delt;
unsigned int i;
unsigned int j;
- bitset_windex index;
+ bitset_windex windex;
switch (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. */
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++)
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;
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;
}
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);
}
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"
bitset_bindex bitno;
bitset_bindex rbitno;
bitset_bindex count;
- bitset_windex index;
+ bitset_windex windex;
unsigned int bitcnt;
bitset_bindex bitoff;
bitset_word word;
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)
{
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);
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)
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)
}
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)
}
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 ();
}
projects / bison.git / commitdiff
