From 84e08e17163c62ea0f4d2847471a9636e24d3c4d Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Sun, 29 Nov 2020 15:55:35 +0100 Subject: [PATCH] bitset: use integer_length in vector implementation * lib/bitset/array.c (vbitset_list_reverse): Use BITSET_FOR_EACH_BIT_REVERSE. --- ChangeLog | 6 ++++++ lib/bitset/vector.c | 23 +++++++++++------------ 2 files changed, 17 insertions(+), 12 deletions(-) diff --git a/ChangeLog b/ChangeLog index c3c5574f8e..b03ea1cd77 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2020-11-29 Akim Demaille + + bitset: use integer_length in vector implementation + * lib/bitset/array.c (vbitset_list_reverse): Use + BITSET_FOR_EACH_BIT_REVERSE. + 2020-11-29 Akim Demaille bitset: use integer_length in array implementation diff --git a/lib/bitset/vector.c b/lib/bitset/vector.c index 4c0c9dbfd2..9f1c08e774 100644 --- a/lib/bitset/vector.c +++ b/lib/bitset/vector.c @@ -152,11 +152,11 @@ static bitset_bindex vbitset_list_reverse (bitset src, bitset_bindex *list, bitset_bindex num, bitset_bindex *next) { + /* FIXME: almost a duplicate of abitset_list_reverse. Factor? */ + bitset_bindex rbitno = *next; bitset_word *srcp = VBITSET_WORDS (src); bitset_bindex n_bits = BITSET_SIZE_ (src); - bitset_bindex rbitno = *next; - /* If num is 1, we could speed things up with a binary search of the word of interest. */ @@ -173,19 +173,18 @@ vbitset_list_reverse (bitset src, bitset_bindex *list, do { - bitset_word word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); - for (; word; bitcnt--) + bitset_word word = srcp[windex]; + if (bitcnt + 1 < BITSET_WORD_BITS) + /* We're starting in the middle of a word: smash bits to ignore. */ + word &= ((bitset_word) 1 << (bitcnt + 1)) - 1; + BITSET_FOR_EACH_BIT_REVERSE(pos, word) { - if (word & BITSET_MSB) + list[count++] = bitoff + pos; + if (count >= num) { - list[count++] = bitoff + bitcnt; - if (count >= num) - { - *next = n_bits - (bitoff + bitcnt); - return count; - } + *next = n_bits - (bitoff + pos); + return count; } - word <<= 1; } bitoff -= BITSET_WORD_BITS; bitcnt = BITSET_WORD_BITS - 1; -- 2.39.5