tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: 64-bit masks



On Sun, 29 Nov 2009 23:55:12 -0000, der Mouse <mouse%rodents-montreal.org@localhost> wrote:

Hi, well I really need to find the first free object, not all the
free objects at once.

It also needs to be portable to at least BSD, Linux and Solaris.

On what hardware?  In particular, relying on ffs to be implemented as a
very fast assembly instruction is going to be fairly hardware-specific.

Based on your code, your "first" maps to "least-significant".  In that
case, you may be able to do something useful with the x&~(x-1) trick
(given x, that expression picks out its least-significant set bit).
Given your convention for bit values, you'd have to complement your
mask before using it, but it may still be fast enough to be useful:

int first_free(uint64_t m)
{
 m = (~m) & ~((~m)-1);
 if (! m) return(-1);
 return( ((m & 0xffffffff00000000ULL) ? 32 : 0) +
         ((m & 0xffff0000ffff0000ULL) ? 16 : 0) +
         ((m & 0xff00ff00ff00ff00ULL) ?  8 : 0) +
         ((m & 0xf0f0f0f0f0f0f0f0ULL) ?  4 : 0) +
         ((m & 0xccccccccccccccccULL) ?  2 : 0) +
         ((m & 0x5555555555555555ULL) ?  1 : 0) );
}

Your algorithm doesn't seem to work:

for m = 0x7 (binary 00000111), first_free() returns 2, which is wrong.


Home | Main Index | Thread Index | Old Index