1// Copyright 2016 The Fuchsia Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include <bitmap/rle-bitmap.h> 6#include <fbl/algorithm.h> 7#include <fbl/alloc_checker.h> 8#include <unittest/unittest.h> 9 10namespace bitmap { 11namespace tests { 12 13typedef bool(VerifyCallback)(size_t index, size_t bitoff, size_t bitlen); 14 15static bool VerifyCounts(const RleBitmap& bitmap, size_t rng_expected, size_t bit_expected, 16 VerifyCallback cb) { 17 BEGIN_HELPER; 18 size_t rng_count = 0; 19 size_t bit_count = 0; 20 for (auto& range : bitmap) { 21 EXPECT_TRUE(cb(rng_count, range.bitoff, range.bitlen)); 22 rng_count++; 23 bit_count += range.bitlen; 24 } 25 26 EXPECT_EQ(rng_count, rng_expected, "unexpected range count"); 27 EXPECT_EQ(rng_count, bitmap.num_ranges(), "unexpected range count"); 28 EXPECT_EQ(bit_count, bit_expected, "unexpected bit count"); 29 EXPECT_EQ(bit_count, bitmap.num_bits(), "unexpected bit count"); 30 END_HELPER; 31} 32static bool InitializedEmpty(void) { 33 BEGIN_TEST; 34 35 RleBitmap bitmap; 36 EXPECT_FALSE(bitmap.Get(5, 6), "get one bit"); 37 for (__UNUSED auto& range : bitmap) { 38 EXPECT_FALSE(true, "iterating on empty set"); 39 } 40 41 END_TEST; 42} 43 44static bool SingleBit(void) { 45 BEGIN_TEST; 46 47 RleBitmap bitmap; 48 EXPECT_FALSE(bitmap.Get(2, 3), "get bit before setting"); 49 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"); 53 54 auto cb = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 55 BEGIN_HELPER; 56 EXPECT_EQ(bitoff, 2U, "bitoff"); 57 EXPECT_EQ(bitlen, 1U, "bitlen"); 58 END_HELPER; 59 }; 60 EXPECT_TRUE(VerifyCounts(bitmap, 1U, 1U, cb)); 61 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)); 65 66 END_TEST; 67} 68 69static bool SetTwice(void) { 70 BEGIN_TEST; 71 72 RleBitmap bitmap; 73 74 ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); 75 EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting"); 76 77 EXPECT_EQ(bitmap.num_bits(), 1); 78 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); 82 83 auto cb = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 84 BEGIN_HELPER; 85 EXPECT_EQ(bitoff, 2U, "bitoff"); 86 EXPECT_EQ(bitlen, 1U, "bitlen"); 87 END_HELPER; 88 }; 89 EXPECT_TRUE(VerifyCounts(bitmap, 1U, 1U, cb)); 90 91 END_TEST; 92} 93 94static bool ClearTwice(void) { 95 BEGIN_TEST; 96 97 RleBitmap bitmap; 98 99 ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); 100 EXPECT_EQ(bitmap.num_bits(), 1U, "unexpected bit count"); 101 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"); 105 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"); 109 110 for (__UNUSED auto& range : bitmap) { 111 EXPECT_FALSE(true, "iterating on empty set"); 112 } 113 114 END_TEST; 115} 116 117static bool GetReturnArg(void) { 118 BEGIN_TEST; 119 120 RleBitmap bitmap; 121 122 size_t first_unset = 0; 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"); 125 EXPECT_EQ(first_unset, 2U, "check returned arg"); 126 127 ASSERT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); 128 EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get bit after setting"); 129 EXPECT_EQ(first_unset, 3U, "check returned arg"); 130 131 first_unset = 0; 132 EXPECT_FALSE(bitmap.Get(2, 4, &first_unset), "get larger range after setting"); 133 EXPECT_EQ(first_unset, 3U, "check returned arg"); 134 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"); 137 EXPECT_EQ(first_unset, 4U, "check returned arg"); 138 139 auto cb = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 140 BEGIN_HELPER; 141 EXPECT_EQ(bitoff, 2U, "bitoff"); 142 EXPECT_EQ(bitlen, 2U, "bitlen"); 143 END_HELPER; 144 }; 145 EXPECT_TRUE(VerifyCounts(bitmap, 1U, 2U, cb)); 146 END_TEST; 147} 148 149static bool SetRange(void) { 150 BEGIN_TEST; 151 152 RleBitmap bitmap; 153 ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); 154 EXPECT_EQ(bitmap.num_bits(), 98U, "unexpected bit count"); 155 156 size_t first_unset = 0; 157 EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get first bit in range"); 158 EXPECT_EQ(first_unset, 3U, "check returned arg"); 159 160 EXPECT_TRUE(bitmap.Get(99, 100, &first_unset), "get last bit in range"); 161 EXPECT_EQ(first_unset, 100U, "check returned arg"); 162 163 EXPECT_FALSE(bitmap.Get(1, 2, &first_unset), "get bit before first in range"); 164 EXPECT_EQ(first_unset, 1U, "check returned arg"); 165 166 EXPECT_FALSE(bitmap.Get(100, 101, &first_unset), "get bit after last in range"); 167 EXPECT_EQ(first_unset, 100U, "check returned arg"); 168 169 EXPECT_TRUE(bitmap.Get(2, 100, &first_unset), "get entire range"); 170 EXPECT_EQ(first_unset, 100U, "check returned arg"); 171 172 EXPECT_TRUE(bitmap.Get(50, 80, &first_unset), "get part of range"); 173 EXPECT_EQ(first_unset, 80U, "check returned arg"); 174 175 END_TEST; 176} 177 178static bool ClearAll(void) { 179 BEGIN_TEST; 180 181 RleBitmap bitmap; 182 183 ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); 184 185 bitmap.ClearAll(); 186 187 for (__UNUSED auto& range : bitmap) { 188 EXPECT_FALSE(true, "iterating on empty set"); 189 } 190 191 ASSERT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); 192 193 for (auto& range : bitmap) { 194 EXPECT_EQ(range.bitoff, 2U, "bitoff"); 195 EXPECT_EQ(range.bitlen, 100U - 2U, "bitlen"); 196 } 197 198 auto cb = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 199 BEGIN_HELPER; 200 EXPECT_EQ(bitoff, 2U, "bitoff"); 201 EXPECT_EQ(bitlen, 100U - 2U, "bitlen"); 202 END_HELPER; 203 }; 204 205 EXPECT_TRUE(VerifyCounts(bitmap, 1U, 100U - 2U, cb)); 206 END_TEST; 207} 208 209static bool ClearSubrange(void) { 210 BEGIN_TEST; 211 212 RleBitmap bitmap; 213 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"); 218 219 size_t first_unset = 0; 220 EXPECT_FALSE(bitmap.Get(2, 100, &first_unset), "get whole original range"); 221 EXPECT_EQ(first_unset, 50U, "check returned arg"); 222 223 first_unset = 0; 224 EXPECT_TRUE(bitmap.Get(2, 50, &first_unset), "get first half range"); 225 EXPECT_EQ(first_unset, 50U, "check returned arg"); 226 227 EXPECT_TRUE(bitmap.Get(80, 100, &first_unset), "get second half range"); 228 EXPECT_EQ(first_unset, 100U, "check returned arg"); 229 230 EXPECT_FALSE(bitmap.Get(50, 80, &first_unset), "get cleared range"); 231 EXPECT_EQ(first_unset, 50U, "check returned arg"); 232 233 auto cb = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 234 BEGIN_HELPER; 235 if (index == 0) { 236 EXPECT_EQ(bitoff, 2U, "bitoff"); 237 EXPECT_EQ(bitlen, 50U - 2U, "bitlen"); 238 } else { 239 EXPECT_EQ(bitoff, 80U, "bitoff"); 240 EXPECT_EQ(bitlen, 100U - 80U, "bitlen"); 241 } 242 END_HELPER; 243 }; 244 245 EXPECT_TRUE(VerifyCounts(bitmap, 2U, 68U, cb)); 246 END_TEST; 247} 248 249static bool MergeRanges(void) { 250 BEGIN_TEST; 251 252 RleBitmap bitmap; 253 254 constexpr size_t kMaxVal = 100; 255 256 for (size_t i = 0; i < kMaxVal; i += 2) { 257 ASSERT_EQ(bitmap.SetOne(i), ZX_OK, "setting even bits"); 258 } 259 260 auto cb = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 261 BEGIN_HELPER; 262 EXPECT_EQ(bitoff, 2 * index, "bitoff"); 263 EXPECT_EQ(bitlen, 1U, "bitlen"); 264 END_HELPER; 265 }; 266 267 EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 2, kMaxVal / 2, cb)); 268 269 for (size_t i = 1; i < kMaxVal; i += 4) { 270 ASSERT_EQ(bitmap.SetOne(i), ZX_OK, "setting congruent 1 mod 4 bits"); 271 } 272 273 auto cb2 = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 274 BEGIN_HELPER; 275 EXPECT_EQ(bitoff, 4 * index, "bitoff"); 276 EXPECT_EQ(bitlen, 3U, "bitlen"); 277 END_HELPER; 278 }; 279 280 EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4, 3 * kMaxVal / 4, cb2)); 281 END_TEST; 282} 283 284static bool SplitRanges(void) { 285 BEGIN_TEST; 286 287 RleBitmap bitmap; 288 289 constexpr size_t kMaxVal = 100; 290 ASSERT_EQ(bitmap.Set(0, kMaxVal), ZX_OK, "setting all bits"); 291 292 for (size_t i = 1; i < kMaxVal; i += 4) { 293 ASSERT_EQ(bitmap.ClearOne(i), ZX_OK, "clearing congruent 1 mod 4 bits"); 294 } 295 296 auto cb = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 297 BEGIN_HELPER; 298 if (index == 0) { 299 EXPECT_EQ(bitoff, 0U, "bitoff"); 300 EXPECT_EQ(bitlen, 1U, "bitlen"); 301 } else { 302 size_t offset = 4 * index - 2; 303 size_t len = fbl::min(size_t(3), kMaxVal - offset); 304 EXPECT_EQ(bitoff, offset, "bitoff"); 305 EXPECT_EQ(bitlen, len, "bitlen"); 306 } 307 END_HELPER; 308 }; 309 310 EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4 + 1, 3 * kMaxVal / 4, cb)); 311 312 for (size_t i = 0; i < kMaxVal; i += 2) { 313 ASSERT_EQ(bitmap.ClearOne(i), ZX_OK, "clearing even bits"); 314 } 315 316 auto cb2 = [](size_t index, size_t bitoff, size_t bitlen) -> bool { 317 BEGIN_HELPER; 318 EXPECT_EQ(bitoff, 4 * index + 3, "bitoff"); 319 EXPECT_EQ(bitlen, 1U, "bitlen"); 320 END_HELPER; 321 }; 322 323 EXPECT_TRUE(VerifyCounts(bitmap, kMaxVal / 4, kMaxVal / 4, cb2)); 324 END_TEST; 325} 326 327static bool BoundaryArguments(void) { 328 BEGIN_TEST; 329 330 RleBitmap bitmap; 331 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"); 335 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"); 339 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"); 343 344 END_TEST; 345} 346 347static bool NoAlloc(void) { 348 BEGIN_TEST; 349 350 RleBitmap bitmap; 351 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"); 354 355 RleBitmap::FreeList free_list; 356 EXPECT_EQ(bitmap.SetNoAlloc(0, 65536, &free_list), ZX_ERR_NO_MEMORY, "set bits with empty freelist"); 357 358 fbl::AllocChecker ac; 359 free_list.push_back(fbl::unique_ptr<RleBitmapElement>(new (&ac) RleBitmapElement())); 360 ASSERT_TRUE(ac.check(), "alloc check"); 361 EXPECT_EQ(bitmap.SetNoAlloc(0, 65536, &free_list), ZX_OK, "set bits"); 362 EXPECT_TRUE(bitmap.Get(0, 65536), "get bit after setting"); 363 EXPECT_EQ(free_list.size_slow(), 0U, "free list empty after alloc"); 364 365 EXPECT_EQ(bitmap.ClearNoAlloc(1, 65535, &free_list), ZX_ERR_NO_MEMORY, "clear bits with empty freelist and alloc needed"); 366 367 free_list.push_back(fbl::unique_ptr<RleBitmapElement>(new (&ac) RleBitmapElement())); 368 ASSERT_TRUE(ac.check(), "alloc check"); 369 EXPECT_EQ(bitmap.ClearNoAlloc(1, 65535, &free_list), ZX_OK, "clear bits"); 370 size_t first_unset = 0; 371 EXPECT_FALSE(bitmap.Get(0, 65536, &first_unset), "get bit after clearing"); 372 EXPECT_EQ(first_unset, 1U, "check first_unset"); 373 EXPECT_EQ(free_list.size_slow(), 0U, "free list empty after alloc"); 374 375 free_list.push_back(fbl::unique_ptr<RleBitmapElement>(new (&ac) RleBitmapElement())); 376 ASSERT_TRUE(ac.check(), "alloc check"); 377 EXPECT_EQ(bitmap.SetNoAlloc(1, 65535, &free_list), ZX_OK, "add range back in"); 378 EXPECT_EQ(free_list.size_slow(), 2U, "free list has two entries after starting with one and merging two existing ranges"); 379 380 EXPECT_EQ(bitmap.ClearNoAlloc(0, 65536, &free_list), ZX_OK, "remove everything we allocated"); 381 EXPECT_EQ(free_list.size_slow(), 3U, "free list has as many entries as we allocated"); 382 383 END_TEST; 384} 385 386static bool SetOutOfOrder(void) { 387 BEGIN_TEST; 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"); 395 END_TEST; 396} 397 398static bool VerifyRange(const RleBitmap& bitmap, size_t bitoff, size_t bitmax, size_t min_val, 399 size_t max_val) { 400 BEGIN_HELPER; 401 size_t out; 402 EXPECT_TRUE(bitmap.Get(bitoff, bitmax)); 403 EXPECT_EQ(bitmap.Find(false, min_val, max_val, bitoff - min_val, &out), ZX_OK); 404 EXPECT_EQ(out, min_val); 405 EXPECT_EQ(bitmap.Find(false, min_val, max_val, max_val - bitmax, &out), ZX_OK); 406 EXPECT_EQ(out, bitmax); 407 EXPECT_EQ(bitmap.num_bits(), bitmax - bitoff); 408 END_HELPER; 409} 410 411static bool VerifyCleared(const RleBitmap& bitmap, size_t min_val, size_t max_val) { 412 BEGIN_HELPER; 413 size_t out; 414 EXPECT_EQ(bitmap.Find(false, min_val, max_val, max_val - min_val, &out), ZX_OK); 415 EXPECT_EQ(out, min_val); 416 EXPECT_EQ(bitmap.num_bits(), 0); 417 END_HELPER; 418} 419 420static bool CheckOverlap(size_t bitoff1, size_t bitmax1, size_t bitoff2, size_t bitmax2, 421 size_t min_val, size_t max_val) { 422 BEGIN_HELPER; 423 EXPECT_GE(bitoff1, min_val); 424 EXPECT_GE(bitoff2, min_val); 425 EXPECT_LE(bitmax1, max_val); 426 EXPECT_LE(bitmax2, max_val); 427 428 RleBitmap bitmap; 429 size_t min_off = fbl::min(bitoff1, bitoff2); 430 size_t max_max = fbl::max(bitmax1, bitmax2); 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)); 436 END_HELPER; 437} 438 439static bool SetOverlap(void) { 440 BEGIN_TEST; 441 EXPECT_TRUE(CheckOverlap(5, 6, 4, 5, 0, 100)); 442 EXPECT_TRUE(CheckOverlap(3, 5, 1, 4, 0, 100)); 443 EXPECT_TRUE(CheckOverlap(1, 6, 3, 5, 0, 100)); 444 EXPECT_TRUE(CheckOverlap(20, 30, 10, 20, 0, 100)); 445 EXPECT_TRUE(CheckOverlap(20, 30, 15, 25, 0, 100)); 446 EXPECT_TRUE(CheckOverlap(10, 20, 15, 20, 0, 100)); 447 EXPECT_TRUE(CheckOverlap(10, 20, 15, 25, 0, 100)); 448 EXPECT_TRUE(CheckOverlap(10, 30, 15, 25, 0, 100)); 449 EXPECT_TRUE(CheckOverlap(15, 25, 10, 30, 0, 100)); 450 END_TEST; 451} 452 453static bool FindRange(void) { 454 BEGIN_TEST; 455 456 size_t out; 457 RleBitmap bitmap; 458 459 EXPECT_EQ(bitmap.Set(5, 10), ZX_OK, "setting range"); 460 EXPECT_EQ(bitmap.num_bits(), 5, "unexpected bit count"); 461 // Find unset run before range 462 EXPECT_EQ(bitmap.Find(false, 0, 15, 5, &out), ZX_OK, "finding range"); 463 EXPECT_EQ(out, 0, "unexpected bitoff"); 464 // Find unset run after range 465 EXPECT_EQ(bitmap.Find(false, 1, 15, 5, &out), ZX_OK, "finding range"); 466 EXPECT_EQ(out, 10, "unexpected bitoff"); 467 // Unset range too large 468 EXPECT_EQ(bitmap.Find(false, 0, 15, 6, &out), ZX_ERR_NO_RESOURCES, "finding range"); 469 EXPECT_EQ(out, 15, "unexpected bitoff"); 470 // Find entire set range 471 EXPECT_EQ(bitmap.Find(true, 0, 15, 5, &out), ZX_OK, "finding range"); 472 EXPECT_EQ(out, 5, "unexpected bitoff"); 473 // Find set run within range 474 EXPECT_EQ(bitmap.Find(true, 6, 15, 3, &out), ZX_OK, "finding range"); 475 EXPECT_EQ(out, 6, "unexpected bitoff"); 476 // Set range too large 477 EXPECT_EQ(bitmap.Find(true, 0, 15, 6, &out), ZX_ERR_NO_RESOURCES, "finding range"); 478 EXPECT_EQ(out, 15, "unexpected bitoff"); 479 // Set range too large 480 EXPECT_EQ(bitmap.Find(true, 0, 8, 4, &out), ZX_ERR_NO_RESOURCES, "finding range"); 481 EXPECT_EQ(out, 8, "unexpected bitoff"); 482 483 EXPECT_EQ(bitmap.Set(20, 30), ZX_OK, "setting range"); 484 EXPECT_EQ(bitmap.num_bits(), 15, "unexpected bit count"); 485 // Find unset run after both ranges 486 EXPECT_EQ(bitmap.Find(false, 0, 50, 11, &out), ZX_OK, "finding range"); 487 EXPECT_EQ(out, 30, "unexpected bitoff"); 488 // Unset range too large 489 EXPECT_EQ(bitmap.Find(false, 0, 40, 11, &out), ZX_ERR_NO_RESOURCES, "finding range"); 490 EXPECT_EQ(out, 40, "unexpected bitoff"); 491 // Find set run in first range 492 EXPECT_EQ(bitmap.Find(true, 0, 50, 5, &out), ZX_OK, "finding range"); 493 EXPECT_EQ(out, 5, "unexpected bitoff"); 494 // Find set run in second range 495 EXPECT_EQ(bitmap.Find(true, 0, 50, 7, &out), ZX_OK, "finding range"); 496 EXPECT_EQ(out, 20, "unexpected bitoff"); 497 // Find set run in second range 498 EXPECT_EQ(bitmap.Find(true, 7, 50, 5, &out), ZX_OK, "finding range"); 499 EXPECT_EQ(out, 20, "unexpected bitoff"); 500 // Set range too large 501 EXPECT_EQ(bitmap.Find(true, 0, 50, 11, &out), ZX_ERR_NO_RESOURCES, "finding range"); 502 EXPECT_EQ(out, 50, "unexpected bitoff"); 503 // Set range too large 504 EXPECT_EQ(bitmap.Find(true, 35, 50, 6, &out), ZX_ERR_NO_RESOURCES, "finding range"); 505 EXPECT_EQ(out, 50, "unexpected bitoff"); 506 END_TEST; 507} 508 509BEGIN_TEST_CASE(rle_bitmap_tests) 510RUN_TEST(InitializedEmpty) 511RUN_TEST(SingleBit) 512RUN_TEST(SetTwice) 513RUN_TEST(ClearTwice) 514RUN_TEST(GetReturnArg) 515RUN_TEST(SetRange) 516RUN_TEST(ClearSubrange) 517RUN_TEST(MergeRanges) 518RUN_TEST(SplitRanges) 519RUN_TEST(BoundaryArguments) 520RUN_TEST(NoAlloc) 521RUN_TEST(ClearAll) 522RUN_TEST(SetOutOfOrder) 523RUN_TEST(SetOverlap) 524RUN_TEST(FindRange) 525END_TEST_CASE(rle_bitmap_tests); 526 527} // namespace tests 528} // namespace bitmap 529