blob: 33fdf47fc378c3fe9f7aa5c97d23fcb683548fbd [file] [log] [blame]
// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <bitmap/rle-bitmap.h>
#include <stddef.h>
#include <zircon/errors.h>
#include <zircon/types.h>
#include <fbl/algorithm.h>
#include <fbl/alloc_checker.h>
#include <utility>
namespace bitmap {
namespace {
// Allocate a new bitmap element. If *free_list* is null, allocate one using
// new. If *free_list* is not null, take one from *free_list*.
RleBitmapElementPtr AllocateElement(RleBitmap::FreeList* free_list) {
if (!free_list) {
fbl::AllocChecker ac;
RleBitmapElementPtr new_elem(new (&ac) RleBitmapElement());
if (!ac.check()) {
return RleBitmapElementPtr();
}
return new_elem;
} else {
return free_list->pop_front();
}
}
// Release the element *elem*. If *free_list* is null, release the element
// with delete. If *free_list* is not null, append it to *free_list*.
void ReleaseElement(RleBitmap::FreeList* free_list, RleBitmapElementPtr&& elem) {
if (free_list) {
free_list->push_back(std::move(elem));
}
}
} // namespace
zx_status_t RleBitmap::Find(bool is_set, size_t bitoff, size_t bitmax, size_t run_len,
size_t* out) const {
*out = bitmax;
// Loop through all existing elems to try to find a |run_len| length range of |is_set| bits.
// On each loop, |bitoff| is guaranteed to be either within the current elem, or in the range
// of unset bits leading up to it.
// Therefore, we can check whether |run_len| bits between |bitmax| and |bitoff| exist before
// the start of the elem (for unset runs), or within the current elem (for set runs).
for (const auto& elem : elems_) {
if (bitoff >= elem.end()) {
continue;
} else if (bitmax - bitoff < run_len) {
return ZX_ERR_NO_RESOURCES;
}
size_t elem_min = fbl::max(bitoff, elem.bitoff); // Minimum valid bit within elem.
size_t elem_max = fbl::min(bitmax, elem.end()); // Maximum valid bit within elem.
if (is_set && elem_max > elem_min && elem_max - elem_min >= run_len) {
// This element contains at least |run_len| bits
// which are between |bitoff| and |bitmax|.
*out = elem_min;
return ZX_OK;
}
if (!is_set && bitoff < elem.bitoff && elem.bitoff - bitoff >= run_len) {
// There are at least |run_len| bits between |bitoff| and the beginning of this element.
*out = bitoff;
return ZX_OK;
}
if (bitmax < elem.end()) {
// We have not found a valid run, and the specified range
// does not extend past this element.
return ZX_ERR_NO_RESOURCES;
}
// Update bitoff to the next value we want to check within the range.
bitoff = elem.end();
}
if (!is_set && bitmax - bitoff >= run_len) {
// We have not found an element with bits > bitoff, which means there is an infinite unset
// range starting at bitoff.
*out = bitoff;
return ZX_OK;
}
return ZX_ERR_NO_RESOURCES;
}
bool RleBitmap::Get(size_t bitoff, size_t bitmax, size_t* first_unset) const {
for (const auto& elem : elems_) {
if (bitoff < elem.bitoff) {
break;
}
if (bitoff < elem.bitoff + elem.bitlen) {
bitoff = elem.bitoff + elem.bitlen;
break;
}
}
if (bitoff > bitmax) {
bitoff = bitmax;
}
if (first_unset) {
*first_unset = bitoff;
}
return bitoff == bitmax;
}
void RleBitmap::ClearAll() {
elems_.clear();
num_elems_ = 0;
num_bits_ = 0;
}
zx_status_t RleBitmap::Set(size_t bitoff, size_t bitmax) {
return SetInternal(bitoff, bitmax, nullptr);
}
zx_status_t RleBitmap::SetNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list) {
if (free_list == nullptr) {
return ZX_ERR_INVALID_ARGS;
}
return SetInternal(bitoff, bitmax, free_list);
}
zx_status_t RleBitmap::Clear(size_t bitoff, size_t bitmax) {
return ClearInternal(bitoff, bitmax, nullptr);
}
zx_status_t RleBitmap::ClearNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list) {
if (free_list == nullptr) {
return ZX_ERR_INVALID_ARGS;
}
return ClearInternal(bitoff, bitmax, free_list);
}
zx_status_t RleBitmap::SetInternal(size_t bitoff, size_t bitmax, FreeList* free_list) {
if (bitmax < bitoff) {
return ZX_ERR_INVALID_ARGS;
}
const size_t bitlen = bitmax - bitoff;
if (bitlen == 0) {
return ZX_OK;
}
RleBitmapElementPtr new_elem = AllocateElement(free_list);
if (!new_elem) {
return ZX_ERR_NO_MEMORY;
}
++num_elems_;
new_elem->bitoff = bitoff;
new_elem->bitlen = bitlen;
auto ends_after = elems_.find_if([bitoff](const RleBitmapElement& elem) -> bool {
return elem.bitoff + elem.bitlen >= bitoff;
});
// Insert the new element before the first node that ends at a point >=
// when we begin.
elems_.insert(ends_after, std::move(new_elem));
num_bits_ += bitlen;
// If ends_after was the end of the list, there is no merging to do.
if (ends_after == elems_.end()) {
return ZX_OK;
}
auto itr = ends_after;
RleBitmapElement& elem = *--ends_after;
if (elem.bitoff >= itr->bitoff) {
// Our range either starts before or in the middle/end of *elem*.
// Adjust it so it starts at the same place as *elem*, to allow
// the merge logic to not consider this overlap case.
elem.bitlen += elem.bitoff - itr->bitoff;
num_bits_ += elem.bitoff - itr->bitoff;
elem.bitoff = itr->bitoff;
}
// Walk forwards and remove/merge any overlaps
size_t max = elem.bitoff + elem.bitlen;
while (itr != elems_.end()) {
if (itr->bitoff > max) {
break;
}
max = fbl::max(max, itr->bitoff + itr->bitlen);
num_bits_ += max - elem.bitoff - itr->bitlen - elem.bitlen;
elem.bitlen = max - elem.bitoff;
auto to_erase = itr;
++itr;
ReleaseElement(free_list, elems_.erase(to_erase));
--num_elems_;
}
return ZX_OK;
}
zx_status_t RleBitmap::ClearInternal(size_t bitoff, size_t bitmax, FreeList* free_list) {
if (bitmax < bitoff) {
return ZX_ERR_INVALID_ARGS;
}
if (bitmax - bitoff == 0) {
return ZX_OK;
}
auto itr = elems_.begin();
while (itr != elems_.end()) {
if (itr->bitoff + itr->bitlen < bitoff) {
++itr;
continue;
}
if (bitmax < itr->bitoff) {
break;
}
if (itr->bitoff < bitoff) {
if (itr->bitoff + itr->bitlen <= bitmax) {
// '*itr' contains 'bitoff'.
num_bits_ -= (itr->bitlen - (bitoff - itr->bitoff));
itr->bitlen = bitoff - itr->bitoff;
++itr;
continue;
} else {
// '*itr' contains [bitoff, bitmax), and we need to split it.
RleBitmapElementPtr new_elem = AllocateElement(free_list);
if (!new_elem) {
return ZX_ERR_NO_MEMORY;
}
++num_elems_;
new_elem->bitoff = bitmax;
new_elem->bitlen = itr->bitoff + itr->bitlen - bitmax;
elems_.insert_after(itr, std::move(new_elem));
itr->bitlen = bitoff - itr->bitoff;
num_bits_ -= (bitmax - bitoff);
break;
}
} else {
if (bitmax < itr->bitoff + itr->bitlen) {
// 'elem' contains 'bitmax'
num_bits_ -= (bitmax - itr->bitoff);
itr->bitlen = itr->bitoff + itr->bitlen - bitmax;
itr->bitoff = bitmax;
break;
} else {
// [bitoff, bitmax) fully contains '*itr'.
num_bits_ -= itr->bitlen;
auto to_erase = itr++;
ReleaseElement(free_list, elems_.erase(to_erase));
--num_elems_;
}
}
}
return ZX_OK;
}
} // namespace bitmap