[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 4/6] bitset: use ffs where possible in the vector implementation
From: |
Akim Demaille |
Subject: |
[PATCH 4/6] bitset: use ffs where possible in the vector implementation |
Date: |
Thu, 19 Nov 2020 07:01:53 +0100 |
* lib/bitset/vector.c (vbitset_list): Use BITSET_FOR_EACH_BIT.
---
ChangeLog | 5 ++++
lib/bitset/vector.c | 57 +++++++++++++++++----------------------------
2 files changed, 27 insertions(+), 35 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 951b82b04..2bc68b9dc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2020-11-19 Akim Demaille <akim@lrde.epita.fr>
+
+ bitset: use ffs where possible in the vector implementation
+ * lib/bitset/vector.c (vbitset_list): Use BITSET_FOR_EACH_BIT.
+
2020-11-19 Akim Demaille <akim@lrde.epita.fr>
bitset: use ffs where possible in the table implementation
diff --git a/lib/bitset/vector.c b/lib/bitset/vector.c
index fe14d6703..4c0c9dbfd 100644
--- a/lib/bitset/vector.c
+++ b/lib/bitset/vector.c
@@ -204,6 +204,7 @@ static bitset_bindex
vbitset_list (bitset src, bitset_bindex *list,
bitset_bindex num, bitset_bindex *next)
{
+ /* FIXME: almost a duplicate of abitset_list. Factor? */
bitset_windex size = VBITSET_SIZE (src);
bitset_word *srcp = VBITSET_WORDS (src);
bitset_bindex bitno = *next;
@@ -211,7 +212,6 @@ vbitset_list (bitset src, bitset_bindex *list,
bitset_windex windex;
bitset_bindex bitoff;
- bitset_word word;
if (!bitno)
{
@@ -242,19 +242,16 @@ vbitset_list (bitset src, bitset_bindex *list,
on the previous call to this function. */
bitoff = windex * BITSET_WORD_BITS;
- word = srcp[windex] >> bitno;
- for (bitno = bitoff + bitno; word; bitno++)
+ bitset_word word = srcp[windex] >> bitno;
+ bitno = bitoff + bitno;
+ BITSET_FOR_EACH_BIT (pos, word)
{
- if (word & 1)
+ list[count++] = bitno + pos;
+ if (count >= num)
{
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
+ *next = bitno + pos + 1;
+ return count;
}
- word >>= 1;
}
windex++;
}
@@ -263,34 +260,24 @@ vbitset_list (bitset src, bitset_bindex *list,
for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
{
- if (!(word = srcp[windex]))
+ bitset_word word = srcp[windex];
+ if (!word)
continue;
+ /* Is there enough room to avoid checking in each iteration? */
if ((count + BITSET_WORD_BITS) < num)
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
+ BITSET_FOR_EACH_BIT (pos, word)
+ list[count++] = bitoff + pos;
else
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- }
+ BITSET_FOR_EACH_BIT (pos, word)
+ {
+ list[count++] = bitoff + pos;
+ if (count >= num)
+ {
+ *next = bitoff + pos + 1;
+ return count;
+ }
+ }
}
*next = bitoff;
--
2.29.2
- [PATCH 0/6] bitset: more conversions to ffs, Akim Demaille, 2020/11/19
- [PATCH 1/6] bitset: be sure to always return a value, Akim Demaille, 2020/11/19
- [PATCH 2/6] bitset: check empty and full bitsets, Akim Demaille, 2020/11/19
- [PATCH 3/6] bitset: use ffs where possible in the table implementation, Akim Demaille, 2020/11/19
- [PATCH 4/6] bitset: use ffs where possible in the vector implementation,
Akim Demaille <=
- [PATCH 5/6] bitset: tests: try harder to break it, Akim Demaille, 2020/11/19
- [PATCH 6/6] bitset: exercise the stats too, Akim Demaille, 2020/11/19
- [PATCH 6/6] bitset: tests: exercise the stats too, Akim Demaille, 2020/11/19
- Re: [PATCH 0/6] bitset: more conversions to ffs, Bruno Haible, 2020/11/19