Merge.
[ccan] / junkcode / fork0@users.sf.net-bitmaps / bitmaps.h
1 /* bitmaps and bitmap operations */
2 #ifndef _BITMAPS_H_
3 #define _BITMAPS_H_
4
5 /*
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.
9  *
10  * The callers are responsible to do all the bounds-checking.
11  */
12 enum { BITS_PER_BITMAP_ELEM = 8 * sizeof(unsigned) };
13
14 typedef unsigned bitmap_elem_t;
15
16 /* returned is the unshifted bit state. IOW: NOT 0 or 1, but something
17  * like 0x00001000 or 0x40000000 */
18 static inline
19 bitmap_elem_t bitmap_test_bit(const bitmap_elem_t* bits, unsigned bit)
20 {
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));
25     else
26     {
27         return bits[bit / BITS_PER_BITMAP_ELEM] &
28             1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1);
29     }
30 }
31
32 static inline
33 bitmap_elem_t bitmap_set_bit(bitmap_elem_t* bits, unsigned bit)
34 {
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));
39     else
40     {
41         return bits[bit / BITS_PER_BITMAP_ELEM] |=
42             1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1);
43     }
44 }
45
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 */
49 static inline
50 void bitmap_set_8bits_fast(bitmap_elem_t* bits, unsigned pos, unsigned b8)
51 {
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));
56     else
57     {
58         bits[pos / BITS_PER_BITMAP_ELEM] |=
59             b8 << (BITS_PER_BITMAP_ELEM - 8 - pos % BITS_PER_BITMAP_ELEM);
60     }
61 }
62
63 static inline
64 bitmap_elem_t bitmap_clear_bit(bitmap_elem_t* bits, unsigned bit)
65 {
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));
70     else
71     {
72         return bits[bit / BITS_PER_BITMAP_ELEM] &=
73             ~(1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1));
74     }
75 }
76
77 #endif /* _BITMAPS_H_ */
78