idalloc/
lib.rs

1//! A library for different methods of allocating unique identifiers efficiently.
2//!
3//! Provided methods:
4//!
5//! * [Slab] - Allocates id in a slab-like manner, handling automatic
6//!   reclamation by keeping a record of which identifier slot to allocate next.
7//!
8//! # Examples
9//!
10//! ```rust
11//! let mut alloc = idalloc::Slab::<u32>::new();
12//! assert_eq!(0u32, alloc.next());
13//! assert_eq!(1u32, alloc.next());
14//! alloc.free(0u32);
15//! ```
16#[deny(missing_docs)]
17use std::fmt;
18
19/// A type that can be used an allocator index.
20pub trait Id: Copy + fmt::Display + fmt::Debug {
21    /// Allocate the initial, unallocated value.
22    ///
23    /// # Examples
24    ///
25    /// ```rust
26    /// use idalloc::Id as _;
27    ///
28    /// assert_eq!(0, u16::initial());
29    /// assert_eq!(0, u16::initial());
30    /// ```
31    fn initial() -> Self;
32
33    /// Get the index as a usize.
34    ///
35    /// # Examples
36    ///
37    /// ```rust
38    /// use idalloc::Id as _;
39    ///
40    /// assert_eq!(42, 42u16.as_usize());
41    /// assert_eq!(42, 42u32.as_usize());
42    /// ```
43    fn as_usize(self) -> usize;
44
45    /// Increment the index and return the incremented value.
46    ///
47    /// # Examples
48    ///
49    /// ```rust
50    /// use idalloc::Id as _;
51    ///
52    /// assert_eq!(1, 0u16.increment());
53    /// assert_eq!(1, 0u32.increment());
54    /// ```
55    fn increment(self) -> Self;
56
57    /// Take the value and replace the existing value with the none variant.
58    ///
59    /// # Examples
60    ///
61    /// ```rust
62    /// use idalloc::Id as _;
63    ///
64    /// let mut v = 1u32;
65    /// assert_eq!(1u32, v.take());
66    /// assert_eq!(u32::none(), v);
67    /// ```
68    fn take(&mut self) -> Self;
69
70    /// Test if the current value is none, and panic with the given message if
71    /// if is.
72    ///
73    /// # Examples
74    ///
75    /// ```rust
76    /// use idalloc::Id as _;
77    ///
78    /// let mut v = 1u32;
79    /// assert_eq!(1u32, v.expect("value must be defined"));
80    /// ```
81    fn expect(self, m: &str) -> Self;
82
83    /// Construct the none sentinel value for this type.
84    ///
85    /// # Examples
86    ///
87    /// ```rust
88    /// use idalloc::Id as _;
89    ///
90    /// assert!(u32::none().is_none());
91    /// ```
92    fn none() -> Self;
93
94    /// Test if the value is the none sentinel value.
95    ///
96    /// # Examples
97    ///
98    /// ```rust
99    /// use idalloc::Id as _;
100    ///
101    /// assert!(u32::none().is_none());
102    /// ```
103    fn is_none(self) -> bool;
104}
105
106macro_rules! impl_primitive_index {
107    ($ty:ident) => {
108        impl Id for $ty {
109            #[inline(always)]
110            fn initial() -> Self {
111                0
112            }
113
114            #[inline(always)]
115            fn as_usize(self) -> usize {
116                self as usize
117            }
118
119            #[inline(always)]
120            fn increment(self) -> Self {
121                if self.is_none() {
122                    panic!("index `{}` is out of bounds: 0-{}", self, std::$ty::MAX);
123                }
124
125                self + 1
126            }
127
128            #[inline(always)]
129            fn take(&mut self) -> Self {
130                std::mem::replace(self, Self::none())
131            }
132
133            #[inline(always)]
134            fn expect(self, m: &str) -> Self {
135                if self.is_none() {
136                    panic!("{}", m);
137                }
138
139                self
140            }
141
142            #[inline(always)]
143            fn none() -> Self {
144                std::$ty::MAX
145            }
146
147            #[inline(always)]
148            fn is_none(self) -> bool {
149                self == Self::none()
150            }
151        }
152    };
153}
154
155impl_primitive_index!(u8);
156impl_primitive_index!(u16);
157impl_primitive_index!(u32);
158impl_primitive_index!(u64);
159impl_primitive_index!(u128);
160
161/// A slab-based id allocator which can deal with automatic reclamation as ids
162/// are [freed][Slab::free].
163///
164/// # Examples
165///
166/// ```rust
167/// use idalloc::Slab;
168///
169/// let mut alloc = Slab::<u32>::new();
170///
171/// let mut alloc = Slab::<u32>::new();
172/// assert_eq!(0, alloc.next());
173/// assert_eq!(1, alloc.next());
174/// alloc.free(0);
175/// assert_eq!(0, alloc.next());
176/// assert_eq!(2, alloc.next());
177/// alloc.free(0);
178/// alloc.free(0);
179/// alloc.free(1);
180/// assert_eq!(1, alloc.next());
181/// assert_eq!(0, alloc.next());
182/// assert_eq!(3, alloc.next());
183/// ```
184pub struct Slab<I>
185where
186    I: Id,
187{
188    data: Vec<I>,
189    next: I,
190}
191
192impl<I> Slab<I>
193where
194    I: Id,
195{
196    /// Construct a new slab allocator.
197    ///
198    /// # Examples
199    ///
200    /// ```rust
201    /// use idalloc::Slab;
202    ///
203    /// let mut alloc = Slab::<u32>::new();
204    ///
205    /// let mut alloc = Slab::<u32>::new();
206    /// assert_eq!(0, alloc.next());
207    /// assert_eq!(1, alloc.next());
208    /// alloc.free(0);
209    /// assert_eq!(0, alloc.next());
210    /// ```
211    pub fn new() -> Self {
212        Self {
213            data: Vec::new(),
214            next: I::initial(),
215        }
216    }
217
218    /// Allocate the next id.
219    ///
220    /// # Examples
221    ///
222    /// ```rust
223    /// let mut alloc = idalloc::Slab::<u32>::new();
224    /// assert_eq!(0u32, alloc.next());
225    /// assert_eq!(1u32, alloc.next());
226    /// ```
227    pub fn next(&mut self) -> I {
228        let index = self.next;
229
230        self.next = if let Some(entry) = self.data.get_mut(self.next.as_usize()) {
231            entry.take().expect("next index is null")
232        } else {
233            self.data.push(I::none());
234            self.next.increment()
235        };
236
237        index
238    }
239
240    /// Free the specified id.
241    ///
242    /// # Examples
243    ///
244    /// ```rust
245    /// let mut alloc = idalloc::Slab::<u32>::new();
246    /// let id = alloc.next();
247    /// assert!(!alloc.free(id + 1));
248    /// assert!(alloc.free(id));
249    /// assert!(!alloc.free(id));
250    /// ```
251    pub fn free(&mut self, index: I) -> bool {
252        if let Some(entry) = self.data.get_mut(index.as_usize()) {
253            if entry.is_none() {
254                *entry = self.next;
255                self.next = index;
256                return true;
257            }
258        }
259
260        false
261    }
262}
263
264impl<I> Default for Slab<I>
265where
266    I: Id,
267{
268    fn default() -> Self {
269        Self::new()
270    }
271}