Lines Matching refs:bitmap
10 namespace bitmap { namespace
15 static bool VerifyCounts(const RleBitmap& bitmap, size_t rng_expected, size_t bit_expected, in VerifyCounts() argument
20 for (auto& range : bitmap) { in VerifyCounts()
29 EXPECT_EQ(rng_count, bitmap.num_ranges(), "unexpected range count"); in VerifyCounts()
31 EXPECT_EQ(bit_count, bitmap.num_bits(), "unexpected bit count"); in VerifyCounts()
37 RleBitmap bitmap; in InitializedEmpty() local
38 EXPECT_FALSE(bitmap.Get(5, 6), "get one bit"); in InitializedEmpty()
39 for (__UNUSED auto& range : bitmap) { in InitializedEmpty()
49 RleBitmap bitmap; in SingleBit() local
50 EXPECT_FALSE(bitmap.Get(2, 3), "get bit before setting"); in SingleBit()
52 ASSERT_EQ(bitmap.Set(2, 3), ZX_OK, "set bit"); in SingleBit()
53 EXPECT_TRUE(bitmap.Get(2, 3), "get bit after setting"); in SingleBit()
54 EXPECT_EQ(bitmap.num_bits(), 1U, "unexpected bit count"); in SingleBit()
62 EXPECT_TRUE(VerifyCounts(bitmap, 1U, 1U, cb)); in SingleBit()
64 ASSERT_EQ(bitmap.Clear(2, 3), ZX_OK, "clear bit"); in SingleBit()
65 EXPECT_FALSE(bitmap.Get(2, 3), "get bit after clearing"); in SingleBit()
66 EXPECT_TRUE(VerifyCounts(bitmap, 0U, 0U, cb)); in SingleBit()
74 RleBitmap bitmap; in SetTwice() local
76 ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); in SetTwice()
77 EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting"); in SetTwice()
79 EXPECT_EQ(bitmap.num_bits(), 1); in SetTwice()
81 ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit again"); in SetTwice()
82 EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting again"); in SetTwice()
83 EXPECT_EQ(bitmap.num_bits(), 1); in SetTwice()
91 EXPECT_TRUE(VerifyCounts(bitmap, 1U, 1U, cb)); in SetTwice()
99 RleBitmap bitmap; in ClearTwice() local
101 ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); in ClearTwice()
102 EXPECT_EQ(bitmap.num_bits(), 1U, "unexpected bit count"); in ClearTwice()
104 ASSERT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit"); in ClearTwice()
105 EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing"); in ClearTwice()
106 EXPECT_EQ(bitmap.num_bits(), 0U, "unexpected bit count"); in ClearTwice()
108 ASSERT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit again"); in ClearTwice()
109 EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing again"); in ClearTwice()
110 EXPECT_EQ(bitmap.num_bits(), 0U, "unexpected bit count"); in ClearTwice()
112 for (__UNUSED auto& range : bitmap) { in ClearTwice()
122 RleBitmap bitmap; in GetReturnArg() local
125 EXPECT_FALSE(bitmap.Get(2, 3, nullptr), "get bit with null"); in GetReturnArg()
126 EXPECT_FALSE(bitmap.Get(2, 3, &first_unset), "get bit with nonnull"); in GetReturnArg()
129 ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); in GetReturnArg()
130 EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get bit after setting"); in GetReturnArg()
134 EXPECT_FALSE(bitmap.Get(2, 4, &first_unset), "get larger range after setting"); in GetReturnArg()
137 ASSERT_EQ(bitmap.Set(3, 4), ZX_OK, "set another bit"); in GetReturnArg()
138 EXPECT_FALSE(bitmap.Get(2, 5, &first_unset), "get larger range after setting another"); in GetReturnArg()
147 EXPECT_TRUE(VerifyCounts(bitmap, 1U, 2U, cb)); in GetReturnArg()
154 RleBitmap bitmap; in SetRange() local
155 ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); in SetRange()
156 EXPECT_EQ(bitmap.num_bits(), 98U, "unexpected bit count"); in SetRange()
159 EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get first bit in range"); in SetRange()
162 EXPECT_TRUE(bitmap.Get(99, 100, &first_unset), "get last bit in range"); in SetRange()
165 EXPECT_FALSE(bitmap.Get(1, 2, &first_unset), "get bit before first in range"); in SetRange()
168 EXPECT_FALSE(bitmap.Get(100, 101, &first_unset), "get bit after last in range"); in SetRange()
171 EXPECT_TRUE(bitmap.Get(2, 100, &first_unset), "get entire range"); in SetRange()
174 EXPECT_TRUE(bitmap.Get(50, 80, &first_unset), "get part of range"); in SetRange()
183 RleBitmap bitmap; in ClearAll() local
185 ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); in ClearAll()
187 bitmap.ClearAll(); in ClearAll()
189 for (__UNUSED auto& range : bitmap) { in ClearAll()
193 ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); in ClearAll()
195 for (auto& range : bitmap) { in ClearAll()
207 EXPECT_TRUE(VerifyCounts(bitmap, 1U, 100U - 2U, cb)); in ClearAll()
214 RleBitmap bitmap; in ClearSubrange() local
216 ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); in ClearSubrange()
217 EXPECT_EQ(bitmap.num_bits(), 98U, "unexpected bit count"); in ClearSubrange()
218 ASSERT_EQ(bitmap.Clear(50, 80), ZX_OK, "clear range"); in ClearSubrange()
219 EXPECT_EQ(bitmap.num_bits(), 68U, "unexpected bit count"); in ClearSubrange()
222 EXPECT_FALSE(bitmap.Get(2, 100, &first_unset), "get whole original range"); in ClearSubrange()
226 EXPECT_TRUE(bitmap.Get(2, 50, &first_unset), "get first half range"); in ClearSubrange()
229 EXPECT_TRUE(bitmap.Get(80, 100, &first_unset), "get second half range"); in ClearSubrange()
232 EXPECT_FALSE(bitmap.Get(50, 80, &first_unset), "get cleared range"); in ClearSubrange()
247 EXPECT_TRUE(VerifyCounts(bitmap, 2U, 68U, cb)); in ClearSubrange()
254 RleBitmap bitmap; in MergeRanges() local
259 ASSERT_EQ(bitmap.SetOne(i), ZX_OK, "setting even bits"); in MergeRanges()
269 EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 2, kMaxVal / 2, cb)); in MergeRanges()
272 ASSERT_EQ(bitmap.SetOne(i), ZX_OK, "setting congruent 1 mod 4 bits"); in MergeRanges()
282 EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4, 3 * kMaxVal / 4, cb2)); in MergeRanges()
289 RleBitmap bitmap; in SplitRanges() local
292 ASSERT_EQ(bitmap.Set(0, kMaxVal), ZX_OK, "setting all bits"); in SplitRanges()
295 ASSERT_EQ(bitmap.ClearOne(i), ZX_OK, "clearing congruent 1 mod 4 bits"); in SplitRanges()
312 EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4 + 1, 3 * kMaxVal / 4, cb)); in SplitRanges()
315 ASSERT_EQ(bitmap.ClearOne(i), ZX_OK, "clearing even bits"); in SplitRanges()
325 EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4, kMaxVal / 4, cb2)); in SplitRanges()
332 RleBitmap bitmap; in BoundaryArguments() local
334 EXPECT_EQ(bitmap.Set(0, 0), ZX_OK, "range contains no bits"); in BoundaryArguments()
335 EXPECT_EQ(bitmap.Set(5, 4), ZX_ERR_INVALID_ARGS, "max is less than off"); in BoundaryArguments()
336 EXPECT_EQ(bitmap.Set(5, 5), ZX_OK, "range contains no bits"); in BoundaryArguments()
338 EXPECT_EQ(bitmap.Clear(0, 0), ZX_OK, "range contains no bits"); in BoundaryArguments()
339 EXPECT_EQ(bitmap.Clear(5, 4), ZX_ERR_INVALID_ARGS, "max is less than off"); in BoundaryArguments()
340 EXPECT_EQ(bitmap.Clear(5, 5), ZX_OK, "range contains no bits"); in BoundaryArguments()
342 EXPECT_TRUE(bitmap.Get(0, 0), "range contains no bits, so all are true"); in BoundaryArguments()
343 EXPECT_TRUE(bitmap.Get(5, 4), "range contains no bits, so all are true"); in BoundaryArguments()
344 EXPECT_TRUE(bitmap.Get(5, 5), "range contains no bits, so all are true"); in BoundaryArguments()
352 RleBitmap bitmap; in NoAlloc() local
354 …EXPECT_EQ(bitmap.SetNoAlloc(0, 65536, nullptr), ZX_ERR_INVALID_ARGS, "set bits with nullptr freeli… in NoAlloc()
355 …EXPECT_EQ(bitmap.ClearNoAlloc(0, 65536, nullptr), ZX_ERR_INVALID_ARGS, "clear bits with nullptr fr… in NoAlloc()
358 …EXPECT_EQ(bitmap.SetNoAlloc(0, 65536, &free_list), ZX_ERR_NO_MEMORY, "set bits with empty freelist… in NoAlloc()
363 EXPECT_EQ(bitmap.SetNoAlloc(0, 65536, &free_list), ZX_OK, "set bits"); in NoAlloc()
364 EXPECT_TRUE(bitmap.Get(0, 65536), "get bit after setting"); in NoAlloc()
367 …EXPECT_EQ(bitmap.ClearNoAlloc(1, 65535, &free_list), ZX_ERR_NO_MEMORY, "clear bits with empty free… in NoAlloc()
371 EXPECT_EQ(bitmap.ClearNoAlloc(1, 65535, &free_list), ZX_OK, "clear bits"); in NoAlloc()
373 EXPECT_FALSE(bitmap.Get(0, 65536, &first_unset), "get bit after clearing"); in NoAlloc()
379 EXPECT_EQ(bitmap.SetNoAlloc(1, 65535, &free_list), ZX_OK, "add range back in"); in NoAlloc()
382 EXPECT_EQ(bitmap.ClearNoAlloc(0, 65536, &free_list), ZX_OK, "remove everything we allocated"); in NoAlloc()
390 RleBitmap bitmap; in SetOutOfOrder() local
391 EXPECT_EQ(bitmap.Set(0x64, 0x65), ZX_OK, "setting later"); in SetOutOfOrder()
392 EXPECT_EQ(bitmap.Set(0x60, 0x61), ZX_OK, "setting earlier"); in SetOutOfOrder()
393 EXPECT_EQ(bitmap.num_ranges(), 2U, "unexpected range count"); in SetOutOfOrder()
394 EXPECT_EQ(bitmap.num_bits(), 2U, "unexpected bit count"); in SetOutOfOrder()
395 EXPECT_TRUE(bitmap.Get(0x64, 0x65), "getting first set"); in SetOutOfOrder()
396 EXPECT_TRUE(bitmap.Get(0x60, 0x61), "getting second set"); in SetOutOfOrder()
400 static bool VerifyRange(const RleBitmap& bitmap, size_t bitoff, size_t bitmax, size_t min_val, in VerifyRange() argument
404 EXPECT_TRUE(bitmap.Get(bitoff, bitmax)); in VerifyRange()
405 EXPECT_EQ(bitmap.Find(false, min_val, max_val, bitoff - min_val, &out), ZX_OK); in VerifyRange()
407 EXPECT_EQ(bitmap.Find(false, min_val, max_val, max_val - bitmax, &out), ZX_OK); in VerifyRange()
409 EXPECT_EQ(bitmap.num_bits(), bitmax - bitoff); in VerifyRange()
413 static bool VerifyCleared(const RleBitmap& bitmap, size_t min_val, size_t max_val) { in VerifyCleared() argument
416 EXPECT_EQ(bitmap.Find(false, min_val, max_val, max_val - min_val, &out), ZX_OK); in VerifyCleared()
418 EXPECT_EQ(bitmap.num_bits(), 0); in VerifyCleared()
430 RleBitmap bitmap; in CheckOverlap() local
433 EXPECT_EQ(bitmap.Set(bitoff1, bitmax1), ZX_OK); in CheckOverlap()
434 EXPECT_EQ(bitmap.Set(bitoff2, bitmax2), ZX_OK); in CheckOverlap()
435 EXPECT_TRUE(VerifyRange(bitmap, min_off, max_max, min_val, max_val)); in CheckOverlap()
436 EXPECT_EQ(bitmap.Clear(min_off, max_max), ZX_OK); in CheckOverlap()
437 EXPECT_TRUE(VerifyCleared(bitmap, min_val, max_val)); in CheckOverlap()
459 RleBitmap bitmap; in FindRange() local
461 EXPECT_EQ(bitmap.Set(5, 10), ZX_OK, "setting range"); in FindRange()
462 EXPECT_EQ(bitmap.num_bits(), 5, "unexpected bit count"); in FindRange()
464 EXPECT_EQ(bitmap.Find(false, 0, 15, 5, &out), ZX_OK, "finding range"); in FindRange()
467 EXPECT_EQ(bitmap.Find(false, 1, 15, 5, &out), ZX_OK, "finding range"); in FindRange()
470 EXPECT_EQ(bitmap.Find(false, 0, 15, 6, &out), ZX_ERR_NO_RESOURCES, "finding range"); in FindRange()
473 EXPECT_EQ(bitmap.Find(true, 0, 15, 5, &out), ZX_OK, "finding range"); in FindRange()
476 EXPECT_EQ(bitmap.Find(true, 6, 15, 3, &out), ZX_OK, "finding range"); in FindRange()
479 EXPECT_EQ(bitmap.Find(true, 0, 15, 6, &out), ZX_ERR_NO_RESOURCES, "finding range"); in FindRange()
482 EXPECT_EQ(bitmap.Find(true, 0, 8, 4, &out), ZX_ERR_NO_RESOURCES, "finding range"); in FindRange()
485 EXPECT_EQ(bitmap.Set(20, 30), ZX_OK, "setting range"); in FindRange()
486 EXPECT_EQ(bitmap.num_bits(), 15, "unexpected bit count"); in FindRange()
488 EXPECT_EQ(bitmap.Find(false, 0, 50, 11, &out), ZX_OK, "finding range"); in FindRange()
491 EXPECT_EQ(bitmap.Find(false, 0, 40, 11, &out), ZX_ERR_NO_RESOURCES, "finding range"); in FindRange()
494 EXPECT_EQ(bitmap.Find(true, 0, 50, 5, &out), ZX_OK, "finding range"); in FindRange()
497 EXPECT_EQ(bitmap.Find(true, 0, 50, 7, &out), ZX_OK, "finding range"); in FindRange()
500 EXPECT_EQ(bitmap.Find(true, 7, 50, 5, &out), ZX_OK, "finding range"); in FindRange()
503 EXPECT_EQ(bitmap.Find(true, 0, 50, 11, &out), ZX_ERR_NO_RESOURCES, "finding range"); in FindRange()
506 EXPECT_EQ(bitmap.Find(true, 35, 50, 6, &out), ZX_ERR_NO_RESOURCES, "finding range"); in FindRange()