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_mut().map(|f| &mut **f);
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_mut();
169        loop {
170            let (e_bitoff, e_bitlen) = match cursor.get() {
171                Some(e) => (e.bitoff, e.bitlen),
172                None => break,
173            };
174            if e_bitoff + e_bitlen >= bitoff {
175                break;
176            }
177            cursor.move_next();
178        }
179
180        cursor.insert_before(new_elem);
181        self.num_bits = self.num_bits + bitlen;
182
183        let mut has_successor = false;
184        let mut successor_bitoff = T::default();
185        if let Some(succ) = cursor.get() {
186            has_successor = true;
187            successor_bitoff = succ.bitoff;
188        }
189
190        cursor.move_prev();
191        let mut elem_bitoff = cursor.get().unwrap().bitoff;
192        let mut elem_bitlen = cursor.get().unwrap().bitlen;
193
194        if has_successor && elem_bitoff >= successor_bitoff {
195            let diff = elem_bitoff - successor_bitoff;
196            elem_bitlen = elem_bitlen + diff;
197            elem_bitoff = successor_bitoff;
198            let elem = cursor.get_mut().unwrap();
199            elem.bitoff = elem_bitoff;
200            elem.bitlen = elem_bitlen;
201            self.num_bits = self.num_bits + diff;
202        }
203
204        cursor.move_next();
205        let mut max = elem_bitoff + elem_bitlen;
206        loop {
207            let (succ_bitoff, succ_bitlen) = match cursor.get() {
208                Some(s) => (s.bitoff, s.bitlen),
209                None => break,
210            };
211            if succ_bitoff > max {
212                break;
213            }
214            let succ_max = succ_bitoff + succ_bitlen;
215            max = core::cmp::max(max, succ_max);
216            self.num_bits = self.num_bits - elem_bitlen - succ_bitlen + (max - elem_bitoff);
217            elem_bitlen = max - elem_bitoff;
218            let erased = cursor.erase().unwrap();
219            self.num_elems -= 1;
220            let free_list_ref = free_list.as_mut().map(|f| &mut **f);
221            release_element(free_list_ref, erased);
222        }
223
224        cursor.move_prev();
225        cursor.get_mut().unwrap().bitlen = elem_bitlen;
226        Ok(())
227    }
228
229    fn clear_internal(
230        &mut self,
231        bitoff: T,
232        bitmax: T,
233        mut free_list: Option<&mut FreeList<T>>,
234    ) -> Result<(), Status> {
235        if bitmax < bitoff {
236            return Err(Status::INVALID_ARGS);
237        }
238        let bitlen = bitmax - bitoff;
239        if bitlen == T::default() {
240            return Ok(());
241        }
242
243        let mut cursor = self.elems.cursor_mut();
244        loop {
245            let (elem_bitoff, elem_bitlen) = match cursor.get() {
246                Some(e) => (e.bitoff, e.bitlen),
247                None => break,
248            };
249
250            if elem_bitoff + elem_bitlen < bitoff {
251                cursor.move_next();
252                continue;
253            }
254            if bitmax < elem_bitoff {
255                break;
256            }
257            if elem_bitoff < bitoff {
258                if elem_bitoff + elem_bitlen <= bitmax {
259                    let new_bitlen = bitoff - elem_bitoff;
260                    self.num_bits = self.num_bits - (elem_bitlen - new_bitlen);
261                    cursor.get_mut().unwrap().bitlen = new_bitlen;
262                    cursor.move_next();
263                    continue;
264                }
265                let free_list_ref = free_list.as_mut().map(|f| &mut **f);
266                let mut new_elem = allocate_element(free_list_ref)?;
267                self.num_elems += 1;
268                new_elem.bitoff = bitmax;
269                new_elem.bitlen = elem_bitoff + elem_bitlen - bitmax;
270                cursor.insert_after(new_elem);
271                let new_bitlen = bitoff - elem_bitoff;
272                self.num_bits = self.num_bits - (bitmax - bitoff);
273                cursor.get_mut().unwrap().bitlen = new_bitlen;
274                break;
275            }
276            if bitmax < elem_bitoff + elem_bitlen {
277                self.num_bits = self.num_bits - (bitmax - elem_bitoff);
278                let elem_mut = cursor.get_mut().unwrap();
279                elem_mut.bitlen = elem_mut.bitoff + elem_mut.bitlen - bitmax;
280                elem_mut.bitoff = bitmax;
281                break;
282            }
283            self.num_bits = self.num_bits - elem_bitlen;
284            self.num_elems -= 1;
285            let erased = cursor.erase().unwrap();
286            let free_list_ref = free_list.as_mut().map(|f| &mut **f);
287            release_element(free_list_ref, erased);
288        }
289        Ok(())
290    }
291}
292
293impl<T> Bitmap<T> for RleBitmapBase<T>
294where
295    T: Copy
296        + Eq
297        + Ord
298        + Default
299        + core::ops::Add<Output = T>
300        + core::ops::Sub<Output = T>
301        + From<u8>,
302{
303    fn find(&self, is_set: bool, mut bitoff: T, bitmax: T, run_len: T) -> Result<T, Status> {
304        for elem in self.elems.iter() {
305            if bitoff >= elem.end() {
306                continue;
307            }
308            if bitmax - bitoff < run_len {
309                return Err(Status::NO_RESOURCES);
310            }
311            let elem_min = core::cmp::max(bitoff, elem.bitoff);
312            let elem_max = core::cmp::min(bitmax, elem.end());
313            if is_set && elem_max > elem_min && elem_max - elem_min >= run_len {
314                return Ok(elem_min);
315            }
316            if !is_set && bitoff < elem.bitoff && elem.bitoff - bitoff >= run_len {
317                return Ok(bitoff);
318            }
319            if bitmax < elem.end() {
320                return Err(Status::NO_RESOURCES);
321            }
322            bitoff = elem.end();
323        }
324        if !is_set && bitmax - bitoff >= run_len {
325            return Ok(bitoff);
326        }
327        Err(Status::NO_RESOURCES)
328    }
329
330    fn get(&self, mut bitoff: T, bitmax: T) -> GetResult<T> {
331        for elem in self.elems.iter() {
332            if bitoff < elem.bitoff {
333                break;
334            }
335            if bitoff < elem.bitoff + elem.bitlen {
336                bitoff = elem.bitoff + elem.bitlen;
337                break;
338            }
339        }
340        if bitoff > bitmax {
341            bitoff = bitmax;
342        }
343        GetResult { all_set: bitoff == bitmax, first_unset: bitoff }
344    }
345
346    fn set(&mut self, bitoff: T, bitmax: T) -> Result<(), Status> {
347        self.set_internal(bitoff, bitmax, None)
348    }
349
350    fn clear(&mut self, bitoff: T, bitmax: T) -> Result<(), Status> {
351        self.clear_internal(bitoff, bitmax, None)
352    }
353
354    fn clear_all(&mut self) {
355        self.elems.clear();
356        self.num_elems = 0;
357        self.num_bits = T::default();
358    }
359}
360
361impl<'a, T> IntoIterator for &'a RleBitmapBase<T> {
362    type Item = &'a Element<T>;
363    type IntoIter = fbl::Iterator<'a, ElementPtr<T>>;
364
365    fn into_iter(self) -> Self::IntoIter {
366        self.elems.iter()
367    }
368}
369
370pub type RleBitmap = RleBitmapBase<usize>;
371pub type RleBitmapElement = Element<usize>;
bitmap/rle_bitmap.rs

bitmap/
rle_bitmap.rs
