utest/bitmap/raw-bitmap-tests.cpp

5 #include <bitmap/raw-bitmap.h>
6 #include <bitmap/storage.h>
12 namespace bitmap {
18     RawBitmap bitmap;
19     EXPECT_EQ(bitmap.Reset(0), ZX_OK);
20     EXPECT_EQ(bitmap.size(), 0U, "get size");
22     EXPECT_TRUE(bitmap.GetOne(0), "get one bit");
23     EXPECT_EQ(bitmap.SetOne(0), ZX_ERR_INVALID_ARGS, "set one bit");
24     EXPECT_EQ(bitmap.ClearOne(0), ZX_ERR_INVALID_ARGS, "clear one bit");
26     EXPECT_EQ(bitmap.Reset(1), ZX_OK);
27     EXPECT_FALSE(bitmap.GetOne(0), "get one bit");
28     EXPECT_EQ(bitmap.SetOne(0), ZX_OK, "set one bit");
29     EXPECT_EQ(bitmap.ClearOne(0), ZX_OK, "clear one bit");
37     RawBitmap bitmap;
38     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
39     EXPECT_EQ(bitmap.size(), 128U, "get size");
41     EXPECT_FALSE(bitmap.GetOne(2), "get bit before setting");
43     EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
44     EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting");
46     EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit");
47     EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing");
55     RawBitmap bitmap;
56     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
57     EXPECT_EQ(bitmap.size(), 128U, "get size");
59     EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
60     EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting");
62     EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit again");
63     EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting again");
71     RawBitmap bitmap;
72     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
73     EXPECT_EQ(bitmap.size(), 128U, "get size");
75     EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
77     EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit");
78     EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing");
80     EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit again");
81     EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing again");
89     RawBitmap bitmap;
90     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
91     EXPECT_EQ(bitmap.size(), 128U, "get size");
94     EXPECT_FALSE(bitmap.Get(2, 3, nullptr), "get bit with null");
95     EXPECT_FALSE(bitmap.Get(2, 3, &first_unset), "get bit with nonnull");
98     EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
99     EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get bit after setting");
103     EXPECT_FALSE(bitmap.Get(2, 4, &first_unset), "get larger range after setting");
106     EXPECT_EQ(bitmap.SetOne(3), ZX_OK, "set another bit");
107     EXPECT_FALSE(bitmap.Get(2, 5, &first_unset), "get larger range after setting another");
116     RawBitmap bitmap;
117     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
118     EXPECT_EQ(bitmap.size(), 128U, "get size");
120     EXPECT_EQ(bitmap.Set(2, 100), ZX_OK, "set range");
123     EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get first bit in range");
126     EXPECT_TRUE(bitmap.Get(99, 100, &first_unset), "get last bit in range");
129     EXPECT_FALSE(bitmap.Get(1, 2, &first_unset), "get bit before first in range");
132     EXPECT_FALSE(bitmap.Get(100, 101, &first_unset), "get bit after last in range");
135     EXPECT_TRUE(bitmap.Get(2, 100, &first_unset), "get entire range");
138     EXPECT_TRUE(bitmap.Get(50, 80, &first_unset), "get part of range");
142     EXPECT_FALSE(bitmap.Scan(0, 100, true, &result), "scan set bits");
144     EXPECT_FALSE(bitmap.ReverseScan(0, 100, true, &result), "reverse scan set bits");
147     EXPECT_FALSE(bitmap.Scan(0, 100, false, &result), "scan cleared bits");
149     EXPECT_FALSE(bitmap.ReverseScan(0, 100, false, &result), "reverse scan cleared bits");
152     EXPECT_TRUE(bitmap.Scan(2, 100, true), "scan set bits in set range");
153     EXPECT_TRUE(bitmap.ReverseScan(2, 100, true), "reverse scan set bits in set range");
155     EXPECT_FALSE(bitmap.Scan(2, 100, false, &result), "scan cleared bits in set range");
157     EXPECT_FALSE(bitmap.ReverseScan(2, 100, false, &result),
161     EXPECT_TRUE(bitmap.Scan(50, 80, true), "scan set bits in subrange");
162     EXPECT_TRUE(bitmap.ReverseScan(50, 80, true), "reverse scan set bits in subrange");
164     EXPECT_TRUE(bitmap.Scan(100, 200, false), "scan past end of bitmap");
165     EXPECT_TRUE(bitmap.ReverseScan(100, 200, false), "reverse scan past end of bitmap");
173     RawBitmap bitmap;
174     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
175     EXPECT_EQ(bitmap.size(), 128U, "get size");
180     EXPECT_EQ(bitmap.Find(false, 0, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
181     EXPECT_EQ(bitmap.ReverseFind(false, 0, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
182     EXPECT_EQ(bitmap.Find(false, 1, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
183     EXPECT_EQ(bitmap.ReverseFind(false, 1, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
184     EXPECT_EQ(bitmap.Find(false, 0, 1, 1, nullptr), ZX_ERR_INVALID_ARGS, "bad output");
185     EXPECT_EQ(bitmap.ReverseFind(false, 0, 1, 1, nullptr), ZX_ERR_INVALID_ARGS, "bad output");
188     EXPECT_EQ(bitmap.Find(false, 0, 100, 1, &bitoff_start), ZX_OK, "find unset");
190     EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 1, &bitoff_start), ZX_OK, "reverse find unset");
193     EXPECT_EQ(bitmap.Find(true, 0, 100, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, "find set");
194     EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
197     EXPECT_EQ(bitmap.Find(false, 0, 100, 5, &bitoff_start), ZX_OK, "find more unset");
199     EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 5, &bitoff_start), ZX_OK,
203     EXPECT_EQ(bitmap.Find(true, 0, 100, 5, &bitoff_start), ZX_ERR_NO_RESOURCES, "find more set");
204     EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 5, &bitoff_start), ZX_ERR_NO_RESOURCES,
207     EXPECT_EQ(bitmap.Find(false, 0, 100, 100, &bitoff_start), ZX_OK, "find all unset");
209     EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 100, &bitoff_start), ZX_OK,
213     EXPECT_EQ(bitmap.Find(true, 0, 100, 100, &bitoff_start), ZX_ERR_NO_RESOURCES, "find all set");
214     EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 100, &bitoff_start), ZX_ERR_NO_RESOURCES,
218     EXPECT_EQ(bitmap.Find(false, 50, 100, 3, &bitoff_start), ZX_OK, "find at offset");
220     EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 3, &bitoff_start), ZX_OK,
224     EXPECT_EQ(bitmap.Find(true, 50, 100, 3, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail at offset");
225     EXPECT_EQ(bitmap.ReverseFind(true, 50, 100, 3, &bitoff_start), ZX_ERR_NO_RESOURCES,
228     EXPECT_EQ(bitmap.Find(false, 90, 100, 10, &bitoff_start), ZX_OK, "find at offset end");
230     EXPECT_EQ(bitmap.ReverseFind(false, 90, 100, 10, &bitoff_start), ZX_OK,
235     EXPECT_EQ(bitmap.Find(false, 0, 100, 101, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
236     EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 101, &bitoff_start), ZX_ERR_NO_RESOURCES,
238     EXPECT_EQ(bitmap.Find(false, 91, 100, 10, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
239     EXPECT_EQ(bitmap.ReverseFind(false, 91, 100, 10, &bitoff_start), ZX_ERR_NO_RESOURCES,
241     EXPECT_EQ(bitmap.Find(false, 90, 100, 11, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
242     EXPECT_EQ(bitmap.ReverseFind(false, 90, 100, 11, &bitoff_start), ZX_ERR_NO_RESOURCES,
244     EXPECT_EQ(bitmap.Find(false, 90, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
245     EXPECT_EQ(bitmap.ReverseFind(false, 90, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
247     // Fill the bitmap
248     EXPECT_EQ(bitmap.Set(5, 10), ZX_OK, "set range");
249     EXPECT_EQ(bitmap.Set(20, 30), ZX_OK, "set range");
250     EXPECT_EQ(bitmap.Set(32, 35), ZX_OK, "set range");
251     EXPECT_EQ(bitmap.Set(90, 95), ZX_OK, "set range");
252     EXPECT_EQ(bitmap.Set(70, 80), ZX_OK, "set range");
253     EXPECT_EQ(bitmap.Set(65, 68), ZX_OK, "set range");
255     EXPECT_EQ(bitmap.Find(false, 0, 50, 5, &bitoff_start), ZX_OK, "find in first group");
257     EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 5, &bitoff_start), ZX_OK,
261     EXPECT_EQ(bitmap.Find(false, 0, 50, 10, &bitoff_start), ZX_OK, "find in second group");
263     EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 10, &bitoff_start), ZX_OK,
267     EXPECT_EQ(bitmap.Find(false, 0, 50, 15, &bitoff_start), ZX_OK, "find in third group");
269     EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 15, &bitoff_start), ZX_OK,
273     EXPECT_EQ(bitmap.Find(false, 0, 50, 16, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
274     EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 16, &bitoff_start), ZX_ERR_NO_RESOURCES,
277     EXPECT_EQ(bitmap.Find(false, 5, 20, 10, &bitoff_start), ZX_OK, "find space (offset)");
279     EXPECT_EQ(bitmap.ReverseFind(false, 80, 95, 10, &bitoff_start), ZX_OK,
283     EXPECT_EQ(bitmap.Find(false, 5, 25, 10, &bitoff_start), ZX_OK, "find space (offset)");
285     EXPECT_EQ(bitmap.ReverseFind(false, 75, 95, 10, &bitoff_start), ZX_OK,
289     EXPECT_EQ(bitmap.Find(false, 5, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
291     EXPECT_EQ(bitmap.ReverseFind(false, 85, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
294     EXPECT_EQ(bitmap.Find(true, 0, 15, 2, &bitoff_start), ZX_OK, "find set bits");
296     EXPECT_EQ(bitmap.ReverseFind(true, 85, 100, 2, &bitoff_start), ZX_OK, "reverse find set bits");
299     EXPECT_EQ(bitmap.Find(true, 0, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
301     EXPECT_EQ(bitmap.ReverseFind(true, 85, 100, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
304     EXPECT_EQ(bitmap.Find(false, 32, 35, 3, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
305     EXPECT_EQ(bitmap.ReverseFind(false, 65, 68, 3, &bitoff_start), ZX_ERR_NO_RESOURCES,
308     EXPECT_EQ(bitmap.Find(false, 32, 35, 4, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
309     EXPECT_EQ(bitmap.ReverseFind(false, 65, 68, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
312     EXPECT_EQ(bitmap.Find(true, 32, 35, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
314     EXPECT_EQ(bitmap.ReverseFind(true, 65, 68, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
317     // Fill the whole bitmap
318     EXPECT_EQ(bitmap.Set(0, 128), ZX_OK, "set range");
320     EXPECT_EQ(bitmap.Find(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
322     EXPECT_EQ(bitmap.ReverseFind(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
325     EXPECT_EQ(bitmap.Find(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
327     EXPECT_EQ(bitmap.ReverseFind(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
336     RawBitmap bitmap;
337     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
338     EXPECT_EQ(bitmap.size(), 128U, "get size");
340     EXPECT_EQ(bitmap.Set(0, 100), ZX_OK, "set range");
342     bitmap.ClearAll();
345     EXPECT_FALSE(bitmap.Get(2, 100, &first), "get range");
348     EXPECT_EQ(bitmap.Set(0, 99), ZX_OK, "set range");
349     EXPECT_FALSE(bitmap.Get(0, 100, &first), "get range");
358     RawBitmap bitmap;
359     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
360     EXPECT_EQ(bitmap.size(), 128U, "get size");
362     EXPECT_EQ(bitmap.Set(2, 100), ZX_OK, "set range");
363     EXPECT_EQ(bitmap.Clear(50, 80), ZX_OK, "clear range");
366     EXPECT_FALSE(bitmap.Get(2, 100, &first_unset), "get whole original range");
370     EXPECT_TRUE(bitmap.Get(2, 50, &first_unset), "get first half range");
373     EXPECT_TRUE(bitmap.Get(80, 100, &first_unset), "get second half range");
376     EXPECT_FALSE(bitmap.Get(50, 80, &first_unset), "get cleared range");
385     RawBitmap bitmap;
386     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
387     EXPECT_EQ(bitmap.size(), 128U, "get size");
389     EXPECT_EQ(bitmap.Set(0, 0), ZX_OK, "range contains no bits");
390     EXPECT_EQ(bitmap.Set(5, 4), ZX_ERR_INVALID_ARGS, "max is less than off");
391     EXPECT_EQ(bitmap.Set(5, 5), ZX_OK, "range contains no bits");
393     EXPECT_EQ(bitmap.Clear(0, 0), ZX_OK, "range contains no bits");
394     EXPECT_EQ(bitmap.Clear(5, 4), ZX_ERR_INVALID_ARGS, "max is less than off");
395     EXPECT_EQ(bitmap.Clear(5, 5), ZX_OK, "range contains no bits");
397     EXPECT_TRUE(bitmap.Get(0, 0), "range contains no bits, so all are true");
398     EXPECT_TRUE(bitmap.Get(5, 4), "range contains no bits, so all are true");
399     EXPECT_TRUE(bitmap.Get(5, 5), "range contains no bits, so all are true");
407     RawBitmap bitmap;
408     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
409     EXPECT_EQ(bitmap.size(), 128U, "get size");
411     EXPECT_EQ(bitmap.SetOne(0x64), ZX_OK, "setting later");
412     EXPECT_EQ(bitmap.SetOne(0x60), ZX_OK, "setting earlier");
414     EXPECT_TRUE(bitmap.GetOne(0x64), "getting first set");
415     EXPECT_TRUE(bitmap.GetOne(0x60), "getting second set");
422     RawBitmap bitmap;
423     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
424     EXPECT_EQ(bitmap.size(), 128u);
426     EXPECT_FALSE(bitmap.GetOne(100));
427     EXPECT_EQ(bitmap.SetOne(100), ZX_OK);
428     EXPECT_TRUE(bitmap.GetOne(100));
431     EXPECT_EQ(bitmap.Find(true, 101, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
432               "Expected tail end of bitmap to be unset");
435     EXPECT_NE(bitmap.SetOne(16 * PAGE_SIZE - 1), ZX_OK);
437     EXPECT_EQ(bitmap.Grow(16 * PAGE_SIZE), ZX_OK);
438     EXPECT_EQ(bitmap.Find(true, 101, 16 * PAGE_SIZE, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
439               "Expected tail end of bitmap to be unset");
442     EXPECT_FALSE(bitmap.GetOne(16 * PAGE_SIZE - 1));
443     EXPECT_EQ(bitmap.SetOne(16 * PAGE_SIZE - 1), ZX_OK);
444     EXPECT_TRUE(bitmap.GetOne(16 * PAGE_SIZE - 1));
447     EXPECT_TRUE(bitmap.GetOne(100), "Growing should not unset bits");
449     // If we shrink and re-expand the bitmap, it should
451     EXPECT_EQ(bitmap.Shrink(99), ZX_OK);
452     EXPECT_EQ(bitmap.Grow(16 * PAGE_SIZE), ZX_OK);
453     EXPECT_FALSE(bitmap.GetOne(100));
454     EXPECT_FALSE(bitmap.GetOne(16 * PAGE_SIZE - 1));
462     RawBitmap bitmap;
463     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
464     EXPECT_EQ(bitmap.size(), 128u);
466     EXPECT_FALSE(bitmap.GetOne(100));
467     EXPECT_EQ(bitmap.SetOne(100), ZX_OK);
468     EXPECT_TRUE(bitmap.GetOne(100));
475                 EXPECT_EQ(bitmap.Reset(bitmap_size), ZX_OK);
476                 EXPECT_EQ(bitmap.size(), bitmap_size);
479                 EXPECT_FALSE(bitmap.GetOne(bitmap_size - shrink_len));
480                 EXPECT_EQ(bitmap.SetOne(bitmap_size - shrink_len), ZX_OK);
481                 EXPECT_TRUE(bitmap.GetOne(bitmap_size - shrink_len));
484                 EXPECT_FALSE(bitmap.GetOne(bitmap_size - shrink_len - 1));
485                 EXPECT_EQ(bitmap.SetOne(bitmap_size - shrink_len - 1), ZX_OK);
486                 EXPECT_TRUE(bitmap.GetOne(bitmap_size - shrink_len - 1));
488                 EXPECT_EQ(bitmap.Shrink(bitmap_size - shrink_len), ZX_OK);
489                 EXPECT_EQ(bitmap.Grow(bitmap_size), ZX_OK);
491                 EXPECT_FALSE(bitmap.GetOne(bitmap_size - shrink_len),
493                 EXPECT_TRUE(bitmap.GetOne(bitmap_size - shrink_len - 1),
498                     bitmap.Find(true, bitmap_size - shrink_len, bitmap_size, 1, &bitoff_start),
499                     ZX_ERR_NO_RESOURCES, "Expected tail end of bitmap to be unset");
510     RawBitmap bitmap;
511     EXPECT_EQ(bitmap.Reset(128), ZX_OK);
512     EXPECT_EQ(bitmap.size(), 128u);
514     EXPECT_EQ(bitmap.Grow(64), ZX_ERR_NO_RESOURCES);
515     EXPECT_EQ(bitmap.Grow(128), ZX_ERR_NO_RESOURCES);
516     EXPECT_EQ(bitmap.Grow(128 + 1), ZX_ERR_NO_RESOURCES);
517     EXPECT_EQ(bitmap.Grow(8 * PAGE_SIZE), ZX_ERR_NO_RESOURCES);
544 } // namespace bitmap