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}