[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
22-fyi-update-bitset.patch
|
From: |
Akim Demaille |
|
Subject: |
22-fyi-update-bitset.patch |
|
Date: |
Mon, 04 Mar 2002 13:06:46 +0100 |
Index: ChangeLog
from Akim Demaille <address@hidden>
* lib/bitset.c, lib/bitset.h, lib/bitsetv.c, lib/bitsetv.h,
* lib/ebitset.c, lib/ebitset.h, lib/lbitset.c, lib/lbitset.h,
* lib/sbitset.c, lib/sbitset.h, lib/bbitset.h: Update from the
latest sources from Michael.
Index: lib/Makefile.am
--- lib/Makefile.am Mon, 04 Feb 2002 23:18:59 +0100 akim
+++ lib/Makefile.am Sun, 03 Mar 2002 11:45:44 +0100 akim
@@ -44,6 +44,7 @@
# Implementation of bitsets
libbison_a_SOURCES += \
+ bbitset.h \
bitset-int.h bitset.h bitsetv.h ebitset.h lbitset.h sbitset.h \
bitset.c bitsetv.c ebitset.c lbitset.c sbitset.c
Index: lib/bitset.c
--- lib/bitset.c Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/bitset.c Sun, 03 Mar 2002 11:35:00 +0100 akim
@@ -2,19 +2,19 @@
Copyright (C) 2002 Free Software Foundation, Inc.
Contributed by Michael Hayes (address@hidden).
-This program is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2 of the License, or
-(at your option) any later version.
-
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with this program; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
@@ -22,28 +22,13 @@
#include <stdlib.h>
#include "bitset.h"
+#include "sbitset.h"
+#include "lbitset.h"
+#include "ebitset.h"
#include "obstack.h"
static void bitset_print PARAMS ((FILE *, bitset, int));
-#if BITSET_CHECK
-#define BITSET__CHECK2(DST, SRC) \
-if ((DST)->OPS != (SRC)->OPS) abort ();
-
-#define BITSET__CHECK3(DST, SRC1, SRC2) \
-if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS) abort ();
-
-#define BITSET__CHECK4(DST, SRC1, SRC2) \
-if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS \
- || (DST)->OPS != (SRC3)->OPS) abort ();
-#else
-#define BITSET__CHECK2(DST, SRC)
-
-#define BITSET__CHECK3(DST, SRC1, SRC2)
-
-#define BITSET__CHECK4(DST, SRC1, SRC2, SRC3)
-#endif
-
#if BITSET_STATS
#define BITSET_STATS_FILE "bitset.dat"
@@ -65,8 +50,8 @@
struct bitset_stats_struct
{
- unsigned int runs;
- struct bitset_type_stats_struct types[BITSET_TYPE_NUM];
+ unsigned int runs;
+ struct bitset_type_stats_struct types[BITSET_TYPE_NUM];
};
struct bitset_stats_struct bitset_stats_data;
@@ -78,9 +63,10 @@
unsigned int *));
static void bitset_log_histogram_print PARAMS ((FILE *, const char *,
const char *,
- unsigned int, unsigned int *));
-static void bitset_stats_print_1 PARAMS ((FILE *, const char *,
- struct bitset_type_stats_struct *));
+ unsigned int,
+ unsigned int *));
+static void bitset_stats_print_1
+PARAMS ((FILE *, const char *, struct bitset_type_stats_struct *));
static void bitset_stats_print PARAMS ((FILE *, int));
static void bitset_stats_read PARAMS ((void));
static void bitset_stats_write PARAMS ((void));
@@ -91,31 +77,31 @@
#define BITSET_STATS_XFREES_INC(BSET) \
if (bitset_stats) \
- bitset_stats->types[(BSET)->ops->type].xfrees++
+ bitset_stats->types[BITSET_TYPE_ (BSET)].xfrees++
#define BITSET_STATS_OBALLOCS_INC(TYPE) \
if (bitset_stats) \
bitset_stats->types[(TYPE)].oballocs++
-#define BITSET_STATS_OBFREES_INC(BSET) \
+#define BITSET_STATS_OBFREES_INC(BSET) \
if (bitset_stats) \
- bitset_stats->types[(BSET)->ops->type].obfrees++
+ bitset_stats->types[BITSET_TYPE_ (BSET)].obfrees++
#define BITSET_STATS_LISTS_INC(BSET) \
if (bitset_stats) \
- bitset_stats->types[(BSET)->ops->type].lists++
+ bitset_stats->types[BITSET_TYPE_ (BSET)].lists++
#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \
if (bitset_stats) \
- bitset_stats->types[(BSET)->ops->type].list_counts[(I)]++
+ bitset_stats->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++
#define BITSET_STATS_LIST_SIZES_INC(BSET, I) \
if (bitset_stats) \
- bitset_stats->types[(BSET)->ops->type].list_sizes[(I)]++
+ bitset_stats->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++
#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \
if (bitset_stats) \
- bitset_stats->types[(BSET)->ops->type].list_density[(I)]++
+ bitset_stats->types[BITSET_TYPE_ (BSET)].list_density[(I)]++
#else
#define BITSET_STATS_XMALLOCS_INC(TYPE)
@@ -136,7 +122,6 @@
#endif /* BITSET_STATS */
-
/* Return number of bytes required to create a N_BIT bitset
of TYPE. The bitset may grow to require more bytes than this. */
int
@@ -202,7 +187,7 @@
{
enum bitset_type type;
-#ifdef ENABLE_CHECKING
+#if BITSET_CHECK
/* Check attributes. */
if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
abort ();
@@ -241,7 +226,11 @@
bytes = bitset_bytes (type, n_bits);
- bset = (bitset) xmalloc (bytes);
+ bset = (bitset) xcalloc (1, bytes);
+
+ /* The cache is disabled until some elements are allocated. If we
+ have variable length arrays, then we may need to allocate dummy
+ element. */
return bitset_init (bset, n_bits, type);
}
@@ -250,17 +239,21 @@
/* Create a bitset of N_BITS of type TYPE. */
bitset
bitset_obstack_alloc (bobstack, n_bits, type)
- struct obstack *bobstack;
- bitset_bindex n_bits;
- enum bitset_type type;
+ struct obstack *bobstack;
+ bitset_bindex n_bits;
+ enum bitset_type type;
{
unsigned int bytes;
+ bitset bset;
BITSET_STATS_OBALLOCS_INC (type);
bytes = bitset_bytes (type, n_bits);
- return bitset_init (obstack_alloc (bobstack, bytes), n_bits, type);
+ bset = obstack_alloc (bobstack, bytes);
+ memset (bset, 0, bytes);
+
+ return bitset_init (bset, n_bits, type);
}
@@ -286,10 +279,7 @@
{
BITSET_STATS_XFREES_INC (bset);
- if (bset->ops->free)
- BITSET__FREE (bset);
-
- bset->ops = NULL;
+ BITSET_FREE_ (bset);
free (bset);
}
@@ -301,9 +291,7 @@
{
BITSET_STATS_OBFREES_INC (bset);
- if (bset->ops->free)
- BITSET__FREE (bset);
- bset->ops = NULL;
+ BITSET_FREE_ (bset);
}
@@ -357,6 +345,7 @@
}
+/* Print contents of bitset BSET to FILE. */
static void
bitset_print (file, bset, verbose)
FILE *file;
@@ -386,153 +375,225 @@
}
+/* DST = SRC. Return non-zero if DST != SRC. */
int
bitset_copy (dst, src)
- bitset dst;
- bitset src;
+ bitset dst;
+ bitset src;
{
- unsigned int i;
+ unsigned int i;
- if (dst->ops == src->ops)
- return BITSET__COPY (dst, src);
+ 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_EXECUTE (src, 0, i,
- {
- bitset_set (dst, i);
- });
+ /* Convert bitset types. We assume that the DST bitset
+ is large enough to hold the SRC bitset. */
+ bitset_zero (dst);
+ BITSET_EXECUTE (src, 0, i,
+ {
+ bitset_set (dst, i);
+ });
- return 1;
+ return 1;
}
/* Return size in bits of bitset SRC. */
int
bitset_size (src)
- bitset src;
+ bitset src;
+{
+ return BITSET_SIZE_ (src);
+}
+
+
+/* Return number of bits set in bitset SRC. */
+int
+bitset_count (src)
+ bitset src;
{
- return BITSET__SIZE (src);
+ bitset_bindex list[BITSET_LIST_SIZE];
+ bitset_bindex next;
+ int num;
+ int count;
+
+ next = 0;
+ for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
+ count += num)
+ continue;
+
+ return count;
}
/* DST = 0. */
int
bitset_zero (dst)
- bitset dst;
+ bitset dst;
{
- return BITSET__OP1 (dst, BITSET_ZERO);
+ return BITSET_ZERO_ (dst);
}
/* DST = ~0. */
int
bitset_ones (dst)
- bitset dst;
+ bitset dst;
{
- return BITSET__OP1 (dst, BITSET_ONES);
+ return BITSET_ONES_ (dst);
}
-/* Return non-zero if all bits in bitset SRC are reset. */
+/* Return SRC == 0. */
int
bitset_empty_p (src)
- bitset src;
+ bitset src;
{
- return BITSET__OP1 (src, BITSET_EMPTY_P);
+ return BITSET_EMPTY_P_ (src);
}
/* Return DST == DST | SRC. */
int
bitset_subset_p (dst, src)
- bitset dst;
- bitset src;
+ bitset dst;
+ bitset src;
{
- return BITSET__OP2 (dst, src, BITSET_SUBSET_P);
+ BITSET_CHECK2_ (dst, src);
+ return BITSET_SUBSET_P_ (dst, src);
}
/* Return DST == SRC. */
int
bitset_equal_p (dst, src)
- bitset dst;
- bitset src;
+ bitset dst;
+ bitset src;
{
- BITSET__CHECK2 (dst, src);
- return BITSET__OP2 (dst, src, BITSET_EQUAL_P);
+ BITSET_CHECK2_ (dst, src);
+ return BITSET_EQUAL_P_ (dst, src);
+}
+
+
+/* Return DST & SRC == 0. */
+int
+bitset_disjoint_p (dst, src)
+ bitset dst;
+ bitset src;
+{
+ BITSET_CHECK2_ (dst, src);
+ return BITSET_DISJOINT_P_ (dst, src);
}
/* DST = ~SRC. */
int
bitset_not (dst, src)
- bitset dst;
- bitset src;
+ bitset dst;
+ bitset src;
{
- BITSET__CHECK2 (dst, src);
- return BITSET__OP2 (dst, src, BITSET_NOT);
+ BITSET_CHECK2_ (dst, 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;
+ bitset dst;
+ bitset src1;
+ bitset src2;
{
- BITSET__CHECK3 (dst, src1, src2);
- return BITSET__OP3 (dst, src1, src2, BITSET_OR);
+ BITSET_CHECK3_ (dst, src1, 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;
+ bitset dst;
+ bitset src1;
+ bitset src2;
{
- BITSET__CHECK3 (dst, src1, src2);
- return BITSET__OP3 (dst, src1, src2, BITSET_AND);
+ BITSET_CHECK3_ (dst, src1, 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;
+ bitset dst;
+ bitset src1;
+ bitset src2;
{
- BITSET__CHECK3 (dst, src1, src2);
- return BITSET__OP3 (dst, src1, src2, BITSET_XOR);
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_XOR_ (dst, src1, src2);
}
/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
int
bitset_andn (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
+ bitset dst;
+ bitset src1;
+ bitset src2;
{
- BITSET__CHECK3 (dst, src1, src2);
- return BITSET__OP3 (dst, src1, src2, BITSET_ANDN);
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_ANDN_ (dst, src1, src2);
}
/* DST = SRC1 | ~SRC2. Return non-zero if DST != SRC1 | ~SRC2. */
int
bitset_orn (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
+ bitset dst;
+ bitset src1;
+ bitset src2;
{
- BITSET__CHECK3 (dst, src1, src2);
- return BITSET__OP3 (dst, src1, src2, BITSET_ORN);
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_ORN_ (dst, src1, src2);
+}
+
+
+int
+bitset_op4 (dst, src1, src2, src3, op)
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+ enum bitset_ops op;
+{
+ int changed = 0;
+ bitset tmp;
+
+ /* Create temporary bitset. */
+ tmp = bitset_alloc (BITSET_TYPE_ (dst), 0);
+
+ switch (op)
+ {
+ case BITSET_OP_OR_AND:
+ BITSET_OR_ (tmp, src1, src2);
+ changed = BITSET_AND_ (dst, src3, tmp);
+ break;
+
+ case BITSET_OP_AND_OR:
+ BITSET_AND_ (tmp, src1, src2);
+ changed = BITSET_OR_ (dst, src3, tmp);
+ break;
+
+ case BITSET_OP_ANDN_OR:
+ BITSET_ANDN_ (tmp, src1, src2);
+ changed = BITSET_OR_ (dst, src3, tmp);
+ break;
+
+ default:
+ abort ();
+ }
+
+ bitset_free (tmp);
+ return changed;
}
@@ -540,13 +601,13 @@
DST != (SRC1 | SRC2) & SRC3. */
int
bitset_or_and (dst, src1, src2, src3)
- bitset dst;
- bitset src1;
- bitset src2;
- bitset src3;
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
{
- BITSET__CHECK4 (dst, src1, src2, src3);
- return BITSET__OP4 (dst, src1, src2, src3, BITSET_OR_AND);
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ return BITSET_OR_AND_ (dst, src1, src2, src3);
}
@@ -554,13 +615,27 @@
DST != (SRC1 & SRC2) | SRC3. */
int
bitset_and_or (dst, src1, src2, src3)
- bitset dst;
- bitset src1;
- bitset src2;
- bitset src3;
+ bitset dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ return BITSET_AND_OR_ (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 dst;
+ bitset src1;
+ bitset src2;
+ bitset src3;
{
- BITSET__CHECK4 (dst, src1, src2, src3);
- return BITSET__OP4 (dst, src1, src2, src3, BITSET_AND_OR);
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ return BITSET_ANDN_OR_ (dst, src1, src2, src3);
}
@@ -579,7 +654,8 @@
debug_bitset (bset)
bitset bset;
{
- bitset_print (stderr, bset, 1);
+ if (bset)
+ bitset_print (stderr, bset, 1);
}
@@ -595,47 +671,47 @@
#if BITSET_STATS
int
bitset_list (bset, list, num, next)
- bitset bset;
- bitset_bindex *list;
- bitset_bindex num;
- bitset_bindex *next;
+ bitset bset;
+ bitset_bindex *list;
+ bitset_bindex num;
+ bitset_bindex *next;
{
- bitset_bindex count;
+ bitset_bindex count;
- count = BITSET__LIST (bset, list, num, next);
+ count = BITSET_LIST_ (bset, list, num, next);
- if (bitset_stats)
- {
- bitset_bindex tmp;
- bitset_bindex size;
- bitset_bindex i;
- enum bitset_type type;
-
- type = bset->ops->type;
- BITSET_STATS_LISTS_INC (bset);
-
- /* Log histogram of number of set bits. */
- for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
- continue;
- if (i >= BITSET_LOG_COUNT_BINS)
- i = BITSET_LOG_COUNT_BINS - 1;
- BITSET_STATS_LIST_COUNTS_INC (bset, i);
-
- /* Log histogram of number of bits in set. */
- size = bitset_size (bset);
- for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
- continue;
- if (i >= BITSET_LOG_SIZE_BINS)
- i = BITSET_LOG_SIZE_BINS - 1;
- BITSET_STATS_LIST_SIZES_INC (bset, i);
-
- /* Histogram of fraction of bits set. */
- i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
- if (i >= BITSET_DENSITY_BINS)
- i = BITSET_DENSITY_BINS - 1;
- BITSET_STATS_LIST_DENSITY_INC (bset, i);
- }
- return count;
+ if (bitset_stats)
+ {
+ bitset_bindex tmp;
+ bitset_bindex size;
+ bitset_bindex i;
+ enum bitset_type type;
+
+ type = BITSET_TYPE_ (bset);
+ BITSET_STATS_LISTS_INC (bset);
+
+ /* Log histogram of number of set bits. */
+ for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
+ continue;
+ if (i >= BITSET_LOG_COUNT_BINS)
+ i = BITSET_LOG_COUNT_BINS - 1;
+ BITSET_STATS_LIST_COUNTS_INC (bset, i);
+
+ /* Log histogram of number of bits in set. */
+ size = bitset_size (bset);
+ for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
+ continue;
+ if (i >= BITSET_LOG_SIZE_BINS)
+ i = BITSET_LOG_SIZE_BINS - 1;
+ BITSET_STATS_LIST_SIZES_INC (bset, i);
+
+ /* Histogram of fraction of bits set. */
+ i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
+ if (i >= BITSET_DENSITY_BINS)
+ i = BITSET_DENSITY_BINS - 1;
+ BITSET_STATS_LIST_DENSITY_INC (bset, i);
+ }
+ return count;
}
@@ -656,14 +732,14 @@
total += bins[i];
if (!total)
- return;
+ return;
fprintf (file, "%s %s", name, msg);
for (i = 0; i < n_bins; i++)
fprintf (file, "%.0f-%.0f%%\t%8d (%5.1f%%)\n",
i * 100.0 / n_bins,
- (i + 1) * 100.0 / n_bins,
- bins[i], (100.0 * bins[i]) / total);
+ (i + 1) * 100.0 / n_bins, bins[i],
+ (100.0 * bins[i]) / total);
}
@@ -685,10 +761,10 @@
total += bins[i];
if (!total)
- return;
+ return;
/* 2 * ceil (log10(2) * (N - 1)) + 1 */
- max_width = 2 * (unsigned int)(0.30103 * (n_bins - 1) + 0.9999) + 1;
+ max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
fprintf (file, "%s %s", name, msg);
for (i = 0; i < 2; i++)
@@ -699,7 +775,8 @@
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], (100.0 * bins[i]) / total);
+ 1 << (i - 1), (1 << i) - 1, bins[i],
+ (100.0 * bins[i]) / total);
}
@@ -721,10 +798,10 @@
fprintf (file, "%d bitset_lists\n", stats->lists);
bitset_log_histogram_print (file, name, "count log histogram\n",
- BITSET_LOG_COUNT_BINS, stats->list_counts);
+ BITSET_LOG_COUNT_BINS, stats->list_counts);
bitset_log_histogram_print (file, name, "size log histogram\n",
- BITSET_LOG_SIZE_BINS, stats->list_sizes);
+ BITSET_LOG_SIZE_BINS, stats->list_sizes);
bitset_percent_histogram_print (file, name, "density histogram\n",
BITSET_DENSITY_BINS, stats->list_density);
@@ -738,7 +815,7 @@
int verbose ATTRIBUTE_UNUSED;
{
int i;
- static const char *names[] = BITSET__TYPE_NAMES;
+ static const char *names[] = BITSET_TYPE_NAMES;
if (!bitset_stats)
return;
@@ -749,7 +826,7 @@
fprintf (file, "Accumulated runs = %d\n", bitset_stats->runs);
for (i = 0; i < BITSET_TYPE_NUM; i++)
- bitset_stats_print_1 (file, names[i], &bitset_stats->types[i]);
+ bitset_stats_print_1 (file, names[i], &bitset_stats->types[i]);
}
#endif /* BITSET_STATS */
@@ -759,9 +836,9 @@
bitset_stats_init ()
{
#if BITSET_STATS
- bitset_stats = &bitset_stats_data;
- bitset_stats_read ();
-#endif /* BITSET_STATS */
+ bitset_stats = &bitset_stats_data;
+ bitset_stats_read ();
+#endif /* BITSET_STATS */
}
@@ -769,25 +846,25 @@
static void
bitset_stats_read ()
{
- FILE *file;
+ FILE *file;
- if (!bitset_stats)
- return;
+ if (!bitset_stats)
+ return;
- file = fopen (BITSET_STATS_FILE, "r");
- if (file)
- {
- if (fread (&bitset_stats_data, sizeof (bitset_stats_data),
- 1, file) != 1)
- {
- if (ferror (file))
- perror ("Could not read stats file");
- else
- fprintf (stderr, "Bad stats file size\n");
- }
- fclose (file);
- }
- bitset_stats_data.runs++;
+ file = fopen (BITSET_STATS_FILE, "r");
+ if (file)
+ {
+ if (fread (&bitset_stats_data, sizeof (bitset_stats_data),
+ 1, file) != 1)
+ {
+ if (ferror (file))
+ perror ("Could not read stats file.");
+ else
+ fprintf (stderr, "Bad stats file size.\n");
+ }
+ fclose (file);
+ }
+ bitset_stats_data.runs++;
}
@@ -795,21 +872,21 @@
static void
bitset_stats_write ()
{
- FILE *file;
+ FILE *file;
- if (!bitset_stats)
- return;
+ if (!bitset_stats)
+ return;
- file = fopen (BITSET_STATS_FILE, "w");
- if (file)
- {
- if (fwrite (&bitset_stats_data, sizeof (bitset_stats_data),
- 1, file) != 1)
- perror ("Could not write stats file");
- fclose (file);
- }
- else
- perror ("Could not open stats file for writing");
+ file = fopen (BITSET_STATS_FILE, "w");
+ if (file)
+ {
+ if (fwrite (&bitset_stats_data, sizeof (bitset_stats_data),
+ 1, file) != 1)
+ perror ("Could not write stats file.");
+ fclose (file);
+ }
+ else
+ perror ("Could not open stats file for writing.");
}
Index: lib/bitset.h
--- lib/bitset.h Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/bitset.h Sun, 03 Mar 2002 11:40:05 +0100 akim
@@ -19,42 +19,14 @@
#ifndef _BITSET_H
#define _BITSET_H
-#if HAVE_CONFIG_H
-# include <config.h>
-#endif
-
-#define BITSET_STATS 1
+/* This file is the public interface to the bitset abstract data type.
+ Only use the functions and macros defined in this file. */
-# ifndef PARAMS
-# if defined PROTOTYPES || (defined __STDC__ && __STDC__)
-# define PARAMS(Args) Args
-# else
-# define PARAMS(Args) ()
-# endif
-# endif
-
-# ifndef __attribute__
-# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
-# define __attribute__(x)
-# endif
-# endif
-
-# ifndef ATTRIBUTE_NORETURN
-# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
-# endif
-
-# ifndef ATTRIBUTE_UNUSED
-# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
-# endif
-
-#include "bitset-int.h"
-#include "sbitset.h"
-#include "lbitset.h"
-#include "ebitset.h"
+#include "bbitset.h"
#include "obstack.h"
#include <stdio.h>
-#include "xalloc.h"
+/* Attributes used to select a bitset implementation. */
enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */
BITSET_VARIABLE = 2, /* Bitset size variable. */
BITSET_DENSE = 4, /* Bitset dense. */
@@ -64,75 +36,48 @@
typedef unsigned int bitset_attrs;
-/* The elements of these structures should be considered
- to be private. */
-typedef struct bitset_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. */
- union bitset_data
- {
- struct sbitset_struct s;
- struct lbitset_struct l;
- struct ebitset_struct e;
- } u;
-} *bitset;
-
-
-/* The contents of this structure should be considered private. */
-struct bitset_ops_struct
+/* The contents of the structure should be considered to be private.
+ While I would like to make this structure opaque, it needs to be
+ visible for the inline bit set/test functions. */
+struct bitset_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;
+ struct bbitset_struct b;
};
-
/* Return bytes required for bitset of desired type and size. */
extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
/* Initialise a bitset with desired type and size. */
extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
+/* Select an implementation type based on the desired bitset size
+ and attributes. */
extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
bitset_attrs));
-/* Create a bitset of desired type and size. */
+/* Create a bitset of desired type and size. The bitset is zeroed. */
extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
/* Free bitset. */
extern void bitset_free PARAMS ((bitset));
-/* Create a bitset of desired type and size using obstack. */
+/* Create a bitset of desired type and size using an obstack. The
+ bitset is zeroed. */
extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
bitset_bindex, enum bitset_type));
/* Free bitset allocated on obstack. */
extern void bitset_obstack_free PARAMS ((bitset));
-/* Create a bitset of desired size and attributes. */
+/* 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));
+
#if BITSET_CACHE && BITSET_INLINE
static inline void bitset_set PARAMS ((bitset, bitset_bindex));
static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
@@ -144,12 +89,12 @@
bitset_bindex bitno;
{
bitset_windex index = bitno / BITSET_WORD_BITS;
- bitset_windex offset = index - bset->cindex;
+ bitset_windex offset = index - bset->b.cindex;
- if (offset < bset->csize)
- bset->cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
+ if (offset < bset->b.csize)
+ bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
else
- BITSET__SET (bset, bitno);
+ BITSET_SET_ (bset, bitno);
}
@@ -159,12 +104,12 @@
bitset_bindex bitno;
{
bitset_windex index = bitno / BITSET_WORD_BITS;
- bitset_windex offset = index - bset->cindex;
+ bitset_windex offset = index - bset->b.cindex;
- if (offset < bset->csize)
- bset->cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
+ if (offset < bset->b.csize)
+ bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
else
- BITSET__RESET (bset, bitno);
+ BITSET_RESET_ (bset, bitno);
}
@@ -174,12 +119,12 @@
bitset_bindex bitno;
{
bitset_windex index = bitno / BITSET_WORD_BITS;
- bitset_windex offset = index - bset->cindex;
+ bitset_windex offset = index - bset->b.cindex;
- if (offset < bset->csize)
- return (bset->cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
+ if (offset < bset->b.csize)
+ return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
else
- return BITSET__TEST (bset, bitno);
+ return BITSET_TEST_ (bset, bitno);
}
#endif
@@ -191,12 +136,12 @@
{ \
bitset_bindex _bitno = (bitno); \
bitset_windex _index = _bitno / BITSET_WORD_BITS; \
- bitset_windex _offset = _index - (bset)->cindex; \
+ bitset_windex _offset = _index - (bset)->b.cindex; \
\
- if (_offset < (bset)->csize) \
- (bset)->cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); \
+ if (_offset < (bset)->b.csize) \
+ (bset)->b.cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); \
else \
- BITSET__SET ((bset), _bitno); \
+ BITSET_SET_ ((bset), _bitno); \
} while (0)
@@ -206,32 +151,32 @@
{ \
bitset_bindex _bitno = (bitno); \
bitset_windex _index = _bitno / BITSET_WORD_BITS; \
- bitset_windex _offset = _index - (bset)->cindex; \
+ bitset_windex _offset = _index - (bset)->b.cindex; \
\
- if (_offset < (bset)->csize) \
- (bset)->cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \
+ if (_offset < (bset)->b.csize) \
+ (bset)->b.cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \
else \
- BITSET__RESET ((bset), _bitno); \
+ BITSET_RESET_ ((bset), _bitno); \
} while (0)
/* Test bit BITNO in bitset BSET. */
#define bitset_test(bset, bitno) \
-(((((bitno) / BITSET_WORD_BITS) - (bset)->cindex) < (bset)->csize) \
- ? ((bset)->cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->cindex)] \
+(((((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)))
+ : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
#endif
#if ! BITSET_CACHE
/* Set bit BITNO in bitset SRC. */
-#define bitset_set(SRC, BITNO) BITSET__SET (SRC, BITNO)
+#define bitset_set(SRC, BITNO) BITSET_SET_ (SRC, BITNO)
/* Reset bit BITNO in bitset SRC. */
-#define bitset_reset(SRC, BITNO) BITSET__RESET (SRC, BITNO)
+#define bitset_reset(SRC, BITNO) BITSET_RESET_ (SRC, BITNO)
/* Return non-zero if bit BITNO in bitset SRC is set. */
-#define bitset_test(SRC, BITNO) BITSET__TEST (SRC, BITNO)
+#define bitset_test(SRC, BITNO) BITSET_TEST_ (SRC, BITNO)
#endif
/* DST = 0. */
@@ -249,6 +194,9 @@
/* Return DST == SRC. */
extern int bitset_equal_p PARAMS ((bitset, bitset));
+/* Return DST & SRC == 0. */
+extern int bitset_disjoint_p PARAMS ((bitset, bitset));
+
/* DST == SRC. */
extern int bitset_copy PARAMS ((bitset, bitset));
@@ -280,7 +228,7 @@
/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
DST != (SRC1 & ~SRC2) | SRC3. */
-#define bitset_andn_or(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));
@@ -296,14 +244,14 @@
bitset_bindex *));
#else
#define bitset_list(BSET, LIST, NUM, NEXT) \
-BITSET__LIST (BSET, LIST, NUM, NEXT)
+BITSET_LIST_ (BSET, LIST, NUM, NEXT)
#endif
/* 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)
+BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT)
/* Find first set bit. */
extern int bitset_first PARAMS ((bitset));
@@ -360,7 +308,7 @@
} while (0)
-/* Define set operations in terms of bit operations. */
+/* Define set operations in terms of logical operations. */
#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
@@ -369,7 +317,8 @@
#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
-bitset_andn_or (DST, SRC1, SRC2, SRC3)
+ bitset_andn_or (DST, SRC1, SRC2, SRC3)
+
/* Release any memory tied up with bitsets. */
extern void bitset_release_memory PARAMS ((void));
@@ -385,11 +334,5 @@
/* Function to debug bitset stats from debugger. */
extern void debug_bitset_stats PARAMS ((void));
-
-extern bitset sbitset_init PARAMS ((bitset, bitset_bindex));
-
-extern bitset lbitset_init PARAMS ((bitset, bitset_bindex));
-
-extern bitset ebitset_init PARAMS ((bitset, bitset_bindex));
#endif /* _BITSET_H */
Index: lib/bitsetv.c
--- lib/bitsetv.c Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/bitsetv.c Sun, 03 Mar 2002 11:35:00 +0100 akim
@@ -30,29 +30,32 @@
type TYPE. */
bitset *
bitsetv_alloc (n_vecs, n_bits, type)
- unsigned int n_vecs;
- unsigned int n_bits;
- enum bitset_type type;
-{
- unsigned int vector_bytes;
- unsigned int bytes;
- bitset *bsetv;
- unsigned int i;
-
- /* Determine number of bytes for each set. */
- bytes = bitset_bytes (type, n_bits);
-
- /* Allocate vector table at head of bitset array. */
- vector_bytes = n_vecs * sizeof (bitset);
- bsetv = (bitset *) xmalloc (vector_bytes + bytes * n_vecs);
-
- for (i = 0; i < n_vecs; i++)
+ unsigned int n_vecs;
+ unsigned int n_bits;
+ enum bitset_type type;
+{
+ unsigned int vector_bytes;
+ unsigned int bytes;
+ bitset *bsetv;
+ unsigned int i;
+
+ /* Determine number of bytes for each set. */
+ bytes = bitset_bytes (type, n_bits);
+
+ /* Allocate vector table at head of bitset array. */
+ vector_bytes = (n_vecs + 1) * sizeof (bitset);
+ bsetv = (bitset *) xcalloc (1, vector_bytes + bytes * n_vecs);
+
+ for (i = 0; i < n_vecs; i++)
{
- bsetv[i] = (bitset)((char *)bsetv + vector_bytes + i * bytes);
+ bsetv[i] = (bitset) ((char *) bsetv + vector_bytes + i * bytes);
bitset_init (bsetv[i], n_bits, type);
}
- return bsetv;
+
+ /* Null terminate table. */
+ bsetv[i] = 0;
+ return bsetv;
}
@@ -60,48 +63,50 @@
attribute hints specified by ATTR. */
bitset *
bitsetv_create (n_vecs, n_bits, attr)
- unsigned int n_vecs;
- unsigned int n_bits;
- unsigned int attr;
+ unsigned int n_vecs;
+ unsigned int n_bits;
+ unsigned int attr;
{
- enum bitset_type type;
-
- type = bitset_type_choose (n_bits, attr);
- return bitsetv_alloc (n_vecs, n_bits, type);
+ enum bitset_type type;
+
+ type = bitset_type_choose (n_bits, attr);
+ return bitsetv_alloc (n_vecs, n_bits, type);
}
/* Free bitset vector BSETV. */
void
bitsetv_free (bsetv)
- bitset *bsetv;
+ bitset *bsetv;
{
- free (bsetv);
+ unsigned int i;
+
+ for (i = 0; bsetv[i]; i++)
+ BITSET_FREE_ (bsetv[i]);
+ free (bsetv);
}
-/* Zero a vector of N_VECS bitsets. */
+/* Zero a vector of bitsets. */
void
-bitsetv_zero (bsetv, n_vecs)
+bitsetv_zero (bsetv)
struct bitset_struct **bsetv;
- unsigned int n_vecs;
{
unsigned int i;
-
- for (i = 0; i < n_vecs; i++)
- bitset_zero (bsetv[i]);
+
+ for (i = 0; bsetv[i]; i++)
+ bitset_zero (bsetv[i]);
}
-/* Set a vector of N_VECS bitsets to ones. */
+/* Set a vector of bitsets to ones. */
void
-bitsetv_ones (bsetv, n_vecs)
+bitsetv_ones (bsetv)
bitset *bsetv;
- unsigned int n_vecs;
{
unsigned int i;
-
- for (i = 0; i < n_vecs; i++)
+
+ for (i = 0; bsetv[i]; i++)
bitset_ones (bsetv[i]);
}
@@ -109,20 +114,35 @@
/* Dump the contents of a bitset vector BSETV with N_VECS elements to
FILE. */
void
-bitsetv_dump (file, title, subtitle, bsetv, n_vecs)
+bitsetv_dump (file, title, subtitle, bsetv)
FILE *file;
const char *title, *subtitle;
bitset *bsetv;
- unsigned int n_vecs;
{
unsigned int i;
-
+
fprintf (file, "%s\n", title);
- for (i = 0; i < n_vecs; i++)
+ for (i = 0; bsetv[i]; i++)
{
fprintf (file, "%s %d\n", subtitle, i);
bitset_dump (file, bsetv[i]);
}
-
+
fprintf (file, "\n");
+}
+
+
+void
+debug_bitsetv (bsetv)
+ bitset *bsetv;
+{
+ unsigned int i;
+
+ for (i = 0; bsetv[i]; i++)
+ {
+ fprintf (stderr, "%d: ", i);
+ debug_bitset (bsetv[i]);
+ }
+
+ fprintf (stderr, "\n");
}
Index: lib/bitsetv.h
--- lib/bitsetv.h Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/bitsetv.h Sun, 03 Mar 2002 11:35:12 +0100 akim
@@ -37,13 +37,12 @@
extern void bitsetv_free PARAMS ((bitsetv));
/* Zero vector of bitsets. */
-extern void bitsetv_zero PARAMS ((bitsetv, unsigned int));
+extern void bitsetv_zero PARAMS ((bitsetv));
/* Set vector of bitsets. */
-extern void bitsetv_ones PARAMS ((bitsetv, unsigned int));
+extern void bitsetv_ones PARAMS ((bitsetv));
/* Dump vector of bitsets. */
extern void bitsetv_dump PARAMS ((FILE *, const char *,
- const char *, bitsetv,
- unsigned int));
+ const char *, bitsetv));
#endif /* _BITSETV_H */
Index: lib/ebitset.c
--- lib/ebitset.c Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/ebitset.c Sun, 03 Mar 2002 11:35:00 +0100 akim
@@ -1,43 +1,33 @@
-/* Functions to support efficient bitsets.
+/* Functions to support expandable bitsets.
Copyright (C) 2002 Free Software Foundation, Inc.
Contributed by Michael Hayes (address@hidden).
-This program is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2 of the License, or
-(at your option) any later version.
-
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with this program; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
-#include "bitset.h"
+#include "bbitset.h"
#include "obstack.h"
#include <stdlib.h>
-# if WITH_DMALLOC
-# define DMALLOC_FUNC_CHECK
-# include <dmalloc.h>
-# endif /* WITH_DMALLOC */
-
-/* This file implements linked-list bitsets. These bitsets can be of
+/* This file implements expandable bitsets. These bitsets can be of
arbitrary length and are more efficient than arrays of bits for
large sparse sets.
- Usually if all the bits in an element are zero we remove the element
- from the list. However, a side effect of the bit caching is that we
- do not always notice when an element becomes zero. Hence the
- ebitset_weed function which removes zero elements.
-
Empty elements are represented by a NULL pointer in the table of
element pointers. An alternative is to point to a special zero
element. Similarly, we could represent an all 1's element with
@@ -46,33 +36,76 @@
Bitsets are commonly empty so we need to ensure that this special
case is fast. A zero bitset is indicated when cdata is 0. This is
conservative since cdata may be non zero and the bitset may still
- be zero.
+ be zero.
The bitset cache can be disabled either by setting cindex to
- some large number or by setting csize to 0. Here
+ some large number or by setting csize to 0. Here
we use the former approach since cindex needs to be updated whenever
- cdata is changed.
+ cdata is changed.
*/
+
+/* Number of words to use for each element. */
+
+#ifndef EBITSET_ELT_WORDS
+#define EBITSET_ELT_WORDS 2
+#endif
+
+/* Number of bits stored in each element. */
+#define EBITSET_ELT_BITS \
+ ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
+
+/* Ebitset element. We use an array of bits. */
+typedef struct ebitset_elt_struct
+{
+ union
+ {
+ bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */
+ struct ebitset_elt_struct *next;
+ }
+ u;
+}
+ebitset_elt;
+
+
+typedef ebitset_elt *ebitset_elts;
+
+/* Head of ebitset linked list. */
+typedef struct ebitset_struct
+{
+ unsigned int size; /* Number of elements. */
+ ebitset_elts *elts; /* Expanding array of pointers to elements. */
+}
+*ebitset;
+
+
/* Number of elements to initially allocate. */
+
#ifndef EBITSET_INITIAL_SIZE
#define EBITSET_INITIAL_SIZE 2
#endif
/* Minimum number of elements to grow table. */
+
#ifndef EBITSET_GROW_SIZE
#define EBITSET_GROW_SIZE 4
#endif
+struct bitset_struct
+{
+ struct bbitset_struct b;
+ struct ebitset_struct e;
+};
-enum ebitset_find_mode {EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST};
+enum ebitset_find_mode
+ { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits. */
/* Obstack to allocate bitset elements from. */
static struct obstack ebitset_obstack;
static int ebitset_obstack_init = 0;
-static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */
+static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */
static void ebitset_elts_grow PARAMS ((bitset, unsigned int));
static ebitset_elt *ebitset_elt_alloc PARAMS ((void));
@@ -86,58 +119,55 @@
static int ebitset_elt_zero_p PARAMS ((ebitset_elt *));
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_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_op4 PARAMS((bitset, bitset, bitset, bitset,
- enum bitset_ops));
-static int ebitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
-static int ebitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
-static void ebitset_free 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_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_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
+ bitset_bindex *));
+static int ebitset_reverse_list
+PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
+static void ebitset_free PARAMS ((bitset));
-#define EBITSET_ELTS(BSET) ((BSET)->u.e.elts)
-#define EBITSET_SIZE(BSET) ((BSET)->u.e.size)
+#define EBITSET_ELTS(BSET) ((BSET)->e.elts)
+#define EBITSET_SIZE(BSET) ((BSET)->e.size)
#define EBITSET_NEXT(ELT) ((ELT)->u.next)
#define EBITSET_WORDS(ELT) ((ELT)->u.words)
/* Disable bitset cache and mark BSET as being zero. */
-#define EBITSET_ZERO_SET(BSET) ((BSET)->cindex = BITSET_INDEX_MAX, \
- (BSET)->cdata = 0)
+#define EBITSET_OP_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX, \
+ (BSET)->b.cdata = 0)
-#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->cindex = BITSET_INDEX_MAX)
+#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX)
/* Disable bitset cache and mark BSET as being possibly non-zero. */
#define EBITSET_NONZERO_SET(BSET) \
- (EBITSET_CACHE_DISABLE (BSET), (BSET)->cdata = (bitset_word *)~0)
+ (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
/* 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_ZERO_P(BSET) ((BSET)->cdata == 0)
+#define EBITSET_OP_ZERO_P(BSET) ((BSET)->b.cdata == 0)
-/* Enable cache to point to element with table index EINDEX.
+/* Enable cache to point to element with table index EINDEX.
The element must exist. */
#define EBITSET_CACHE_SET(BSET, EINDEX) \
- ((BSET)->cindex = (EINDEX) * EBITSET_ELT_WORDS, \
- (BSET)->cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
+ ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
+ (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
/* Grow the expandable table for BSET by SIZE elements. */
static void
ebitset_elts_grow (bset, size)
- bitset bset;
- unsigned int size;
+ bitset bset;
+ unsigned int size;
{
unsigned int oldsize;
unsigned int newsize;
@@ -146,7 +176,7 @@
newsize = oldsize + size;
EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
- newsize * sizeof (ebitset_elt *));
+ newsize * sizeof (ebitset_elt *));
EBITSET_SIZE (bset) = newsize;
memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *));
@@ -174,13 +204,17 @@
ebitset_obstack_init = 1;
/* Let particular systems override the size of a chunk. */
+
#ifndef OBSTACK_CHUNK_SIZE
#define OBSTACK_CHUNK_SIZE 0
#endif
+
/* Let them override the alloc and free routines too. */
+
#ifndef OBSTACK_CHUNK_ALLOC
#define OBSTACK_CHUNK_ALLOC xmalloc
#endif
+
#ifndef OBSTACK_CHUNK_FREE
#define OBSTACK_CHUNK_FREE free
#endif
@@ -191,12 +225,14 @@
obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
__alignof__ (ebitset_elt),
- (void *(*) PARAMS ((long)))
OBSTACK_CHUNK_ALLOC,
- (void (*) PARAMS ((void *)))
OBSTACK_CHUNK_FREE);
+ (void *(*)PARAMS ((long)))
+ OBSTACK_CHUNK_ALLOC,
+ (void (*)PARAMS ((void *)))
+ OBSTACK_CHUNK_FREE);
}
/* Perhaps we should add a number of new elements to the free
- list. */
+ list. */
elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack,
sizeof (ebitset_elt));
}
@@ -296,7 +332,7 @@
if ((elt = elts[eindex]))
{
- if (EBITSET_WORDS (elt) == bset->cdata)
+ if (EBITSET_WORDS (elt) == bset->b.cdata)
return elt;
EBITSET_CACHE_SET (bset, eindex);
@@ -366,7 +402,7 @@
bitset_windex j;
int count;
- if (EBITSET_ZERO_P (bset))
+ if (EBITSET_OP_ZERO_P (bset))
return 0;
elts = EBITSET_ELTS (bset);
@@ -390,14 +426,14 @@
count = j - count;
if (!count)
{
- /* All the bits are zero. We could shrink the elts.
+ /* All the bits are zero. We could shrink the elts.
For now just mark BSET as known to be zero. */
- EBITSET_ZERO_SET (bset);
+ EBITSET_OP_ZERO_SET (bset);
}
else
EBITSET_NONZERO_SET (bset);
- return count;
+ return count;
}
@@ -409,7 +445,7 @@
ebitset_elts *elts;
bitset_windex j;
- if (EBITSET_ZERO_P (bset))
+ if (EBITSET_OP_ZERO_P (bset))
return;
elts = EBITSET_ELTS (bset);
@@ -421,9 +457,9 @@
ebitset_elt_remove (bset, j);
}
- /* All the bits are zero. We could shrink the elts.
+ /* All the bits are zero. We could shrink the elts.
For now just mark BSET as known to be zero. */
- EBITSET_ZERO_SET (bset);
+ EBITSET_OP_ZERO_SET (bset);
}
@@ -454,9 +490,9 @@
ebitset_elt *selt = selts[j];
ebitset_elt *delt = delts[j];
- if (! selt && ! delt)
+ if (!selt && !delt)
continue;
- if ((selt && ! delt) || (!selt && delt))
+ if ((selt && !delt) || (!selt && delt))
return 0;
for (i = 0; i < EBITSET_ELT_WORDS; i++)
@@ -515,10 +551,10 @@
if (src == dst)
return 0;
- if (EBITSET_ZERO_P (dst))
+ if (EBITSET_OP_ZERO_P (dst))
{
ebitset_copy (dst, src);
- return ! EBITSET_ZERO_P (src);
+ return !EBITSET_OP_ZERO_P (src);
}
if (ebitset_equal_p (dst, src))
@@ -549,7 +585,7 @@
ebitset_elt_find (dst, index, EBITSET_CREATE);
- dst->cdata[index - dst->cindex] |= (1 << (bitno % BITSET_WORD_BITS));
+ dst->b.cdata[index - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS));
}
@@ -562,11 +598,11 @@
bitset_windex index = bitno / BITSET_WORD_BITS;
if (!ebitset_elt_find (dst, index, EBITSET_FIND))
- return;
+ return;
- dst->cdata[index - dst->cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
+ dst->b.cdata[index - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
- /* If all the data is zero, perhaps we should remove it now...
+ /* If all the data is zero, perhaps we should remove it now...
However, there could be a good chance that the element will be needed
again soon. */
}
@@ -583,7 +619,8 @@
if (!ebitset_elt_find (src, index, EBITSET_FIND))
return 0;
- return (src->cdata[index - src->cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
+ return (src->b.
+ cdata[index - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
}
@@ -597,8 +634,8 @@
/* 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. */
+ *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)
bitset bset;
@@ -619,7 +656,7 @@
bitset_word word;
ebitset_elts *elts;
- if (EBITSET_ZERO_P (bset))
+ if (EBITSET_OP_ZERO_P (bset))
return 0;
size = EBITSET_SIZE (bset);
@@ -627,13 +664,13 @@
rbitno = *next;
if (rbitno >= n_bits)
- return 0;
+ return 0;
elts = EBITSET_ELTS (bset);
bitno = n_bits - (rbitno + 1);
- index = bitno / BITSET_WORD_BITS;
+ index = bitno / BITSET_WORD_BITS;
eindex = bitno / EBITSET_ELT_BITS;
windex = index - eindex * EBITSET_ELT_WORDS;
@@ -684,8 +721,8 @@
/* 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. */
+ *NEXT and store in array LIST. Return with actual number of bits
+ found and with *NEXT indicating where search stopped. */
static int
ebitset_list (bset, list, num, next)
bitset bset;
@@ -702,7 +739,7 @@
bitset_word word;
ebitset_elts *elts;
- if (EBITSET_ZERO_P (bset))
+ if (EBITSET_OP_ZERO_P (bset))
return 0;
bitno = *next;
@@ -777,12 +814,12 @@
word = srcp[i];
if (word)
{
- if (! (word & 0xffff))
+ if (!(word & 0xffff))
{
word >>= 16;
bitno += 16;
}
- if (! (word & 0xff))
+ if (!(word & 0xff))
{
word >>= 8;
bitno += 8;
@@ -837,22 +874,23 @@
switch (op)
{
- case BITSET_ZERO:
+ case BITSET_OP_ZERO:
ebitset_zero (dst);
return 1;
- case BITSET_ONES:
+ 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);
+ we should just add pointers to a ones element. */
+ elt =
+ ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
memset (EBITSET_WORDS (elt), ~0, sizeof (EBITSET_WORDS (elt)));
}
break;
- case BITSET_EMPTY_P:
- return ! ebitset_weed (dst);
+ case BITSET_OP_EMPTY_P:
+ return !ebitset_weed (dst);
default:
abort ();
@@ -876,28 +914,31 @@
switch (op)
{
- case BITSET_COPY:
+ case BITSET_OP_COPY:
ebitset_copy (dst, src);
break;
- case BITSET_NOT:
+ case BITSET_OP_NOT:
for (j = 0; j < EBITSET_SIZE (src); j++)
{
/* 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;
- case BITSET_EQUAL_P:
+ /* Return 1 if DST == SRC. */
+ case BITSET_OP_EQUAL_P:
return ebitset_equal_p (dst, src);
/* Return 1 if DST == DST | SRC. */
- case BITSET_SUBSET_P:
+ case BITSET_OP_SUBSET_P:
{
ebitset_elts *selts;
ebitset_elts *delts;
@@ -918,7 +959,7 @@
selt = j < ssize ? selts[j] : 0;
delt = j < dsize ? delts[j] : 0;
- if (! selt && ! delt)
+ if (!selt && !delt)
continue;
if (!selt)
@@ -935,6 +976,44 @@
}
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++)
+ {
+ 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 (selt)[i] & EBITSET_WORDS (delt)[i]))
+ return 0;
+ }
+ return 1;
+ }
+ break;
+
default:
abort ();
}
@@ -966,30 +1045,31 @@
bitset_windex j;
/* Fast track common, simple cases. */
- if (EBITSET_ZERO_P (src2))
+ if (EBITSET_OP_ZERO_P (src2))
{
- if (op == BITSET_AND)
+ if (op == BITSET_OP_AND)
{
ebitset_weed (dst);
- changed = EBITSET_ZERO_P (dst);
+ changed = EBITSET_OP_ZERO_P (dst);
ebitset_zero (dst);
return changed;
}
- else if (op == BITSET_ANDN || op == BITSET_OR || op == BITSET_XOR)
+ else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR
+ || op == BITSET_OP_XOR)
{
return ebitset_copy_compare (dst, src1);
}
}
- else if (EBITSET_ZERO_P (src1))
+ else if (EBITSET_OP_ZERO_P (src1))
{
- if (op == BITSET_AND || op == BITSET_ANDN)
+ if (op == BITSET_OP_AND || op == BITSET_OP_ANDN)
{
ebitset_weed (dst);
- changed = EBITSET_ZERO_P (dst);
+ changed = EBITSET_OP_ZERO_P (dst);
ebitset_zero (dst);
return changed;
}
- else if (op == BITSET_OR || op == BITSET_XOR)
+ else if (op == BITSET_OP_OR || op == BITSET_OP_XOR)
{
return ebitset_copy_compare (dst, src2);
}
@@ -1003,7 +1083,7 @@
size = ssize2;
if (size > dsize)
- ebitset_elts_grow (dst, size - dsize);
+ ebitset_elts_grow (dst, size - dsize);
selts1 = EBITSET_ELTS (src1);
selts2 = EBITSET_ELTS (src2);
@@ -1019,7 +1099,7 @@
selt2 = j < ssize2 ? selts2[j] : 0;
delt = j < dsize ? delts[j] : 0;
- if (! selt1 && ! selt2)
+ if (!selt1 && !selt2)
{
if (delt)
{
@@ -1043,7 +1123,7 @@
dstp = EBITSET_WORDS (delt);
switch (op)
{
- case BITSET_OR:
+ case BITSET_OP_OR:
for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ | *srcp2++;
@@ -1056,7 +1136,7 @@
}
break;
- case BITSET_AND:
+ case BITSET_OP_AND:
for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ & *srcp2++;
@@ -1069,7 +1149,7 @@
}
break;
- case BITSET_XOR:
+ case BITSET_OP_XOR:
for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ ^ *srcp2++;
@@ -1082,7 +1162,7 @@
}
break;
- case BITSET_ANDN:
+ case BITSET_OP_ANDN:
for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ & ~(*srcp2++);
@@ -1095,7 +1175,7 @@
}
break;
- case BITSET_ORN:
+ case BITSET_OP_ORN:
for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ | ~(*srcp2++);
@@ -1112,7 +1192,7 @@
abort ();
}
- if (! ebitset_elt_zero_p (delt))
+ if (!ebitset_elt_zero_p (delt))
{
ebitset_elt_add (dst, delt, j);
}
@@ -1140,62 +1220,21 @@
}
-static int
-ebitset_op4 (dst, src1, src2, src3, op)
- bitset dst;
- bitset src1;
- bitset src2;
- bitset src3;
- enum bitset_ops op;
-{
- int changed = 0;
- bitset tmp;
-
- tmp = bitset_create (BITSET_LIST, 0);
-
- switch (op)
- {
- case BITSET_OR_AND:
- bitset_or (tmp, src1, src2);
- changed = bitset_and (dst, src3, tmp);
- break;
-
- case BITSET_AND_OR:
- bitset_and (tmp, src1, src2);
- changed = bitset_or (dst, src3, tmp);
- break;
-
- case BITSET_ANDN_OR:
- bitset_andn (tmp, src1, src2);
- changed = bitset_or (dst, src3, tmp);
- break;
-
- default:
- abort ();
- }
-
- bitset_free (tmp);
- EBITSET_NONZERO_SET (dst);
- return changed;
-}
-
-
/* Vector of operations for linked-list bitsets. */
-struct bitset_ops_struct ebitset_ops =
- {
- ebitset_set,
- ebitset_reset,
- ebitset_test,
- ebitset_size,
- ebitset_op1,
- ebitset_op2,
- ebitset_op3,
- ebitset_op4,
- ebitset_list,
- ebitset_reverse_list,
- ebitset_free,
- BITSET_TABLE
- };
+struct bitset_ops_struct ebitset_ops = {
+ ebitset_set,
+ ebitset_reset,
+ ebitset_test,
+ ebitset_size,
+ ebitset_op1,
+ ebitset_op2,
+ ebitset_op3,
+ bitset_op4,
+ ebitset_list,
+ ebitset_reverse_list,
+ ebitset_free,
+ BITSET_TABLE
+};
/* Return size of initial structure. */
@@ -1216,11 +1255,11 @@
{
unsigned int size;
- bset->ops = &ebitset_ops;
+ bset->b.ops = &ebitset_ops;
- bset->csize = EBITSET_ELT_WORDS;
+ bset->b.csize = EBITSET_ELT_WORDS;
- EBITSET_ZERO_SET (bset);
+ EBITSET_OP_ZERO_SET (bset);
size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
: EBITSET_INITIAL_SIZE;
Index: lib/ebitset.h
--- lib/ebitset.h Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/ebitset.h Sun, 03 Mar 2002 11:35:12 +0100 akim
@@ -19,39 +19,11 @@
#ifndef _EBITSET_H
#define _EBITSET_H
-#include "bitset-int.h"
-
-/* Number of words to use for each element. */
-#ifndef EBITSET_ELT_WORDS
-#define EBITSET_ELT_WORDS 2
-#endif
-
-/* Number of bits stored in each element. */
-#define EBITSET_ELT_BITS \
- ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
-
-/* Ebitset element. We use an array of bits. */
-typedef struct ebitset_elt_struct
-{
- union
- {
- bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */
- struct ebitset_elt_struct *next;
- } u;
-} ebitset_elt;
-
-
-typedef ebitset_elt *ebitset_elts;
-
-/* Head of ebitset linked list. */
-typedef struct ebitset_struct
-{
- unsigned int size; /* Number of elements. */
- ebitset_elts *elts; /* Expanding array of pointers to elements. */
-} *ebitset;
-
+#include "bbitset.h"
extern int ebitset_bytes PARAMS ((bitset_bindex));
+
+extern bitset ebitset_init PARAMS ((bitset, bitset_bindex));
extern void ebitset_release_memory PARAMS ((void));
Index: lib/lbitset.c
--- lib/lbitset.c Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/lbitset.c Sun, 03 Mar 2002 11:35:00 +0100 akim
@@ -2,50 +2,92 @@
Copyright (C) 2002 Free Software Foundation, Inc.
Contributed by Michael Hayes (address@hidden).
-This program is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2 of the License, or
-(at your option) any later version.
-
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with this program; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
-#include "bitset.h"
+#include "bbitset.h"
#include "obstack.h"
#include <stdlib.h>
-# if WITH_DMALLOC
-# define DMALLOC_FUNC_CHECK
-# include <dmalloc.h>
-# endif /* WITH_DMALLOC */
-
/* This file implements linked-list bitsets. These bitsets can be of
arbitrary length and are more efficient than arrays of bits for
large sparse sets.
- Usually if all the bits in an element are zero we remove the element
- from the list. However, a side effect of the bit caching is that we
- do not always notice when an element becomes zero. Hence the
- lbitset_weed function which removes zero elements. */
+ Usually if all the bits in an element are zero we remove the element
+ from the list. However, a side effect of the bit caching is that we
+ do not always notice when an element becomes zero. Hence the
+ lbitset_weed function which removes zero elements. */
+
+
+/* Number of words to use for each element. The larger the value the
+ greater the size of the cache and the shorter the time to find a given bit
+ but the more memory wasted for sparse bitsets and the longer the time
+ to search for set bits. */
+
+#ifndef LBITSET_ELT_WORDS
+#define LBITSET_ELT_WORDS 2
+#endif
+
+typedef bitset_word lbitset_word;
+
+#define LBITSET_WORD_BITS BITSET_WORD_BITS
+
+/* Number of bits stored in each element. */
+#define LBITSET_ELT_BITS \
+ ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
+
+/* Lbitset element. We use an array of bits for each element.
+ These are linked together in a doubly-linked list. */
+typedef struct lbitset_elt_struct
+{
+ struct lbitset_elt_struct *next; /* Next element. */
+ struct lbitset_elt_struct *prev; /* Previous element. */
+ bitset_windex index; /* bitno / BITSET_WORD_BITS. */
+ bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */
+}
+lbitset_elt;
+
+
+/* Head of lbitset linked list. */
+typedef struct lbitset_struct
+{
+ lbitset_elt *head; /* First element in linked list. */
+ lbitset_elt *tail; /* Last element in linked list. */
+}
+*lbitset;
+
-enum lbitset_find_mode {LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST};
+struct bitset_struct
+{
+ struct bbitset_struct b;
+ struct lbitset_struct l;
+};
-static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */
+
+enum lbitset_find_mode
+ { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
+
+static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits.
*/
/* Obstack to allocate bitset elements from. */
static struct obstack lbitset_obstack;
static int lbitset_obstack_init = 0;
-static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */
+static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */
static lbitset_elt *lbitset_elt_alloc PARAMS ((void));
static lbitset_elt *lbitset_elt_calloc PARAMS ((void));
@@ -58,32 +100,30 @@
static void lbitset_prune PARAMS ((bitset, lbitset_elt *));
static void lbitset_weed PARAMS ((bitset));
-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 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_op4 PARAMS((bitset, bitset, bitset, bitset,
- enum bitset_ops));
-static int lbitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
-static int lbitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
-static void lbitset_free PARAMS((bitset));
+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 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_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
+ bitset_bindex *));
+static int lbitset_reverse_list
+PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
+static void lbitset_free PARAMS ((bitset));
#define LBITSET_CURRENT1(X) (lbitset_elt *)((char *)(X) + ((char
*)&(((lbitset_elt *)(X))->next) - (char *)&(((lbitset_elt *)(X))->words)))
-#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->cdata)
+#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
-#define LBITSET_HEAD(X) ((X)->u.l.head)
-#define LBITSET_TAIL(X) ((X)->u.l.tail)
+#define LBITSET_HEAD(X) ((X)->l.head)
+#define LBITSET_TAIL(X) ((X)->l.tail)
/* Allocate a lbitset element. The bits are not cleared. */
static inline lbitset_elt *
@@ -106,13 +146,17 @@
lbitset_obstack_init = 1;
/* Let particular systems override the size of a chunk. */
+
#ifndef OBSTACK_CHUNK_SIZE
#define OBSTACK_CHUNK_SIZE 0
#endif
+
/* Let them override the alloc and free routines too. */
+
#ifndef OBSTACK_CHUNK_ALLOC
#define OBSTACK_CHUNK_ALLOC xmalloc
#endif
+
#ifndef OBSTACK_CHUNK_FREE
#define OBSTACK_CHUNK_FREE free
#endif
@@ -123,12 +167,14 @@
obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
__alignof__ (lbitset_elt),
- (void *(*) PARAMS ((long)))
OBSTACK_CHUNK_ALLOC,
- (void (*) PARAMS ((void *)))
OBSTACK_CHUNK_FREE);
+ (void *(*)PARAMS ((long)))
+ OBSTACK_CHUNK_ALLOC,
+ (void (*)PARAMS ((void *)))
+ OBSTACK_CHUNK_FREE);
}
/* Perhaps we should add a number of new elements to the free
- list. */
+ list. */
elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack,
sizeof (lbitset_elt));
}
@@ -185,18 +231,18 @@
{
if (next)
{
- bset->cdata = next->words;
- bset->cindex = next->index;
+ bset->b.cdata = next->words;
+ bset->b.cindex = next->index;
}
else if (prev)
{
- bset->cdata = prev->words;
- bset->cindex = prev->index;
+ bset->b.cdata = prev->words;
+ bset->b.cindex = prev->index;
}
else
{
- bset->csize = 0;
- bset->cdata = 0;
+ bset->b.csize = 0;
+ bset->b.cdata = 0;
}
}
@@ -214,22 +260,22 @@
lbitset_elt *next;
if (!elt)
- return;
+ return;
if (elt->prev)
- {
+ {
LBITSET_TAIL (bset) = elt->prev;
- bset->cdata = elt->prev->words;
- bset->cindex = elt->prev->index;
+ bset->b.cdata = elt->prev->words;
+ bset->b.cindex = elt->prev->index;
elt->prev->next = 0;
- }
+ }
else
- {
+ {
LBITSET_HEAD (bset) = 0;
LBITSET_TAIL (bset) = 0;
- bset->cdata = 0;
- bset->csize = 0;
- }
+ bset->b.cdata = 0;
+ bset->b.csize = 0;
+ }
for (; elt; elt = next)
{
@@ -264,10 +310,10 @@
lbitset_elt *ptr;
lbitset_elt *current;
- if (bset->csize)
- current = LBITSET_CURRENT (bset);
+ if (bset->b.csize)
+ current = LBITSET_CURRENT (bset);
else
- current = LBITSET_HEAD (bset);
+ current = LBITSET_HEAD (bset);
/* If this is the first and only element, add it in. */
if (LBITSET_HEAD (bset) == 0)
@@ -279,11 +325,10 @@
/* If this index is less than that of the current element, it goes
somewhere before the current element. */
- else if (index < bset->cindex)
+ else if (index < bset->b.cindex)
{
for (ptr = current;
- ptr->prev && ptr->prev->index > index;
- ptr = ptr->prev)
+ ptr->prev && ptr->prev->index > index; ptr = ptr->prev)
continue;
if (ptr->prev)
@@ -300,8 +345,7 @@
else
{
for (ptr = current;
- ptr->next && ptr->next->index < index;
- ptr = ptr->next)
+ ptr->next && ptr->next->index < index; ptr = ptr->next)
continue;
if (ptr->next)
@@ -315,9 +359,9 @@
}
/* Set up so this is the first element searched. */
- bset->cindex = index;
- bset->csize = LBITSET_ELT_WORDS;
- bset->cdata = elt->words;
+ bset->b.cindex = index;
+ bset->b.csize = LBITSET_ELT_WORDS;
+ bset->b.cdata = elt->words;
}
@@ -330,11 +374,11 @@
lbitset_elt *elt;
lbitset_elt *current;
- if (bset->csize)
+ if (bset->b.csize)
{
current = LBITSET_CURRENT (bset);
/* Check if element is the cached element. */
- if ((index - bset->cindex) < bset->csize)
+ if ((index - bset->b.cindex) < bset->b.csize)
return current;
}
else
@@ -344,11 +388,10 @@
if (current)
{
- if (index < bset->cindex)
+ if (index < bset->b.cindex)
{
for (elt = current;
- elt->prev && elt->index > index;
- elt = elt->prev)
+ elt->prev && elt->index > index; elt = elt->prev)
continue;
}
else
@@ -363,9 +406,9 @@
we want, the one we want does not exist. */
if (elt && (index - elt->index) < LBITSET_ELT_WORDS)
{
- bset->cindex = elt->index;
- bset->csize = LBITSET_ELT_WORDS;
- bset->cdata = elt->words;
+ bset->b.cindex = elt->index;
+ bset->b.csize = LBITSET_ELT_WORDS;
+ bset->b.cdata = elt->words;
return elt;
}
}
@@ -449,7 +492,7 @@
if (delt->words[j] != selt->words[j])
return 0;
}
- return ! selt && ! delt;
+ return !selt && !delt;
}
@@ -490,9 +533,9 @@
}
LBITSET_TAIL (dst) = tmp;
- dst->csize = LBITSET_ELT_WORDS;
- dst->cdata = LBITSET_HEAD (dst)->words;
- dst->cindex = LBITSET_HEAD (dst)->index;
+ dst->b.csize = LBITSET_ELT_WORDS;
+ dst->b.cdata = LBITSET_HEAD (dst)->words;
+ dst->b.cindex = LBITSET_HEAD (dst)->index;
}
@@ -506,7 +549,7 @@
if (src == dst)
return 0;
- if (! LBITSET_HEAD (dst))
+ if (!LBITSET_HEAD (dst))
{
lbitset_copy (dst, src);
return LBITSET_HEAD (src) != 0;
@@ -529,7 +572,7 @@
elt = LBITSET_TAIL (src);
if (!elt)
- return 0;
+ return 0;
/* Return current size of bitset in bits. */
return (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
@@ -546,7 +589,7 @@
lbitset_elt_find (dst, index, LBITSET_CREATE);
- dst->cdata[index - dst->cindex] |= (1 << (bitno % BITSET_WORD_BITS));
+ dst->b.cdata[index - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS));
}
@@ -559,9 +602,9 @@
bitset_windex index = bitno / BITSET_WORD_BITS;
if (!lbitset_elt_find (dst, index, LBITSET_FIND))
- return;
+ return;
- dst->cdata[index - dst->cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
+ dst->b.cdata[index - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
/* If all the data is zero, perhaps we should unlink it now... */
}
@@ -578,7 +621,8 @@
if (!lbitset_elt_find (src, index, LBITSET_FIND))
return 0;
- return (src->cdata[index - src->cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
+ return (src->b.
+ cdata[index - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
}
@@ -591,8 +635,8 @@
/* 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. */
+ *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)
bitset bset;
@@ -618,7 +662,7 @@
rbitno = *next;
if (rbitno >= n_bits)
- return 0;
+ return 0;
bitno = n_bits - (rbitno + 1);
@@ -644,9 +688,10 @@
for (; (index - elt->index) < LBITSET_ELT_WORDS;
index--, bitoff -= BITSET_WORD_BITS,
- bitcnt = BITSET_WORD_BITS - 1)
+ bitcnt = BITSET_WORD_BITS - 1)
{
- word = srcp[index - elt->index] << (BITSET_WORD_BITS - 1 - bitcnt);
+ word =
+ srcp[index - elt->index] << (BITSET_WORD_BITS - 1 - bitcnt);
for (; word; bitcnt--)
{
@@ -677,8 +722,8 @@
/* 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. */
+ *NEXT and store in array LIST. Return with actual number of bits
+ found and with *NEXT indicating where search stopped. */
static int
lbitset_list (bset, list, num, next)
bitset bset;
@@ -695,7 +740,7 @@
head = LBITSET_HEAD (bset);
if (!head)
- return 0;
+ return 0;
bitno = *next;
count = 0;
@@ -779,12 +824,12 @@
word = srcp[0];
if (word)
{
- if (! (word & 0xffff))
+ if (!(word & 0xffff))
{
word >>= 16;
bitno += 16;
}
- if (! (word & 0xff))
+ if (!(word & 0xff))
{
word >>= 8;
bitno += 8;
@@ -802,7 +847,7 @@
word = srcp[1];
if (word)
{
- if (! (word & 0xffff))
+ if (!(word & 0xffff))
{
word >>= 16;
bitno += 16;
@@ -822,12 +867,12 @@
word = srcp[i];
if (word)
{
- if (! (word & 0xffff))
+ if (!(word & 0xffff))
{
word >>= 16;
bitno += 16;
}
- if (! (word & 0xff))
+ if (!(word & 0xff))
{
word >>= 8;
bitno += 8;
@@ -893,11 +938,11 @@
switch (op)
{
- case BITSET_ZERO:
+ case BITSET_OP_ZERO:
lbitset_zero (dst);
break;
- case BITSET_ONES:
+ case BITSET_OP_ONES:
/* This is a decidedly unfriendly operation for a linked list
bitset! */
elt = LBITSET_TAIL (dst);
@@ -914,7 +959,7 @@
}
break;
- case BITSET_EMPTY_P:
+ case BITSET_OP_EMPTY_P:
lbitset_weed (dst);
if (LBITSET_HEAD (dst))
return 0;
@@ -943,11 +988,11 @@
switch (op)
{
- case BITSET_COPY:
+ case BITSET_OP_COPY:
lbitset_copy (dst, src);
break;
- case BITSET_NOT:
+ case BITSET_OP_NOT:
/* This is another unfriendly operation for a linked list
bitset! */
elt = LBITSET_TAIL (dst);
@@ -969,11 +1014,13 @@
lbitset_weed (dst);
break;
- case BITSET_EQUAL_P:
+ /* Return 1 if DST == SRC. */
+ case BITSET_OP_EQUAL_P:
return lbitset_equal_p (dst, src);
break;
- case BITSET_SUBSET_P:
+ /* 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)
{
@@ -1001,6 +1048,31 @@
}
break;
+ /* 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)
+ {
+ 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];
+ }
+ }
+
+ for (j = 0; j < LBITSET_ELT_WORDS; j++)
+ if (selt->words[j] & delt->words[j])
+ return 0;
+ }
+ break;
+
default:
abort ();
}
@@ -1034,36 +1106,36 @@
/* Fast track common, simple cases. */
if (!selt2)
{
- if (op == BITSET_AND)
+ if (op == BITSET_OP_AND)
{
lbitset_weed (dst);
- changed = ! LBITSET_HEAD (dst);
+ changed = !LBITSET_HEAD (dst);
lbitset_zero (dst);
return changed;
}
- else if (op == BITSET_ANDN || op == BITSET_OR || op == BITSET_XOR)
+ 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_AND || op == BITSET_ANDN)
+ if (op == BITSET_OP_AND || op == BITSET_OP_ANDN)
{
lbitset_weed (dst);
- changed = ! LBITSET_HEAD (dst);
+ changed = !LBITSET_HEAD (dst);
lbitset_zero (dst);
return changed;
}
- else if (op == BITSET_OR || op == BITSET_XOR)
+ else if (op == BITSET_OP_OR || op == BITSET_OP_XOR)
{
return lbitset_copy_compare (dst, src2);
}
}
-
LBITSET_HEAD (dst) = 0;
- dst->csize = 0;
+ dst->b.csize = 0;
index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
@@ -1123,7 +1195,7 @@
dstp = dtmp->words;
switch (op)
{
- case BITSET_OR:
+ case BITSET_OP_OR:
for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ | *srcp2++;
@@ -1136,7 +1208,7 @@
}
break;
- case BITSET_AND:
+ case BITSET_OP_AND:
for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ & *srcp2++;
@@ -1149,7 +1221,7 @@
}
break;
- case BITSET_XOR:
+ case BITSET_OP_XOR:
for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ ^ *srcp2++;
@@ -1162,7 +1234,7 @@
}
break;
- case BITSET_ANDN:
+ case BITSET_OP_ANDN:
for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ & ~(*srcp2++);
@@ -1175,7 +1247,7 @@
}
break;
- case BITSET_ORN:
+ case BITSET_OP_ORN:
for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
{
bitset_word tmp = *srcp1++ | ~(*srcp2++);
@@ -1192,7 +1264,7 @@
abort ();
}
- if (! lbitset_elt_zero_p (dtmp))
+ if (!lbitset_elt_zero_p (dtmp))
{
dtmp->index = index;
/* Perhaps this could be optimised... */
@@ -1215,67 +1287,21 @@
}
-static int
-lbitset_op4 (dst, src1, src2, src3, op)
- bitset dst;
- bitset src1;
- bitset src2;
- bitset src3;
- enum bitset_ops op;
-{
- int changed = 0;
- bitset tmp;
-
-#ifdef ENABLE_CHECKING
- /* Check for compatiblity. */
- if (src1->ops != dst->ops || src2->ops != dst->ops || src3->ops != dst->ops)
- abort ();
-#endif
-
- tmp = bitset_create (BITSET_LIST, 0);
-
- switch (op)
- {
- case BITSET_OR_AND:
- bitset_or (tmp, src1, src2);
- changed = bitset_and (dst, src3, tmp);
- break;
-
- case BITSET_AND_OR:
- bitset_and (tmp, src1, src2);
- changed = bitset_or (dst, src3, tmp);
- break;
-
- case BITSET_ANDN_OR:
- bitset_andn (tmp, src1, src2);
- changed = bitset_or (dst, src3, tmp);
- break;
-
- default:
- abort ();
- }
-
- bitset_free (tmp);
- return changed;
-}
-
-
/* Vector of operations for linked-list bitsets. */
-struct bitset_ops_struct lbitset_ops =
- {
- lbitset_set,
- lbitset_reset,
- lbitset_test,
- lbitset_size,
- lbitset_op1,
- lbitset_op2,
- lbitset_op3,
- lbitset_op4,
- lbitset_list,
- lbitset_reverse_list,
- lbitset_free,
- BITSET_LIST
- };
+struct bitset_ops_struct lbitset_ops = {
+ lbitset_set,
+ lbitset_reset,
+ lbitset_test,
+ lbitset_size,
+ lbitset_op1,
+ lbitset_op2,
+ lbitset_op3,
+ bitset_op4,
+ lbitset_list,
+ lbitset_reverse_list,
+ lbitset_free,
+ BITSET_LIST
+};
/* Return size of initial structure. */
@@ -1294,17 +1320,7 @@
bitset bset;
bitset_bindex n_bits ATTRIBUTE_UNUSED;
{
- LBITSET_HEAD (bset) = 0;
- LBITSET_TAIL (bset) = 0;
-
- bset->ops = &lbitset_ops;
-
- bset->cindex = 0;
- /* Disable cache until have some elements allocated.
- If we have variable length arrays, then we may
- need to allocate dummy element. */
- bset->csize = 0;
- bset->cdata = 0;
+ bset->b.ops = &lbitset_ops;
return bset;
}
Index: lib/lbitset.h
--- lib/lbitset.h Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/lbitset.h Sun, 03 Mar 2002 11:35:12 +0100 akim
@@ -19,43 +19,11 @@
#ifndef _LBITSET_H
#define _LBITSET_H
-#include "bitset-int.h"
-
-/* Number of words to use for each element. The larger the value the
- greater the size of the cache and the shorter the time to find a given bit
- but the more memory wasted for sparse bitsets and the longer the time
- to search for set bits. */
-#ifndef LBITSET_ELT_WORDS
-#define LBITSET_ELT_WORDS 2
-#endif
-
-typedef bitset_word lbitset_word;
-#define LBITSET_WORD_BITS BITSET_WORD_BITS
-
-/* Number of bits stored in each element. */
-#define LBITSET_ELT_BITS \
- ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
-
-/* Lbitset element. We use an array of bits for each element.
- These are linked together in a doubly-linked list. */
-typedef struct lbitset_elt_struct
-{
- struct lbitset_elt_struct *next; /* Next element. */
- struct lbitset_elt_struct *prev; /* Previous element. */
- bitset_windex index; /* bitno / BITSET_WORD_BITS. */
- bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */
-} lbitset_elt;
-
-
-/* Head of lbitset linked list. */
-typedef struct lbitset_struct
-{
- lbitset_elt *head; /* First element in linked list. */
- lbitset_elt *tail; /* Last element in linked list. */
-} *lbitset;
-
+#include "bbitset.h"
extern int lbitset_bytes PARAMS ((bitset_bindex));
+
+extern bitset lbitset_init PARAMS ((bitset, bitset_bindex));
extern void lbitset_release_memory PARAMS ((void));
Index: lib/sbitset.c
--- lib/sbitset.c Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/sbitset.c Sun, 03 Mar 2002 11:35:00 +0100 akim
@@ -2,57 +2,67 @@
Copyright (C) 2002 Free Software Foundation, Inc.
Contributed by Michael Hayes (address@hidden).
-This program is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2 of the License, or
-(at your option) any later version.
-
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with this program; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
-#include "bitset.h"
+#include "sbitset.h"
#include <stdlib.h>
-
-# if WITH_DMALLOC
-# define DMALLOC_FUNC_CHECK
-# include <dmalloc.h>
-# endif /* WITH_DMALLOC */
+#include <string.h>
/* This file implements fixed size bitsets stored as an array
of words. Any unused bits in the last word must be zero. */
-static void sbitset_unused_clear PARAMS((bitset));
+typedef struct sbitset_struct
+{
+ unsigned int n_bits; /* Number of bits. */
+ bitset_word words[1]; /* The array of bits. */
+}
+*sbitset;
+
-static int sbitset_small_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
+struct bitset_struct
+{
+ struct bbitset_struct b;
+ struct sbitset_struct s;
+};
-static void sbitset_set PARAMS((bitset, bitset_bindex));
-static void sbitset_reset PARAMS((bitset, bitset_bindex));
-static int sbitset_test PARAMS((bitset, bitset_bindex));
-static int sbitset_size PARAMS((bitset));
-static int sbitset_op1 PARAMS((bitset, enum bitset_ops));
-static int sbitset_op2 PARAMS((bitset, bitset, enum bitset_ops));
-static int sbitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops));
-static int sbitset_op4 PARAMS((bitset, bitset, bitset, bitset,
- enum bitset_ops));
-static int sbitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
-static int sbitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
+static void sbitset_unused_clear PARAMS ((bitset));
+
+static int sbitset_small_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
+ bitset_bindex *));
+
+static void sbitset_set PARAMS ((bitset, bitset_bindex));
+static void sbitset_reset PARAMS ((bitset, bitset_bindex));
+static int sbitset_test PARAMS ((bitset, bitset_bindex));
+static int sbitset_size PARAMS ((bitset));
+static int sbitset_op1 PARAMS ((bitset, enum bitset_ops));
+static int sbitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
+static int sbitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
+static int sbitset_op4 PARAMS ((bitset, bitset, bitset, bitset,
+ enum bitset_ops));
+static int sbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
+ bitset_bindex *));
+static int sbitset_reverse_list
+PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
#define SBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
-#define SBITSET_WORDS(X) ((X)->u.s.words)
-#define SBITSET_N_BITS(X) ((X)->u.s.n_bits)
+#define SBITSET_WORDS(X) ((X)->s.words)
+#define SBITSET_N_BITS(X) ((X)->s.n_bits)
/* Return size in bits of bitset SRC. */
@@ -60,13 +70,13 @@
sbitset_size (src)
bitset src;
{
- return SBITSET_N_BITS (src);
+ return SBITSET_N_BITS (src);
}
/* 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. */
+ *NEXT and store in array LIST. Return with actual number of bits
+ found and with *NEXT indicating where search stopped. */
static int
sbitset_small_list (src, list, num, next)
bitset src;
@@ -96,30 +106,30 @@
of the word of interest. */
if (num >= BITSET_WORD_BITS)
- {
+ {
for (count = 0; word; bitno++)
- {
+ {
if (word & 1)
- list[count++] = bitno;
+ list[count++] = bitno;
word >>= 1;
- }
- }
+ }
+ }
else
- {
+ {
for (count = 0; word; bitno++)
- {
+ {
if (word & 1)
- {
+ {
list[count++] = bitno;
if (count >= num)
- {
+ {
bitno++;
break;
- }
- }
+ }
+ }
word >>= 1;
- }
- }
+ }
+ }
*next = bitno;
return count;
@@ -132,8 +142,8 @@
bitset dst ATTRIBUTE_UNUSED;
bitset_bindex bitno ATTRIBUTE_UNUSED;
{
- /* This should never occur for sbitsets. */
- abort ();
+ /* This should never occur for sbitsets. */
+ abort ();
}
@@ -143,8 +153,8 @@
bitset dst ATTRIBUTE_UNUSED;
bitset_bindex bitno ATTRIBUTE_UNUSED;
{
- /* This should never occur for sbitsets. */
- abort ();
+ /* This should never occur for sbitsets. */
+ abort ();
}
@@ -154,9 +164,9 @@
bitset src ATTRIBUTE_UNUSED;
bitset_bindex bitno ATTRIBUTE_UNUSED;
{
- /* This should never occur for sbitsets. */
- abort ();
- return 0;
+ /* This should never occur for sbitsets. */
+ abort ();
+ return 0;
}
@@ -187,7 +197,7 @@
of the word of interest. */
if (rbitno >= n_bits)
- return 0;
+ return 0;
count = 0;
@@ -198,7 +208,7 @@
bitoff = index * BITSET_WORD_BITS;
for (; index != ~0U; index--, bitoff -= BITSET_WORD_BITS,
- bitcnt = BITSET_WORD_BITS - 1)
+ bitcnt = BITSET_WORD_BITS - 1)
{
word = srcp[index] << (BITSET_WORD_BITS - 1 - bitcnt);
for (; word; bitcnt--)
@@ -222,8 +232,8 @@
/* 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. */
+ *NEXT and store in array LIST. Return with actual number of bits
+ found and with *NEXT indicating where search stopped. */
static int
sbitset_list (src, list, num, next)
bitset src;
@@ -235,17 +245,17 @@
bitset_bindex count;
bitset_windex index;
bitset_bindex bitoff;
- bitset_windex size = src->csize;
+ bitset_windex size = src->b.csize;
bitset_word *srcp = SBITSET_WORDS (src);
bitset_word word;
bitno = *next;
count = 0;
- if (! bitno)
+ if (!bitno)
{
/* Many bitsets are zero, so make this common case fast. */
- for (index = 0; index < size && ! srcp[index]; index++)
+ for (index = 0; index < size && !srcp[index]; index++)
continue;
if (index >= size)
return 0;
@@ -292,18 +302,18 @@
for (; index < size; index++, bitoff += BITSET_WORD_BITS)
{
- if (! (word = srcp[index]))
+ if (!(word = srcp[index]))
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++)
@@ -336,7 +346,8 @@
last_bit = SBITSET_N_BITS (dst) % BITSET_WORD_BITS;
if (last_bit)
- SBITSET_WORDS (dst)[dst->csize - 1] &= (bitset_word)((1 << last_bit) - 1);
+ SBITSET_WORDS (dst)[dst->b.csize - 1] &=
+ (bitset_word) ((1 << last_bit) - 1);
}
@@ -349,21 +360,21 @@
bitset_word *dstp = SBITSET_WORDS (dst);
unsigned int bytes;
- bytes = sizeof (bitset_word) * dst->csize;
+ bytes = sizeof (bitset_word) * dst->b.csize;
switch (op)
{
- case BITSET_ZERO:
+ case BITSET_OP_ZERO:
memset (dstp, 0, bytes);
break;
- case BITSET_ONES:
+ case BITSET_OP_ONES:
memset (dstp, ~0, bytes);
sbitset_unused_clear (dst);
break;
- case BITSET_EMPTY_P:
- for (i = 0; i < dst->csize; i++)
+ case BITSET_OP_EMPTY_P:
+ for (i = 0; i < dst->b.csize; i++)
if (dstp[i])
return 0;
break;
@@ -385,42 +396,46 @@
unsigned int i;
bitset_word *srcp = SBITSET_WORDS (src);
bitset_word *dstp = SBITSET_WORDS (dst);
- bitset_windex size = dst->csize;
+ bitset_windex size = dst->b.csize;
#ifdef ENABLE_CHECKING
/* Check for compatiblity. */
- if (src->ops != dst->ops || SBITSET_N_BITS (src) != SBITSET_N_BITS (dst))
+ if (SBITSET_N_BITS (src) != SBITSET_N_BITS (dst))
abort ();
#endif
switch (op)
{
- case BITSET_COPY:
+ case BITSET_OP_COPY:
if (srcp == dstp)
break;
memcpy (dstp, srcp, sizeof (bitset_word) * size);
break;
- case BITSET_NOT:
+ case BITSET_OP_NOT:
for (i = 0; i < size; i++)
*dstp++ = ~(*srcp++);
sbitset_unused_clear (dst);
break;
- case BITSET_EQUAL_P:
+ case BITSET_OP_EQUAL_P:
for (i = 0; i < size; i++)
- if (*dstp++ != *srcp++)
+ if (*srcp++ != *dstp++)
return 0;
break;
-
- case BITSET_SUBSET_P:
+
+ case BITSET_OP_SUBSET_P:
for (i = 0; i < size; i++, dstp++, srcp++)
- {
- if (*dstp != (*srcp | *dstp))
- return 0;
- }
+ if (*dstp != (*srcp | *dstp))
+ return 0;
break;
-
+
+ case BITSET_OP_DISJOINT_P:
+ for (i = 0; i < size; i++)
+ if (*srcp++ & *dstp++)
+ return 0;
+ break;
+
default:
abort ();
}
@@ -441,18 +456,18 @@
bitset_word *src1p = SBITSET_WORDS (src1);
bitset_word *src2p = SBITSET_WORDS (src2);
bitset_word *dstp = SBITSET_WORDS (dst);
- bitset_windex size = dst->csize;
+ bitset_windex size = dst->b.csize;
#ifdef ENABLE_CHECKING
/* Check for compatiblity. */
- if (src1->ops != dst->ops || SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
- || src2->ops != dst->ops || SBITSET_N_BITS (src2) != SBITSET_N_BITS
(dst))
+ if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
+ SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst))
abort ();
#endif
switch (op)
{
- case BITSET_OR:
+ case BITSET_OP_OR:
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = *src1p++ | *src2p++;
@@ -465,7 +480,7 @@
}
break;
- case BITSET_AND:
+ case BITSET_OP_AND:
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = *src1p++ & *src2p++;
@@ -478,7 +493,7 @@
}
break;
- case BITSET_XOR:
+ case BITSET_OP_XOR:
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = *src1p++ ^ *src2p++;
@@ -491,7 +506,7 @@
}
break;
- case BITSET_ANDN:
+ case BITSET_OP_ANDN:
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = *src1p++ & ~(*src2p++);
@@ -504,7 +519,7 @@
}
break;
- case BITSET_ORN:
+ case BITSET_OP_ORN:
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = *src1p++ | ~(*src2p++);
@@ -540,19 +555,19 @@
bitset_word *src2p = SBITSET_WORDS (src2);
bitset_word *src3p = SBITSET_WORDS (src3);
bitset_word *dstp = SBITSET_WORDS (dst);
- bitset_windex size = dst->csize;
+ bitset_windex size = dst->b.csize;
#ifdef ENABLE_CHECKING
/* Check for compatiblity. */
- if (src1->ops != dst->ops || SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
- || src2->ops != dst->ops || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)
- || src3->ops != dst->ops || SBITSET_N_BITS (src3) != SBITSET_N_BITS
(dst))
+ if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
+ || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)
+ || SBITSET_N_BITS (src3) != SBITSET_N_BITS (dst))
abort ();
#endif
switch (op)
{
- case BITSET_OR_AND:
+ case BITSET_OP_OR_AND:
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
@@ -565,7 +580,7 @@
}
break;
- case BITSET_AND_OR:
+ case BITSET_OP_AND_OR:
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
@@ -578,7 +593,7 @@
}
break;
- case BITSET_ANDN_OR:
+ case BITSET_OP_ANDN_OR:
for (i = 0; i < size; i++, dstp++)
{
bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
@@ -600,38 +615,36 @@
/* Vector of operations for single word bitsets. */
-struct bitset_ops_struct sbitset_small_ops =
- {
- sbitset_set,
- sbitset_reset,
- sbitset_test,
- sbitset_size,
- sbitset_op1,
- sbitset_op2,
- sbitset_op3,
- sbitset_op4,
- sbitset_small_list,
- sbitset_reverse_list,
- NULL,
- BITSET_ARRAY
- };
+struct bitset_ops_struct sbitset_small_ops = {
+ sbitset_set,
+ sbitset_reset,
+ sbitset_test,
+ sbitset_size,
+ sbitset_op1,
+ sbitset_op2,
+ sbitset_op3,
+ sbitset_op4,
+ sbitset_small_list,
+ sbitset_reverse_list,
+ NULL,
+ BITSET_ARRAY
+};
/* Vector of operations for multiple word bitsets. */
-struct bitset_ops_struct sbitset_ops =
- {
- sbitset_set,
- sbitset_reset,
- sbitset_test,
- sbitset_size,
- sbitset_op1,
- sbitset_op2,
- sbitset_op3,
- sbitset_op4,
- sbitset_list,
- sbitset_reverse_list,
- NULL,
- BITSET_ARRAY
+struct bitset_ops_struct sbitset_ops = {
+ sbitset_set,
+ sbitset_reset,
+ sbitset_test,
+ sbitset_size,
+ sbitset_op1,
+ sbitset_op2,
+ sbitset_op3,
+ sbitset_op4,
+ sbitset_list,
+ sbitset_reverse_list,
+ NULL,
+ BITSET_ARRAY
};
@@ -661,12 +674,12 @@
There is probably little merit if using caching since
the small bitset will always fit in the cache. */
if (size == 1)
- bset->ops = &sbitset_small_ops;
+ bset->b.ops = &sbitset_small_ops;
else
- bset->ops = &sbitset_ops;
+ bset->b.ops = &sbitset_ops;
- bset->cindex = 0;
- bset->csize = size;
- bset->cdata = SBITSET_WORDS (bset);
+ bset->b.cindex = 0;
+ bset->b.csize = size;
+ bset->b.cdata = SBITSET_WORDS (bset);
return bset;
}
Index: lib/sbitset.h
--- lib/sbitset.h Sun, 27 Jan 2002 20:40:44 +0100 akim
+++ lib/sbitset.h Sun, 03 Mar 2002 11:35:12 +0100 akim
@@ -19,15 +19,10 @@
#ifndef _SBITSET_H
#define _SBITSET_H
-#include "bitset-int.h"
-
-typedef struct sbitset_struct
-{
- unsigned int n_bits; /* Number of bits. */
- bitset_word words[1]; /* The array of bits. */
-} *sbitset;
-
+#include "bbitset.h"
extern int sbitset_bytes PARAMS ((bitset_bindex));
+
+extern bitset sbitset_init PARAMS ((bitset, bitset_bindex));
#endif
Index: lib/bbitset.h
--- lib/bbitset.h Sun, 03 Mar 2002 11:48:50 +0100 akim
+++ lib/bbitset.h Sun, 03 Mar 2002 11:42:39 +0100 akim
@@ -0,0 +1,275 @@
+/* Base bitset stuff.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+
+#ifndef _BBITSET_H
+#define _BBITSET_H
+
+/* Bison modifications: BEGIN. */
+#define IN_BISON 1
+#if IN_BISON
+# if HAVE_CONFIG_H
+# include <config.h>
+# endif
+# include <stdlib.h>
+
+# define BITSET_STATS 1
+/* This file is the public interface to the bitset abstract data type.
+ Only use the functions and macros defined in this file. */
+
+# ifndef PARAMS
+# if defined PROTOTYPES || (defined __STDC__ && __STDC__)
+# define PARAMS(Args) Args
+# else
+# define PARAMS(Args) ()
+# endif
+# endif
+
+# ifndef __attribute__
+# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
+# define __attribute__(x)
+# endif
+# endif
+
+# ifndef ATTRIBUTE_NORETURN
+# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
+# endif
+
+# ifndef ATTRIBUTE_UNUSED
+# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
+# endif
+# include "xalloc.h"
+#else /* ! IN_BISON */
+# include "libiberty.h"
+#endif
+
+#ifdef HAVE_LIMITS_H
+#include <limits.h>
+#endif
+
+/* Currently we support three flavours of bitsets:
+ BITSET_ARRAY: Array of bits (fixed size, faster).
+ BITSET_LIST: Linked list of array of bits (variable size, least storage
+ for large very sparse sets).
+ BITSET_TABLE: Expandable table of pointers to array of bits
+ (variable size, less storage for large sparse sets).
+*/
+enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM};
+#define BITSET_TYPE_NAMES {"sbitset", "lbitset", "ebitset"}
+
+/* Non-zero to enable bitset caching. */
+#define BITSET_CACHE 1
+
+/* Non-zero to use inline functions instead of macros. */
+#define BITSET_INLINE 0
+
+/* Non-zero to enable bitset statistics gathering. */
+#define BITSET_STATS 1
+
+/* Non-zero to enable bitset type checking. */
+#define BITSET_CHECK 1
+
+/* Data type used to store a word of bits. */
+typedef unsigned long bitset_word;
+#define BITSET_WORD_BITS ((unsigned) CHAR_BIT * sizeof (bitset_word))
+
+/* Bit index. */
+typedef unsigned long bitset_bindex;
+
+/* Word index. */
+typedef unsigned long bitset_windex;
+
+#define BITSET_INDEX_MAX ((1U << (BITSET_WORD_BITS - 1)))
+
+#define BITSET_MSB (1U << (BITSET_WORD_BITS - 1))
+
+#define BITSET_LIST_SIZE 1024
+
+enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES,
+ BITSET_OP_COPY, BITSET_OP_NOT,
+ BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P,
+ BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P,
+ BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR,
+ BITSET_OP_ANDN, BITSET_OP_ORN,
+ BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR};
+
+/* Return size in bits of bitset SRC. */
+#define BITSET_SIZE_(SRC) (SRC)->b.ops->size (SRC)
+
+/* Return type of bitset SRC. */
+#define BITSET_TYPE_(DST) (DST)->b.ops->type
+
+/* Set bit BITNO in bitset DST. */
+#define BITSET_SET_(DST, BITNO) (DST)->b.ops->set (DST, BITNO)
+
+/* Reset bit BITNO in bitset DST. */
+#define BITSET_RESET_(DST, BITNO) (DST)->b.ops->reset (DST, BITNO)
+
+/* Return non-zero if bit BITNO in bitset SRC is set. */
+#define BITSET_TEST_(SRC, BITNO) (SRC)->b.ops->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)
+
+/* 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)
+
+/* 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_ZERO_(DST) BITSET_OP1_ (DST, BITSET_OP_ZERO);
+
+/* 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);
+
+/* Return DST == SRC. */
+#define BITSET_EQUAL_P_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_EQUAL_P)
+
+/* Return DST == DST | SRC. */
+#define BITSET_SUBSET_P_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_SUBSET_P)
+
+/* 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 = ~SRC. */
+#define BITSET_NOT_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_NOT)
+
+/* DST = SRC1 | SRC2. */
+#define BITSET_OR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\
+ BITSET_OP_OR)
+
+/* DST = SRC1 ^ SRC2. */
+#define BITSET_XOR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\
+ BITSET_OP_XOR)
+
+/* 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. */
+#define BITSET_ORN_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \
+ BITSET_OP_ORN)
+
+/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & SRC2) | SRC3. */
+#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3)\
+ BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_AND_OR)
+
+/* 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)
+
+/* 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)
+
+/* 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)
+
+
+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. */
+};
+
+
+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;
+};
+
+#define BITSET_COMPATIBLE_(BSET1, BSET2) ((BSET1)->b.ops == (BSET2)->b.ops)
+
+#if BITSET_CHECK
+#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 ();
+#else
+#define BITSET_CHECK2_(DST, SRC)
+
+#define BITSET_CHECK3_(DST, SRC1, SRC2)
+
+#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3)
+#endif
+
+extern int bitset_op4 PARAMS ((bitset, bitset, bitset, bitset,
+ enum bitset_ops op));
+
+#endif /* _BBITSET_H */
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- 22-fyi-update-bitset.patch,
Akim Demaille <=