tess2_rust/
bucketalloc.rs

1// Copyright 2025 Lars Brubaker
2// License: SGI Free Software License B (MIT-compatible)
3//
4// Port of libtess2 bucketalloc.c/h
5//
6// In Rust, the bucket allocator pattern is replaced by Vec-backed arenas.
7// This module provides the BucketAlloc type as a thin wrapper used by the
8// mesh, dict, and region pool subsystems.
9
10/// A simple arena allocator backed by a Vec.
11/// Items are allocated by pushing to the vec and freed via a freelist.
12pub struct BucketAlloc<T> {
13    items: Vec<Option<T>>,
14    free_list: Vec<u32>,
15}
16
17impl<T: Default> BucketAlloc<T> {
18    pub fn new() -> Self {
19        Self {
20            items: Vec::new(),
21            free_list: Vec::new(),
22        }
23    }
24
25    /// Allocate a new item, returning its index.
26    pub fn alloc(&mut self) -> u32 {
27        if let Some(idx) = self.free_list.pop() {
28            self.items[idx as usize] = Some(T::default());
29            idx
30        } else {
31            let idx = self.items.len() as u32;
32            self.items.push(Some(T::default()));
33            idx
34        }
35    }
36
37    /// Free an item by index (returns it to the free list).
38    pub fn free(&mut self, idx: u32) {
39        self.items[idx as usize] = None;
40        self.free_list.push(idx);
41    }
42
43    pub fn get(&self, idx: u32) -> Option<&T> {
44        self.items.get(idx as usize)?.as_ref()
45    }
46
47    pub fn get_mut(&mut self, idx: u32) -> Option<&mut T> {
48        self.items.get_mut(idx as usize)?.as_mut()
49    }
50}
51
52impl<T: Default> Default for BucketAlloc<T> {
53    fn default() -> Self {
54        Self::new()
55    }
56}
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn alloc_and_free() {
64        let mut ba: BucketAlloc<u32> = BucketAlloc::new();
65        let a = ba.alloc();
66        let b = ba.alloc();
67        assert_ne!(a, b);
68        ba.free(a);
69        let c = ba.alloc();
70        // c should reuse a's slot
71        assert_eq!(c, a);
72    }
73
74    #[test]
75    fn get_returns_default() {
76        let mut ba: BucketAlloc<i32> = BucketAlloc::new();
77        let idx = ba.alloc();
78        assert_eq!(*ba.get(idx).unwrap(), 0);
79    }
80
81    #[test]
82    fn get_after_free_returns_none() {
83        let mut ba: BucketAlloc<i32> = BucketAlloc::new();
84        let idx = ba.alloc();
85        ba.free(idx);
86        assert!(ba.get(idx).is_none());
87    }
88}
tess2_rust/bucketalloc.rs

tess2_rust/
bucketalloc.rs
