[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: 64-bit masks
> 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) );
/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML mouse%rodents-montreal.org@localhost
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
Main Index |
Thread Index |