kernel/fiasco/src/lib/libk/bitmap.cpp

   1 INTERFACE:
   2
   3 #include "atomic.h"
   4
   5 template< bool LARGE, unsigned BITS >
   6 class Bitmap_base;
   7
   8 // Implementation for bitmaps bigger than sizeof(unsigned long) * 8
   9 // Derived classes have to make sure to provide the storage space for
  10 // holding the bitmap.
  11 template<unsigned BITS>
  12 class Bitmap_base< true, BITS >
  13 {
  14 public:
  15   enum {
  16     Bpl      = sizeof(unsigned long) * 8,
  17     Nr_elems = (BITS + Bpl - 1) / Bpl,
  18   };
  19
  20   void bit(unsigned long bit, bool on)
  21   {
  22     unsigned long idx = bit / Bpl;
  23     unsigned long b   = bit % Bpl;
  24     _bits[idx] = (_bits[idx] & ~(1UL << b)) | ((unsigned long)on << b);
  25   }
  26
  27   void clear_bit(unsigned long bit)
  28   {
  29     unsigned long idx = bit / Bpl;
  30     unsigned long b   = bit % Bpl;
  31     _bits[idx] &= ~(1UL << b);
  32   }
  33
  34   void set_bit(unsigned long bit)
  35   {
  36     unsigned long idx = bit / Bpl;
  37     unsigned long b   = bit % Bpl;
  38     _bits[idx] |= (1UL << b);
  39   }
  40
  41   unsigned long operator [] (unsigned long bit) const
  42   {
  43     unsigned long idx = bit / Bpl;
  44     unsigned long b   = bit % Bpl;
  45     return _bits[idx] & (1UL << b);
  46   }
  47
  48   bool atomic_get_and_clear(unsigned long bit)
  49   {
  50     unsigned long idx = bit / Bpl;
  51     unsigned long b   = bit % Bpl;
  52     unsigned long v;
  53
  54     if (!(_bits[idx] & (1UL << b)))
  55       return false;
  56
  57     do
  58       {
  59         v = _bits[idx];
  60       }
  61     while (!mp_cas(&_bits[idx], v, v & ~(1UL << b)));
  62
  63     return v & (1UL << b);
  64   }
  65
  66   void atomic_set_bit(unsigned long bit)
  67   {
  68     unsigned long idx = bit / Bpl;
  69     unsigned long b   = bit % Bpl;
  70     atomic_mp_or(&_bits[idx], 1UL << b);
  71   }
  72
  73   void atomic_clear_bit(unsigned long bit)
  74   {
  75     unsigned long idx = bit / Bpl;
  76     unsigned long b   = bit % Bpl;
  77     atomic_mp_and(&_bits[idx], ~(1UL << b));
  78   }
  79
  80   void clear_all()
  81   {
  82     for (unsigned i = 0; i < Nr_elems; ++i)
  83       _bits[i] = 0;
  84   }
  85
  86   bool is_empty() const
  87   {
  88     for (unsigned i = 0; i < Nr_elems; ++i)
  89       if (_bits[i])
  90         return false;
  91     return true;
  92   }
  93
  94   void atomic_or(Bitmap_base const &r)
  95   {
  96     for (unsigned i = 0; i < Nr_elems; ++i)
  97       atomic_mp_or(&_bits[i], r._bits[i]);
  98   }
  99
 100 protected:
 101   Bitmap_base() {}
 102   Bitmap_base(Bitmap_base const &) = delete;
 103   Bitmap_base &operator = (Bitmap_base const &) = delete;
 104
 105
 106   void _or(Bitmap_base const &r)
 107   {
 108     for (unsigned i = 0; i < Nr_elems; ++i)
 109       _bits[i] |= r._bits[i];
 110   }
 111
 112   void _copy(Bitmap_base const &s)
 113   { __builtin_memcpy(_bits, s._bits, Nr_elems * sizeof(_bits[0])); }
 114
 115   unsigned long _bits[Nr_elems];
 116 };
 117
 118 // Implementation for a bitmap up to sizeof(unsigned long) * 8 bits
 119 template<unsigned BITS>
 120 class Bitmap_base<false, BITS>
 121 {
 122 public:
 123   void bit(unsigned long bit, bool on)
 124   {
 125     _bits = (_bits & ~(1UL << bit)) | ((unsigned long)on << bit);
 126   }
 127
 128   void clear_bit(unsigned long bit)
 129   {
 130     _bits &= ~(1UL << bit);
 131   }
 132
 133   void set_bit(unsigned long bit)
 134   {
 135     _bits |= 1UL << bit;
 136   }
 137
 138   unsigned long operator [] (unsigned long bit) const
 139   {
 140     return _bits & (1UL << bit);
 141   }
 142
 143   bool atomic_get_and_clear(unsigned long bit)
 144   {
 145     if (!(_bits & (1UL << bit)))
 146       return false;
 147
 148     unsigned long v;
 149     do
 150       {
 151         v = _bits;
 152       }
 153     while (!mp_cas(&_bits, v, v & ~(1UL << bit)));
 154
 155     return v & (1UL << bit);
 156   }
 157
 158   void atomic_set_bit(unsigned long bit)
 159   {
 160     atomic_mp_or(&_bits, 1UL << bit);
 161   }
 162
 163   void atomic_clear_bit(unsigned long bit)
 164   {
 165     atomic_mp_and(&_bits, ~(1UL << bit));
 166   }
 167
 168   void clear_all()
 169   {
 170     _bits = 0;
 171   }
 172
 173   bool is_empty() const
 174   {
 175     return !_bits;
 176   }
 177
 178   void atomic_or(Bitmap_base const &r)
 179   {
 180     atomic_mp_or(&_bits, r._bits);
 181   }
 182
 183
 184
 185 protected:
 186   enum
 187   {
 188     Bpl      = sizeof(unsigned long) * 8,
 189     Nr_elems = 1,
 190   };
 191   unsigned long _bits;
 192
 193   Bitmap_base() {}
 194   Bitmap_base(Bitmap_base const &) = delete;
 195   Bitmap_base &operator = (Bitmap_base const &) = delete;
 196
 197   void _or(Bitmap_base const &r)
 198   {
 199     _bits |= r._bits;
 200   }
 201
 202   void _copy(Bitmap_base const &s)
 203   { _bits = s._bits; }
 204 };
 205
 206 template<int BITS>
 207 class Bitmap : public Bitmap_base< (BITS > sizeof(unsigned long) * 8), BITS >
 208 {
 209 public:
 210   Bitmap() {}
 211   Bitmap(Bitmap const &o)
 212   { this->_copy(o); }
 213
 214   Bitmap &operator = (Bitmap const &o)
 215   {
 216     this->_copy(o);
 217     return *this;
 218   }
 219
 220   Bitmap &operator |= (Bitmap const &o)
 221   {
 222     this->_or(o);
 223     return *this;
 224   }
 225 };