+2002-09-30 Akim Demaille <akim@epita.fr>
+
+ * lib/abitset.c, lib/bbitset.h, lib/bitset.c, lib/bitset.h,
+ * lib/bitset_stats.c, lib/bitsetv.c, lib/ebitset.c, lib/lbitset.c:
+ Updates from Michael Hayes.
+
2002-09-30 Art Haas <ahaas@neosoft.com>
* configure.ac: Update AC_OUTPUT and AM_CONFIG_HEADER
static void abitset_reset PARAMS ((bitset, bitset_bindex));
static int abitset_test PARAMS ((bitset, bitset_bindex));
static int abitset_size PARAMS ((bitset));
-static int abitset_op1 PARAMS ((bitset, enum bitset_ops));
-static int abitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
-static int abitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
-static int abitset_op4 PARAMS ((bitset, bitset, bitset, bitset,
- enum bitset_ops));
static int abitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
bitset_bindex *));
-static int abitset_reverse_list
+static int abitset_list_reverse
PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
bitset dst ATTRIBUTE_UNUSED;
bitset_bindex bitno ATTRIBUTE_UNUSED;
{
- /* This should never occur for abitsets. */
+ /* This should never occur for abitsets since we should always
+ hit the cache. */
abort ();
}
bitset dst ATTRIBUTE_UNUSED;
bitset_bindex bitno ATTRIBUTE_UNUSED;
{
- /* This should never occur for abitsets. */
+ /* This should never occur for abitsets since we should always
+ hit the cache. */
abort ();
}
bitset src ATTRIBUTE_UNUSED;
bitset_bindex bitno ATTRIBUTE_UNUSED;
{
- /* This should never occur for abitsets. */
+ /* This should never occur for abitsets since we should always
+ hit the cache. */
abort ();
return 0;
}
actual number of bits found and with *NEXT indicating where search
stopped. */
static int
-abitset_reverse_list (src, list, num, next)
+abitset_list_reverse (src, list, num, next)
bitset src;
bitset_bindex *list;
bitset_bindex num;
bitset_windex windex;
unsigned int bitcnt;
bitset_bindex bitoff;
- bitset_word word;
bitset_word *srcp = ABITSET_WORDS (src);
bitset_bindex n_bits = ABITSET_N_BITS (src);
do
{
+ bitset_word word;
+
word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
for (; word; bitcnt--)
{
}
-static int
-abitset_op1 (dst, op)
+static void
+abitset_ones (dst)
bitset dst;
- enum bitset_ops op;
{
- unsigned int i;
bitset_word *dstp = ABITSET_WORDS (dst);
unsigned int bytes;
bytes = sizeof (bitset_word) * dst->b.csize;
- switch (op)
- {
- case BITSET_OP_ZERO:
- memset (dstp, 0, bytes);
- break;
-
- case BITSET_OP_ONES:
- memset (dstp, -1, bytes);
- abitset_unused_clear (dst);
- break;
-
- case BITSET_OP_EMPTY_P:
- for (i = 0; i < dst->b.csize; i++)
- if (dstp[i])
- return 0;
- break;
+ memset (dstp, -1, bytes);
+ abitset_unused_clear (dst);
+}
+
+
+static void
+abitset_zero (dst)
+ bitset dst;
+{
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ unsigned int bytes;
+
+ bytes = sizeof (bitset_word) * dst->b.csize;
+
+ memset (dstp, 0, bytes);
+}
- default:
- abort ();
- }
+
+static int
+abitset_empty_p (dst)
+ bitset dst;
+{
+ unsigned int i;
+ bitset_word *dstp = ABITSET_WORDS (dst);
+
+ for (i = 0; i < dst->b.csize; i++)
+ if (dstp[i])
+ return 0;
return 1;
}
+static void
+abitset_copy1 (dst, src)
+ bitset dst;
+ bitset src;
+{
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ if (srcp == dstp)
+ return;
+ memcpy (dstp, srcp, sizeof (bitset_word) * size);
+}
+
+
+static void
+abitset_not (dst, src)
+ bitset dst;
+ bitset src;
+{
+ unsigned int i;
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++)
+ *dstp++ = ~(*srcp++);
+ abitset_unused_clear (dst);
+}
+
+
static int
-abitset_op2 (dst, src, op)
+abitset_equal_p (dst, src)
bitset dst;
bitset src;
- enum bitset_ops op;
{
unsigned int i;
bitset_word *srcp = ABITSET_WORDS (src);
bitset_word *dstp = ABITSET_WORDS (dst);
bitset_windex size = dst->b.csize;
- switch (op)
- {
- case BITSET_OP_COPY:
- if (srcp == dstp)
- break;
- memcpy (dstp, srcp, sizeof (bitset_word) * size);
- break;
-
- case BITSET_OP_NOT:
- for (i = 0; i < size; i++)
- *dstp++ = ~(*srcp++);
- abitset_unused_clear (dst);
- break;
-
- case BITSET_OP_EQUAL_P:
- for (i = 0; i < size; i++)
- if (*srcp++ != *dstp++)
+ for (i = 0; i < size; i++)
+ if (*srcp++ != *dstp++)
return 0;
- break;
-
- case BITSET_OP_SUBSET_P:
- for (i = 0; i < size; i++, dstp++, srcp++)
- if (*dstp != (*srcp | *dstp))
+ return 1;
+}
+
+
+static int
+abitset_subset_p (dst, src)
+ bitset dst;
+ bitset src;
+{
+ unsigned int i;
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++, dstp++, srcp++)
+ if (*dstp != (*srcp | *dstp))
return 0;
- break;
-
- case BITSET_OP_DISJOINT_P:
- for (i = 0; i < size; i++)
- if (*srcp++ & *dstp++)
+ return 1;
+}
+
+
+static int
+abitset_disjoint_p (dst, src)
+ bitset dst;
+ bitset src;
+{
+ unsigned int i;
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++)
+ if (*srcp++ & *dstp++)
return 0;
- break;
-
- default:
- abort ();
- }
return 1;
}
+static void
+abitset_and (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ unsigned int i;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++)
+ *dstp++ = *src1p++ & *src2p++;
+}
+
+
static int
-abitset_op3 (dst, src1, src2, op)
+abitset_and_cmp (dst, src1, src2)
bitset dst;
bitset src1;
bitset src2;
- enum bitset_ops op;
{
unsigned int i;
int changed = 0;
bitset_word *dstp = ABITSET_WORDS (dst);
bitset_windex size = dst->b.csize;
- switch (op)
+ for (i = 0; i < size; i++, dstp++)
{
- case BITSET_OP_OR:
- for (i = 0; i < size; i++, dstp++)
+ bitset_word tmp = *src1p++ & *src2p++;
+
+ if (*dstp != tmp)
{
- bitset_word tmp = *src1p++ | *src2p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ changed = 1;
+ *dstp = tmp;
}
- break;
+ }
+ return changed;
+}
- case BITSET_OP_AND:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = *src1p++ & *src2p++;
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
+static void
+abitset_andn (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ unsigned int i;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
- case BITSET_OP_XOR:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = *src1p++ ^ *src2p++;
+ for (i = 0; i < size; i++)
+ *dstp++ = *src1p++ & ~(*src2p++);
+}
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
- case BITSET_OP_ANDN:
- for (i = 0; i < size; i++, dstp++)
+static int
+abitset_andn_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ unsigned int i;
+ int changed = 0;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ & ~(*src2p++);
+
+ if (*dstp != tmp)
{
- bitset_word tmp = *src1p++ & ~(*src2p++);
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ changed = 1;
+ *dstp = tmp;
}
- break;
+ }
+ return changed;
+}
+
+
+static void
+abitset_or (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ unsigned int i;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++)
+ *dstp++ = *src1p++ | *src2p++;
+}
+
- default:
- abort ();
+static int
+abitset_or_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ unsigned int i;
+ int changed = 0;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ | *src2p++;
+
+ if (*dstp != tmp)
+ {
+ changed = 1;
+ *dstp = tmp;
+ }
}
+ return changed;
+}
+
+static void
+abitset_xor (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ unsigned int i;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++)
+ *dstp++ = *src1p++ ^ *src2p++;
+}
+
+
+static int
+abitset_xor_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ unsigned int i;
+ int changed = 0;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ ^ *src2p++;
+
+ if (*dstp != tmp)
+ {
+ changed = 1;
+ *dstp = tmp;
+ }
+ }
return changed;
}
+static void
+abitset_and_or (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ unsigned int i;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++)
+ *dstp++ = (*src1p++ & *src2p++) | *src3p++;
+}
+
+
static int
-abitset_op4 (dst, src1, src2, src3, op)
+abitset_and_or_cmp (dst, src1, src2, src3)
bitset dst;
bitset src1;
bitset src2;
bitset src3;
- enum bitset_ops op;
{
unsigned int i;
int changed = 0;
bitset_word *src3p = ABITSET_WORDS (src3);
bitset_word *dstp = ABITSET_WORDS (dst);
bitset_windex size = dst->b.csize;
-
- switch (op)
+
+ for (i = 0; i < size; i++, dstp++)
{
- case BITSET_OP_OR_AND:
- for (i = 0; i < size; i++, dstp++)
+ bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
+
+ if (*dstp != tmp)
{
- bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+ changed = 1;
+ *dstp = tmp;
}
- break;
+ }
+ return changed;
+}
- case BITSET_OP_AND_OR:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
+static void
+abitset_andn_or (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ unsigned int i;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++)
+ *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
+}
- case BITSET_OP_ANDN_OR:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
+static int
+abitset_andn_or_cmp (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ unsigned int i;
+ int changed = 0;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
+
+ if (*dstp != tmp)
+ {
+ changed = 1;
+ *dstp = tmp;
}
- break;
-
- default:
- abort ();
}
+ return changed;
+}
+
+
+static void
+abitset_or_and (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ unsigned int i;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++)
+ *dstp++ = (*src1p++ | *src2p++) & *src3p++;
+}
+
+static int
+abitset_or_and_cmp (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ unsigned int i;
+ int changed = 0;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
+
+ if (*dstp != tmp)
+ {
+ changed = 1;
+ *dstp = tmp;
+ }
+ }
return changed;
}
+void
+abitset_copy (dst, src)
+ bitset dst;
+ bitset src;
+{
+ if (BITSET_COMPATIBLE_ (dst, src))
+ abitset_copy1 (dst, src);
+ else
+ bitset_copy_ (dst, src);
+}
+
+
/* Vector of operations for single word bitsets. */
-struct bitset_ops_struct abitset_small_ops = {
+struct bitset_vtable abitset_small_vtable = {
abitset_set,
abitset_reset,
+ bitset_toggle_,
abitset_test,
abitset_size,
- abitset_op1,
- abitset_op2,
- abitset_op3,
- abitset_op4,
+ bitset_count_,
+ abitset_empty_p,
+ abitset_ones,
+ abitset_zero,
+ abitset_copy,
+ abitset_disjoint_p,
+ abitset_equal_p,
+ abitset_not,
+ abitset_subset_p,
+ abitset_and,
+ abitset_and_cmp,
+ abitset_andn,
+ abitset_andn_cmp,
+ abitset_or,
+ abitset_or_cmp,
+ abitset_xor,
+ abitset_xor_cmp,
+ abitset_and_or,
+ abitset_and_or_cmp,
+ abitset_andn_or,
+ abitset_andn_or_cmp,
+ abitset_or_and,
+ abitset_or_and_cmp,
abitset_small_list,
- abitset_reverse_list,
+ abitset_list_reverse,
NULL,
BITSET_ARRAY
};
/* Vector of operations for multiple word bitsets. */
-struct bitset_ops_struct abitset_ops = {
+struct bitset_vtable abitset_vtable = {
abitset_set,
abitset_reset,
+ bitset_toggle_,
abitset_test,
abitset_size,
- abitset_op1,
- abitset_op2,
- abitset_op3,
- abitset_op4,
+ bitset_count_,
+ abitset_empty_p,
+ abitset_ones,
+ abitset_zero,
+ abitset_copy,
+ abitset_disjoint_p,
+ abitset_equal_p,
+ abitset_not,
+ abitset_subset_p,
+ abitset_and,
+ abitset_and_cmp,
+ abitset_andn,
+ abitset_andn_cmp,
+ abitset_or,
+ abitset_or_cmp,
+ abitset_xor,
+ abitset_xor_cmp,
+ abitset_and_or,
+ abitset_and_or_cmp,
+ abitset_andn_or,
+ abitset_andn_or_cmp,
+ abitset_or_and,
+ abitset_or_and_cmp,
abitset_list,
- abitset_reverse_list,
+ abitset_list_reverse,
NULL,
BITSET_ARRAY
};
There is probably little merit if using caching since
the small bitset will always fit in the cache. */
if (size == 1)
- bset->b.ops = &abitset_small_ops;
+ bset->b.vtable = &abitset_small_vtable;
else
- bset->b.ops = &abitset_ops;
+ bset->b.vtable = &abitset_vtable;
bset->b.cindex = 0;
bset->b.csize = size;
#endif
/* Currently we support three flavours of bitsets:
- BITSET_ARRAY: Array of bits (fixed size, faster).
+ BITSET_ARRAY: Array of bits (fixed size, fast for dense bitsets).
BITSET_LIST: Linked list of array of bits (variable size, least storage
- for large very sparse sets).
+ for large very sparse sets).
BITSET_TABLE: Expandable table of pointers to array of bits
- (variable size, less storage for large sparse sets).
+ (variable size, less storage for large sparse sets).
BITSET_STATS: Wrapper bitset for internal use only.
*/
BITSET_STATS};
#define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset"}
+extern const char * const bitset_type_names[];
+
enum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC};
/* Non-zero to use inline functions instead of macros. */
BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN,
BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR};
+struct bbitset_struct
+{
+ const struct bitset_vtable * vtable;
+ 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. */
+};
+
+
+typedef struct bitset_struct *bitset;
+
+
+/* The contents of this structure should be considered private. */
+struct bitset_vtable
+{
+ void (*set) PARAMS ((struct bitset_struct *, bitset_bindex));
+ void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex));
+ int (*toggle) PARAMS ((struct bitset_struct *, bitset_bindex));
+ int (*test) PARAMS ((struct bitset_struct *, bitset_bindex));
+ int (*size) PARAMS ((struct bitset_struct *));
+ int (*count) PARAMS ((struct bitset_struct *));
+
+ int (*empty_p) PARAMS ((struct bitset_struct *));
+ void (*ones) PARAMS ((struct bitset_struct *));
+ void (*zero) PARAMS ((struct bitset_struct *));
+
+ void (*copy) PARAMS ((struct bitset_struct *, struct bitset_struct *));
+ int (*disjoint_p) PARAMS ((struct bitset_struct *, struct bitset_struct *));
+ int (*equal_p) PARAMS ((struct bitset_struct *, struct bitset_struct *));
+ void (*not) PARAMS ((struct bitset_struct *, struct bitset_struct *));
+ int (*subset_p) PARAMS ((struct bitset_struct *, struct bitset_struct *));
+
+ void (*and) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *));
+ int (*and_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *));
+ void (*andn) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *));
+ int (*andn_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *));
+ void (*or) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *));
+ int (*or_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *));
+ void (*xor) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *));
+ int (*xor_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *));
+
+ void (*and_or) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *, struct bitset_struct *));
+ int (*and_or_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *, struct bitset_struct *));
+ void (*andn_or) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *, struct bitset_struct *));
+ int (*andn_or_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *, struct bitset_struct *));
+ void (*or_and) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *, struct bitset_struct *));
+ int (*or_and_cmp) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+ struct bitset_struct *, struct bitset_struct *));
+
+ int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *,
+ bitset_bindex, bitset_bindex *));
+ int (*list_reverse) PARAMS ((struct bitset_struct *, bitset_bindex *,
+ bitset_bindex, bitset_bindex *));
+ void (*free) PARAMS ((struct bitset_struct *));
+ enum bitset_type type;
+};
+
+#define BITSET_COMPATIBLE_(BSET1, BSET2) ((BSET1)->b.vtable == (BSET2)->b.vtable)
+
+#define BITSET_CHECK2_(DST, SRC) \
+if (!BITSET_COMPATIBLE_ (DST, SRC)) abort ();
+
+#define BITSET_CHECK3_(DST, SRC1, SRC2) \
+if (!BITSET_COMPATIBLE_ (DST, SRC1) \
+ || !BITSET_COMPATIBLE_ (DST, SRC2)) abort ();
+
+#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \
+if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \
+ || !BITSET_COMPATIBLE_ (DST, SRC3)) abort ();
+
+
/* Return size in bits of bitset SRC. */
-#define BITSET_SIZE_(SRC) (SRC)->b.ops->size (SRC)
+#define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC)
+
+/* Return number of bits set in bitset SRC. */
+#define BITSET_COUNT_(SRC) (SRC)->b.vtable->count (SRC)
/* Return type of bitset SRC. */
-#define BITSET_TYPE_(DST) (DST)->b.ops->type
+#define BITSET_TYPE_(DST) (DST)->b.vtable->type
/* Set bit BITNO in bitset DST. */
-#define BITSET_SET_(DST, BITNO) (DST)->b.ops->set (DST, BITNO)
+#define BITSET_SET_(DST, BITNO) (DST)->b.vtable->set (DST, BITNO)
/* Reset bit BITNO in bitset DST. */
-#define BITSET_RESET_(DST, BITNO) (DST)->b.ops->reset (DST, BITNO)
+#define BITSET_RESET_(DST, BITNO) (DST)->b.vtable->reset (DST, BITNO)
+
+/* Toggle bit BITNO in bitset DST. */
+#define BITSET_TOGGLE_(DST, BITNO) (DST)->b.vtable->toggle (DST, BITNO)
/* Return non-zero if bit BITNO in bitset SRC is set. */
-#define BITSET_TEST_(SRC, BITNO) (SRC)->b.ops->test (SRC, BITNO)
+#define BITSET_TEST_(SRC, BITNO) (SRC)->b.vtable->test (SRC, BITNO)
/* Free bitset SRC. */
#define BITSET_FREE_(SRC)\
- ((SRC)->b.ops->free ? (SRC)->b.ops->free (SRC) :(void)0)
-
-/* Perform operation OP on DST. */
-#define BITSET_OP1_(DST, OP) (DST)->b.ops->op1 (DST, OP)
+ ((SRC)->b.vtable->free ? (SRC)->b.vtable->free (SRC) :(void)0)
-/* Perform operation OP on SRC and store in DST. */
-#define BITSET_OP2_(DST, SRC, OP) (DST)->b.ops->op2 (DST, SRC, OP)
-/* DST = SRC1 OP SRC2. */
-#define BITSET_OP3_(DST, SRC1, SRC2, OP) \
-(DST)->b.ops->op3 (DST, SRC1, SRC2, OP)
+/* Return SRC == 0. */
+#define BITSET_EMPTY_P_(SRC) (SRC)->b.vtable->empty_p (SRC)
-/* DST = (SRC1 OP1 SRC2) OP2 SRC3. */
-#define BITSET_OP4_(DST, SRC1, SRC2, SRC3, OP) \
-(DST)->b.ops->op4 (DST, SRC1, SRC2, SRC3, OP)
+/* DST = ~0. */
+#define BITSET_ONES_(DST) (DST)->b.vtable->ones (DST)
/* DST = 0. */
-#define BITSET_ZERO_(DST) BITSET_OP1_ (DST, BITSET_OP_ZERO);
+#define BITSET_ZERO_(DST) (DST)->b.vtable->zero (DST)
-/* DST = ~0. */
-#define BITSET_ONES_(DST) BITSET_OP1_ (DST, BITSET_OP_ONES);
-/* Return SRC == 0. */
-#define BITSET_EMPTY_P_(SRC) BITSET_OP1_ (SRC, BITSET_OP_EMPTY_P);
+
+/* DST = SRC. */
+#define BITSET_COPY_(DST, SRC) (SRC)->b.vtable->copy (DST, SRC)
+
+/* Return DST & SRC == 0. */
+#define BITSET_DISJOINT_P_(DST, SRC) (SRC)->b.vtable->disjoint_p (DST, SRC)
/* Return DST == SRC. */
-#define BITSET_EQUAL_P_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_EQUAL_P)
+#define BITSET_EQUAL_P_(DST, SRC) (SRC)->b.vtable->equal_p (DST, SRC)
+
+/* DST = ~SRC. */
+#define BITSET_NOT_(DST, SRC) (SRC)->b.vtable->not (DST, SRC)
/* Return DST == DST | SRC. */
-#define BITSET_SUBSET_P_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_SUBSET_P)
+#define BITSET_SUBSET_P_(DST, SRC) (SRC)->b.vtable->subset_p (DST, SRC)
-/* Return DST & SRC == 0. */
-#define BITSET_DISJOINT_P_(DST, SRC)\
- BITSET_OP2_ (DST, SRC, BITSET_OP_DISJOINT_P)
-/* DST = SRC. */
-#define BITSET_COPY_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_COPY)
+/* DST = SRC1 & SRC2. */
+#define BITSET_AND_(DST, SRC1, SRC2) (SRC1)->b.vtable->and (DST, SRC1, SRC2)
+#define BITSET_AND_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_cmp (DST, SRC1, SRC2)
-/* DST = ~SRC. */
-#define BITSET_NOT_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_NOT)
+/* DST = SRC1 & ~SRC2. */
+#define BITSET_ANDN_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn (DST, SRC1, SRC2)
+#define BITSET_ANDN_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn_cmp (DST, SRC1, SRC2)
/* DST = SRC1 | SRC2. */
-#define BITSET_OR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\
- BITSET_OP_OR)
+#define BITSET_OR_(DST, SRC1, SRC2) (SRC1)->b.vtable->or (DST, SRC1, SRC2)
+#define BITSET_OR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_cmp (DST, SRC1, SRC2)
/* DST = SRC1 ^ SRC2. */
-#define BITSET_XOR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\
- BITSET_OP_XOR)
+#define BITSET_XOR_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor (DST, SRC1, SRC2)
+#define BITSET_XOR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_cmp (DST, SRC1, SRC2)
-/* DST = SRC1 & SRC2. */
-#define BITSET_AND_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \
- BITSET_OP_AND)
-/* DST = SRC1 & ~SRC2. */
-#define BITSET_ANDN_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \
- BITSET_OP_ANDN)
/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
DST != (SRC1 & SRC2) | SRC3. */
-#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3)\
- BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_AND_OR)
+#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->and_or (DST, SRC1, SRC2, SRC3)
+#define BITSET_AND_OR_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->and_or_cmp (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & ~SRC2) | SRC3. */
+#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->andn_or (DST, SRC1, SRC2, SRC3)
+#define BITSET_ANDN_OR_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->andn_or_cmp (DST, SRC1, SRC2, SRC3)
/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
DST != (SRC1 | SRC2) & SRC3. */
-#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3)\
- BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_OR_AND)
+#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->or_and (DST, SRC1, SRC2, SRC3)
+#define BITSET_OR_AND_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->or_and_cmp (DST, SRC1, SRC2, SRC3)
-/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & ~SRC2) | SRC3. */
-#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3)\
- BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_ANDN_OR)
/* 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. */
#define BITSET_LIST_(BSET, LIST, NUM, NEXT) \
-(BSET)->b.ops->list (BSET, LIST, NUM, NEXT)
+ (BSET)->b.vtable->list (BSET, LIST, NUM, NEXT)
/* Find reverse 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. */
-#define BITSET_REVERSE_LIST_(BSET, LIST, NUM, NEXT) \
-(BSET)->b.ops->reverse_list (BSET, LIST, NUM, NEXT)
+#define BITSET_LIST_REVERSE_(BSET, LIST, NUM, NEXT) \
+ (BSET)->b.vtable->list_reverse (BSET, LIST, NUM, NEXT)
-struct bbitset_struct
-{
- struct bitset_ops_struct *ops;
- 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. */
-};
+/* Private functions for bitset implementations. */
+
+extern int bitset_toggle_ PARAMS ((bitset, bitset_bindex));
+extern int bitset_count_ PARAMS ((bitset));
-typedef struct bitset_struct *bitset;
-
-
-/* The contents of this structure should be considered private. */
-struct bitset_ops_struct
-{
- void (*set) PARAMS ((struct bitset_struct *, bitset_bindex));
- void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex));
- int (*test) PARAMS ((struct bitset_struct *, bitset_bindex));
- int (*size) PARAMS ((struct bitset_struct *));
- int (*op1) PARAMS ((struct bitset_struct *, enum bitset_ops));
- int (*op2) PARAMS ((struct bitset_struct *, struct bitset_struct *,
- enum bitset_ops));
- int (*op3) PARAMS ((struct bitset_struct *, struct bitset_struct *,
- struct bitset_struct *, enum bitset_ops));
- int (*op4) PARAMS ((struct bitset_struct *, struct bitset_struct *,
- struct bitset_struct *, struct bitset_struct *,
- enum bitset_ops));
- int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *,
- bitset_bindex, bitset_bindex *));
- int (*reverse_list) PARAMS ((struct bitset_struct *, bitset_bindex *,
- bitset_bindex, bitset_bindex *));
- void (*free) PARAMS ((struct bitset_struct *));
- enum bitset_type type;
-};
+extern int bitset_copy_ PARAMS ((bitset, bitset));
-#define BITSET_COMPATIBLE_(BSET1, BSET2) ((BSET1)->b.ops == (BSET2)->b.ops)
-
-#define BITSET_CHECK2_(DST, SRC) \
-if (!BITSET_COMPATIBLE_ (DST, SRC)) abort ();
-
-#define BITSET_CHECK3_(DST, SRC1, SRC2) \
-if (!BITSET_COMPATIBLE_ (DST, SRC1) \
- || !BITSET_COMPATIBLE_ (DST, SRC2)) abort ();
-
-#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \
-if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \
- || !BITSET_COMPATIBLE_ (DST, SRC3)) abort ();
+extern int bitset_and_or_cmp_ PARAMS ((bitset, bitset, bitset, bitset));
+extern int bitset_andn_or_cmp_ PARAMS ((bitset, bitset, bitset, bitset));
-extern int bitset_op4 PARAMS ((bitset, bitset, bitset, bitset,
- enum bitset_ops op));
+extern int bitset_or_and_cmp_ PARAMS ((bitset, bitset, bitset, bitset));
#endif /* _BBITSET_H */
#include "bitset_stats.h"
#include "obstack.h"
+const char * const bitset_type_names[] = BITSET_TYPE_NAMES;
+
static void bitset_print PARAMS ((FILE *, bitset, int));
if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
abort ();
- /* Note that sometimes we will be asked for a zero length
- fixed size bitset. */
-
- /* Choose the type of bitset. */
+ /* Choose the type of bitset. Note that sometimes we will be asked
+ for a zero length fixed size bitset. */
type = BITSET_ARRAY;
/* Currently, the simple bitsets do not support a variable size. */
}
+/* Return name of bitset type. */
+const char *
+bitset_type_name_get (bset)
+ bitset bset;
+{
+ enum bitset_type type;
+
+ type = bitset_type_get (bset);
+
+ return bitset_type_names[type];
+}
+
+
/* Find next bit set in SRC starting from and including BITNO.
Return -1 if SRC empty. */
int
bitset_bindex val;
bitset_bindex next = bitno;
- if (!bitset_reverse_list (src, &val, 1, &next))
+ if (!bitset_list_reverse (src, &val, 1, &next))
return -1;
return val;
}
}
-/* 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)
bitset bset;
int verbose;
{
- unsigned int i, pos;
+ unsigned int pos;
+ bitset_bindex i;
bitset_iterator iter;
if (verbose)
}
-/* DST = SRC. Return non-zero if DST != SRC. */
-int
-bitset_copy (dst, src)
- bitset dst;
- bitset src;
+/* Dump bitset BSET to FILE. */
+void
+bitset_dump (file, bset)
+ FILE *file;
+ bitset bset;
{
- unsigned int i;
- bitset_iterator iter;
+ bitset_print (file, bset, 0);
+}
- if (BITSET_COMPATIBLE_ (dst, src))
- return BITSET_COPY_ (dst, src);
- /* Convert bitset types. We assume that the DST bitset
- is large enough to hold the SRC bitset. */
- bitset_zero (dst);
- BITSET_FOR_EACH (iter, src, i, 0)
- {
- bitset_set (dst, i);
- };
- return 1;
+/* Release memory associated with bitsets. */
+void
+bitset_release_memory ()
+{
+ lbitset_release_memory ();
+ ebitset_release_memory ();
}
-/* Return size in bits of bitset SRC. */
+
+/* Toggle bit BITNO in bitset BSET and return non-zero if not set. */
int
-bitset_size (src)
- bitset src;
+bitset_toggle_ (bset, bitno)
+ bitset bset;
+ bitset_bindex bitno;
{
- return BITSET_SIZE_ (src);
+ /* 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;
+ }
}
/* Return number of bits set in bitset SRC. */
int
-bitset_count (src)
+bitset_count_ (src)
bitset src;
{
bitset_bindex list[BITSET_LIST_SIZE];
}
-/* DST = 0. */
-int
-bitset_zero (dst)
- bitset dst;
-{
- return BITSET_ZERO_ (dst);
-}
-
-
-/* DST = ~0. */
-int
-bitset_ones (dst)
- bitset dst;
-{
- return BITSET_ONES_ (dst);
-}
-
-
-/* Return SRC == 0. */
-int
-bitset_empty_p (src)
- bitset src;
-{
- return BITSET_EMPTY_P_ (src);
-}
-
-
-/* Return DST == DST | SRC. */
-int
-bitset_subset_p (dst, src)
- bitset dst;
- bitset src;
-{
- return BITSET_SUBSET_P_ (dst, src);
-}
-
-
-/* Return DST == SRC. */
-int
-bitset_equal_p (dst, src)
- bitset dst;
- bitset src;
-{
- return BITSET_EQUAL_P_ (dst, src);
-}
-
-
-/* Return DST & SRC == 0. */
+/* DST = SRC. Return non-zero if DST != SRC.
+ This is a fallback for the case where SRC and DST are different
+ bitset types. */
int
-bitset_disjoint_p (dst, src)
+bitset_copy_ (dst, src)
bitset dst;
bitset src;
{
- return BITSET_DISJOINT_P_ (dst, src);
-}
-
-
-/* DST = ~SRC. */
-int
-bitset_not (dst, src)
- bitset dst;
- bitset src;
-{
- return BITSET_NOT_ (dst, src);
-}
-
-
-/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
-int
-bitset_or (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
-{
- return BITSET_OR_ (dst, src1, src2);
-}
-
-
-/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
-int
-bitset_and (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
-{
- return BITSET_AND_ (dst, src1, src2);
-}
-
-
-/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
-int
-bitset_xor (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
-{
- return BITSET_XOR_ (dst, src1, src2);
-}
+ bitset_bindex i;
+ bitset_iterator iter;
+ /* Convert bitset types. We assume that the DST bitset
+ is large enough to hold the SRC bitset. */
+ bitset_zero (dst);
+ BITSET_FOR_EACH (iter, src, i, 0)
+ {
+ bitset_set (dst, i);
+ };
-/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
-int
-bitset_andn (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
-{
- return BITSET_ANDN_ (dst, src1, src2);
+ return 1;
}
/* This is a fallback for implementations that do not support
four operand operations. */
-int
-bitset_op4 (dst, src1, src2, src3, op)
+static inline int
+bitset_op4_cmp (dst, src1, src2, src3, op)
bitset dst;
bitset src1;
bitset src2;
enum bitset_ops op;
{
int changed = 0;
+ int stats_enabled_save;
bitset tmp;
/* Create temporary bitset. */
+ stats_enabled_save = bitset_stats_enabled;
+ bitset_stats_enabled = 0;
tmp = bitset_alloc (0, bitset_type_get (dst));
+ bitset_stats_enabled = stats_enabled_save;
switch (op)
{
case BITSET_OP_OR_AND:
- BITSET_OR_ (tmp, src1, src2);
- changed = BITSET_AND_ (dst, src3, tmp);
+ bitset_or (tmp, src1, src2);
+ changed = bitset_and_cmp (dst, src3, tmp);
break;
case BITSET_OP_AND_OR:
- BITSET_AND_ (tmp, src1, src2);
- changed = BITSET_OR_ (dst, src3, tmp);
+ bitset_and (tmp, src1, src2);
+ changed = bitset_or_cmp (dst, src3, tmp);
break;
case BITSET_OP_ANDN_OR:
- BITSET_ANDN_ (tmp, src1, src2);
- changed = BITSET_OR_ (dst, src3, tmp);
+ bitset_andn (tmp, src1, src2);
+ changed = bitset_or_cmp (dst, src3, tmp);
break;
default:
}
-/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
- DST != (SRC1 | SRC2) & SRC3. */
+/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & SRC2) | SRC3. */
int
-bitset_or_and (dst, src1, src2, src3)
+bitset_and_or_cmp_ (dst, src1, src2, src3)
bitset dst;
bitset src1;
bitset src2;
bitset src3;
{
- return BITSET_OR_AND_ (dst, src1, src2, src3);
+ return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
}
-/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & SRC2) | SRC3. */
+/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & ~SRC2) | SRC3. */
int
-bitset_and_or (dst, src1, src2, src3)
+bitset_andn_or_cmp_ (dst, src1, src2, src3)
bitset dst;
bitset src1;
bitset src2;
bitset src3;
{
- return BITSET_AND_OR_ (dst, src1, src2, src3);
+ return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
}
-/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & ~SRC2) | SRC3. */
+/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
+ DST != (SRC1 | SRC2) & SRC3. */
int
-bitset_andn_or (dst, src1, src2, src3)
+bitset_or_and_cmp_ (dst, src1, src2, src3)
bitset dst;
bitset src1;
bitset src2;
bitset src3;
{
- return BITSET_ANDN_OR_ (dst, src1, src2, src3);
-}
-
-
-/* Dump bitset BSET to FILE. */
-void
-bitset_dump (file, bset)
- FILE *file;
- bitset bset;
-{
- bitset_print (file, bset, 0);
+ return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
}
if (bset)
bitset_print (stderr, bset, 1);
}
-
-
-/* Release memory associated with bitsets. */
-void
-bitset_release_memory ()
-{
- lbitset_release_memory ();
- ebitset_release_memory ();
-}
BITSET_DENSE = 4, /* Bitset dense. */
BITSET_SPARSE = 8, /* Bitset sparse. */
BITSET_FRUGAL = 16, /* Prefer most compact. */
- BITSET_GREEDY = 32}; /* Prefer fastest. */
+ BITSET_GREEDY = 32}; /* Prefer fastest at memory expense. */
typedef unsigned int bitset_attrs;
/* Create a bitset of desired size and attributes. The bitset is zeroed. */
extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
-/* Return size in bits of bitset SRC. */
-extern int bitset_size PARAMS ((bitset));
-
-/* Return number of bits set in bitset SRC. */
-extern int bitset_count PARAMS ((bitset));
-
/* Return bitset type. */
extern enum bitset_type bitset_type_get PARAMS ((bitset));
+/* Return bitset type name. */
+extern const char *bitset_type_name_get PARAMS ((bitset));
+
#if BITSET_INLINE
static inline void bitset_set PARAMS ((bitset, bitset_bindex));
static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
bitset_windex _index = _bitno / BITSET_WORD_BITS; \
bitset_windex _offset = _index - (bset)->b.cindex; \
\
- if (_offset < (bset)->b.csize) \
- (bset)->b.cdata[_offset] &= \
- ~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
+ if (_offset < (bset)->b.csize) \
+ (bset)->b.cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \
else \
BITSET_RESET_ ((bset), _bitno); \
} while (0)
/* Test bit BITNO in bitset BSET. */
#define bitset_test(bset, bitno) \
-(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
- ? (((int) \
- ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
- >> ((bitno) % BITSET_WORD_BITS))) \
- & 1) \
- : BITSET_TEST_ ((bset), (bitno)))
+(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
+ ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
+ >> ((bitno) % BITSET_WORD_BITS)) & 1 \
+ : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
#endif
/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
-extern int bitset_toggle PARAMS ((bitset, bitset_bindex));
+#define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
-/* DST = 0. */
-extern int bitset_zero PARAMS ((bitset));
+/* Return size in bits of bitset SRC. */
+#define bitset_size(SRC) BITSET_SIZE_ (SRC)
+
+/* Return number of bits set in bitset SRC. */
+#define bitset_count(SRC) BITSET_COUNT_ (SRC)
+
+
+/* Return SRC == 0. */
+#define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
/* DST = ~0. */
-extern int bitset_ones PARAMS ((bitset));
+#define bitset_ones(DST) BITSET_ONES_ (DST)
-/* Return non-zero if all bits in bitset SRC are reset. */
-extern int bitset_empty_p PARAMS ((bitset));
+/* DST = 0. */
+#define bitset_zero(DST) BITSET_ZERO_ (DST)
-/* Return DST == DST | SRC. */
-extern int bitset_subset_p PARAMS ((bitset, bitset));
-/* Return DST == SRC. */
-extern int bitset_equal_p PARAMS ((bitset, bitset));
+
+/* DST = SRC. */
+#define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
/* Return DST & SRC == 0. */
-extern int bitset_disjoint_p PARAMS ((bitset, bitset));
+#define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
-/* DST == SRC. */
-extern int bitset_copy PARAMS ((bitset, bitset));
+/* Return DST == SRC. */
+#define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
/* DST = ~SRC. */
-extern int bitset_not PARAMS ((bitset, bitset));
+#define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
+
+/* Return DST == DST | SRC. */
+#define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
-/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
-extern int bitset_or PARAMS ((bitset, bitset, bitset));
+
+
+/* DST = SRC1 & SRC2. */
+#define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
-extern int bitset_and PARAMS ((bitset, bitset, bitset));
+#define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
-/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
-extern int bitset_xor PARAMS ((bitset, bitset, bitset));
+/* DST = SRC1 & ~SRC2. */
+#define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
-extern int bitset_andn PARAMS ((bitset, bitset, bitset));
+#define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
-/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
- DST != (SRC1 | SRC2) & SRC3. */
-extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
+/* DST = SRC1 | SRC2. */
+#define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
+#define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 ^ SRC2. */
+#define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
+#define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
+
+
+
+/* DST = (SRC1 & SRC2) | SRC3. */
+#define bitset_and_or(DST, SRC1, SRC2, SRC3) \
+ BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
DST != (SRC1 & SRC2) | SRC3. */
-extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
+#define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
+ BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 & ~SRC2) | SRC3. */
+#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
+ BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
DST != (SRC1 & ~SRC2) | SRC3. */
-extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
-
-/* Find next bit set in BSET starting from and including BITNO. */
-extern int bitset_next PARAMS ((bitset, bitset_bindex));
+#define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
+ BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
-/* Find previous bit set in BSET starting from and including BITNO. */
-extern int bitset_prev PARAMS ((bitset, bitset_bindex));
+/* DST = (SRC1 | SRC2) & SRC3. */
+#define bitset_or_and(DST, SRC1, SRC2, SRC3)\
+ BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
-/* Return non-zero if BITNO in SRC is the only set bit. */
-extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
+/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
+ DST != (SRC1 | SRC2) & SRC3. */
+#define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
+ BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
/* 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. */
#define bitset_list(BSET, LIST, NUM, NEXT) \
-BITSET_LIST_ (BSET, LIST, NUM, NEXT)
+ BITSET_LIST_ (BSET, LIST, NUM, NEXT)
/* Find reverse 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. */
-#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
-BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT)
+#define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
+ BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
+
/* Find first set bit. */
extern int bitset_first PARAMS ((bitset));
extern void bitset_dump PARAMS ((FILE *, bitset));
/* Loop over all elements of BSET, starting with MIN, setting BIT
- to the index of each set bit. */
+ to the index of each set bit. For example, the following will print
+ the bits set in a bitset:
+
+ bitset_bindex i;
+ bitset_iterator iter;
+
+ bitset_zero (dst);
+ BITSET_FOR_EACH (iter, src, i, 0)
+ {
+ printf ("%ld ", i);
+ };
+*/
#define BITSET_FOR_EACH(ITER, BSET, BIT, MIN) \
for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
(ITER.num == BITSET_LIST_SIZE) \
/* Loop over all elements of BSET, in reverse order starting with
- MIN, setting BIT to the index of each set bit. */
+ MIN, setting BIT to the index of each set bit. For example, the
+ following will print the bits set in a bitset in reverse order:
+
+ bitset_bindex i;
+ bitset_iterator iter;
+
+ bitset_zero (dst);
+ BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
+ {
+ printf ("%ld ", i);
+ };
+*/
#define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN) \
for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
(ITER.num == BITSET_LIST_SIZE) \
/* Define set operations in terms of logical operations. */
-#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
+#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
+#define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
-#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
+#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
+#define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
-#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
+#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
+#define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
+/* Symmetrical difference. */
+#define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
+#define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
+
+/* Union of difference. */
#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
bitset_andn_or (DST, SRC1, SRC2, SRC3)
+#define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
+ bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
+
/* Release any memory tied up with bitsets. */
static void bitset_stats_set PARAMS ((bitset, bitset_bindex));
static void bitset_stats_reset PARAMS ((bitset, bitset_bindex));
+static int bitset_stats_toggle PARAMS ((bitset, bitset_bindex));
static int bitset_stats_test PARAMS ((bitset, bitset_bindex));
static int bitset_stats_size PARAMS ((bitset));
-static int bitset_stats_op1 PARAMS ((bitset, enum bitset_ops));
-static int bitset_stats_op2 PARAMS ((bitset, bitset, enum bitset_ops));
-static int bitset_stats_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
-static int bitset_stats_op4 PARAMS ((bitset, bitset, bitset, bitset,
- enum bitset_ops));
static int bitset_stats_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
bitset_bindex *));
-static int bitset_stats_reverse_list
+static int bitset_stats_list_reverse
PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
static void bitset_stats_free PARAMS ((bitset));
static void bitset_percent_histogram_print PARAMS ((FILE *, const char *,
unsigned int i;
unsigned int total;
unsigned int max_width;
- unsigned int last_bin;
total = 0;
for (i = 0; i < n_bins; i++)
if (!total)
return;
+ /* Determine number of useful bins. */
for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
continue;
- last_bin = i - 1;
+ n_bins = i;
/* 2 * ceil (log10 (2) * (N - 1)) + 1. */
max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
fprintf (file, "%*d\t%8d (%5.1f%%)\n",
max_width, i, bins[i], 100.0 * bins[i] / total);
- for (; i <= last_bin; i++)
+ for (; i < n_bins; i++)
fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n",
max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
1 << (i - 1), (1 << i) - 1, bins[i],
int verbose ATTRIBUTE_UNUSED;
{
int i;
- static const char *names[] = BITSET_TYPE_NAMES;
if (!bitset_stats_info)
return;
fprintf (file, _("Accumulated runs = %d\n"), bitset_stats_info->runs);
for (i = 0; i < BITSET_TYPE_NUM; i++)
- bitset_stats_print_1 (file, names[i], &bitset_stats_info->types[i]);
+ bitset_stats_print_1 (file, bitset_type_names[i],
+ &bitset_stats_info->types[i]);
}
}
+static int
+bitset_stats_toggle (src, bitno)
+ bitset src;
+ bitset_bindex bitno;
+{
+ return BITSET_TOGGLE_ (src->s.bset, bitno);
+}
+
+
static int
bitset_stats_test (src, bitno)
bitset src;
static int
-bitset_stats_op1 (dst, op)
+bitset_stats_count (src)
+ bitset src;
+{
+ return BITSET_COUNT_ (src->s.bset);
+}
+
+
+static int
+bitset_stats_empty_p (dst)
+ bitset dst;
+{
+ return BITSET_EMPTY_P_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_ones (dst)
+ bitset dst;
+{
+ BITSET_ONES_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_zero (dst)
+ bitset dst;
+{
+ BITSET_ZERO_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_copy (dst, src)
+ bitset dst;
+ bitset src;
+{
+ BITSET_CHECK2_ (dst, src);
+ BITSET_COPY_ (dst->s.bset, src->s.bset);
+}
+
+
+static int
+bitset_stats_disjoint_p (dst, src)
bitset dst;
- enum bitset_ops op;
+ bitset src;
{
- return BITSET_OP1_ (dst->s.bset, op);
+ BITSET_CHECK2_ (dst, src);
+ return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset);
}
static int
-bitset_stats_op2 (dst, src, op)
+bitset_stats_equal_p (dst, src)
bitset dst;
bitset src;
- enum bitset_ops op;
{
BITSET_CHECK2_ (dst, src);
- return BITSET_OP2_ (dst->s.bset, src->s.bset, op);
+ return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static void
+bitset_stats_not (dst, src)
+ bitset dst;
+ bitset src;
+{
+ BITSET_CHECK2_ (dst, src);
+ BITSET_NOT_ (dst->s.bset, src->s.bset);
+}
+
+
+static int
+bitset_stats_subset_p (dst, src)
+ bitset dst;
+ bitset src;
+{
+ BITSET_CHECK2_ (dst, src);
+ return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static void
+bitset_stats_and (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static int
+bitset_stats_and_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_andn (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static int
+bitset_stats_andn_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_or (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static int
+bitset_stats_or_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_xor (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset);
}
static int
-bitset_stats_op3 (dst, src1, src2, op)
+bitset_stats_xor_cmp (dst, src1, src2)
bitset dst;
bitset src1;
bitset src2;
- enum bitset_ops op;
{
BITSET_CHECK3_ (dst, src1, src2);
- return BITSET_OP3_ (dst->s.bset, src1->s.bset, src2->s.bset, op);
+ return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_and_or (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+
+ BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
}
static int
-bitset_stats_op4 (dst, src1, src2, src3, op)
+bitset_stats_and_or_cmp (dst, src1, src2, src3)
bitset dst;
bitset src1;
bitset src2;
bitset src3;
- enum bitset_ops op;
{
BITSET_CHECK4_ (dst, src1, src2, src3);
- /* This is a bit of a hack. If the implementation handles
- a four operand operation then vector to it, passing
- the enclosed bitsets. Otherwise use the fallback
- bitset_op4 routine. */
- if (dst->s.bset->b.ops->op4 != bitset_op4)
- return BITSET_OP4_ (dst->s.bset, src1->s.bset, src2->s.bset,
- src3->s.bset, op);
+ return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static void
+bitset_stats_andn_or (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+
+ BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static int
+bitset_stats_andn_or_cmp (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+
+ return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static void
+bitset_stats_or_and (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+
+ BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static int
+bitset_stats_or_and_cmp (dst, src1, src2, src3)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
- return bitset_op4 (dst, src1, src2, src3, op);
+ return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
}
static int
-bitset_stats_reverse_list (bset, list, num, next)
+bitset_stats_list_reverse (bset, list, num, next)
bitset bset;
bitset_bindex *list;
bitset_bindex num;
bitset_bindex *next;
{
- return BITSET_REVERSE_LIST_ (bset->s.bset, list, num, next);
+ return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next);
}
}
-struct bitset_ops_struct bitset_stats_ops = {
+struct bitset_vtable bitset_stats_vtable = {
bitset_stats_set,
bitset_stats_reset,
+ bitset_stats_toggle,
bitset_stats_test,
bitset_stats_size,
- bitset_stats_op1,
- bitset_stats_op2,
- bitset_stats_op3,
- bitset_stats_op4,
+ bitset_stats_count,
+ bitset_stats_empty_p,
+ bitset_stats_ones,
+ bitset_stats_zero,
+ bitset_stats_copy,
+ bitset_stats_disjoint_p,
+ bitset_stats_equal_p,
+ bitset_stats_not,
+ bitset_stats_subset_p,
+ bitset_stats_and,
+ bitset_stats_and_cmp,
+ bitset_stats_andn,
+ bitset_stats_andn_cmp,
+ bitset_stats_or,
+ bitset_stats_or_cmp,
+ bitset_stats_xor,
+ bitset_stats_xor_cmp,
+ bitset_stats_and_or,
+ bitset_stats_and_or_cmp,
+ bitset_stats_andn_or,
+ bitset_stats_andn_or_cmp,
+ bitset_stats_or_and,
+ bitset_stats_or_and_cmp,
bitset_stats_list,
- bitset_stats_reverse_list,
+ bitset_stats_list_reverse,
bitset_stats_free,
BITSET_STATS
};
unsigned int bytes;
bitset sbset;
- bset->b.ops = &bitset_stats_ops;
+ bset->b.vtable = &bitset_stats_vtable;
/* Disable cache. */
bset->b.cindex = 0;
/* Bitset vectors.
- Copyright (C) 2001 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002 Free Software Foundation, Inc.
This file is part of GCC.
*ebitset;
+typedef void(*PFV)();
+
+
/* Number of elements to initially allocate. */
#ifndef EBITSET_INITIAL_SIZE
static int ebitset_weed PARAMS ((bitset));
static void ebitset_zero PARAMS ((bitset));
-static int ebitset_equal_p PARAMS ((bitset, bitset));
-static void ebitset_copy PARAMS ((bitset, bitset));
-static int ebitset_copy_compare PARAMS ((bitset, bitset));
+static void ebitset_copy_ PARAMS ((bitset, bitset));
+static int ebitset_copy_cmp PARAMS ((bitset, bitset));
static void ebitset_set PARAMS ((bitset, bitset_bindex));
static void ebitset_reset PARAMS ((bitset, bitset_bindex));
static int ebitset_test PARAMS ((bitset, bitset_bindex));
static int ebitset_size PARAMS ((bitset));
-static int ebitset_op1 PARAMS ((bitset, enum bitset_ops));
-static int ebitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
-static int ebitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
+static int ebitset_disjoint_p PARAMS ((bitset, bitset));
+static int ebitset_equal_p PARAMS ((bitset, bitset));
+static void ebitset_not PARAMS ((bitset, bitset));
+static int ebitset_subset_p PARAMS ((bitset, bitset));
+static int ebitset_op3_cmp PARAMS ((bitset, bitset, bitset, enum bitset_ops));
+static int ebitset_and_cmp PARAMS ((bitset, bitset, bitset));
+static int ebitset_andn_cmp PARAMS ((bitset, bitset, bitset));
+static int ebitset_or_cmp PARAMS ((bitset, bitset, bitset));
+static int ebitset_xor_cmp PARAMS ((bitset, bitset, bitset));
static int ebitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
bitset_bindex *));
-static int ebitset_reverse_list
+static int ebitset_list_reverse
PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
static void ebitset_free PARAMS ((bitset));
#define EBITSET_WORDS(ELT) ((ELT)->u.words)
/* Disable bitset cache and mark BSET as being zero. */
-#define EBITSET_OP_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX, \
+#define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX, \
(BSET)->b.cdata = 0)
#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX)
/* A conservative estimate of whether the bitset is zero.
This is non-zero only if we know for sure that the bitset is zero. */
-#define EBITSET_OP_ZERO_P(BSET) ((BSET)->b.cdata == 0)
+#define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
/* Enable cache to point to element with table index EINDEX.
The element must exist. */
bitset_windex j;
int count;
- if (EBITSET_OP_ZERO_P (bset))
+ if (EBITSET_ZERO_P (bset))
return 0;
elts = EBITSET_ELTS (bset);
{
/* All the bits are zero. We could shrink the elts.
For now just mark BSET as known to be zero. */
- EBITSET_OP_ZERO_SET (bset);
+ EBITSET_ZERO_SET (bset);
}
else
EBITSET_NONZERO_SET (bset);
ebitset_elts *elts;
bitset_windex j;
- if (EBITSET_OP_ZERO_P (bset))
+ if (EBITSET_ZERO_P (bset))
return;
elts = EBITSET_ELTS (bset);
/* All the bits are zero. We could shrink the elts.
For now just mark BSET as known to be zero. */
- EBITSET_OP_ZERO_SET (bset);
+ EBITSET_ZERO_SET (bset);
}
/* Copy bits from bitset SRC to bitset DST. */
static inline void
-ebitset_copy (dst, src)
+ebitset_copy_ (dst, src)
bitset dst;
bitset src;
{
/* Copy bits from bitset SRC to bitset DST. Return non-zero if
bitsets different. */
static inline int
-ebitset_copy_compare (dst, src)
+ebitset_copy_cmp (dst, src)
bitset dst;
bitset src;
{
if (src == dst)
return 0;
- if (EBITSET_OP_ZERO_P (dst))
+ if (EBITSET_ZERO_P (dst))
{
- ebitset_copy (dst, src);
- return !EBITSET_OP_ZERO_P (src);
+ ebitset_copy_ (dst, src);
+ return !EBITSET_ZERO_P (src);
}
if (ebitset_equal_p (dst, src))
return 0;
- ebitset_copy (dst, src);
+ ebitset_copy_ (dst, src);
return 1;
}
*NEXT and store in array LIST. Return with actual number of bits
found and with *NEXT indicating where search stopped. */
static int
-ebitset_reverse_list (bset, list, num, next)
+ebitset_list_reverse (bset, list, num, next)
bitset bset;
bitset_bindex *list;
bitset_bindex num;
bitset_windex size;
ebitset_elts *elts;
- if (EBITSET_OP_ZERO_P (bset))
+ if (EBITSET_ZERO_P (bset))
return 0;
size = EBITSET_SIZE (bset);
do
{
ebitset_elt *elt;
-
+ bitset_word *srcp;
+
elt = elts[eindex];
if (elt)
- {
- bitset_word *srcp;
-
+ {
srcp = EBITSET_WORDS (elt);
-
+
do
{
bitset_word word;
-
+
word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
-
+
for (; word; bcount--)
{
if (word & BITSET_MSB)
}
word <<= 1;
}
-
boffset -= BITSET_WORD_BITS;
- bcount = BITSET_WORD_BITS - 1;
+ bcount = BITSET_WORD_BITS - 1;
}
while (woffset--);
-
- woffset = EBITSET_ELT_WORDS;
}
+ woffset = EBITSET_ELT_WORDS - 1;
boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
}
while (eindex--);
bitset_word word;
ebitset_elts *elts;
- if (EBITSET_OP_ZERO_P (bset))
+ if (EBITSET_ZERO_P (bset))
return 0;
bitno = *next;
}
-static int
-ebitset_op1 (dst, op)
+static void
+ebitset_ones (dst)
bitset dst;
- enum bitset_ops op;
{
bitset_windex j;
ebitset_elt *elt;
- switch (op)
- {
- case BITSET_OP_ZERO:
- ebitset_zero (dst);
- return 1;
-
- case BITSET_OP_ONES:
- for (j = 0; j < EBITSET_SIZE (dst); j++)
- {
- /* Create new elements if they cannot be found. Perhaps
- we should just add pointers to a ones element. */
- elt =
- ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
- memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
- }
- break;
-
- case BITSET_OP_EMPTY_P:
- return !ebitset_weed (dst);
- default:
- abort ();
+ for (j = 0; j < EBITSET_SIZE (dst); j++)
+ {
+ /* Create new elements if they cannot be found. Perhaps
+ we should just add pointers to a ones element. */
+ elt =
+ ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
+ memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
}
-
EBITSET_NONZERO_SET (dst);
- return 1;
}
static int
-ebitset_op2 (dst, src, op)
+ebitset_empty_p (dst)
+ bitset dst;
+{
+ return !ebitset_weed (dst);
+}
+
+
+static void
+ebitset_not (dst, src)
bitset dst;
bitset src;
- enum bitset_ops op;
{
+ unsigned int i;
ebitset_elt *selt;
ebitset_elt *delt;
- unsigned int i;
bitset_windex j;
- switch (op)
+ for (j = 0; j < EBITSET_SIZE (src); j++)
{
- case BITSET_OP_COPY:
- ebitset_copy (dst, src);
- break;
-
- case BITSET_OP_NOT:
- for (j = 0; j < EBITSET_SIZE (src); j++)
- {
- /* Create new elements for dst if they cannot be found
+ /* Create new elements for dst if they cannot be found
or substitute zero elements if src elements not found. */
- selt =
- ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
- delt =
- ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
+ selt =
+ ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
+ delt =
+ ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
- for (i = 0; i < EBITSET_ELT_WORDS; i++)
- EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
- }
- break;
-
- /* Return 1 if DST == SRC. */
- case BITSET_OP_EQUAL_P:
- return ebitset_equal_p (dst, src);
-
- /* Return 1 if DST == DST | SRC. */
- case BITSET_OP_SUBSET_P:
- {
- ebitset_elts *selts;
- ebitset_elts *delts;
- bitset_windex ssize;
- bitset_windex dsize;
-
- selts = EBITSET_ELTS (src);
- delts = EBITSET_ELTS (dst);
-
- ssize = EBITSET_SIZE (src);
- dsize = EBITSET_SIZE (dst);
-
- for (j = 0; j < ssize; j++)
- {
- selt = j < ssize ? selts[j] : 0;
- delt = j < dsize ? delts[j] : 0;
-
- 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 (delt)[i]
- != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
- return 0;
- }
- return 1;
- }
- break;
-
- /* Return 1 if DST & SRC == 0. */
- case BITSET_OP_DISJOINT_P:
- {
- ebitset_elts *selts;
- ebitset_elts *delts;
- bitset_windex ssize;
- bitset_windex dsize;
-
- selts = EBITSET_ELTS (src);
- delts = EBITSET_ELTS (dst);
-
- ssize = EBITSET_SIZE (src);
- dsize = EBITSET_SIZE (dst);
-
- for (j = 0; j < ssize; j++)
- {
- selt = j < ssize ? selts[j] : 0;
- delt = j < dsize ? delts[j] : 0;
-
- if (!selt || !delt)
- continue;
-
- for (i = 0; i < EBITSET_ELT_WORDS; i++)
- if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
- return 0;
- }
- return 1;
- }
- break;
+ for (i = 0; i < EBITSET_ELT_WORDS; i++)
+ EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
+ }
+ EBITSET_NONZERO_SET (dst);
+}
- default:
- abort ();
+
+/* Return 1 if DST == DST | SRC. */
+static int
+ebitset_subset_p (dst, src)
+ bitset dst;
+ bitset src;
+{
+ bitset_windex j;
+ ebitset_elts *selts;
+ ebitset_elts *delts;
+ bitset_windex ssize;
+ bitset_windex dsize;
+
+ selts = EBITSET_ELTS (src);
+ delts = EBITSET_ELTS (dst);
+
+ ssize = EBITSET_SIZE (src);
+ dsize = EBITSET_SIZE (dst);
+
+ for (j = 0; j < ssize; j++)
+ {
+ unsigned int i;
+ ebitset_elt *selt;
+ ebitset_elt *delt;
+
+ selt = j < ssize ? selts[j] : 0;
+ delt = j < dsize ? delts[j] : 0;
+
+ 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 (delt)[i]
+ != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
+ return 0;
}
+ return 1;
+}
- EBITSET_NONZERO_SET (dst);
+
+/* Return 1 if DST & SRC == 0. */
+static int
+ebitset_disjoint_p (dst, src)
+ bitset dst;
+ bitset src;
+{
+ bitset_windex j;
+ ebitset_elts *selts;
+ ebitset_elts *delts;
+ bitset_windex ssize;
+ bitset_windex dsize;
+
+ selts = EBITSET_ELTS (src);
+ delts = EBITSET_ELTS (dst);
+
+ ssize = EBITSET_SIZE (src);
+ dsize = EBITSET_SIZE (dst);
+
+ for (j = 0; j < ssize; j++)
+ {
+ unsigned int i;
+ ebitset_elt *selt;
+ ebitset_elt *delt;
+
+ selt = j < ssize ? selts[j] : 0;
+ delt = j < dsize ? delts[j] : 0;
+
+ if (!selt || !delt)
+ continue;
+
+ for (i = 0; i < EBITSET_ELT_WORDS; i++)
+ if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
+ return 0;
+ }
return 1;
}
+
static int
-ebitset_op3 (dst, src1, src2, op)
+ebitset_op3_cmp (dst, src1, src2, op)
bitset dst;
bitset src1;
bitset src2;
unsigned int i;
bitset_windex j;
- /* Fast track common, simple cases. */
- if (EBITSET_OP_ZERO_P (src2))
- {
- if (op == BITSET_OP_AND)
- {
- ebitset_weed (dst);
- changed = EBITSET_OP_ZERO_P (dst);
- ebitset_zero (dst);
- return changed;
- }
- else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR
- || op == BITSET_OP_XOR)
- {
- return ebitset_copy_compare (dst, src1);
- }
- }
- else if (EBITSET_OP_ZERO_P (src1))
- {
- if (op == BITSET_OP_AND || op == BITSET_OP_ANDN)
- {
- ebitset_weed (dst);
- changed = EBITSET_OP_ZERO_P (dst);
- ebitset_zero (dst);
- return changed;
- }
- else if (op == BITSET_OP_OR || op == BITSET_OP_XOR)
- {
- return ebitset_copy_compare (dst, src2);
- }
- }
-
ssize1 = EBITSET_SIZE (src1);
ssize2 = EBITSET_SIZE (src2);
dsize = EBITSET_SIZE (dst);
}
+static int
+ebitset_and_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ int changed;
+
+ if (EBITSET_ZERO_P (src2))
+ {
+ ebitset_weed (dst);
+ changed = EBITSET_ZERO_P (dst);
+ ebitset_zero (dst);
+ return changed;
+ }
+ else if (EBITSET_ZERO_P (src1))
+ {
+ ebitset_weed (dst);
+ changed = EBITSET_ZERO_P (dst);
+ ebitset_zero (dst);
+ return changed;
+ }
+ return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
+}
+
+
+static int
+ebitset_andn_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ int changed;
+
+ if (EBITSET_ZERO_P (src2))
+ {
+ return ebitset_copy_cmp (dst, src1);
+ }
+ else if (EBITSET_ZERO_P (src1))
+ {
+ ebitset_weed (dst);
+ changed = EBITSET_ZERO_P (dst);
+ ebitset_zero (dst);
+ return changed;
+ }
+ return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
+}
+
+
+static int
+ebitset_or_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ if (EBITSET_ZERO_P (src2))
+ {
+ return ebitset_copy_cmp (dst, src1);
+ }
+ else if (EBITSET_ZERO_P (src1))
+ {
+ return ebitset_copy_cmp (dst, src2);
+ }
+ return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
+}
+
+
+static int
+ebitset_xor_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ if (EBITSET_ZERO_P (src2))
+ {
+ return ebitset_copy_cmp (dst, src1);
+ }
+ else if (EBITSET_ZERO_P (src1))
+ {
+ return ebitset_copy_cmp (dst, src2);
+ }
+ return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
+}
+
+
+static void
+ebitset_copy (dst, src)
+ bitset dst;
+ bitset src;
+{
+ if (BITSET_COMPATIBLE_ (dst, src))
+ ebitset_copy_ (dst, src);
+ else
+ bitset_copy_ (dst, src);
+}
+
+
/* Vector of operations for linked-list bitsets. */
-struct bitset_ops_struct ebitset_ops = {
+struct bitset_vtable ebitset_vtable = {
ebitset_set,
ebitset_reset,
+ bitset_toggle_,
ebitset_test,
ebitset_size,
- ebitset_op1,
- ebitset_op2,
- ebitset_op3,
- bitset_op4,
+ bitset_count_,
+ ebitset_empty_p,
+ ebitset_ones,
+ ebitset_zero,
+ ebitset_copy,
+ ebitset_disjoint_p,
+ ebitset_equal_p,
+ ebitset_not,
+ ebitset_subset_p,
+ (PFV) ebitset_and_cmp,
+ ebitset_and_cmp,
+ (PFV) ebitset_andn_cmp,
+ ebitset_andn_cmp,
+ (PFV) ebitset_or_cmp,
+ ebitset_or_cmp,
+ (PFV) ebitset_xor_cmp,
+ ebitset_xor_cmp,
+ (PFV) bitset_and_or_cmp_,
+ bitset_and_or_cmp_,
+ (PFV) bitset_andn_or_cmp_,
+ bitset_andn_or_cmp_,
+ (PFV) bitset_or_and_cmp_,
+ bitset_or_and_cmp_,
ebitset_list,
- ebitset_reverse_list,
+ ebitset_list_reverse,
ebitset_free,
BITSET_TABLE
};
{
unsigned int size;
- bset->b.ops = &ebitset_ops;
+ bset->b.vtable = &ebitset_vtable;
bset->b.csize = EBITSET_ELT_WORDS;
- EBITSET_OP_ZERO_SET (bset);
+ EBITSET_ZERO_SET (bset);
size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
: EBITSET_INITIAL_SIZE;
#include "lbitset.h"
#include "obstack.h"
#include <stdlib.h>
+#include <stdio.h>
/* This file implements linked-list bitsets. These bitsets can be of
arbitrary length and are more efficient than arrays of bits for
};
+typedef void(*PFV)();
+
+
enum lbitset_find_mode
{ LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
static void lbitset_zero PARAMS ((bitset));
static int lbitset_equal_p PARAMS ((bitset, bitset));
static void lbitset_copy PARAMS ((bitset, bitset));
-static int lbitset_copy_compare PARAMS ((bitset, bitset));
+static int lbitset_copy_cmp PARAMS ((bitset, bitset));
static void lbitset_set PARAMS ((bitset, bitset_bindex));
static void lbitset_reset PARAMS ((bitset, bitset_bindex));
static int lbitset_test PARAMS ((bitset, bitset_bindex));
static int lbitset_size PARAMS ((bitset));
-static int lbitset_op1 PARAMS ((bitset, enum bitset_ops));
-static int lbitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
-static int lbitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
+static int lbitset_op3_cmp PARAMS ((bitset, bitset, bitset, enum bitset_ops));
static int lbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
bitset_bindex *));
-static int lbitset_reverse_list
+static int lbitset_list_reverse
PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
static void lbitset_free PARAMS ((bitset));
continue;
}
- /* `element' is the nearest to the one we want. If it's not the one
+ /* ELT 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 && (windex - elt->index) < LBITSET_ELT_WORDS)
{
/* Set all bits in the bitset to zero. */
-static inline void
+static void
lbitset_zero (bset)
bitset bset;
{
}
+/* Return 1 if DST == SRC. */
static inline int
lbitset_equal_p (dst, src)
bitset dst;
/* Copy bits from bitset SRC to bitset DST. Return non-zero if
bitsets different. */
static inline int
-lbitset_copy_compare (dst, src)
+lbitset_copy_cmp (dst, src)
bitset dst;
bitset src;
{
*NEXT and store in array LIST. Return with actual number of bits
found and with *NEXT indicating where search stopped. */
static int
-lbitset_reverse_list (bset, list, num, next)
+lbitset_list_reverse (bset, list, num, next)
bitset bset;
bitset_bindex *list;
bitset_bindex num;
if (!elt)
return 0;
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
+ if (windex >= elt->index + LBITSET_ELT_WORDS)
+ {
+ /* We are trying to start in no-mans land so start
+ at end of current elt. */
+ bcount = BITSET_WORD_BITS - 1;
+ windex = elt->index + LBITSET_ELT_WORDS - 1;
+ }
+ else
+ {
+ bcount = bitno % BITSET_WORD_BITS;
+ }
count = 0;
- bcount = bitno % BITSET_WORD_BITS;
boffset = windex * BITSET_WORD_BITS;
+ /* If num is 1, we could speed things up with a binary search
+ of the word of interest. */
+
while (elt)
{
bitset_word *srcp = elt->words;
static int
-lbitset_op1 (dst, op)
+lbitset_empty_p (dst)
+ bitset dst;
+{
+ lbitset_weed (dst);
+ if (LBITSET_HEAD (dst))
+ return 0;
+ return 1;
+}
+
+
+static void
+lbitset_ones (dst)
bitset dst;
- enum bitset_ops op;
{
unsigned int i;
bitset_windex windex;
lbitset_elt *elt;
- switch (op)
+ /* This is a decidedly unfriendly operation for a linked list
+ bitset! It makes a sparse bitset become dense. An alternative
+ is to have a flag that indicates that the bitset stores the
+ complement of what it indicates. */
+ elt = LBITSET_TAIL (dst);
+ /* Ignore empty set. */
+ if (!elt)
+ return;
+
+ windex = elt->index;
+ for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
{
- case BITSET_OP_ZERO:
- lbitset_zero (dst);
- break;
-
- case BITSET_OP_ONES:
- /* This is a decidedly unfriendly operation for a linked list
- bitset! */
- elt = LBITSET_TAIL (dst);
- /* Ignore empty set. */
- if (!elt)
- return 0;
-
- 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);
- memset (elt->words, -1, sizeof (elt->words));
- }
- break;
-
- case BITSET_OP_EMPTY_P:
- lbitset_weed (dst);
- if (LBITSET_HEAD (dst))
- return 0;
- break;
-
- default:
- abort ();
+ /* Create new elements if they cannot be found. */
+ elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+ memset (elt->words, -1, sizeof (elt->words));
}
-
- return 1;
}
-static int
-lbitset_op2 (dst, src, op)
+static void
+lbitset_not (dst, src)
bitset dst;
bitset src;
- enum bitset_ops op;
{
lbitset_elt *elt;
lbitset_elt *selt;
unsigned int j;
bitset_windex windex;
- switch (op)
+ /* This is another unfriendly operation for a linked list
+ bitset! */
+ elt = LBITSET_TAIL (dst);
+ /* Ignore empty set. */
+ if (!elt)
+ return;
+
+ windex = elt->index;
+ for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
{
- case BITSET_OP_COPY:
- lbitset_copy (dst, src);
- break;
-
- case BITSET_OP_NOT:
- /* This is another unfriendly operation for a linked list
- bitset! */
- elt = LBITSET_TAIL (dst);
- /* Ignore empty set. */
- if (!elt)
- return 0;
-
- 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. */
- selt = lbitset_elt_find (dst, i, LBITSET_SUBST);
- delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+ /* Create new elements for dst if they cannot be found
+ or substitute zero elements if src elements not found. */
+ selt = lbitset_elt_find (src, i, LBITSET_SUBST);
+ delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+
+ for (j = 0; j < LBITSET_ELT_WORDS; j++)
+ delt->words[j] = ~selt->words[j];
+ }
+ lbitset_weed (dst);
+ return;
+}
- for (j = 0; j < LBITSET_ELT_WORDS; j++)
- delt->words[j] = ~selt->words[j];
- }
- lbitset_weed (dst);
- break;
- /* Return 1 if DST == SRC. */
- case BITSET_OP_EQUAL_P:
- return lbitset_equal_p (dst, src);
- break;
+/* Return 1 if DST == DST | SRC. */
+static int
+lbitset_subset_p (dst, src)
+ bitset dst;
+ bitset src;
+{
+ lbitset_elt *selt;
+ lbitset_elt *delt;
+ unsigned int j;
- /* Return 1 if DST == DST | SRC. */
- case BITSET_OP_SUBSET_P:
- for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
- selt || delt; selt = selt->next, delt = delt->next)
+ for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
+ selt || delt; selt = selt->next, delt = delt->next)
+ {
+ if (!selt)
+ selt = &lbitset_zero_elts[0];
+ else if (!delt)
+ delt = &lbitset_zero_elts[0];
+ else if (selt->index != delt->index)
{
- if (!selt)
- selt = &lbitset_zero_elts[0];
- else if (!delt)
- delt = &lbitset_zero_elts[0];
- else if (selt->index != delt->index)
+ if (selt->index < delt->index)
{
- if (selt->index < delt->index)
- {
- lbitset_zero_elts[2].next = delt;
- delt = &lbitset_zero_elts[2];
- }
- else
- {
- lbitset_zero_elts[1].next = selt;
- selt = &lbitset_zero_elts[1];
- }
+ lbitset_zero_elts[2].next = delt;
+ delt = &lbitset_zero_elts[2];
+ }
+ else
+ {
+ lbitset_zero_elts[1].next = selt;
+ selt = &lbitset_zero_elts[1];
}
-
- for (j = 0; j < LBITSET_ELT_WORDS; j++)
- if (delt->words[j] != (selt->words[j] | delt->words[j]))
- return 0;
}
- break;
+
+ for (j = 0; j < LBITSET_ELT_WORDS; j++)
+ if (delt->words[j] != (selt->words[j] | delt->words[j]))
+ return 0;
+ }
+ return 1;
+}
+
- /* Return 1 if DST & SRC == 0. */
- case BITSET_OP_DISJOINT_P:
- for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
- selt && delt; selt = selt->next, delt = delt->next)
+/* Return 1 if DST & SRC == 0. */
+static int
+lbitset_disjoint_p (dst, src)
+ bitset dst;
+ bitset src;
+{
+ lbitset_elt *selt;
+ lbitset_elt *delt;
+ unsigned int j;
+
+ for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
+ selt && delt; selt = selt->next, delt = delt->next)
+ {
+ if (selt->index != delt->index)
{
- if (selt->index != delt->index)
+ if (selt->index < delt->index)
{
- if (selt->index < delt->index)
- {
- lbitset_zero_elts[2].next = delt;
- delt = &lbitset_zero_elts[2];
- }
- else
- {
- lbitset_zero_elts[1].next = selt;
- selt = &lbitset_zero_elts[1];
- }
- /* Since the elements are different, there is no
- intersection of these elements. */
- continue;
+ lbitset_zero_elts[2].next = delt;
+ delt = &lbitset_zero_elts[2];
}
-
- for (j = 0; j < LBITSET_ELT_WORDS; j++)
- if (selt->words[j] & delt->words[j])
- return 0;
+ else
+ {
+ lbitset_zero_elts[1].next = selt;
+ selt = &lbitset_zero_elts[1];
+ }
+ /* Since the elements are different, there is no
+ intersection of these elements. */
+ continue;
}
- break;
-
- default:
- abort ();
+
+ for (j = 0; j < LBITSET_ELT_WORDS; j++)
+ if (selt->words[j] & delt->words[j])
+ return 0;
}
-
return 1;
}
static int
-lbitset_op3 (dst, src1, src2, op)
+lbitset_op3_cmp (dst, src1, src2, op)
bitset dst;
bitset src1;
bitset src2;
int changed = 0;
unsigned int i;
- /* Fast track common, simple cases. */
- if (!selt2)
- {
- if (op == BITSET_OP_AND)
- {
- lbitset_weed (dst);
- changed = !LBITSET_HEAD (dst);
- lbitset_zero (dst);
- return changed;
- }
- else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR
- || op == BITSET_OP_XOR)
- {
- return lbitset_copy_compare (dst, src1);
- }
- }
- else if (!selt1)
- {
- if (op == BITSET_OP_AND || op == BITSET_OP_ANDN)
- {
- lbitset_weed (dst);
- changed = !LBITSET_HEAD (dst);
- lbitset_zero (dst);
- return changed;
- }
- else if (op == BITSET_OP_OR || op == BITSET_OP_XOR)
- {
- return lbitset_copy_compare (dst, src2);
- }
- }
-
LBITSET_HEAD (dst) = 0;
dst->b.csize = 0;
}
+static int
+lbitset_and_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ lbitset_elt *selt1 = LBITSET_HEAD (src1);
+ lbitset_elt *selt2 = LBITSET_HEAD (src2);
+ int changed;
+
+ if (!selt2)
+ {
+ lbitset_weed (dst);
+ changed = !LBITSET_HEAD (dst);
+ lbitset_zero (dst);
+ return changed;
+ }
+ else if (!selt1)
+ {
+ lbitset_weed (dst);
+ changed = !LBITSET_HEAD (dst);
+ lbitset_zero (dst);
+ return changed;
+ }
+ return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
+}
+
+
+static int
+lbitset_andn_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ lbitset_elt *selt1 = LBITSET_HEAD (src1);
+ lbitset_elt *selt2 = LBITSET_HEAD (src2);
+ int changed;
+
+ if (!selt2)
+ {
+ return lbitset_copy_cmp (dst, src1);
+ }
+ else if (!selt1)
+ {
+ lbitset_weed (dst);
+ changed = !LBITSET_HEAD (dst);
+ lbitset_zero (dst);
+ return changed;
+ }
+ return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
+}
+
+
+static int
+lbitset_or_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ lbitset_elt *selt1 = LBITSET_HEAD (src1);
+ lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+ if (!selt2)
+ {
+ return lbitset_copy_cmp (dst, src1);
+ }
+ else if (!selt1)
+ {
+ return lbitset_copy_cmp (dst, src2);
+ }
+ return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
+}
+
+
+static int
+lbitset_xor_cmp (dst, src1, src2)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+{
+ lbitset_elt *selt1 = LBITSET_HEAD (src1);
+ lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+ if (!selt2)
+ {
+ return lbitset_copy_cmp (dst, src1);
+ }
+ else if (!selt1)
+ {
+ return lbitset_copy_cmp (dst, src2);
+ }
+ return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
+}
+
+
+
/* Vector of operations for linked-list bitsets. */
-struct bitset_ops_struct lbitset_ops = {
+struct bitset_vtable lbitset_vtable = {
lbitset_set,
lbitset_reset,
+ bitset_toggle_,
lbitset_test,
lbitset_size,
- lbitset_op1,
- lbitset_op2,
- lbitset_op3,
- bitset_op4,
+ bitset_count_,
+ lbitset_empty_p,
+ lbitset_ones,
+ lbitset_zero,
+ lbitset_copy,
+ lbitset_disjoint_p,
+ lbitset_equal_p,
+ lbitset_not,
+ lbitset_subset_p,
+ (PFV) lbitset_and_cmp,
+ lbitset_and_cmp,
+ (PFV) lbitset_andn_cmp,
+ lbitset_andn_cmp,
+ (PFV) lbitset_or_cmp,
+ lbitset_or_cmp,
+ (PFV) lbitset_xor_cmp,
+ lbitset_xor_cmp,
+ (PFV) bitset_and_or_cmp_,
+ bitset_and_or_cmp_,
+ (PFV) bitset_andn_or_cmp_,
+ bitset_andn_or_cmp_,
+ (PFV) bitset_or_and_cmp_,
+ bitset_or_and_cmp_,
lbitset_list,
- lbitset_reverse_list,
+ lbitset_list_reverse,
lbitset_free,
BITSET_LIST
};
/* Initialize a bitset. */
-
bitset
lbitset_init (bset, n_bits)
bitset bset;
bitset_bindex n_bits ATTRIBUTE_UNUSED;
{
- bset->b.ops = &lbitset_ops;
+ bset->b.vtable = &lbitset_vtable;
return bset;
}
obstack_free (&lbitset_obstack, NULL);
}
}
+
+
+/* Function to be called from debugger to debug lbitset. */
+void
+debug_lbitset (bset)
+ bitset bset;
+{
+ lbitset_elt *elt;
+ unsigned int i;
+
+ if (!bset)
+ return;
+
+ for (elt = LBITSET_HEAD (bset); elt; elt = elt->next)
+ {
+ fprintf (stderr, "Elt %d\n", elt->index);
+ for (i = 0; i < LBITSET_ELT_WORDS; i++)
+ {
+ unsigned int j;
+ bitset_word word;
+
+ word = elt->words[i];
+
+ fprintf (stderr, " Word %d:", i);
+ for (j = 0; j < LBITSET_WORD_BITS; j++)
+ if ((word & (1 << j)))
+ fprintf (stderr, " %d", j);
+ fprintf (stderr, "\n");
+ }
+ }
+}
projects / bison.git / commitdiff
