zircon/system/ulib/bitmap/include/bitmap/rle-bitmap.h

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

#pragma once

#include <bitmap/bitmap.h>

#include <stddef.h>

#include <zircon/types.h>
#include <fbl/intrusive_double_list.h>
#include <fbl/macros.h>

#ifdef _KERNEL
#include <ktl/unique_ptr.h>
#else
#include <fbl/unique_ptr.h>
#endif

namespace bitmap {

struct RleBitmapElement;

#ifdef _KERNEL
using RleBitmapElementPtr = ktl::unique_ptr<RleBitmapElement>;
#else
using RleBitmapElementPtr = fbl::unique_ptr<RleBitmapElement>;
#endif

// A run-length encoded bitmap.
class RleBitmap final : public Bitmap {
private:
    // Private forward-declaration to share the type between the iterator type
    // and the internal list.
    using ListType = fbl::DoublyLinkedList<RleBitmapElementPtr>;

public:
    using const_iterator = ListType::const_iterator;
    using FreeList = ListType;

    constexpr RleBitmap()
        : num_elems_(0), num_bits_(0) {}
    virtual ~RleBitmap() = default;

    RleBitmap(RleBitmap&& rhs) = default;
    RleBitmap& operator=(RleBitmap&& rhs) = default;

    DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(RleBitmap);

    // Returns the current number of ranges.
    size_t num_ranges() const { return num_elems_; }

    // Returns the current number of bits.
    size_t num_bits() const { return num_bits_; }

    zx_status_t Find(bool is_set, size_t bitoff, size_t bitmax,
                     size_t run_len, size_t* out) const override;

    // 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
    // first unset bit after *bitoff*.
    bool Get(size_t bitoff, size_t bitmax, size_t* first_unset = nullptr) const override;

    // Sets all bits in the range [*bitoff*, *bitmax*).  Only fails on allocation
    // error or if bitmax < bitoff.
    zx_status_t Set(size_t bitoff, size_t bitmax) override;

    // Sets all bits in the range [*bitoff*, *bitmax*).  Only fails if
    // *bitmax* < *bitoff* or if an allocation is needed and *free_list*
    // does not contain one.
    //
    // *free_list* is a list of usable allocations.  If an allocation is needed,
    // it will be drawn from it.  This function is guaranteed to need at most
    // one allocation.  If any nodes need to be deleted, they will be appended
    // to *free_list*.
    zx_status_t SetNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list);

    // Clears all bits in the range [*bitoff*, *bitmax*).  Only fails on allocation
    // error or if bitmax < bitoff.
    zx_status_t Clear(size_t bitoff, size_t bitmax) override;

    // Clear all bits in the range [*bitoff*, *bitmax*).  Only fails if
    // *bitmax* < *bitoff* or if an allocation is needed and *free_list*
    // does not contain one.
    //
    // *free_list* is a list of usable allocations.  If an allocation is needed,
    // it will be drawn from it.  This function is guaranteed to need at most
    // one allocation.  If any nodes need to be deleted, they will be appended
    // to *free_list*.
    zx_status_t ClearNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list);

    // Clear all bits in the bitmap.
    void ClearAll() override;

    // Iterate over the ranges in the bitmap.  Modifying the list while
    // iterating over it may yield undefined results.
    const_iterator cbegin() const { return elems_.cbegin(); }
    const_iterator begin() const { return elems_.cbegin(); }
    const_iterator end() const { return elems_.cend(); }
    const_iterator cend() const { return elems_.cend(); }

private:
    zx_status_t SetInternal(size_t bitoff, size_t bitmax, FreeList* free_list);
    zx_status_t ClearInternal(size_t bitoff, size_t bitmax, FreeList* free_list);

    // The ranges of the bitmap. Ranges are ordered by ascending |bitoff| value.
    // When no "Set" operation is in progress, there should not be any overlapping ranges.
    ListType elems_;

    // The number of ranges in elems_.
    size_t num_elems_;

    // The number of total bits in elems_; i.e. the sum of the bitlen field of all stored
    // RleBitmapElements.
    size_t num_bits_;
};

// Elements of the bitmap list
struct RleBitmapElement : public fbl::DoublyLinkedListable<RleBitmapElementPtr> {
    // The start of this run of 1-bits.
    size_t bitoff;
    // The number of 1-bits in this run.
    size_t bitlen;

    // The (inclusive) start of this run of 1-bits.
    size_t start() const { return bitoff; }

    // The (exclusive) end of this run of 1-bits.
    size_t end() const { return bitoff + bitlen; }
};

} // namespace bitmap