box2d_rust/
id_pool.rs

1// Port of box2d-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 b2Array(int) free array maps to Vec<i32>.
5//
6// SPDX-FileCopyrightText: 2023 Erin Catto
7// SPDX-License-Identifier: MIT
8
9/// (b2IdPool)
10#[derive(Debug, Clone, Default)]
11pub struct IdPool {
12    pub(crate) free_array: Vec<i32>,
13    pub(crate) next_index: i32,
14}
15
16impl IdPool {
17    /// (b2CreateIdPool)
18    pub fn new() -> IdPool {
19        IdPool {
20            // C: b2Array_CreateN(pool.freeArray, 32) — capacity 32, count 0.
21            free_array: Vec::with_capacity(32),
22            next_index: 0,
23        }
24    }
25
26    /// (b2DestroyIdPool)
27    pub fn destroy(&mut self) {
28        *self = IdPool {
29            free_array: Vec::new(),
30            next_index: 0,
31        };
32    }
33
34    /// (b2AllocId)
35    pub fn alloc_id(&mut self) -> i32 {
36        if let Some(id) = self.free_array.pop() {
37            return id;
38        }
39
40        let id = self.next_index;
41        self.next_index += 1;
42        id
43    }
44
45    /// (b2FreeId)
46    pub fn free_id(&mut self, id: i32) {
47        debug_assert!(self.next_index > 0);
48        debug_assert!(0 <= id && id < self.next_index);
49        self.free_array.push(id);
50    }
51
52    /// (b2GetIdCount)
53    pub fn id_count(&self) -> i32 {
54        self.next_index - self.free_array.len() as i32
55    }
56
57    /// (b2GetIdCapacity)
58    pub fn id_capacity(&self) -> i32 {
59        self.next_index
60    }
61
62    /// (b2GetIdBytes)
63    pub fn id_bytes(&self) -> i32 {
64        (self.free_array.capacity() * core::mem::size_of::<i32>()) as i32
65    }
66
67    /// Debug check that `id` is currently free. (b2ValidateFreeId)
68    pub fn validate_free_id(&self, id: i32) {
69        // B2_VALIDATE: compiled out in release like the C reference
70        if !cfg!(debug_assertions) {
71            return;
72        }
73
74        if self.free_array.contains(&id) {
75            return;
76        }
77
78        debug_assert!(false, "id {id} is not free");
79    }
80
81    /// Debug check that `id` is currently in use. (b2ValidateUsedId)
82    pub fn validate_used_id(&self, id: i32) {
83        // B2_VALIDATE: compiled out in release like the C reference
84        if !cfg!(debug_assertions) {
85            return;
86        }
87
88        debug_assert!(!self.free_array.contains(&id), "id {id} is free");
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    // id_pool has no dedicated C unit test (test_id.c covers the public id
97    // handles); this locks in the allocator behavior.
98    #[test]
99    fn alloc_free_recycle() {
100        let mut pool = IdPool::new();
101
102        assert_eq!(pool.alloc_id(), 0);
103        assert_eq!(pool.alloc_id(), 1);
104        assert_eq!(pool.alloc_id(), 2);
105        assert_eq!(pool.id_count(), 3);
106        assert_eq!(pool.id_capacity(), 3);
107
108        // Free list is LIFO: last freed id is reused first.
109        pool.free_id(1);
110        pool.validate_free_id(1);
111        pool.validate_used_id(2);
112        assert_eq!(pool.id_count(), 2);
113
114        assert_eq!(pool.alloc_id(), 1);
115        assert_eq!(pool.id_count(), 3);
116
117        // Exhausted free list resumes bump allocation.
118        assert_eq!(pool.alloc_id(), 3);
119        assert_eq!(pool.id_capacity(), 4);
120
121        pool.destroy();
122        assert_eq!(pool.id_count(), 0);
123    }
124}
box2d_rust/id_pool.rs

box2d_rust/
id_pool.rs
