L4Re - L4 Runtime Environment
bitmap
1 // vi:set ft=cpp: -*- Mode: C++ -*-
2 /*
3  * (c) 2008-2014 Alexander Warg <warg@os.inf.tu-dresden.de>
4  * economic rights: Technische Universit├Ąt Dresden (Germany)
5  *
6  * This file is part of TUD:OS and distributed under the terms of the
7  * GNU General Public License 2.
8  * Please see the COPYING-GPL-2 file for details.
9  *
10  * As a special exception, you may use this file as part of a free software
11  * library without restriction. Specifically, if other files instantiate
12  * templates or use macros or inline functions from this file, or you compile
13  * this file and link it with other files to produce an executable, this
14  * file does not by itself cause the resulting executable to be covered by
15  * the GNU General Public License. This exception does not however
16  * invalidate any other reasons why the executable file might be covered by
17  * the GNU General Public License.
18  */
19 
20 #pragma once
21 
22 namespace cxx {
23 
24 /**
25  * \ingroup cxx_api
26  * \brief Basic bitmap abstraction.
27  *
28  * This abstraction keeps a pointer to a memory area that is used as bitmap.
29  */
30 class Bitmap_base
31 {
32 protected:
33  /**
34  * \brief Data type for each element of the bit buffer.
35  */
36  typedef unsigned long word_type;
37 
38  enum
39  {
40  W_bits = sizeof(word_type) * 8, ///< number of bits in word_type
41  C_bits = 8, ///< number of bits in char
42  };
43 
44  /**
45  * \brief Pointer to the buffer storing the bits.
46  */
47  word_type *_bits;
48 
49  /**
50  * \brief Get the word index for the given bit.
51  * \param bit the index of the bit in question.
52  * \return the index in Bitmap_base::_bits for the given bit (bit / W_bits).
53  */
54  static unsigned word_index(unsigned bit) { return bit / W_bits; }
55 
56  /**
57  * \brief Get the bit index within word_type for the given bit.
58  * \param bit the bit index in the bitmap.
59  * \return the bit index within word_type (bit % W_bits).
60  */
61  static unsigned bit_index(unsigned bit) { return bit % W_bits; }
62 
63  /**
64  * \brief A writeable bit in a bitmap.
65  */
66  class Bit
67  {
68  Bitmap_base *_bm;
69  long _bit;
70 
71  public:
72  Bit(Bitmap_base *bm, long bit) : _bm(bm), _bit(bit) {}
73  Bit &operator = (bool val) { _bm->bit(_bit, val); return *this; }
74  operator bool () const { return _bm->bit(_bit); }
75  };
76 
77 public:
78  explicit Bitmap_base(void *bits) throw() : _bits((word_type *)bits) {}
79 
80  /** \brief Get the number of \a Words that are used for the bitmap. */
81  static long words(long bits) throw() { return (bits + W_bits -1) / W_bits; }
82  static long bit_buffer_bytes(long bits) throw()
83  { return words(bits) * W_bits / 8; }
84 
85  /** \brief Helper abstraction for a word contained in the bitmap. */
86  template< long BITS >
87  class Word
88  {
89  public:
90  typedef unsigned long Type;
91  enum
92  {
93  Size = (BITS + W_bits - 1) / W_bits
94  };
95  };
96 
97  /** \brief Get the number of chars that are used for the bitmap. */
98  static long chars(long bits) throw ()
99  { return (bits + C_bits -1) / C_bits; }
100 
101  /** \brief Helper abstraction for a byte contained in the bitmap. */
102  template< long BITS >
103  class Char
104  {
105  public:
106  typedef unsigned char Type;
107  enum
108  {
109  Size = (BITS + C_bits - 1) / C_bits
110  };
111  };
112 
113  /**
114  * \brief Set the value of bit \a bit to \a on.
115  * \param bit the number of the bit
116  * \param on the boolean value that shall be assigned to the bit.
117  */
118  void bit(long bit, bool on) throw();
119 
120  /**
121  * \brief Clear bit \a bit.
122  * \param bit the number of the bit to clear.
123  */
124  void clear_bit(long bit) throw();
125  /**
126  * \brief Set bit \a bit.
127  * \param bit the number of the bit to set,
128  */
129  void set_bit(long bit) throw();
130 
131  /**
132  * \brief Get the truth value of a bit.
133  * \param bit the number of the bit to read.
134  * \return 0 if \a bit is not set, != 0 if \a bit is set.
135  */
136  word_type bit(long bit) const throw();
137 
138  /**
139  * \brief Get the bit at index \a bit.
140  * \param bit the number of the bit to read.
141  * \return 0 if \a bit is not set, != 0 if \a bit is set.
142  */
143  word_type operator [] (long bit) const throw()
144  { return this->bit(bit); }
145 
146  /**
147  * \brief Get the lvalue for the bit at index \a bit.
148  * \param bit the number.
149  * \return lvalue for \a bit
150  */
151  Bit operator [] (long bit) throw()
152  { return Bit(this, bit); }
153 
154  /**
155  * Scan for the first zero bit.
156  *
157  * \param max_bit Upper bound (exclusive) for the scanning operation.
158  * \param start_bit Hint at the number of the first bit to look at.
159  * Zero bits below `start_bit` may or may not be
160  * taken into account by the implementation.
161  *
162  * \retval >= 0 Number of first zero bit found.
163  * \retval -1 All bits between `start_bit` and `max_bit` are set.
164  */
165  long scan_zero(long max_bit, long start_bit = 0) const throw();
166 
167  void *bit_buffer() const throw() { return _bits; }
168 
169 protected:
170  static int _bzl(unsigned long w) throw();
171 };
172 
173 
174 /**
175  * \ingroup cxx_api
176  * \brief A static bit map.
177  * \param BITS the number of bits that shall be in the bitmap.
178  */
179 template<int BITS>
180 class Bitmap : public Bitmap_base
181 {
182 private:
183  char _bits[Bitmap_base::Char<BITS>::Size];
184 
185 public:
186  /** \brief Create a bitmap with \a BITS bits. */
187  Bitmap() throw() : Bitmap_base(_bits) {}
188  Bitmap(Bitmap<BITS> const &o) throw() : Bitmap_base(_bits)
189  { __builtin_memcpy(_bits, o._bits, sizeof(_bits)); }
190  /**
191  * Scan for the first zero bit.
192  *
193  * \param start_bit Hint at the number of the first bit to look at.
194  * Zero bits below `start_bit` may or may not be
195  * taken into account by the implementation.
196  *
197  * \retval >= 0 Number of first zero bit found.
198  * \retval -1 All bits at `start_bit` or higher are set.
199  *
200  * Compared to Bitmap_base::scan_zero(), the upper bound is set to BITS.
201  */
202  long scan_zero(long start_bit = 0) const throw();
203 
204  void clear_all()
205  { __builtin_memset(_bits, 0, sizeof(_bits)); }
206 };
207 
208 
209 inline
210 void
211 Bitmap_base::bit(long bit, bool on) throw()
212 {
213  long idx = word_index(bit);
214  long b = bit_index(bit);
215  _bits[idx] = (_bits[idx] & ~(1UL << b)) | ((unsigned long)on << b);
216 }
217 
218 inline
219 void
220 Bitmap_base::clear_bit(long bit) throw()
221 {
222  long idx = word_index(bit);
223  long b = bit_index(bit);
224  _bits[idx] &= ~(1UL << b);
225 }
226 
227 inline
228 void
229 Bitmap_base::set_bit(long bit) throw()
230 {
231  long idx = word_index(bit);
232  long b = bit_index(bit);
233  _bits[idx] |= (1UL << b);
234 }
235 
236 inline
237 unsigned long
238 Bitmap_base::bit(long bit) const throw()
239 {
240  long idx = word_index(bit);
241  long b = bit_index(bit);
242  return _bits[idx] & (1UL << b);
243 }
244 
245 inline
246 int
247 Bitmap_base::_bzl(unsigned long w) throw()
248 {
249  for (int i = 0; i < W_bits; ++i, w >>= 1)
250  {
251  if ((w & 1) == 0)
252  return i;
253  }
254  return -1;
255 }
256 
257 inline
258 long
259 Bitmap_base::scan_zero(long max_bit, long start_bit) const throw()
260 {
261  if (!(operator [] (start_bit)))
262  return start_bit;
263 
264  long idx = word_index(start_bit);
265 
266  max_bit -= start_bit & ~(W_bits - 1);
267 
268  for (; max_bit > 0; max_bit -= W_bits, ++idx)
269  {
270  if (_bits[idx] == 0)
271  return idx * W_bits;
272 
273  if (_bits[idx] != ~0UL)
274  {
275  long zbit = _bzl(_bits[idx]);
276  return zbit < max_bit ? idx * W_bits + zbit : -1;
277  }
278  }
279 
280  return -1;
281 }
282 
283 template<int BITS> inline
284 long
285 Bitmap<BITS>::scan_zero(long start_bit) const throw()
286 {
287  return Bitmap_base::scan_zero(BITS, start_bit);
288 }
289 
290 };
291