1#include "structures/tests/test_internal.h"
2
3TEST_GROUP_DEFINE(bitmap, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "bits",
6 });
7
8/* Bitmaps are arrays of 64 bit words, so every op that takes a bit count
9 * has a partial trailing word to deal with, which can cause counting/reporting
10 * bits that live past nbits inside the last word, and mishandling of cases
11 * where nbits lands on a word boundary
12 *
13 * We try to test exact boundaries and off-by-ones, 64, 1, 63, 65, 128, etc */
14
15#define BM_WORDS 4
16#define BM_BITS (BM_WORDS * BITMAP_BITS_PER_WORD)
17
18static void bm_reset(bitmap_word_t *map) {
19 for (size_t i = 0; i < BM_WORDS; i++)
20 map[i] = 0;
21}
22
23static void bm_fill(bitmap_word_t *map) {
24 for (size_t i = 0; i < BM_WORDS; i++)
25 map[i] = ~(bitmap_word_t) 0;
26}
27
28static void bm_reset_n(bitmap_word_t *map, size_t nwords) {
29 for (size_t i = 0; i < nwords; i++)
30 map[i] = 0;
31}
32
33static void bm_fill_n(bitmap_word_t *map, size_t nwords) {
34 for (size_t i = 0; i < nwords; i++)
35 map[i] = ~(bitmap_word_t) 0;
36}
37
38TEST_DEFINE_UNIT(bitmap, set_test_clear, TEST_INTENSITY(64, 256, 4096)) {
39 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
40 size_t nwords = BITMAP_WORDS(nbits);
41 bitmap_word_t *map = vnews(map, nwords, ALLOC_ZERO);
42 TEST_ASSERT_NONNULL(map);
43
44 for (size_t bit = 0; bit < nbits; bit++) {
45 TEST_ASSERT(!bitmap_test(map, bit));
46 bitmap_set(map, bit);
47 TEST_ASSERT(bitmap_test(map, bit));
48
49 /* Setting one bit must not
50 * disturb neighbors across the word boundary */
51 if (bit > 0)
52 TEST_ASSERT(!bitmap_test(map, bit - 1));
53
54 bitmap_clear(map, bit);
55 TEST_ASSERT(!bitmap_test(map, bit));
56 }
57
58 vfree(map);
59 return TEST_SUCCESS;
60}
61
62TEST_DEFINE_UNIT(bitmap, bit_isolation, TEST_INTENSITY(64, 256, 1024)) {
63 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
64 size_t nwords = BITMAP_WORDS(nbits);
65 bitmap_word_t *map = vnews(map, nwords, .flags = ALLOC_FLAGS_NONE);
66 TEST_ASSERT_NONNULL(map);
67
68 for (size_t bit = 0; bit < nbits; bit++) {
69 bm_reset_n(map, nwords);
70 bitmap_set(map, bit);
71
72 for (size_t other = 0; other < nbits; other++)
73 TEST_ASSERT_EQ(bitmap_test(map, other), (other == bit));
74
75 TEST_ASSERT_EQ(bitmap_weight(map, nbits), 1);
76 }
77
78 vfree(map);
79 return TEST_SUCCESS;
80}
81
82TEST_DEFINE_UNIT(bitmap, toggle_and_test_ops) {
83 bitmap_word_t map[BM_WORDS];
84 bm_reset(map);
85
86 bitmap_toggle(map, bit: 70);
87 TEST_ASSERT(bitmap_test(map, 70));
88 bitmap_toggle(map, bit: 70);
89 TEST_ASSERT(!bitmap_test(map, 70));
90
91 /* The test_and_* must report the state from before change */
92 TEST_ASSERT_EQ(bitmap_test_and_set(map, 5), false);
93 TEST_ASSERT_EQ(bitmap_test_and_set(map, 5), true);
94 TEST_ASSERT_EQ(bitmap_test_and_clear(map, 5), true);
95 TEST_ASSERT_EQ(bitmap_test_and_clear(map, 5), false);
96
97 return TEST_SUCCESS;
98}
99
100/* Bits above nbits are memory and could be set, but shan't be counted */
101TEST_DEFINE_UNIT(bitmap, weight_ignores_past_end) {
102 bitmap_word_t map[BM_WORDS];
103 bm_fill(map);
104
105 static const size_t sizes[] = {1, 7, 63, 64, 65, 100, 127, 128, BM_BITS};
106
107 for (size_t i = 0; i < TEST_ARRAY_LEN(sizes); i++)
108 TEST_ASSERT_EQ(bitmap_weight(map, sizes[i]), sizes[i]);
109
110 bm_reset(map);
111 TEST_ASSERT_EQ(bitmap_weight(map, BM_BITS), 0);
112
113 return TEST_SUCCESS;
114}
115
116TEST_DEFINE_UNIT(bitmap, weight_counts, TEST_INTENSITY(64, 256, 4096)) {
117 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
118 size_t nwords = BITMAP_WORDS(nbits);
119 bitmap_word_t *map = vnews(map, nwords, ALLOC_ZERO);
120 TEST_ASSERT_NONNULL(map);
121
122 for (size_t n = 0; n < nbits; n++) {
123 TEST_ASSERT_EQ(bitmap_weight(map, nbits), n);
124 bitmap_set(map, bit: n);
125 }
126 TEST_ASSERT_EQ(bitmap_weight(map, nbits), nbits);
127
128 vfree(map);
129 return TEST_SUCCESS;
130}
131
132TEST_DEFINE_UNIT(bitmap, set_clear_range) {
133 bitmap_word_t map[BM_WORDS];
134 bm_reset(map);
135
136 /* range over word boundary */
137 bitmap_set_range(map, start: 60, len: 10);
138 for (size_t bit = 0; bit < BM_BITS; bit++)
139 TEST_ASSERT_EQ(bitmap_test(map, bit), (bit >= 60 && bit < 70));
140
141 bitmap_clear_range(map, start: 62, len: 4);
142 for (size_t bit = 60; bit < 70; bit++)
143 TEST_ASSERT_EQ(bitmap_test(map, bit), (bit < 62 || bit >= 66));
144
145 /* zero length range == no-op */
146 bm_reset(map);
147 bitmap_set_range(map, start: 10, len: 0);
148 TEST_ASSERT_EQ(bitmap_weight(map, BM_BITS), 0);
149
150 return TEST_SUCCESS;
151}
152
153TEST_DEFINE_UNIT(bitmap, find_first_set, TEST_INTENSITY(64, 256, 2048)) {
154 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
155 size_t nwords = BITMAP_WORDS(nbits);
156 bitmap_word_t *map = vnews(map, nwords, .flags = ALLOC_FLAGS_NONE);
157 TEST_ASSERT_NONNULL(map);
158
159 bm_reset_n(map, nwords);
160 TEST_ASSERT_EQ(bitmap_find_first_set(map, nbits), nbits);
161
162 for (size_t bit = 0; bit < nbits; bit++) {
163 bm_reset_n(map, nwords);
164 bitmap_set(map, bit);
165 TEST_ASSERT_EQ(bitmap_find_first_set(map, nbits), bit);
166 }
167
168 /* Bit set beyond nbits mustn't report as found */
169 if (nbits >= 128) {
170 bm_reset_n(map, nwords);
171 bitmap_set(map, bit: 100);
172 TEST_ASSERT_EQ(bitmap_find_first_set(map, 100), 100);
173 TEST_ASSERT_EQ(bitmap_find_first_set(map, 101), 100);
174 }
175
176 vfree(map);
177 return TEST_SUCCESS;
178}
179
180TEST_DEFINE_UNIT(bitmap, find_first_zero, TEST_INTENSITY(64, 256, 2048)) {
181 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
182 size_t nwords = BITMAP_WORDS(nbits);
183 bitmap_word_t *map = vnews(map, nwords, .flags = ALLOC_FLAGS_NONE);
184 TEST_ASSERT_NONNULL(map);
185
186 bm_reset_n(map, nwords);
187 TEST_ASSERT_EQ(bitmap_find_first_zero(map, nbits), 0);
188
189 bm_fill_n(map, nwords);
190 TEST_ASSERT_EQ(bitmap_find_first_zero(map, nbits), nbits);
191
192 for (size_t bit = 0; bit < nbits; bit++) {
193 bm_fill_n(map, nwords);
194 bitmap_clear(map, bit);
195 TEST_ASSERT_EQ(bitmap_find_first_zero(map, nbits), bit);
196 }
197
198 /* Full at word boundary must report nothing free */
199 if (nbits >= 128) {
200 bm_fill_n(map, nwords);
201 TEST_ASSERT_EQ(bitmap_find_first_zero(map, 64), 64);
202 TEST_ASSERT_EQ(bitmap_find_first_zero(map, 128), 128);
203 }
204
205 vfree(map);
206 return TEST_SUCCESS;
207}
208
209TEST_DEFINE_UNIT(bitmap, find_next_bit) {
210 bitmap_word_t map[BM_WORDS];
211 bm_reset(map);
212
213 bitmap_set(map, bit: 3);
214 bitmap_set(map, bit: 64);
215 bitmap_set(map, bit: 65);
216 bitmap_set(map, bit: 200);
217
218 /* Starting on a set bit finds that bit */
219 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 0), 3);
220 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 3), 3);
221 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 4), 64);
222 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 64), 64);
223 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 65), 65);
224 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 66), 200);
225 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 201), BM_BITS);
226
227 /* A start at or past the end isn't a search */
228 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, BM_BITS), BM_BITS);
229 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, BM_BITS + 10), BM_BITS);
230
231 /* Bits past nbits stay invisible */
232 TEST_ASSERT_EQ(bitmap_find_next_bit(map, 100, 66), 100);
233
234 return TEST_SUCCESS;
235}
236
237/* Walking every set bit via find_next_bit must visit the bits that
238 * bitmap_test agrees are set, and terminate */
239TEST_DEFINE_UNIT(bitmap, find_next_bit_walk, TEST_INTENSITY(64, 256, 4096)) {
240 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
241 size_t nwords = BITMAP_WORDS(nbits);
242 bitmap_word_t *map = vnews(map, nwords, ALLOC_ZERO);
243 TEST_ASSERT_NONNULL(map);
244
245 for (size_t bit = 0; bit < nbits; bit += 7)
246 bitmap_set(map, bit);
247
248 size_t seen = 0;
249 for (size_t bit = bitmap_find_next_bit(map, nbits, start: 0); bit < nbits;
250 bit = bitmap_find_next_bit(map, nbits, start: bit + 1)) {
251 TEST_ASSERT(bitmap_test(map, bit));
252 TEST_ASSERT_EQ(bit % 7, 0);
253 seen++;
254 }
255
256 TEST_ASSERT_EQ(seen, bitmap_weight(map, nbits));
257
258 vfree(map);
259 return TEST_SUCCESS;
260}
261
262TEST_DEFINE_UNIT(bitmap, word_index_math) {
263 TEST_ASSERT_EQ(BITMAP_WORD_INDEX(0), 0);
264 TEST_ASSERT_EQ(BITMAP_WORD_INDEX(63), 0);
265 TEST_ASSERT_EQ(BITMAP_WORD_INDEX(64), 1);
266 TEST_ASSERT_EQ(BITMAP_BIT_OFFSET(64), 0);
267 TEST_ASSERT_EQ(BITMAP_BIT_OFFSET(65), 1);
268
269 /* BITMAP_WORDS rounds up */
270 TEST_ASSERT_EQ(BITMAP_WORDS(1), 1);
271 TEST_ASSERT_EQ(BITMAP_WORDS(64), 1);
272 TEST_ASSERT_EQ(BITMAP_WORDS(65), 2);
273 TEST_ASSERT_EQ(BITMAP_WORDS(128), 2);
274
275 return TEST_SUCCESS;
276}
277