intid_allocator/
reusing.rs

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

intid_allocator/
reusing.rs
