[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 1/6] bitset: use ffs where possible in array implementation
From: |
Akim Demaille |
Subject: |
[PATCH 1/6] bitset: use ffs where possible in array implementation |
Date: |
Tue, 17 Nov 2020 18:59:24 +0100 |
* lib/bitset/array.c (abitset_small_list): Use BITSET_FOR_EACH_BIT.
---
ChangeLog | 5 +++++
lib/bitset/array.c | 46 +++++++++++++++-------------------------------
2 files changed, 20 insertions(+), 31 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index c8f4ffaac..ba738c8c5 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2020-11-17 Akim Demaille <akim@lrde.epita.fr>
+
+ bitset: use ffs where possible in array implementation
+ * lib/bitset/array.c (abitset_small_list): Use BITSET_FOR_EACH_BIT.
+
2020-11-16 Bruno Haible <bruno@clisp.org>
Fix link errors on platforms with libunistring.
diff --git a/lib/bitset/array.c b/lib/bitset/array.c
index 6c5f7ed34..3f8bcca87 100644
--- a/lib/bitset/array.c
+++ b/lib/bitset/array.c
@@ -62,38 +62,25 @@ abitset_small_list (bitset src, bitset_bindex *list,
word >>= bitno;
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- bitset_bindex count;
+ bitset_bindex count = 0;
+ /* Is there enough room to avoid checking in each iteration? */
if (num >= BITSET_WORD_BITS)
{
- for (count = 0; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
+ BITSET_FOR_EACH_BIT (pos, word)
+ list[count++] = bitno + pos;
+ *next = bitno + BITSET_WORD_BITS;
+ return count;
}
else
- {
- for (count = 0; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- bitno++;
- break;
- }
- }
- word >>= 1;
- }
- }
-
- *next = bitno;
- return count;
+ BITSET_FOR_EACH_BIT (pos, word)
+ {
+ list[count++] = bitno + pos;
+ if (count >= num)
+ {
+ *next = bitno + pos + 1;
+ return count;
+ }
+ }
}
@@ -205,9 +192,6 @@ abitset_list (bitset src, bitset_bindex *list,
if (windex >= size)
return 0;
- /* If num is 1, we could speed things up with a binary search
- of the current word. */
-
bitoff = windex * BITSET_WORD_BITS;
}
else
--
2.29.2
- [PATCH 0/6] bitset: clean up, test, fix, accelerate, Akim Demaille, 2020/11/17
- [PATCH 1/6] bitset: use ffs where possible in array implementation,
Akim Demaille <=
- [PATCH 2/6] bitset: use ffs where possible in the list implementation, Akim Demaille, 2020/11/17
- [PATCH 3/6] bitset: test: run deterministic tests on several bitset sizes, Akim Demaille, 2020/11/17
- [PATCH 4/6] bitset: strengthen tests, Akim Demaille, 2020/11/17
- [PATCH 5/6] bitset: rename internal details for consistency, Akim Demaille, 2020/11/17
- [PATCH 6/6] bitset: fix iteration over table bitsets, Akim Demaille, 2020/11/17
- Re: [PATCH 0/6] bitset: clean up, test, fix, accelerate, Bruno Haible, 2020/11/17