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