L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
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
22namespace cxx {
23
30{
31protected:
35 typedef unsigned long word_type;
36
37 enum
38 {
39 W_bits = sizeof(word_type) * 8,
40 C_bits = 8,
41 };
42
47
55 static unsigned word_index(unsigned bit) { return bit / W_bits; }
56
64 static unsigned bit_index(unsigned bit) { return bit % W_bits; }
65
69 class Bit
70 {
71 Bitmap_base *_bm;
72 long _bit;
73
74 public:
75 Bit(Bitmap_base *bm, long bit) : _bm(bm), _bit(bit) {}
76 Bit &operator = (bool val) { _bm->bit(_bit, val); return *this; }
77 operator bool () const { return _bm->bit(_bit); }
78 };
79
80public:
81 explicit Bitmap_base(void *bits) noexcept : _bits(reinterpret_cast<word_type *>(bits)) {}
82
84 static long words(long bits) noexcept { return (bits + W_bits -1) / W_bits; }
85 static long bit_buffer_bytes(long bits) noexcept
86 { return words(bits) * W_bits / 8; }
87
89 template< long BITS >
90 class Word
91 {
92 public:
93 typedef unsigned long Type;
94 enum
95 {
96 Size = (BITS + W_bits - 1) / W_bits
97 };
98 };
99
101 static long chars(long bits) noexcept
102 { return (bits + C_bits -1) / C_bits; }
103
105 template< long BITS >
106 class Char
107 {
108 public:
109 typedef unsigned char Type;
110 enum
111 {
112 Size = (BITS + C_bits - 1) / C_bits
113 };
114 };
115
122 void bit(long bit, bool on) noexcept;
123
129 void clear_bit(long bit) noexcept;
130
138 void atomic_clear_bit(long bit) noexcept;
139
147 word_type atomic_get_and_clear(long bit) noexcept;
148
154 void set_bit(long bit) noexcept;
155
163 void atomic_set_bit(long bit) noexcept;
164
172 word_type atomic_get_and_set(long bit) noexcept;
173
182 word_type bit(long bit) const noexcept;
183
192 word_type operator [] (long bit) const noexcept
193 { return this->bit(bit); }
194
202 Bit operator [] (long bit) noexcept
203 { return Bit(this, bit); }
204
216 long scan_zero(long max_bit, long start_bit = 0) const noexcept;
217
218 void *bit_buffer() const noexcept { return _bits; }
219
220protected:
221 static int _bzl(unsigned long w) noexcept;
222};
223
224
230template<int BITS>
231class Bitmap : public Bitmap_base
232{
233private:
235
236public:
238 Bitmap() noexcept : Bitmap_base(_bits) {}
239 Bitmap(Bitmap<BITS> const &o) noexcept : Bitmap_base(_bits)
240 { __builtin_memcpy(_bits, o._bits, sizeof(_bits)); }
253 long scan_zero(long start_bit = 0) const noexcept;
254
255 void clear_all()
256 { __builtin_memset(_bits, 0, sizeof(_bits)); }
257};
258
259
260inline
261void
262Bitmap_base::bit(long bit, bool on) noexcept
263{
264 long idx = word_index(bit);
265 long b = bit_index(bit);
266 _bits[idx] = (_bits[idx] & ~(1UL << b)) | (static_cast<unsigned long>(on) << b);
267}
268
269inline
270void
271Bitmap_base::clear_bit(long bit) noexcept
272{
273 long idx = word_index(bit);
274 long b = bit_index(bit);
275 _bits[idx] &= ~(1UL << b);
276}
277
278inline
279void
281{
282 long idx = word_index(bit);
283 long b = bit_index(bit);
284 word_type mask = 1UL << b;
285 __atomic_and_fetch(&_bits[idx], ~mask, __ATOMIC_RELAXED);
286}
287
288inline
291{
292 long idx = word_index(bit);
293 long b = bit_index(bit);
294 word_type mask = 1UL << b;
295 return __atomic_fetch_and(&_bits[idx], ~mask, __ATOMIC_RELAXED) & mask;
296}
297
298inline
299void
300Bitmap_base::set_bit(long bit) noexcept
301{
302 long idx = word_index(bit);
303 long b = bit_index(bit);
304 _bits[idx] |= (1UL << b);
305}
306
307inline
308void
310{
311 long idx = word_index(bit);
312 long b = bit_index(bit);
313 word_type mask = 1UL << b;
314 __atomic_or_fetch(&_bits[idx], mask, __ATOMIC_RELAXED);
315}
316
317inline
320{
321 long idx = word_index(bit);
322 long b = bit_index(bit);
323 word_type mask = 1UL << b;
324 return __atomic_fetch_or(&_bits[idx], mask, __ATOMIC_RELAXED) & mask;
325}
326
327inline
329Bitmap_base::bit(long bit) const noexcept
330{
331 long idx = word_index(bit);
332 long b = bit_index(bit);
333 return _bits[idx] & (1UL << b);
334}
335
336inline
337int
338Bitmap_base::_bzl(unsigned long w) noexcept
339{
340 for (int i = 0; i < W_bits; ++i, w >>= 1)
341 {
342 if ((w & 1) == 0)
343 return i;
344 }
345 return -1;
346}
347
348inline
349long
350Bitmap_base::scan_zero(long max_bit, long start_bit) const noexcept
351{
352 if (!(operator [] (start_bit)))
353 return start_bit;
354
355 long idx = word_index(start_bit);
356
357 max_bit -= start_bit & ~(W_bits - 1);
358
359 for (; max_bit > 0; max_bit -= W_bits, ++idx)
360 {
361 if (_bits[idx] == 0)
362 return idx * W_bits;
363
364 if (_bits[idx] != ~0UL)
365 {
366 long zbit = _bzl(_bits[idx]);
367 return zbit < max_bit ? idx * W_bits + zbit : -1;
368 }
369 }
370
371 return -1;
372}
373
374template<int BITS> inline
375long
376Bitmap<BITS>::scan_zero(long start_bit) const noexcept
377{
378 return Bitmap_base::scan_zero(BITS, start_bit);
379}
380
381};
A writeable bit in a bitmap.
Definition bitmap:70
Helper abstraction for a byte contained in the bitmap.
Definition bitmap:107
Helper abstraction for a word contained in the bitmap.
Definition bitmap:91
Basic bitmap abstraction.
Definition bitmap:30
static long chars(long bits) noexcept
Get the number of chars that are used for the bitmap.
Definition bitmap:101
long scan_zero(long max_bit, long start_bit=0) const noexcept
Scan for the first zero bit.
Definition bitmap:350
void atomic_clear_bit(long bit) noexcept
Clear bit bit atomically.
Definition bitmap:280
word_type atomic_get_and_clear(long bit) noexcept
Clear bit bit atomically and return old state.
Definition bitmap:290
void atomic_set_bit(long bit) noexcept
Set bit bit atomically.
Definition bitmap:309
static unsigned bit_index(unsigned bit)
Get the bit index within word_type for the given bit.
Definition bitmap:64
unsigned long word_type
Data type for each element of the bit buffer.
Definition bitmap:35
static long words(long bits) noexcept
Get the number of Words that are used for the bitmap.
Definition bitmap:84
static unsigned word_index(unsigned bit)
Get the word index for the given bit.
Definition bitmap:55
@ W_bits
number of bits in word_type
Definition bitmap:39
@ C_bits
number of bits in char
Definition bitmap:40
void clear_bit(long bit) noexcept
Clear bit bit.
Definition bitmap:271
void set_bit(long bit) noexcept
Set bit bit.
Definition bitmap:300
word_type atomic_get_and_set(long bit) noexcept
Set bit bit atomically and return old state.
Definition bitmap:319
word_type operator[](long bit) const noexcept
Get the bit at index bit.
Definition bitmap:192
void bit(long bit, bool on) noexcept
Set the value of bit bit to on.
Definition bitmap:262
word_type * _bits
Pointer to the buffer storing the bits.
Definition bitmap:46
A static bitmap.
Definition bitmap:232
Bitmap() noexcept
Create a bitmap with BITS bits.
Definition bitmap:238
long scan_zero(long start_bit=0) const noexcept
Scan for the first zero bit.
Definition bitmap:376
Our C++ library.
Definition arith:22