bitmap/
rle_bitmap.rs

1// Copyright 2026 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
5use crate::bitmap::{Bitmap, GetResult};
6
7use core::pin::Pin;
8use pin_init::{PinInit, pin_data, pin_init};
9use zx_status::Status;
10
11/// An element representing a run of set bits in an `RleBitmapBase`.
12#[derive(Default, Debug, fbl::DoublyLinkedListContainable, fbl::Recyclable)]
13#[pin_data]
14#[repr(C)]
15pub struct Element<T> {
16    /// The start offset of this run of 1-bits.
17    pub bitoff: T,
18    /// The number of 1-bits in this run.
19    pub bitlen: T,
20    #[pin]
21    #[dll_node]
22    node: fbl::DoublyLinkedListNode<Self>,
23}
24
25impl<T> Element<T> {
26    /// Create a new Element with the given range.
27    pub fn new(bitoff: T, bitlen: T) -> Self {
28        Self { bitoff, bitlen, node: fbl::DoublyLinkedListNode::new() }
29    }
30}
31
32impl<T: Copy + core::ops::Add<Output = T>> Element<T> {
33    /// Returns the (inclusive) start of this run of 1-bits.
34    pub fn start(&self) -> T {
35        self.bitoff
36    }
37
38    /// Returns the (exclusive) end of this run of 1-bits.
39    pub fn end(&self) -> T {
40        self.bitoff + self.bitlen
41    }
42}
43
44pub type ElementPtr<T> = fbl::UniquePtr<Element<T>>;
45pub type FreeList<T> = fbl::DoublyLinkedList<ElementPtr<T>>;
46
47/// A run-length encoded bitmap.
48///
49/// # Invariants
50///
51/// `RleBitmapBase` contains a pinned intrusive `DoublyLinkedList` and can only be constructed in
52/// place via its `PinInit` initializer (`RleBitmapBase::new()`). It must never be constructed by
53/// value or moved after initialization.
54#[pin_data]
55#[derive(Debug)]
56pub struct RleBitmapBase<T> {
57    #[pin]
58    elems: fbl::DoublyLinkedList<ElementPtr<T>>,
59    num_elems: usize,
60    num_bits: T,
61}
62
63fn allocate_element<T: Default>(
64    free_list: Option<Pin<&mut FreeList<T>>>,
65) -> Result<ElementPtr<T>, Status> {
66    if let Some(fl) = free_list {
67        if let Some(elem) = fl.pop_front() {
68            return Ok(elem);
69        }
70        return Err(Status::NO_MEMORY);
71    }
72    let elem = Element::default();
73    fbl::UniquePtr::try_new(elem).map_err(|_| Status::NO_MEMORY)
74}
75
76fn release_element<T>(free_list: Option<Pin<&mut FreeList<T>>>, elem: ElementPtr<T>) {
77    if let Some(fl) = free_list {
78        fl.push_back(elem);
79    }
80}
81
82impl<T> RleBitmapBase<T> {
83    /// Returns an iterator over the elements of this bitmap.
84    pub fn iter(&self) -> fbl::Iterator<'_, ElementPtr<T>> {
85        self.elems.iter()
86    }
87}
88
89impl<T> RleBitmapBase<T>
90where
91    T: Copy
92        + Eq
93        + Ord
94        + Default
95        + core::ops::Add<Output = T>
96        + core::ops::Sub<Output = T>
97        + From<u8>,
98{
99    /// Create a new, empty run-length encoded bitmap.
100    ///
101    /// Since the underlying intrusive list must be pinned in memory, this returns
102    /// an initializer that must be pinned (e.g. using `pin_init::pin_init!`).
103    pub fn new() -> impl PinInit<Self, core::convert::Infallible> {
104        pin_init!(Self {
105            elems <- fbl::DoublyLinkedList::new(),
106            num_elems: 0,
107            num_bits: T::default(),
108        })
109    }
110
111    /// Returns the current number of ranges (runs of set bits) in the bitmap.
112    pub fn num_ranges(&self) -> usize {
113        self.num_elems
114    }
115
116    /// Returns the current total number of set bits in the bitmap.
117    pub fn num_bits(&self) -> T {
118        self.num_bits
119    }
120
121    /// Sets all bits in the range `[bitoff, bitmax)`.
122    ///
123    /// Only fails if `bitmax < bitoff` or if an allocation is needed and `free_list`
124    /// does not contain one.
125    ///
126    /// `free_list` is a list of usable allocations. If an allocation is needed,
127    /// it will be drawn from it. This function is guaranteed to need at most
128    /// one allocation. If any nodes need to be deleted, they will be appended
129    /// to `free_list`.
130    pub fn set_no_alloc(
131        self: Pin<&mut Self>,
132        bitoff: T,
133        bitmax: T,
134        free_list: Pin<&mut FreeList<T>>,
135    ) -> Result<(), Status> {
136        self.set_internal(bitoff, bitmax, Some(free_list))
137    }
138
139    /// Clears all bits in the range `[bitoff, bitmax)`.
140    ///
141    /// Only fails if `bitmax < bitoff` or if an allocation is needed and `free_list`
142    /// does not contain one.
143    ///
144    /// `free_list` is a list of usable allocations. If an allocation is needed,
145    /// it will be drawn from it. This function is guaranteed to need at most
146    /// one allocation. If any nodes need to be deleted, they will be appended
147    /// to `free_list`.
148    pub fn clear_no_alloc(
149        self: Pin<&mut Self>,
150        bitoff: T,
151        bitmax: T,
152        free_list: Pin<&mut FreeList<T>>,
153    ) -> Result<(), Status> {
154        self.clear_internal(bitoff, bitmax, Some(free_list))
155    }
156
157    fn set_internal(
158        self: Pin<&mut Self>,
159        bitoff: T,
160        bitmax: T,
161        mut free_list: Option<Pin<&mut FreeList<T>>>,
162    ) -> Result<(), Status> {
163        let this = self.project();
164        if bitmax < bitoff {
165            return Err(Status::INVALID_ARGS);
166        }
167        let bitlen = bitmax - bitoff;
168        if bitlen == T::default() {
169            return Ok(());
170        }
171
172        let mut new_elem = allocate_element(free_list.as_mut().map(Pin::as_mut))?;
173        *this.num_elems += 1;
174        new_elem.bitoff = bitoff;
175        new_elem.bitlen = bitlen;
176
177        let mut cursor = this.elems.cursor_front_mut();
178        while let Some(e) = cursor.get() {
179            if e.bitoff + e.bitlen >= bitoff {
180                break;
181            }
182            cursor.move_next();
183        }
184
185        cursor.insert_before(new_elem);
186        *this.num_bits = *this.num_bits + bitlen;
187
188        let mut has_successor = false;
189        let mut successor_bitoff = T::default();
190        if let Some(succ) = cursor.get() {
191            has_successor = true;
192            successor_bitoff = succ.bitoff;
193        }
194
195        cursor.move_prev();
196        let mut elem_bitoff = cursor.get().unwrap().bitoff;
197        let mut elem_bitlen = cursor.get().unwrap().bitlen;
198
199        if has_successor && elem_bitoff >= successor_bitoff {
200            let diff = elem_bitoff - successor_bitoff;
201            elem_bitlen = elem_bitlen + diff;
202            elem_bitoff = successor_bitoff;
203            let elem = cursor.get_mut().unwrap().project();
204            *elem.bitoff = elem_bitoff;
205            *elem.bitlen = elem_bitlen;
206            *this.num_bits = *this.num_bits + diff;
207        }
208
209        cursor.move_next();
210        let mut max = elem_bitoff + elem_bitlen;
211        while let Some(s) = cursor.get() {
212            let (succ_bitoff, succ_bitlen) = (s.bitoff, s.bitlen);
213            if succ_bitoff > max {
214                break;
215            }
216            let succ_max = succ_bitoff + succ_bitlen;
217            max = core::cmp::max(max, succ_max);
218            *this.num_bits = *this.num_bits - elem_bitlen - succ_bitlen + (max - elem_bitoff);
219            elem_bitlen = max - elem_bitoff;
220            let erased = cursor.erase().unwrap();
221            *this.num_elems -= 1;
222            release_element(free_list.as_mut().map(Pin::as_mut), erased);
223        }
224
225        cursor.move_prev();
226        *cursor.get_mut().unwrap().project().bitlen = elem_bitlen;
227        Ok(())
228    }
229
230    fn clear_internal(
231        self: Pin<&mut Self>,
232        bitoff: T,
233        bitmax: T,
234        mut free_list: Option<Pin<&mut FreeList<T>>>,
235    ) -> Result<(), Status> {
236        let this = self.project();
237        if bitmax < bitoff {
238            return Err(Status::INVALID_ARGS);
239        }
240        let bitlen = bitmax - bitoff;
241        if bitlen == T::default() {
242            return Ok(());
243        }
244
245        let mut cursor = this.elems.cursor_front_mut();
246        while let Some(e) = cursor.get() {
247            let (elem_bitoff, elem_bitlen) = (e.bitoff, e.bitlen);
248
249            if elem_bitoff + elem_bitlen < bitoff {
250                cursor.move_next();
251                continue;
252            }
253            if bitmax < elem_bitoff {
254                break;
255            }
256            if elem_bitoff < bitoff {
257                if elem_bitoff + elem_bitlen <= bitmax {
258                    let new_bitlen = bitoff - elem_bitoff;
259                    *this.num_bits = *this.num_bits - (elem_bitlen - new_bitlen);
260                    *cursor.get_mut().unwrap().project().bitlen = new_bitlen;
261                    cursor.move_next();
262                    continue;
263                }
264                let mut new_elem = allocate_element(free_list.as_mut().map(Pin::as_mut))?;
265                *this.num_elems += 1;
266                new_elem.bitoff = bitmax;
267                new_elem.bitlen = elem_bitoff + elem_bitlen - bitmax;
268                cursor.insert_after(new_elem);
269                let new_bitlen = bitoff - elem_bitoff;
270                *this.num_bits = *this.num_bits - (bitmax - bitoff);
271                *cursor.get_mut().unwrap().project().bitlen = new_bitlen;
272                break;
273            }
274            if bitmax < elem_bitoff + elem_bitlen {
275                *this.num_bits = *this.num_bits - (bitmax - elem_bitoff);
276                let elem_mut = cursor.get_mut().unwrap().project();
277                *elem_mut.bitlen = *elem_mut.bitoff + *elem_mut.bitlen - bitmax;
278                *elem_mut.bitoff = bitmax;
279                break;
280            }
281            *this.num_bits = *this.num_bits - elem_bitlen;
282            *this.num_elems -= 1;
283            let erased = cursor.erase().unwrap();
284            release_element(free_list.as_mut().map(Pin::as_mut), erased);
285        }
286        Ok(())
287    }
288}
289
290impl<T> Bitmap<T> for Pin<&mut RleBitmapBase<T>>
291where
292    T: Copy
293        + Eq
294        + Ord
295        + Default
296        + core::ops::Add<Output = T>
297        + core::ops::Sub<Output = T>
298        + From<u8>,
299{
300    fn find(&self, is_set: bool, mut bitoff: T, bitmax: T, run_len: T) -> Result<T, Status> {
301        for elem in self.elems.iter() {
302            if bitoff >= elem.end() {
303                continue;
304            }
305            if bitmax - bitoff < run_len {
306                return Err(Status::NO_RESOURCES);
307            }
308            let elem_min = core::cmp::max(bitoff, elem.bitoff);
309            let elem_max = core::cmp::min(bitmax, elem.end());
310            if is_set && elem_max > elem_min && elem_max - elem_min >= run_len {
311                return Ok(elem_min);
312            }
313            if !is_set && bitoff < elem.bitoff && elem.bitoff - bitoff >= run_len {
314                return Ok(bitoff);
315            }
316            if bitmax < elem.end() {
317                return Err(Status::NO_RESOURCES);
318            }
319            bitoff = elem.end();
320        }
321        if !is_set && bitmax - bitoff >= run_len {
322            return Ok(bitoff);
323        }
324        Err(Status::NO_RESOURCES)
325    }
326
327    fn get(&self, mut bitoff: T, bitmax: T) -> GetResult<T> {
328        for elem in self.elems.iter() {
329            if bitoff < elem.bitoff {
330                break;
331            }
332            if bitoff < elem.bitoff + elem.bitlen {
333                bitoff = elem.bitoff + elem.bitlen;
334                break;
335            }
336        }
337        if bitoff > bitmax {
338            bitoff = bitmax;
339        }
340        GetResult { all_set: bitoff == bitmax, first_unset: bitoff }
341    }
342
343    fn set(&mut self, bitoff: T, bitmax: T) -> Result<(), Status> {
344        self.as_mut().set_internal(bitoff, bitmax, None)
345    }
346
347    fn clear(&mut self, bitoff: T, bitmax: T) -> Result<(), Status> {
348        self.as_mut().clear_internal(bitoff, bitmax, None)
349    }
350
351    fn clear_all(&mut self) {
352        let this = self.as_mut().project();
353        this.elems.clear();
354        *this.num_elems = 0;
355        *this.num_bits = T::default();
356    }
357}
358
359impl<'a, T> IntoIterator for &'a RleBitmapBase<T> {
360    type Item = &'a Element<T>;
361    type IntoIter = fbl::Iterator<'a, ElementPtr<T>>;
362
363    fn into_iter(self) -> Self::IntoIter {
364        self.elems.iter()
365    }
366}
367
368pub type RleBitmap = RleBitmapBase<usize>;
369pub type RleBitmapElement = Element<usize>;
bitmap/rle_bitmap.rs

bitmap/
rle_bitmap.rs
