intid_allocator/
reusing.rs

1use alloc::collections::BinaryHeap;
2
3use crate::{IdExhaustedError, UniqueIdAllocator};
4use intid::IntegerIdCounter;
5
6/// A type that allocates integer ids,
7/// with the ability to free unused ids back to storage.
8///
9/// This will minimize the integer value of the keys,
10/// reducing memory needed for lookup tables and bitsets.
11/// It is useful in conjunction with the "direct" maps/sets of the [idmap crate][idmap].
12///
13/// If the ability to free unused ids is not necessary,
14/// consider [`crate::UniqueIdAllocator`] or [`crate::UniqueIdAllocatorAtomic`].
15/// These are more efficient and do not require an allocator.
16///
17/// There is not any way to iterate over all currently allocated ids.
18/// With the current implementation (a [`BinaryHeap`]),
19/// it would be difficult to implement without any allocation.
20///
21/// [idmap]: https://docs.rs/idmap/
22pub struct IdAllocator<T: IntegerIdCounter> {
23    next_id: crate::UniqueIdAllocator<T>,
24    /// Tracks freed ids for reuse, preferring smaller ids where possible
25    ///
26    /// The use of a [`BinaryHeap`] here is inspired by the `thread-local` crate.
27    /// No part of the implementation was copied.
28    heap: BinaryHeap<core::cmp::Reverse<intid::utils::OrderByInt<T>>>,
29}
30impl<T: IntegerIdCounter> Default for IdAllocator<T> {
31    fn default() -> Self {
32        Self::new()
33    }
34}
35
36impl<T: IntegerIdCounter> IdAllocator<T> {
37    /// Create a new allocator, with ids starting at [`T::START`] (usually zero).
38    ///
39    /// [`T::START`]: IntegerIdCounter::START
40    #[inline]
41    #[rustversion::attr(since(1.80), const)]
42    pub fn new() -> Self {
43        Self::with_start(T::START)
44    }
45
46    /// Create a new allocator, with ids starting at the specified value.
47    ///
48    /// This function is a `const fn` on all rust versions since 1.80.
49    /// Before that release, it can only be called at runtime.
50    #[inline]
51    #[rustversion::attr(since(1.80), const)]
52    #[rustversion::attr(since(1.80), clippy::msrv = "1.80")]
53    pub fn with_start(start: T) -> Self {
54        IdAllocator {
55            next_id: UniqueIdAllocator::with_start(start),
56            heap: alloc::collections::BinaryHeap::new(),
57        }
58    }
59
60    /// Allocate a new id, reusing freed ids wherever possible.
61    ///
62    /// # Errors
63    /// If no more ids are available, this will return an error.
64    /// This can only happen if the entire range of the [`IntegerIdCounter`]
65    /// has been , and none have been fred
66    #[inline]
67    pub fn try_alloc(&mut self) -> Result<T, IdExhaustedError<T>> {
68        match self.heap.pop() {
69            Some(existing) => Ok(existing.0 .0),
70            None => self.next_id.try_alloc(),
71        }
72    }
73
74    /// Allocate a new id, reusing freed ids wherever possible.
75    ///
76    /// # Panics
77    /// If there are no ids available, this will panic.
78    /// See [`Self::try_alloc`] for a version that returns an error instead.
79    #[track_caller]
80    #[inline]
81    #[must_use]
82    pub fn alloc(&mut self) -> T {
83        match self.try_alloc() {
84            Ok(id) => id,
85            Err(e) => e.panic(),
86        }
87    }
88
89    /// Free all existing ids, resetting the allocator.
90    #[inline]
91    pub fn free_all(&mut self) {
92        self.heap.clear();
93        self.next_id.reset();
94    }
95
96    /// Free the specified id, making it available
97    ///
98    /// Used ids will be used in preference to creating new ones.
99    #[inline]
100    pub fn free(&mut self, id: T) {
101        self.heap
102            .push(core::cmp::Reverse(intid::utils::OrderByInt(id)));
103    }
104}
intid_allocator/reusing.rs

intid_allocator/
reusing.rs
