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    free_array: Vec<i32>,
13    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        if self.free_array.contains(&id) {
70            return;
71        }
72
73        debug_assert!(false, "id {id} is not free");
74    }
75
76    /// Debug check that `id` is currently in use. (b2ValidateUsedId)
77    pub fn validate_used_id(&self, id: i32) {
78        debug_assert!(!self.free_array.contains(&id), "id {id} is free");
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    // id_pool has no dedicated C unit test (test_id.c covers the public id
87    // handles); 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        pool.validate_used_id(2);
102        assert_eq!(pool.id_count(), 2);
103
104        assert_eq!(pool.alloc_id(), 1);
105        assert_eq!(pool.id_count(), 3);
106
107        // Exhausted free list resumes bump allocation.
108        assert_eq!(pool.alloc_id(), 3);
109        assert_eq!(pool.id_capacity(), 4);
110
111        pool.destroy();
112        assert_eq!(pool.id_count(), 0);
113    }
114}
box2d_rust/id_pool.rs

box2d_rust/
id_pool.rs
