[bitmap] Add reverse scanning
This CL adds RScan and RFind to complement Scan and Find, respectively.
The functions find the last occurences of a non-matching bit or run of
matching bits, instead of the first.
The interface for Scan and Find has also slightly changed: while
returning "bitmax" made some sense on failure before, returning "bitoff"
doesn't for the reverse versions since it would be a valid offset.
Returning "bitoff-1" is similarly problematic, as bitoff may be 0.
Instead, Scan now returns a bool, and Find does not set "out" in their
respective failure cases.
ZX-1781 #comment Fixed
Change-Id: Ied08f8c74bca17e7b537d16075a2005e00d536fc
diff --git a/kernel/lib/hypervisor/include/hypervisor/interrupt_tracker.h b/kernel/lib/hypervisor/include/hypervisor/interrupt_tracker.h
index c0d6caf..c10139f 100644
--- a/kernel/lib/hypervisor/include/hypervisor/interrupt_tracker.h
+++ b/kernel/lib/hypervisor/include/hypervisor/interrupt_tracker.h
@@ -26,7 +26,7 @@
// Returns whether there are pending interrupts.
bool Pending() {
AutoSpinLock lock(&lock_);
- return bitmap_.Scan(0, N, false) != N;
+ return !bitmap_.Scan(0, N, false);
}
bool TryPop(uint32_t vector) {
@@ -40,16 +40,15 @@
// Pops the highest priority interrupt.
zx_status_t Pop(uint32_t* vector) {
- uint32_t value;
+ size_t value;
{
AutoSpinLock lock(&lock_);
- value = static_cast<uint32_t>(bitmap_.Scan(0, N, false));
- if (value == N) {
+ if (bitmap_.Scan(0, N, false, &value)) {
return ZX_ERR_NOT_FOUND;
}
bitmap_.ClearOne(value);
}
- *vector = reverse(value);
+ *vector = reverse(static_cast<uint32_t>(value));
return ZX_OK;
}
diff --git a/system/ulib/bitmap/include/bitmap/raw-bitmap.h b/system/ulib/bitmap/include/bitmap/raw-bitmap.h
index 2aac169..4e10bfa 100644
--- a/system/ulib/bitmap/include/bitmap/raw-bitmap.h
+++ b/system/ulib/bitmap/include/bitmap/raw-bitmap.h
@@ -11,11 +11,11 @@
#include <stdint.h>
#include <string.h>
-#include <zircon/assert.h>
-#include <zircon/types.h>
#include <fbl/algorithm.h>
#include <fbl/macros.h>
#include <fbl/type_support.h>
+#include <zircon/assert.h>
+#include <zircon/types.h>
namespace bitmap {
namespace internal {
@@ -45,15 +45,24 @@
// restrict access to a smaller portion of the bitmap (via Shrink).
zx_status_t Shrink(size_t size);
- // Returns the lesser of bitmax and the index of the first bit that doesn't
- // match *is_set* starting from *bitoff*.
- size_t Scan(size_t bitoff, size_t bitmax, bool is_set) const;
+ // Returns true if all bits in the range [*bitoff*, *bitmax*) match
+ // *is_set*, otherwise returns false and sets *out* (if provided) to the
+ // first (or last, in the case of ReverseScan) bit that doesn't match. An
+ // empty region (i.e. *bitoff* is greater than *bitmax*, or *bitoff* is
+ // outside the range of the bitmap) will return true.
+ bool Scan(size_t bitoff, size_t bitmax, bool is_set,
+ size_t* out = nullptr) const;
+ bool ReverseScan(size_t bitoff, size_t bitmax, bool is_set,
+ size_t* out = nullptr) const;
- // Find a run of *run_len* *is_set* bits, between bitoff and bitmax.
- // Returns the start of the run in *out*, or bitmax if it is
- // not found in the provided range.
- // If the run is not found, "ZX_ERR_NO_RESOURCES" is returned.
- zx_status_t Find(bool is_set, size_t bitoff, size_t bitmax, size_t run_len, size_t* out) const;
+ // Finds the first (or last, in the case of ReverseFind) run of *run_len*
+ // *is_set* bits, in [*bitoff*, *bitmax*). Returns the start of the run in
+ // *out* and returns ZX_OK if a run is found, otherwise returns
+ // ZX_ERR_NO_RESOURCES.
+ zx_status_t Find(bool is_set, size_t bitoff, size_t bitmax, size_t run_len,
+ size_t* out) const;
+ zx_status_t ReverseFind(bool is_set, size_t bitoff, size_t bitmax,
+ size_t run_len, size_t* out) const;
// Returns true if all the bits in [*bitoff*, *bitmax*) are set. Afterwards,
// *first_unset* will be set to the lesser of bitmax and the index of the
@@ -86,7 +95,8 @@
// - void* GetData()
// To access the underlying storage.
// - zx_status_t Grow(size_t size)
-// (optional) To expand the underlying storage to fit at least |size| bytes.
+// (optional) To expand the underlying storage to fit at least |size|
+// bytes.
template <typename Storage>
class RawBitmapGeneric final : public RawBitmapBase {
public:
@@ -116,8 +126,10 @@
}
// Clear all the "newly grown" bytes
- uintptr_t addr = reinterpret_cast<uintptr_t>(bits_.GetData()) + old_len * sizeof(size_t);
- memset(reinterpret_cast<void*>(addr), 0, (new_len - old_len) * sizeof(size_t));
+ uintptr_t addr = reinterpret_cast<uintptr_t>(bits_.GetData()) +
+ old_len * sizeof(size_t);
+ memset(reinterpret_cast<void*>(addr), 0,
+ (new_len - old_len) * sizeof(size_t));
size_t old_size = size_;
data_ = static_cast<size_t*>(bits_.GetData());
diff --git a/system/ulib/bitmap/raw-bitmap.cpp b/system/ulib/bitmap/raw-bitmap.cpp
index d66646d..6c7b724 100644
--- a/system/ulib/bitmap/raw-bitmap.cpp
+++ b/system/ulib/bitmap/raw-bitmap.cpp
@@ -8,18 +8,19 @@
#include <limits.h>
#include <stddef.h>
-#include <zircon/types.h>
#include <fbl/algorithm.h>
#include <fbl/macros.h>
+#include <zircon/types.h>
+namespace bitmap {
namespace {
// Translates a bit offset into a starting index in the bitmap array.
constexpr size_t FirstIdx(size_t bitoff) {
- return bitoff / bitmap::kBits;
+ return bitoff / kBits;
}
-// GetMask returns a 64-bit bitmask. If the block of the bitmap we're looking
+// GetMask returns a 64-bit bitmask. If the block of the bitmap we're looking
// at isn't the first or last, all bits are set. Otherwise, the bits outside of
// [off,max) are cleared. Bits are counted with the LSB as 0 and the MSB as 63.
//
@@ -29,38 +30,51 @@
// GetMask(false, true, 16, 48) => 0x0000ffffffffffff
// GetMask(true, true, 16, 48) => 0x0000ffffffff0000
size_t GetMask(bool first, bool last, size_t off, size_t max) {
- size_t ones = 0;
- ones = ~ones;
+ size_t ones = ~(size_t(0));
size_t mask = ones;
if (first) {
- mask &= ones << (off % bitmap::kBits);
+ mask &= ones << (off % kBits);
}
if (last) {
- mask &= ones >> ((bitmap::kBits - (max % bitmap::kBits)) % bitmap::kBits);
+ mask &= ones >> ((kBits - (max % kBits)) % kBits);
}
return mask;
}
+// Applies a bitmask to the given data value. The result value has bits set
+// which fall within the mask but do not match is_set.
+size_t MaskBits(size_t data, size_t idx, size_t bitoff, size_t bitmax,
+ bool is_set) {
+ size_t mask = GetMask(idx == FirstIdx(bitoff), idx == LastIdx(bitmax),
+ bitoff, bitmax);
+ if (is_set) {
+ // If is_set=true, invert the mask, OR it with the value, and invert
+ // it again to hopefully get all zeros.
+ return ~(~mask | data);
+ } else {
+ // If is_set=false, just AND the mask with the value to hopefully
+ // get all zeros.
+ return mask & data;
+ }
+}
+
// Counts the number of zeros. It assumes everything in the array up to
// bits_[idx] is zero.
#if (SIZE_MAX == UINT_MAX)
-#define CTZ(x) (x == 0 ? bitmap::kBits : __builtin_ctz(x))
+#define CLZ(x) (x == 0 ? kBits : __builtin_clz(x))
+#define CTZ(x) (x == 0 ? kBits : __builtin_ctz(x))
#elif (SIZE_MAX == ULONG_MAX)
-#define CTZ(x) (x == 0 ? bitmap::kBits : __builtin_ctzl(x))
+#define CLZ(x) (x == 0 ? kBits : __builtin_clzl(x))
+#define CTZ(x) (x == 0 ? kBits : __builtin_ctzl(x))
#elif (SIZE_MAX == ULLONG_MAX)
-#define CTZ(x) (x == 0 ? bitmap::kBits : __builtin_ctzll(x))
+#define CLZ(x) (x == 0 ? kBits : __builtin_clzll(x))
+#define CTZ(x) (x == 0 ? kBits : __builtin_ctzll(x))
#else
#error "Unsupported size_t length"
#endif
-size_t CountZeros(size_t idx, size_t value) {
- return idx * bitmap::kBits + CTZ(value);
-}
-#undef CTZ
} // namespace
-namespace bitmap {
-
zx_status_t RawBitmapBase::Shrink(size_t size) {
if (size > size_) {
return ZX_ERR_NO_MEMORY;
@@ -69,58 +83,96 @@
return ZX_OK;
}
-size_t RawBitmapBase::Scan(size_t bitoff, size_t bitmax, bool is_set) const {
+bool RawBitmapBase::Scan(size_t bitoff, size_t bitmax, bool is_set,
+ size_t* out) const {
bitmax = fbl::min(bitmax, size_);
if (bitoff >= bitmax) {
- return bitmax;
+ return true;
}
- size_t first_idx = FirstIdx(bitoff);
- size_t last_idx = LastIdx(bitmax);
- size_t i = first_idx;
- size_t value = 0;
- for (i = first_idx; i <= last_idx; ++i) {
- value = GetMask(i == first_idx, i == last_idx, bitoff, bitmax);
- if (is_set) {
- // If is_set=true, invert the mask, OR it with the value, and invert
- // it again to hopefully get all zeros.
- value = ~(~value | data_[i]);
- } else {
- // If is_set=false, just AND the mask with the value to hopefully
- // get all zeros.
- value &= data_[i];
+ size_t i = FirstIdx(bitoff);
+ while (true) {
+ size_t masked = MaskBits(data_[i], i, bitoff, bitmax, is_set);
+ if (masked != 0) {
+ if (out) {
+ *out = i * bitmap::kBits + CTZ(masked);
+ }
+ return false;
}
- if (value != 0) {
- break;
+ if (i == LastIdx(bitmax)) {
+ return true;
}
+ ++i;
}
- return fbl::min(bitmax, CountZeros(i, value));
+}
+
+bool RawBitmapBase::ReverseScan(size_t bitoff, size_t bitmax, bool is_set,
+ size_t* out) const {
+ bitmax = fbl::min(bitmax, size_);
+ if (bitoff >= bitmax) {
+ return true;
+ }
+ size_t i = LastIdx(bitmax);
+ while (true) {
+ size_t masked = MaskBits(data_[i], i, bitoff, bitmax, is_set);
+ if (masked != 0) {
+ if (out) {
+ *out = (i + 1) * bitmap::kBits - (CLZ(masked) + 1);
+ }
+ return false;
+ }
+ if (i == FirstIdx(bitoff)) {
+ return true;
+ }
+ --i;
+ }
}
zx_status_t RawBitmapBase::Find(bool is_set, size_t bitoff, size_t bitmax,
- size_t run_len, size_t* out) const {
+ size_t run_len, size_t* out) const {
if (!out || bitmax <= bitoff) {
return ZX_ERR_INVALID_ARGS;
}
size_t start = bitoff;
- while (bitoff - start < run_len && bitoff < bitmax) {
- start = Scan(bitoff, bitmax, !is_set);
- if (bitmax - start < run_len) {
- *out = bitmax;
+ while (true) {
+ if (Scan(bitoff, bitmax, !is_set, &start) ||
+ (bitmax - start < run_len)) {
return ZX_ERR_NO_RESOURCES;
}
- bitoff = Scan(start, start + run_len, is_set);
+ if (Scan(start, start + run_len, is_set, &bitoff)) {
+ *out = start;
+ return ZX_OK;
+ }
}
- *out = start;
- return ZX_OK;
+}
+
+zx_status_t RawBitmapBase::ReverseFind(bool is_set, size_t bitoff, size_t bitmax,
+ size_t run_len, size_t* out) const {
+ if (!out || bitmax <= bitoff) {
+ return ZX_ERR_INVALID_ARGS;
+ }
+ size_t start = bitmax;
+ while (true) {
+ if (ReverseScan(bitoff, bitmax, !is_set, &start)) {
+ return ZX_ERR_NO_RESOURCES;
+ }
+ // Increment start to be last bit that is !is_set
+ ++start;
+ if ((start - bitoff < run_len)) {
+ return ZX_ERR_NO_RESOURCES;
+ }
+ if (ReverseScan(start - run_len, start, is_set, &bitmax)) {
+ *out = start - run_len;
+ return ZX_OK;
+ }
+ }
}
bool RawBitmapBase::Get(size_t bitoff, size_t bitmax, size_t* first) const {
- bitmax = fbl::min(bitmax, size_);
- size_t result = Scan(bitoff, bitmax, true);
- if (first) {
- *first = result;
+ bool result;
+ if ((result = Scan(bitoff, bitmax, true, first)) && first) {
+ *first = bitmax;
}
- return result == bitmax;
+ return result;
}
zx_status_t RawBitmapBase::Set(size_t bitoff, size_t bitmax) {
@@ -133,8 +185,7 @@
size_t first_idx = FirstIdx(bitoff);
size_t last_idx = LastIdx(bitmax);
for (size_t i = first_idx; i <= last_idx; ++i) {
- data_[i] |=
- GetMask(i == first_idx, i == last_idx, bitoff, bitmax);
+ data_[i] |= GetMask(i == first_idx, i == last_idx, bitoff, bitmax);
}
return ZX_OK;
}
@@ -149,8 +200,7 @@
size_t first_idx = FirstIdx(bitoff);
size_t last_idx = LastIdx(bitmax);
for (size_t i = first_idx; i <= last_idx; ++i) {
- data_[i] &=
- ~(GetMask(i == first_idx, i == last_idx, bitoff, bitmax));
+ data_[i] &= ~(GetMask(i == first_idx, i == last_idx, bitoff, bitmax));
}
return ZX_OK;
}
diff --git a/system/utest/bitmap/raw-bitmap-tests.cpp b/system/utest/bitmap/raw-bitmap-tests.cpp
index bd5b01b..c540ae8 100644
--- a/system/utest/bitmap/raw-bitmap-tests.cpp
+++ b/system/utest/bitmap/raw-bitmap-tests.cpp
@@ -12,8 +12,7 @@
namespace bitmap {
namespace tests {
-template <typename RawBitmap>
-static bool InitializedEmpty(void) {
+template <typename RawBitmap> static bool InitializedEmpty(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -32,8 +31,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool SingleBit(void) {
+template <typename RawBitmap> static bool SingleBit(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -51,8 +49,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool SetTwice(void) {
+template <typename RawBitmap> static bool SetTwice(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -68,8 +65,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool ClearTwice(void) {
+template <typename RawBitmap> static bool ClearTwice(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -87,8 +83,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool GetReturnArg(void) {
+template <typename RawBitmap> static bool GetReturnArg(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -115,8 +110,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool SetRange(void) {
+template <typename RawBitmap> static bool SetRange(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -144,18 +138,36 @@
EXPECT_TRUE(bitmap.Get(50, 80, &first_unset), "get part of range");
EXPECT_EQ(first_unset, 80U, "check returned arg");
- EXPECT_EQ(bitmap.Scan(0, 100, true), 0U, "scan set bits out of range");
- EXPECT_EQ(bitmap.Scan(0, 100, false), 2U, "scan cleared bits to start");
- EXPECT_EQ(bitmap.Scan(2, 100, true), 100U, "scan set bits to end");
- EXPECT_EQ(bitmap.Scan(2, 100, false), 2U, "scan cleared bits in set range");
- EXPECT_EQ(bitmap.Scan(50, 80, true), 80U, "scan set bits in subrange");
- EXPECT_EQ(bitmap.Scan(100, 200, false), 128U, "scan past end of bitmap");
+ size_t result;
+ EXPECT_FALSE(bitmap.Scan(0, 100, true, &result), "scan set bits");
+ EXPECT_EQ(result, 0U, "scan set bits");
+ EXPECT_FALSE(bitmap.ReverseScan(0, 100, true, &result), "reverse scan set bits");
+ EXPECT_EQ(result, 1U, "reverse scan set bits");
+
+ EXPECT_FALSE(bitmap.Scan(0, 100, false, &result), "scan cleared bits");
+ EXPECT_EQ(result, 2U, "scan cleared bits to start");
+ EXPECT_FALSE(bitmap.ReverseScan(0, 100, false, &result), "reverse scan cleared bits");
+ EXPECT_EQ(result, 99U, "reverse scan cleared bits");
+
+ EXPECT_TRUE(bitmap.Scan(2, 100, true), "scan set bits in set range");
+ EXPECT_TRUE(bitmap.ReverseScan(2, 100, true), "reverse scan set bits in set range");
+
+ EXPECT_FALSE(bitmap.Scan(2, 100, false, &result), "scan cleared bits in set range");
+ EXPECT_EQ(result, 2U, "scan cleared bits in set range");
+ EXPECT_FALSE(bitmap.ReverseScan(2, 100, false, &result),
+ "reverse scan cleared bits in set range");
+ EXPECT_EQ(result, 99U, "reverse scan cleared bits in set range");
+
+ EXPECT_TRUE(bitmap.Scan(50, 80, true), "scan set bits in subrange");
+ EXPECT_TRUE(bitmap.ReverseScan(50, 80, true), "reverse scan set bits in subrange");
+
+ EXPECT_TRUE(bitmap.Scan(100, 200, false), "scan past end of bitmap");
+ EXPECT_TRUE(bitmap.ReverseScan(100, 200, false), "reverse scan past end of bitmap");
END_TEST;
}
-template <typename RawBitmap>
-static bool FindSimple(void) {
+template <typename RawBitmap> static bool FindSimple(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -166,87 +178,159 @@
// Invalid finds
EXPECT_EQ(bitmap.Find(false, 0, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
+ EXPECT_EQ(bitmap.ReverseFind(false, 0, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
EXPECT_EQ(bitmap.Find(false, 1, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
+ EXPECT_EQ(bitmap.ReverseFind(false, 1, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
EXPECT_EQ(bitmap.Find(false, 0, 1, 1, nullptr), ZX_ERR_INVALID_ARGS, "bad output");
+ EXPECT_EQ(bitmap.ReverseFind(false, 0, 1, 1, nullptr), ZX_ERR_INVALID_ARGS, "bad output");
// Finds from offset zero
EXPECT_EQ(bitmap.Find(false, 0, 100, 1, &bitoff_start), ZX_OK, "find unset");
EXPECT_EQ(bitoff_start, 0, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 1, &bitoff_start), ZX_OK, "reverse find unset");
+ EXPECT_EQ(bitoff_start, 99, "check returned arg");
+
EXPECT_EQ(bitmap.Find(true, 0, 100, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, "find set");
- EXPECT_EQ(bitoff_start, 100, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse find set");
+
EXPECT_EQ(bitmap.Find(false, 0, 100, 5, &bitoff_start), ZX_OK, "find more unset");
EXPECT_EQ(bitoff_start, 0, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 5, &bitoff_start), ZX_OK,
+ "reverse find more unset");
+ EXPECT_EQ(bitoff_start, 95, "check returned arg");
+
EXPECT_EQ(bitmap.Find(true, 0, 100, 5, &bitoff_start), ZX_ERR_NO_RESOURCES, "find more set");
- EXPECT_EQ(bitoff_start, 100, "check returned arg");
- EXPECT_EQ(bitmap.Find(false, 0, 100, 100, &bitoff_start), ZX_OK, "find all uset");
+ EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 5, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse find more set");
+
+ EXPECT_EQ(bitmap.Find(false, 0, 100, 100, &bitoff_start), ZX_OK, "find all unset");
EXPECT_EQ(bitoff_start, 0, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 100, &bitoff_start), ZX_OK,
+ "reverse find all unset");
+ EXPECT_EQ(bitoff_start, 0, "check returned arg");
+
EXPECT_EQ(bitmap.Find(true, 0, 100, 100, &bitoff_start), ZX_ERR_NO_RESOURCES, "find all set");
- EXPECT_EQ(bitoff_start, 100, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 100, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse find all set");
// Finds at an offset
EXPECT_EQ(bitmap.Find(false, 50, 100, 3, &bitoff_start), ZX_OK, "find at offset");
EXPECT_EQ(bitoff_start, 50, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 3, &bitoff_start), ZX_OK,
+ "reverse find at offset");
+ EXPECT_EQ(bitoff_start, 97, "check returned arg");
+
EXPECT_EQ(bitmap.Find(true, 50, 100, 3, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail at offset");
- EXPECT_EQ(bitoff_start, 100, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(true, 50, 100, 3, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse fail at offset");
+
EXPECT_EQ(bitmap.Find(false, 90, 100, 10, &bitoff_start), ZX_OK, "find at offset end");
EXPECT_EQ(bitoff_start, 90, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 90, 100, 10, &bitoff_start), ZX_OK,
+ "reverse find at offset end");
+ EXPECT_EQ(bitoff_start, 90, "check returned arg");
// Invalid scans
EXPECT_EQ(bitmap.Find(false, 0, 100, 101, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
- EXPECT_EQ(bitoff_start, 100, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 101, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "no space");
EXPECT_EQ(bitmap.Find(false, 91, 100, 10, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
- EXPECT_EQ(bitoff_start, 100, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 91, 100, 10, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "no space");
EXPECT_EQ(bitmap.Find(false, 90, 100, 11, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
- EXPECT_EQ(bitoff_start, 100, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 90, 100, 11, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "no space");
EXPECT_EQ(bitmap.Find(false, 90, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
- EXPECT_EQ(bitoff_start, 95, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 90, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
// Fill the bitmap
EXPECT_EQ(bitmap.Set(5, 10), ZX_OK, "set range");
EXPECT_EQ(bitmap.Set(20, 30), ZX_OK, "set range");
EXPECT_EQ(bitmap.Set(32, 35), ZX_OK, "set range");
+ EXPECT_EQ(bitmap.Set(90, 95), ZX_OK, "set range");
+ EXPECT_EQ(bitmap.Set(70, 80), ZX_OK, "set range");
+ EXPECT_EQ(bitmap.Set(65, 68), ZX_OK, "set range");
EXPECT_EQ(bitmap.Find(false, 0, 50, 5, &bitoff_start), ZX_OK, "find in first group");
EXPECT_EQ(bitoff_start, 0, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 5, &bitoff_start), ZX_OK,
+ "reverse find in first group");
+ EXPECT_EQ(bitoff_start, 95, "check returned arg");
+
EXPECT_EQ(bitmap.Find(false, 0, 50, 10, &bitoff_start), ZX_OK, "find in second group");
EXPECT_EQ(bitoff_start, 10, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 10, &bitoff_start), ZX_OK,
+ "reverse find in second group");
+ EXPECT_EQ(bitoff_start, 80, "check returned arg");
+
EXPECT_EQ(bitmap.Find(false, 0, 50, 15, &bitoff_start), ZX_OK, "find in third group");
EXPECT_EQ(bitoff_start, 35, "check returned arg");
- EXPECT_EQ(bitmap.Find(false, 0, 50, 16, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
+ EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 15, &bitoff_start), ZX_OK,
+ "reverse find in third group");
EXPECT_EQ(bitoff_start, 50, "check returned arg");
+ EXPECT_EQ(bitmap.Find(false, 0, 50, 16, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
+ EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 16, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse fail to find");
+
EXPECT_EQ(bitmap.Find(false, 5, 20, 10, &bitoff_start), ZX_OK, "find space (offset)");
EXPECT_EQ(bitoff_start, 10, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 80, 95, 10, &bitoff_start), ZX_OK,
+ "reverse find space (offset)");
+ EXPECT_EQ(bitoff_start, 80, "check returned arg");
+
EXPECT_EQ(bitmap.Find(false, 5, 25, 10, &bitoff_start), ZX_OK, "find space (offset)");
EXPECT_EQ(bitoff_start, 10, "check returned arg");
- EXPECT_EQ(bitmap.Find(false, 5, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find (offset)");
- EXPECT_EQ(bitoff_start, 15, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 75, 95, 10, &bitoff_start), ZX_OK,
+ "reverse find space (offset)");
+ EXPECT_EQ(bitoff_start, 80, "check returned arg");
+
+ EXPECT_EQ(bitmap.Find(false, 5, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "fail to find (offset)");
+ EXPECT_EQ(bitmap.ReverseFind(false, 85, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse fail to find (offset)");
EXPECT_EQ(bitmap.Find(true, 0, 15, 2, &bitoff_start), ZX_OK, "find set bits");
EXPECT_EQ(bitoff_start, 5, "check returned arg");
- EXPECT_EQ(bitmap.Find(true, 0, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, "find set bits (fail)");
- EXPECT_EQ(bitoff_start, 15, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(true, 85, 100, 2, &bitoff_start), ZX_OK, "reverse find set bits");
+ EXPECT_EQ(bitoff_start, 93, "check returned arg");
+
+ EXPECT_EQ(bitmap.Find(true, 0, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "find set bits (fail)");
+ EXPECT_EQ(bitmap.ReverseFind(true, 85, 100, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse find set bits (fail)");
EXPECT_EQ(bitmap.Find(false, 32, 35, 3, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
- EXPECT_EQ(bitoff_start, 35, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 65, 68, 3, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse fail to find");
+
EXPECT_EQ(bitmap.Find(false, 32, 35, 4, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
- EXPECT_EQ(bitoff_start, 35, "check returned arg");
- EXPECT_EQ(bitmap.Find(true, 32, 35, 4, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find (set)");
- EXPECT_EQ(bitoff_start, 35, "check returned arg");
+ EXPECT_EQ(bitmap.ReverseFind(false, 65, 68, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse fail to find");
+
+ EXPECT_EQ(bitmap.Find(true, 32, 35, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "fail to find (set)");
+ EXPECT_EQ(bitmap.ReverseFind(true, 65, 68, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse fail to find (set)");
// Fill the whole bitmap
EXPECT_EQ(bitmap.Set(0, 128), ZX_OK, "set range");
- EXPECT_EQ(bitmap.Find(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find (small)");
- EXPECT_EQ(bitoff_start, 1, "check returned arg");
- EXPECT_EQ(bitmap.Find(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find (large)");
- EXPECT_EQ(bitoff_start, 128, "check returned arg");
+ EXPECT_EQ(bitmap.Find(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "fail to find (small)");
+ EXPECT_EQ(bitmap.ReverseFind(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse fail to find (small)");
+
+ EXPECT_EQ(bitmap.Find(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "fail to find (large)");
+ EXPECT_EQ(bitmap.ReverseFind(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "reverse fail to find (large)");
END_TEST;
}
-template <typename RawBitmap>
-static bool ClearAll(void) {
+template <typename RawBitmap> static bool ClearAll(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -268,8 +352,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool ClearSubrange(void) {
+template <typename RawBitmap> static bool ClearSubrange(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -296,8 +379,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool BoundaryArguments(void) {
+template <typename RawBitmap> static bool BoundaryArguments(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -319,8 +401,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool SetOutOfOrder(void) {
+template <typename RawBitmap> static bool SetOutOfOrder(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -335,8 +416,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool GrowAcrossPage(void) {
+template <typename RawBitmap> static bool GrowAcrossPage(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -355,8 +435,8 @@
EXPECT_NE(bitmap.SetOne(16 * PAGE_SIZE - 1), ZX_OK);
EXPECT_EQ(bitmap.Grow(16 * PAGE_SIZE), ZX_OK);
- EXPECT_EQ(bitmap.Find(true, 101, 16 * PAGE_SIZE, 1, &bitoff_start),
- ZX_ERR_NO_RESOURCES, "Expected tail end of bitmap to be unset");
+ EXPECT_EQ(bitmap.Find(true, 101, 16 * PAGE_SIZE, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
+ "Expected tail end of bitmap to be unset");
// Now we can set the previously inaccessible bits
EXPECT_FALSE(bitmap.GetOne(16 * PAGE_SIZE - 1));
@@ -376,8 +456,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool GrowShrink(void) {
+template <typename RawBitmap> static bool GrowShrink(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -415,10 +494,9 @@
"Expected bit outside shrink range to be set");
size_t bitoff_start;
- EXPECT_EQ(bitmap.Find(true, bitmap_size - shrink_len,
- bitmap_size, 1, &bitoff_start),
- ZX_ERR_NO_RESOURCES,
- "Expected tail end of bitmap to be unset");
+ EXPECT_EQ(
+ bitmap.Find(true, bitmap_size - shrink_len, bitmap_size, 1, &bitoff_start),
+ ZX_ERR_NO_RESOURCES, "Expected tail end of bitmap to be unset");
}
}
}
@@ -426,8 +504,7 @@
END_TEST;
}
-template <typename RawBitmap>
-static bool GrowFailure(void) {
+template <typename RawBitmap> static bool GrowFailure(void) {
BEGIN_TEST;
RawBitmap bitmap;
@@ -442,17 +519,17 @@
}
#define RUN_TEMPLATIZED_TEST(test, specialization) RUN_TEST(test<specialization>)
-#define ALL_TESTS(specialization) \
- RUN_TEMPLATIZED_TEST(InitializedEmpty, specialization) \
- RUN_TEMPLATIZED_TEST(SingleBit, specialization) \
- RUN_TEMPLATIZED_TEST(SetTwice, specialization) \
- RUN_TEMPLATIZED_TEST(ClearTwice, specialization) \
- RUN_TEMPLATIZED_TEST(GetReturnArg, specialization) \
- RUN_TEMPLATIZED_TEST(SetRange, specialization) \
- RUN_TEMPLATIZED_TEST(FindSimple, specialization) \
- RUN_TEMPLATIZED_TEST(ClearSubrange, specialization) \
- RUN_TEMPLATIZED_TEST(BoundaryArguments, specialization) \
- RUN_TEMPLATIZED_TEST(ClearAll, specialization) \
+#define ALL_TESTS(specialization) \
+ RUN_TEMPLATIZED_TEST(InitializedEmpty, specialization) \
+ RUN_TEMPLATIZED_TEST(SingleBit, specialization) \
+ RUN_TEMPLATIZED_TEST(SetTwice, specialization) \
+ RUN_TEMPLATIZED_TEST(ClearTwice, specialization) \
+ RUN_TEMPLATIZED_TEST(GetReturnArg, specialization) \
+ RUN_TEMPLATIZED_TEST(SetRange, specialization) \
+ RUN_TEMPLATIZED_TEST(FindSimple, specialization) \
+ RUN_TEMPLATIZED_TEST(ClearSubrange, specialization) \
+ RUN_TEMPLATIZED_TEST(BoundaryArguments, specialization) \
+ RUN_TEMPLATIZED_TEST(ClearAll, specialization) \
RUN_TEMPLATIZED_TEST(SetOutOfOrder, specialization)
BEGIN_TEST_CASE(raw_bitmap_tests)
