box3d_rust/
id_pool.rs

1// Port of box3d-cpp-reference/src/id_pool.h and src/id_pool.c
2//
3// An index allocator with a free list: ids are dense while allocated and
4// recycled LIFO. The C b3Array(int) free array maps to Vec<i32>.
5//
6// SPDX-FileCopyrightText: 2025 Erin Catto
7// SPDX-License-Identifier: MIT
8
9/// (b3IdPool)
10#[derive(Debug, Clone, Default)]
11pub struct IdPool {
12    /// Free-list of recycled ids. C: `b3Array(int) freeArray` → `Vec<i32>`.
13    pub(crate) free_array: Vec<i32>,
14    pub(crate) next_index: i32,
15}
16
17impl IdPool {
18    /// (b3CreateIdPool)
19    pub fn new() -> IdPool {
20        IdPool {
21            // C: b3Array_Reserve(pool.freeArray, 32) — capacity 32, count 0.
22            free_array: Vec::with_capacity(32),
23            next_index: 0,
24        }
25    }
26
27    /// (b3DestroyIdPool)
28    pub fn destroy(&mut self) {
29        *self = IdPool {
30            free_array: Vec::new(),
31            next_index: 0,
32        };
33    }
34
35    /// (b3AllocId)
36    pub fn alloc_id(&mut self) -> i32 {
37        if let Some(id) = self.free_array.pop() {
38            return id;
39        }
40
41        let id = self.next_index;
42        self.next_index += 1;
43        id
44    }
45
46    /// (b3FreeId)
47    ///
48    /// C has a dead shrink branch (`if id == nextIndex`) that is unreachable
49    /// under the asserts above it (`id < nextIndex`). Always push, matching
50    /// the reachable C path and box2d-rust.
51    pub fn free_id(&mut self, id: i32) {
52        debug_assert!(self.next_index > 0);
53        debug_assert!(0 <= id && id < self.next_index);
54        self.free_array.push(id);
55    }
56
57    /// (b3GetIdCount)
58    pub fn id_count(&self) -> i32 {
59        self.next_index - self.free_array.len() as i32
60    }
61
62    /// (b3GetIdCapacity)
63    pub fn id_capacity(&self) -> i32 {
64        self.next_index
65    }
66
67    /// (b3GetIdBytes)
68    pub fn id_bytes(&self) -> i32 {
69        // C: b3Array_ByteCount(a) = capacity * sizeof(*data)
70        (self.free_array.capacity() * core::mem::size_of::<i32>()) as i32
71    }
72
73    /// Debug check that `id` is currently free. (b3ValidateFreeId)
74    pub fn validate_free_id(&self, id: i32) {
75        if self.free_array.contains(&id) {
76            return;
77        }
78
79        debug_assert!(false, "id {id} is not free");
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    // id_pool has no dedicated C unit test; this locks in the allocator behavior.
88    #[test]
89    fn alloc_free_recycle() {
90        let mut pool = IdPool::new();
91
92        assert_eq!(pool.alloc_id(), 0);
93        assert_eq!(pool.alloc_id(), 1);
94        assert_eq!(pool.alloc_id(), 2);
95        assert_eq!(pool.id_count(), 3);
96        assert_eq!(pool.id_capacity(), 3);
97
98        // Free list is LIFO: last freed id is reused first.
99        pool.free_id(1);
100        pool.validate_free_id(1);
101        assert_eq!(pool.id_count(), 2);
102
103        assert_eq!(pool.alloc_id(), 1);
104        assert_eq!(pool.id_count(), 3);
105
106        // Exhausted free list resumes bump allocation.
107        assert_eq!(pool.alloc_id(), 3);
108        assert_eq!(pool.id_capacity(), 4);
109
110        pool.destroy();
111        assert_eq!(pool.id_count(), 0);
112    }
113}
box3d_rust/id_pool.rs

box3d_rust/
id_pool.rs
