avian3d/data_structures/
id_pool.rs

1//! An [`IdPool`] for managing and reusing identifiers.
2
3use alloc::collections::BinaryHeap;
4use core::cmp::Reverse;
5
6/// A pool for efficient allocation and reuse of `u32` identifiers.
7///
8/// Freed IDs are stored in a min-heap, and reused such that the lowest available IDs are allocated first.
9#[derive(Clone, Debug, Default)]
10#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
11pub struct IdPool {
12    /// A min-heap of free IDs. The lowest free IDs are allocated first.
13    free_ids: BinaryHeap<Reverse<u32>>,
14    /// The next ID to be allocated. Only incremented when no free IDs are available.
15    next_index: u32,
16}
17
18impl IdPool {
19    /// Creates a new empty [`IdPool`].
20    #[inline(always)]
21    pub const fn new() -> Self {
22        Self {
23            free_ids: BinaryHeap::new(),
24            next_index: 0,
25        }
26    }
27
28    /// Creates a new [`IdPool`] with the given initial capacity.
29    ///
30    /// This is useful for preallocating space for IDs to avoid reallocations.
31    #[inline(always)]
32    pub fn with_capacity(capacity: usize) -> Self {
33        Self {
34            free_ids: BinaryHeap::with_capacity(capacity),
35            next_index: 0,
36        }
37    }
38
39    /// Allocates a new ID.
40    ///
41    /// If there are free IDs available, the lowest free ID is reused.
42    #[inline(always)]
43    pub fn alloc(&mut self) -> u32 {
44        if let Some(id) = self.free_ids.pop() {
45            id.0
46        } else {
47            let id = self.next_index;
48            self.next_index += 1;
49            id
50        }
51    }
52
53    /// Frees an ID, making it available for reuse.
54    ///
55    /// The ID is assumed to not already be freed.
56    #[inline(always)]
57    pub fn free(&mut self, id: u32) {
58        debug_assert!(id < self.next_index);
59        self.free_ids.push(Reverse(id));
60    }
61
62    /// Clears the pool, removing all free IDs and resetting the next index.
63    #[inline(always)]
64    pub fn clear(&mut self) {
65        self.free_ids.clear();
66        self.next_index = 0;
67    }
68
69    /// Returns the next ID that will be allocated.
70    #[inline(always)]
71    pub fn next_id(&self) -> u32 {
72        if let Some(id) = self.free_ids.peek() {
73            id.0
74        } else {
75            self.next_index
76        }
77    }
78
79    /// Returns the number of allocated IDs.
80    #[inline(always)]
81    pub fn len(&self) -> usize {
82        self.next_index as usize - self.free_ids.len()
83    }
84
85    /// Returns the number of free IDs.
86    #[inline(always)]
87    pub fn free_len(&self) -> usize {
88        self.free_ids.len()
89    }
90
91    /// Returns the total number of IDs (allocated + free).
92    #[inline(always)]
93    pub fn total_len(&self) -> usize {
94        self.next_index as usize
95    }
96
97    /// Returns `true` if the pool is empty (no allocated IDs).
98    #[inline(always)]
99    pub fn is_empty(&self) -> bool {
100        self.len() == 0
101    }
102}
avian3d/data_structures/id_pool.rs

avian3d/data_structures/
id_pool.rs
