/* Array bitsets.
- Copyright (C) 2002 Free Software Foundation, Inc.
+
+ Copyright (C) 2002-2003, 2006, 2009-2012 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
+ 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
+ the Free Software Foundation, either version 3 of the License, or
(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
- 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/>. */
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
+#include <config.h>
#include "abitset.h"
#include <stddef.h>
#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
#define ABITSET_WORDS(X) ((X)->a.words)
-#define ABITSET_N_BITS(X) ((X)->a.n_bits)
-/* Return size in bits of bitset SRC. */
static bitset_bindex
-abitset_size (bitset src)
+abitset_resize (bitset src, bitset_bindex size)
{
- return ABITSET_N_BITS (src);
-}
+ /* These bitsets have a fixed size. */
+ if (BITSET_SIZE_ (src) != size)
+ abort ();
+ return size;
+}
/* 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
abitset_small_list (bitset src, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
+ bitset_bindex num, bitset_bindex *next)
{
bitset_bindex bitno;
bitset_bindex count;
if (!word)
return 0;
- size = ABITSET_N_BITS (src);
+ size = BITSET_SIZE_ (src);
bitno = *next;
if (bitno >= size)
return 0;
if (num >= BITSET_WORD_BITS)
{
for (count = 0; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
+ {
+ if (word & 1)
+ list[count++] = bitno;
+ word >>= 1;
+ }
}
else
{
for (count = 0; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- bitno++;
- break;
- }
- }
- word >>= 1;
- }
+ {
+ if (word & 1)
+ {
+ list[count++] = bitno;
+ if (count >= num)
+ {
+ bitno++;
+ break;
+ }
+ }
+ word >>= 1;
+ }
}
*next = bitno;
static void
abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
{
- /* This should never occur for abitsets since we should always
- hit the cache. */
+ /* This should never occur for abitsets since we should always hit
+ the cache. It is likely someone is trying to access outside the
+ bounds of the bitset. */
abort ();
}
/* Reset bit BITNO in bitset DST. */
static void
abitset_reset (bitset dst ATTRIBUTE_UNUSED,
- bitset_bindex bitno ATTRIBUTE_UNUSED)
+ bitset_bindex bitno ATTRIBUTE_UNUSED)
{
- /* This should never occur for abitsets since we should always
- hit the cache. */
- abort ();
+ /* This should never occur for abitsets since we should always hit
+ the cache. It is likely someone is trying to access outside the
+ bounds of the bitset. Since the bit is zero anyway, let it pass. */
}
/* Test bit BITNO in bitset SRC. */
-static int
+static bool
abitset_test (bitset src ATTRIBUTE_UNUSED,
- bitset_bindex bitno ATTRIBUTE_UNUSED)
+ bitset_bindex bitno ATTRIBUTE_UNUSED)
{
/* This should never occur for abitsets since we should always
hit the cache. */
- abort ();
- return 0;
+ return false;
}
stopped. */
static bitset_bindex
abitset_list_reverse (bitset src, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
+ bitset_bindex num, bitset_bindex *next)
{
bitset_bindex bitno;
bitset_bindex rbitno;
unsigned int bitcnt;
bitset_bindex bitoff;
bitset_word *srcp = ABITSET_WORDS (src);
- bitset_bindex n_bits = ABITSET_N_BITS (src);
+ bitset_bindex n_bits = BITSET_SIZE_ (src);
rbitno = *next;
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;
- }
+ {
+ 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;
}
found and with *NEXT indicating where search stopped. */
static bitset_bindex
abitset_list (bitset src, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
+ bitset_bindex num, bitset_bindex *next)
{
bitset_bindex bitno;
bitset_bindex count;
{
/* Many bitsets are zero, so make this common case fast. */
for (windex = 0; windex < size && !srcp[windex]; windex++)
- continue;
+ continue;
if (windex >= size)
- return 0;
+ return 0;
/* If num is 1, we could speed things up with a binary search
- of the current word. */
+ of the current word. */
bitoff = windex * BITSET_WORD_BITS;
}
else
{
- if (bitno >= ABITSET_N_BITS (src))
- return 0;
+ 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++;
- }
+ {
+ /* 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;
+ continue;
if ((count + BITSET_WORD_BITS) < num)
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
+ {
+ 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;
- }
- }
+ {
+ for (bitno = bitoff; word; bitno++)
+ {
+ if (word & 1)
+ {
+ list[count++] = bitno;
+ if (count >= num)
+ {
+ *next = bitno + 1;
+ return count;
+ }
+ }
+ word >>= 1;
+ }
+ }
}
*next = bitoff;
{
unsigned int last_bit;
- last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS;
+ last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
if (last_bit)
ABITSET_WORDS (dst)[dst->b.csize - 1] &=
((bitset_word) 1 << last_bit) - 1;
}
-static int
+static bool
abitset_empty_p (bitset dst)
{
bitset_windex i;
for (i = 0; i < dst->b.csize; i++)
if (dstp[i])
- return 0;
+ return false;
- return 1;
+ return true;
}
}
-static int
+static bool
abitset_equal_p (bitset dst, bitset src)
{
bitset_windex i;
for (i = 0; i < size; i++)
if (*srcp++ != *dstp++)
- return 0;
- return 1;
+ return false;
+ return true;
}
-static int
+static bool
abitset_subset_p (bitset dst, bitset src)
{
bitset_windex i;
for (i = 0; i < size; i++, dstp++, srcp++)
if (*dstp != (*srcp | *dstp))
- return 0;
- return 1;
+ return false;
+ return true;
}
-static int
+static bool
abitset_disjoint_p (bitset dst, bitset src)
{
bitset_windex i;
for (i = 0; i < size; i++)
if (*srcp++ & *dstp++)
- return 0;
+ return false;
- return 1;
+ return true;
}
}
-static int
+static bool
abitset_and_cmp (bitset dst, bitset src1, bitset src2)
{
bitset_windex i;
- int changed = 0;
+ bool changed = false;
bitset_word *src1p = ABITSET_WORDS (src1);
bitset_word *src2p = ABITSET_WORDS (src2);
bitset_word *dstp = ABITSET_WORDS (dst);
bitset_word tmp = *src1p++ & *src2p++;
if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ {
+ changed = true;
+ *dstp = tmp;
+ }
}
return changed;
}
}
-static int
+static bool
abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
{
bitset_windex i;
- int changed = 0;
+ bool changed = false;
bitset_word *src1p = ABITSET_WORDS (src1);
bitset_word *src2p = ABITSET_WORDS (src2);
bitset_word *dstp = ABITSET_WORDS (dst);
bitset_word tmp = *src1p++ & ~(*src2p++);
if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ {
+ changed = true;
+ *dstp = tmp;
+ }
}
return changed;
}
}
-static int
+static bool
abitset_or_cmp (bitset dst, bitset src1, bitset src2)
{
bitset_windex i;
- int changed = 0;
+ bool changed = false;
bitset_word *src1p = ABITSET_WORDS (src1);
bitset_word *src2p = ABITSET_WORDS (src2);
bitset_word *dstp = ABITSET_WORDS (dst);
bitset_word tmp = *src1p++ | *src2p++;
if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ {
+ changed = true;
+ *dstp = tmp;
+ }
}
return changed;
}
}
-static int
+static bool
abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
{
bitset_windex i;
- int changed = 0;
+ bool changed = false;
bitset_word *src1p = ABITSET_WORDS (src1);
bitset_word *src2p = ABITSET_WORDS (src2);
bitset_word *dstp = ABITSET_WORDS (dst);
bitset_word tmp = *src1p++ ^ *src2p++;
if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ {
+ changed = true;
+ *dstp = tmp;
+ }
}
return changed;
}
}
-static int
+static bool
abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
bitset_windex i;
- int changed = 0;
+ bool changed = false;
bitset_word *src1p = ABITSET_WORDS (src1);
bitset_word *src2p = ABITSET_WORDS (src2);
bitset_word *src3p = ABITSET_WORDS (src3);
bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ {
+ changed = true;
+ *dstp = tmp;
+ }
}
return changed;
}
}
-static int
+static bool
abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
bitset_windex i;
- int changed = 0;
+ bool changed = false;
bitset_word *src1p = ABITSET_WORDS (src1);
bitset_word *src2p = ABITSET_WORDS (src2);
bitset_word *src3p = ABITSET_WORDS (src3);
bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ {
+ changed = true;
+ *dstp = tmp;
+ }
}
return changed;
}
}
-static int
+static bool
abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
{
bitset_windex i;
- int changed = 0;
+ bool changed = false;
bitset_word *src1p = ABITSET_WORDS (src1);
bitset_word *src2p = ABITSET_WORDS (src2);
bitset_word *src3p = ABITSET_WORDS (src3);
bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ {
+ changed = true;
+ *dstp = tmp;
+ }
}
return changed;
}
abitset_reset,
bitset_toggle_,
abitset_test,
- abitset_size,
+ abitset_resize,
+ bitset_size_,
bitset_count_,
abitset_empty_p,
abitset_ones,
abitset_reset,
bitset_toggle_,
abitset_test,
- abitset_size,
+ abitset_resize,
+ bitset_size_,
bitset_count_,
abitset_empty_p,
abitset_ones,
bitset_windex size;
size = ABITSET_N_WORDS (n_bits);
- ABITSET_N_BITS (bset) = n_bits;
+ BITSET_NBITS_ (bset) = n_bits;
/* Use optimized routines if bitset fits within a single word.
There is probably little merit if using caching since
projects / bison.git / blobdiff