From b668eb60de0f35ea012de87a6005892fb3127ffa Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Mon, 16 Nov 2020 07:49:08 +0100 Subject: [PATCH] bitset: use ffs where possible in the list implementation * lib/bitset/list.c (lbitset_list): Use BITSET_FOR_EACH_BIT. --- ChangeLog | 5 +++ lib/bitset/list.c | 100 +++++++++++----------------------------------- 2 files changed, 28 insertions(+), 77 deletions(-) diff --git a/ChangeLog b/ChangeLog index 8ee603345f..42996e590f 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,8 @@ +2020-11-17 Akim Demaille + + bitset: use ffs where possible in the list implementation + * lib/bitset/list.c (lbitset_list): Use BITSET_FOR_EACH_BIT. + 2020-11-17 Akim Demaille bitset: use ffs where possible in array implementation diff --git a/lib/bitset/list.c b/lib/bitset/list.c index dc00fdc294..96f1630879 100644 --- a/lib/bitset/list.c +++ b/lib/bitset/list.c @@ -691,19 +691,14 @@ lbitset_list (bitset bset, bitset_bindex *list, for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) { bitset_word word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS); - - for (; word; 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; } bitno = (windex + 1) * BITSET_WORD_BITS; } @@ -717,14 +712,11 @@ lbitset_list (bitset bset, bitset_bindex *list, } } - - /* If num is 1, we could speed things up with a binary search - of the word of interest. */ - while (elt) { bitset_word *srcp = elt->words; + /* Is there enough room to avoid checking in each iteration? */ if ((count + LBITSET_ELT_BITS) < num) { /* The coast is clear, plant boot! */ @@ -732,42 +724,15 @@ lbitset_list (bitset bset, bitset_bindex *list, #if LBITSET_ELT_WORDS == 2 bitset_word word = srcp[0]; if (word) - { - if (!(word & 0xffff)) - { - word >>= 16; - bitno += 16; - } - if (!(word & 0xff)) - { - word >>= 8; - bitno += 8; - } - for (; word; bitno++) - { - if (word & 1) - list[count++] = bitno; - word >>= 1; - } - } + BITSET_FOR_EACH_BIT (pos, word) + list[count++] = bitno + pos; windex++; bitno = windex * BITSET_WORD_BITS; word = srcp[1]; if (word) - { - if (!(word & 0xffff)) - { - word >>= 16; - bitno += 16; - } - for (; word; bitno++) - { - if (word & 1) - list[count++] = bitno; - word >>= 1; - } - } + BITSET_FOR_EACH_BIT (pos, word) + list[count++] = bitno + pos; windex++; bitno = windex * BITSET_WORD_BITS; #else @@ -775,24 +740,8 @@ lbitset_list (bitset bset, bitset_bindex *list, { bitset_word word = srcp[i]; if (word) - { - if (!(word & 0xffff)) - { - word >>= 16; - bitno += 16; - } - if (!(word & 0xff)) - { - word >>= 8; - bitno += 8; - } - for (; word; bitno++) - { - if (word & 1) - list[count++] = bitno; - word >>= 1; - } - } + BITSET_FOR_EACH_BIT (pos, word) + list[count++] = bitno + pos; windex++; bitno = windex * BITSET_WORD_BITS; } @@ -802,22 +751,19 @@ lbitset_list (bitset bset, bitset_bindex *list, { /* Tread more carefully since we need to check if array overflows. */ - for (int i = 0; i < LBITSET_ELT_WORDS; i++) { - for (bitset_word word = srcp[i]; word; bitno++) - { - if (word & 1) - { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } - } - word >>= 1; - } + bitset_word word = srcp[i]; + if (word) + BITSET_FOR_EACH_BIT (pos, word) + { + list[count++] = bitno + pos; + if (count >= num) + { + *next = bitno + pos + 1; + return count; + } + } windex++; bitno = windex * BITSET_WORD_BITS; } -- 2.39.5