[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: bitpack search in bitsets
From: |
Akim Demaille |
Subject: |
Re: bitpack search in bitsets |
Date: |
Wed, 18 Nov 2020 07:06:58 +0100 |
Bruno,
> Le 17 nov. 2020 à 22:50, Bruno Haible <bruno@clisp.org> a écrit :
>
> Hi Akim,
>
> In gnulib/lib/ssfmalloc-bitmap.h there is a function
>
> /* Returns the smallest index k >= 0 for which the bit packet of c consecutive
> bits (1 <= c <= 32) is all set in the bitmap consisting of num_words words.
> Returns (size_t)(-1) if there is none. */
>
> I can easily extend this to c > 32. So, this will be a one-pass search for
> c consecutive bits in a bitmap, that operates on words and fetches every word
> only twice at most.
>
> Is this something that could be useful for your 'bitset' module?
(FTR, I am not the author, Michael Hayes is. It was a contribution
for GCC, that actually didn't make it into GCC. But I liked it very much
and took it for Bison.)
That doesn't ring any bell. I don't remember I saw any feature in bitset
that depends on consecutive set bits, and a quick search did not find
anything.
Conversely: couldn't ssfmalloc sit on top of bitset?