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
22namespace 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 */
30class Bitmap_base
31{
32protected:
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
77public:
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
169protected:
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 */
179template<int BITS>
180class Bitmap : public Bitmap_base
181{
182private:
183  char _bits[Bitmap_base::Char<BITS>::Size];
184
185public:
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
209inline
210void
211Bitmap_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
218inline
219void
220Bitmap_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
227inline
228void
229Bitmap_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
236inline
237Bitmap_base::word_type
238Bitmap_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
245inline
246int
247Bitmap_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
257inline
258long
259Bitmap_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
283template<int BITS> inline
284long
285Bitmap<BITS>::scan_zero(long start_bit) const throw()
286{
287  return Bitmap_base::scan_zero(BITS, start_bit);
288}
289
290};
291
292