[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Bitset patches
|
From: |
Akim Demaille |
|
Subject: |
Re: Bitset patches |
|
Date: |
28 Aug 2002 16:36:20 +0200 |
|
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Honest Recruiter) |
Paul Eggert> Here are the patches I installed.
Thanks Paul! But the following bits of your patch are related to
Michael's implementation of bitsets, which is also used in GCC. So I
guess this should be applied to the main sources.
2002-08-12 Paul Eggert <address@hidden>
* lib/abitset.c (abitset_reverse_list, ebitset_reverse_list):
Do not assume that bitset_windex is the same width as unsigned.
* lib/abitset.c (abitset_unused_clear): Do not assume that
bitset_word is the same width as int.
* lib/bbitset.h (BITSET_INDEX_MAX, BITSET_MSB): Likewise.
* lib/bitset.h (bitset_set, bitset_reset): Likewise.
* lib/bitset_stats.c (bitset_stats_set, bitset_stats_reset): Likewise.
* lib/ebitset.c (ebitset_set, ebitset_reset): Likewise.
* lib/lbitset.c (lbitset_set, lbitset_reset): Likewise.
* lib/abitset.c (abitset_op1): Use -1, not ~0, as memset arg (for
portability to one's complement hosts!).
* lib/ebitset.c (ebitset_op1): Likewise.
* lib/lbitset.c (lbitset_op1): Likewise.
* lib/bbitset.h (BITSET_WORD_BITS): Now of type unsigned, not
size_t; the old version tried to do this but casted improperly.
(bitset_bindex, bitset_windex): Now size_t, not unsigned long.
(bitset_test): Now returns int, not unsigned long.
* lib/bitset_stats.c: Include "gettext.h".
(_): New macro.
(bitset_stats_set, bitset_stats_reset, bitset_stats_test): Don't
name locals "index", as it generates unnecessary warnings on some
hosts that have an "index" function.
* lib/bitset_stats.c (bitset_stats_print_1, bitset_stats_print,
bitset_stats_read, bitset_stats_write): Wrap strings in _() if
they need translation.
diff -pru .del/bison2/lib/abitset.c bison/lib/abitset.c
--- .del/bison2/lib/abitset.c 2002-07-02 06:51:26.000000000 -0700
+++ bison/lib/abitset.c 2002-08-12 07:09:24.000000000 -0700
@@ -208,8 +208,7 @@ abitset_reverse_list (src, list, num, ne
bitcnt = bitno % BITSET_WORD_BITS;
bitoff = windex * BITSET_WORD_BITS;
- for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS,
- bitcnt = BITSET_WORD_BITS - 1)
+ do
{
word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
for (; word; bitcnt--)
@@ -225,7 +224,10 @@ abitset_reverse_list (src, list, num, ne
}
word <<= 1;
}
+ bitoff -= BITSET_WORD_BITS;
+ bitcnt = BITSET_WORD_BITS - 1;
}
+ while (windex--);
*next = n_bits - (bitoff + 1);
return count;
@@ -348,7 +350,7 @@ abitset_unused_clear (dst)
last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS;
if (last_bit)
ABITSET_WORDS (dst)[dst->b.csize - 1] &=
- (bitset_word) ((1 << last_bit) - 1);
+ ((bitset_word) 1 << last_bit) - 1;
}
@@ -370,7 +372,7 @@ abitset_op1 (dst, op)
break;
case BITSET_OP_ONES:
- memset (dstp, ~0, bytes);
+ memset (dstp, -1, bytes);
abitset_unused_clear (dst);
break;
diff -pru .del/bison2/lib/bbitset.h bison/lib/bbitset.h
--- .del/bison2/lib/bbitset.h 2002-07-02 06:51:26.000000000 -0700
+++ bison/lib/bbitset.h 2002-08-12 07:13:56.000000000 -0700
@@ -45,17 +45,19 @@ enum bitset_alloc_type {BITSET_MALLOC, B
/* Data type used to store a word of bits. */
typedef unsigned long bitset_word;
-#define BITSET_WORD_BITS ((unsigned) CHAR_BIT * sizeof (bitset_word))
+#define BITSET_WORD_BITS ((unsigned) (CHAR_BIT * sizeof (bitset_word)))
-/* Bit index. */
-typedef unsigned long bitset_bindex;
+/* Bit index. In theory we might need a type wider than size_t, but
+ in practice we lose at most a factor of CHAR_BIT by going with
+ size_t, and that is good enough. */
+typedef size_t bitset_bindex;
/* Word index. */
-typedef unsigned long bitset_windex;
+typedef size_t bitset_windex;
-#define BITSET_INDEX_MAX ((1U << (BITSET_WORD_BITS - 1)))
+#define BITSET_INDEX_MAX ((bitset_word) 1 << (BITSET_WORD_BITS - 1))
-#define BITSET_MSB (1U << (BITSET_WORD_BITS - 1))
+#define BITSET_MSB ((bitset_word) 1 << (BITSET_WORD_BITS - 1))
#define BITSET_LIST_SIZE 1024
diff -pru .del/bison2/lib/bitset.h bison/lib/bitset.h
--- .del/bison2/lib/bitset.h 2002-07-02 06:51:26.000000000 -0700
+++ bison/lib/bitset.h 2002-08-12 07:19:02.000000000 -0700
@@ -107,7 +107,7 @@ static inline void bitset_set (bset, bit
bitset_windex offset = index - bset->b.cindex;
if (offset < bset->b.csize)
- bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
+ bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
else
BITSET_SET_ (bset, bitno);
}
@@ -122,7 +122,7 @@ static inline void bitset_reset (bset, b
bitset_windex offset = index - bset->b.cindex;
if (offset < bset->b.csize)
- bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
+ bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
else
BITSET_RESET_ (bset, bitno);
}
@@ -154,7 +154,8 @@ do
\
bitset_windex _offset = _index - (bset)->b.cindex; \
\
if (_offset < (bset)->b.csize) \
- (bset)->b.cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); \
+ (bset)->b.cdata[_offset] |= \
+ ((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
else \
BITSET_SET_ ((bset), _bitno); \
} while (0)
@@ -169,7 +170,8 @@ do
\
bitset_windex _offset = _index - (bset)->b.cindex; \
\
if (_offset < (bset)->b.csize) \
- (bset)->b.cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \
+ (bset)->b.cdata[_offset] &= \
+ ~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
else \
BITSET_RESET_ ((bset), _bitno); \
} while (0)
@@ -178,9 +180,11 @@ do
\
/* Test bit BITNO in bitset BSET. */
#define bitset_test(bset, bitno) \
(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
- ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
- >> ((bitno) % BITSET_WORD_BITS)) & 1 \
- : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
+ ? (((int) \
+ ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
+ >> ((bitno) % BITSET_WORD_BITS))) \
+ & 1) \
+ : BITSET_TEST_ ((bset), (bitno)))
#endif
diff -pru .del/bison2/lib/bitset_stats.c bison/lib/bitset_stats.c
--- .del/bison2/lib/bitset_stats.c 2002-07-02 06:51:26.000000000 -0700
+++ bison/lib/bitset_stats.c 2002-08-12 07:16:49.000000000 -0700
@@ -38,6 +38,8 @@
#include <string.h>
#include <stdio.h>
+#include "gettext.h"
+#define _(Msgid) gettext (Msgid)
/* Configuration macros. */
#define BITSET_STATS_FILE "bitset.dat"
@@ -221,28 +223,28 @@ bitset_stats_print_1 (file, name, stats)
return;
fprintf (file, "%s:\n", name);
- fprintf (file, "%d bitset_allocs, %d freed (%.2f%%).\n",
+ fprintf (file, _("%d bitset_allocs, %d freed (%.2f%%).\n"),
stats->allocs, stats->frees,
stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
- fprintf (file, "%d bitset_sets, %d cached (%.2f%%)\n",
+ fprintf (file, _("%d bitset_sets, %d cached (%.2f%%)\n"),
stats->sets, stats->cache_sets,
stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
- fprintf (file, "%d bitset_resets, %d cached (%.2f%%)\n",
+ fprintf (file, _("%d bitset_resets, %d cached (%.2f%%)\n"),
stats->resets, stats->cache_resets,
stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
- fprintf (file, "%d bitset_tests, %d cached (%.2f%%)\n",
+ fprintf (file, _("%d bitset_tests, %d cached (%.2f%%)\n"),
stats->tests, stats->cache_tests,
stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
- fprintf (file, "%d bitset_lists\n", stats->lists);
+ fprintf (file, _("%d bitset_lists\n"), stats->lists);
- bitset_log_histogram_print (file, name, "count log histogram\n",
+ bitset_log_histogram_print (file, name, _("count log histogram\n"),
BITSET_LOG_COUNT_BINS, stats->list_counts);
- bitset_log_histogram_print (file, name, "size log histogram\n",
+ bitset_log_histogram_print (file, name, _("size log histogram\n"),
BITSET_LOG_SIZE_BINS, stats->list_sizes);
- bitset_percent_histogram_print (file, name, "density histogram\n",
+ bitset_percent_histogram_print (file, name, _("density histogram\n"),
BITSET_DENSITY_BINS, stats->list_density);
}
@@ -259,10 +261,10 @@ bitset_stats_print (file, verbose)
if (!bitset_stats_info)
return;
- fprintf (file, "Bitset statistics:\n\n");
+ fprintf (file, _("Bitset statistics:\n\n"));
if (bitset_stats_info->runs > 1)
- fprintf (file, "Accumulated runs = %d\n", bitset_stats_info->runs);
+ fprintf (file, _("Accumulated runs = %d\n"), bitset_stats_info->runs);
for (i = 0; i < BITSET_TYPE_NUM; i++)
bitset_stats_print_1 (file, names[i], &bitset_stats_info->types[i]);
@@ -306,9 +308,9 @@ bitset_stats_read (filename)
1, file) != 1)
{
if (ferror (file))
- perror ("Could not read stats file.");
+ perror (_("Could not read stats file."));
else
- fprintf (stderr, "Bad stats file size.\n");
+ fprintf (stderr, _("Bad stats file size.\n"));
}
fclose (file);
}
@@ -334,11 +336,11 @@ bitset_stats_write (filename)
{
if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
1, file) != 1)
- perror ("Could not write stats file.");
+ perror (_("Could not write stats file."));
fclose (file);
}
else
- perror ("Could not open stats file for writing.");
+ perror (_("Could not open stats file for writing."));
}
@@ -365,14 +367,14 @@ bitset_stats_set (dst, bitno)
bitset_bindex bitno;
{
bitset bset = dst->s.bset;
- bitset_windex index = bitno / BITSET_WORD_BITS;
- bitset_windex offset = index - bset->b.cindex;
+ bitset_windex wordno = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = wordno - bset->b.cindex;
BITSET_STATS_SETS_INC (bset);
if (offset < bset->b.csize)
{
- bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
+ bset->b.cdata[offset] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
BITSET_STATS_CACHE_SETS_INC (bset);
}
else
@@ -386,14 +388,15 @@ bitset_stats_reset (dst, bitno)
bitset_bindex bitno;
{
bitset bset = dst->s.bset;
- bitset_windex index = bitno / BITSET_WORD_BITS;
- bitset_windex offset = index - bset->b.cindex;
+ bitset_windex wordno = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = wordno - bset->b.cindex;
BITSET_STATS_RESETS_INC (bset);
if (offset < bset->b.csize)
{
- bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
+ bset->b.cdata[offset] &=
+ ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
BITSET_STATS_CACHE_RESETS_INC (bset);
}
else
@@ -407,8 +410,8 @@ bitset_stats_test (src, bitno)
bitset_bindex bitno;
{
bitset bset = src->s.bset;
- bitset_windex index = bitno / BITSET_WORD_BITS;
- bitset_windex offset = index - bset->b.cindex;
+ bitset_windex wordno = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = wordno - bset->b.cindex;
BITSET_STATS_TESTS_INC (bset);
diff -pru .del/bison2/lib/ebitset.c bison/lib/ebitset.c
--- .del/bison2/lib/ebitset.c 2002-07-02 06:51:26.000000000 -0700
+++ bison/lib/ebitset.c 2002-08-12 07:20:35.000000000 -0700
@@ -578,7 +578,8 @@ ebitset_set (dst, bitno)
ebitset_elt_find (dst, windex, EBITSET_CREATE);
- dst->b.cdata[windex - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS));
+ dst->b.cdata[windex - dst->b.cindex] |=
+ (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
}
@@ -593,7 +594,8 @@ ebitset_reset (dst, bitno)
if (!ebitset_elt_find (dst, windex, EBITSET_FIND))
return;
- dst->b.cdata[windex - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
+ dst->b.cdata[windex - dst->b.cindex] &=
+ ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
/* If all the data is zero, perhaps we should remove it now...
However, there is a good chance that the element will be needed
@@ -646,7 +648,6 @@ ebitset_reverse_list (bset, list, num, n
bitset_windex woffset;
bitset_bindex count;
bitset_windex size;
- bitset_word word;
ebitset_elts *elts;
if (EBITSET_OP_ZERO_P (bset))
@@ -674,40 +675,48 @@ ebitset_reverse_list (bset, list, num, n
bcount = bitno % BITSET_WORD_BITS;
boffset = windex * BITSET_WORD_BITS;
- for (; eindex != ~0U;
- boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS, eindex--)
+ do
{
ebitset_elt *elt;
- bitset_word *srcp;
elt = elts[eindex];
- if (!elt)
- continue;
-
- srcp = EBITSET_WORDS (elt);
-
- for (; woffset != ~0U; woffset--, boffset -= BITSET_WORD_BITS,
- bcount = BITSET_WORD_BITS - 1)
+ if (elt)
{
- word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
+ bitset_word *srcp;
+
+ srcp = EBITSET_WORDS (elt);
- for (; word; bcount--)
+ do
{
- if (word & BITSET_MSB)
+ bitset_word word;
+
+ word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
+
+ for (; word; bcount--)
{
- list[count++] = boffset + bcount;
- if (count >= num)
+ if (word & BITSET_MSB)
{
- *next = n_bits - (boffset + bcount);
- return count;
+ list[count++] = boffset + bcount;
+ if (count >= num)
+ {
+ *next = n_bits - (boffset + bcount);
+ return count;
+ }
}
+ word <<= 1;
}
- word <<= 1;
+
+ boffset -= BITSET_WORD_BITS;
+ bcount = BITSET_WORD_BITS - 1;
}
+ while (woffset--);
+
+ woffset = EBITSET_ELT_WORDS;
}
- woffset = EBITSET_ELT_WORDS;
+ boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
}
+ while (eindex--);
*next = n_bits - (boffset + 1);
return count;
@@ -878,7 +887,7 @@ ebitset_op1 (dst, op)
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)));
+ memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
}
break;
diff -pru .del/bison2/lib/lbitset.c bison/lib/lbitset.c
--- .del/bison2/lib/lbitset.c 2002-07-02 06:51:26.000000000 -0700
+++ bison/lib/lbitset.c 2002-08-12 07:22:08.000000000 -0700
@@ -585,7 +585,8 @@ lbitset_set (dst, bitno)
lbitset_elt_find (dst, windex, LBITSET_CREATE);
- dst->b.cdata[windex - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS));
+ dst->b.cdata[windex - dst->b.cindex] |=
+ (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
}
@@ -600,7 +601,8 @@ lbitset_reset (dst, bitno)
if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
return;
- dst->b.cdata[windex - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
+ dst->b.cdata[windex - dst->b.cindex] &=
+ ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
/* If all the data is zero, perhaps we should unlink it now... */
}
@@ -951,7 +953,7 @@ lbitset_op1 (dst, op)
{
/* Create new elements if they cannot be found. */
elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
- memset (elt->words, ~0, sizeof (elt->words));
+ memset (elt->words, -1, sizeof (elt->words));
}
break;