git.ozlabs.org Git - ccan/blob - 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