From ae6bdfaddd4711e1ccdc3bebb8a4c68aeb649992 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Wed, 18 Nov 2020 07:48:25 +0100 Subject: [PATCH] bitset: use ffs where possible in the table implementation * lib/bitset/table.c (tbitset_list): Use BITSET_FOR_EACH_BIT. --- ChangeLog | 5 +++ lib/bitset/table.c | 104 ++++++++++++--------------------------------- 2 files changed, 31 insertions(+), 78 deletions(-) diff --git a/ChangeLog b/ChangeLog index 50f5deb088..5880f9032a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,8 @@ +2020-11-19 Akim Demaille + + bitset: use ffs where possible in the table implementation + * lib/bitset/table.c (tbitset_list): Use BITSET_FOR_EACH_BIT. + 2020-11-19 Akim Demaille bitset: check empty and full bitsets diff --git a/lib/bitset/table.c b/lib/bitset/table.c index d111e02037..3643b60745 100644 --- a/lib/bitset/table.c +++ b/lib/bitset/table.c @@ -623,18 +623,14 @@ tbitset_list (bitset bset, bitset_bindex *list, { bitset_word word = srcp[windex - woffset] >> (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; } @@ -649,7 +645,6 @@ tbitset_list (bitset bset, bitset_bindex *list, for (; eindex < size; eindex++) { - tbitset_elt *elt = elts[eindex]; if (!elt) continue; @@ -666,69 +661,25 @@ tbitset_list (bitset bset, bitset_bindex *list, #if TBITSET_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 for (int i = 0; i < TBITSET_ELT_WORDS; i++, windex++) { - bitno = windex * BITSET_WORD_BITS; - - word = srcp[i]; + 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; + bitno = windex * BITSET_WORD_BITS; } #endif } @@ -736,24 +687,21 @@ tbitset_list (bitset bset, bitset_bindex *list, { /* Tread more carefully since we need to check if array overflows. */ - - for (int i = 0; i < TBITSET_ELT_WORDS; i++, windex++) + for (int i = 0; i < TBITSET_ELT_WORDS; i++) { + 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; - - for (bitset_word word = srcp[i]; word; bitno++) - { - if (word & 1) - { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } - } - word >>= 1; - } } } } -- 2.39.5