1 /* bitmaps and bitmap operations */
6 * Bitmaps are arrays of unsigned ints, filled with bits in most-
7 * significant-first order. So bitmap[0] shall contain the bits from
8 * 0 to 31 on a 32bit architecture, bitmap[1] - 32-63, and so forth.
10 * The callers are responsible to do all the bounds-checking.
12 enum { BITS_PER_BITMAP_ELEM = 8 * sizeof(unsigned) };
14 typedef unsigned bitmap_elem_t;
16 /* returned is the unshifted bit state. IOW: NOT 0 or 1, but something
17 * like 0x00001000 or 0x40000000 */
19 bitmap_elem_t bitmap_test_bit(const bitmap_elem_t* bits, unsigned bit)
21 if ( sizeof(*bits) == 4 )
22 return bits[bit >> 5] & (0x80000000 >> (bit & 0x1f));
23 else if ( sizeof(*bits) == 8 )
24 return bits[bit >> 6] & (0x8000000000000000ull >> (bit & 0x3f));
27 return bits[bit / BITS_PER_BITMAP_ELEM] &
28 1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1);
33 bitmap_elem_t bitmap_set_bit(bitmap_elem_t* bits, unsigned bit)
35 if ( sizeof(*bits) == 4 )
36 return bits[bit >> 5] |= (0x80000000 >> (bit & 0x1f));
37 else if ( sizeof(*bits) == 8 )
38 return bits[bit >> 6] |= (0x8000000000000000ull >> (bit & 0x3f));
41 return bits[bit / BITS_PER_BITMAP_ELEM] |=
42 1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1);
46 /* pos must position the bits inside of a bitmap element, otherwise
47 * the index shift puts the bits in the wrong word (for simplicity).
48 * Only low 8 bits of b8 shall be used */
50 void bitmap_set_8bits_fast(bitmap_elem_t* bits, unsigned pos, unsigned b8)
52 if ( sizeof(*bits) == 4 )
53 bits[pos >> 5] |= b8 << (24 - (pos & 0x1f));
54 else if ( sizeof(*bits) == 8 )
55 bits[pos >> 6] |= b8 << (56 - (pos & 0x3f));
58 bits[pos / BITS_PER_BITMAP_ELEM] |=
59 b8 << (BITS_PER_BITMAP_ELEM - 8 - pos % BITS_PER_BITMAP_ELEM);
64 bitmap_elem_t bitmap_clear_bit(bitmap_elem_t* bits, unsigned bit)
66 if ( sizeof(*bits) == 4 )
67 return bits[bit >> 5] &= ~(0x80000000 >> (bit & 0x1f));
68 else if ( sizeof(*bits) == 8 )
69 return bits[bit >> 6] &= ~(0x8000000000000000ull >> (bit & 0x3f));
72 return bits[bit / BITS_PER_BITMAP_ELEM] &=
73 ~(1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1));
77 #endif /* _BITMAPS_H_ */