- Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+
+ Copyright (C) 2002-2006, 2009-2013 Free Software Foundation, Inc.
+
(at your option) any later version.
This program is distributed in the hope that it will be useful,
(at your option) any later version.
This program is distributed in the hope that it will be useful,
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
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.
-*/
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include <stdlib.h>
#include <string.h>
/* This file implements variable size bitsets stored as a variable
length array of words. Any unused bits in the last word must be
#include <stdlib.h>
#include <string.h>
/* This file implements variable size bitsets stored as a variable
length array of words. Any unused bits in the last word must be
static void vbitset_set (bitset, bitset_bindex);
static void vbitset_reset (bitset, bitset_bindex);
static bool vbitset_test (bitset, bitset_bindex);
static void vbitset_set (bitset, bitset_bindex);
static void vbitset_reset (bitset, bitset_bindex);
static bool vbitset_test (bitset, bitset_bindex);
-static bitset_bindex vbitset_list (bitset, bitset_bindex *,
- bitset_bindex, bitset_bindex *);
+static bitset_bindex vbitset_list (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 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))
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
- /* The bitset needs to grow. If we already have enough memory
- allocated, then just zero what we need. */
+ /* The bitset needs to grow. If we already have enough memory
+ allocated, then just zero what we need. */
- {
- /* 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));
+ {
+ /* 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_WORDS (src)
- = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
- VBITSET_ASIZE (src) = newsize;
- }
+ {
+ VBITSET_WORDS (src)
+ = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
+ VBITSET_ASIZE (src) = newsize;
+ }
{
/* Many bitsets are zero, so make this common case fast. */
for (windex = 0; windex < size && !srcp[windex]; windex++)
{
/* Many bitsets are zero, so make this common case fast. */
for (windex = 0; windex < size && !srcp[windex]; windex++)
- {
- /* 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++;
- }
+ {
+ /* 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]))
bitoff = windex * BITSET_WORD_BITS;
}
for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
{
if (!(word = srcp[windex]))
memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
memset (dstp + sizeof (bitset_word) * ssize, 0,
memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
memset (dstp + sizeof (bitset_word) * ssize, 0,
vbitset_unused_clear (dst);
memset (dstp + sizeof (bitset_word) * ssize, 0,
vbitset_unused_clear (dst);
memset (dstp + sizeof (bitset_word) * ssize, 0,
bitset_word *dstp = VBITSET_WORDS (dst);
bitset_windex ssize = VBITSET_SIZE (src);
bitset_windex dsize = VBITSET_SIZE (dst);
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))
for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++)
if (*dstp != (*srcp | *dstp))
for (i = 0; i < min (ssize1, ssize2); i++)
*dstp++ = *src1p++ & *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++)
*dstp++ = *src1p++ & *src2p++;
memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2)));
}
memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2)));
}
for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
{
bitset_word tmp = *src1p++ & *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
{
bitset_word tmp = *src1p++ & *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++)
*dstp++ = *src1p++ & ~(*src2p++);
for (i = 0; i < min (ssize1, ssize2); i++)
*dstp++ = *src1p++ & ~(*src2p++);
for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
{
bitset_word tmp = *src1p++ & ~(*src2p++);
for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
{
bitset_word tmp = *src1p++ & ~(*src2p++);
memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
}
else
{
for (; i < ssize1; i++, dstp++)
memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
}
else
{
for (; i < ssize1; i++, dstp++)
for (i = 0; i < min (ssize1, ssize2); i++)
*dstp++ = *src1p++ | *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++)
*dstp++ = *src1p++ | *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
{
bitset_word tmp = *src1p++ | *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
{
bitset_word tmp = *src1p++ | *src2p++;
for (; i < ssize1; i++, dstp++)
{
bitset_word tmp = *src1p++;
for (; i < ssize1; i++, dstp++)
{
bitset_word tmp = *src1p++;
for (i = 0; i < min (ssize1, ssize2); i++)
*dstp++ = *src1p++ ^ *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++)
*dstp++ = *src1p++ ^ *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
{
bitset_word tmp = *src1p++ ^ *src2p++;
for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
{
bitset_word tmp = *src1p++ ^ *src2p++;
for (; i < ssize1; i++, dstp++)
{
bitset_word tmp = *src1p++;
for (; i < ssize1; i++, dstp++)
{
bitset_word tmp = *src1p++;
if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
|| BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
return bitset_and_or_cmp_ (dst, src1, src2, src3);
if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
|| BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
return bitset_and_or_cmp_ (dst, src1, src2, src3);
src3p = VBITSET_WORDS (src3);
dstp = VBITSET_WORDS (dst);
size = VBITSET_SIZE (dst);
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++;
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
|| BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
return bitset_andn_or_cmp_ (dst, src1, src2, src3);
if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
|| BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
return bitset_andn_or_cmp_ (dst, src1, src2, src3);
src3p = VBITSET_WORDS (src3);
dstp = VBITSET_WORDS (dst);
size = VBITSET_SIZE (dst);
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++;
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
src3p = VBITSET_WORDS (src3);
dstp = VBITSET_WORDS (dst);
size = VBITSET_SIZE (dst);
src3p = VBITSET_WORDS (src3);
dstp = VBITSET_WORDS (dst);
size = VBITSET_SIZE (dst);
if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
|| BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
return bitset_or_and_cmp_ (dst, src1, src2, src3);
if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
|| BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
return bitset_or_and_cmp_ (dst, src1, src2, src3);
src3p = VBITSET_WORDS (src3);
dstp = VBITSET_WORDS (dst);
size = VBITSET_SIZE (dst);
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++;
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;