bug-gnulib
[Top][All Lists]
Advanced

[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?


reply via email to

[Prev in Thread] Current Thread [Next in Thread]