ulib/bitmap/rle-bitmap.cpp

43 zx_status_t RleBitmap::Find(bool is_set, size_t bitoff, size_t bitmax, size_t run_len, size_t* out)
48     // On each loop, |bitoff| is guaranteed to be either within the current elem, or in the range
50     // Therefore, we can check whether |run_len| bits between |bitmax| and |bitoff| exist before
53         if (bitoff >= elem.end()) {
55         } else if (bitmax - bitoff < run_len) {
59         size_t elem_min = fbl::max(bitoff, elem.bitoff); // Minimum valid bit within elem.
64             // which are between |bitoff| and |bitmax|.
69         if (!is_set && bitoff < elem.bitoff && elem.bitoff - bitoff >= run_len) {
70             // There are at least |run_len| bits between |bitoff| and the beginning of this element.
71             *out = bitoff;
81         // Update bitoff to the next value we want to check within the range.
82         bitoff = elem.end();
86     if (!is_set && bitmax - bitoff >= run_len) {
87         // We have not found an element with bits > bitoff, which means there is an infinite unset
88         // range starting at bitoff.
89         *out = bitoff;
97 bool RleBitmap::Get(size_t bitoff, size_t bitmax, size_t* first_unset) const {
99         if (bitoff < elem.bitoff) {
102         if (bitoff < elem.bitoff + elem.bitlen) {
103             bitoff = elem.bitoff + elem.bitlen;
107     if (bitoff > bitmax) {
108         bitoff = bitmax;
111         *first_unset = bitoff;
114     return bitoff == bitmax;
123 zx_status_t RleBitmap::Set(size_t bitoff, size_t bitmax) {
124     return SetInternal(bitoff, bitmax, nullptr);
127 zx_status_t RleBitmap::SetNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list) {
132     return SetInternal(bitoff, bitmax, free_list);
135 zx_status_t RleBitmap::Clear(size_t bitoff, size_t bitmax) {
136     return ClearInternal(bitoff, bitmax, nullptr);
139 zx_status_t RleBitmap::ClearNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list) {
144     return ClearInternal(bitoff, bitmax, free_list);
147 zx_status_t RleBitmap::SetInternal(size_t bitoff, size_t bitmax, FreeList* free_list) {
148     if (bitmax < bitoff) {
152     const size_t bitlen = bitmax - bitoff;
162     new_elem->bitoff = bitoff;
165     auto ends_after = elems_.find_if([bitoff](const RleBitmapElement& elem) -> bool {
166         return elem.bitoff + elem.bitlen >= bitoff;
182     if (elem.bitoff >= itr->bitoff) {
186         elem.bitlen += elem.bitoff - itr->bitoff;
187         num_bits_ += elem.bitoff - itr->bitoff;
188         elem.bitoff = itr->bitoff;
192     size_t max = elem.bitoff + elem.bitlen;
194         if (itr->bitoff > max) {
198         max = fbl::max(max, itr->bitoff + itr->bitlen);
199         num_bits_ += max - elem.bitoff - itr->bitlen - elem.bitlen;
200         elem.bitlen = max - elem.bitoff;
210 zx_status_t RleBitmap::ClearInternal(size_t bitoff, size_t bitmax, FreeList* free_list) {
211     if (bitmax < bitoff) {
215     if (bitmax - bitoff == 0) {
221         if (itr->bitoff + itr->bitlen < bitoff) {
225         if (bitmax < itr->bitoff) {
228         if (itr->bitoff < bitoff) {
229             if (itr->bitoff + itr->bitlen <= bitmax) {
230                 // '*itr' contains 'bitoff'.
231                 num_bits_ -= (itr->bitlen - (bitoff - itr->bitoff));
232                 itr->bitlen = bitoff - itr->bitoff;
236                 // '*itr' contains [bitoff, bitmax), and we need to split it.
242                 new_elem->bitoff = bitmax;
243                 new_elem->bitlen = itr->bitoff + itr->bitlen - bitmax;
246                 itr->bitlen = bitoff - itr->bitoff;
247                 num_bits_ -= (bitmax - bitoff);
251             if (bitmax < itr->bitoff + itr->bitlen) {
253                 num_bits_ -= (bitmax - itr->bitoff);
254                 itr->bitlen = itr->bitoff + itr->bitlen - bitmax;
255                 itr->bitoff = bitmax;
258                 // [bitoff, bitmax) fully contains '*itr'.