jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/Bitmap.h>
10
11TEST_CASE(construct_empty)
12{
13 Bitmap bitmap;
14 EXPECT_EQ(bitmap.size(), 0u);
15}
16
17TEST_CASE(find_first_set)
18{
19 auto bitmap = MUST(Bitmap::create(128, false));
20 bitmap.set(69, true);
21 EXPECT_EQ(bitmap.find_first_set().value(), 69u);
22}
23
24TEST_CASE(find_first_unset)
25{
26 auto bitmap = MUST(Bitmap::create(128, true));
27 bitmap.set(51, false);
28 EXPECT_EQ(bitmap.find_first_unset().value(), 51u);
29}
30
31TEST_CASE(find_one_anywhere_set)
32{
33 {
34 auto bitmap = MUST(Bitmap::create(168, false));
35 bitmap.set(34, true);
36 bitmap.set(97, true);
37 EXPECT_EQ(bitmap.find_one_anywhere_set(0).value(), 34u);
38 EXPECT_EQ(bitmap.find_one_anywhere_set(31).value(), 34u);
39 EXPECT_EQ(bitmap.find_one_anywhere_set(32).value(), 34u);
40 EXPECT_EQ(bitmap.find_one_anywhere_set(34).value(), 34u);
41 EXPECT_EQ(bitmap.find_one_anywhere_set(36).value(), 34u);
42 EXPECT_EQ(bitmap.find_one_anywhere_set(63).value(), 34u);
43 EXPECT_EQ(bitmap.find_one_anywhere_set(64).value(), 97u);
44 EXPECT_EQ(bitmap.find_one_anywhere_set(96).value(), 97u);
45 EXPECT_EQ(bitmap.find_one_anywhere_set(96).value(), 97u);
46 EXPECT_EQ(bitmap.find_one_anywhere_set(97).value(), 97u);
47 EXPECT_EQ(bitmap.find_one_anywhere_set(127).value(), 97u);
48 EXPECT_EQ(bitmap.find_one_anywhere_set(128).value(), 34u);
49 }
50 {
51 auto bitmap = MUST(Bitmap::create(128 + 24, false));
52 bitmap.set(34, true);
53 bitmap.set(126, true);
54 EXPECT_EQ(bitmap.find_one_anywhere_set(0).value(), 34u);
55 EXPECT_EQ(bitmap.find_one_anywhere_set(63).value(), 34u);
56 EXPECT_EQ(bitmap.find_one_anywhere_set(64).value(), 126u);
57 }
58 {
59 auto bitmap = MUST(Bitmap::create(32, false));
60 bitmap.set(12, true);
61 bitmap.set(24, true);
62 auto got = bitmap.find_one_anywhere_set(0).value();
63 EXPECT(got == 12 || got == 24);
64 }
65}
66
67TEST_CASE(find_one_anywhere_unset)
68{
69 {
70 auto bitmap = MUST(Bitmap::create(168, true));
71 bitmap.set(34, false);
72 bitmap.set(97, false);
73 EXPECT_EQ(bitmap.find_one_anywhere_unset(0).value(), 34u);
74 EXPECT_EQ(bitmap.find_one_anywhere_unset(31).value(), 34u);
75 EXPECT_EQ(bitmap.find_one_anywhere_unset(32).value(), 34u);
76 EXPECT_EQ(bitmap.find_one_anywhere_unset(34).value(), 34u);
77 EXPECT_EQ(bitmap.find_one_anywhere_unset(36).value(), 34u);
78 EXPECT_EQ(bitmap.find_one_anywhere_unset(63).value(), 34u);
79 EXPECT_EQ(bitmap.find_one_anywhere_unset(64).value(), 97u);
80 EXPECT_EQ(bitmap.find_one_anywhere_unset(96).value(), 97u);
81 EXPECT_EQ(bitmap.find_one_anywhere_unset(96).value(), 97u);
82 EXPECT_EQ(bitmap.find_one_anywhere_unset(97).value(), 97u);
83 EXPECT_EQ(bitmap.find_one_anywhere_unset(127).value(), 97u);
84 EXPECT_EQ(bitmap.find_one_anywhere_unset(128).value(), 34u);
85 }
86 {
87 auto bitmap = MUST(Bitmap::create(128 + 24, true));
88 bitmap.set(34, false);
89 bitmap.set(126, false);
90 EXPECT_EQ(bitmap.find_one_anywhere_unset(0).value(), 34u);
91 EXPECT_EQ(bitmap.find_one_anywhere_unset(63).value(), 34u);
92 EXPECT_EQ(bitmap.find_one_anywhere_unset(64).value(), 126u);
93 }
94 {
95 auto bitmap = MUST(Bitmap::create(32, true));
96 bitmap.set(12, false);
97 bitmap.set(24, false);
98 auto got = bitmap.find_one_anywhere_unset(0).value();
99 EXPECT(got == 12 || got == 24);
100 }
101}
102
103TEST_CASE(find_first_range)
104{
105 auto bitmap = MUST(Bitmap::create(128, true));
106 bitmap.set(47, false);
107 bitmap.set(48, false);
108 bitmap.set(49, false);
109 bitmap.set(50, false);
110 bitmap.set(51, false);
111 size_t found_range_size = 0;
112 auto result = bitmap.find_longest_range_of_unset_bits(5, found_range_size);
113 EXPECT_EQ(result.has_value(), true);
114 EXPECT_EQ(found_range_size, 5u);
115 EXPECT_EQ(result.value(), 47u);
116}
117
118TEST_CASE(set_range)
119{
120 {
121 auto bitmap = MUST(Bitmap::create(128, false));
122 bitmap.set_range(41, 10, true);
123 EXPECT_EQ(bitmap.get(40), false);
124 EXPECT_EQ(bitmap.get(41), true);
125 EXPECT_EQ(bitmap.get(42), true);
126 EXPECT_EQ(bitmap.get(43), true);
127 EXPECT_EQ(bitmap.get(44), true);
128 EXPECT_EQ(bitmap.get(45), true);
129 EXPECT_EQ(bitmap.get(46), true);
130 EXPECT_EQ(bitmap.get(47), true);
131 EXPECT_EQ(bitmap.get(48), true);
132 EXPECT_EQ(bitmap.get(49), true);
133 EXPECT_EQ(bitmap.get(50), true);
134 EXPECT_EQ(bitmap.get(51), false);
135 }
136 {
137 auto bitmap = MUST(Bitmap::create(288, false));
138 bitmap.set_range(48, 32, true);
139 bitmap.set_range(94, 39, true);
140 bitmap.set_range(190, 71, true);
141 bitmap.set_range(190 + 71 - 7, 21, false); // slightly overlapping clear
142 for (size_t i = 0; i < bitmap.size(); i++) {
143 bool should_be_set = (i >= 48 && i < 48 + 32)
144 || (i >= 94 && i < 94 + 39)
145 || ((i >= 190 && i < 190 + 71) && !(i >= 190 + 71 - 7 && i < 190 + 71 - 7 + 21));
146 EXPECT_EQ(bitmap.get(i), should_be_set);
147 }
148 EXPECT_EQ(bitmap.count_slow(true), 32u + 39u + 71u - 7u);
149 }
150}
151
152TEST_CASE(find_first_fit)
153{
154 {
155 auto bitmap = MUST(Bitmap::create(32, true));
156 auto fit = bitmap.find_first_fit(1);
157 EXPECT_EQ(fit.has_value(), false);
158 }
159 {
160 auto bitmap = MUST(Bitmap::create(32, true));
161 bitmap.set(31, false);
162 auto fit = bitmap.find_first_fit(1);
163 EXPECT_EQ(fit.has_value(), true);
164 EXPECT_EQ(fit.value(), 31u);
165 }
166
167 for (size_t i = 0; i < 128; ++i) {
168 auto bitmap = MUST(Bitmap::create(128, true));
169 bitmap.set(i, false);
170 auto fit = bitmap.find_first_fit(1);
171 EXPECT_EQ(fit.has_value(), true);
172 EXPECT_EQ(fit.value(), i);
173 }
174
175 for (size_t i = 0; i < 127; ++i) {
176 auto bitmap = MUST(Bitmap::create(128, true));
177 bitmap.set(i, false);
178 bitmap.set(i + 1, false);
179 auto fit = bitmap.find_first_fit(2);
180 EXPECT_EQ(fit.has_value(), true);
181 EXPECT_EQ(fit.value(), i);
182 }
183
184 size_t bitmap_size = 1024;
185 for (size_t chunk_size = 1; chunk_size < 64; ++chunk_size) {
186 for (size_t i = 0; i < bitmap_size - chunk_size; ++i) {
187 auto bitmap = MUST(Bitmap::create(bitmap_size, true));
188 for (size_t c = 0; c < chunk_size; ++c)
189 bitmap.set(i + c, false);
190 auto fit = bitmap.find_first_fit(chunk_size);
191 EXPECT_EQ(fit.has_value(), true);
192 EXPECT_EQ(fit.value(), i);
193 }
194 }
195}
196
197TEST_CASE(find_longest_range_of_unset_bits_edge)
198{
199 auto bitmap = MUST(Bitmap::create(36, true));
200 bitmap.set_range(32, 4, false);
201 size_t found_range_size = 0;
202 auto result = bitmap.find_longest_range_of_unset_bits(1, found_range_size);
203 EXPECT_EQ(result.has_value(), true);
204 EXPECT_EQ(result.value(), 32u);
205}
206
207TEST_CASE(count_in_range)
208{
209 auto bitmap = MUST(Bitmap::create(256, false));
210 bitmap.set(14, true);
211 bitmap.set(17, true);
212 bitmap.set(19, true);
213 bitmap.set(20, true);
214 for (size_t i = 34; i < 250; i++) {
215 if (i < 130 || i > 183)
216 bitmap.set(i, true);
217 }
218
219 auto count_bits_slow = [](Bitmap const& b, size_t start, size_t len, bool value) -> size_t {
220 size_t count = 0;
221 for (size_t i = start; i < start + len; i++) {
222 if (b.get(i) == value)
223 count++;
224 }
225 return count;
226 };
227 auto test_with_value = [&](bool value) {
228 auto do_test = [&](size_t start, size_t len) {
229 EXPECT_EQ(bitmap.count_in_range(start, len, value), count_bits_slow(bitmap, start, len, value));
230 };
231 do_test(16, 2);
232 do_test(16, 3);
233 do_test(16, 4);
234
235 for (size_t start = 8; start < 24; start++) {
236 for (size_t end = 9; end < 25; end++) {
237 if (start >= end)
238 continue;
239 do_test(start, end - start);
240 }
241 }
242
243 for (size_t start = 1; start <= 9; start++) {
244 for (size_t i = start + 1; i < bitmap.size() - start + 1; i++)
245 do_test(start, i - start);
246 }
247 };
248 test_with_value(true);
249 test_with_value(false);
250}
251
252TEST_CASE(byte_aligned_access)
253{
254 {
255 auto bitmap = MUST(Bitmap::create(16, true));
256 EXPECT_EQ(bitmap.count_in_range(0, 16, true), 16u);
257 EXPECT_EQ(bitmap.count_in_range(8, 8, true), 8u);
258 EXPECT_EQ(bitmap.count_in_range(0, 8, true), 8u);
259 EXPECT_EQ(bitmap.count_in_range(4, 8, true), 8u);
260 }
261 {
262 auto bitmap = MUST(Bitmap::create(16, false));
263 bitmap.set_range(4, 8, true);
264 EXPECT_EQ(bitmap.count_in_range(0, 16, true), 8u);
265 EXPECT_EQ(bitmap.count_in_range(8, 8, true), 4u);
266 EXPECT_EQ(bitmap.count_in_range(0, 8, true), 4u);
267 EXPECT_EQ(bitmap.count_in_range(4, 8, true), 8u);
268 }
269 {
270 auto bitmap = MUST(Bitmap::create(8, false));
271 bitmap.set(2, true);
272 bitmap.set(4, true);
273 EXPECT_EQ(bitmap.count_in_range(0, 2, true), 0u);
274 EXPECT_EQ(bitmap.count_in_range(0, 4, true), 1u);
275 EXPECT_EQ(bitmap.count_in_range(0, 8, true), 2u);
276 EXPECT_EQ(bitmap.count_in_range(4, 4, true), 1u);
277 }
278}