diff options
| author | Akim Demaille <akim.demaille@gmail.com> | 2020-11-16 07:49:08 +0100 |
|---|---|---|
| committer | Akim Demaille <akim.demaille@gmail.com> | 2020-11-18 06:50:28 +0100 |
| commit | b668eb60de0f35ea012de87a6005892fb3127ffa (patch) | |
| tree | 4c1c1237a9921e20144f4144999e75480e8e4b2a | |
| parent | abc5606bb1b591cf03d51029e4d5d532d16b717e (diff) | |
| download | gnulib-b668eb60de0f35ea012de87a6005892fb3127ffa.tar.gz gnulib-b668eb60de0f35ea012de87a6005892fb3127ffa.tar.bz2 | |
bitset: use ffs where possible in the list implementation
* lib/bitset/list.c (lbitset_list): Use BITSET_FOR_EACH_BIT.
| -rw-r--r-- | ChangeLog | 5 | ||||
| -rw-r--r-- | lib/bitset/list.c | 100 |
2 files changed, 28 insertions, 77 deletions
@@ -1,5 +1,10 @@ 2020-11-17 Akim Demaille <akim@lrde.epita.fr> + 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 <akim@lrde.epita.fr> + bitset: use ffs where possible in array implementation * lib/bitset/array.c (abitset_small_list): Use BITSET_FOR_EACH_BIT. 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; } |