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

bitmap/
rle_bitmap.rs
