[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 5/7] bitset: use integrer_length in vector implementation
From: |
Akim Demaille |
Subject: |
[PATCH 5/7] bitset: use integrer_length in vector implementation |
Date: |
Sun, 29 Nov 2020 17:42:19 +0100 |
* lib/bitset/array.c (vbitset_list_reverse): Use
BITSET_FOR_EACH_BIT_REVERSE.
---
ChangeLog | 6 ++++++
lib/bitset/vector.c | 23 +++++++++++------------
2 files changed, 17 insertions(+), 12 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index ecf0fc054..37024c15c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2020-11-29 Akim Demaille <akim@lrde.epita.fr>
+
+ bitset: use integrer_length in vector implementation
+ * lib/bitset/array.c (vbitset_list_reverse): Use
+ BITSET_FOR_EACH_BIT_REVERSE.
+
2020-11-29 Akim Demaille <akim@lrde.epita.fr>
bitset: use integrer_length in array implementation
diff --git a/lib/bitset/vector.c b/lib/bitset/vector.c
index 4c0c9dbfd..9f1c08e77 100644
--- a/lib/bitset/vector.c
+++ b/lib/bitset/vector.c
@@ -152,11 +152,11 @@ static bitset_bindex
vbitset_list_reverse (bitset src, bitset_bindex *list,
bitset_bindex num, bitset_bindex *next)
{
+ /* FIXME: almost a duplicate of abitset_list_reverse. Factor? */
+ bitset_bindex rbitno = *next;
bitset_word *srcp = VBITSET_WORDS (src);
bitset_bindex n_bits = BITSET_SIZE_ (src);
- bitset_bindex rbitno = *next;
-
/* If num is 1, we could speed things up with a binary search
of the word of interest. */
@@ -173,19 +173,18 @@ vbitset_list_reverse (bitset src, bitset_bindex *list,
do
{
- bitset_word word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
- for (; word; bitcnt--)
+ bitset_word word = srcp[windex];
+ if (bitcnt + 1 < BITSET_WORD_BITS)
+ /* We're starting in the middle of a word: smash bits to ignore. */
+ word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
+ BITSET_FOR_EACH_BIT_REVERSE(pos, word)
{
- if (word & BITSET_MSB)
+ list[count++] = bitoff + pos;
+ if (count >= num)
{
- list[count++] = bitoff + bitcnt;
- if (count >= num)
- {
- *next = n_bits - (bitoff + bitcnt);
- return count;
- }
+ *next = n_bits - (bitoff + pos);
+ return count;
}
- word <<= 1;
}
bitoff -= BITSET_WORD_BITS;
bitcnt = BITSET_WORD_BITS - 1;
--
2.29.2
- [PATCH 0/7] bitset: use integrer_length in reverse iterations, Akim Demaille, 2020/11/29
- [PATCH 1/7] bitset: tests: check BITSET_FOR_EACH_REVERSE, Akim Demaille, 2020/11/29
- [PATCH 2/7] bitset: style: sort header, Akim Demaille, 2020/11/29
- [PATCH 3/7] bitset: style: use consistent names, Akim Demaille, 2020/11/29
- [PATCH 4/7] bitset: use integrer_length in array implementation, Akim Demaille, 2020/11/29
- [PATCH 5/7] bitset: use integrer_length in vector implementation,
Akim Demaille <=
- [PATCH 6/7] bitset: use integrer_length in list implementation, Akim Demaille, 2020/11/29
- [PATCH 7/7] bitset: use integrer_length in table implementation, Akim Demaille, 2020/11/29