From: Paul Eggert Date: Mon, 2 Jun 2003 11:54:30 +0000 (+0000) Subject: Initial revision X-Git-Tag: BISON-2_0~284 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/cea532473773fd64de45002a03a507c794e5b1e1 Initial revision --- diff --git a/lib/vbitset.c b/lib/vbitset.c new file mode 100644 index 00000000..8e402408 --- /dev/null +++ b/lib/vbitset.c @@ -0,0 +1,1207 @@ +/* Variable array bitsets. + Copyright (C) 2002, 2003 Free Software Foundation, Inc. + Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + 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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include "vbitset.h" +#include +#include + +/* This file implements variable size bitsets stored as a variable + length array of words. Any unused bits in the last word must be + zero. + + Note that binary or ternary operations assume that each bitset operand + has the same size. +*/ + +static void vbitset_unused_clear PARAMS ((bitset)); + +static void vbitset_set PARAMS ((bitset, bitset_bindex)); +static void vbitset_reset PARAMS ((bitset, bitset_bindex)); +static bool vbitset_test PARAMS ((bitset, bitset_bindex)); +static bitset_bindex vbitset_list PARAMS ((bitset, bitset_bindex *, + bitset_bindex, + bitset_bindex *)); +static bitset_bindex vbitset_list_reverse PARAMS ((bitset, bitset_bindex *, + bitset_bindex, + bitset_bindex *)); + +#define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) +#define VBITSET_WORDS(X) ((X)->b.cdata) +#define VBITSET_SIZE(X) ((X)->b.csize) +#define VBITSET_ASIZE(X) ((X)->v.size) + + +#define min(a, b) ((a) > (b) ? (b) : (a)) +#define max(a, b) ((a) > (b) ? (a) : (b)) + +static bitset_bindex +vbitset_resize (src, n_bits) + bitset src; + bitset_bindex n_bits; +{ + bitset_windex oldsize; + bitset_windex newsize; + + if (n_bits == BITSET_NBITS_ (src)) + return n_bits; + + oldsize = VBITSET_SIZE (src); + newsize = VBITSET_N_WORDS (n_bits); + + if (oldsize < newsize) + { + bitset_windex size; + + /* The bitset needs to grow. If we already have enough memory + allocated, then just zero what we need. */ + if (newsize > VBITSET_ASIZE (src)) + { + /* We need to allocate more memory. When oldsize is + non-zero this means that we are changing the size, so + grow the bitset 25% larger than requested to reduce + number of reallocations. */ + + if (oldsize == 0) + size = newsize; + else + size = newsize + newsize / 4; + + VBITSET_WORDS (src) + = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word)); + VBITSET_ASIZE (src) = size; + } + + memset (VBITSET_WORDS (src) + oldsize, 0, + (newsize - oldsize) * sizeof (bitset_word)); + VBITSET_SIZE (src) = newsize; + } + else + { + /* The bitset needs to shrink. There's no point deallocating + the memory unless it is shrinking by a reasonable amount. */ + if ((oldsize - newsize) >= oldsize / 2) + { + VBITSET_WORDS (src) + = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word)); + VBITSET_ASIZE (src) = newsize; + } + + /* Need to prune any excess bits. FIXME. */ + + VBITSET_SIZE (src) = newsize; + } + + BITSET_NBITS_ (src) = n_bits; + return n_bits; +} + + +/* Set bit BITNO in bitset DST. */ +static void +vbitset_set (dst, bitno) + bitset dst; + bitset_bindex bitno; +{ + bitset_windex windex = bitno / BITSET_WORD_BITS; + + /* Perhaps we should abort. The user should explicitly call + bitset_resize since this will not catch the case when we set a + bit larger than the current size but smaller than the allocated + size. */ + vbitset_resize (dst, bitno); + + dst->b.cdata[windex - dst->b.cindex] |= + (bitset_word) 1 << (bitno % BITSET_WORD_BITS); +} + + +/* Reset bit BITNO in bitset DST. */ +static void +vbitset_reset (dst, bitno) + bitset dst ATTRIBUTE_UNUSED; + bitset_bindex bitno ATTRIBUTE_UNUSED; +{ + /* We must be accessing outside the cache so the bit is + zero anyway. */ +} + + +/* Test bit BITNO in bitset SRC. */ +static bool +vbitset_test (src, bitno) + bitset src ATTRIBUTE_UNUSED; + bitset_bindex bitno ATTRIBUTE_UNUSED; +{ + /* We must be accessing outside the cache so the bit is + zero anyway. */ + return 0; +} + + +/* Find list of up to NUM bits set in BSET in reverse order, starting + from and including NEXT and store in array LIST. Return with + actual number of bits found and with *NEXT indicating where search + stopped. */ +static bitset_bindex +vbitset_list_reverse (src, list, num, next) + bitset src; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_bindex rbitno; + bitset_bindex count; + bitset_windex windex; + unsigned int bitcnt; + bitset_bindex bitoff; + bitset_word *srcp = VBITSET_WORDS (src); + bitset_bindex n_bits = BITSET_SIZE_ (src); + + rbitno = *next; + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + if (rbitno >= n_bits) + return 0; + + count = 0; + + bitno = n_bits - (rbitno + 1); + + windex = bitno / BITSET_WORD_BITS; + bitcnt = bitno % BITSET_WORD_BITS; + bitoff = windex * BITSET_WORD_BITS; + + do + { + bitset_word word; + + word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); + for (; word; bitcnt--) + { + if (word & BITSET_MSB) + { + list[count++] = bitoff + bitcnt; + if (count >= num) + { + *next = n_bits - (bitoff + bitcnt); + return count; + } + } + word <<= 1; + } + bitoff -= BITSET_WORD_BITS; + bitcnt = BITSET_WORD_BITS - 1; + } + while (windex--); + + *next = n_bits - (bitoff + 1); + return count; +} + + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ +static bitset_bindex +vbitset_list (src, list, num, next) + bitset src; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_bindex count; + bitset_windex windex; + bitset_bindex bitoff; + bitset_windex size = VBITSET_SIZE (src); + bitset_word *srcp = VBITSET_WORDS (src); + bitset_word word; + + bitno = *next; + + count = 0; + if (!bitno) + { + /* Many bitsets are zero, so make this common case fast. */ + for (windex = 0; windex < size && !srcp[windex]; windex++) + continue; + if (windex >= size) + return 0; + + /* If num is 1, we could speed things up with a binary search + of the current word. */ + + bitoff = windex * BITSET_WORD_BITS; + } + else + { + if (bitno >= BITSET_SIZE_ (src)) + return 0; + + windex = bitno / BITSET_WORD_BITS; + bitno = bitno % BITSET_WORD_BITS; + + if (bitno) + { + /* Handle the case where we start within a word. + Most often, this is executed with large bitsets + with many set bits where we filled the array + on the previous call to this function. */ + + bitoff = windex * BITSET_WORD_BITS; + word = srcp[windex] >> bitno; + for (bitno = bitoff + bitno; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + windex++; + } + bitoff = windex * BITSET_WORD_BITS; + } + + for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) + { + if (!(word = srcp[windex])) + continue; + + if ((count + BITSET_WORD_BITS) < num) + { + for (bitno = bitoff; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } + else + { + for (bitno = bitoff; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + } + } + + *next = bitoff; + return count; +} + + +/* Ensure that any unused bits within the last word are clear. */ +static inline void +vbitset_unused_clear (dst) + bitset dst; +{ + unsigned int last_bit; + + last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS; + if (last_bit) + VBITSET_WORDS (dst)[VBITSET_SIZE (dst) - 1] &= + ((bitset_word) 1 << last_bit) - 1; +} + + +static void +vbitset_ones (dst) + bitset dst; +{ + bitset_word *dstp = VBITSET_WORDS (dst); + unsigned int bytes; + + bytes = sizeof (bitset_word) * VBITSET_SIZE (dst); + + memset (dstp, -1, bytes); + vbitset_unused_clear (dst); +} + + +static void +vbitset_zero (dst) + bitset dst; +{ + bitset_word *dstp = VBITSET_WORDS (dst); + unsigned int bytes; + + bytes = sizeof (bitset_word) * VBITSET_SIZE (dst); + + memset (dstp, 0, bytes); +} + + +static bool +vbitset_empty_p (dst) + bitset dst; +{ + unsigned int i; + bitset_word *dstp = VBITSET_WORDS (dst); + + for (i = 0; i < VBITSET_SIZE (dst); i++) + if (dstp[i]) + return 0; + + return 1; +} + + +static void +vbitset_copy1 (dst, src) + bitset dst; + bitset src; +{ + bitset_word *srcp; + bitset_word *dstp; + bitset_windex ssize; + bitset_windex dsize; + + if (src == dst) + return; + + vbitset_resize (dst, BITSET_SIZE_ (src)); + + srcp = VBITSET_WORDS (src); + dstp = VBITSET_WORDS (dst); + ssize = VBITSET_SIZE (src); + dsize = VBITSET_SIZE (dst); + + memcpy (dstp, srcp, sizeof (bitset_word) * ssize); + + memset (dstp + sizeof (bitset_word) * ssize, 0, + sizeof (bitset_word) * (dsize - ssize)); +} + + +static void +vbitset_not (dst, src) + bitset dst; + bitset src; +{ + unsigned int i; + bitset_word *srcp; + bitset_word *dstp; + bitset_windex ssize; + bitset_windex dsize; + + vbitset_resize (dst, BITSET_SIZE_ (src)); + + srcp = VBITSET_WORDS (src); + dstp = VBITSET_WORDS (dst); + ssize = VBITSET_SIZE (src); + dsize = VBITSET_SIZE (dst); + + for (i = 0; i < ssize; i++) + *dstp++ = ~(*srcp++); + + vbitset_unused_clear (dst); + memset (dstp + sizeof (bitset_word) * ssize, 0, + sizeof (bitset_word) * (dsize - ssize)); +} + + +static bool +vbitset_equal_p (dst, src) + bitset dst; + bitset src; +{ + unsigned int i; + bitset_word *srcp = VBITSET_WORDS (src); + bitset_word *dstp = VBITSET_WORDS (dst); + bitset_windex ssize = VBITSET_SIZE (src); + bitset_windex dsize = VBITSET_SIZE (dst); + + for (i = 0; i < min (ssize, dsize); i++) + if (*srcp++ != *dstp++) + return 0; + + if (ssize > dsize) + { + for (; i < ssize; i++) + if (*srcp++) + return 0; + } + else + { + for (; i < dsize; i++) + if (*dstp++) + return 0; + } + + return 1; +} + + +static bool +vbitset_subset_p (dst, src) + bitset dst; + bitset src; +{ + unsigned int i; + bitset_word *srcp = VBITSET_WORDS (src); + bitset_word *dstp = VBITSET_WORDS (dst); + bitset_windex ssize = VBITSET_SIZE (src); + bitset_windex dsize = VBITSET_SIZE (dst); + + for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++) + if (*dstp != (*srcp | *dstp)) + return 0; + + if (ssize > dsize) + { + for (; i < ssize; i++) + if (*srcp++) + return 0; + } + + return 1; +} + + +static bool +vbitset_disjoint_p (dst, src) + bitset dst; + bitset src; +{ + unsigned int i; + bitset_word *srcp = VBITSET_WORDS (src); + bitset_word *dstp = VBITSET_WORDS (dst); + bitset_windex ssize = VBITSET_SIZE (src); + bitset_windex dsize = VBITSET_SIZE (dst); + + for (i = 0; i < min (ssize, dsize); i++) + if (*srcp++ & *dstp++) + return 0; + + return 1; +} + + +static void +vbitset_and (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *dstp; + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + + vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); + + dsize = VBITSET_SIZE (dst); + ssize1 = VBITSET_SIZE (src1); + ssize2 = VBITSET_SIZE (src2); + dstp = VBITSET_WORDS (dst); + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + + for (i = 0; i < min (ssize1, ssize2); i++) + *dstp++ = *src1p++ & *src2p++; + + memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2))); +} + + +static bool +vbitset_and_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *dstp; + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + + vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); + + dsize = VBITSET_SIZE (dst); + ssize1 = VBITSET_SIZE (src1); + ssize2 = VBITSET_SIZE (src2); + dstp = VBITSET_WORDS (dst); + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + + for (i = 0; i < min (ssize1, ssize2); i++, dstp++) + { + bitset_word tmp = *src1p++ & *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + + if (ssize2 > ssize1) + { + src1p = src2p; + ssize1 = ssize2; + } + + for (; i < ssize1; i++, dstp++) + { + if (*dstp != 0) + { + changed = 1; + *dstp = 0; + } + } + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); + + return changed; +} + + +static void +vbitset_andn (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *dstp; + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + + vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); + + dsize = VBITSET_SIZE (dst); + ssize1 = VBITSET_SIZE (src1); + ssize2 = VBITSET_SIZE (src2); + dstp = VBITSET_WORDS (dst); + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + + for (i = 0; i < min (ssize1, ssize2); i++) + *dstp++ = *src1p++ & ~(*src2p++); + + if (ssize2 > ssize1) + { + for (; i < ssize2; i++) + *dstp++ = 0; + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2)); + } + else + { + for (; i < ssize1; i++) + *dstp++ = *src1p++; + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); + } +} + + +static bool +vbitset_andn_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *dstp; + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + + vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); + + dsize = VBITSET_SIZE (dst); + ssize1 = VBITSET_SIZE (src1); + ssize2 = VBITSET_SIZE (src2); + dstp = VBITSET_WORDS (dst); + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + + for (i = 0; i < min (ssize1, ssize2); i++, dstp++) + { + bitset_word tmp = *src1p++ & ~(*src2p++); + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + + if (ssize2 > ssize1) + { + for (; i < ssize2; i++, dstp++) + { + if (*dstp != 0) + { + changed = 1; + *dstp = 0; + } + } + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2)); + } + else + { + for (; i < ssize1; i++, dstp++) + { + bitset_word tmp = *src1p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); + } + + return changed; +} + + +static void +vbitset_or (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *dstp; + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + + vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); + + dsize = VBITSET_SIZE (dst); + ssize1 = VBITSET_SIZE (src1); + ssize2 = VBITSET_SIZE (src2); + dstp = VBITSET_WORDS (dst); + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + + for (i = 0; i < min (ssize1, ssize2); i++) + *dstp++ = *src1p++ | *src2p++; + + if (ssize2 > ssize1) + { + src1p = src2p; + ssize1 = ssize2; + } + + for (; i < ssize1; i++) + *dstp++ = *src1p++; + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); +} + + +static bool +vbitset_or_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *dstp; + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + + vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); + + dsize = VBITSET_SIZE (dst); + ssize1 = VBITSET_SIZE (src1); + ssize2 = VBITSET_SIZE (src2); + dstp = VBITSET_WORDS (dst); + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + + for (i = 0; i < min (ssize1, ssize2); i++, dstp++) + { + bitset_word tmp = *src1p++ | *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + + if (ssize2 > ssize1) + { + src1p = src2p; + ssize1 = ssize2; + } + + for (; i < ssize1; i++, dstp++) + { + bitset_word tmp = *src1p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); + + return changed; +} + + +static void +vbitset_xor (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *dstp; + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + + vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); + + dsize = VBITSET_SIZE (dst); + ssize1 = VBITSET_SIZE (src1); + ssize2 = VBITSET_SIZE (src2); + dstp = VBITSET_WORDS (dst); + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + + for (i = 0; i < min (ssize1, ssize2); i++) + *dstp++ = *src1p++ ^ *src2p++; + + if (ssize2 > ssize1) + { + src1p = src2p; + ssize1 = ssize2; + } + + for (; i < ssize1; i++) + *dstp++ = *src1p++; + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); +} + + +static bool +vbitset_xor_cmp (dst, src1, src2) + bitset dst; + bitset src1; + bitset src2; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *dstp; + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + + vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); + + dsize = VBITSET_SIZE (dst); + ssize1 = VBITSET_SIZE (src1); + ssize2 = VBITSET_SIZE (src2); + dstp = VBITSET_WORDS (dst); + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + + for (i = 0; i < min (ssize1, ssize2); i++, dstp++) + { + bitset_word tmp = *src1p++ ^ *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + + if (ssize2 > ssize1) + { + src1p = src2p; + ssize1 = ssize2; + } + + for (; i < ssize1; i++, dstp++) + { + bitset_word tmp = *src1p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + + memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); + + return changed; +} + + +/* FIXME, these operations need fixing for different size + bitsets. */ + +static void +vbitset_and_or (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *src3p; + bitset_word *dstp; + bitset_windex size; + + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) + || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) + { + bitset_and_or_ (dst, src1, src2, src3); + return; + } + + vbitset_resize (dst, BITSET_NBITS_ (src1)); + + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + src3p = VBITSET_WORDS (src3); + dstp = VBITSET_WORDS (dst); + size = VBITSET_SIZE (dst); + + for (i = 0; i < size; i++) + *dstp++ = (*src1p++ & *src2p++) | *src3p++; +} + + +static bool +vbitset_and_or_cmp (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *src3p; + bitset_word *dstp; + bitset_windex size; + + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) + || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) + return bitset_and_or_cmp_ (dst, src1, src2, src3); + + vbitset_resize (dst, BITSET_NBITS_ (src1)); + + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + src3p = VBITSET_WORDS (src3); + dstp = VBITSET_WORDS (dst); + size = VBITSET_SIZE (dst); + + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + return changed; +} + + +static void +vbitset_andn_or (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *src3p; + bitset_word *dstp; + bitset_windex size; + + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) + || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) + { + bitset_andn_or_ (dst, src1, src2, src3); + return; + } + + vbitset_resize (dst, BITSET_NBITS_ (src1)); + + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + src3p = VBITSET_WORDS (src3); + dstp = VBITSET_WORDS (dst); + size = VBITSET_SIZE (dst); + + for (i = 0; i < size; i++) + *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++; +} + + +static bool +vbitset_andn_or_cmp (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *src3p; + bitset_word *dstp; + bitset_windex size; + + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) + || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) + return bitset_andn_or_cmp_ (dst, src1, src2, src3); + + vbitset_resize (dst, BITSET_NBITS_ (src1)); + + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + src3p = VBITSET_WORDS (src3); + dstp = VBITSET_WORDS (dst); + size = VBITSET_SIZE (dst); + + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + return changed; +} + + +static void +vbitset_or_and (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *src3p; + bitset_word *dstp; + bitset_windex size; + + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) + || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) + { + bitset_or_and_ (dst, src1, src2, src3); + return; + } + + vbitset_resize (dst, BITSET_NBITS_ (src1)); + + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + src3p = VBITSET_WORDS (src3); + dstp = VBITSET_WORDS (dst); + size = VBITSET_SIZE (dst); + + for (i = 0; i < size; i++) + *dstp++ = (*src1p++ | *src2p++) & *src3p++; +} + + +static bool +vbitset_or_and_cmp (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p; + bitset_word *src2p; + bitset_word *src3p; + bitset_word *dstp; + bitset_windex size; + + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) + || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) + return bitset_or_and_cmp_ (dst, src1, src2, src3); + + vbitset_resize (dst, BITSET_NBITS_ (src1)); + + src1p = VBITSET_WORDS (src1); + src2p = VBITSET_WORDS (src2); + src3p = VBITSET_WORDS (src3); + dstp = VBITSET_WORDS (dst); + size = VBITSET_SIZE (dst); + + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + return changed; +} + + +void +vbitset_copy (dst, src) + bitset dst; + bitset src; +{ + if (BITSET_COMPATIBLE_ (dst, src)) + vbitset_copy1 (dst, src); + else + bitset_copy_ (dst, src); +} + + +/* Vector of operations for multiple word bitsets. */ +struct bitset_vtable vbitset_vtable = { + vbitset_set, + vbitset_reset, + bitset_toggle_, + vbitset_test, + vbitset_resize, + bitset_size_, + bitset_count_, + vbitset_empty_p, + vbitset_ones, + vbitset_zero, + vbitset_copy, + vbitset_disjoint_p, + vbitset_equal_p, + vbitset_not, + vbitset_subset_p, + vbitset_and, + vbitset_and_cmp, + vbitset_andn, + vbitset_andn_cmp, + vbitset_or, + vbitset_or_cmp, + vbitset_xor, + vbitset_xor_cmp, + vbitset_and_or, + vbitset_and_or_cmp, + vbitset_andn_or, + vbitset_andn_or_cmp, + vbitset_or_and, + vbitset_or_and_cmp, + vbitset_list, + vbitset_list_reverse, + NULL, + BITSET_VARRAY +}; + + +size_t +vbitset_bytes (n_bits) + bitset_bindex n_bits ATTRIBUTE_UNUSED; +{ + return sizeof (struct vbitset_struct); +} + + +bitset +vbitset_init (bset, n_bits) + bitset bset; + bitset_bindex n_bits; +{ + bset->b.vtable = &vbitset_vtable; + + bset->b.cindex = 0; + + VBITSET_SIZE (bset) = 0; + vbitset_resize (bset, n_bits); + return bset; +}