zircon/system/ulib/bitmap/rle-bitmap.cc

// 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