1 // Copyright 2016 The Fuchsia Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #pragma once 6 7 #include <bitmap/bitmap.h> 8 9 #include <stddef.h> 10 11 #include <zircon/types.h> 12 #include <fbl/intrusive_double_list.h> 13 #include <fbl/macros.h> 14 15 #ifdef _KERNEL 16 #include <ktl/unique_ptr.h> 17 #else 18 #include <fbl/unique_ptr.h> 19 #endif 20 21 namespace bitmap { 22 23 struct RleBitmapElement; 24 25 #ifdef _KERNEL 26 using RleBitmapElementPtr = ktl::unique_ptr<RleBitmapElement>; 27 #else 28 using RleBitmapElementPtr = fbl::unique_ptr<RleBitmapElement>; 29 #endif 30 31 // A run-length encoded bitmap. 32 class RleBitmap final : public Bitmap { 33 private: 34 // Private forward-declaration to share the type between the iterator type 35 // and the internal list. 36 using ListType = fbl::DoublyLinkedList<RleBitmapElementPtr>; 37 38 public: 39 using const_iterator = ListType::const_iterator; 40 using FreeList = ListType; 41 RleBitmap()42 constexpr RleBitmap() 43 : num_elems_(0), num_bits_(0) {} 44 virtual ~RleBitmap() = default; 45 46 RleBitmap(RleBitmap&& rhs) = default; 47 RleBitmap& operator=(RleBitmap&& rhs) = default; 48 49 DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(RleBitmap); 50 51 // Returns the current number of ranges. num_ranges()52 size_t num_ranges() const { return num_elems_; } 53 54 // Returns the current number of bits. num_bits()55 size_t num_bits() const { return num_bits_; } 56 57 zx_status_t Find(bool is_set, size_t bitoff, size_t bitmax, 58 size_t run_len, size_t* out) const override; 59 60 // Returns true if all the bits in [*bitoff*, *bitmax*) are set. Afterwards, 61 // *first_unset* will be set to the lesser of bitmax and the index of the 62 // first unset bit after *bitoff*. 63 bool Get(size_t bitoff, size_t bitmax, size_t* first_unset = nullptr) const override; 64 65 // Sets all bits in the range [*bitoff*, *bitmax*). Only fails on allocation 66 // error or if bitmax < bitoff. 67 zx_status_t Set(size_t bitoff, size_t bitmax) override; 68 69 // Sets all bits in the range [*bitoff*, *bitmax*). Only fails if 70 // *bitmax* < *bitoff* or if an allocation is needed and *free_list* 71 // does not contain one. 72 // 73 // *free_list* is a list of usable allocations. If an allocation is needed, 74 // it will be drawn from it. This function is guaranteed to need at most 75 // one allocation. If any nodes need to be deleted, they will be appended 76 // to *free_list*. 77 zx_status_t SetNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list); 78 79 // Clears all bits in the range [*bitoff*, *bitmax*). Only fails on allocation 80 // error or if bitmax < bitoff. 81 zx_status_t Clear(size_t bitoff, size_t bitmax) override; 82 83 // Clear all bits in the range [*bitoff*, *bitmax*). Only fails if 84 // *bitmax* < *bitoff* or if an allocation is needed and *free_list* 85 // does not contain one. 86 // 87 // *free_list* is a list of usable allocations. If an allocation is needed, 88 // it will be drawn from it. This function is guaranteed to need at most 89 // one allocation. If any nodes need to be deleted, they will be appended 90 // to *free_list*. 91 zx_status_t ClearNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list); 92 93 // Clear all bits in the bitmap. 94 void ClearAll() override; 95 96 // Iterate over the ranges in the bitmap. Modifying the list while 97 // iterating over it may yield undefined results. cbegin()98 const_iterator cbegin() const { return elems_.cbegin(); } begin()99 const_iterator begin() const { return elems_.cbegin(); } end()100 const_iterator end() const { return elems_.cend(); } cend()101 const_iterator cend() const { return elems_.cend(); } 102 103 private: 104 zx_status_t SetInternal(size_t bitoff, size_t bitmax, FreeList* free_list); 105 zx_status_t ClearInternal(size_t bitoff, size_t bitmax, FreeList* free_list); 106 107 // The ranges of the bitmap. Ranges are ordered by ascending |bitoff| value. 108 // When no "Set" operation is in progress, there should not be any overlapping ranges. 109 ListType elems_; 110 111 // The number of ranges in elems_. 112 size_t num_elems_; 113 114 // The number of total bits in elems_; i.e. the sum of the bitlen field of all stored 115 // RleBitmapElements. 116 size_t num_bits_; 117 }; 118 119 // Elements of the bitmap list 120 struct RleBitmapElement : public fbl::DoublyLinkedListable<RleBitmapElementPtr> { 121 // The start of this run of 1-bits. 122 size_t bitoff; 123 // The number of 1-bits in this run. 124 size_t bitlen; 125 126 // The (inclusive) start of this run of 1-bits. startRleBitmapElement127 size_t start() const { return bitoff; } 128 129 // The (exclusive) end of this run of 1-bits. endRleBitmapElement130 size_t end() const { return bitoff + bitlen; } 131 }; 132 133 } // namespace bitmap 134