jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2021, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#pragma once
8
9#include <AK/Array.h>
10#include <AK/BuiltinWrappers.h>
11#include <AK/Optional.h>
12#include <AK/StdLibExtras.h>
13#include <AK/Types.h>
14
15namespace AK {
16
17static constexpr Array bitmask_first_byte = { 0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80 };
18static constexpr Array bitmask_last_byte = { 0x00, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F };
19
20class BitmapView {
21public:
22 BitmapView() = default;
23
24 BitmapView(u8* data, size_t size)
25 : m_data(data)
26 , m_size(size)
27 {
28 }
29
30 [[nodiscard]] size_t size() const { return m_size; }
31 [[nodiscard]] size_t size_in_bytes() const { return ceil_div(m_size, static_cast<size_t>(8)); }
32 [[nodiscard]] bool get(size_t index) const
33 {
34 VERIFY(index < m_size);
35 return 0 != (m_data[index / 8] & (1u << (index % 8)));
36 }
37
38 [[nodiscard]] size_t count_slow(bool value) const
39 {
40 return count_in_range(0, m_size, value);
41 }
42
43 [[nodiscard]] size_t count_in_range(size_t start, size_t len, bool value) const
44 {
45 VERIFY(start < m_size);
46 VERIFY(start + len <= m_size);
47 if (len == 0)
48 return 0;
49
50 size_t count;
51 u8 const* first = &m_data[start / 8];
52 u8 const* last = &m_data[(start + len) / 8];
53 u8 byte = *first;
54 byte &= bitmask_first_byte[start % 8];
55 if (first == last) {
56 byte &= bitmask_last_byte[(start + len) % 8];
57 count = popcount(byte);
58 } else {
59 count = popcount(byte);
60 // Don't access *last if it's out of bounds
61 if (last < &m_data[size_in_bytes()]) {
62 byte = *last;
63 byte &= bitmask_last_byte[(start + len) % 8];
64 count += popcount(byte);
65 }
66 if (++first < last) {
67 size_t const* ptr_large = reinterpret_cast<size_t const*>((reinterpret_cast<FlatPtr>(first) + sizeof(size_t) - 1) & ~(sizeof(size_t) - 1));
68 if (reinterpret_cast<u8 const*>(ptr_large) > last)
69 ptr_large = reinterpret_cast<size_t const*>(last);
70 while (first < reinterpret_cast<u8 const*>(ptr_large)) {
71 count += popcount(*first);
72 first++;
73 }
74 size_t const* last_large = reinterpret_cast<size_t const*>(reinterpret_cast<FlatPtr>(last) & ~(sizeof(size_t) - 1));
75 while (ptr_large < last_large) {
76 count += popcount(*ptr_large);
77 ptr_large++;
78 }
79 for (first = reinterpret_cast<u8 const*>(ptr_large); first < last; first++)
80 count += popcount(*first);
81 }
82 }
83
84 if (!value)
85 count = len - count;
86 return count;
87 }
88
89 [[nodiscard]] bool is_null() const { return m_data == nullptr; }
90
91 [[nodiscard]] u8 const* data() const { return m_data; }
92
93 template<bool VALUE>
94 Optional<size_t> find_one_anywhere(size_t hint = 0) const
95 {
96 VERIFY(hint < m_size);
97 u8 const* end = &m_data[m_size / 8];
98
99 for (;;) {
100 // We will use hint as what it is: a hint. Because we try to
101 // scan over entire 32 bit words, we may start searching before
102 // the hint!
103 size_t const* ptr_large = reinterpret_cast<size_t const*>(reinterpret_cast<FlatPtr>(&m_data[hint / 8]) & ~(sizeof(size_t) - 1));
104 if (reinterpret_cast<u8 const*>(ptr_large) < &m_data[0]) {
105 ptr_large++;
106
107 // m_data isn't aligned, check first bytes
108 size_t start_ptr_large = reinterpret_cast<u8 const*>(ptr_large) - &m_data[0];
109 size_t i = 0;
110 u8 byte = VALUE ? 0x00 : 0xff;
111 while (i < start_ptr_large && m_data[i] == byte)
112 i++;
113 if (i < start_ptr_large) {
114 byte = m_data[i];
115 if constexpr (!VALUE)
116 byte = ~byte;
117 VERIFY(byte != 0);
118 return i * 8 + bit_scan_forward(byte) - 1;
119 }
120 }
121
122 size_t val_large = VALUE ? 0x0 : NumericLimits<size_t>::max();
123 size_t const* end_large = reinterpret_cast<size_t const*>(reinterpret_cast<FlatPtr>(end) & ~(sizeof(size_t) - 1));
124 while (ptr_large < end_large && *ptr_large == val_large)
125 ptr_large++;
126
127 if (ptr_large == end_large) {
128 // We didn't find anything, check the remaining few bytes (if any)
129 u8 byte = VALUE ? 0x00 : 0xff;
130 size_t i = reinterpret_cast<u8 const*>(ptr_large) - &m_data[0];
131 size_t byte_count = m_size / 8;
132 VERIFY(i <= byte_count);
133 while (i < byte_count && m_data[i] == byte)
134 i++;
135 if (i == byte_count) {
136 if (hint <= 8)
137 return {}; // We already checked from the beginning
138
139 // Try scanning before the hint
140 end = reinterpret_cast<u8 const*>(reinterpret_cast<FlatPtr>(&m_data[hint / 8]) & ~(sizeof(size_t) - 1));
141 hint = 0;
142 continue;
143 }
144 byte = m_data[i];
145 if constexpr (!VALUE)
146 byte = ~byte;
147 VERIFY(byte != 0);
148 return i * 8 + bit_scan_forward(byte) - 1;
149 }
150
151 // NOTE: We don't really care about byte ordering. We found *one*
152 // free bit, just calculate the position and return it
153 val_large = *ptr_large;
154 if constexpr (!VALUE)
155 val_large = ~val_large;
156 VERIFY(val_large != 0);
157 return (reinterpret_cast<u8 const*>(ptr_large) - &m_data[0]) * 8 + bit_scan_forward(val_large) - 1;
158 }
159 }
160
161 Optional<size_t> find_one_anywhere_set(size_t hint = 0) const
162 {
163 return find_one_anywhere<true>(hint);
164 }
165
166 Optional<size_t> find_one_anywhere_unset(size_t hint = 0) const
167 {
168 return find_one_anywhere<false>(hint);
169 }
170
171 template<bool VALUE>
172 Optional<size_t> find_first() const
173 {
174 size_t byte_count = m_size / 8;
175 size_t i = 0;
176
177 u8 byte = VALUE ? 0x00 : 0xff;
178 while (i < byte_count && m_data[i] == byte)
179 i++;
180 if (i == byte_count)
181 return {};
182
183 byte = m_data[i];
184 if constexpr (!VALUE)
185 byte = ~byte;
186 VERIFY(byte != 0);
187 return i * 8 + bit_scan_forward(byte) - 1;
188 }
189
190 Optional<size_t> find_first_set() const { return find_first<true>(); }
191 Optional<size_t> find_first_unset() const { return find_first<false>(); }
192
193 // The function will return the next range of unset bits starting from the
194 // @from value.
195 // @from: the position from which the search starts. The var will be
196 // changed and new value is the offset of the found block.
197 // @min_length: minimum size of the range which will be returned.
198 // @max_length: maximum size of the range which will be returned.
199 // This is used to increase performance, since the range of
200 // unset bits can be long, and we don't need the while range,
201 // so we can stop when we've reached @max_length.
202 inline Optional<size_t> find_next_range_of_unset_bits(size_t& from, size_t min_length = 1, size_t max_length = max_size) const
203 {
204 if (min_length > max_length) {
205 return {};
206 }
207
208 size_t bit_size = 8 * sizeof(size_t);
209
210 size_t* bitmap = reinterpret_cast<size_t*>(m_data);
211
212 // Calculating the start offset.
213 size_t start_bucket_index = from / bit_size;
214 size_t start_bucket_bit = from % bit_size;
215
216 size_t* start_of_free_chunks = &from;
217 size_t free_chunks = 0;
218
219 for (size_t bucket_index = start_bucket_index; bucket_index < m_size / bit_size; ++bucket_index) {
220 if (bitmap[bucket_index] == NumericLimits<size_t>::max()) {
221 // Skip over completely full bucket of size bit_size.
222 if (free_chunks >= min_length) {
223 return min(free_chunks, max_length);
224 }
225 free_chunks = 0;
226 start_bucket_bit = 0;
227 continue;
228 }
229 if (bitmap[bucket_index] == 0x0) {
230 // Skip over completely empty bucket of size bit_size.
231 if (free_chunks == 0) {
232 *start_of_free_chunks = bucket_index * bit_size;
233 }
234 free_chunks += bit_size;
235 if (free_chunks >= max_length) {
236 return max_length;
237 }
238 start_bucket_bit = 0;
239 continue;
240 }
241
242 size_t bucket = bitmap[bucket_index];
243 u8 viewed_bits = start_bucket_bit;
244 u32 trailing_zeroes = 0;
245
246 bucket >>= viewed_bits;
247 start_bucket_bit = 0;
248
249 while (viewed_bits < bit_size) {
250 if (bucket == 0) {
251 if (free_chunks == 0) {
252 *start_of_free_chunks = bucket_index * bit_size + viewed_bits;
253 }
254 free_chunks += bit_size - viewed_bits;
255 viewed_bits = bit_size;
256 } else {
257 trailing_zeroes = count_trailing_zeroes(bucket);
258 bucket >>= trailing_zeroes;
259
260 if (free_chunks == 0) {
261 *start_of_free_chunks = bucket_index * bit_size + viewed_bits;
262 }
263 free_chunks += trailing_zeroes;
264 viewed_bits += trailing_zeroes;
265
266 if (free_chunks >= min_length) {
267 return min(free_chunks, max_length);
268 }
269
270 // Deleting trailing ones.
271 u32 trailing_ones = count_trailing_zeroes(~bucket);
272 bucket >>= trailing_ones;
273 viewed_bits += trailing_ones;
274 free_chunks = 0;
275 }
276 }
277 }
278
279 if (free_chunks < min_length) {
280 size_t first_trailing_bit = (m_size / bit_size) * bit_size;
281 size_t trailing_bits = size() % bit_size;
282 for (size_t i = 0; i < trailing_bits; ++i) {
283 if (!get(first_trailing_bit + i)) {
284 if (free_chunks == 0)
285 *start_of_free_chunks = first_trailing_bit + i;
286 if (++free_chunks >= min_length)
287 return min(free_chunks, max_length);
288 } else {
289 free_chunks = 0;
290 }
291 }
292 return {};
293 }
294
295 return min(free_chunks, max_length);
296 }
297
298 Optional<size_t> find_longest_range_of_unset_bits(size_t max_length, size_t& found_range_size) const
299 {
300 size_t start = 0;
301 size_t max_region_start = 0;
302 size_t max_region_size = 0;
303
304 while (true) {
305 // Look for the next block which is bigger than currunt.
306 auto length_of_found_range = find_next_range_of_unset_bits(start, max_region_size + 1, max_length);
307 if (length_of_found_range.has_value()) {
308 max_region_start = start;
309 max_region_size = length_of_found_range.value();
310 start += max_region_size;
311 } else {
312 // No ranges which are bigger than current were found.
313 break;
314 }
315 }
316
317 found_range_size = max_region_size;
318 if (max_region_size != 0) {
319 return max_region_start;
320 }
321 return {};
322 }
323
324 Optional<size_t> find_first_fit(size_t minimum_length) const
325 {
326 size_t start = 0;
327 auto length_of_found_range = find_next_range_of_unset_bits(start, minimum_length, minimum_length);
328 if (length_of_found_range.has_value()) {
329 return start;
330 }
331 return {};
332 }
333
334 Optional<size_t> find_best_fit(size_t minimum_length) const
335 {
336 size_t start = 0;
337 size_t best_region_start = 0;
338 size_t best_region_size = max_size;
339 bool found = false;
340
341 while (true) {
342 // Look for the next block which is bigger than requested length.
343 auto length_of_found_range = find_next_range_of_unset_bits(start, minimum_length, best_region_size);
344 if (length_of_found_range.has_value()) {
345 if (best_region_size > length_of_found_range.value() || !found) {
346 best_region_start = start;
347 best_region_size = length_of_found_range.value();
348 found = true;
349 }
350 start += length_of_found_range.value();
351 } else {
352 // There are no ranges which can fit requested length.
353 break;
354 }
355 }
356
357 if (found) {
358 return best_region_start;
359 }
360 return {};
361 }
362
363 static constexpr size_t max_size = 0xffffffff;
364
365protected:
366 u8* m_data { nullptr };
367 size_t m_size { 0 };
368};
369
370}
371
372#if USING_AK_GLOBALLY
373using AK::BitmapView;
374#endif