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 <limits.h>
10#include <stddef.h>
11#include <stdint.h>
12#include <string.h>
13
14#include <fbl/algorithm.h>
15#include <fbl/macros.h>
16#include <fbl/type_support.h>
17#include <zircon/assert.h>
18#include <zircon/types.h>
19
20namespace bitmap {
21namespace internal {
22
23DECLARE_HAS_MEMBER_FN(has_grow, Grow);
24
25} // namespace internal
26
27const size_t kBits = sizeof(size_t) * CHAR_BIT;
28
29// Translates a max bit into a final index in the bitmap array.
30constexpr size_t LastIdx(size_t bitmax) {
31    return (bitmax - 1) / kBits;
32}
33
34// Base class for RawGenericBitmap, to reduce what needs to be templated.
35class RawBitmapBase : public Bitmap {
36public:
37    // Returns the size of this bitmap.
38    size_t size() const { return size_; }
39
40    // Shrinks the accessible portion of the bitmap, without re-allocating
41    // the underlying storage.
42    //
43    // This is useful for programs which require underlying bitmap storage
44    // to be aligned to a certain size (initialized via Reset), but want to
45    // restrict access to a smaller portion of the bitmap (via Shrink).
46    zx_status_t Shrink(size_t size);
47
48    // Returns true if all bits in the range [*bitoff*, *bitmax*) match
49    // *is_set*, otherwise returns false and sets *out* (if provided) to the
50    // first (or last, in the case of ReverseScan) bit that doesn't match. An
51    // empty region (i.e. *bitoff* is greater than *bitmax*, or *bitoff* is
52    // outside the range of the bitmap) will return true.
53    bool Scan(size_t bitoff, size_t bitmax, bool is_set,
54              size_t* out = nullptr) const;
55    bool ReverseScan(size_t bitoff, size_t bitmax, bool is_set,
56                     size_t* out = nullptr) const;
57
58    // Finds the first (or last, in the case of ReverseFind) run of *run_len*
59    // *is_set* bits, in [*bitoff*, *bitmax*). Returns the start of the run in
60    // *out* and returns ZX_OK if a run is found, otherwise returns
61    // ZX_ERR_NO_RESOURCES.
62    zx_status_t Find(bool is_set, size_t bitoff, size_t bitmax, size_t run_len,
63                     size_t* out) const override;
64    zx_status_t ReverseFind(bool is_set, size_t bitoff, size_t bitmax,
65                            size_t run_len, size_t* out) const;
66
67    // Returns true if all the bits in [*bitoff*, *bitmax*) are set. Afterwards,
68    // *first_unset* will be set to the lesser of bitmax and the index of the
69    // first unset bit after *bitoff*.
70    bool Get(size_t bitoff, size_t bitmax,
71             size_t* first_unset = nullptr) const override;
72
73    // Sets all bits in the range [*bitoff*, *bitmax*).  Returns an error if
74    // bitmax < bitoff or size_ < bitmax, and ZX_OK otherwise.
75    zx_status_t Set(size_t bitoff, size_t bitmax) override;
76
77    // Clears all bits in the range [*bitoff*, *bitmax*).  Returns an error if
78    // bitmax < bitoff or size_ < bitmax, and ZX_OK otherwise.
79    zx_status_t Clear(size_t bitoff, size_t bitmax) override;
80
81    // Clear all bits in the bitmap.
82    void ClearAll() override;
83
84protected:
85    // The size of this bitmap, in bits.
86    size_t size_ = 0;
87    // Owned by bits_, cached
88    size_t* data_ = nullptr;
89};
90
91// A simple bitmap backed by generic storage.
92// Storage must implement:
93//   - zx_status_t Allocate(size_t size)
94//      To allocate |size| bytes of storage.
95//   - void* GetData()
96//      To access the underlying storage.
97//   - zx_status_t Grow(size_t size)
98//      (optional) To expand the underlying storage to fit at least |size|
99//      bytes.
100template <typename Storage>
101class RawBitmapGeneric final : public RawBitmapBase {
102public:
103    RawBitmapGeneric() = default;
104    virtual ~RawBitmapGeneric() = default;
105    RawBitmapGeneric(RawBitmapGeneric&& rhs) = default;
106    RawBitmapGeneric& operator=(RawBitmapGeneric&& rhs) = default;
107    DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(RawBitmapGeneric);
108
109    // Increases the bitmap size
110    template <typename U = Storage>
111    typename fbl::enable_if<internal::has_grow<U>::value, zx_status_t>::type
112    Grow(size_t size) {
113        if (size < size_) {
114            return ZX_ERR_INVALID_ARGS;
115        } else if (size == size_) {
116            return ZX_OK;
117        }
118
119        size_t old_len = LastIdx(size_) + 1;
120        size_t new_len = LastIdx(size) + 1;
121        size_t new_bitsize = sizeof(size_t) * new_len;
122        ZX_ASSERT(new_bitsize >= new_len); // Overflow
123        zx_status_t status = bits_.Grow(new_bitsize);
124        if (status != ZX_OK) {
125            return status;
126        }
127
128        // Clear all the "newly grown" bytes
129        uintptr_t addr = reinterpret_cast<uintptr_t>(bits_.GetData()) +
130                         old_len * sizeof(size_t);
131        memset(reinterpret_cast<void*>(addr), 0,
132               (new_len - old_len) * sizeof(size_t));
133
134        size_t old_size = size_;
135        data_ = static_cast<size_t*>(bits_.GetData());
136        size_ = size;
137
138        // Clear the partial bits not included in the new "size_t"s.
139        Clear(old_size, fbl::min(old_len * kBits, size_));
140        return ZX_OK;
141    }
142
143    template <typename U = Storage>
144    typename fbl::enable_if<!internal::has_grow<U>::value, zx_status_t>::type
145    Grow(size_t size) {
146        return ZX_ERR_NO_RESOURCES;
147    }
148
149    // Resets the bitmap; clearing and resizing it.
150    // Allocates memory, and can fail.
151    zx_status_t Reset(size_t size) {
152        size_ = size;
153        if (size_ == 0) {
154            data_ = nullptr;
155            return ZX_OK;
156        }
157        size_t last_idx = LastIdx(size);
158        zx_status_t status = bits_.Allocate(sizeof(size_t) * (last_idx + 1));
159        if (status != ZX_OK) {
160            return status;
161        }
162        data_ = static_cast<size_t*>(bits_.GetData());
163        ClearAll();
164        return ZX_OK;
165    }
166
167    // This function allows access to underlying data, but is dangerous: It
168    // leaks the pointer to bits_. Reset and the bitmap destructor should not
169    // be called on the bitmap while the pointer returned from data() is alive.
170    const Storage* StorageUnsafe() const { return &bits_; }
171
172private:
173    // The storage backing this bitmap.
174    Storage bits_;
175};
176
177} // namespace bitmap
178