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