tech-userlevel archive

[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


Home | Main Index | Thread Index | Old Index