5 #include <bitmap/rle-bitmap.h>
10 namespace bitmap {
15 static bool VerifyCounts(const RleBitmap& bitmap, size_t rng_expected, size_t bit_expected,
20     for (auto& range : bitmap) {
27     EXPECT_EQ(rng_count, bitmap.num_ranges(), "unexpected range count");
29     EXPECT_EQ(bit_count, bitmap.num_bits(), "unexpected bit count");
35     RleBitmap bitmap;
36     EXPECT_FALSE(bitmap.Get(5, 6), "get one bit");
37     for (__UNUSED auto& range : bitmap) {
47     RleBitmap bitmap;
48     EXPECT_FALSE(bitmap.Get(2, 3), "get bit before setting");
50     ASSERT_EQ(bitmap.Set(2, 3), ZX_OK, "set bit");
51     EXPECT_TRUE(bitmap.Get(2, 3), "get bit after setting");
52     EXPECT_EQ(bitmap.num_bits(), 1U, "unexpected bit count");
60     EXPECT_TRUE(VerifyCounts(bitmap, 1U, 1U, cb));
62     ASSERT_EQ(bitmap.Clear(2, 3), ZX_OK, "clear bit");
63     EXPECT_FALSE(bitmap.Get(2, 3), "get bit after clearing");
64     EXPECT_TRUE(VerifyCounts(bitmap, 0U, 0U, cb));
72     RleBitmap bitmap;
74     ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
75     EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting");
77     EXPECT_EQ(bitmap.num_bits(), 1);
79     ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit again");
80     EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting again");
81     EXPECT_EQ(bitmap.num_bits(), 1);
89     EXPECT_TRUE(VerifyCounts(bitmap, 1U, 1U, cb));
97     RleBitmap bitmap;
99     ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
100     EXPECT_EQ(bitmap.num_bits(), 1U, "unexpected bit count");
102     ASSERT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit");
103     EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing");
104     EXPECT_EQ(bitmap.num_bits(), 0U, "unexpected bit count");
106     ASSERT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit again");
107     EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing again");
108     EXPECT_EQ(bitmap.num_bits(), 0U, "unexpected bit count");
110     for (__UNUSED auto& range : bitmap) {
120     RleBitmap bitmap;
123     EXPECT_FALSE(bitmap.Get(2, 3, nullptr), "get bit with null");
124     EXPECT_FALSE(bitmap.Get(2, 3, &first_unset), "get bit with nonnull");
127     ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
128     EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get bit after setting");
132     EXPECT_FALSE(bitmap.Get(2, 4, &first_unset), "get larger range after setting");
135     ASSERT_EQ(bitmap.Set(3, 4), ZX_OK, "set another bit");
136     EXPECT_FALSE(bitmap.Get(2, 5, &first_unset), "get larger range after setting another");
145     EXPECT_TRUE(VerifyCounts(bitmap, 1U, 2U, cb));
152     RleBitmap bitmap;
153     ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range");
154     EXPECT_EQ(bitmap.num_bits(), 98U, "unexpected bit count");
157     EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get first bit in range");
160     EXPECT_TRUE(bitmap.Get(99, 100, &first_unset), "get last bit in range");
163     EXPECT_FALSE(bitmap.Get(1, 2, &first_unset), "get bit before first in range");
166     EXPECT_FALSE(bitmap.Get(100, 101, &first_unset), "get bit after last in range");
169     EXPECT_TRUE(bitmap.Get(2, 100, &first_unset), "get entire range");
172     EXPECT_TRUE(bitmap.Get(50, 80, &first_unset), "get part of range");
181     RleBitmap bitmap;
183     ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range");
185     bitmap.ClearAll();
187     for (__UNUSED auto& range : bitmap) {
191     ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range");
193     for (auto& range : bitmap) {
205     EXPECT_TRUE(VerifyCounts(bitmap, 1U, 100U - 2U, cb));
212     RleBitmap bitmap;
214     ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range");
215     EXPECT_EQ(bitmap.num_bits(), 98U, "unexpected bit count");
216     ASSERT_EQ(bitmap.Clear(50, 80), ZX_OK, "clear range");
217     EXPECT_EQ(bitmap.num_bits(), 68U, "unexpected bit count");
220     EXPECT_FALSE(bitmap.Get(2, 100, &first_unset), "get whole original range");
224     EXPECT_TRUE(bitmap.Get(2, 50, &first_unset), "get first half range");
227     EXPECT_TRUE(bitmap.Get(80, 100, &first_unset), "get second half range");
230     EXPECT_FALSE(bitmap.Get(50, 80, &first_unset), "get cleared range");
245     EXPECT_TRUE(VerifyCounts(bitmap, 2U, 68U, cb));
252     RleBitmap bitmap;
257         ASSERT_EQ(bitmap.SetOne(i), ZX_OK, "setting even bits");
267     EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 2, kMaxVal / 2, cb));
270         ASSERT_EQ(bitmap.SetOne(i), ZX_OK, "setting congruent 1 mod 4 bits");
280     EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4, 3 * kMaxVal / 4, cb2));
287     RleBitmap bitmap;
290     ASSERT_EQ(bitmap.Set(0, kMaxVal), ZX_OK, "setting all bits");
293         ASSERT_EQ(bitmap.ClearOne(i), ZX_OK, "clearing congruent 1 mod 4 bits");
310     EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4 + 1, 3 * kMaxVal / 4, cb));
313         ASSERT_EQ(bitmap.ClearOne(i), ZX_OK, "clearing even bits");
323     EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4, kMaxVal / 4, cb2));
330     RleBitmap bitmap;
332     EXPECT_EQ(bitmap.Set(0, 0), ZX_OK, "range contains no bits");
333     EXPECT_EQ(bitmap.Set(5, 4), ZX_ERR_INVALID_ARGS, "max is less than off");
334     EXPECT_EQ(bitmap.Set(5, 5), ZX_OK, "range contains no bits");
336     EXPECT_EQ(bitmap.Clear(0, 0), ZX_OK, "range contains no bits");
337     EXPECT_EQ(bitmap.Clear(5, 4), ZX_ERR_INVALID_ARGS, "max is less than off");
338     EXPECT_EQ(bitmap.Clear(5, 5), ZX_OK, "range contains no bits");
340     EXPECT_TRUE(bitmap.Get(0, 0), "range contains no bits, so all are true");
341     EXPECT_TRUE(bitmap.Get(5, 4), "range contains no bits, so all are true");
342     EXPECT_TRUE(bitmap.Get(5, 5), "range contains no bits, so all are true");
350     RleBitmap bitmap;
352     EXPECT_EQ(bitmap.SetNoAlloc(0, 65536, nullptr), ZX_ERR_INVALID_ARGS, "set bits with nullptr freelist");
353     EXPECT_EQ(bitmap.ClearNoAlloc(0, 65536, nullptr), ZX_ERR_INVALID_ARGS, "clear bits with nullptr freelist");
356     EXPECT_EQ(bitmap.SetNoAlloc(0, 65536, &free_list), ZX_ERR_NO_MEMORY, "set bits with empty freelist");
361     EXPECT_EQ(bitmap.SetNoAlloc(0, 65536, &free_list), ZX_OK, "set bits");
362     EXPECT_TRUE(bitmap.Get(0, 65536), "get bit after setting");
365     EXPECT_EQ(bitmap.ClearNoAlloc(1, 65535, &free_list), ZX_ERR_NO_MEMORY, "clear bits with empty freelist and alloc needed");
369     EXPECT_EQ(bitmap.ClearNoAlloc(1, 65535, &free_list), ZX_OK, "clear bits");
371     EXPECT_FALSE(bitmap.Get(0, 65536, &first_unset), "get bit after clearing");
377     EXPECT_EQ(bitmap.SetNoAlloc(1, 65535, &free_list), ZX_OK, "add range back in");
380     EXPECT_EQ(bitmap.ClearNoAlloc(0, 65536, &free_list), ZX_OK, "remove everything we allocated");
388     RleBitmap bitmap;
389     EXPECT_EQ(bitmap.Set(0x64, 0x65), ZX_OK, "setting later");
390     EXPECT_EQ(bitmap.Set(0x60, 0x61), ZX_OK, "setting earlier");
391     EXPECT_EQ(bitmap.num_ranges(), 2U, "unexpected range count");
392     EXPECT_EQ(bitmap.num_bits(), 2U, "unexpected bit count");
393     EXPECT_TRUE(bitmap.Get(0x64, 0x65), "getting first set");
394     EXPECT_TRUE(bitmap.Get(0x60, 0x61), "getting second set");
398 static bool VerifyRange(const RleBitmap& bitmap, size_t bitoff, size_t bitmax, size_t min_val,
402     EXPECT_TRUE(bitmap.Get(bitoff, bitmax));
403     EXPECT_EQ(bitmap.Find(false, min_val, max_val, bitoff - min_val, &out), ZX_OK);
405     EXPECT_EQ(bitmap.Find(false, min_val, max_val, max_val - bitmax, &out), ZX_OK);
407     EXPECT_EQ(bitmap.num_bits(), bitmax - bitoff);
411 static bool VerifyCleared(const RleBitmap& bitmap, size_t min_val, size_t max_val) {
414     EXPECT_EQ(bitmap.Find(false, min_val, max_val, max_val - min_val, &out), ZX_OK);
416     EXPECT_EQ(bitmap.num_bits(), 0);
428     RleBitmap bitmap;
431     EXPECT_EQ(bitmap.Set(bitoff1, bitmax1), ZX_OK);
432     EXPECT_EQ(bitmap.Set(bitoff2, bitmax2), ZX_OK);
433     EXPECT_TRUE(VerifyRange(bitmap, min_off, max_max, min_val, max_val));
434     EXPECT_EQ(bitmap.Clear(min_off, max_max), ZX_OK);
435     EXPECT_TRUE(VerifyCleared(bitmap, min_val, max_val));
457     RleBitmap bitmap;
459     EXPECT_EQ(bitmap.Set(5, 10), ZX_OK, "setting range");
460     EXPECT_EQ(bitmap.num_bits(), 5, "unexpected bit count");
462     EXPECT_EQ(bitmap.Find(false, 0, 15, 5, &out), ZX_OK, "finding range");
465     EXPECT_EQ(bitmap.Find(false, 1, 15, 5, &out), ZX_OK, "finding range");
468     EXPECT_EQ(bitmap.Find(false, 0, 15, 6, &out), ZX_ERR_NO_RESOURCES, "finding range");
471     EXPECT_EQ(bitmap.Find(true, 0, 15, 5, &out), ZX_OK, "finding range");
474     EXPECT_EQ(bitmap.Find(true, 6, 15, 3, &out), ZX_OK, "finding range");
477     EXPECT_EQ(bitmap.Find(true, 0, 15, 6, &out), ZX_ERR_NO_RESOURCES, "finding range");
480     EXPECT_EQ(bitmap.Find(true, 0, 8, 4, &out), ZX_ERR_NO_RESOURCES, "finding range");
483     EXPECT_EQ(bitmap.Set(20, 30), ZX_OK, "setting range");
484     EXPECT_EQ(bitmap.num_bits(), 15, "unexpected bit count");
486     EXPECT_EQ(bitmap.Find(false, 0, 50, 11, &out), ZX_OK, "finding range");
489     EXPECT_EQ(bitmap.Find(false, 0, 40, 11, &out), ZX_ERR_NO_RESOURCES, "finding range");
492     EXPECT_EQ(bitmap.Find(true, 0, 50, 5, &out), ZX_OK, "finding range");
495     EXPECT_EQ(bitmap.Find(true, 0, 50, 7, &out), ZX_OK, "finding range");
498     EXPECT_EQ(bitmap.Find(true, 7, 50, 5, &out), ZX_OK, "finding range");
501     EXPECT_EQ(bitmap.Find(true, 0, 50, 11, &out), ZX_ERR_NO_RESOURCES, "finding range");
504     EXPECT_EQ(bitmap.Find(true, 35, 50, 6, &out), ZX_ERR_NO_RESOURCES, "finding range");
528 } // namespace bitmap

Indexes created Fri Jul 05 22:58:02 MDT 2024