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/raw-bitmap.h> 6#include <bitmap/storage.h> 7 8#include <fbl/algorithm.h> 9#include <fbl/alloc_checker.h> 10#include <unittest/unittest.h> 11 12namespace bitmap { 13namespace tests { 14 15template <typename RawBitmap> static bool InitializedEmpty(void) { 16 BEGIN_TEST; 17 18 RawBitmap bitmap; 19 EXPECT_EQ(bitmap.Reset(0), ZX_OK); 20 EXPECT_EQ(bitmap.size(), 0U, "get size"); 21 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"); 25 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"); 30 31 END_TEST; 32} 33 34template <typename RawBitmap> static bool SingleBit(void) { 35 BEGIN_TEST; 36 37 RawBitmap bitmap; 38 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 39 EXPECT_EQ(bitmap.size(), 128U, "get size"); 40 41 EXPECT_FALSE(bitmap.GetOne(2), "get bit before setting"); 42 43 EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); 44 EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting"); 45 46 EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit"); 47 EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing"); 48 49 END_TEST; 50} 51 52template <typename RawBitmap> static bool SetTwice(void) { 53 BEGIN_TEST; 54 55 RawBitmap bitmap; 56 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 57 EXPECT_EQ(bitmap.size(), 128U, "get size"); 58 59 EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); 60 EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting"); 61 62 EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit again"); 63 EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting again"); 64 65 END_TEST; 66} 67 68template <typename RawBitmap> static bool ClearTwice(void) { 69 BEGIN_TEST; 70 71 RawBitmap bitmap; 72 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 73 EXPECT_EQ(bitmap.size(), 128U, "get size"); 74 75 EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); 76 77 EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit"); 78 EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing"); 79 80 EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit again"); 81 EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing again"); 82 83 END_TEST; 84} 85 86template <typename RawBitmap> static bool GetReturnArg(void) { 87 BEGIN_TEST; 88 89 RawBitmap bitmap; 90 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 91 EXPECT_EQ(bitmap.size(), 128U, "get size"); 92 93 size_t first_unset = 0; 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"); 96 EXPECT_EQ(first_unset, 2U, "check returned arg"); 97 98 EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit"); 99 EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get bit after setting"); 100 EXPECT_EQ(first_unset, 3U, "check returned arg"); 101 102 first_unset = 0; 103 EXPECT_FALSE(bitmap.Get(2, 4, &first_unset), "get larger range after setting"); 104 EXPECT_EQ(first_unset, 3U, "check returned arg"); 105 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"); 108 EXPECT_EQ(first_unset, 4U, "check returned arg"); 109 110 END_TEST; 111} 112 113template <typename RawBitmap> static bool SetRange(void) { 114 BEGIN_TEST; 115 116 RawBitmap bitmap; 117 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 118 EXPECT_EQ(bitmap.size(), 128U, "get size"); 119 120 EXPECT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); 121 122 size_t first_unset = 0; 123 EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get first bit in range"); 124 EXPECT_EQ(first_unset, 3U, "check returned arg"); 125 126 EXPECT_TRUE(bitmap.Get(99, 100, &first_unset), "get last bit in range"); 127 EXPECT_EQ(first_unset, 100U, "check returned arg"); 128 129 EXPECT_FALSE(bitmap.Get(1, 2, &first_unset), "get bit before first in range"); 130 EXPECT_EQ(first_unset, 1U, "check returned arg"); 131 132 EXPECT_FALSE(bitmap.Get(100, 101, &first_unset), "get bit after last in range"); 133 EXPECT_EQ(first_unset, 100U, "check returned arg"); 134 135 EXPECT_TRUE(bitmap.Get(2, 100, &first_unset), "get entire range"); 136 EXPECT_EQ(first_unset, 100U, "check returned arg"); 137 138 EXPECT_TRUE(bitmap.Get(50, 80, &first_unset), "get part of range"); 139 EXPECT_EQ(first_unset, 80U, "check returned arg"); 140 141 size_t result; 142 EXPECT_FALSE(bitmap.Scan(0, 100, true, &result), "scan set bits"); 143 EXPECT_EQ(result, 0U, "scan set bits"); 144 EXPECT_FALSE(bitmap.ReverseScan(0, 100, true, &result), "reverse scan set bits"); 145 EXPECT_EQ(result, 1U, "reverse scan set bits"); 146 147 EXPECT_FALSE(bitmap.Scan(0, 100, false, &result), "scan cleared bits"); 148 EXPECT_EQ(result, 2U, "scan cleared bits to start"); 149 EXPECT_FALSE(bitmap.ReverseScan(0, 100, false, &result), "reverse scan cleared bits"); 150 EXPECT_EQ(result, 99U, "reverse scan cleared bits"); 151 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"); 154 155 EXPECT_FALSE(bitmap.Scan(2, 100, false, &result), "scan cleared bits in set range"); 156 EXPECT_EQ(result, 2U, "scan cleared bits in set range"); 157 EXPECT_FALSE(bitmap.ReverseScan(2, 100, false, &result), 158 "reverse scan cleared bits in set range"); 159 EXPECT_EQ(result, 99U, "reverse scan cleared bits in set range"); 160 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"); 163 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"); 166 167 END_TEST; 168} 169 170template <typename RawBitmap> static bool FindSimple(void) { 171 BEGIN_TEST; 172 173 RawBitmap bitmap; 174 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 175 EXPECT_EQ(bitmap.size(), 128U, "get size"); 176 177 size_t bitoff_start; 178 179 // Invalid finds 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"); 186 187 // Finds from offset zero 188 EXPECT_EQ(bitmap.Find(false, 0, 100, 1, &bitoff_start), ZX_OK, "find unset"); 189 EXPECT_EQ(bitoff_start, 0, "check returned arg"); 190 EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 1, &bitoff_start), ZX_OK, "reverse find unset"); 191 EXPECT_EQ(bitoff_start, 99, "check returned arg"); 192 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, 195 "reverse find set"); 196 197 EXPECT_EQ(bitmap.Find(false, 0, 100, 5, &bitoff_start), ZX_OK, "find more unset"); 198 EXPECT_EQ(bitoff_start, 0, "check returned arg"); 199 EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 5, &bitoff_start), ZX_OK, 200 "reverse find more unset"); 201 EXPECT_EQ(bitoff_start, 95, "check returned arg"); 202 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, 205 "reverse find more set"); 206 207 EXPECT_EQ(bitmap.Find(false, 0, 100, 100, &bitoff_start), ZX_OK, "find all unset"); 208 EXPECT_EQ(bitoff_start, 0, "check returned arg"); 209 EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 100, &bitoff_start), ZX_OK, 210 "reverse find all unset"); 211 EXPECT_EQ(bitoff_start, 0, "check returned arg"); 212 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, 215 "reverse find all set"); 216 217 // Finds at an offset 218 EXPECT_EQ(bitmap.Find(false, 50, 100, 3, &bitoff_start), ZX_OK, "find at offset"); 219 EXPECT_EQ(bitoff_start, 50, "check returned arg"); 220 EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 3, &bitoff_start), ZX_OK, 221 "reverse find at offset"); 222 EXPECT_EQ(bitoff_start, 97, "check returned arg"); 223 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, 226 "reverse fail at offset"); 227 228 EXPECT_EQ(bitmap.Find(false, 90, 100, 10, &bitoff_start), ZX_OK, "find at offset end"); 229 EXPECT_EQ(bitoff_start, 90, "check returned arg"); 230 EXPECT_EQ(bitmap.ReverseFind(false, 90, 100, 10, &bitoff_start), ZX_OK, 231 "reverse find at offset end"); 232 EXPECT_EQ(bitoff_start, 90, "check returned arg"); 233 234 // Invalid scans 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, 237 "no space"); 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, 240 "no space"); 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, 243 "no space"); 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"); 246 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"); 254 255 EXPECT_EQ(bitmap.Find(false, 0, 50, 5, &bitoff_start), ZX_OK, "find in first group"); 256 EXPECT_EQ(bitoff_start, 0, "check returned arg"); 257 EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 5, &bitoff_start), ZX_OK, 258 "reverse find in first group"); 259 EXPECT_EQ(bitoff_start, 95, "check returned arg"); 260 261 EXPECT_EQ(bitmap.Find(false, 0, 50, 10, &bitoff_start), ZX_OK, "find in second group"); 262 EXPECT_EQ(bitoff_start, 10, "check returned arg"); 263 EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 10, &bitoff_start), ZX_OK, 264 "reverse find in second group"); 265 EXPECT_EQ(bitoff_start, 80, "check returned arg"); 266 267 EXPECT_EQ(bitmap.Find(false, 0, 50, 15, &bitoff_start), ZX_OK, "find in third group"); 268 EXPECT_EQ(bitoff_start, 35, "check returned arg"); 269 EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 15, &bitoff_start), ZX_OK, 270 "reverse find in third group"); 271 EXPECT_EQ(bitoff_start, 50, "check returned arg"); 272 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, 275 "reverse fail to find"); 276 277 EXPECT_EQ(bitmap.Find(false, 5, 20, 10, &bitoff_start), ZX_OK, "find space (offset)"); 278 EXPECT_EQ(bitoff_start, 10, "check returned arg"); 279 EXPECT_EQ(bitmap.ReverseFind(false, 80, 95, 10, &bitoff_start), ZX_OK, 280 "reverse find space (offset)"); 281 EXPECT_EQ(bitoff_start, 80, "check returned arg"); 282 283 EXPECT_EQ(bitmap.Find(false, 5, 25, 10, &bitoff_start), ZX_OK, "find space (offset)"); 284 EXPECT_EQ(bitoff_start, 10, "check returned arg"); 285 EXPECT_EQ(bitmap.ReverseFind(false, 75, 95, 10, &bitoff_start), ZX_OK, 286 "reverse find space (offset)"); 287 EXPECT_EQ(bitoff_start, 80, "check returned arg"); 288 289 EXPECT_EQ(bitmap.Find(false, 5, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, 290 "fail to find (offset)"); 291 EXPECT_EQ(bitmap.ReverseFind(false, 85, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, 292 "reverse fail to find (offset)"); 293 294 EXPECT_EQ(bitmap.Find(true, 0, 15, 2, &bitoff_start), ZX_OK, "find set bits"); 295 EXPECT_EQ(bitoff_start, 5, "check returned arg"); 296 EXPECT_EQ(bitmap.ReverseFind(true, 85, 100, 2, &bitoff_start), ZX_OK, "reverse find set bits"); 297 EXPECT_EQ(bitoff_start, 93, "check returned arg"); 298 299 EXPECT_EQ(bitmap.Find(true, 0, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, 300 "find set bits (fail)"); 301 EXPECT_EQ(bitmap.ReverseFind(true, 85, 100, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, 302 "reverse find set bits (fail)"); 303 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, 306 "reverse fail to find"); 307 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, 310 "reverse fail to find"); 311 312 EXPECT_EQ(bitmap.Find(true, 32, 35, 4, &bitoff_start), ZX_ERR_NO_RESOURCES, 313 "fail to find (set)"); 314 EXPECT_EQ(bitmap.ReverseFind(true, 65, 68, 4, &bitoff_start), ZX_ERR_NO_RESOURCES, 315 "reverse fail to find (set)"); 316 317 // Fill the whole bitmap 318 EXPECT_EQ(bitmap.Set(0, 128), ZX_OK, "set range"); 319 320 EXPECT_EQ(bitmap.Find(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, 321 "fail to find (small)"); 322 EXPECT_EQ(bitmap.ReverseFind(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, 323 "reverse fail to find (small)"); 324 325 EXPECT_EQ(bitmap.Find(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, 326 "fail to find (large)"); 327 EXPECT_EQ(bitmap.ReverseFind(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, 328 "reverse fail to find (large)"); 329 330 END_TEST; 331} 332 333template <typename RawBitmap> static bool ClearAll(void) { 334 BEGIN_TEST; 335 336 RawBitmap bitmap; 337 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 338 EXPECT_EQ(bitmap.size(), 128U, "get size"); 339 340 EXPECT_EQ(bitmap.Set(0, 100), ZX_OK, "set range"); 341 342 bitmap.ClearAll(); 343 344 size_t first = 0; 345 EXPECT_FALSE(bitmap.Get(2, 100, &first), "get range"); 346 EXPECT_EQ(first, 2U, "all clear"); 347 348 EXPECT_EQ(bitmap.Set(0, 99), ZX_OK, "set range"); 349 EXPECT_FALSE(bitmap.Get(0, 100, &first), "get range"); 350 EXPECT_EQ(first, 99U, "all clear"); 351 352 END_TEST; 353} 354 355template <typename RawBitmap> static bool ClearSubrange(void) { 356 BEGIN_TEST; 357 358 RawBitmap bitmap; 359 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 360 EXPECT_EQ(bitmap.size(), 128U, "get size"); 361 362 EXPECT_EQ(bitmap.Set(2, 100), ZX_OK, "set range"); 363 EXPECT_EQ(bitmap.Clear(50, 80), ZX_OK, "clear range"); 364 365 size_t first_unset = 0; 366 EXPECT_FALSE(bitmap.Get(2, 100, &first_unset), "get whole original range"); 367 EXPECT_EQ(first_unset, 50U, "check returned arg"); 368 369 first_unset = 0; 370 EXPECT_TRUE(bitmap.Get(2, 50, &first_unset), "get first half range"); 371 EXPECT_EQ(first_unset, 50U, "check returned arg"); 372 373 EXPECT_TRUE(bitmap.Get(80, 100, &first_unset), "get second half range"); 374 EXPECT_EQ(first_unset, 100U, "check returned arg"); 375 376 EXPECT_FALSE(bitmap.Get(50, 80, &first_unset), "get cleared range"); 377 EXPECT_EQ(first_unset, 50U, "check returned arg"); 378 379 END_TEST; 380} 381 382template <typename RawBitmap> static bool BoundaryArguments(void) { 383 BEGIN_TEST; 384 385 RawBitmap bitmap; 386 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 387 EXPECT_EQ(bitmap.size(), 128U, "get size"); 388 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"); 392 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"); 396 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"); 400 401 END_TEST; 402} 403 404template <typename RawBitmap> static bool SetOutOfOrder(void) { 405 BEGIN_TEST; 406 407 RawBitmap bitmap; 408 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 409 EXPECT_EQ(bitmap.size(), 128U, "get size"); 410 411 EXPECT_EQ(bitmap.SetOne(0x64), ZX_OK, "setting later"); 412 EXPECT_EQ(bitmap.SetOne(0x60), ZX_OK, "setting earlier"); 413 414 EXPECT_TRUE(bitmap.GetOne(0x64), "getting first set"); 415 EXPECT_TRUE(bitmap.GetOne(0x60), "getting second set"); 416 END_TEST; 417} 418 419template <typename RawBitmap> static bool GrowAcrossPage(void) { 420 BEGIN_TEST; 421 422 RawBitmap bitmap; 423 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 424 EXPECT_EQ(bitmap.size(), 128u); 425 426 EXPECT_FALSE(bitmap.GetOne(100)); 427 EXPECT_EQ(bitmap.SetOne(100), ZX_OK); 428 EXPECT_TRUE(bitmap.GetOne(100)); 429 430 size_t bitoff_start; 431 EXPECT_EQ(bitmap.Find(true, 101, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, 432 "Expected tail end of bitmap to be unset"); 433 434 // We can't set bits out of range 435 EXPECT_NE(bitmap.SetOne(16 * PAGE_SIZE - 1), ZX_OK); 436 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"); 440 441 // Now we can set the previously inaccessible bits 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)); 445 446 // But our orignal 'set bit' is still set 447 EXPECT_TRUE(bitmap.GetOne(100), "Growing should not unset bits"); 448 449 // If we shrink and re-expand the bitmap, it should 450 // have cleared the underlying bits 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)); 455 456 END_TEST; 457} 458 459template <typename RawBitmap> static bool GrowShrink(void) { 460 BEGIN_TEST; 461 462 RawBitmap bitmap; 463 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 464 EXPECT_EQ(bitmap.size(), 128u); 465 466 EXPECT_FALSE(bitmap.GetOne(100)); 467 EXPECT_EQ(bitmap.SetOne(100), ZX_OK); 468 EXPECT_TRUE(bitmap.GetOne(100)); 469 470 for (size_t i = 8; i < 16; i++) { 471 for (int j = -16; j <= 16; j++) { 472 size_t bitmap_size = (1 << i) + j; 473 474 for (size_t shrink_len = 1; shrink_len < 32; shrink_len++) { 475 EXPECT_EQ(bitmap.Reset(bitmap_size), ZX_OK); 476 EXPECT_EQ(bitmap.size(), bitmap_size); 477 478 // This bit will be eliminated by shrink / grow 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)); 482 483 // This bit will stay 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)); 487 488 EXPECT_EQ(bitmap.Shrink(bitmap_size - shrink_len), ZX_OK); 489 EXPECT_EQ(bitmap.Grow(bitmap_size), ZX_OK); 490 491 EXPECT_FALSE(bitmap.GetOne(bitmap_size - shrink_len), 492 "Expected 'shrunk' bit to be unset"); 493 EXPECT_TRUE(bitmap.GetOne(bitmap_size - shrink_len - 1), 494 "Expected bit outside shrink range to be set"); 495 496 size_t bitoff_start; 497 EXPECT_EQ( 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"); 500 } 501 } 502 } 503 504 END_TEST; 505} 506 507template <typename RawBitmap> static bool GrowFailure(void) { 508 BEGIN_TEST; 509 510 RawBitmap bitmap; 511 EXPECT_EQ(bitmap.Reset(128), ZX_OK); 512 EXPECT_EQ(bitmap.size(), 128u); 513 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); 518 END_TEST; 519} 520 521#define RUN_TEMPLATIZED_TEST(test, specialization) RUN_TEST(test<specialization>) 522#define ALL_TESTS(specialization) \ 523 RUN_TEMPLATIZED_TEST(InitializedEmpty, specialization) \ 524 RUN_TEMPLATIZED_TEST(SingleBit, specialization) \ 525 RUN_TEMPLATIZED_TEST(SetTwice, specialization) \ 526 RUN_TEMPLATIZED_TEST(ClearTwice, specialization) \ 527 RUN_TEMPLATIZED_TEST(GetReturnArg, specialization) \ 528 RUN_TEMPLATIZED_TEST(SetRange, specialization) \ 529 RUN_TEMPLATIZED_TEST(FindSimple, specialization) \ 530 RUN_TEMPLATIZED_TEST(ClearSubrange, specialization) \ 531 RUN_TEMPLATIZED_TEST(BoundaryArguments, specialization) \ 532 RUN_TEMPLATIZED_TEST(ClearAll, specialization) \ 533 RUN_TEMPLATIZED_TEST(SetOutOfOrder, specialization) 534 535BEGIN_TEST_CASE(raw_bitmap_tests) 536ALL_TESTS(RawBitmapGeneric<DefaultStorage>) 537ALL_TESTS(RawBitmapGeneric<VmoStorage>) 538RUN_TEST(GrowAcrossPage<RawBitmapGeneric<VmoStorage>>) 539RUN_TEST(GrowShrink<RawBitmapGeneric<VmoStorage>>) 540RUN_TEST(GrowFailure<RawBitmapGeneric<DefaultStorage>>) 541END_TEST_CASE(raw_bitmap_tests); 542 543} // namespace tests 544} // namespace bitmap 545